分布式唯一ID

分布式系统全局唯一的 id 是所有系统都会遇到的场景，往往会被用在搜索，存储方面，用于作为唯一的标识或者排序，比如全局唯一的订单号，优惠券的券码等，如果出现两个相同的订单号，对于用户无疑将是一个巨大的bug。

在单体的系统中，生成唯一的 id 没有什么挑战，因为只有一台机器一个应用，直接使用单例加上一个原子操作自增即可。而在分布式系统中，不同的应用，不同的机房，不同的机器，要想生成的 ID 都是唯一的，确实需要下点功夫。

一句话总结：

分布式唯一ID是为了给数据进行唯一标识。

分布式唯一ID的特征

分布式唯一ID的核心是唯一性，其他的都是附加属性，一般来说，一个优秀的全局唯一ID方案有以下的特点，仅供参考：

  • 全局唯一：不可以重复，核心特点！
  • 大致有序或者单调递增：自增的特性有利于搜索，排序，或者范围查询等
  • 高性能：生成ID响应要快，延迟低
  • 高可用：要是只能单机，挂了，全公司依赖全局唯一ID的服务，全部都不可用了，所以生成ID的服务必须高可用
  • 方便使用：对接入者友好，能封装到开箱即用最好
  • 信息安全：有些场景，如果连续，那么很容易被猜到，攻击也是有可能的，这得取舍。

雪花算法

snowflake 是 Twitter 开源的分布式ID生成算法，结果是一个long型的ID。其核心思想是：

使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。

雪花算法是 64 位 的二进制，一共包含了四部分：

  • 1位是符号位，也就是最高位，始终是0，没有任何意义，因为要是唯一计算机二进制补码中就是负数，0才是正数。

  • 41位是时间戳，具体到毫秒，41位的二进制可以使用69年，因为时间理论上永恒递增，所以根据这个排序是可以的。

  • 10位是机器标识，可以全部用作机器ID，也可以用来标识机房ID + 机器ID，10位最多可以表示1024台机器。

  • 12位是计数序列号，同一台机器上同一时间，理论上还可以同时生成不同的ID，12位的序列号能够区分出4096个ID。

snowflake

SnowFlake 算法的缺点或者限制：

1、在Snowflake算法中，每个节点的机器ID和数据中心ID都是硬编码在代码中的，而且这些ID是全局唯一的。当某个节点出现故障或者需要扩容时，就需要更改其对应的机器ID或数据中心ID，但是这个过程比较麻烦，需要重新编译代码，重新部署系统。还有就是，如果某个节点的机器ID或数据中心ID被设置成了已经被分配的ID，那么就会出现重复的ID，这样会导致系统的错误和异常。

2、Snowflake算法中，需要使用zookeeper来协调各个节点的ID生成，但是ZK的部署其实是有挺大的成本的，并且zookeeper本身也可能成为系统的瓶颈。

3、依赖于系统时间的一致性，如果系统时间被回拨，或者不一致，可能会造成 ID 重复。

时间回拨问题

在获取时间的时候，可能会出现时间回拨的问题，什么是时间回拨问题呢？就是服务器上的时间突然倒退到之前的时间。

  1. 人为原因，把系统环境的时间改了。
  2. 有时候不同的机器上需要同步时间，可能不同机器之间存在误差，那么可能会出现时间回拨问题。

解决方案

  1. 回拨时间小的时候，不生成 ID，循环等待到时间点到达。
  2. 上面的方案只适合时钟回拨较小的，如果间隔过大，阻塞等待，肯定是不可取的，因此要么超过一定大小的回拨直接报错，拒绝服务，或者有一种方案是利用拓展位，回拨之后在拓展位上加1就可以了，这样ID依然可以保持唯一。但是这个要求我们提前预留出位数，要么从机器id中，要么从序列号中，腾出一定的位，在时间回拨的时候，这个位置 +1。

百度的UidGenerator

UidGenerator 是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。

UidGenerator 通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

DefaultUidGenerator

delta seconds

这个值是指当前时间与epoch时间的时间差，且单位为秒。epoch时间就是指集成 UidGenerator 生成分布式 ID 服务第一次上线的时间，可配置，也一定要根据你的上线时间进行配置，因为默认的epoch时间可是2016-09-20，不配置的话，会浪费好几年的可用时间。

worker id

接下来说一下 UidGenerator 是如何被worker id赋值的，搭建 UidGenerator 的话，需要创建一个表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
DROP DATABASE IF EXISTS `xxxx`;
CREATE DATABASE `xxxx` ;
use `xxxx`;
DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE
(
ID BIGINT NOT NULL AUTO_INCREMENT COMMENT 'auto increment id',
HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',
PORT VARCHAR(64) NOT NULL COMMENT 'port',
TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',
MODIFIED TIMESTAMP NOT NULL COMMENT 'modified time',
CREATED TIMESTAMP NOT NULL COMMENT 'created time',
PRIMARY KEY(ID)
)
 COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;

UidGenerator 会在集成用它生成分布式 ID 的实例启动的时候，往这个表中插入一行数据，得到的 ID 值就是准备赋给workerId的值。由于workerId默认 22 位，那么，集成 UidGenerator 生成分布式 ID 的所有实例重启次数是不允许超过 4194303 次（即2^22-1），否则会抛出异常。

这段逻辑的核心代码来自 DisposableWorkerIdAssigner.java中，当然，你也可以实现WorkerIdAssigner.java接口，自定义生成workerId。

sequence

核心代码如下，几个实现的关键点：

  • synchronized保证线程安全
  • 如果时间有任何的回拨，那么直接抛出异常
  • 如果当前时间和上一次是同一秒时间，那么sequence自增。如果同一秒内自增值超过2^13-1，那么就会自旋等待下一秒（getNextSecond）
  • 如果是新的一秒，那么sequence重新从 0 开始

CachedUidGenerator

RingBuffer环形数组，数组每个元素成为一个slot。RingBuffer容量，默认为Snowflake算法中sequence(最后12位序列值)最大值，且为2^N。可通过boostPower配置进行扩容，以提高RingBuffer 读写吞吐量。

Tail指针、Cursor指针用于环形数组上读写slot：

  • Tail指针
    表示Producer生产的最大序号(此序号从0开始，持续递增)。Tail不能超过Cursor，即生产者不能覆盖未消费的slot。当Tail已赶上curosr，此时可通过rejectedPutBufferHandler指定PutRejectPolicy
  • Cursor指针
    表示Consumer消费到的最小序号(序号序列与Producer序列相同)。Cursor不能超过Tail，即不能消费未生产的slot。当Cursor已赶上tail，此时可通过rejectedTakeBufferHandler指定TakeRejectPolicy

ringbuffer

CachedUidGenerator采用了双RingBuffer，Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)

由于数组元素在内存中是连续分配的，可最大程度利用CPU cache以提升性能。但同时会带来伪共享**伪共享**（False Sharing）指的是当多个线程在处理不同数据时，这些数据恰好被存储在同一个CPU缓存行（通常是64字节）中，导致不必要的缓存一致性流量，进而降低性能。 举个简单的例子，假设有两个线程分别处理两个不同的变量，这两个变量刚好存储在同一个缓存行里。虽然线程操作的是不同的变量，但由于它们共享同一个缓存行，任何一个线程对其中一个变量的修改都会导致另一个线程的缓存无效，迫使它重新从主内存读取数据。FalseSharing问题，为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine 补齐方式。人为增加变量之间的距离，避免它们落在同一个缓存行中，从而减少伪共享的影响。

ringbuffer

RingBuffer填充时机

  • 初始化预填充
    RingBuffer初始化时，预先填充满整个RingBuffer.
  • 即时填充
    Take消费时，即时检查剩余可用slot量(tail - cursor)，如小于设定阈值，则补全空闲slots。阈值可通过paddingFactor来进行配置
  • 周期填充
    通过Schedule线程，定时补全空闲slots。可通过scheduleInterval配置，以应用定时填充功能，并指定Schedule时间间隔

Leaf——美团点评分布式ID生成系统

Leaf这个名字是来自德国哲学家、数学家莱布尼茨的一句话： >There are no two identical leaves in the world > “世界上没有两片相同的树叶”

Leaf-segment数据库方案

第一种Leaf-segment方案，在使用数据库的方案上，做了如下改变：

  • 原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。
  • 各个业务不同的发号需求用biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。

数据库表设计如下：

1
2
3
4
5
6
7
8
9
+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

重要字段说明：biz_tag用来区分业务，max_id表示该biz_tag目前所被分配的ID号段的最大值，step表示每次分配的号段长度。原来获取ID每次都需要写数据库，现在只需要把step设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step，大致架构如下图所示：

img

test_tag在第一台Leaf机器上是1~1000的号段，当这个号段用完时，会去加载另一个长度为step=1000的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是3001~4000。同时数据库对应的biz_tag这条数据的max_id会从3000被更新成4000，更新号段的SQL语句如下：

1
2
3
4
Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

这种模式有以下优缺点：

优点：

  • Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
  • ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。
  • 容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。
  • 可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。

缺点：

  • ID号码不够随机，能够泄露发号数量的信息，不太安全。
  • TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。
  • DB宕机会造成整个系统不可用。

双buffer优化

对于第二个缺点，Leaf-segment做了一些优化，简单的说就是：

Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。

为此，我们希望DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。详细实现如下图所示：

img

采用双buffer的方式，Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。

  • 每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。
  • 每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

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是按照下面几个步骤启动的：

  1. 启动Leaf-snowflake服务，连接Zookeeper，在leaf_forever父节点下检查自己是否已经注册过（是否有该顺序子节点）。
  2. 如果有注册过直接取回自己的workerID（zk顺序节点生成的int类型ID号），启动服务。
  3. 如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的workerID号，启动服务。

img

解决时钟问题

img

参见上图整个启动流程图，服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点：

  1. 若写过，则用自身系统时间与leaf_forever/${self}节点记录时间做比较，若小于leaf_forever/${self}时间则认为机器时间发生了大步长回拨，服务启动失败并报警。
  2. 若未写过，证明是新服务节点，直接创建持久节点leaf_forever/${self}并写入自身系统时间，接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确，具体做法是取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize。
  3. 若abs( 系统时间-sum(time)/nodeSize ) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点leaf_temporary/${self} 维持租约。
  4. 否则认为本机系统时间发生大步长偏移，启动失败并报警。
  5. 每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}。

由于强依赖时钟，对时间的要求比较敏感，在机器工作时NTP同步也会造成秒级别的回退，建议可以直接关闭NTP同步。要么在时钟回拨的时候直接不提供服务直接返回ERROR_CODE，等时钟追上即可。或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//发生了回拨，此刻时间小于上次发号时间
if (timestamp < lastTimestamp) {
           long offset = lastTimestamp - timestamp;
           if (offset <= 5) {
               try {
               	//时间偏差大小小于5ms，则等待两倍时间
                   wait(offset << 1);//wait
                   timestamp = timeGen();
                   if (timestamp < lastTimestamp) {
                      //还是小于，抛异常并上报
                       throwClockBackwardsEx(timestamp);
                     }    
               } catch (InterruptedException e) {  
                  throw  e;
               }
           } else {
               //throw
               throwClockBackwardsEx(timestamp);
           }
       }
//分配ID

参考资料

引用站外地址
twitter开源的雪花算法
https://github.com/twitter/snowflake
引用站外地址
百度开源 UidGenerator
https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
引用站外地址
Leaf—美团点评分布式ID生成系统
https://tech.meituan.com/2017/04/21/mt-leaf.html