Distributed ID Generator

2019-01-27

Table of content:

About
发号器需要哪些特性
方案
常见问题
- 基于时间戳的方案的时间戳同步以及时钟回拨等问题怎么处理（todo）
Reference 和推荐阅读
关于头图

About

这篇文章是对业内 ID 生成方案的一些调研和思考, 后续会增加一些实现。

发号器需要哪些特性

特性	说明
唯一性	这是发号器的基础要求
高并发	能够在很多时间内生成大量的唯一 id
高可用	不能一台机器 down 了，整个发号器都不可用
按照时间排序	构建索引，按照范围查询
可反解	通过反解，能够快速定位问题
格式优雅	通常对外的 id 要求足够短
不容易被猜出	比如自增 id 就是顺着 + 1，这样很容易被猜到

方案

UUID

UUID 算法，生成的 ObjectId 占 12 个字节，由以下几个部分组成，

4 个字节表示的 Unix timestamp,
3 个字节表示的机器的 ID
2 个字节表示的进程 ID
3 个字节表示的计数器

UUID 是一类算法的统称，具体有不同的实现。UUID 的有点是每台机器可以独立产生 ID，理论上保证不会重复，所以天然是分布式的，缺点是生成的 ID 太长，不仅占用内存，而且索引查询效率低。UUID 是由 128 位二进制组成，一般转换成十六进制，然后用 String 表示。

生成策略包括：

随机生成
通过当前时间，随机数，和本地 Mac 地址来计算出来
基于名字的 UUID，通过计算名字和名字空间的 MD5 来计算 UUID

优点：本地生成，生成简单，性能好，没有高可用风险
缺点：长度过长，存储冗余，且无序不可读，查询效率低

数据库自增 ID

使用数据库的 id 自增策略，如 MySQL 的 auto_increment。并且可以使用两台数据库分别设置不同步长，生成不重复 ID 的策略来实现高可用, 一个例子:

Server1:
auto-increment-increment = 2
auto-increment-offset = 1

Server2:
auto-increment-increment = 2
auto-increment-offset = 2

优点：数据库生成的 ID 绝对有序，高可用实现方式简单
缺点：

需要独立部署数据库实例，成本高，有性能瓶颈
分库分表会带来问题，需要进行改造
不是严格实现的全局递增
简单递增容易被其他人猜测利用

Flickr 使用了类似的方案, http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

Redis

Redis 是单线程的，所以也可以用生成全局唯一的 ID。可以用 Redis 的原子操作 INCR 和 INCRBY 来实现。
使用 Redis 集群来获取更高的吞吐量。假如一个集群中有 5 台 Redis。可以初始化每台 Redis 的值分别是 1,2,3,4,5，然后步长都是 5。各个 Redis 生成的 ID 为：

A：1,6,11,16,21
B：2,7,12,17,22
C：3,8,13,18,23
D：4,9,14,19,24
E：5,10,15,20,25

优点：