分布式 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 号), 之后就可以独立工作了，做到了去中心化