1. 9IM首页
  2. 热点

Leaf和uid-generator存在的一些问题及如何进行优化改进

百度的uid-generator

默认模式

每次启动时向数据库插入一条数据,这行数据的主键是自增的,主键id就是workId,

因为默认是snowflake算法是1标志位+41位时间戳+10位机器号+12位序列号,

因为百度的是每次启动都获取新的机器号,所以它修改了这些位数配比,是

1标志位+28位的时间差+22位的机器号+13位的序列号,所以总共支出2的22次方次启动,也就是400万次启动。

解决时间回拨问题:

  • 启动时时间回拨

因为是每次都用新的机器号,所以当前机器号都是之前没有的,所以即便时间戳回拨也不影响。

  • 运行时时间回拨

会使用lastSecond来记录上次生成id的时间戳,如果当前时间戳比lastSecond还小,就抛出异常。

缓存模式

主要继承自默认模式,只是用一个环形数组来存储生成好的id,每次去环形数组中去,默认大小是2的13次方,8192。这种模式使用的时间取得不是实时的系统时间,而且使用启动时的时间,每次生成一组id时,对之前保存的时间+1。

阀值检测,然后填充

取id时,可用id数小于阀值50%时,去填充

定期填充

会去检查环形数组中id使用情况,然后生成一组最大序列号个数的id(默认是8192个),然后进行填充,多的直接丢弃掉,

美团的leaf

snowflake模式

1位的符号位+41位的时间戳+10位的workID+10位的序列号

1 .时钟回拨问题

若机器出现时钟回拨,会产生重复id

1)启动时回拨

启动时获取其他机器的时间,计算出平均时间后,将本机时间与平均时间比较,若超过阈值则启动失败。

2)运行时回拨
  1. 直接拒绝,抛异常
  2. 若回拨时间小于阈值,则睡眠
  3. 若回拨时间大于阈值,直接拒绝服务并报错,或者更换机器号,或者利用拓展位

2.时间类型

  • 时间戳:自1970.01.01起(今日头条)
  • 时间差:自选起始时间(百度、美团)
时间精度
  • 秒级:支持峰值更高(今日头条、百度)
  • 毫秒级:记录时间粒度更细(美团)

汽车之家是自增的id,只是作品类型不同,文章,视频等

头条,百度,美团也是使用了snowFlake只是改变了位数占比。

比如头条是去掉了符号标示位,缩短了时间戳,前31位是秒级时间戳+自定义的序列(可能是机器id+递增的数),记录的时间粒度会粗一些,每一秒生成的id会少一些,但是支持的峰值会高一些,时间戳也可以不从1970年开始选,也可以从自定义的时间开始选,这样支持的年长会多一些。

3 .机器号

纯机器号,或,机房号+机器号

1)物理机
  • 手动配置
  • zookeeper(美团) 在zookeeper如未注册则创建持久顺序节点,顺序号当机器号,并本地缓存
2)虚拟机
  • redis 利用redis原子计数器,虚拟机启动后,请求计数器,按机器号位数取余
  • zookeeper 从0到机器号上限,在zookeeper尝试创建临时节点,成功则为当前机器号
  • 数据库(百度) 利用系统变量的host和port为唯一索引,在数据库中存取,主键作为机器id

缺点是

1.趋势递增,容易被猜到订单量,第一条下单多少,第二条下单多少,可以自己加随机数。

2.依赖机器时间,如果机器时间出现回拨,变成以前的时间,可能会导致id重复。

解决回拨的问题

就是机器需要同步时间,不一致会对时间回拨,可能会导致id重复,像百度的snowflake是几台特定的服务器,每次的机器id也是从数据库里面生成的,所以不需要做时间同步。

4.类snowflake算法

采用snowflake算法思想,类snowflake算法根据各自业务需要,做出了不同改动。比如改变了位数占比,添加了业务线等其他信息

厂商长度组合说明
美团Leaf64位1+41+10+12沿用snowflake方案的bit位设计,1符号位+41位毫秒时间戳+10位机器位+12位序列号,只不过41位毫秒时间戳存的是某个指定时间点后的时间差
百度UidGenerator64位1+28+22+131符号位+28秒级时间差(最多可支持约8.7年)+22位机器号(最多可支持约420w次机器启动)+13位序列号
今日头条-文章64位1+31+321符号位+31秒级时间戳+32位其他
今日头条-微头条52位1+31+201符号位+31秒级时间戳+20位其他
我们自己的方案54位1+30+10+13其实跟百度的方案类似,只是调小了机器位分配,增大了时间位,因为百度值支持8.7年,我们的可以支持34年生成出来的结果,转换10进制是最小14位,目前最大id是15位(因为目前时间距离自定义的时间点比较近)
附:位数对应
二进制45-47位48-50位51-54位55-57位58-60位61-64位
十进制14位15位16位17位18位19位

原创文章,作者:9IM,如若转载,请注明出处:https://www.9im.cn/821.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注