分布式环境下，大家可能经常会遇到需要一个全局唯一的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，在获取其他节点，进行比较
- 如果有异常，就直接报警处理
