分布式ID详解

背景

分布式ID：用在分布式系统中
在我们的业务需求中通常有需要一些唯一的ID，来记录我们某个数据的标识:

• 某个用户的ID
• 某个订单的单号
• 某个信息的ID

为什么需要分布式ID

1.如果id我们使用的是数据库的自增长类型，在分布式系统中需要分库和分表，会有两个相同的表，有可能产生主键冲突

分布式ID类型：全球唯一，不会冲突

• UUID:全球唯一：字符串
• 数据库表来维护ID ：新建一张表来产生ID，使用哪种数据库由自己选择Mysql、MongoDB、Redis,性能不好：字符串或数字类型
• 雪花ID：时间戳的类型：数值：每次产生的数值会越来越大，递增型

选择的标准是什么？

根据数据库的存储结构来定，mysql底层用的是Innodb引擎,底层存储结构是B+树,大家可以去https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
用B+Tree插入String类型数据，从插入第四个字符串开始看
第四个字符串是从树的右边插入的
第五个字符串是从树中间插入的
第六个客串是从树的左边插入的

当往B+树中插入字符串，不确定会往树的哪个地方插，这样会破坏这颗树，
结论：

• 字符串类型：不知道往树的哪个节点插，性能底
  而UUID使用的是字符串，如果存储在mysql中，会破坏底层B+树，从而造成性能比较低，因为你要根据id查询，到时候查询就会比较慢。

所以我们选用数值类型作为分布式ID
那么数值类型中又应该如何筛选呢
我在里面插入的数值是越来越大的，而且每次都是往树的右节点插入的
而最后，我插入小值时，就不确定它往树的哪边插入，这样就会像插入字符串一样，破坏树的结构

数值越来越大时，就会一直往树的最右节点插入
最终结论

• 数值类型：递增的数字类型，数字永远在树的最右边，查询快，性能好
  而分布式id：要支持高并发，mysql的支持的并发量比较少，如果使用redis的话，要自己写一些算法策略，所以我们选择开源的分布式ID：雪花ID:推特公司推出的分布式id算法实现

雪花ID

雪花：自然界中不存在两片一毛一样的雪花，唯一，与时间有关，递增
简单原理：

• 雪花算法会生成一个64位的二进制数据等于8byte[字节]，为一个Long型。(转换成字符串后长度最多19) ，其基本结构：
  

第一部分：备用

第二部分：时间戳：由于是二进制，所以是2的41次方得到毫秒值，再计算是年份69年，41位为毫秒级时间(41位的长度可以使用69年) 如果大于69年，就会使用第一部分，时间戳只会越来越大

第三部分：用来记录机器ID，一般用前5位代表数据中心，后面5位是某个数据中心的机器ID(10位的长度最多支持部署1024个节点【集群】）

第四部分：***：支持并发，逐渐递增 ，2的12次方=4096，也就是一毫秒内支持产生4096个id，一秒4096*100=4096000，所以一台机器每秒的并发可以支持4096000，但是经测试snowflake每秒能够产生26万个ID。

snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。经测试snowflake每秒能够产生26万个ID。