分布式|全网最全的分布式ID生成方案解析 java|数据库

通过本文可以学到什么

什么是全局唯一ID
全局唯一ID特点
常见的全局唯一ID策略

什么是全局唯一ID 全局唯一ID也就是分布式ID，拿MySQL举个例子，在我们项目初期，数据量不大的时候，单库单表已经可以满足我们的业务需求，数据库稍微在增加些使用MySQL主从也读写分离也可以满足。
随着数据量的增加，在主从同步也无法抗住业务压力的时候，此时我们对数据库进行了分库分表，而分库分表就需要一个全局的唯一ID来满足业务的需求，很显然数据库本身的自增ID是无法满足我们的需求的，所以此时就出现了全局唯一ID这个概念，也就是对应于我们分布式系统中的分布式ID
下面让我们看一下全局唯一ID的特点都是有什么？
全局唯一ID的特点

全局唯一：全局（分库分表之后的全局唯一），不能出现重复的ID，这是最基本的要求
单调递增或者趋势递增：在主键的选择上面我们应该尽量使用有序的主键保证写入性能，保证下一个ID一定大于上一个ID，可以满足我们业务中的大部分特殊需求，比如排序，事务版本号
高性能/高可用：ID生成响应要快，不能有单点故障，否则会成为业务瓶颈
信息安全：如果ID是连续的，容易暴漏业务量，所以个别场景下需要ID无规则
好接入：最好是拿来即用，在系统设计和实现上尽可能的简单
分片支持：最后能够控制分片，比如某一个用户的所有内容都路由到同一个分片
长度适中

上面了解了全局唯一ID的特点之后，下一步就应该知道我们业务中现在常用的全局唯一ID策略都是有哪几种，下面跟随我的脚步带你熟悉常见的全局唯一ID策略
常见全局唯一ID策略数据库自增长序列或字段最常见的方式，利用数据库实现全数据库唯一
优点：

简单，代码实现方便，性能也能接受
生成的ID天然有序，对分页或者需要排序的业务结果很有帮助

缺点：

不同数据库语法或实现不同，数据库迁移的时候需要处理
在单个数据库或读写分离或一主多从多情况下，只有一个主库可以生成ID，有单点故障的风险
在性能达不到要求的情况下比较难以扩展
数据迁移或者系统数据合并比较麻烦
分库分表时会比较麻烦

优化方案：
针对主库单点问题，如果有多个主库，可以让每个主库单起始数字不一样，步长一样，可以是主库的个数。比如主库1生成1，4，7，10，主库2生成2，5，8，11，主库3生成3，6，9，12.这样就可以生成集群中的唯一ID，也可以大大降低ID生成数据库的负载。

基于数据库集群模式

单点数据库性能不够好，容易有宕机风险的话此时就可以改为集群模式，双主模式或者主从模式，也就是两个数据库实例都可以单独生成ID
此时，还会有另一个问题，就是两个数据都生成id，生成的ID重复怎么办，此时就可以使用设置自增步长和起始值
实例1设置起始值1，步长为2
实例2设置起始值2，步长2
这样两个数据库实例生成的ID就为

1,3,5,7,9 2,4,6,8,10

此时，如果双主集群还是无法扛住高并发，就要考虑增加数据库节点，此时的自增步长就要设置为数据库实例的数量
此时还能再优化就是基于数据库的号段模式

基于数据库的号段模式
号段模式是当下分布式ID生成器的主流实现方式之一，号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如（1，1000].代表1000个ID，具体的业务将本号段，生成1-1000的自增id加载到内存，表结构如下

CREATE TABLE id_generator ( id int(10) NOT NULL, max_id bigint(20) NOT NULL COMMENT '当前最大id', step int(20) NOT NULL COMMENT '号段的布长', biz_typeint(20) NOT NULL COMMENT '业务类型', version int(20) NOT NULL COMMENT '版本号', PRIMARY KEY (`id`) )

Bit_type :代表不同的业务类型
max_id：当前最大的可用ID
step：代表号段的长度
version：乐观锁，每次都更新version，保证并发时数据正确性

id Bit_type Max_id Step Version

1 1001 1000 2000 0

等这批号段用完，在向数据库申请新号段，对max_id做一次更新操作，update max_id = max_id+step，update成功则说明号段获取成功，新的号段范围是（max_id，max_id+step]。

update id_generator set max_id = #{max_id+step},version=version+1 where version = #{version} and biz_type="具体业务代码"

由于会有多业务端同时操作，所以采用乐观锁的方式更新，这种分布式id生成方式不强依赖数据库，不会频繁的访问数据库，对数据库的压力小很多
基于Redis模式
原理是使用redis的incr命令实现原子自增
使用redis，要考虑的就是redis的持久化问题，redis有两种持久化方式，AOF和RDB
AOF：会对每条命令进行持久化，但是由于incr，会造成aof文件很大，初始化加载缓慢，不过Redis有aof文件重写优化，命令合并重写aof文件
RDB：redis定时做一个快照，在redis宕机之后，会有ID重复的问题

id	Bit_type	Max_id	Step	Version
1	1001	1000	2000	0

UUID 常见的主键生成方式，可以利用数据库生成或者程序生成
优点：

简单，代码方便
生成ID性能好，基本不会有性能问题
全局唯一，遇见数据迁移的场景，系统数据合并，或者数据库变更的情况下，可以从容应对。

缺点：

没有排序，无法保证递增
UUID一般是字符串存储，查询效率较低
存储占用空间大，如果是海量数据库，还需要考虑存储量的问题
传输数据量大
可读性差

UUID的变种

为了解决UUID的不可读性，可以使用生成有序的UUID

Zookeeper生成ID

zookeeper主要通过其znode版本号来生成序列号，客户端可以使用这个版本号当作分布式id
也可以根据zookeeper的持久顺序节点的特性，多个客户端同时创建一个节点，zk能保证有序的创建，此时创建成功之后返回的path就可以取出来当作分布式id

很少会选用zk来生成分布式id，主要是由于需要依赖zookeeper，如果在竞争较大时，还需要考虑使用分布式锁，因此，在高并发环境中，并不是很理想
Mongdb ObjectId 官网Objectid链接

文章图片

Objectid 很小，可能是唯一的，生成速度快，有序，长度12个字节，包括

一个4字节的时间戳，代表创建时间，以Unix依赖的秒数为单位
没个进程生成一个5字节的随机数，这个随机值对于机器和过程是唯一的
一个3字节的递增计数器，初始化为随机值

雪花算法 github地址

文章图片

描述
snowflake 是Twitter开源的分布式ID生成算法，结果是一个long型的ID，核心思想是：
- 41bit毫秒数
- 10bit机器id（5个bit数据中心，5个bit机器id）
- 12bit毫秒内的流水号（就是说支持每个节点每毫秒产生4096个序列号，1<<12=4096）
- 第一位符号位，永远是0
优点
雪花算法是使用数据中心id和机器id来作为标识，不会产生重复的id，并且也是在本地生成，效率高。
缺点
- 缺点就是有可能发生时钟回拨，因为雪花算法的计算依赖与实践，若是发生系统时间回拨，就会产生重复id情况。id可能不是全局递增，在单机上面是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可完全同步，也许有时候也会出现不是全局递增的情况
- 机器id分配与回收问题：机器id需要每台机器不一样，这样的分配方式需要有方案进行处理，同时也要考虑宕机之后的处理，如果宕机了对应的id分配后的回收问题
- 机器id的上限问题，机器id是固定的bit，那么对应的机器个数是有上限的，在有些业务场景下，需要所有的机器共享同一个业务空间，那么机器的数量是有限制的
解决
- 时钟回拨
  - 直接抛异常，很粗暴，不友好
  - 采用等待跟上次时间的一段范围，这种算是简单解决，可以接受的情况，但是要是等待一段时间之后又发生了时钟回拨，则抛异常，可以接受只能说是不算完全解决
- 机器id分配与回收
  - 采用zookeeper的顺序节点分配，解决分配。回收采用zookeeper临时节点回收，但是临时节点不可靠，存在无故消失问题，因为也不是很可靠
  - 采用中数据库中插入数据作为节点值，解决了分配，但是没有解决回收
- 机器id上限
  如果采用雪花算法这也是不可避免的。不过这种场景也只有在大量的业务机器在一个共享的场景才会出现，这种情况可以采用客户端双buffer+db的这种非雪花算法也并不是不行

百度UidGenerator github地址
uid-generator是基于snowflake算法实现的，与snowflake算法不同的是uid-generator支持自定义时间戳，工作机器id和序列号等各部分的位数，而且uid-generator采用用户自定义workid的生成策略
uid-generator需要与数据库配合使用，需要新增一个worker_node表，当应用启动时会向数据库表中插入一条数据，插入成功后返回的自增id就是该机器的workid，数据有host，port组成

组成
- sign(1bit)
  固定1bit符号标识，即生成的UID为正数。
- delta seconds (28 bits)
  当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年
- worker id (22 bits)
  机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。
- sequence (13 bits)
  每秒下的并发序列，13 bits可支持每秒8192个并发
workId，占用了22个bit位，时间占用了28个bit位，序列化占用了13个bit位，需要注意的是，和原始的snowflake不太一样，时间的单位是秒，而不是毫秒，workId也不一样，而且同一应用每次重启就会消费一个workId。

美团Leaf github地址
【分布式|全网最全的分布式ID生成方案解析】Leaf支持两种方式，号段方式和snowflake模式，可以同时开启两种模式，也可以指定开启哪种模式，默认两种关闭
滴滴Tinyid github
Tinyid是用Java开发的一款分布式id生成系统，基于数据库号段算法实现，关于这个算法可以参考美团leaf或者tinyid原理介绍。Tinyid扩展了leaf-segment算法，支持了多db(master)，同时提供了java-client(sdk)使id生成本地化，获得了更好的性能与可用性。Tinyid在滴滴客服部门使用，均通过tinyid-client方式接入，每天生成亿级别的id。
特点