分布式ID生成方案
一、问题背景
由于MySQL的单表数据量超过了千万级别，需要根据日期对数据库进行水平分表，分表后需要保证每个分表Id的全局唯一性，原来单表使用自增保证Id的有序性和唯一性，分表后需要生成全局唯一的Id。
所以接下来讨论一下分布式Id的生成方案，以及各种方案的优缺点等。
二、分布式ID生成方案
2.1 UUID
A universally unique identifier (UUID) is a 128-bit label used for information in computer systems. The term globally unique identifier (GUID) is also used
通用唯一识别码（英语：Universally Unique Identifier，缩写：UUID）是用于计算机体系中以识别信息的一个128位标识符。
根据标准方法生成，不依赖中央机构的注册和分配，UUID具有唯一性，这与其他大多数编号方案不同。重复UUID码概率接近零，可以忽略不计。通用唯一识别码-维基百科
2.1.1 UUID定义
UUID是由一个16进制下的32位数所构成，故UUID理论上的总数为16的32次方=2的128次方，约等于3.4 x 10的38次方。也就是说若每纳秒（ns）产生1万亿个UUID，要花100亿年才会将所有UUID用完。
UUID的标准型式包含32个16进制数字，以连字号分为五段，形式为 8-4-4-4-12 的32个字符。示例：550e8400-e29b-41d4-a716-446655440000
优点
- 生成容易、速度快
- ID唯一（几乎不会产生重复ID，部分实现依赖于MAC硬件地址）
- 无需中心化服务器
- 不会泄露商业机密
缺点
- 可读性差
- 占用空间太多（16个字节）
- 作为数据库主键时，影响数据库性能
为什么UUID不建议作为MySQL数据库表的主键？
MySQL数据库InnoDB存储引擎使用了聚簇索引，底层使用B+树来存储数据，B+树的非叶子节点存储索引数据，叶子节点存储具体的行数据，每个节点的大小默认为
16KB。
其中叶子节点内部的记录根据主键大小进行排序，叶子节点之间使用双向链表进行连接。如果使用UUID作为主键，由于UUID是无序的，在进行插入操作的时候，存储引擎需要维护主键索引的顺序,一条新的记录插入进来，可能会被插入到之前已经存放满的叶子结点内，此时将会产生页分裂，带来性能损耗。
根据MySQL InnoDb存储引擎的聚簇索引的特性，建议主键选取为递增有序的字段。
2.2 基于数据库自增ID
通过关系型数据库自增主键产生唯一的ID，现在流行的商业数据库都支持自增主键的特性，比如MySQL等。
优点
- 容易产生
- ID单调递增
- 存储很小（int类型占用4个字节，bigint类型占用8个字节）
缺点
- 依赖于数据库、而且需要处理单点问题，而且单点有性能瓶颈问题
- 每次生成一个ID都需要访问一次数据库
关于数据库单点风险的问题可以通过数据库集群模式去优化，部署多个数据库实例，每个实例均可产生Id，每个数据库实例设置不通过的起始值和自增步长。
这种方式虽可以解决点单点问题，但是不利于后续的扩容。
2.3 基于数据库的分段发号方案
号段方案是当下分布式ID生成器的主流实现方式之一，分段方案使用数据库表来存储最大ID，每次获取一个范围段的ID，获取后更新数据库表，并将这一段ID加载到内从中，在内存中进行分配，内存中的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_type` int(20) NOT NULL COMMENT '业务类型',
`version` int(20) NOT NULL COMMENT '版本号',
PRIMARY KEY (`id`)
)- max_id ：当前最大的可用id
- step ：代表号段的长度
- biz_type ：代表不同业务类型
- version ：是一个乐观锁，每次都更新version，保证并发时数据的正确性
优点
- 相对于数据库自增的Id，有效减轻了数据库压力
缺点
- 依赖于数据库
- 每个节点产生的Id号段内递增
2.4 基于Redis的原子性递增
INCR key
Available since 1.0.0.
Time complexity: O(1)
Increments the number stored at key by one. If the key does not exist, it is set to 0 before performing the operation. An error is returned if the key contains a value of the wrong type or contains a string that can not be represented as integer. This operation is limited to 64 bit signed integers.
Note: this is a string operation because Redis does not have a dedicated integer type. The string stored at the key is interpreted as a base-10 64 bit signed integer to execute the operation.
Redis stores integers in their integer representation, so for string values that actually hold an integer, there is no overhead for storing the string representation of the integer.
Redis提供了incr指令，该指令可以对key中存储的值进行+1操作（Redis不支持Integer类型，key中存储的string值将会被转为一个64位的有符号整数进行操作）。
优点
- 实现简单
- 生成id效率高
缺点
- 强依赖于数据库
- 需要考虑Redis持久化的问题
2.5 基于雪花算法（Snowflake）
snowflake是Twitter开源的分布式ID生成算法，生成的结果是一个Long类型的ID。
snowflake使用64bit来生成ID，由高位到低位成部分如下：
- 1bit作为保留位，没有使用，永远是0
- 41bit作为时间戳，表示从1970-01-01年以来的毫秒数
- 10bit作为机器ID（5bit是数据中心，5bit是机器ID）
- 12bit作为毫秒内的流水号，每毫秒可以生成4096个ID
雪花算法每秒可以生成400万+的ID，由于高位41位使用了时间戳，所以各节点生成的ID都是大致有序的。
优点
- 实现简单
- 不依赖其它组件
- 生成ID速度快
缺点
- 生成的Id是趋势递增的（绝对递增会导致业务信息泄露）
- 依赖机器时间，需要处理时钟回拨的问题
2.6 百度(UidGenerator)
UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
依赖版本：Java8及以上版本, MySQL(内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖）
| sign | delta seconds | worker node id | sequence |
|---|---|---|---|
| 1bit | 28bits | 22bits | 13bits |
Snowflake算法描述：指定机器 & 同一时刻 & 某一并发序列，是唯一的。据此可生成一个64 bits的唯一ID（long）。默认采用上图字节分配方式：
- 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个并发。
以上参数均可通过Spring进行自定义。
优点
- 可以根据业务调整
delta seconds、worker id、sequence的长度
缺点
- 依赖于数据库表
2.7 美团(Leaf)
Leaf这个名字是来自德国哲学家、数学家莱布尼茨的一句话： >There are no two identical leaves in the world > “世界上没有两片相同的树叶”
Leaf-segment数据库方案
第一种Leaf-segment方案，在使用数据库的方案上，做了如下改变： - 原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。
Leaf-snowflake方案
Leaf-segment方案可以生成趋势递增的ID，同时ID号是可计算的，不适用于订单ID生成场景，比如竞对在两天中午12点分别下单，通过订单id号相减就能大致计算出公司一天的订单量，这个是不能忍受的。面对这一问题，我们提供了 Leaf-snowflake方案。
Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装ID号。对于workerID的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf服务规模较大，动手配置成本太高。所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。Leaf-snowflake是按照下面几个步骤启动的：
- 启动Leaf-snowflake服务，连接Zookeeper，在leaf_forever父节点下检查自己是否已经注册过（是否有该顺序子节点）。
- 如果有注册过直接取回自己的workerID（zk顺序节点生成的int类型ID号），启动服务。
- 如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的workerID号，启动服务。
三、总结
上面介绍了6种分布式ID生成方案：
- UUID
- 基于数据库自增ID
- 基于数据库的分段发号方案
- 基于Redis的原子性递增
- 基于雪花算法（Snowflake）
- 百度(UidGenerator)
- 美团(Leaf)
以上分布式ID生成方案又可以大致分为三类：
- UUID生成随机字符串，基本可以保证全局唯一，这类方法生成的ID占用空间较大（16字节）,而且生成的ID无序。
- 基于数据库生成的单调递增的ID，需要解决单点及性能问题，而且可能会导致业务数据泄露。
比如：通过订单ID推测出业务系统每天的订单量 - snowflake算法类，对ID进行分段，分段表示时间、机器节点、序列号等，此类算法中由于包含时间段，所以需要考虑时钟回拨的问题。
参考文章