分布式唯一ID-雪花算法_雪花散列

于今日，看到了久违的太阳，在此纪念一下。

下面步入正题。

世上没有两片相同的雪花。

背景

在复杂的分布式系统中，常常需要为某条数据或消息生成一个全局唯一的标识。例如请求的 RequestId，支付流水号，订单号等。

因此分布式唯一ID的生成方案不可或缺，对于这个唯一ID有以下要求：

• 全局唯一性，ID 之间不能重复
• 单调递增，即下一个生成的 ID 要比上一个大，满足某些特定业务的排序要求
• 趋势递增，ID 的总体趋势是递增的，为了保证数据库存储的性能
• 信息安全，要求 ID 是无规则的，如果是简单的单调递增，则容易被爬虫或是被竞对推测订单量

另外作为分布式系统中一个基础的服务，对于服务的高吞吐，高可用也有严格的要求。

方案

唯一ID的生成方案主要可以概括为两类：

• 第一类基于第三方中间件，例如数据库，Redis 等，虽然实现简单，但引入了系统复杂度，易受中间件故障影响，且存在读写的性能问题
• 第二类基于特定算法本地生成，例如雪花算法，UUID等，特点的是性能好，且系统复杂度较低

基于数据库的实现方案可以参照美团的这篇文章，里面有相关问题的解决方案，其中双 buffer 优化的思想很有启示意义：https://tech.meituan.com/2017/04/21/mt-leaf.html

我们部门目前使用的是雪花算法，下面也主要讲雪花算法相关的实现。

雪花算法

该算法使用分段思想，通过 时间戳 + 机器ID + 自增序列 组合生成一个长度为 64 位的 Long 类型ID。

• 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
• 时间戳 占用41bit，精确到毫秒，总共可以容纳约69年的时间（需要注意的是：不是指当前时间戳，而是和时间戳相关）
• 工作节点ID 占用10bit，其中高位5bit是数据中心ID，低位5bit是工作节点ID，可以容纳1024个节点
• 自增序列号 占用12bit，每个节点每毫秒从0开始不断累加（实际应用一般不从 0 开始累加，会随机一个起始数），最多可以累加到4095

具体实现主要涉及以下核心点：

• 时间戳信息，工作节点ID的计算
• 自增序列号的处理
• 系统时针倒退问题
• 多个节点时间不同步问题
• 安全性

时间戳信息

下面是 id 生成的公式：

long id = ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;
1

可以看到时间戳信息 = timestamp - twepoch，其中 timestamp 为当前时间，而 twepoch 则是自定义的一个起始时间，为什么需要这个时间呢？

时间戳信息占总长的 41 bit ，如果直接用当前时间作为时间戳信息，则会浪费 41 bit 能表示的数据集中绝大部分，故让其减去 twepoch，twepoch 一般设置为系统投入生产的时间。

另外 41 bit 时间戳最多能表示 69 年，如果用完了怎么办？

互联网行业，能活 69 年的企业已经很不容易了（手动狗头），即使真活了那么久，系统可能也经历了多次重构，所以暂且不考虑这个问题。

工作节点ID

美团 Leaf-snowflake 的实现中是通过 zookeeper 为集群中每个节点生成唯一的工作节点ID。

个人觉得，如果单纯只是想生成唯一的工作节点ID，没有必要引入
zookeeper，可以根据 HostName + IP地址编码 的方式生成节点ID（我们便是如此）。

自增序列号

自增序列号的作用是防止同一毫秒，同一节点产生重复的ID，占 12 bit，最大为 4095。

如果同一毫秒同一节点存在多个生成ID的请求，则会触发自增序列自增，
如果自增序列打满了，则会阻塞到下一毫秒。

另外每当时间戳发生变更（当前时间戳与上一次生成的时间戳作比较），都会重置自增序列的值，如果想让ID分布足够散列，可以重置到一个随机值。

如何判断自增序列打满了，算法中通过与运算的方式，sequenceMask 为自增序列的掩码（低12位都为1，其余位为0），如果结果 sequence = 0，则说明自增序列被打满溢出了。

sequence = (sequence + 1) & sequenceMask;
1

时钟倒退

即系统时间发生了回退，如果不做处理，则会生成重复ID。

针对这个问题，每次生成id后，记录一个最后生成时间 lastTimestamp，可以用来判断系统时钟是否发生倒退(currentTimestamp < lastTimestamp)。

如果发生了倒退，可以有如下几种处理方案：

• 直接响应 Error
• 如果偏差较小（如5毫秒以内），可以做一层重试，重试失败则触发报警
• 直接摘除发生时钟倒退的节点，暂时不再对外提供服务

节点时间不同步

节点间时间不同步，可能会导致ID不满足严格的单调递增。

举个例子：存在两个节点 worker1，worker2，worker1 的时钟落后于 worker2，即使 worker1 上的 ID 后生成，也可能小于 worker2 先生成的 ID。

如果业务对于 ID 的单调递增有严格要求，则需要解决这个问题，美团 Leaf-snowflake 是通过启动时，节点间的时间协商解决这个问题的。

假设当前节点的系统时间为 currentTime，集群内节点的平均系统时间为 averageTime，如果 currentTime - averageTime > 阈值，则认为当前节点的时间发生大步长偏移，当前节点启动失败并触发报警。

具体实现可以参看原文：https://tech.meituan.com/2017/04/21/mt-leaf.html

安全性

安全性指的是生成的ID是否存在信息泄露的危险。

比如：如果订单号是简单的自增（每次+1），那么竞争对手只要前后两天同一时间，分别下一单，然后通过订单号相减就能推测你们这一天之间的订单量了，你说安不安全。

当然雪花算法满足安全性要求，它的ID主要是根据时间戳生成的，并没有和订单的增长逻辑直接关联，另外自增序列 sequence 的随机散列也可以保证信息安全。

综上所述，雪花算法满足分布式唯一ID对于唯一性，单调递增性，安全性的要求，无论在实现复杂度，还是性能方面都有很大的优势，且，能适用于大部分业务场景。