分布式id生成器设计分享

分布式环境下，大家可能经常会遇到需要一个全局唯一的id的需求，常见的方案雪花算法（SnowFlake）大家应该也很熟悉了，今天来分享一个分布式id生成器的设计思路，代码因为公司原因，就不贴出来了

先来分析一下分布式id生成器的应用场景

1.数据库分表分库后的主键

• 业务数据库由于量级问题分库分表后，需要一个分布式主键id器，来生成主键，保证数据的主键id唯一
• 这种场景下，生成的id最好基于时间自增，因为数据主键一般使用聚簇索引，基于时间自增的主键，可以避免随机IO导致的数据库写入性能低下

2.服务调用链路追踪的traceId

• 在目前微服务架构流行的情况下，有很多分布式追踪方案应用而生，来追溯监控整个服务调用链路，来排查问题或者查看链路各个节点的响应时间，很多方案中，都会生成一个唯一id,作为traceId来追踪整个服务调用链
• 这种场景下，因为要记录追踪每一次调用，生成的id除了要求唯一之外，还要求生成的效率高、吞吐量大

再来说一下我们这次设计的背景

我们设计分布式id生成器的背景

• 1.随着业务的快速发展，我们一个服务的调用方越来越多，需要做水平扩容来提高服务的吞吐量；
• 2.该服务中，分布式id生成逻辑耦合在服务逻辑代码中，目前分布式id生成的方案是基于snowflake雪花算法来生成；
• 3.id为64bit位的long类型，算法只使用了3位bit位作为机器码，所以导致只能扩展到8个节点，严重制约了我们服务的水平扩展能力；
• 4.而且每个节点的机器码是存储到配置文件中的，导致每一个版本上线时候，都需要根据要上线的节点，修改配置文件的机器码，造成了服务上线流程麻烦，潜在风险很大，并且没有办法实现自动扩容（因为新加节点，要修改配置文件中的机器码）

基于这个背景，我们确立了本次设计的目标

• 1.把分布式id生成器单抽取出来，不和业务服务耦合，作为一个公共工具使用，支持多个服务的分布式id生成需求
• 2.修改生成id的算法，接触节点的扩容限制
• 3.机器码的配置从本地配置文件中提取到一个分布式配置中心，来简化上线流程，降低上线扩容时候的风险点。

分布式id技术选型

说一下分布式id的常用技术选型

UUID

UUID

标准格式说明：

• UUID是128位的bit数组，格式化成36位字符串
• 使用其8-4-4-4-12格式来分割32个16进制字符串
• 目前为止，业界一共有5种方式生成UUID，这里就不详细说了，感兴趣的朋友可以查一下

优点

• 本地算法生成，没有额外的网络请求开销，性能好
• 能作为时间、空间上的唯一，而且接入成本低

缺点：

• 如果使用作为数据库主键，36长度的字符串作为主键，占用物理空间，还占用大量的索引页（聚簇索引，辅助索引）的存储空间
• 使用UUID作为主键，生成ID比较离散，会造成随机IO，导致的数据库写入性能低下

使用场景

• 适用于非数据库主键场景，如幂等id、链路traceId、日志id等

基于mysql、redis等存储的自增序列

• oracle中有序列，但是我基本没用过oracle，这里就拿mysql做例子了

mysql实现：

• mysql实现，主要是利用自增主键auto_increment来实现，生成全局唯一id
• 在分布式系统中，使用一个共用的数据库，创建一张表
• 表的主键是自增式主键
• 每次需要一个全局唯一id时候，在该表中插入一条数据，返回插入成功数据的主键来作为全局唯一的id

redis实现

• redis的实现，主要依赖于redis单线程，使用redis的原子命令incr就可以生成一个全局唯一的id
• 在分布式系统中，使用一个共用的redis，共用一个主键生成key
• 每次使用命令incr就可以生成一个全局唯一的id

优点

• 这里不对比mysql实现和redis实现了
• 实现简单，利用存储各自的特性就可以实现，接入成本小
• 而且主键是可以保证全局唯一并且是严格自增的

缺点

• 利用数据存储系统实现的缺点都差不多
• 性能严重受存储系统的性能制约，以我们公司的存储性能为例，mysql健康的qps在8千左右，redis健康qps在 8万左右
• 扩展性差，难以通过数据分片实现扩展

优化方案

• 实现数据切片，增加多个master节点，通过设计各个节点之间自增的数字不同；来保证master之间不能生成重复ID
• 每个节点可以批量获取多个ID，减少与数据库的交互，提高性能
• 但是多个master节点，太耗资源，基本很少人使用该方案（我见过一个toB的项目使用了）

基于zookeeper实现

实现思路一

• 使用znode数据版本来生成序列号，生成32位和64位的数据版本
• 客户端以这个版本号来作为唯一的序列号
• 每当节点数据变化的时候dataversion的版本号会自增1，可以生成全局唯一的32位id
• 每当修改数据，对应的mzxid（修改事务id）也会自增，可以生成全局唯一的64位id

实现思路二

• 创建一个持久化节点，节点的数据为计数器的值，可以保证多个节点下计数器可以生成全局唯一的id

优点

• 接入成本低
• id可以保证严格全局唯一
• 整个系统可以利用zk的高可靠性

缺点

• zk性能上不上，还不如利用redis实现的性能好

sonwflake

• Twitter在把存储系统从Mysql迁移到Cassandra的过程中，由于Cassandra没有顺序ID生成机制，于是自己开发一套全局唯一id生成算法，Snowflake 雪花算法，根据Twitter的业务需求，Sonwflake系统生成64位的ID由下面三部分组成：
• 41位的时间戳（精准到毫秒，41位的长度可以使用69年）
• 10位的机器码（10位的长度可以最多支持部署1024个节点）
• 12位的计数顺序号（12位的计数器顺序号支持每个节点每毫秒产生4096个序列号）

雪花算法.png

优点

• 因为是本地算法实现的，没有额外的网络开销，所以性能高
• 时间戳在高位，自增序列号在低位，保证唯一的同时，又可以保证基于时间上是严格递增的
• 不依赖于外部存储系统，没有外部依赖的限制

缺点

• 因为高位是时间戳，生成时间戳的过程依赖本地服务的时钟系统
• 如果服务器发生时钟回拨，基于本地时钟系统获取的时间戳可能会造成id重复

我们最后采用了sonwflake雪花算法，在结合我们的业务背景做了一些改动，实现了一个分布式id服务，供团队内的业务使用，这里说一下关键的改动点吧

为了解决机器码本地配置文件存放的问题，我们引入了zk来维护整个分布式id服务各个节点的机器码

• 每个节点启动时，先获取机器id，连接zk
• 判断是否为新增的节点
• 如果是新增的节点，则生成一个唯一的机器码
• 并且持久化到zk中
• 并吧唯一机器码返回给服务节点，服务节点持久化到服务本地
• 如果是已经注册过的节点（节点重启）
• 直接获取生成过的机器码返回给服务节点，服务节点持久化到服务本地

为了减少时钟回拨的影响，利用zk来实现了一个时间校验器

• 定时进行时钟校验
• 服务节点连接zk，把自己的当前时间戳同步到zk，在获取其他节点，进行比较
• 如果有异常，就直接报警处理