分布式ID生成方案
内容来自
问题描述
在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现.
但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群, 在这个集群中插入数据), 这个问题会变得复杂, 所生成的全局的 unique ID 要满足以下需求:
- 保证生成的 ID 全局唯一
- 今后数据在多个 Shards 之间迁移不会受到 ID 生成方式的限制
- 生成的 ID 中最好能带上时间信息, 例如 ID 的前 k 位是 Timestamp, 这样能够直接通过对 ID 的前 k 位的排序来对数据按时间排序
- 生成的 ID 最好不大于 64 bits
- 生成 ID 的速度有要求. 例如, 在一个高吞吐量的场景中, 需要每秒生成几万个 ID (Twitter 最新的峰值到达了143,199 Tweets/s, 也就是 10万+/秒)
- 整个服务最好没有单点
时间戳
用时间做唯一id，这个在并发比较高或者分布式环境中基本不可行，统一时间生成的id是重复的，不满足全局唯一
利用数据库自增
依然利用数据库产生自增id，保证唯一性。但是要注意的是没有分库分表，可以单独使用固定数量的数据库表专门来产生自增ID，与业务无关，后续不再分表。
好处是实现简单，容易理解。不足在于id产生速率受数据库性能以及连接数据库的网络影响
利用Redis原子操作
- 不依赖于数据库，灵活方便，且性能优于数据库。
- 数字ID天然排序，对分页或者需要排序的结果很有帮助
注意:
- 在Redis集群情况下,需要设置不同的增长步长
- 生成的ID超过自增增长的话，可以采用前缀+自增+并且设置有效期
利用UUID/GUID
基本概念
UUID是指在一台机器上生成的数字，它保证对在同一时空中的所有机器都是唯一的。
UUID组成部分:当前日期和时间+时钟序列+随机数+全局唯一的IEEE机器识别号
优缺点
优点:
- 简单，代码方便
- 生成ID性能非常好，基本不会有性能问题
- 全球唯一，在遇见数据迁移，系统数据合并，或者数据库变更等情况下，可以从容应对
缺点:
- 没有排序，无法保证趋势递增
- UUID往往是使用字符串存储，查询的效率比较低
- 存储空间比较大，如果是海量数据库，就需要考虑存储量的问题。
- 太长，128bit，不适合做数据库主键
Twitter Snowflake
snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。
其核心思想是：高位随机+毫秒数+机器码（数据中心+机器id）+10位的流水号码
ID 生成过程
- 10 bits 的机器号, 在 ID 分配 Worker 启动的时候, 从一个 Zookeeper 集群获取 (保证所有的 Worker 不会有重复的机器号)
- 41 bits 的 Timestamp: 每次要生成一个新 ID 的时候, 都会获取一下当前的 Timestamp, 然后分两种情况生成 sequence number:
- 如果当前的 Timestamp 和前一个已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一个 ID 的 sequence number + 1 作为新的 sequence number (12 bits); 如果本毫秒内的所有 ID 用完, 等到下一毫秒继续 (这个等待过程中, 不能分配出新的 ID)
- 如果当前的 Timestamp 比前一个 ID 的 Timestamp 大, 随机生成一个初始 sequence number (12 bits) 作为本毫秒内的第一个 sequence number 整个过程中, 只是在 Worker 启动的时候会对外部有依赖 (需要从 Zookeeper 获取 Worker 号), 之后就可以独立工作了, 做到了去中心化