雪花算法源码分析及实践
一、雪花算法简介
雪花算法（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指定PutRejectPolicyCursor指针
表示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
- 依赖于数据库，可以实现单调递增和趋势递增
- 雪花算法类，依赖于时间戳，趋势递增，有时钟回拨问题