对于分布式ID的要求有哪些？

• 全局唯一：这是分布式ID最基本的要求。
• 趋势递增：对数据库做分库分表时需要用到分布式ID，而MySQL InnerDB引擎所使用的是B+Tree的数据结构进行索引的存储，且主键索引所使用的是聚集索引，这种场景下就要求有序，以保证写入性能。
• 信息安全：要求ID包含的信息要尽量安全，不被有心人给解析出重要信息，例如MAC地址。

对于生成分布式ID的服务要求有哪些？

• 高可用：保证服务在整个服务集群中持续可用。（一般要求达到5个9的标准）
• 高并发低延时：保证较高且稳定的QPS，满足多系统同时调用ID生成服务的场景。

实现方案

方案一：uuid(Universally Unique Identifier)

一般长度为32个16进制数字加“-”字符进行连接，分为五段，最终长度为36。示例：550e8400-e29b-41d4-a716-446655440000。除此之前业界还有其他4种生成方式，详见：https://www.ietf.org/rfc/rfc4122.txt

优点：由于是本地生成，其生成速度非常快，没有网络消耗

缺点：

• 长度过长，不易存储。
• 不安全。基于MAC地址生成的uuid可以被解析出MAC地址，定位到服务器位置。
• 其无序性导致难以用来作为主键使用。（mysql官方明确指出主键盘越短越好，而且在InnoDB 引擎下，UUID 的无序性可能会引起数据位置频繁变动，严重影响性能）

方案二：基于数据库实现的号段

例如mysql，我们可以利用给字段设置auto_increment_offset（列的初始值）和auto_increment_increment（增长步长）来保证字段按照我们所需的步长进行自增，从而达到生成递增id的效果。（注意：mysql限定初始值和步长范围均为1~65535）每次使用下面sql得到ID号：

# 每次插入一条数据，并取出最后一次插入数据mysql生成的id
begin;
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
commit;

image.png

优点：

• 简单易用，不用过多去关注和设计ID的生成规则。
• 单调递增可以满足一些需要严格顺序ID的场景。

缺点：

• 严重依赖于数据库，一旦数据库宕机整个发号服务即不可用。对此，配置主从复制部署模式，可以尽可能的增加其可用性，但是数据一致性在特殊情况下难以保证，并且主从切换时的不一致可能会导致重复发号。
• 瓶颈落在了单台数据库的读写性能。
• id递增有序，容易被竞争对手解析出业务量。

对于单机性能问题，我们可以部署多几台机器，例如部2台服务A和B，A生成id初始值为1，B初始值为2，并且设置同样的步长。于是服务器A就会从1开始发号，每次发号完就递增2，服务器B也一样，从2开始发号每次递增2，这样可以满足两台服务器发不重复号段的需求。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

不过这种方案一般不被采用，缺点很明显：

• 可扩展性差。假如因为业务量逐渐变大，AB两台服务器的生成速度已经不能满足需求了，假设我们进行水平扩展增加一台机器C，此时需要做的是（1）先把新增进来的服务id初始值设置成一个前面A和B服务器暂时不能达到的值（假设10000）然后把步长设置为3，（2）部署成功再把前面两台服务停掉，并重新给这两台赋一个10001和10002，并且步长同步为3，完成部署。这么一看似乎能解决水平拓展的问题，但目前只是水平拓展1台服务器就需要停掉前面服务，假设后期需要拓展10台、100台，那么部署复杂度和风险都会成指数级增长，并且每次部署，都需要浪费掉一批号段，显然这种方案不适用于大流量的分布式系统。
• 由于多台机器部署，获取到的ID就无法再保证单调递增，只是趋势递增（趋势递增允许小部分号段递减）。比如有A、B两台服务，A的id为100，B的id为99，步长为2，假设负载到A服务器两次，A发了两次号变成104，然后才到B发号，于是A为104、B为101，101 < 104，也就是说出现非单调递增的情况。
• 因为每次都需要从数据库获取id，数据库仍然压力山大。

方案三：美团点评 Leaf-segment

针对方案二的缺点，美团点评团队对该方案做了一些优化，解决了可扩展性差、并减轻了数据库的部分压力，该方案称为 Leaf-segment，具体优化方案如下：

方案三part1：改造id获取方式与表结构，采用下面的表结构来替代原先的发号表：

+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

重要字段说明：

biz_tag：用来区分不同业务 max_id：目前所被分配的id最大值 step：步长。

简单来说，增加一层proxy-server层（可以理解为就是生成分布式id的服务，真正与数据库交互的服务），在业务系统需要生成id时，不再每次都去数据库取，而且通过step字段定义我们一次性取出多少个id来使用，然后在程序中使用一个segment（数组）结构进行存储，只有当segment中的id用完之后，才会再次去数据库中取，这样便可大大降低数据库的读写压力（从n降低到n/step），其架构如下图：

比如，pay_ordertag业务部署了三台机器A、B、C，该业务id生成步长为1000（也就是说每次拿1000个去用），此时A持有[1, 1000]，B持有[1001, 2000]，C持有[2001, 3000]，当A的号段用完后，假设B、C均未用完各自持有的号段，那么A再去数据库取号时应该会取到[3001, 4000]，其更新号段的sql如下：

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

方案优点：

• 高可拓展性。Leaf服务可方便地进行水平拓展，其性能也完全足够支撑大部分的业务场景。
• 较高的可用性。原来的ID每次生成都完全依赖于数据库，现在改成批量获取，step设置合理的情况下，在发号数据库宕机后短时间不会造成Leaf服务不可用。
• 生成ID呈趋势线递增，满足作为MySQL InnerDB存储引擎主键的需求。
• 可通过自定义max_id使得很方便地从原来ID增长方式迁移过来（定义为大于原来增长id最大值）。

缺点：

• ID号码不够随机，如果对外暴露会被竞对很容易地解析出业务量。
• TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。简单理解就是在临界点去获取新号段时性能会急剧下降，导致整体的QPS不够稳定。
• DB宕机时间过长同样会致使服务不可用。

方案三part2：双buffer方案

针对part1方案我们发现，在临界点去DB获取新号段时，如果出现网络抖动或者DB慢查询，可能导致整个发号服务的性能急剧下降，甚至阻塞获取id的客户端线程，这对一个需要24小时不间断运行的系统而言是不可忍受的。因此，如果我们可以考虑采取一些方式，提前主动去检测segment中的号段的使用情况，当号段快要被用尽，便提前去数据库中获取号段，这样便可保证整体QPS的稳定性，降低TP999指标。

part2具体方案如下：

由原来的只用一个segment存储，改为由s1、s2两个segment存储（所谓的双buffer）。s1存储正在被使用的号段，s2用于存储下一批从数据库中取出来待使用的号段，除此之外增加一个指针pos来记录s1最后一个被使用到的号段位置，并实时计算s1的使用率，比如图中，当使用到pos位置的id时，触发阀值（使用率达到10%），此时判断s2是否为空，如果s2为空的就启动一个线程去数据库中load下一批号段。这样便不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。当s1被用尽后，则判断下个号段s2是否准备好，是则直接切换到下个号段为s1，继续发号。

image.png

注意的点：美团团队推荐单个segment的长度设置值是高峰QPS值的600倍（例如高峰1000/s，则设置为60w），即保证服务在DB宕机后至少可以在高峰QPS下抗10～20分钟。

除此之外，对于DB高可用性问题美团团队使用一主两从的方式进行多机房部署，Master和Slave则采用半同步方式进行数据同步，并设置DBProxy来做主从的切换（极端情况下会造成数据不一致）。但如果还需要保证数据的强一致性，可以考虑“类Paxos算法”的MGR（MySQL Group Replication），只是运维成本会增加许多，所以需要根据业务情况来选定方案。关于数据库高可用的部署方案非本文的主题，此处不进行详述。

方案四：snowflake-ID 雪花算法id

雪花算法是由Twitter推出的一种分布式ID解决方案，其核心思想就是使用一个64bit位的long型数字作为分布式ID，结构如图：

image.png

• 1bit：固定为0；
• 41bit时间戳：表示从系统初始时间到现在的毫秒数, 可以用大概69年：2 ^ 41 / (365 * 24 * 3600 * 1000) = 69.73年；
• 10bit机器id（workerID）：表示可以部署1 << 10 = 1024台机器（如果更细分，5bit为机房id，5bit为服务器id）。
• 12bit的序列号：每台机器每毫秒最多产生1 << 12 = 4096个id，每秒则为：1000 * 4096 约等于400w，也就说理论上单机可以达到400w的QPS（实际测得300多w），基本能满足大多数需要生成id的业务场景。

举例：

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

优点：

• 不需要依赖数据库等第三方系统。
• 高位为毫秒数，低位为递增序列号，因此整体趋势递增。
• 可根据自身业务灵活分配bit位。

缺点：

• 强依赖于时钟，如果出现时钟回拨，会导致id重复或整个服务不可用。
• 由于ID的趋势递增且可计算，对于竟对而言容易暴露业务量，不适用于订单的ID。

方案五：Leaf-snowflake

Leaf-snowflake对于位数完全沿用来snowflake64bit的设计，但在snowflake方案中，如果集群机器较少，workerID完全可以手工进行管理，而在大规模集群下手工管理就变得不大现实，因此Leaf-snowflake方案首先做的就是利用zookeeper的持久化顺序节点特性，对workerID进行管理。

具体如下：

1、启动leaf服务时连接zk检查本服务（ip+port）是否已经注册过持久化顺序节点

2、已注册过则取回自己的int类型的workerID，并启动服务

3、如果未注册则创建一个持久化顺序节点，并取回顺序号作为workerID，启动服务。

发号服务的具体架构图如下：

image.png

Leaf-snowflake带来的zookeeper强依赖问题

我们发现，由于发放服务启动时需要确定能够生成workerID，而workerID的生成要强依赖于zk，所以如果在启动服务时zk出现故障，且又恰逢发号服务在重启，会导致服务启动失败。对于这个问题也很好解决，与dubbo缓存注册中心返回的服务IP地址的做法类似，因为workerID对服务而言一般是不变的，所以在zk第一次返回workerID时，我们可以用一个workerID文件进行存储，在zk出现问题时也可以保证服务正常启动。

解决时钟回拨问题

snowflake最大的问题就是强依赖于时钟，而Leaf-snowflake给出的方案，也是在zk持久化顺序节点进行解决，具体做法：

1、启动Leaf服务时判断是否已写过leaf-forever节点，是则拿当前服务时间戳与节点上的时间戳leaf_forever/{self}，说明机器出现大步长的回拨，需要告警，且不允许启动。

2、如果不存在节点，则创建leaf_forever/${self}并写入当前服务器时间，同时比对其余Leaf节点的系统时间来判断自身系统时间在集群中是否准确，具体做法：取leaf_temporary下所有临时节点，同时通过rpc调用获取其他节点的系统时间，计算sum(time)/nodesize。

3、假如abs（系统时间-sum(time)/nodesize）< 阀值说明正常，可以启动，同时写入临时节点leaf_temporary/${self}进行租约。反之认为本机发生大步长偏移，启动失败并告警。

4、后台启动线程每3s上报自身系统时间写入leaf_forever/${self}。

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

//发生了回拨，此刻时间小于上次发号时间
if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
            //时间偏差大小小于5ms，则等待两倍时间
            wait(offset << 1);//wait
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
               //还是小于，抛异常并上报
                throwClockBackwardsEx(timestamp);
              }    
        } catch (InterruptedException e) {  
           throw  e;
        }
    } else {
        //throw
        throwClockBackwardsEx(timestamp);
    }
}
//分配ID

总结

对于一个大型分布式系统而言，必然会有不同的业务场景需要用到分布式ID来对某些数据做唯一标志。如果某个业务所需要的ID只需在内部展示而不会对外暴露，这种情况可以考虑用Leaf-segment的双buffer方案来生成ID，因其部署与应用还是比较简单的，除了在数据库中新增一张表以外，不用再依赖到第三方组件（在不过多考虑mysql高可用部署方案情况下），且正常情况下ID是单调递增的，这对于内部运营人员而言会更加友好。而如果是订单系统、账务系统等涉及到需要对外暴露订单流水号、且并发量较高的场景，则Leaf-snowflake更为适用，因其bit位可以灵活变换，对外能做到业务信息不易被解读，另外单机400w（理论值）的QPS可以满足大部分并发量较高的业务场景。

参考文献
Leaf--美团点评分布式ID生成系统