分布式ID生成方案

业务系统的需求

当前业务要求

业务系统对 ID 号码的要求

全局唯一性
趋势递增：在 MySQL InnoDB 引擎中使用的是聚集索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能
单调递增：保证下一个 ID 一定大于上一个 ID，例如事务版本号、IM 聊天中的增量消息、排序等特殊需求
信息安全：如果 ID 是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定 URL 即可；如果是订单号就更危险了，竞争对手可以直接知道我们一天的单量。所以在一些应用场景下，会需要 ID 无规则、不规则。

上述123对应三类不同的场景，3和4需求还是互斥的，无法使用同一个方案满足。

业务系统对 ID 号生成系统的可用性要求：

平均延迟和 TP999（Top Percentile 99.9%）延迟都要尽可能低
可用性5个9
高 QPS

不用UUID的原因

UUID（Universally Unique Identifier）的标准型式包含 32 个 16 进制数字，以连字号分为五段，形式为 8-4-4-4-12 的 36 个字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前为止业界一共有5种方式生成UUID，详情见 IETF 发布的 UUID 规范：《A Universally Unique IDentifier (UUID) URN Namespace》。

使用 UUID 的优势

性能非常高：本地生成，没有网络消耗。

使用 UUID 的缺陷

不易于存储：UUID 太长，16 字节 128 位，通常以36长度的字符串表示，很多场景不适用；
信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用：

① MySQL官方有明确的建议主键要尽量越短越好，36个字符长度的UUID不符合要求：

All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key.

② 对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。

总之，UUID 有很多合适的应用场景，但对于有些业务系统来说，UUID 显然不是最佳选择。

不用数据库的自增ID的原因

使用DB自增ID的优势

非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护
ID号单调自增，可以实现一些对ID有特殊要求的业务。

使用DB自增ID的缺陷

强依赖DB，当DB异常时整个系统不可用，属于致命问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号；
ID发号性能瓶颈限制在单台MySQL的读写性能。

对于MySQL性能问题，可用如下方案解决：在分布式系统中可以多部署几台机器，每台机器设置不同的初始值，且步长和机器数相等。比如有两台机器。设置步长step为2，TicketServer1的初始值为1（1，3，5，7，9，11…）、TicketServer2的初始值为2（2，4，6，8，10…）。这是Flickr团队在2010年撰文介绍的一种主键生成策略（详见：《Ticket Servers: Distributed Unique Primary Keys on the Cheap》）。如下所示，为了实现上述方案分别设置两台机器对应的参数，TicketServer1从1开始发号，TicketServer2从2开始发号，两台机器每次发号之后都递增2。

假设要部署N台机器，步长需设置为N，每台的初始值依次为0,1,2…N-1那么整个架构就变成了如下图所示：

这种架构有显而易见的缺点：

系统水平扩展比较困难：比如定义好了步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器发号是1,2,3,4,5（步长是1），这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，比如14（假设在扩容时间之内第一台不可能发到14），同时设置步长为2，那么这台机器下发的号码都是14以后的偶数。然后摘掉第一台，把ID值保留为奇数，比如7，然后修改第一台的步长为2。让它符合我们定义的号段标准，对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗？貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦。所以系统水平扩展方案复杂难以实现
ID没有了单调递增的特性：只能趋势递增，这个缺点对于一般业务需求不是很重要，可以容忍
数据库压力还是很大：每次获取ID都得读写一次数据库，只能靠堆机器来提高性能。

Twitter-Snowflake方案

全局唯一、局部有序

前置知识

整型表示

在 Java 标准中明确定义了整数数据类型需要采用补码表示和存储。表示方法如下：

Binary to Unsigned 二进制数转无符号数

w 代表二进制位数，其最高位，也就是 w-1 所在的位置可以被解释为负权（negative weight）

$B2U_w(\vec{x})=\sum^{w-1}_{i=0}x_i2^i$

Binary to Sign-Magnitude 二进制数转原码

$B2S_w(\vec{x})=(-1)^{x_{w-1}} \sum^{w-2}_{i=0}x_i2^i$

Binary to Ones’ Complement 二进制转反码

$B2O_w(\vec{x})=-x_{w-1}(2^{w-1}-1)+\sum^{w-2}_{i=0}x_i2^i$

Binary to Two’s-Complement 二进制数转补码

$B2T_w(\vec{x})=-x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i$

模

“模”是指一个计量系统的计数范围。表示 n 位的计算机计量范围是 0~2^n，模 = 2^n。任何有模的计量器都可化减法为加法。

关键概念：原码 + 补码 = 模

假设当前时针指向8点，而准确时间是6点，调整时间可有以下两种拨法

一种是倒拨2小时，即8 - 2 = 6
另一种是顺拨10小时，8 + 10 = 12 + 6 = 6，即8 - 2 = 8 + 10 = 8 + 12 - 2 (mod 12)

公式的一般表示

$a-b=a+(-b+mod)=a+(mod-b)$

算法原理

snowflake 是 Twitter 开源的分布式ID生成算法，结果是一个 long 型的 ID。

这种方案大致来说是一种以划分命名空间（UUID 也算，由于比较常见，所以单独分析）来生成 ID 的一种算法，这种方案把 64bit 分别划分成多段。其核心思想是：使用 41bit 作为毫秒数，10bit 作为机器的 ID，12bit 作为毫秒内的流水号，最后还有一个符号位，永远是0（一般 ID 不会出现负数的情况）。

由于整个结构是64位，所以我们在Java中可以使用Long来进行存储。该算法实现基本就是二进制操作,单机每秒内理论上最多可以生成1024*(2^12)，也就是 409.6 万个 ID (1024 X 4096 = 4194304)

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

1位标识，由于 Long 基本类型在 Java 中是带符号的，最高位是符号位，正数是0，负数是1，所以 id 一般是正数，最高位是0

41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截) 得到的值，这里的的开始时间截，一般是我们的 ID 生成器开始使用的时间，由我们程序来指定的。41位的时间截，可以使用 69年，年T = (1L << 41) / (1000L 60 60 24 365) = 69

10位的数据机器位，可以部署在 1024个节点，包括 5位 datacenterId 和 5位 workerId。10-bit 机器可以分别表示 1024台机器。如果我们对 IDC 划分有需求，还可以将 10-bit 分 5-bit 给IDC，分 5-bit 给工作机器。这样就可以表示 32 个 IDC，每个 IDC 下可以有 32 台机器，可以根据自身需求定义。

12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生 4096个 ID序号。12个自增序列号可以表示 2^12个 ID，理论上 snowflake 方案的 QPS 约为 409.6w/s，这种分配方式可以保证在任何一个 IDC 的任何一台机器在任意毫秒内生成的 ID 都是不同的。

优点：

整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。

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

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

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

缺点：

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

针对此，美团做出了改进：https://github.com/Meituan-Dianping/Leaf

算法实现

package org.tarot.leaf;

/**
 * @package: org.tarot.leaf
 * @author: 王子豪
 * @date: 2020/12/16 20:28
 * @description: 基于Twitter开源的分布式ID生成算法 Snowflake
 * Long型数据 64bit 各位分布
 * 1bit    弃用（符号位）
 * 41bit   时间戳差值
 * 10bit   数据中心-机器ID
 * 12bit   序列号
 * 移位算法 ~(-1 << bit) 算出bit位的最大正数 即五位数最大值为31
 */
public class SnowflakeIDGenerator {
    //开始时间截 (2020-12-01)
    private final long twepoch = 1606752000000L;
    // 数据中心id所占的位数
    private final long dataCenterIdBits = 5L;
    // 机器id所占的位数
    private final long workerIdBits = 5L;
    // 序列在id中占的位数
    private final long sequenceBits = 12L;
    // 支持的最大数据标识id
    private final long maxDataCenterId = ~(-1L << dataCenterIdBits);
    // 支持的最大机器id
    private final long maxWorkerId = ~(-1L << workerIdBits);
    // 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
    private final long sequenceMask = ~(-1L << sequenceBits);
    // 机器ID向左移12位(12)
    private final long workerIdShift = sequenceBits;
    // 数据中心id向左移17位(12+5)
    private final long dataCenterIdShift = sequenceBits + workerIdBits;
    // 时间截向左移22位(12+5+5)
    private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;
    //数据中心ID(0~31)
    private long dataCenterId;
    //工作机器ID(0~31)
    private long workerId;
    //毫秒内序列(0~4095)
    private long sequence = 0L;
    //上次生成ID的时间截
    private long lastTimestamp = -1L;

    public SnowflakeIDGenerator(long dataCenterId, long workerId, long sequence) {
        if (dataCenterId > maxDataCenterId || dataCenterId < 0)
            throw new IllegalArgumentException("Snowflake dataCenterId is out of bounds");
        if (workerId > maxWorkerId || workerId < 0)
            throw new IllegalArgumentException("Snowflake workerId is out of bounds");
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
        this.sequence = sequence % sequenceMask;
    }

    /**
     * 获取下一个ID
     */
    public long get() {
        long timestamp = timeGen();

        //如果当前时间戳小于上次时间戳，时间戳处理出现异常
        if (timestamp < lastTimestamp) {
            System.err.printf("Clock is moving backwards. Rejecting requests until %d", lastTimestamp);
            throw new RuntimeException(String.format("Clock is moving backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        //如果当前时间戳等于上次时间戳，同一毫秒内，递增序列号，否则清零重新开始
        if (timestamp == lastTimestamp) {
            //在sequence递增一后，如果超过最大值1，则会为0
            //127 & 127 = 127 ; 128 & 127 = 0 ; 129 & 127 = 1
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMills(lastTimestamp);
            }
        } else {
            sequence = 0;
        }

        //刷新上次时间戳值
        lastTimestamp = timestamp;

        return (timestamp-twepoch) << timestampLeftShift
                | dataCenterId << dataCenterIdBits
                | workerId << workerIdBits
                | sequence;
    }

    /**
     * 取到下一个时间戳
     * @param lastTimestamp 上一次生成ID的时间戳
     * @return 新的时间戳
     */
    private long tilNextMills(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 获取系统时间戳
     * @return 13位时间戳(ms)
     */
    private long timeGen() {
        return System.currentTimeMillis();
    }
}

算法的优缺点

► 优点：

毫秒数在高位，自增序列在低位，整个ID都是趋势递增的
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的
可以根据自身业务特性分配bit位，非常灵活

► 缺点：

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

► 应用举例——Mongdb的objectID：

MongoDB官方文档 ObjectID 可以算作是和snowflake类似方法，通过“时间+机器码+pid+inc”共12个字节，通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。

Leaf-Segment方案

全局唯一，全局有序

算法原理

在数据库自增ID方案的基础上的改进策略。

美团的Leaf-segment对数据库自增ID方案做了如下改变：

原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用 proxy server 批量获取，每次获取一个 segment（step 决定大小）号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力
各个业务不同的发号需求用 biz_tag 字段来区分，每个 biz-tag 的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对 biz_tag 分库分表就行。

数据库设计

Field	Type	Null	Key	Default	Extra
biz_tag	varchar(128)	NO	PRI		用来区分业务
max_id	bigint(20)	NO		1	表示该biz_tag目前所被分配的ID号段的最大值
step	int(11)	NO		NULL	表示每次分配的号段长度
desc	varchar(256)	YES		NULL
update_time	timestamp	NO		CURRENT_TIMESTAMP	on update CURRENT_TIMESTAMP

原来获取 ID 每次都需要写数据库，现在只需要把 step 设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。

读写数据库的频率从 1 减小到了 1/step，大致架构如下图所示：

算法优缺点

► 优点：

Leaf 服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景
ID 号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求
容灾性高：Leaf 服务内部有号段缓存，即使 DB 宕机，短时间内 Leaf 仍能正常对外提供服务
可以自定义 max_id 的大小，非常方便业务从原有的 ID 方式上迁移过来

► 缺点：

ID 号码不够随机，能够泄露发号数量的信息，不太安全
TP999 数据波动大，当号段使用完之后还是会 hang 在更新数据库的 I/O 上，TP999 数据会出现偶尔的尖刺
DB 宕机会造成整个系统不可用

双Buffer优化（解决Segment TP波动大）

Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的 ID 下发时间取决于下一次从 DB 取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。

为此，我们希望 DB 取号段的过程能够做到无阻塞，不需要在 DB 取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的 TP999 指标。

详细实现如下图所示：

采用双 Buffer 的方式，Leaf 服务内部有两个号段缓存区 Segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前 Segment 接着下发，循环往复。

主要特性如下：

1）每个 biz-tag 都有消费速度监控，通常推荐 Segment 长度设置为服务高峰期发号 QPS 的 600 倍（10分钟），这样即使 DB 宕机，Leaf 仍能持续发号 10-20 分钟不受影响；

2）每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

高可用容灾（解决Segment DB宕机系统不可用）

采用一主两从的方式，同时分机房部署，Master 和 Slave 之间采用半同步方式同步数据。同时使用公司 Atlas 数据库中间件（已开源，改名为 DBProxy）做主从切换。

当然这种方案在一些情况会退化成异步模式，甚至在非常极端情况下仍然会造成数据不一致的情况，但是出现的概率非常小。如果你的系统要保证100%的数据强一致，可以选择使用“类 Paxos 算法”实现的强一致 MySQL 方案，如 MySQL 5.7 前段时间刚刚GA的MySQL 5.7 Reference Manual :: 17 Group Replication。但是运维成本和精力都会相应的增加，根据实际情况选型即可。

同时 Leaf 服务分 IDC 部署，内部的服务化框架是“MTthrift RPC”。服务调用的时候，根据负载均衡算法会优先调用同机房的Leaf服务。在该IDC内Leaf服务不可用的时候才会选择其他机房的Leaf服务。同时服务治理平台 OCTO 还提供了针对服务的过载保护、一键截流、动态流量分配等对服务的保护措施。

不过，Leaf-Segment 方案虽好，但必竟不适用于所有场景。

Leaf-Segment 方案可以生成趋势递增的ID，同时 ID 号是可计算的，但不适用于订单 ID 生成场景。比如竞争对手在两天中午12点分别下单，通过订单id号相减就能大致计算出公司一天的订单量，这个是不能忍受的。面对这一问题，美团技术团队实现了 Leaf-Snowflake 这个方案。

Leaf-Snowflake方案

全局唯一、局部有序

基本原理

严格来说，Leaf-Snowflake 方案是 Twitter Snowflake 改进版，它完全沿用 Snowflake 方案的 bit 位设计。

对于 workerID 的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf 服务规模较大，动手配置成本太高。所以使用 Zookeeper 持久顺序节点的特性自动对 Snowflake 节点配置 workerID。

Leaf-snowflake 是按照下面几个步骤启动的：

启动 Leaf-snowflake 服务，连接 Zookeeper，在 leaf_forever 父节点下检查自己是否已经注册过（是否有该顺序子节点）
如果有注册过直接取回自己的 workerID（zk顺序节点生成的int类型ID号），启动服务
如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的workerID号，启动服务。

弱依赖ZooKeeper

除了每次会去 ZK 拿数据以外，也会在本机文件系统上缓存一个 workerID 文件。当 ZooKeeper 出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。这样做到了对三方组件的弱依赖。一定程度上提高了 SLA。

解决时钟问题

因为这种方案依赖时间，如果机器的时钟发生了回拨，那么就会有可能生成重复的ID号，需要解决时钟回退的问题。

服务启动流程

服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点
若写过，则用自身系统时间与 leaf_forever/${self} 节点记录时间做比较，若小于 leaf_forever/${self} 时间则认为机器时间发生了大步长回拨，服务启动失败并报警
若未写过，证明是新服务节点，直接创建持久节点 leaf_forever/${self} 并写入自身系统时间，接下来综合对比其余 Leaf 节点的系统时间来判断自身系统时间是否准确，具体做法是取 leaf_temporary 下的所有临时节点(所有运行中的 Leaf-snowflake 节点)的服务 IP：Port，然后通过 RPC 请求得到所有节点的系统时间，计算 sum(time)/nodeSize
若abs(系统时间 - sum(time) / nodeSize) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点 leaf_temporary/${self} 维持租约
否则认为本机系统时间发生大步长偏移，启动失败并报警
每隔一段时间(3s)上报自身系统时间写入 leaf_forever/${self}

由于强依赖时钟，对时间的要求比较敏感，在机器工作时 NTP 同步也会造成秒级别的回退，建议可以直接关闭 NTP 同步。要么在时钟回拨的时候直接不提供服务直接返回 ERROR_CODE，等时钟追上即可。或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警。

实现代码如下：

if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
            wait(offset << 1);
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                return new Result(-1, Status.EXCEPTION);
            }
        } catch (InterruptedException e) {
            LOGGER.error("wait interrupted");
            return new Result(-2, Status.EXCEPTION);
        }
    } else {
        return new Result(-3, Status.EXCEPTION);
    }
}

从上线情况来看，在2017年闰秒出现那一次出现过部分机器回拨，由于 Leaf-snowflake 的策略保证，成功避免了对业务造成的影响。目前Leaf的性能在4C8G的机器上QPS能压测到近5w/s，TP999 1ms，已经能够满足大部分的业务的需求。每天提供亿数量级的调用量。

PS：网上已有人按照文章中Leaf-snowflake方案做了一个开源版本，项目地址：https://github.com/weizhenyi/leaf-snowflake。作者宣称的测试情况，TPS：1W+/sec，单机190秒生成了200W无重复，单调递增的long型整数ID。

UidGenerator 的 RingBuffer 优化方案

CachedUidGenerator

CachedUidGenerator 的核心利用了 RingBuffer，它本质上是一个数组，数组中每个项被称为 slot。CachedUidGenerator 设计了两个 RingBuffer，一个保存唯一 ID，一个保存 flag。RingBuffer 的尺寸是 2^n，n 必须是正整数。

以下是 CachedUidGenerator 中的 RingBuffer 原理示意图：

扩展知识：什么是RingBuffer？

Ring Buffer的概念，其实来自于Linux内核（Maybe），是为解决某些特殊情况下的竞争问题提供了一种免锁的方法。这种特殊的情况就是当生产者和消费者都只有一个，而在其它情况下使用它也是必须要加锁的。

环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲区的数据读取和写入。在通常情况下，环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户，那么不需要添加互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。

更多说明见 github uid-generator

这样的好处是不用实时计算 ID 号，提高吞吐量。

Lanchester Blog

分布式系统分布式ID生成方案

业务系统的需求

当前业务要求

不用UUID的原因

不用数据库的自增ID的原因

Twitter-Snowflake方案

前置知识

算法原理

算法实现

算法的优缺点

Leaf-Segment方案

算法原理

数据库设计

算法优缺点

双Buffer优化（解决Segment TP波动大）

高可用容灾（解决Segment DB宕机系统不可用）

Leaf-Snowflake方案

基本原理

弱依赖ZooKeeper

解决时钟问题

UidGenerator 的 RingBuffer 优化方案

CachedUidGenerator