分布式：分布式ID生成策略

参考资料：

《分布式 ID》

《Leaf——美团点评分布式ID生成系统》

《一口气说出 9种 分布式ID生成方式》

《分布式id生成策略》

《唯一 ID 生成算法》

《分布式全局ID生成方案》

        写在开头：本文为学习后的总结，可能有不到位的地方，错误的地方，欢迎各位指正。

目录

一、分布式ID介绍

        1、什么是分布式ID

        2、分布式ID的要求

二、数据库方案

        基于数据库自增ID

        基于数据库集群模式

        基于数据库的号段模式

        基于Redis模式

三、算法方案

        基于UUID

        基于雪花算法（Snowflake）模式

四、开源框架Leaf

        Leaf-segment 方案

        双buffer优化

        Leaf-snowflake方案

---

一、分布式ID介绍

        1、什么是分布式ID

        以为MySQL为例，在我们业务数据量不大的时候，单库单表完全可以支撑现有业务，数据再大一点搞个MySQL主从同步读写分离也能对付。

        但随着数据日渐增长，主从同步也扛不住了，就需要对数据库进行分库分表，但分库分表后需要有一个唯一ID来标识一条数据，数据库的自增ID显然不能满足需求。

         如上图，如果第一个订单存储在 DB1 上则订单 ID 为1，当一个新订单又入库了存储在 DB2 上订单 ID 也为1。我们系统的架构虽然是分布式的，但是在用户层应是无感知的，重复的订单主键显而易见是不被允许的。

        此时一个能够生成全局唯一ID的系统是非常必要的。那么这个全局唯一ID就叫分布式ID。

        2、分布式ID的要求

        一个最基本的分布式 ID 需要满足下面这些要求：

• 全局唯一 ：ID 的全局唯一性肯定是首先要满足的！
• 高性能 ： 分布式 ID 的生成速度要快，对本地资源消耗要小。
• 高可用 ：生成分布式 ID 的服务要保证可用性无限接近于 100%。
• 方便易用 ：拿来即用，使用方便，快速接入。

        除了这些之外，一个比较好的分布式 ID 还应保证：

• 安全 ：ID 中不包含敏感信息。
• 有序递增 ：如果要把 ID 存放在数据库的话，ID 的有序性可以提升数据库写入速度。并且，很多时候 ，我们还很有可能会直接通过 ID 来进行排序。
• 有具体的业务含义 ：生成的 ID 如果能有具体的业务含义，可以让定位问题以及开发更透明化（通过 ID 就能确定是哪个业务）。
• 独立部署 ：也就是分布式系统单独有一个发号器服务，专门用来生成分布式 ID。这样就生成 ID 的服务可以和业务相关的服务解耦。不过，这样同样带来了网络调用消耗增加的问题。总的来说，如果需要用到分布式 ID 的场景比较多的话，独立部署的发号器服务还是很有必要的。

二、数据库方案

        基于数据库自增ID

        基于数据库的auto_increment自增ID完全可以充当分布式ID。

         具体实现：需要一个单独的MySQL实例用来生成ID，建表结构如下：        

CREATE TABLE `seq_id` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `str` char(10) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  UNIQUE KEY `stub` (`str`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

        使用str字段并创建唯一索引，是为了使用insert的增强方法replace into         

BEGIN;
REPLACE INTO seq_id (str) VALUES ('str'); --给唯一索引列插入随机字符串
SELECT LAST_INSERT_ID(); -- 返回最新行号
COMMIT;

        replace into具体步骤是这样的（具体用法可以看这里《MySQL replace into 用法》）：

        （1）第一步： 尝试把数据插入到表中。

        （2）第二步： 如果主键或唯一索引字段出现重复数据错误而插入失败时，先从表中删除含有重复关键字值的冲突行，然后再次尝试把数据插入到表中。

        这种方式的优缺点也比较明显：

        优点 ：实现起来比较简单、ID 有序递增、存储消耗空间小
        缺点 ： 并发量受单台数据库服务器性能影响、单台数据库存在可用性问题（宕机会导致较大影响）、每次获取 ID 都要访问一次数据库（增加了对数据库的压力，获取速度也慢）

        基于数据库集群模式

        上一节发现单点数据库方式不可取，那对上边的方式做一些高可用优化，换成主从模式集群。害怕一个主节点挂掉没法用，那就做双主模式集群，也就是两个Mysql实例都能单独的生产自增ID。

        那这样还会有个问题，两个MySQL实例的自增ID都从1开始，会生成重复的ID怎么办？解决方案：设置起始值和自增步长。

        MySQL_1 配置：

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

        MySQL_2 配置：

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

        这样两个MySQL实例的自增ID分别就是：1、3、5、7、9  2、4、6、8、10

        如果集群后的性能还是扛不住高并发咋办？就要进行MySQL扩容增加节点，这是一个比较麻烦的事。

          

         增加第三台MySQL实例需要人工修改一、二两台MySQL实例的起始值和步长，把第三台机器的ID起始生成位置设定在比现有最大自增ID的位置远一些，但必须在一、二两台MySQL实例ID还没有增长到第三台MySQL实例的起始ID值的时候，否则自增ID就要出现重复了，必要时可能还需要停机修改。

        优点：解决DB单点问题
        缺点：不利于后续扩容，而且实际上单个数据库自身压力还是大，依旧无法满足高并发场景。

        基于数据库的号段模式

        数据库主键自增这种模式，每次获取 ID 都要访问一次数据库，ID 需求比较大的时候，肯定是不行的。

        如果我们可以批量获取，然后存在在内存里面，需要用到的时候，直接从内存里面拿就舒服了！这也就是我们说的 基于数据库的号段模式来生成分布式 ID。

        号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。表结构如下：

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '当前最大id',
  step int(20) NOT NULL COMMENT '号段的布长',
  biz_type	int(20) NOT NULL COMMENT '业务类型',
  version int(20) NOT NULL COMMENT '版本号',
  PRIMARY KEY (`id`)
) 

        biz_type代表不同业务类型、max_id代表当前最大的可用id、step代表号段的长度、version 代表一个乐观锁，每次都更新version，保证并发时数据的正确性

         等这批号段ID用完，再次向数据库申请新号段，对max_id字段做一次update操作，update max_id= max_id + step，update成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]。

update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX

        相比于数据库主键自增的方式，数据库的号段模式对于数据库的访问次数更少，数据库压力更小。另外，为了避免单点问题，你可以从使用主从模式来提高可用性。

        优点 ：ID 有序递增、存储消耗空间小
        缺点 ：存在数据库单点问题（可以使用数据库集群解决，不过增加了复杂度）、ID 没有具体业务含义

        基于Redis模式

        和数据库自增一样，我们通过 Redis 的 incr 命令即可实现对 id 原子顺序递增。

127.0.0.1:6379> set sequence_id_biz_type 1
OK
127.0.0.1:6379> incr sequence_id_biz_type
(integer) 2
127.0.0.1:6379> get sequence_id_biz_type
"2"

        为了提高可用性和并发，我们可以使用 Redis Cluster（《Redis：分片（Redis Cluster）》）。除了高可用和并发之外，我们知道 Redis 基于内存，我们需要持久化数据，避免重启机器或者机器故障后数据丢失（《Redis：持久化RDB与AOF》）。

        优点 ： 性能不错并且生成的 ID 是有序递增的
        缺点 ： 和数据库主键自增方案的缺点类似

三、算法方案

        基于UUID

           在Java的世界里，想要得到一个具有唯一性的ID，首先被想到可能就是UUID，毕竟它有着全球唯一的特性。那么UUID可以做分布式ID吗？答案是可以的，但是并不推荐！

String uuid = UUID.randomUUID().toString().replaceAll("-","");

        虽然 UUID 生成方便，本地生成没有网络消耗，但是使用起来也有一些缺点

        不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。

        信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，暴露使用者的位置。

        对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能（相关知识点可以看这里《MySQL：索引（1）原理与底层结构》）。     

        基于雪花算法（Snowflake）模式

        Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义。而 Java中64bit的整数是Long类型，所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。

• 第 0 位： 符号位（标识正负），始终为 0，没有用，不用管。
• 第 1~41 位 ：一共 41 位，用来表示时间戳，单位是毫秒，可以支撑 2 ^41 毫秒（约 69 年）
• 第 42~52 位 ：一共 10 位，一般来说，前 5 位表示机房 ID，后 5 位表示机器 ID（实际项目中可以根据实际情况调整）。这样就可以区分不同集群/机房的节点。
• 第 53~64 位 ：一共 12 位，用来表示序列号。 序列号为自增值，代表单台机器每毫秒能够产生的最大 ID 数(2^12 = 4096),也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID。

        这样的划分之后相当于在一毫秒一个数据中心的一台机器上可产生4096个有序的不重复的ID。但是我们 IDC 和机器数肯定不止一个，所以毫秒内能生成的有序ID数是翻倍的。

         根据这个算法的逻辑，只需要将这个算法用Java语言实现出来，封装为一个工具方法，那么各个业务应用可以直接使用该工具方法来获取分布式ID，只需保证每个业务应用有自己的工作机器id即可，而不需要单独去搭建一个获取分布式ID的应用。

        Java版本的Snowflake算法实现：

/**
 * Twitter的SnowFlake算法,使用SnowFlake算法生成一个整数，然后转化为62进制变成一个短地址URL
 *
 * https://github.com/beyondfengyu/SnowFlake
 */
public class SnowFlakeShortUrl {
 
    /**
     * 起始的时间戳
     */
    private final static long START_TIMESTAMP = 1480166465631L;
 
    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12;   //序列号占用的位数
    private final static long MACHINE_BIT = 5;     //机器标识占用的位数
    private final static long DATA_CENTER_BIT = 5; //数据中心占用的位数
 
    /**
     * 每一部分的最大值
     */
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);
 
    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
 
    private long dataCenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastTimeStamp = -1L;  //上一次时间戳
 
    private long getNextMill() {
        long mill = getNewTimeStamp();
        while (mill <= lastTimeStamp) {
            mill = getNewTimeStamp();
        }
        return mill;
    }
 
    private long getNewTimeStamp() {
        return System.currentTimeMillis();
    }
 
    /**
     * 根据指定的数据中心ID和机器标志ID生成指定的序列号
     *
     * @param dataCenterId 数据中心ID
     * @param machineId    机器标志ID
     */
    public SnowFlakeShortUrl(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_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 currTimeStamp = getNewTimeStamp();
        if (currTimeStamp < lastTimeStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }
 
        if (currTimeStamp == lastTimeStamp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currTimeStamp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }
 
        lastTimeStamp = currTimeStamp;
 
        return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分
                | dataCenterId << DATA_CENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }
    
    public static void main(String[] args) {
        SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);
 
        for (int i = 0; i < (1 << 4); i++) {
            //10进制
            System.out.println(snowFlake.nextId());
        }
    }
}

        雪花算法提供了一个很好的设计思想，雪花算法生成的ID是趋势递增，不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的，而且可以根据自身业务特性分配bit位，非常灵活。

        但是雪花算法强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID，而时间回退后，生成的ID就有可能重复。官方对于此并没有给出解决方案，而是简单的抛错处理，这样会造成在时间被追回之前的这段时间服务不可用。

        很多其他类雪花算法也是在此思想上的设计然后改进规避它的缺陷，后面介绍的百度 UidGenerator 和 美团分布式ID生成系统 Leaf 中snowflake模式都是在 snowflake 的基础上演进出来的。

四、开源框架Leaf

        Leaf 是美团开源的一个分布式 ID 解决方案 。Leaf 也提供了两种ID生成的方式，分别是 Leaf-segment（号段模式） 数据库方案和 Leaf-snowflake（雪花算法）方案。

        Leaf-segment 方案

        Leaf 对原有的号段模式进行改进，各个业务不同的发号需求用 biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。

        数据库表设计如下：

CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT '' COMMENT '业务key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前已经分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步长，也是动态调整的最小步长',
  `description` varchar(256)  DEFAULT NULL COMMENT '业务key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;

         到这里为止，Leaf-segment都与我们上文介绍的号段模式一致，下面介绍下该方案对于号段模式的优化。

        双buffer优化

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

        为了DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中，而不需要等到号段用尽的时候才去更新号段。详细实现如下图所示：

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

• 每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。 
• 每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

        对于这种方案依然存在一些问题，它仍然依赖 DB的稳定性，需要采用主从备份的方式提高 DB的可用性。

        Leaf-snowflake方案

        Leaf-snowflake方案完全沿用 snowflake 方案的bit位设计，对于workerID的分配引入了Zookeeper持久顺序节点的特性自动对snowflake节点配置 wokerID。避免了服务规模较大时，动手配置成本太高的问题。

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

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

         为了减少对 Zookeeper的依赖性，会在本机文件系统上缓存一个workerID文件。当ZooKeeper出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。

        上文阐述过在类 snowflake算法上都存在时钟回拨的问题，Leaf-snowflake在解决时钟回拨的问题上是通过校验自身系统时间与 leaf_forever/${self}节点记录时间做比较然后启动报警的措施。

                  

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

        在性能上官方提供的数据目前 Leaf 的性能在4C8G 的机器上QPS能压测到近5w/s，TP999 1ms。