一、背景

在复杂分布式系统中，特别是微服构架中，往往需要对大量的数据和消息进行唯一标识。随着系统的复杂，数据的增多，分库分表成为了常见的方案，对数据分库分表后需要有一个唯一ID来标识一条数据或消息（如订单号、交易流水、事件编号等），此时一个能够生成全局唯一ID的系统是非常必要的。
业务对分布式ID规则有哪些要求？对分布式ID系统有什么要求？分布式ID算法有哪些？业内大厂是怎么用的？我们又是怎么玩的？接下来一 一揭晓。

二、分布式序列要求

分布式序列是一个通用的产品，要满足以要求：
1、全局唯一性
  在同一场景下不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
2、趋势递增
  在主键的选择上面我们应该尽量使用有序的主键保证写入性能、同时有利于索引提高查询的性能。
3、序列数据类型
  序列的数据类型决定的存储空间大小，序列尽可能用整类型，以MYSQL bigint unsigned为例存储空间为8字节，范围(0~2*2^63-1 )是一个极大的整数，足以满足需求。
4、简单易用
  能够拿来即用，接入方便，同时在系统设计和实现上要尽可能的简单。

三、序列常用算法

3.1、UUID

UUID 含义是通用唯一识别码 (Universally Unique Identifier)，这是一个软件建构的标准。
UUID是由一组32位数的16进制数字所构成，UUID理论上的总数为16³²⁼²128。若每纳秒产生1兆个UUID，要花100亿年才会将所有UUID用完。

UUID组成：
标准的UUID格式为：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)。
优点:
1、本地生成，无依赖，速度极快，序号个数无限。
2、序号全局唯一性。
不足：
1、序列无规律，对索引不友好。
2、字段串由数字与字母成合，存储空间大。

3.2、雪化算法(snowflake)

snowflake是Twitter开源的分布式ID生成算法，支持多语言(Java、go、scala等),结果是一个64bit大小的整型的ID。

结构图如下：

image.png

标识名称	位数	说明
标识	1bit	正数是0，负数是1，ID一般是正数，最高位是0。
时间截	41bit	存储时间截的差值，41位的时间截，毫秒级，可以使用69年。
数据机器位	10bit	最大支持1024个节点，包括5位datacenterId和5位workerId。
序列号	12bit	毫秒内的计数，12位的计数顺序号最大支持每个节点每毫秒产生4096个ID序号。

优点:
1、本地生成，无依赖。
2、整型，趋势递增，有利于索引。
3、效率较高，理论每节点每秒最大能产生26万ID。
不足：
1、依赖机器时间，如果发生时钟回拨会导致可能生成id重复。
2、workid节点有限，无存储容易碰撞，在超大服务集群使用有风险。

3.3、基于DB数据段算法

利用DB表的存储机制，表主要字段有：命名空间、当前最大值、步长、版本号。通过步长的大小及利用缓存数据段来控制，解决DB的性能瓶颈，提高效率。

数据库表主要字段：

字段code	字段名称	说明
namespace	命名空间	业务场景，用于区分不同的业务。业务之间相互隔间，互不影响。
value	当前最大值	存储时间截的差值，41位的时间截，毫秒级，可以使用69年。
step	步长	每次从数据库获取序号段到服务节点内存，步长越大对DB的压力越小。
version	版本号	用于防并发的乐观锁。
retrytimes	重试次数	乐观锁更新异常时重试次数。

优点:
1、高性能，序列无极限(取决于步长长度)。
2、整型，有顺序，趋势递增，有利于索引。
3、可以自定义value的大小，非常方便业务从原有的ID方式迁移过来。
不足：
1、服务强依赖DB,来存储业务场景、最大值、步长等信息。
2、中心化部署，序列号段缓存服务节点，对序列服务可靠性要求极高。

四、业内大厂序列方案

4.1、美团点评(Leaf)

Leaf美团点评分布式ID生成系统，leaf是基于springboot、以HTTP协议的方式提供获取分布式唯一ID的服务。总计集成了两种模式：Leaf-snowflake算法和Leaf-segment(基于DB数据段算法)。

1、Leaf-segment在基于DB数据段算法上进行了优化：在号段消耗的临界点的ID时，会用异步线程从DB获取新的号段，补充进行到内存中，避免号段消耗再补充新的号段。
2、Leaf-snowflake在原生snowflake进行了优化，弱依赖Zookeeper及延迟3秒上报时间差，可以缓解时间回拔的问题。
优点：
1、Leaf-segment 双buffer优化,避免号段消耗完，再更新DB的TP999波动。
2、Leaf-snowflake 缓解时间回拔的问题。
不足：
1、中心化的部署，通过http获取序列，存在网络开销。
2、Leaf-server故障会影响所有序列的生成，必须保证Leaf-server可用性100%。
部署方式：
中心化部署，leaf-server是基于springboot，以HTTP协议的方式提供获取分布式唯一ID的服务。
开源地址：https://github.com/Meituan-Dianping/Leaf.git

4.2、滴滴出行(Tinyid)

Tinyid是滴滴出行推出的分布序列生成器。Tinyid是基于美团点评分布式ID生成系统（Leaf）基础上进行了优化。

优化办法:
1、双号段缓存，提前异步加载下一个号段，避免号段消耗再补充新的号段。
2、增加tinyid-client,把号段缓存在应用的客户端，有效的减少Tinyid-server的网格开销。
最终架构图如下：

image.png

优点：
1、Tinyid提供http和tinyid-client两种方式接入。
2、tinyid-client有效的减少的网格开销，大大提高了性能。
3、tinyid-server容忍短时间的down掉，大大的提高了可用性。
不足：
暂无
部署方式：
中心化部署，tinyid-server是基于springboot，以HTTP协议及tinyid-client两种方式提供获取分布式唯一ID的服务。
开源地址：https://github.com/didi/tinyid.git

4.3、百度(UidGenerator)

UidGenerator是百度开源的Java语言实现，基于雪花算法的唯一ID生成器。对Snowflake算法的组成部分进行了调整、优化和改进，并解决workid不足及时钟回拨序列重复的问题。它通过消费未来时间克服了雪花算法的并发限制，UidGenerator提前生成ID并压测结果显示，单独实例的QPS理论最大值超过600W。

uid在原生snowflake改进后的结构图：

image.png

标识名称	位数	说明
标识	1bit	正数是0，负数是1，ID一般是正数，最高位是0。
时间截	28bit	存储时间截的差值，28位的时间截，可以使用8.5年(2^28-1/86400/365)。
数据机器位	22bit	最大支持400W个节点。
序列号	13bit	毫秒内的计数，13位的计数顺序号最大支持每个节点每毫秒产生8192个ID序号。

默认调整了各段的位数。
优点：
1、QPS最大值突破生原nowflake算法的限制。
2、解决了时钟回拨序列重复的问题。
3、通过依赖DB优化workid顺序问题，并提升了节点数。
4、snowflake结构图可以自定义调整。
不足：
1、在生原Snowflake算法新增了DB的依赖。
2、因调整时间部分位数，Uid寿命减短，只能承受8.5年（2 ^ 28-1 / 86400/365）。
3、中心化的部署，通过HTTP获取序列，存在网络开销。
4、uid-server故障会影响所有序列的生成，必须保证uid-server可用性100%。
部署方式：
中心化部署，uid-server是基于springboot，以HTTP协议的方式提供获取分布式唯一ID的服务。
开源地址： https://github.com/baidu/uid-generator.git

4.4、阿里(TDDL-sequence)

TDDL（Taobao Distributed Data Layer）是阿里的一个分布式数据库中间件，它在阿里内部被广泛的使用，主要是为了解决分布式数据库产生的相关问题。而tddl-sequence 顾名思义，为解决分布式序列而生的组件。tddl-sequence的原理基于DB数据段算法，以客户端JAR方式的与应用共存，在应用的DB中创建序列表，并利用应用的数据源，在本地生成序列。这种去中心化部署,减少获取序列http接口的网络开销，也不担心seq-server故障的带来的风险。

优点：
1、去中心化部署，本地获取序列，本地缓存号段，极大提高序列的性能。
2、不同应用之间的序列生成互不影响，极大提高容错性了。
不足：
1、接入的复杂度增加，每个应用都要创建自己的序列表。
部署方式：
分布式部署方式，以JAR的方式与应用有机的结合在一起。

五、序列部署方式(中心化 & 分布式)

在前面介绍的各大厂的分布式序列的方案中，部署方式分为：中心化、分布式两方式，两者之间对序列的性能、可用性、数据一致要求是不一样的。

中心化部署：
  中心化部署是指：序列以微服务的方式单部署，连接独立的序列库。提供Http、RPC、restful等协议的接口，给各应用调用并返回序列或号段。
分布式部署：
  分布式部署是指：序列以组件JAR的方式，应用有机的结合一起部署，把序列的相关表，与应用的数据表放一个库，共用数据源。

两者的要求区别如下：

项目	中心化	分布式
高性能	平均延迟和TP999延迟都要尽可能低	当前本地生成，无网络开销，性能高。
可用性	很难实现100%的可用性，但可用性达到99.999(5个9)	与当前应用的可用性一致。

六、总结

分布式序列各大厂公司做法都差不多，无非都是在snowflake、基于DB数据段两大基础算法及结合自身的特点做优化。