分布式id生成策略

一。背景

系统唯一ID是我们在设计一个系统的时候常常会遇见的问题，也常常为这个问题而纠结。生成ID的方法有很多，适应不同的场景、需求以及性能要求。所以有些比较复杂的系统会有多个ID生成的策略。下面就介绍一些常见的ID生成策略。

那业务系统对ID号的要求有哪些呢？

全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。

趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。

单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。

信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。

二。分布式id生成方案

方案一：UUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：

优点：

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

缺点：

不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。

信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。

ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用.

方案二：snowflake方案

这种方案大致来说是一种以划分命名空间来生成ID的一种算法，这种方案把64-bit分别划分成多段，分开来标示机器、时间等，比如在snowflake中的64-bit分别表示如上图。

41-bit的时间可以表示（1L

理论上snowflake方案的QPS约为409.6w/s。

优点：

毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。

不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。

可以根据自身业务特性分配bit位，非常灵活。

缺点：

强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

应用举例Mongdb objectID

方案三：数据库生成

以MySQL举例，利用给字段设置和来保证ID自增，每次业务使用下列SQL读写MySQL得到ID号。

优点：

非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护。

ID号单调自增，可以实现一些对ID有特殊要求的业务。

缺点：

强依赖DB，当DB异常时整个系统不可用，属于致命问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。

ID发号性能瓶颈限制在单台MySQL的读写性能。

方案四：Leaf-segment数据库方案

第一种Leaf-segment方案，在使用数据库的方案上，做了如下改变

优点：

Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。

ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。

容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。

可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。

缺点：

ID号码不够随机，能够泄露发号数量的信息，不太安全。

TP999数据波动大，当号段使用完之后还是会在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。

DB宕机会造成整个系统不可用。

双buffer优化

Leaf-segment方案可以生成趋势递增的ID，同时ID号是可计算的，不适用于订单ID生成场景，比如竞对在两天中午12点分别下单，通过订单id号相减就能大致计算出公司一天的订单量。

方案五：Leaf-snowflake方案

对于workerID的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf服务规模较大，动手配置成本太高。所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。

步骤启动的：

弱依赖ZooKeeper

除了每次会去ZK拿数据以外，也会在本机文件系统上缓存一个workerID文件。当ZooKeeper出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。

解决时钟问题

因为这种方案依赖时间，如果机器的时钟发生了回拨，那么就会有可能生成重复的ID号，需要解决时钟回退的问题。

若写过，则用自身系统时间与leaf_forever/$节点记录时间做比较，若小于leaf_forever/$时间则认为机器时间发生了大步长回拨，服务启动失败并报警。

若未写过，证明是新服务节点，直接创建持久节点leaf_forever/$并写入自身系统时间，接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确，

具体做法是取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize。

若abs( 系统时间-sum(time)/nodeSize )

否则认为本机系统时间发生大步长偏移，启动失败并报警。

每隔一段时间(3s)上报自身系统时间写入leaf_forever/$。