本文介绍常见分布式ID方案的实现和原理。分布式ID方案大致可以分为两类，一类的基于数据库的实现，规定起始位置和步长，来实现趋势递增，保障ID不会重叠。一类是类snowflake的实现，将固定位数的字符串划分为不同的段，每一段代表不同的含义，基本上分段中包括：机器序列、时间戳、自增序列，这种方案需要考虑时钟回拨的情况，同时可以通过双buffer的设计来改进ID生产单点性能不足的问题。
一、概述
为什么需要分布式ID设计？
在单体应用的时代，生成的业务数据保存在单个库表中，通过AUTO_INCREMENT=1就能保障业务数据的主键线性不重复的增长，但在分布式应用的时代，由于保存的业务数据不一定在单个库表中，对于唯一主键的需求无法通过单个数据库来满足，所以就需要一个统c一的分布式ID生成方案。
分布式ID是什么？
分布式ID的常见用途是单一业务数据可能会保存在不同的数据库中，需要生产一个统一的主键ID，这中分布式ID的特征是：
- 全局唯一性：生成的ID保障全局唯一性，在单机环境下主键ID具有的特征在分布式环境下也要具备；
- 趋势有序：对于生成的ID需要趋势递增或者趋势递减；
- 信息安全：对于生成ID的方案来说，不能暴露用户的个人信息，比如设备MAC地址；或者通过生成的分布式ID分布规律能够推导出时间范围内分布式ID的个数，这个对于商业上来说有一定风险；
二、常见方案
1、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太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。
- 信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
- ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用：（1）MySQL官方有明确的建议主键要尽量越短越好[4]，36个字符长度的UUID不符合要求。（2） 对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
实现：
可以直接使用jdk自带的UUID，原始生成的是带中划线的，如果不需要，可自行去除。
public class UUIDService { public static void main(String[] args) { for (int i = 0; i < 5; i++) { String rawUUID = UUID.randomUUID().toString(); System.out.println(rawUUID); //去除"-" String uuid = rawUUID.replaceAll("-", ""); System.out.println(uuid); } } }
2、基于MySQL数据库实现
对于基于MySQL数据库来生成分布式ID有两种思路，（1）一种是创建专门生成分布式ID的表来实现，（2）另一种是对分布式环境下多个数据库中划分范围不重叠的ID。
对于方案（1），需要先创建数据库表sequence_id，其中stub字段是无意义的占位字段，id字段是生产的分布式ID。
CREATE TABLE `sequence_id` ( `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT, `stub` char(10) NOT NULL DEFAULT '', PRIMARY KEY (`id`), UNIQUE KEY `stub` (`stub`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
再通过REPLACE INTO更新语句可以生产分布式ID，该语句作用是如果主键id不存在则insert，如果主键id存在则update。
BEGIN; REPLACE INTO sequence_id ( stub ) VALUES ( 'stub' ); SELECT LAST_INSERT_ID(); COMMIT;
对于方案（2），我们考虑的角度是分布式环境下多个数据库生产分布式ID会造成冲突，原因是多个数据库采用相同的起始位置，在相同的范围区间内生成分布式ID，这样会导致生成的ID重叠。如果我们规定每个数据库采用不同的起始位置在不同的范围区间内生成ID则可以避免这个问题。在MySQL中，规定字段auto_increment_increment和auto_increment_offset来保证ID自增。
auto_increment_offset：表示自增长字段开始的位置，不同的数据库其起始位置不同；auto_increment_increment：表示自增长字段每次递增的步长，规定分布式环境下数据库具有相同的步长；
优点：
- 非常简单，利用现有数据库系统的功能实现，成本小，ID号单调自增，存储消耗空间小。
缺点：
- 由于每次生产ID都需要请求MySQL，但鉴于MySQL数据库的性能，该种方案可能存在单点问题，所以该种方案的并发量可能不大；
- 对于方案（2），由于设计的步长正好是数据库的数量，所以设计好起始位置和步长后再扩展数据库就无法生产不重叠的ID，所以该种方案的扩展性不强；
- 存在信息安全问题，由于利用数据库生产的ID都是趋势递增的，所以能很简单的算出时间段内生成的ID数量，对于订单业务来说，很容易就会被掌握真实订单量。
3、基于Redis的KV数据库实现
通过redis来实现分布式ID，主要是通过：incr sequence_id_biz_type 原子自增命令来实现，由于redis是单线程读写的特性，保障生成ID都是串行执行的，所以能保证分布式ID的唯一性。这种方案和基于MySQL数据库实现方案一样，需要依赖外部组件，系统复杂性的增加意味着系统稳定性的下降，但相对MySQL方案redis方案生成ID的性能会更高。这种方案的缺点是由于redis是内存数据库，在断电和重启之后数据会失效，由于redis具有RDB和AOF的持久化数据机制，在一定程度可以解决该问题，但依旧无法完全保障数据的一致性。
4、雪花算法snowflake实现
雪花算法snowflake是一种划分命名空间来生成分布式ID的实现方式，他是Twitter 开源的分布式 ID 生成算法（twitter-archive/snowflake:https://github.com/twitter-archive/snowflake/tree/snowflake-2010）。snowflake算法将64bit划分为多段，主要包括时间戳、机器码、序列号，在Java中可以用Long数据类型来保存。
- 第1bit位占用1bit，其值始终是0，可看做是符号位不使用。
- 第2bit位开始的41位是时间戳，41-bit位可表示2^41个数，每个数代表毫秒，那么snowflake算法可用的时间年限是
(1L<<41)/(1000L360024*365)=69 年的时间。 - 中间10bit位可表示机器数，即2^10 = 1024台机器，但是一般情况下我们不会部署这么台机器。如果我们对IDC（互联网数据中心）有需求，还可以将 10bit 分 5bit 给 IDC，分5bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，具体的划分可以根据自身需求定义。
- 最后12bit位是自增序列，可表示2^12 = 4096个数。
理论上snowflake算法的QPS约为409.6w/s，这种分配方式可以保证在一毫秒一个数据中心的一台机器上可产生4096个有序的不重复的ID。但是我们 IDC 和机器数肯定不止一个，所以毫秒内能生成的有序ID数是翻倍的。
优点：
- 整个序列是趋势递增的。由于时间戳在高位，序列号在低位，所以生成的分布式ID是递增的；
- 由于将序列进行分段的设计，不同分段可以代表不同业务含义，可以自定义实现分布式ID中的序列含义；
- snowflake算法不需要依赖第三方组件，有效降低服务间的耦合，提升服务的可靠性；
缺点：
- 生成的ID强依赖机器时钟，所以当发生时钟回拨是可能就产生生成的ID重复的问题，在Twitter 开源的分布式 ID 实现中，出现这种问题是通过简单报错来处理的。但在后续的
百度UidGenerator和美团leaf-snowflake实现中都得到了改进。
5、百度UidGenerator实现
百度UidGenerator的实现还是基于snowflake算法来改进的，UidGenerator提供两种分布式ID的实现，一种是DefaultUidGenerator，一种是CachedUidGenerator，其主要改进的方面包括支持自定义WorkId位数和自定义初始化策略。（baidu/uid-generator：https://github.com/baidu/uid-generator）
UidGenerator 依然是以划分命名空间的方式将 64-bit位分割成多个部分，只不过它的默认划分方式有别于雪花算法 snowflake。它默认是由 1-28-22-13 的格式进行划分。可根据你的业务的情况和特点，自己调整各个字段占用的位数。
- 第1位仍然占用1bit，其值始终是0。
- 第2位开始的28位是时间戳，28-bit位可表示2^28个数，这里不再是以毫秒而是以秒为单位，每个数代表秒则可用
（1L<<28）/ (360024365) ≈ 8.51年的时间。 - 中间的 workId （数据中心+工作机器，可以其他组成方式）则由 22-bit位组成，可表示 2^22 = 4194304个工作ID。
- 最后由13-bit位构成自增序列，可表示2^13 = 8192个数。
其中 workId （机器 id），最多可支持约420w次机器启动。内置实现为在启动时由数据库分配（表名为 WORKER_NODE），默认分配策略为用后即弃，后续可提供复用策略。对于DefaultUidGenerator实现，相较于snowflake算法改进了WorkId自定义的策略，并且支持的时间戳以秒做单位了，总体来说改动不大，下面重点分析CachedUidGenerator的实现。
CachedUidGenerator主要改进了生产ID的性能，其通过双Ring Buffer来存储ID和表征ID是否被使用的Flag。其中Tail表示生成的最大ID，Cursor表示目前消费的ID位置，由于是环形队列，所以当消费数量赶上生产数量，即Cursor赶上Tail时，就会通过rejectedTakeBufferHandler进行异常处理，如果生产数量超过环形队列空闲容量，即Tail赶上Cursor是，就会通过rejectedPutBufferHandler进行异常处理。
优势 ：
- CachedUidGenerator在初始化RingBuffer的时候可以通过预填充的方式提升性能。
- 消费的时候，可以通过检查slot余量，当低于设定阈值的时候，则进行即时补充。
- 周期填充，通过异步线程周期性填充到slot中。
6、美团Leaf实现
Leaf是美团基础研发平台推出的一个分布式ID生成服务，名字取自德国哲学家、数学家莱布尼茨的著名的一句话：“There are no two identical leaves in the world”，世间不可能存在两片相同的叶子。Leaf算法有两种实现，一种是Leaf-segment是实现，一种是Leaf-snowflake实现，前者需要引入MySQL数据库来分配segment区间来实现业务在规定范围内的趋势递增。后者实现是在snowflake算法上的改进，通过Zookeeper的持久化顺序节点来为WorkId分配序号，满足分布式ID的顺序特征。
Leaf-segment实现
Leaf-segment方案，是在基于MySQL数据库实现方案上的改进，原MySQL方案每次获取ID都得读写一次数据库，造成数据库压力大。改为批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。各个业务不同的发号需求用biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。
数据库表设计如下：
重要字段说明：biz_tag用来区分业务，max_id表示该biz_tag目前所被分配的ID号段的最大值，step表示每次分配的号段长度。原来获取ID每次都需要写数据库，现在只需要把step设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step。
Leaf-segment通过双Buffer来提升性能。Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。
为此，希望DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。采用双buffer的方式，Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。
Leaf-snowflake实现
Leaf-segment实现存在的问题是生成的ID是趋势递增的，可以通过计算得到固定时间内的生成的ID，在某些业务中就能很简单得到生成的订单量，存在业务上的风险。Leaf-snowflake借鉴snowflake算法，也是沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装ID号，其中workID在设备数量较少的时候可以人工分配，当在设备数比较多的时候，可以借助Zookeeper的持久化顺序节点来为WorkId分配序号。
启动Leaf-snowflake服务的流程：
- 启动Leaf-snowflake，连接Zookeeper，在leaf_forever节点下检查自己服务是否注册；
- 如果该服务已经注册，则取回该节点的值，作为WorkID；
- 如果该服务没有注册，在leaf_forever节点创建一个子节点，创建成功后取回顺序号作为自己的WorkID；
Leaf-snowflake的亮点在于一定程度解决了时钟回拨的问题，其思路是每个服务会周期性的上报自身的系统时间，新的节点在注册的时候会比较自身节点和其余leaf节点的系统时间，如果偏差过大则会报错，运行中的节点也会比较自身系统时间和其他leaf节点的系统时间。
- 新节点通过检查综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确，具体做法是取所有运行中的Leaf-snowflake节点的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize，然后看本机时间与这个平均值是否在阈值之内来确定当前系统时间是否准确，准确正常启动服务，不准确认为本机系统时间发生大步长偏移，启动失败并报警。
- 在ZooKeeper 中登记过的老节点，同样会比较自身系统时间和ZooKeeper 上本节点曾经的记录时间以及所有运行中的Leaf-snowflake节点的时间，不准确同样启动失败并报警。
- 在运行过程中，每隔一段时间节点都会上报自身系统时间写入ZooKeeper 。
代码实现：https://gitee.com/yangnk42/yangnk-mall/tree/master/UniqID
三、总结
TODO
- 完善总结部分
参考资料
- 分布式系统 - 全局唯一ID实现方案：https://www.pdai.tech/md/arch/arch-z-id.html
