分布式唯一ID —— 雪花算法(snowflake)


雪花算法(snowflake)

算法描述:

  • 最高位是符号位,始终为0,不可用。
  • 41位的时间序列,精确到毫秒级,41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。
  • 10位的机器标识,10位的长度最多支持部署1024个节点。
  • 12位的计数序列号,序列号即一系列的自增id,可以支持同一节点同一毫秒生成多个ID序号,12位的计数序列号支持每个节点每毫秒产生4096个ID序号。

缺点:

  1. 时钟回拨问题;
  2. 趋势递增,而不是绝对递增;
  3. 不能在一台服务器上部署多个分布式ID服务;


Twitter实现

GitHub:https://github.com/twitter-archive/snowflake

官方文档:https://twitter.github.io/twitter-server/

Mybatis采用默认的twitter-snowflake,没有解决时钟回拨问题;



Baidu实现

GitHub:https://github.com/baidu/uid-generator

Snowflake算法描述:指定机器 & 同一时刻 & 某一并发序列,是唯一的。据此可生成一个64 bits的唯一ID(long)。默认采用上图字节分配方式:

  • sign(1bit)
    固定1bit符号标识,即生成的UID为正数。
  • delta seconds (28 bits)
    当前时间,相对于时间基点”2016-05-20”的增量值,单位:秒,最多可支持约8.7年(2的28次方/86400=3106.89天)
  • worker id (22 bits)
    机器id,最多可支持约420w次机器启动(2的22次方是4194304)。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略。
  • sequence (13 bits)
    每秒下的并发序列,13 bits可支持每秒8192个并发。

CachedUidGenerator

RingBuffer环形数组,数组每个元素成为一个slot。RingBuffer容量,默认为Snowflake算法中sequence最大值,且为2^N。可通过boostPower配置进行扩容,以提高RingBuffer 读写吞吐量。

Tail指针、Cursor指针用于环形数组上读写slot:

  • Tail指针
    表示Producer生产的最大序号(此序号从0开始,持续递增)。Tail不能超过Cursor,即生产者不能覆盖未消费的slot。当Tail已赶上curosr,此时可通过rejectedPutBufferHandler指定PutRejectPolicy
  • Cursor指针
    表示Consumer消费到的最小序号(序号序列与Producer序列相同)。Cursor不能超过Tail,即不能消费未生产的slot。当Cursor已赶上tail,此时可通过rejectedTakeBufferHandler指定TakeRejectPolicy

CachedUidGenerator采用了双RingBuffer,Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)

由于数组元素在内存中是连续分配的,可最大程度利用CPU cache以提升性能。但同时会带来「伪共享」FalseSharing问题,为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine 补齐方式。

RingBuffer填充时机

  • 初始化预填充
    RingBuffer初始化时,预先填充满整个RingBuffer.
  • 即时填充
    Take消费时,即时检查剩余可用slot量(tail - cursor),如小于设定阈值,则补全空闲slots。阈值可通过paddingFactor来进行配置,请参考Quick Start中CachedUidGenerator配置
  • 周期填充
    通过Schedule线程,定时补全空闲slots。可通过scheduleInterval配置,以应用定时填充功能,并指定Schedule时间间隔

CachedUidGenerator在初始化时除了给workerId赋值,还会初始化RingBuffer。这个过程主要工作有:

  1. 根据boostPower的值确定RingBuffer的size;
  2. 构造RingBuffer,默认paddingFactor为50。这个值的意思是当RingBuffer中剩余可用ID数量少于50%的时候,就会触发一个异步线程往RingBuffer中填充新的唯一ID(调用BufferPaddingExecutor中的paddingBuffer()方法,这个线程中会有一个标志位running控制并发问题),直到填满为止;
  3. 判断是否配置了属性scheduleInterval,这是另外一种RingBuffer填充机制, 在Schedule线程中, 周期性检查填充。默认:不配置, 即不使用Schedule线程. 如需使用, 请指定Schedule线程时间间隔, 单位:秒;
  4. 初始化Put操作拒绝策略,对应属性rejectedPutBufferHandler。即当RingBuffer已满, 无法继续填充时的操作策略。默认无需指定, 将丢弃Put操作, 仅日志记录. 如有特殊需求, 请实现RejectedPutBufferHandler接口(支持Lambda表达式);
  5. 初始化Take操作拒绝策略,对应属性rejectedTakeBufferHandler。即当环已空, 无法继续获取时的操作策略。默认无需指定, 将记录日志, 并抛出UidGenerateException异常. 如有特殊需求, 请实现RejectedTakeBufferHandler接口;
  6. 初始化填满RingBuffer中所有slot(即塞满唯一ID,这一步和第2步骤一样都是调用BufferPaddingExecutor中的paddingBuffer()方法);
  7. 开启buffer补丁线程(前提是配置了属性scheduleInterval),原理就是利用ScheduledExecutorService的scheduleWithFixedDelay()方法。

解决时钟回拨

第二步的异步线程实现非常重要,也是UidGenerator解决时钟回拨的关键:在满足填充新的唯一ID条件时,通过时间值递增得到新的时间值(lastSecond.incrementAndGet()),而不是System.currentTimeMillis()这种方式,而lastSecond是AtomicLong类型,所以能保证线程安全问题

​ 传统的雪花算法实现都是通过System.currentTimeMillis()来获取时间并与上一次时间进行比较,这样的实现严重依赖服务器的时间。而UidGenerator的时间类型是AtomicLong,且通过incrementAndGet()方法获取下一次的时间,从而脱离了对服务器时间的依赖,也就不会有时钟回拨的问题(这种做法也有一个小问题,即分布式ID中的时间信息可能并不是这个ID真正产生的时间点,例如:获取的某分布式ID的值为3200169789968523265,它的反解析结果为{“timestamp”:”2019-05-02 23:26:39”,”workerId”:”21”,”sequence”:”1”},但是这个ID可能并不是在”2019-05-02 23:26:39”这个时间产生的)。