改进的雪花算法——解决时钟回拨问题

原创 公众号: 软件设计活跃区

改进的雪花算法——姑且称为梨花算法吧（忽如一夜春风来，千树万树梨花开）。

改进目标：解决雪花算法的时钟回拨问题；部分避免机器id重复时，号码冲突问题。

                      

分布式唯一ID的方案有很多，雪花算法，组成结构大致分为为符号位、时间位、机器位和序列号位。其特点是趋势递增、有序、纯数字组成查询效率高且不依赖于数据库。适合在分布式的场景中应用，可根据需求调整具体实现细节。

 

snowflake算法

这种方案把64-bit分别划分成多段，分开来标示机器、时间等，比如在snowflake中的64-bit分别表示如下图（图片来自网络）所示：

 

 

snowflake算法得到的ID是分段组成的：

•     1bit：符号位，固定是0，表示全部ID都是正整数

•     与指定日期的时间差（毫秒级），41位，够用69年

•     集群ID 机器ID， 10位，最多支持1024台机器

•     序列，12位，每台机器每毫秒内最多产生4096个序列号

 

41-bit的时间可以表示（1L<<41）/(1000L*3600*24*365)=69年的时间，10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s，这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。

这种方式的优缺点是：

优点：

•   毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。

作为DB表的主键，索引效率高。

•   不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。

高性能高可用：生成时不依赖于数据库，完全在内存中生成。

容量大：每秒中能生成数百万的自增ID。

•   可以根据自身业务特性分配bit位，非常灵活。

 

缺点：

•     强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

•     可能会出现不是全局递增的情况。

 

改进的雪花算法——姑且称为梨花算法吧（忽如一夜春风来，千树万树梨花开）。

改进目标：解决雪花算法的时钟回拨问题；部分避免机器id重复时，号码冲突问题。

 

long型的64位分成以下几个部分组成：

符号位：1位

时间：31位   （精确到秒）够用68年

段号(批次号)：3位    每秒可分为8个段

机器id号：10位   最多支持1024台机器

序列号：19位   可表示:0--524287

 

如下图所示：

 

 

注：根据情况，机器id号可以放到最后部分。

 

(一)

经过调整，时间只对秒灵敏，成功回避了服务器间几百毫秒的时间误差引起的时间回拨问题；若第59秒的8个段号没有用完，则当润秒来临时，还可继续使用。另外具体实现上，可设置一定的秒数（如3秒）内提前消费。比如第10秒的号码，在800毫秒用完了，可以继续使用第11秒的号码。这样，下1秒用的号码不是很多时，就可以借给上1秒使用。

       以上的方案是与时间强相关的。若某一段时间内的号码没用使用，也会浪费掉。当在分布式DB的表主键这种应用场景时，只需要全局id不重复，且是递增的。类似这种场景，可以设计成时间不相关的。

(二)

供分布式DB表主键等类似场景使用的,不浪费号码的方案。long型的64位分配还是一样。只不过，取号时，是取上一个号码加1，而不用管现在的时间是什么时候。当突然down机时，重启又获取当前的时间，重新开始分派号码；这时之前节省下的号码就被浪费掉了。为解决这个问题，可以在一段时间或分派一定数量的号（如10000），就将当前分派的号码记录到日志，或同步到DB表，等重启时，可以设置初始值。实现上，还是要控制分派的速度，若每秒几百万的号不够用，可用表名分隔命名空间，每个表单独取自己的号；即使号码够用，也可以这样做，因为这样得到的号在同一张表里就比较连续，而不只是递增而矣。当各个机器分派的id速度相差太大时，各机器得到的id大小就比较乱；这种问题，可以设置负载均衡，让每台机器轮流出号。

(三)

机器id重复的问题。当两台机器的id一样时，分派的号就会重复。若0-7八个段号（段号3位），每次都是从0-3随机获取一个开始的段号，比方说获取到2，那重复机器id的服务要是获取到0或1的段号就可以避免号码重复的冲突。当然了，这都是基于每秒用不完号码的情况下的。可以循环使用段号，如获取到3，那就从3-7,0,1,2这样使用段号，后面0，1，2这几个段号要是分派出去，号码就不递增了。具体怎么用，还是要根据自己的情况做取舍。

 

   Java版的梨花算法实现，期待下期与你一起讨论！   

(  已实现, 有三种方式.

#1:SerialUniqueId  ,2:OneTimeSnowflakeId  ,3:PearFlowerId. default is 1.
bee.distribution.genid.idGenerator=1

源码地址:

https://github.com/automvc/bee

https://gitee.com/automvc/bee

https://github.com/automvc/bee/blob/master/src/main/java/org/teasoft/bee/distribution/GenId.java

)

   欢迎关注微信公众号！

  长按二维码可关注(公众号: AiTeaSoft)

        更多重磅文章等着你!

 

QQ群:   992650213

微信群:    IT软件设计交流群3

 

相关:

教你如何避开雪花算法的坑

https://blog.csdn.net/abckingaa/article/details/108653637