新来的技术女总监，推荐的分布式 ID 真香！
在复杂的分布式系统中，常常需要一个全局唯一的 ID来标识数据，消息或者请求，比如：订单号，消息的唯一标识，接口的幂等ID等等。今天，我们一起来聊聊几种常见的分布式ID 生成方式。
一、分布式ID具备什么条件？
分布式 ID，通常建议具备以下 4个条件：
1. 全局唯一全局唯一，是指在支撑的业务范围内能保持全局唯一，这里的全局范围可大可小，大到成千上万个部门的集团，小到某个团队内的几个系统， 所以在设计分布式 ID的时候，一定要清晰地定位受众范围。
2. 数量够用分布式ID，一定要保证数量够用，通常需要根据公司具体业务来评估，在一定时间范围内会消耗多个ID， 比如，用于订单号，需要预估每年会产生多少订单，消耗多少个订单号，需要支撑几年的业务使用。
3. 安全性分布式 ID应该是安全的，防止恶意用户预测或推断出其他ID，如果业务对于这种预测不敏感可以忽略。比如，用于接口幂等使用，只要唯一就 ok。
4. 有序性通常建议分布式 ID具备有序性，方便业务排序使用。
二、生成算法
1. UUIDUUID，是 Universally Unique Identifier，通用唯一识别码的缩写，共128-bit（2^128个），通常表示成 32个十六进制数字，并且以“-”分隔成五组（8bit-4bit-4bit-4bit-12bit）， 比如：62f77d2d-aefe-41ba-b0f8-4c4c39ab670e。
UUID有 5种常见的生成方式，这里总结了构成，用途和特点：
(1) 基于时间戳和 MAC地址
构成：基于当前时间戳、时钟序列和机器的MAC地址。用途：可以确保跨空间（不同机器）和时间的唯一性。特点：可能会暴露生成 UUID的机器地址和时间。Java示例代码，需要依赖 java-uuid-generator 工具：
(2) DCE安全的UUID
构成：与方法1类似，但将一部分空间用于包含 POSIX的 UID或 GID。用途：用于DCE（分布式计算环境）的安全性。特点：并不常用，和方法1相似，但提供了额外的用户或组识别信息。(3) 基于名字的MD5散列
构成：使用名字空间（Namespace）和特定名字生成 MD5散列。java.util.UUID 提供了这种方式，需要传入key，使用比较少。用途：为相同名字生成相同的 UUID，但不同名字空间下的相同名字将生成不同的 UUID。特点：相同输入产生相同输出，但由于 MD5容易被破解，不安全，因此现在使用较少。Java代码示例：
(4) 随机生成
构成：使用随机数或伪随机数生成，java.util.UUID 是基于这种方式，使用比较多。用途：不需要基于时间或名字，仅需要快速生成UUID。特点：简单，没有时间顺序，不具备可预测性。Java代码示例：
(5) 基于名字的 SHA-1散列
构成：与方法3类似，使用 SHA-1散列算法代替 MD5。用途：给相同名字生成相同的UUID，通常用于避免 MD5弱点的场景。特点：比方法3的 MD5更安全，但SHA-1目前也已被认为不够安全，比较少使用。Java代码示例：
到此，我们对 UUID有了一个全面的认识，最后，总结下 UUID的优缺点以及一些使用建议：
优点：
生成方式简单，各种语言都有成熟的类库本地生成，性能高，不依赖网络随机机行强，不容被预测缺点：
无序，不利于排序，用于 MySQL主键时对索引不够友好32位，字符串太长，存储需要消耗更多的空间具体生成 UUID算法的缺点使用建议：
日常工作为了使用更美观，一般会把 UUID中的 “-”去掉如果对 UUID的缺点没有任何要求，完全可以采用这种方式来生成分布式 ID，比如，作为接口的幂等IDUUID有重复的概率，但是几乎可以忽略不计2. ULIDULID 是 Universally Unique Lexicographically Sortable Identifier的缩写，它是一种全局唯一、按字典序可排序的标识符。
ULID 由 48-bit的时间戳 + 80-bit 的随机数组成，时间戳表示自 1970 年 1 月 1 日 UTC 起的毫秒数，可以支持大约 280 年的时间范围。
下面借助三方库 Sulky ULID 演示如何使用 Java 生成 ULID：
最后总结下 ULID 的优缺点：
优点：
可排序：ULID 由 48-bit 时间戳开头，可以按照生成时间进行排序高性能：由于 ULID 使用时间戳和随机数，生成速度较快。缺点：
ULID 依赖于时间戳，极端情况可能会出现时间回拨导致 ID冲突3. 基于 Redis在 Redis中，可以通过 INCR 和 INCRBY 这样的自增原子命令，来实现有序的分布式ID：
下面总结下 Redis的优缺点：
优点：
高性能生成的 ID有序缺点：
需要增加 Redis的成本强依赖 Redis，因此需要保证 Redis服务的稳定性生成的ID 有序，对于敏感业务，ID容易被预测4. 基于MySQL通过 MySQL数据表的主键（int 或 bigint）自增来生成分布式 ID，因此，首先来看看 int 和 bigint 类型支持的数据范围。
int（或 integer）：
无符号的范围是 0 到 4294967295（42亿多）有符号的范围是 -2147483648 到 2147483647bigint：
无符号的范围是 0 到 18446744073709551615有符号的范围是 -9223372036854775808 到 9223372036854775807假如每天消耗 1亿个，使用总年数：18446744073709551615 / 100,000,000 / 365 ≈ 505061753 年。
假如每天消耗 1万亿个，使用总年数：18446744073709551615 / 100,000,000,000,0 / 365 ≈ 50506 年（5万年）。
使用 MySQL的 bigint，就算业务体量每天消耗一万亿个 ID，也需要 5万年才能消耗完，绝对够用。
接下来分析 2种常见生成方式：
(1) MySQL乞丐版
首先，创建一张 distributed_ids表，用于记录已经生成的 ID（如果 ID不想从 1开始，可以在创建表时给主键 ID设置一个起始值），表设计如下：
接着，我们需要包装一个 ID生成的服务对外提供给业务使用，整体架构思路图如下：
下面为对外提供服务核心步骤的 java伪代码：
到此，一个简单的 ID生成系统就完成了，总结下该方案的优缺点：
优点：
实现简单，维护成本低ID单调递增可以用较少的成本实现体量较小的业务需求缺点：
每次获取 ID时候需要进行两次 DB操作强依赖于 DB，DB性能以及稳定性直接影响 ID生成系统的稳定性，而且这里有 DB单节点的风险对于缺点中单台 MySQL存在性能问题，我们自然会想到增加一台 MySQL，一台使用奇数自增（1,3,5,7,2n-1），一台使用偶数自增(2,4,6,8,2n)，这样是不是就可以分摊压力了？如果 2台 MySQL还不够用，那我们可以使用 N台，每台的初始值依次为 1, 2, 3 … N-1，步长是N（机器的数量），整个架构思路图如下：
仔细观察上述架构图可以发现，对于 MySQL节点选择其实本质上是一个 Hash算法，因此，该方案存在 Hash算法典型的缺点：水平扩容困难，扩容时，需要涉及到大量的数据迁移。
那么，有没有一个更优的设计方案，既能减少对 DB的操作，又能避免 DB的性能瓶颈？
(2) MySQL号段版
号段版是指每次获取一批 ID（比如 1000，10000），而不是一个 ID，然后在内存中去分发号段内的号码。对此，表结构该如何设计呢？
这里我们引入了号段最大值（max_id） 和步长（step）两个概念，max_id是指表中末次获取号段时的最大 ID号，step是指每次获取多少个 ID。比如，初始值是 1，第一次获取 1000个ID，那 max_id=1000， step=1000，第二获取 1000个ID，那么 max_id=2000， step=1000，表结构设计如下：
整体架构思路图：
对于这个方案中的 step设置多大比较合理，一般会参考流量高峰期的是QPS/TPS， 假设高峰期的 QPS是 1000（1s会消耗 1000个ID）， 如果想取用一次号段持续使用 10分钟，那么 step=1000 * 60 * 10，即 step是 QPS的 600倍，以此类推， 也可以参考以往业务流量分布，确认峰值一般会维持多长时间，根据这个时间来设定一个合理的 step，这样就可以避免业务高峰期频繁去操作 DB获取号段。
总结下方案的优缺点：
优点：
一次批量获取 ID，大大降低了对 MySQL的压力，比如QPS是 1万，如果 step设置为1000， 那么对 MySQL的压力就从 10000降到 10step可以更具业务压力灵活调整，可以将此参数设置为配置变量缺点
DB不可用导致整个ID生成系统不可用ID规律性太强，很容易识别语义，比如，用于订单号时，可以根据某一个订单号轻易地猜测出其他订单号对于缺点1，可以采用高可用容灾方案：主从（一主多从） + 多活（2 地 3活），当主节点挂了，需要将从节点切换成主节点，当机房A 出现问题， 可以切换到机房B，这样充分保证了服务的高可用，思路看起来简单，但实施起来比较困难，特别是主从切换的时候，如何保证数据一致性是一个比较大的挑战。
对于缺点2，可以采用雪花算法等方案来生成随机且递增的 ID，在下文的三方工具里有很好的实现。
整个高可用容灾方案如下图：
Snowflake，雪花算法是由 Twitter开源的分布式 ID生成算法，整个ID包含 64-bit，对应 Java的 Long类型，如下图：
为了更好地说明，本文将 64-bit 分成A, B, C, D 4部分：
A部分，占用 1-bit，代表符号位，其值始终是0B部分，占用 41-bit，代表时间戳，可表示 2^41 个数，每个数代表毫秒，雪花算法可用的时间年限大概是 69年。C部分，占用 10-bit，代表机器数或者 IDC（数据中心）+ 机器数，如果是机器数，即 2^10 = 1024 台机器，如果是 IDC+机器数， 一般 5-bit 用于 IDC（最大 32个IDC）C，5-bit用于工作机器（最大 32台机器），这里可以根据自身业务灵活调整。D部分，占用 12-bit，代表自增序列，可表示 2^12 = 4096个数。基于上述的划分可以看出，每豪秒能产生 1024 * 4096个有序不重复的ID。
最后，总结下雪花算法的优缺点：
优点：
本地生成，不依赖数据库等第三方系统，稳定性高ID是趋势递增，对于敏感业务，不具备可预测性可以根据自身业务特性灵活分配 bit位缺点：
强依赖机器时钟，如果时钟回拨，可能会导致 ID重复6. 三方工具(1) 美团的 Leaf
Leaf是美团开源的分布式 ID生成工具，它包含 Leaf-segment 和 Leaf-snowflake两种方案， Leaf-segment是基于 MySQL数据库，它是针对上述 MySQL方案的更优秀设计，Leaf-snowflake 是基于雪花算法，并且解决雪花算法中时钟回拨的问题。
详情参考官方文档：https://tech.meituan.com/2017/04/21/mt-leaf.html
(2) 滴滴的TinyID
Tinyid是用Java开发的一款分布式id生成系统，基于数据库号段算法实现，Tinyid扩展了leaf-segment算法，支持了多db(master)，同时提供了java-client(sdk)使id生成本地化，获得了更好的性能与可用性。
详情参考官方文档：https://github.com/didi/tinyid/wiki
(3) 百度-UidGenerator
UidGenerator 百度开源的一款用 Java语言实现，基于 Snowflake算法的唯一ID生成器。包含 DefaultUidGenerator 和 CachedUidGenerator 2种实现方式：
DefaultUidGenerator 是基于时间戳和机器位还有序列号的生成方式，和雪花算法很相似，对于时钟回拨也只是抛异常处理。仅有一些不同，如以秒为为单位而不再是毫秒和支持Docker等虚拟化环境。CachedUidGenerator 是使用 RingBuffer 缓存生成的id。数组每个元素成为一个slot。RingBuffer容量，默认为Snowflake算法中sequence最大值（2^13 = 8192）。可通过 boostPower 配置进行扩容，以提高 RingBuffer 读写吞吐量。详情参考官方文档：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
三、总结
本文分析了几种常见的分布式 ID生成方式，具体选用哪种可以根据自身业务而定：
UUID简单高效，但是无序，如果作为 MySQL的ID主键，对于索引不太友好ULID 很好的解决了UUID无序的问题，极端情况下存在时间回拨导致ID重复的风险基于 Redis生成的 ID有序，性能高，需要引入和维护 RedisMySQL 乞丐版，实现简单，但是不适合大流量的场景MySQL 号段版，适合大流量的场景，但是，当 MySQL主节点故障时，主从切换需要保持数据的一致性雪花算法，有序且不易预测，算法很优秀，不过需要解决时钟回拨的问题三方工具，经过生产环境的考验，是很不错的方式，如果不想重复造轮子，优先推荐该方式