自研RPC框架之分布式ID设计

自研RPC框架之分布式ID设计

1.改良的雪花算法

借鉴Seata的分布式ID生成设计方案，采用改良的雪花算法。

标准版雪花算法的几个缺点：

  1. 时钟敏感。因为ID生成总是和当前操作系统的时间戳绑定的(利用了时间的单调递增性)，因此若操作系统的时钟出现回拨，生成的ID就会重复(一般而言不会人为地去回拨时钟，但服务器会有偶发的”时钟漂移”现象)。对于此问题，Seata的解决策略是记录上一次的时间戳，若发现当前时间戳小于记录值(意味着出现了时钟回拨)，则拒绝服务，等待时间戳追上记录值。但这也意味着这段时间内该TC将处于不可用状态。
  2. 突发性能有上限。标准版雪花算法宣称的QPS很大，约400w/s，但严格来说这算耍了个文字游戏~ 因为算法的时间戳单位是毫秒，而分配给序列号的位长度为12，即每毫秒4096个序列空间。所以更准确的描述应该是4096/ms。400w/s与4096/ms的区别在于前者不要求每一毫秒的并发都必须低于4096 (也许有些毫秒会高于4096，有些则低于)。Seata亦遵循此限制，若当前时间戳的序列空间已耗尽，会自旋等待下一个时间戳。

在较新的版本上，该生成器针对原算法进行了一定的优化改良，很好地解决了上述的2个问题。改进的核心思想是解除与操作系统时间戳的时刻绑定，生成器只在初始化时获取了系统当前的时间戳，作为初始时间戳，但之后就不再与系统时间戳保持同步了。它之后的递增，只由序列号的递增来驱动。比如序列号当前值是4095，下一个请求进来，序列号+1溢出12位空间，序列号重新归零，而溢出的进位则加到时间戳上，从而让时间戳+1。至此，时间戳和序列号实际可视为一个整体了。实际上我们也是这样做的，为了方便这种溢出进位，我们调整了64位ID的位分配策略，由原版的：

原版位分配策略

改成(即时间戳和节点ID换个位置)：

改进版位分配策略

这样时间戳和序列号在内存上是连在一块的，在实现上就很容易用一个AtomicLong来同时保存它俩：

1
2
3
4
5
6
7
/**
 * timestamp and sequence mix in one Long
 * highest 11 bit: not used
 * middle  41 bit: timestamp
 * lowest  12 bit: sequence
 */
private AtomicLong timestampAndSequence;

最高11位可以在初始化时就确定好，之后不再变化：

1
2
3
4
5
6
7
8
/**
 * business meaning: machine ID (0 ~ 1023)
 * actual layout in memory:
 * highest 1 bit: 0
 * middle 10 bit: workerId
 * lowest 53 bit: all 0
 */
private long workerId;

那么在生产ID时就很简单了：

1
2
3
4
5
6
7
8
public long nextId() {
   // 获得递增后的时间戳和序列号
   long next = timestampAndSequence.incrementAndGet();
   // 截取低53位
   long timestampWithSequence = next & timestampAndSequenceMask;
   // 跟先前保存好的高11位进行一个或的位运算
   return workerId | timestampWithSequence;
}

至此，我们可以发现：

  1. 生成器不再有4096/ms的突发性能限制了。倘若某个时间戳的序列号空间耗尽，它会直接推进到下一个时间戳，”借用”下一个时间戳的序列号空间(不必担心这种"超前消费"会造成严重后果，下面会阐述理由)。
  2. 生成器弱依赖于操作系统时钟。在运行期间，生成器不受时钟回拨的影响(无论是人为回拨还是机器的时钟漂移)，因为生成器仅在启动时获取了一遍系统时钟，之后两者不再保持同步。唯一可能产生重复ID的只有在重启时的大幅度时钟回拨(人为刻意回拨或者修改操作系统时区，如北京时间改为伦敦时间~ 机器时钟漂移基本是毫秒级的，不会有这么大的幅度)。
  3. 持续不断的”超前消费”会不会使得生成器内的时间戳大大超前于系统的时间戳，从而在重启时造成ID重复？理论上如此，但实际几乎不可能。要达到这种效果，意味该生成器接收的QPS得持续稳定在400w/s之上~ 说实话，TC也扛不住这么高的流量，所以说呢，天塌下来有个子高的先扛着，瓶颈一定不在生成器这里。

此外，我们还调整了下节点ID的生成策略。原版在用户未手动指定节点ID时，会截取本地IPv4地址的低10位作为节点ID。在实践生产中，发现有零散的节点ID重复的现象(多为采用k8s部署的用户)。例如这样的IP就会重复：

  • 192.168.4.10
  • 192.168.8.10

即只要IP的第4个字节和第3个字节的低2位一样就会重复。新版的策略改为优先从本机网卡的MAC地址截取低10位，若本机未配置有效的网卡，则在[0, 1023]中随机挑一个作为节点ID。这样调整后似乎没有新版的用户再报同样的问题了(当然，有待时间的检验，不管怎样，不会比IP截取策略更糟糕)。

有细心的同学提出了一个问题：新版算法在单节点内部确实是单调递增的，但是在多实例部署时，它就不再是全局单调递增了啊！因为显而易见，节点ID排在高位，那么节点ID大的，生成的ID一定大于节点ID小的，不管时间上谁先谁后。而原版算法，时间戳在高位，并且始终追随系统时钟，可以保证早生成的ID小于晚生成的ID，只有当2个节点恰好在同一时间戳生成ID时，2个ID的大小才由节点ID决定。这样看来，新版算法是不是错的？

这是一个很好的问题！能提出这个问题的同学，说明已经深入思考了标准版雪花算法和新版雪花算法的本质区别，这点值得鼓励！在这里，我们先说结论：新版算法的确不具备全局的单调递增性，但这不影响我们的初衷(减少数据库的页分裂)。这个结论看起来有点违反直觉，但可以被证明。

在证明之前，我们先简单回顾一下数据库关于页分裂的知识。以经典的mysql innodb为例，innodb使用B+树索引，其中，主键索引的叶子节点还保存了数据行的完整记录，叶子节点之间以双向链表的形式串联起来。叶子节点的物理存储形式为数据页，一个数据页内最多可以存储N条行记录(N与行的大小成反比)。如图所示：

数据页

B+树的特性要求，左边的节点应小于右边的节点。如果此时要插入一条ID为25的记录，会怎样呢(假设每个数据页只够存放4条记录)？答案是会引起页分裂，如图：

页分裂

页分裂是IO不友好的，需要新建数据页，拷贝转移旧数据页的部分记录等，我们应尽量避免。

理想的情况下，主键ID最好是顺序递增的(例如把主键设置为auto_increment)，这样就只会在当前数据页放满了的时候，才需要新建下一页，双向链表永远是顺序尾部增长的，不会有中间的节点发生分裂的情况。

最糟糕的情况下，主键ID是随机无序生成的(例如Java中一个UUID字符串)，这种情况下，新插入的记录会随机分配到任何一个数据页，如果该页已满，就会触发页分裂。

如果主键ID由标准版雪花算法生成，最好的情况下，是每个时间戳内只有一个节点在生成ID，这时候算法的效果等同于理想情况的顺序递增，即跟auto_increment无差。最坏的情况下，是每个时间戳内所有节点都在生成ID，这时候算法的效果接近于无序(但仍比UUID的完全无序要好得多，因为workerId只有10位决定了最多只有1024个节点)。实际生产中，算法的效果取决于业务流量，并发度越低，算法越接近理想情况。

那么，换成新版算法又会如何呢？

新版算法从全局角度来看，ID是无序的，但对于每一个workerId，它生成的ID都是严格单调递增的，又因为workerId是有限的，所以最多可划分出1024个子序列，每个子序列都是单调递增的。对于数据库而言，也许它初期接收的ID都是无序的，来自各个子序列的ID都混在一起，就像这样：

初期

如果这时候来了个worker1-seq2，显然会造成页分裂：

首次分裂

但分裂之后，有趣的事情发生了，对于worker1而言，后续的seq3，seq4不会再造成页分裂(因为还装得下)，seq5也只需要像顺序增长那样新建页进行链接(区别是这个新页不是在双向链表的尾部)。注意，worker1的后续ID，不会排到worker2及之后的任意节点(因而不会造成后边节点的页分裂)，因为它们总比worker2的ID小；也不会排到worker1当前节点的前边(因而不会造成前边节点的页分裂)，因为worker1的子序列总是单调递增的。在这里，我们称worker1这样的子序列达到了稳态，意为这条子序列已经”稳定”了，它的后续增长只会出现在子序列的尾部，而不会造成其它节点的页分裂。

同样的事情，可以推广到各个子序列上。无论前期数据库接收到的ID有多乱，经过有限次的页分裂后，双向链表总能达到这样一个稳定的终态：

终态

到达终态后，后续的ID只会在该ID所属的子序列上进行顺序增长，而不会造成页分裂。该状态下的顺序增长与auto_increment的顺序增长的区别是，前者有1024个增长位点(各个子序列的尾部)，后者只有尾部一个。

到这里，我们可以回答开头所提出的问题了：新算法从全局来看的确不是全局递增的，但该算法是收敛的，达到稳态后，新算法同样能达成像全局顺序递增一样的效果。

以上只提到了序列不停增长的情况，而实践生产中，不光有新数据的插入，也有旧数据的删除。而数据的删除有可能会导致页合并(innodb若发现相邻2个数据页的空间利用率都不到50%，就会把它俩合并)，这对新算法的影响如何呢？

经过上面的流程，我们可以发现，新算法的本质是利用前期的页分裂，把不同的子序列逐渐分离开来，让算法不断收敛到稳态。而页合并则恰好相反，它有可能会把不同的子序列又合并回同一个数据页里，妨碍算法的收敛。尤其是在收敛的前期，频繁的页合并甚至可以让算法永远无法收敛(你刚分离出来我就又把它们合并回去，一夜回到解放前~)！但在收敛之后，只有在各个子序列的尾节点进行的页合并，才有可能破坏稳态(一个子序列的尾节点和下一个子序列的头节点进行合并)。而在子序列其余节点上的页合并，不影响稳态，因为子序列仍然是有序的，只不过长度变短了而已。

2.数据库号段模式

详细内容参见：GitHub - didi/tinyid: ID Generator id生成器 分布式id生成系统，简单易用、高性能、高可用的id生成系统

在简单系统中，我们常常使用DB的Id自增方式来标识和保存数据，随着系统的复杂，数据的增多，分库分表成为了常见的方案，DB自增已无法满足要求。这时候全局唯一的Id生成系统就派上了用场。当然这只是Id生成其中的一种应用场景。那么Id生成系统有哪些要求呢？

  1. 全局唯一的Id:无论怎样都不能重复，这是最基本的要求了
  2. 高性能:基础服务尽可能耗时少，如果能够本地生成最好
  3. 高可用:虽说很难实现100%的可用性，但是也要无限接近于100%的可用性
  4. 简单易用: 能够拿来即用，接入方便，同时在系统设计和实现上要尽可能的简单

我们先来看一下最常见的Id生成方式，DB的auto_increment，相信大家都非常熟悉，我也见过一些同学在实战中使用这种方案来获取一个Id，这个方案的优点是简单，缺点是每次只能向DB获取一个Id，性能比较差，对DB访问比较频繁，DB的压力会比较大。那么是不是可以对这种方案优化一下呢，可否一次向DB获取一批Id呢？答案当然是可以的。

一批Id，我们可以看成是一个Id范围，例如(1000,2000]，这个1000到2000也可以称为一个”号段”，我们一次向DB申请一个号段，加载到内存中，然后采用自增的方式来生成Id，这个号段用完后，再次向DB申请一个新的号段，这样对DB的压力就减轻了很多，同时内存中直接生成Id，性能则提高了很多。那么保存DB号段的表该怎设计呢？

2.1DB号段算法描述

id start_id end_id
1 1000 2000

如上表，我们很容易想到的是DB直接存储一个范围(start_id,end_id]，当这批Id使用完毕后，我们做一次update操作，update start_id=2000(end_id), end_id=3000(end_id+1000)，update成功了，则说明获取到了下一个Id范围。仔细想想，实际上start_id并没有起什么作用，新的号段总是(end_id,end_id+1000]。所以这里我们更改一下，DB设计应该是这样的:

id biz_type max_id step version
1 1000 2000 1000 0
  • 这里我们增加了biz_type，这个代表业务类型，不同的业务的Id隔离
  • max_id则是上面的end_id了，代表当前最大的可用Id
  • step代表号段的长度，可以根据每个业务的QPS来设置一个合理的长度
  • version是一个乐观锁，每次更新都加上version，能够保证并发更新的正确性

那么我们可以通过如下几个步骤来获取一个可用的号段:

  • A.查询当前的max_id信息：select id, biz_type, max_id, step, version from tiny_id_info where biz_type = ‘test’;
  • B.计算新的max_id: new_max_id = max_id + step
  • C.更新DB中的max_id：update tiny_id_info set max_id = #{new_max_id} , verison = version + 1 where id = #{id} and max_id = #{max_id} and version = #{version}
  • D.如果更新成功，则可用号段获取成功，新的可用号段为(max_id, new_max_id]
  • E.如果更新失败，则号段可能被其他线程获取，回到步骤A，进行重试

2.2号段生成方案的简单架构

如上我们已经完成了号段生成逻辑，那么我们的Id生成服务架构可能是这样的:

简单架构

Id生成系统向外提供http服务，请求经过我们的负载均衡router，到达其中一台tinyid-server，从事先加载好的号段中获取一个Id，如果号段还没有加载，或者已经用完，则向DB再申请一个新的可用号段，多台server之间因为号段生成算法的原子性，而保证每台server上的可用号段不重，从而使Id生成不重。可以看到如果tinyid-server如果重启了，那么号段就作废了，会浪费一部分Id；同时Id也不会连续；每次请求可能会打到不同的机器上，Id也不是单调递增的，而是趋势递增的，不过这对于大部分业务都是可接受的。

2.3简单架构的问题

到此一个简单的Id生成系统就完成了，那么是否还存在问题呢？回想一下我们最开始的Id生成系统要求，高性能、高可用、简单易用，在上面这套架构里，至少还存在以下问题:

  • 当Id用完时需要访问DB加载新的号段，DB更新也可能存在version冲突，此时Id生成耗时明显增加
  • DB是一个单点，虽然DB可以建设主从等高可用架构，但始终是一个单点
  • 使用http方式获取一个Id，存在网络开销，性能和可用性都不太好

2.4架构优化方案

2.4.1双号段缓存

对于号段用完需要访问DB，我们很容易想到在号段用到一定程度的时候，就去异步加载下一个号段，保证内存中始终有可用号段，则可避免性能波动。

2.4.2增加多DB支持

DB只有一个master时，如果DB不可用(down掉或者主从延迟比较大)，则获取号段不可用。实际上我们可以支持多个DB，比如2个DB，A和B，我们获取号段可以随机从其中一台上获取。那么如果A,B都获取到了同一号段，我们怎么保证生成的Id不重呢？tinyid是这么做的，让A只生成偶数Id，B只生产奇数Id，对应的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序列。

2.4.3增加tinyid-client

使用http获取一个Id，存在网络开销，是否可以本地生成Id？为此我们提供了tinyid-client，我们可以向tinyid-server发送请求来获取可用号段，之后在本地构建双号段、Id生成，如此Id生成则变成纯本地操作，性能大大提升，因为本地有双号段缓存，则可以容忍tinyid-server一段时间的down掉，可用性也有了比较大的提升。

2.5tinyid最终架构

最终架构

  • tinyid提供http和tinyid-client两种方式接入
  • tinyid-server内部缓存两个号段
  • 号段基于DB生成，具有原子性
  • DB支持多个
  • tinyid-server内置easy-router选择DB