数据库分库分表实现分布式ID的解决方案
目前的方案:
- UUID
- 数据库自增
- 号段模式
- Redis实现
- 雪花算法（Snowflake）
- 百度Uidgenerator
- 美团Leaf
- 滴滴TinyID
分布式 ID 的要求:
- 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
- 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
- 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
- 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。
UUID:
通用唯一识别码, 标准型包含32个16进制数字, 大小一共 128bit, 有效保证唯一性
- 优点: 本地生成计算生成, 效率极高, 有效保证唯一性
- 缺点: 无序, 不满足趋势递增和单调递增, 写入效率极低, 并且基于 mac 地址的 UUID 还容易导致信息泄露
数据库自增:
简单易懂一张表:
| 数据库 | DB_1 | DB_2 | DB_3 |
|---|---|---|---|
| 主键ID /step=3 | 0,0+3,0+6,0+9,... | 1,1+3,1+6,1+9,... | 2,2+3,2+6,2+9,... |
-
优点:
- 生成效率极高, 数据库自己实现;
- 写入效率高, 自增 ID 的写入是追加写入;
-
缺点:
- 数据库也无法做拓展, 一旦目前的数据库不够用就只能全部数据迁移
- ID 只有趋势上是递增的, 但是实际上可能会存在后进入的数据的 ID 小于以前进入的数据的 ID ( 原因是每个数据库的 ID 各自独立自增的没有任何联系 )
号段模式:
实现思路是会从数据库根据数据获取一个号段范围，比如[1,1000]，生成1到1000的自增ID加载到内存中, 等 ID 都用了, 再去数据库获取, 然后更改最大值, 这种模式依赖于数据库，但是区别于数据库主键自增的模式。假设1000为一个号段1000，2000，3000，每一次 I/O 可以获得1000个 ID，性能显著提高。段号用完了再去取, 降低数据库压力。
Redis 辅助实现
基于 Redis 的自增原子指令 INCR 和 INCRBY , 并且由于 Redis 的单线程特点, 保证了 ID 的唯一性和自增有序性
- 优点: Redis 新能好, 效率高
- 缺点: 很依赖 Redis 性能, 在高并发场景下就需要集群，不过集群后，又要和传统数据库一样，设置分段和步长
雪花算法:
由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义, 通常为
| 符号位 | 时间戳(ms级) | 工作机器id | 序列号 |
|---|---|---|---|
| 1bit / 默认 0 | 41bit | 10bit | 12bit |
ID 长度64位, java 中用 Long 储存, 所以有一个符号位, 这样也可以保证 long 型的 ID 也是自增的
时间错精切到毫秒级别, 41bit可以表示69年数据, 暂时够用.
- 优点：
- ID是趋势递增，不依赖数据库等第三方，生成ID的效率非常高，稳定性好;
- 可以根据自身业务特性分配bit位，比较灵活
- 缺点:
- 强依赖服务器上的机器时钟, 如果时钟回拨, 则会导致ID重复, 服务不可用
企业级方案:
如无必要, 勿增实体
1. 百度 Uidgenerator
来自 Github 介绍:
UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
2. 美团 Leaf
有两种方案: Leaf-segment 和 Leaf-snowflake
Leaf-segment 方案:
优化:
- 原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用 proxy server 批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。
- 各个业务不同的发号需求用 biz_tag 字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。
- 双 Buffer 无阻塞优化, 不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。
Leaf-snowflake 方案:
优化:
- 弱依赖 ZooKeeper 实现 WorkID 的自动注册和分配, 每个节点也会自己缓存自己的 WorkId 避免 ZooKeeper 挂掉导致服务挂掉
- 增加了时钟校验的逻辑, 防止机器时钟回拨带来的问题
3. 滴滴TinyID
Segment 方法实现分布式 ID, 但是做了以下优化:
- 双 buffer 缓存, 避免阻塞
- 支持多 db 集群, 每次获取段号都随机从一个存活的数据库上拿, 这样就可以提高容灾性能, 只要有一个 db 没有挂就可以继续用
| id | biz_type | max_id | step | delta | remainder | version |
|---|---|---|---|---|---|---|
| 1 | 1000 | 2000 | 1000 | 2 | 0 | 0 |
delta代表id每次的增量，remainder代表余数，例如可以将A，B都delta都设置2，remainder分别设置为0，1则，A的号段只生成偶数号段，B是奇数号段。 通过delta和remainder两个字段我们可以根据使用方的需求灵活设计db个数，同时也可以为使用方提供只生产类似奇数的id序列。
- 增加了一个 client 用于本地缓存段号, 不用每次需要拿到 ID 都给服务器发送一个 http 请求, 提高效率
