在日常的业务开发中，通常需要对一些数据做唯一标识，例如为大量抓取的文章入库时分配一个唯一的id，为用户下的订单分配订单号等等。并发量小的时候，通常会使用数据库自增的主键id作为唯一id。并发量大的时候就会考虑使用一些分布式ID的生成方案来生成id。由于一些特殊的业务需求，我们的业务中也使用到了分布式ID的生成，对分布式ID的各种方案进行了调研。也对开源的分布式ID框架进行了一些优化和改造。本文主要分为以下三个部分：

一.常见的分布式ID生成方案的简单介绍。

二.对当前开源的分布式ID框架实现原理进行分析，例如美团的Leaf和百度的uid-generator。

三.Leaf和uid-generator存在的一些问题及如何进行优化改进。

一、分布式ID生成方案简介

目前常用的分布式ID生成方案主要由以下几种：

1.使用UUID算法生成唯一id。

2.利用单机数据库主键自增来生成唯一id。

3.多数据库主键自增生成唯一id。（设置步长区分不同数据库）

4.数据库分段发号生成唯一id。（例如美团的Leaf框架中的segement模式）

5.基于snowflake算法生成唯一id（例如美团的Leaf框架中的snowflake模式，百度的uid-generator）

1.UUID

简单的来说，UUID是服务器在不需要任何外界依赖(像类Snowflake算法的方案都需要注册中心)的情况下，基于当前时间、计数器（counter）和硬件标识等等信息生成的唯一ID。

优点

无任何依赖

其他的技术方案都是有依赖的，比如单机数据库主键自增生成ID强依赖数据库，类Snowflake算法的方案至少启动时都需要注册中心，Leaf框架Snowflake模式需要定时上传时间戳到注册中心，的UUID生成不需要任何外界依赖，

缺点

ID太长，且不是数字类型

当然为了唯一性，带来的牺牲就是生成的结果一般是32位的字符串。由于字符串太长，并且不是数字类型，所以不适合作为数据库的主键。

（字符串作为主键id，插入数据时会是在聚集索引中是随机插入，容易造成页分离。而且字符串的比较比数字类型的开销更大，字符串作为主键id查询效率会低于数字类型的主键。）

适用场景

通常可以作为一些临时性唯一标识，例如用户登陆后，生成一个UUID作为登录的会话ID，作为key存储在Redis中，Value是用户相关的信息。

2.单机数据库主键自增

业务量不大时普遍采用这种方案来生成id。

优点

方便接入

因为一般的项目不一定会用到Zookeeper等这些组件，但是基本都会用到数据库，所以项目接入会比较简单，也没有增加额外的维护成本。

单调递增

是绝对的单调递增的，就是从时间线上看，后面生成的id肯定比前面生成的id要大。

缺点

强依赖于数据库

一旦单机数据库发生宕机，就没法生成id，导致整个系统不可用。如果数据库是主从架构的，主库发生故障，切换成从库，如果从库还没来得及收到主库最新的插入id的更新，就有可能导致从库当前的自增id不是最新的，从而生成出重复的id。

id是连续的

id是连续的有可能会成为缺点，竞争对手在当天12点下一个订单，然后在第二天12点下一个订单，可能根据订单id的差就可以推测出每天的订单量。像猫眼电影就使用了这种方法来生成电影的id。一般我们日常使用时，其实为了让我们生成id的方式更难被竞争对手猜测出，一般是不会从1开始的，但是猫眼电影这里是从1开始的，而且是连续的，所以我们使用二分法很快就确定了8875是最大的值，也就是总共有8875部电影，而且由于是连续的，爬取也会比较方便。 猫眼电影的id——也是使用单机数据库生成的，连续自增的

https://maoyan.com/films/1
https://maoyan.com/films/2
https://maoyan.com/films/8874
https://maoyan.com/films/8875
https://maoyan.com/films/8876
（1到8875可以请求到数据，8876及后面的id
请求不到数据，没有这些id对应的电影，说明总共有8875部电影）

除非去做额外的处理（例如定时去获取当前的自增起始值a，然后生成一个随机数b，使用alter table users AUTO_INCREMENT=a+b;命令对自增起始值修改，也就是跳过一些id。）

适用场景

适用于并发量不高的业务。

3.多数据库主键自增生成唯一id。（设置步长区分不同数据库）

可以使用以下命令设置MySQL中表每次自增时的步长，通过将不同数据库的步长设置为一样，可以让不同数据库生成的id进行区分。

CREATE TABLE table (...) AUTO_INCREMENT = n;
alter table <table name> auto_increment=2;

例如，步长是等于数据库的数量，例如有N台数据库， 第一台数据库的起始值是0，那么生成的id就是0，N，2N，3N等等。

第一台数据库的起始值是1，那么生成的id就是1，N+1，2N+1，3N+1等等。 这样各个数据库生成的id就不会冲突，并且每个数据库可以单独生成id。

优点

生成id的效率比单台数据库要高，因为可以多台数据库同时发号。

缺点

是解决了每次自增是1的问题，缺点是一旦设置了步长，就不方便扩容了，因为分库分表的表的数量已经定下来了。

使用场景

在没有分库分表的框架以前，那些分库分表就是使用这种方案来实现的。

4.数据库分段发号生成唯一id。（例如美团的Leaf框架中的segement模式）

简单来说，就是想下图一样，用一个数据库表来充当发号器， 表中字段介绍如下：

biz_tag字段用于区分每种id应用的业务，
max_id字段记录了当前已生成的最大的id，
step字段代表每次可以获取id的数量

id生成项目每次使用下面这条语句从数据库获取step数量的id，并且更新max_id的值，将step数量的id存储在内存中，供业务方通过HTTP，RPC，Client等方式来获取。

UPDATE leaf_alloc SET max_id = max_id + step WHERE biz_tag = #{tag}

优点

效率高

生成id的效率取决于step的大小，不会像主键自增生成id那样再受限于数据库的数量。

缺点

强依赖于数据库

还是强依赖于数据库，数据库宕机后，虽然id生成系统靠内存中还未使用完id，可以维持系统正常运行一段时间，但是数据库不可用还是会导致整个系统不可用。

5.基于snowflake算法生成唯一id

snowflake是推特开源分布式ID生成算法，一共有64位，

第一位是0，标志位

接下来41位是13位的毫秒时间戳，最大可以到2039年9月

接下来10个二进制位是服务器的id

后面12位是业务序列号

意味着每毫秒最大可以生成2的12次方个id，4096个，支持每个机器每毫秒生成4096个id，每秒可以生成400多万的id

优点

效率高

生成id是比较快，

不依赖其他组件

生成id的过程中，可以做到不额外依赖其他组件。

二、开源的分布式ID框架实现原理分析

Leaf

Leaf主要有Leaf-Segment和Leaf-Snowflake两种模式

Leaf-Segment

Leaf-Segment主要采用上面的第四种.数据库分段发号生成唯一id的技术方案实现的。

这是我画的一个执行流程图，左边部分是业务系统获取id的流程：

1.业务系统通过HTTP，RPC，Client等方式向ID生成系统获取ID。

2.判断ID生成系统内存中当前SegmentBuffer使用率是否达到了10%，是的话触发另一个SegmentBuffer的异步更新。 （SegmentBuffer可以认为是一个容器，用于存放每次从数据库取出的step数量的id，然后供业务系统消耗。）

3.判断当前SegmentBuffer的id是否使用完了，如果没有使用完，就直接从这个SegmentBuffer取一个id返回。否则就将当前SegmentBuffer与备用SegmentBuffer进行交换，然后从交换后的SegmentBuffer取一个id返回给业务系统。

右边是备用SegementBuffer的更新流程：

ID生成系统会判断内存中当前Segement使用率是否达到了10%

Leaf框架的优化点之一就是使用了双SegmentBuffer进行优化，如果单个SegmentBuffer，在id消耗完之后，ID生成系统需要从数据库获取新的号段，填充到SegmentBuffer，然后供业务系统消费，此时业务系统发来的请求需要进行等待。如果是双SegmentBuffer，可以在一个SegmentBuffer的id使用率达到阀值（默认是10%），就触发另一个SegmentBuffer的异步更新，提取把号段获取到，存储到内存中。

百度的uid-generator

默认模式

每次启动时向数据库插入一条数据，这行数据的主键是自增的，主键id就是workId，

因为默认是snowflake算法是1标志位+41位时间戳+10位机器号+12位序列号，

因为百度的是每次启动都获取新的机器号，所以它修改了这些位数配比，是

1标志位+28位的时间差+22位的机器号+13位的序列号，所以总共支出2的22次方次启动，也就是400万次启动。

解决时间回拨问题：

• 启动时时间回拨

因为是每次都用新的机器号，所以当前机器号都是之前没有的，所以即便时间戳回拨也不影响。

• 运行时时间回拨

会使用lastSecond来记录上次生成id的时间戳，如果当前时间戳比lastSecond还小，就抛出异常。

缓存模式

主要继承自默认模式，只是用一个环形数组来存储生成好的id，每次去环形数组中去，默认大小是2的13次方，8192。这种模式使用的时间取得不是实时的系统时间，而且使用启动时的时间，每次生成一组id时，对之前保存的时间+1。

阀值检测，然后填充

取id时，可用id数小于阀值50%时，去填充

定期填充

会去检查环形数组中id使用情况，然后生成一组最大序列号个数的id(默认是8192个)，然后进行填充，多的直接丢弃掉，

美团的leaf

snowflake模式

1位的符号位+41位的时间戳+10位的workID+10位的序列号

1 时钟回拨问题

若机器出现时钟回拨，会产生重复id

1）启动时回拨

启动时获取其他机器的时间，计算出平均时间后，将本机时间与平均时间比较，若超过阈值则启动失败。

2）运行时回拨

1. 直接拒绝，抛异常
   
2. 若回拨时间小于阈值，则睡眠
   
3. 若回拨时间大于阈值，直接拒绝服务并报错，或者更换机器号，或者利用拓展位
   

时间类型

• 时间戳：自1970.01.01起（今日头条）
• 时间差：自选起始时间（百度、美团）

2）时间精度

• 秒级：支持峰值更高（今日头条、百度）
• 毫秒级：记录时间粒度更细（美团）

汽车之家是自增的id，只是作品类型不同，文章，视频等

头条，百度，美团也是使用了snowFlake只是改变了位数占比。

比如头条是去掉了符号标示位，缩短了时间戳，前31位是秒级时间戳+自定义的序列（可能是机器id+递增的数），记录的时间粒度会粗一些，每一秒生成的id会少一些，但是支持的峰值会高一些，时间戳也可以不从1970年开始选，也可以从自定义的时间开始选，这样支持的年长会多一些。

3 机器号

纯机器号，或，机房号+机器号

1）物理机

• 手动配置
• zookeeper（美团） 在zookeeper如未注册则创建持久顺序节点，顺序号当机器号，并本地缓存

2）虚拟机

• redis 利用redis原子计数器，虚拟机启动后，请求计数器，按机器号位数取余
• zookeeper 从0到机器号上限，在zookeeper尝试创建临时节点，成功则为当前机器号
• 数据库（百度） 利用系统变量的host和port为唯一索引，在数据库中存取，主键作为机器id

参考链接：

https://tech.meituan.com/2017/04/21/mt-leaf.html

缺点是

1.趋势递增，容易被猜到订单量，第一条下单多少，第二条下单多少，可以自己加随机数。

2.依赖机器时间，如果机器时间出现回拨，变成以前的时间，可能会导致id重复。

解决回拨的问题

就是机器需要同步时间，不一致会对时间回拨，可能会导致id重复，像百度的snowflake是几台特定的服务器，每次的机器id也是从数据库里面生成的，所以不需要做时间同步。

3 类snowflake算法

采用snowflake算法思想，类snowflake算法根据各自业务需要，做出了不同改动。比如改变了位数占比，添加了业务线等其他信息

附：位数对应

调研了Leaf和uid-generator，由于Leaf有额外的zookeeper依赖，

所以选用了uid-generator，做的改进如下：

1.原本是一旦时钟回拨就抛出异常，修改为时钟回拨小于1s时，就不抛出抛出异常，进行等待1s。

2.加了序列号抛弃策略。按照原有序列号位数分配，是13位，就是每秒可以生成的id数是8192个id，如果并发量比较小，由于每秒获取的id的序列号部分都是从0开始的，或导致后缀0的数据会比较多，容易造成数据倾斜的问题，而且也容易泄露数据信息。可以增加抛弃策略，就是取每一秒的id时，计算一个最大值为序列号的10%随机数，从这个随机数开始取。

3.修改了位数分配，原有的时间位是28位的秒级时间差，最长服务年限只支持8.7年，我们把时间差位数分配了30位，最长可以支持34年。原本机器位是22位，支持启动400万次，我们其实不需要那么多次启动，调整成20位，支持100万次启动。1+30+20+13

4.增加机器位用完时的取余操作，便于复用。

leaf的缺点：

1.号段模式的信息安全性问题，不考虑机器线下和重启丢掉的这些id，id是完全连续的，容易被竞争对手猜到信息安全性。

2.小问题修复，就是Leaf为了减少对Zookeeper的依赖，在本地也存了一个上次使用的workid的缓存文件，保证在Zookeeper挂掉的情况下，id生成服务能正常启动，读取本地缓存的workid，然后启动。但是本地缓存文件里面只存储了workid，没有存储上次生成的id的时间戳，假如启动前服务器的时间被修改了，那么启动时就没法对时间进行校验，就会导致生成的id重复。

3.缺乏对最大支持年限的检查，时间戳部分溢出会影响符号位，导致生成的id是负数。

4.注册中心只支持Zookeeper，issue里面很多人提出，对于他们的项目来说，由于需要引入Zookeeper依赖，增加部署和维护Zookeeper成本。所以我fork了这个项目，增加了使用MySQL作为注册中心，以及本地配置作为注册中心的模块。