雪花算法源码分析及实践

一、雪花算法简介

雪花算法（Snowflake）是一种生成分布式全局唯一ID的算法，这种算法由Twitter创建并开源。

雪花算法由64位的二进制组成，刚好可以用一个Long类型存储，一共包含四个部分：

符号	时间戳	数据中心和机器ID	序列号
1 bit	41 bits	10 bits	12 bits

• 1位是符号位，没有被使用，始终是0
• 41位是时间戳，具体到毫秒，表示现在至1970年以来的毫秒数，最多可用69年
• 10位是数据中心和机器ID，10位最多可以表示1024台机器
• 12位是序列号，表示毫秒内生成的序列号，每毫秒最多可生成4096个ID

二、雪花算法源码(java)

雪花算法Java版本源码来自beyondfengyu的github：Snowflake

/**
 * twitter的snowflake算法 -- java实现
 * 
 * @author beyond
 * @date 2016/11/26
 */
public class SnowFlake {

    /**
     * 起始的时间戳
     */
    private final static long START_STMP = 1480166465631L;

    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12; //序列号占用的位数
    private final static long MACHINE_BIT = 5;   //机器标识占用的位数
    private final static long DATACENTER_BIT = 5;//数据中心占用的位数

    /**
     * 每一部分的最大值
     * 二进制位运算过程如下：
     * 负数的二进制用补码（整数的二进制位取反后加一）表示，-1的补码的二进制位全部为1，进行`<<`左移运算后低位补0，高位全部都是1
     * 再与-1进行`^`异或运算（这里可以替换为`~`取反运算），则高位全部变为0，低位变为1
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    private long datacenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastStmp = -1L;//上一次时间戳

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                | datacenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

    private long getNewstmp() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }

    }
}

上述代码中有两个关键的步骤:

• 获取ID时，如果在同一毫秒内，则在序列号上递增
• 如果同一毫秒内的序列号已经递增到最大值4095，则通过循坏阻塞直到下一毫秒到来

所以雪花算法每毫秒最多可生成4096个ID，每秒最多可生成400万+的ID。

三、时钟回拨

从上述雪花算法的组成及源码可以看出，雪花算法是强依赖于机器时间的，如果机器发生了时钟回拨，则就会产生重复ID，所以必须解决时钟回拨的问题，防止影响业务。

3.1 解决方案

时钟回拨后不生成ID，循环等待时间点到达

• 优点：实现简单，适合时间较小的时钟回拨
• 缺点：回拨时间间隔较大时，会造成业务阻塞

使用LRU缓存近一段时间内每毫秒内的最大序列号

使用LRU缓存近一段时间内每一毫秒的最大序列号，如果发生时钟回拨，则从最大序列号继续递增，适合小范围内时钟回拨

• 优点：实现简单，适合小范围时间回拨
• 缺点：当回拨时间较长时，需要缓存数据量太大

设置备用的数据中心

为每个节点预留一个备用的配置中心ID，当出现时钟回拨时，切换到备用的数据中心生成ID，时钟到达正常时间切换回原来的数据中心ID。

• 优点：实现简单，适合任意范围内的时钟回拨
• 缺点： 需要占用掉一部分数据中心ID作为备用

以上几种方式都没有考虑服务宕机重启后的时钟回拨问题，这个问题可以通过在启动时进行最大ID校验时间戳进行解决。

四、百度UIDGenerator

4.1 百度UIDGenerator

UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。

依赖于数据库（UidGenerator以组件形式工作，内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖）

4.2 DefaultUidGenerator

/** Bits allocate */
 protected int timeBits = 28;
 protected int workerBits = 22;
 protected int seqBits = 13;

 /** Customer epoch, unit as second. For example 2016-05-20 (ms: 1463673600000)*/
 protected String epochStr = "2016-05-20";
 protected long epochSeconds = TimeUnit.MILLISECONDS.toSeconds(1463673600000L);

 /** Stable fields after spring bean initializing */
 protected BitsAllocator bitsAllocator;
 protected long workerId;

 /** Volatile fields caused by nextId() */
 protected long sequence = 0L;
 protected long lastSecond = -1L;

 /** Spring property */
 protected WorkerIdAssigner workerIdAssigner;
 
 /**
  * Get UID
  *
  * @return UID
  * @throws UidGenerateException in the case: Clock moved backwards; Exceeds the max timestamp
  */
 protected synchronized long nextId() {
     long currentSecond = getCurrentSecond();

     // Clock moved backwards, refuse to generate uid
     if (currentSecond < lastSecond) {
         long refusedSeconds = lastSecond - currentSecond;
         throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);
     }

     // At the same second, increase sequence
     if (currentSecond == lastSecond) {
         sequence = (sequence + 1) & bitsAllocator.getMaxSequence();
         // Exceed the max sequence, we wait the next second to generate uid
         if (sequence == 0) {
             currentSecond = getNextSecond(lastSecond);
         }

     // At the different second, sequence restart from zero
     } else {
         sequence = 0L;
     }

     lastSecond = currentSecond;

     // Allocate bits for UID
     return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
 }

DefaultUidGenerator相对于原生的雪花算法做了一些调整，允许对各段占用长度进行自定义

• 时间戳占用的位数减少了，默认占28位,起始时间默认为2016-05-20 (ms: 1463673600000)，时间戳到秒级别
• 机器占用的位数增大了，默认占22位，最多允许420万次的启停（内置实现为在启动时由数据库分配，默认分配策略为用后即弃）
• 序列位增加了一位，默认占13位，可支持每秒8192个并发。

对于时钟回拨问题，DefaultUidGenerator粗暴的直接抛出异常。

4.3 CachedUidGenerator

这种方案和上面默认的方案不同之处在于预先生成UID，将生成的UID缓存在一个环形数组之中，定义了两个指针（tail、cursor）去控制UID的消费位置及生成的最大的UID的位置，端获取客户端获取UID时没有加锁，而是使用了CAS机制，其中提过了两种机制触发UID的生成：

• 阈值机制：获取UID时，如果剩余可获取的UID小于设定的阈值，则通过线程池提交一个任务生成UID缓存到环形数组之中
• 定时机制：通过定时任务定时生成UID缓存到环形数组之中

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

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

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

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

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

• Cursor指针
  表示Consumer消费到的最小序号(序号序列与Producer序列相同)。Cursor不能超过Tail，即不能消费未生产的slot。当Cursor已赶上tail，此时可通过rejectedTakeBufferHandler指定TakeRejectPolicy

RingBuffer填充时机

• 初始化预填充
  RingBuffer初始化时，预先填充满整个RingBuffer.

• 即时填充
  Take消费时，即时检查剩余可用slot量(tail - cursor)，如小于设定阈值，则补全空闲slots。阈值可通过paddingFactor来进行配置

• 周期填充
  通过Schedule线程，定时补全空闲slots。可通过scheduleInterval配置，以应用定时填充功能，并指定Schedule时间间隔

上述描述中存在一个「伪共享」FalseSharing问题，为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine 补齐方式。

4.4 总结

• 较于原生的雪花算法减少了时间戳占用的长度，时间戳的长度调整到了22位，具体到秒级别，起始时间设置为了2016年。
• 增加了机器ID占用的长度，而且机器ID的分配使用了数据库自增的主键，允许单节点420万次的启动。
• 序列号的位数增大了1位，每秒最多可生成8192个UID。

DefaultUidGenerator方案：

• 获取UID时要加锁（synchronized）
• 发生时钟回拨时，直接抛出异常。

CachedUidGenerator方案：

• 获取UID时不用加锁，使用了CAS
• 提前生成UID缓存到环形之中，通过阈值或定制机制预生成UID
• 生成UID时不依赖于时间戳，而是对lastSecond进行加一（这个值的初始值为系统启动时的时间戳）
• 获取的UID中的时间戳不准确

CachedUidGenerator方案没有依赖于时间戳，所以不会在运行时出现时钟回拨问题，而且对于同一秒内如果序列号增长到最大时，可以借用未来时间进行生成。

五、美团（Leaf）

5.1 Leaf：美团分布式ID生成服务开源

Leaf是美团基础研发平台推出的一个分布式ID生成服务，名字取自德国哲学家、数学家莱布尼茨的一句话：“There are no two identical leaves in the world.”Leaf具备高可靠、低延迟、全局唯一等特点。目前已经广泛应用于美团金融、美团外卖、美团酒旅等多个部门。具体的技术细节，可参考此前美团技术博客的一篇文章：《Leaf美团分布式ID生成服务》。近日，Leaf项目已经在Github上开源：https://github.com/Meituan-Dianping/Leaf ，希望能和更多的技术同行一起交流、共建。

Leaf的特性

Leaf在设计之初就秉承着几点要求：

• 全局唯一，绝对不会出现重复的ID，且ID整体趋势递增。
• 高可用，服务完全基于分布式架构，即使MySQL宕机，也能容忍一段时间的数据库不可用。
• 高并发低延时，在CentOS 4C8G的虚拟机上，远程调用QPS可达5W+，TP99在1ms内。
• 接入简单，直接通过公司RPC服务或者HTTP调用即可接入。

5.2 号段模式

依赖于数据库，使用了预分发的方式生成ID，在DB上挂N个Server, 每个Server启动的时候都会去DB拿固定长度的ID List，然后再基于内存进行分发，数据库中记录了当前最大的ID。

• 使用双Buffer，异步获取号段
• MySQL采用半同步方式同步数据

5.3 Leaf Snowflake模式

Leaf Snowflake模式提供了Snowflake的Java版本实现，使用了Zookeeper身体工程机器号，获取后会在本机文件系统化缓存一个workID文件。

5.4 Leaf 总结

• 号段模式：依赖于数据库，低位趋势增长，较少的ID号段浪费，能够容忍MySQL的短时间不可用。
• Snowflake模式：完全分布式，ID有语义（没有解决时钟回拨的问题）。

六、总结

目前来说，分布式ID生成方案总的来说可以分为3类：

• UUID这类依赖于硬件，生成无序的ID
• 依赖于数据库，可以实现单调递增和趋势递增
• 雪花算法类，依赖于时间戳，趋势递增，有时钟回拨问题