如何生成分布式ID（分布式生成唯一id的生成方式）

今天我们聊的是在分布式服务中如何生成分布式ID，本文讨论了几种生成分布式ID的方案及优缺点，笔者推荐的是Twitter公司开源的snowflake算法。

什么是分布式ID

在不分表的情况下，数据的唯一ID，可以通过数据库自增ID来生成。但在互联网的分布式系统中，由于数据量成指数级的增长，对数据分库分表后需要有一个唯一ID来标示，数据库的自增ID显然不能满足需求。所以在这种情况下，需要一个服务全局唯一ID，即分布式ID。

分布式ID有哪些特点

• 全局性唯一：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
• 趋势递增：多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
• 支持高性能：除了对分布式ID码自身的要求，分布式ID生成需支持高QPS，高可用。

分布式ID生成方案选择

第一种方案：Sequence ID

数据库自增长序列或字段，是最常见的方式。由数据库维护。

一.优点：

• 简单，代码方便，性能可以接受。
• 数字ID天然排序，对分页或者需要排序的结果很有帮助。

二.缺点：

• 不同数据库语法和实现不同，数据库迁移的时候或多数据库版本支持的时候需要处理。
• 在单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成。有单点故障的风险。
• 在性能达不到要求的情况下，比较难于扩展。

三.优化方案：

针对主库单点，如果有多个Master库，则每个Master库设置的起始数字不一样，步长一样，可以是Master的个数。
如：Master1 生成的是 1，4，7，10，Master2生成的是2,5,8,11 Master3生成的是 3,6,9,12。这样就可以有效生成集群中的唯一ID，也可以大大降低ID生成数据库操作的负载。

第二种方案：UUID算法

一.概念：UUID是通用唯一识别码（Universally Unique Identifier)的缩写，开放软件基金会(OSF)规范定义了包括网卡MAC地址、时间戳、名字空间（Namespace）、随机或伪随机数、时序等元素。利用这些元素来生成UUID。

UUID是由128位二进制组成，一般转换成十六进制，然后用String表示。在java中有个UUID类,在他的注释中我们看见这里有4种不同的UUID的生成策略:

* <p> The version field holds a value that describes the type of this {@code
 * UUID}.  There are four different basic types of UUIDs: time-based, DCE
 * security, name-based, and randomly generated UUIDs.  These types have a
 * version value of 1, 2, 3 and 4, respectively.

• randomly: 基于随机数生成UUID，由于Java中的随机数是伪随机数，其重复的概率是可以被计算出来的。
• time-based:基于时间的UUID,这个一般是通过当前时间，随机数，和本地Mac地址来计算出来，自带的JDK包并没有这个算法的我们在一些UUIDUtil中，比如我们的log4j.core.util，会重新定义UUID的高位和低位
• DCE security:DCE安全的UUID。
• name-based：基于名字的UUID，通过计算名字和名字空间的MD5来计算UUID。

二 .优缺点：

优点：

• 性能非常高：本地生成，没有网络消耗。

缺点：

• 不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。
• 信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
• ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用：

① MySQL官方有明确的建议主键要尽量越短越好[4]，36个字符长度的UUID不符合要求。

All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.*** If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key***.

② 对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。

三.适用场景：

UUID的适用场景可以为不需要担心过多的空间占用，以及不需要生成有递增趋势的数字。在Log4j里面他在UuidPatternConverter中加入了UUID来标识每一条日志。全链路ID可以用 。

四.优化方案：

为了解决UUID不可读，可以使用UUID to Int64的方法。

第三种方案：snowflake算法

它是Twitter公司开源的算法。也是笔者推荐的算法。

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。

一.结构：

第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位 datacenterId和5位workerId(10位的长度最多支持部署1024个节点） ，最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）一共加起来刚好64位，为一个Long型。(转换成字符串长度为18)snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由 datacenter和workerId作区分），并且效率较高。这个算法单机每秒内理论上最多可以生成1000*(2^12)，也就是409.6万个ID。

上面只是一个将64bit划分的标准，当然snowflake算法可以根据自身项目的需要进行一定的修改。比如估算未来的数据中心个数，每个数据中心的机器数以及统一毫秒可能的并发数来调整在算法中所需要的bit数。

二.业务场景：

举个例子，如有一个业务场景

• 服务目前QPS10万，预计几年之内会发展到百万。
• 当前机器三地部署，上海、北京、青岛。
• 当前机器10台左右，预计未来会增加至百台。

这个时候我们根据上面的场景可以再次合理的划分62bit,QPS几年之内会发展到百万，那么每毫秒就是千级的请求，目前10台机器那么每台机器承担百级的请求，为了保证扩展，后面的循环位可以限制到1024，也就是2^10，那么循环位10位就足够了。

机器三地部署我们可以用3bit总共8来表示机房位置，当前的机器10台，为了保证扩展到百台那么可以用7bit 128来表示，时间位依然是41bit,那么还剩下64-10-3-7-41-1 = 2bit,还剩下2bit可以用来进行扩展。

三 .优缺点

优点：

不依赖于数据库，灵活方便，且性能优于数据库。ID按照时间在单机上是递增的。

缺点：

在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，也许有时候也会出现不是全局递增的情况。

四.防止时钟回拨

因为机器的原因会发生时间回拨，我们的雪花算法是强依赖我们的时间的，如果时间发生回拨，有可能会生成重复的ID，在我们上面的nextId中我们用当前时间和上一次的时间进行判断，如果当前时间小于上一次的时间那么肯定是发生了回拨，普通的算法会直接抛出异常,这里我们可以对其进行优化,一般分为两个情况:

• 如果时间回拨时间较短，比如配置5ms以内，那么可以直接等待一定的时间，让机器的时间追上来。
• 如果时间的回拨时间较长，我们不能接受这么长的阻塞等待，那么又有两个策略:

1. 直接拒绝，抛出异常，打日志，通知RD时钟回滚。
2. 利用扩展位，上面我们讨论过不同业务场景位数可能用不到那么多，那么我们可以把扩展位数利用起来了，比如当这个时间回拨比较长的时候，我们可以不需要等待，直接在扩展位加1。2位的扩展位允许我们有3次大的时钟回拨，一般来说就够了，如果其超过三次我们还是选择抛出异常，打日志。

通过上面的几种策略可以比较的防护我们的时钟回拨，防止出现回拨之后大量的异常出现。

五. JAVA版本snowflake源码

https://github.com/feigaoalibaba/DistributedID/edit/master/src/main/java/com/edu/distributed/SnowflakeIdWorker.java

小结：

分析了各种生产分布式ID的算法的原理，以及他们的适用场景，相信你已经能为自己的项目选择好一个合适的分布式ID生成策略了。没有一个策略是完美的，只有适合自己的才是最好的。