彻底解决雪花算法时间回拨问题新方案

Butterfly 简介

雪花算法是twitter提出的分布式id生成器方案,但是有三个问题,其中前两个问题在业内很常见:

  • 时间回拨问题
  • 机器id的分配和回收问题
  • 机器id的上限问题

Butterfly(蝴蝶)是一个超高性能的发号器框架。起名Butterfly是用世界上没有完全相同的蝴蝶翅膀来表示该算法的唯一性。框架通过引入多种新的方案不仅解决了雪花算法存在的所有问题,而且还能够提供比雪花算法更高的性能。在单机版QPS理论值为51.2(w/s)这种情况下,新的方案在一些机器上可达 1200(w/s) 甚至更高。

其中业内针对前两个问题都有个自己的解决方式,但是都不是很完美,或者说没有完全解决。我们这里从新的思路出发,通过改造雪花算法以及其他相关方式彻底解决了以上的三个问题。该方案算是对雪花算法比较完美的一种实现方式。方案请见方案介绍

框架说明文档:https://www.yuque.com/simonalong/butterfly/tul824

源码:https://github.com/SimonAlong/Butterfly

以下内容摘自框架说明文档

方案介绍

雪花算法

雪花算法是twitter提出的分布式id生成器方案,也叫发号器方案。这里简单介绍下雪花算法

这个就是原生的雪花算法分配

  • 41bit时间戳:这里采用的就是当前系统的具体时间,单位为毫秒
  • 10bit工作机器ID(workerId):每台机器分配一个id,这样可以标示不同的机器,但是上限为1024,标示一个集群某个业务最多部署的机器个数上限
  • 12bit序列号(自增域):表示在某一毫秒下,这个自增域最大可以分配的bit个数,在当前这种配置下,每一毫秒可以分配2^12个数据,也就是说QPS可以到 409.6 w/s。

存在的问题

  • 时间回拨问题:由于机器的时间是动态的调整的,有可能会出现时间跑到之前几毫秒,如果这个时候获取到了这种时间,则会出现数据重复
  • 机器id分配及回收问题:目前机器id需要每台机器不一样,这样的方式分配需要有方案进行处理,同时也要考虑,如果改机器宕机了,对应的workerId分配后的回收问题
  • 机器id上限:机器id是固定的bit,那么也就是对应的机器个数是有上限的,在有些业务场景下,需要所有机器共享同一个业务空间,那么10bit表示的1024台机器是不够的。

业内方案

业内的方案中对以上三个问题有这么几种处理,但是都没有彻底解决,我们这里表述下

1.时间回拨问题:

  • 采用直接抛异常方式:这种很不友好,太粗暴
  • 采用等待跟上次时间的一段范围:这种算是简单解决,可以接受,但是如果等待一段时间后再出现回拨,则抛异常,可接受,但是不算彻底解决

2.机器id分配及回收:

  • 采用zookeeper的顺序节点分配:解决了分配,回收可采用zookeeper临时节点回收,但是临时节点不可靠,存在无故消失问题,因此也不可靠
  • 采用DB中插入数据作为节点值:解决了分配,没有解决回收

3.机器id上限

该问题在业内都没有处理,也就是说如果采用雪花算法,则必定会存在该问题,但是该问题也只有需要大量的业务机器共享的场景才会出现,这种情况,采用客户端双Buffer+DB这种非雪花算法的方案也未尝不可。


Butterfly方案

对于以上三个问题,我们这里简述下我们的方案。

1.时间回拨问题

这里采用新的方案:大概思路是:启动时间戳采用的是“历史时间”,每次请求只增序列值,序列值增满,然后“历史之间”增1,序列值重新计算。具体方案请见后面

2.机器id分配和回收

这里机器id分配和回收具体有两种方案:zookeeper和db。理论上分配方案zk是通过哈希和扩容机器,而db是通过查找机制。回收方案,zk采用的是永久节点,节点中存储下次过期时间,客户端定时上报(设置心跳),db是添加过期时间字段,查找时候判断过期字段。

3.机器id上限

这个采用将改造版雪花+zookeeper分配id方案作为服务端的节点,客户端采用双Buffer+异步获取提高性能,服务端采用每次请求时间戳增1。

以上是方案的简述,对于方案的具体实现请看下面

改进版雪花设计

前面我们已经知道雪花算法的三个问题,以及也简述了我们针对雪花算法的几个方案。这里详细描述针对雪花算法的调整和我们自己的方案。

bit划分调整

我们对雪花算法的bit划分做了调整,将“机器id(workerId)”从高位置换到了地位,同时将bit也边更为了13bit,同时缩减了序列号(自增域)的bit为9bit。

将其中“机器id”调整到最后,是为了避免“序列号”增1导致的整体数据增1的问题,这样可以在一定程度上规避外部数据对id的猜测,以防止恶意爬取。

时间获取处理

采用“历史时间”:

这里是我们方案的核心,我们这里采用的不是实际时间,而是历史时间,在进程启动后,我们会将当前时间(实际处理采用了延迟10ms启动)作为该业务这台机器进程的时间戳中的起始时间字段。后续的自增是在序列号自增到最大值时候时间戳增1,而序列号重新归为0,算是将时间戳和序列号作为一个大值进行自增,只是初始化不同。

序列号自增:

每次有数据请求,直接对序列号增加即可,序列号从0增加到最大,到达最大时,时间戳字段增加1,其实是时间增加1毫秒,序列号重0计算。

机器id分配和回收:

对机器的分配和回收这里有三种默认方式,不过也支持用户自定义实现

(单机版)zookeeper分配和回收:

分配采用哈希方式在预分配的一些空置永久节点中进行分配,节点后缀是有编号的,查找其中节点没有被占用,或者被占用但是占用超时的节点进行分配,其中分配的编号就是WorkerId。分配完毕,定期更新节点中的超时时间,超时后下次节点分配时会判断超时。这里初始节点默认设置为16个节点,如果节点都被占用(占用或者没占用但是超时时间没过),则模仿HashMap方式进行2倍扩容,然后重新分配。

(单机版)db分配和回收:

先看过期的里面最小的id,找到了则当前workerId就是机器id。如果过期中没找到,则查看其中最大的workerId并增1,然后新增,当前增1后的workerId就是分配的workerId。

(分布式版)集群分配workerId:

客户端的wokerId是每次Buffer请求中携带过来的,这样对客户端而言就没有workerId上限问题,因为workerId是服务端节点分配的。由于采用了网络传输,为了提高性能,客户端这里采用双Buffer+异步刷新方式,server端这里采用改进版的雪花+zookeeper分配和回收wokerId方式。

问题解决方式

1.时间回拨问题:

采用历史时间则天然的不存在时间回拨问题。但是在超高并发情况下,历史的时间很快用完,时间一直保持在最新时间的话,这个时候出现时间回拨,则采用业界对于时间回拨的处理方式(首次等待,即等待一段回拨时间)

2.机器id分配及回收:

机器的id分配和回收,我们这里采用zookeeper和db两种方式分配,这两种方式,均只有在进程启动的时候生效,后续就不再跟客户端有更多交互,唯一的是有个定时上报过期时间的任务。该过期时间为24小时,因此zookeeper或者db宕机一天,该发号器都不会有任何问题。回收这里采用的是上报的过期时间,过期了,则下次分配可以直接使用。

3.机器id上限

其中单机版的zookeeper和 DB均不是解决这个问题而存在的,其中(分布式版)distribute分配workerId是采用服务端方式,用服务端方式启动作为workerId的分配者,客户端使用的时候每次Buffer请求中服务端会将那一次的workerId和时间戳返回过来。这样虽然服务集群的workerId上限(即服务集群节点个数上限)是有的,但是对于客户端拥有的集群而言,理论上无上限,因为一个服务端节点就可以服务一个业务集群中的许多节点。

超高性能

由于时间戳采用的是过去时间,我们这样来看,如果实际QPS小于理论值(我们这里是9bit,理论值就是51.2w/s),那么一段时间后,产生的最新的全局id中包含的时间跟当前实际时间就有一定的时间差,那么这个时间差我们可以称之为“时间缓存”,而每一毫秒对应的都是0~最大值的这么多个数据,随着时间的积累,这里可以有海量的“逻辑上”的数据缓存。我们想象这样一个场景,如果通常情况下业务的场景QPS是小于51.2w/s的,那么这个缓存就会越来越大,那么如果一瞬间有大量的请求过来的时候,由于我们有大量的缓存,我们这里就可以产生更多不重复的id,将QPS提高到几十倍甚至更多,自己的小本测试中可以达到1200w/s。如果QPS一直是高位的话比51.2w/s高的话,那么这种其实业务方面就可以通过业务集群化扩容,将单个业务节点性能降低,不过就发号器技术上来说的话,目前单机版的这个在这种持续高并发情况下,经过测试理论上会保持在53w/s左右。

workerId分配

分配workerId我们这里有三种默认方式,用户也可以自定义自己的默认实现方式

1.(单机版)zookeeper分配和回收 2.(单机版)db分配和回收 3.(分布式版)通过服务端分配和回收

其中单机版都是直接提供jar包就可以直接使用,只是根据采用的方式不同,进行不同的配置即可

zookeeper分配

哈希分配

采用zookeeper进行分配workerId的时候,首先生成一个uuid,然后根据这个uuid进行对当前的命名空间的当前已分配的空间最大值进行取余,得到一个临时的下标,然后查看以这个下标作为的zookeeper节点,查看该节点是否被占用,也就是该节点中的过期时间是否过期,如果过期,则该下标就是对应的workerId。如果没有过期,则该下标+1,并重新判断,如果到达当前分配空间的最大值,则从0开始继续查找可用节点,如果最后找到最开始的节点,则说明当前空间中已经没有可用节点,则进入到扩容模块。这里的扩容其实很简单,其实就是在初始节点个数(初始节点个数为16)上乘2,然后重新哈希。

其中数据在zookeeper中的节点分配如下


/butterfly/sequence
|
|_bizType_1
|    |
|    |_config
|    |
|    |_worker_0
|    |	   |
|    |	   |_session
|    |		
|    |_worker_1
|    |	   |
|    |	   |_session
|    |
|    ...
|
|_bizType_2
|    |
|    |_config
|    |
|    |_worker_0
|    |	   |
|    |	   |_session
|    |		
|    |_worker_1
|    |	   |
|    |	   |_session
|    ...

节点解释:

butterfly/sequence:zookeeper中的固定节点bizType1/bizType2:为对应的命名空间,实际命名空间为用户自定义config:为每个命名空间中放置配置的节点,其中存储的信息如下,一个是bit分配值,一个是命名空间中节点对应的值,bit分配的值,是为了以后扩展使用,这里先放置在这里

{    "currentMaxMachine":16,    "sequenceBits":9,    "timestampBits":41,    "workerBits":13}

workerx:对应的workerId对应的节点,其中有个session节点,该节点为临时节点,如果不存在session节点,则表示当前节点没被占用,则不判断过期时间,直接在内部创建session节点,并将下标x作为workerId返回。如果被占用,采用的是查看workerx中存储的下次过期时间,如果当前过期时间小于当前时间,则认为已经过期,即创建session节点,并更新worker_x中的信息,并将x作为workerId使用。


{
    "ip":"127.0.0.1",
    "lastExpireTime":1588955705615,
    "processId":"90705",
    "uidKey":"762bcaad-48f5-4da9-8a1d-5e05a28add18"
}

定时上报

没起对应的进程启动,并分配好workerId之后,就会启动每5s向该worker_x节点上报一次下次过期的时间,目前采用的下次过期时间为24小时,也就是说一个进程一旦占用一个节点,一般情况下都是异常断开后最多占用24小时。但是正常断开的话,会自动将这些信息清理掉。

db分配

查找数据

采用db方式的话,需要先保证已经创建了butterfly_uuid_generator ,如果没有则先在对应的库中创建


CREATE TABLE `butterfly_uuid_generator` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键id',
  `namespace` varchar(128) DEFAULT '' COMMENT '命名空间',
  `work_id` int(16) COMMENT '工作id',
  `last_expire_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '下次失效时间',
  `uid` varchar(128) DEFAULT '0' COMMENT '本次启动唯一id',
  `ip` bigint(20) NOT NULL DEFAULT '0' COMMENT 'ip',
  `process_id` varchar(128) NOT NULL DEFAULT '0' COMMENT '进程id',
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_name_work` (`namespace`,`work_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='发号器表';

查找数据,这里首先是在对应的命名空间中,查找过期的数据,如果能找到其中id最小的,则该id对应中的workerId就是我们要分配的workerId,如果都没有过期,这块有问题,明天继续看,那么就找最小的workerId,并将workerId+1,重新插入到数据库中(之前查询其实是采用事务中添加悲观锁方式,保证这里不会有多个重复的插入),其中对应的workerId+1就是我们要分配的workerId。

定时更新(心跳)

workerId分配之后,每次都要定时(每5秒)刷新当前命名空间中对应workerId中对应的下次过期时间(就是当前时间往后推24小时)。如果对应的进程异常宕机了,则该数据对应的这个数据会存在,只是过期时间不会再更新,而如果改进程是正常宕机,则会正常将db中的对应的那条数据删除掉。方便下次分配者继续分配workerId。

我建议,在表中增加一个status字段,在数据正常宕机之后,就是将当前的这条数据状态设置为不可用,在下次数据请求的时候,首先查找状态为不可用的数据,如果找到,则分配

1.找状态为关闭的2.找已经过期的3.找workerId最大的,并将workerId+1插入到DB中

这样就可以得到最新的workerId了

分布式模式

客户端

一、代理获取数据二、双Buffer+异步获取数据

服务端

采用改进版雪花+zookeeper模式

一、使用示例

目前框架理论完成,还有待验证和考验,暂时还未发布到中央仓库,有意向同学可以先基于源码自行编译在内部使用

该框架中“机器id(workerId)”的分配方式默认有三种方式

1.(单机版)zookeeper分配 2.(单机版)db分配 3.(分布式版)通过服务端分配

不同的分配方式就是不同的用法,依赖也是不同。其中单机版和分布式版也要根据场景来自行选择:

  • 单机版:无网络消耗,高可靠性,超高性能(单机可达1200w/s),有workerId上限问题
  • 分布式版:有网络消耗,高可用,高性能(集群单节点可达100w/s),无雪花算法任何问题,但是需要维护服务端

zookeeper分配workerId

1.添加依赖


<dependency>
  <groupId>com.github.simonalong</groupId>
  <artifactId>butterfly-zookeeper-allocator</artifactId>
  <!--替换为具体版本号-->
  <version>${last.version.release}</version>
</dependency>

2.使用示例


@Test
public void test(){
    ZkButterflyConfig config = new ZkButterflyConfig();
    config.setHost("localhost:2181");

    ButterflyIdGenerator generator = ButterflyIdGenerator.getInstance(config);
    // 设置起始时间,如果不设置,则默认从2020年2月22日开始
    generator.setStartTime(2020, 5, 1, 0, 0, 0);
    // 添加业务空间,如果业务空间不存在,则会注册
    generator.addNamespaces("test1", "test2");
    Long uuid = generator.getUUid("test1");
    System.out.println(uuid);
}

db分配workerId

1.添加依赖


<dependency>
  <groupId>com.github.simonalong</groupId>
  <artifactId>butterfly-db-allocator</artifactId>
  <!--替换为具体版本号-->
  <version>${last.version.release}</version>
</dependency>

2.建表

对应的库中需要包含如下的表,没有则创建


CREATE TABLE `butterfly_uuid_generator` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键id',
  `namespace` varchar(128) DEFAULT '' COMMENT '命名空间',
  `work_id` int(16) COMMENT '工作id',
  `last_expire_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '下次失效时间',
  `uid` varchar(128) DEFAULT '0' COMMENT '本次启动唯一id',
  `ip` bigint(20) NOT NULL DEFAULT '0' COMMENT 'ip',
  `process_id` varchar(128) NOT NULL DEFAULT '0' COMMENT '进程id',
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_name_work` (`namespace`,`work_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='发号器表';

3.使用示例


@Test
public void test(){
    DbButterflyConfig config = new DbButterflyConfig();
    config.setUrl("jdbc:mysql://127.0.0.1:3306/neo?useUnicode=true&characterEncoding=UTF-8&useSSL=false&&allowPublicKeyRetrieval=true");
    config.setUserName("neo_test");
    config.setPassword("neo@Test123");

    ButterflyIdGenerator generator = ButterflyIdGenerator.getInstance(config);
    // 设置起始时间,如果不设置,则默认从2020年2月22日开始
    generator.setStartTime(2020, 5, 1, 0, 0, 0);
    // 添加业务空间,如果业务空间不存在,则会注册
    generator.addNamespaces("test1", "test2");
    Long uuid = generator.getUUid("test1");
    System.out.println(uuid);
}

服务端分配workerId

1.服务端启动

服务端和客户端采用dubbo方式进行通讯,下载server包,将如下命令中的dubbo注册中心替换即可启动。

java -jar -Ddubbo.registry.address=127.0.0.1:2181 butterfly-server-1.0.0.jar

2.客户端添加依赖

客户端添加依赖


<dependency>
  <groupId>com.github.simonalong</groupId>
  <artifactId>butterfly-distribute-allocator</artifactId>
  <!--替换为具体版本号-->
  <version>${last.version.release}</version>
</dependency>

3.使用示例


@Test
public void test(){
    DistributeButterflyConfig config = new DistributeButterflyConfig();
    config.setZkHose("localhost:2181");

    ButterflyIdGenerator generator = ButterflyIdGenerator.getInstance(config);
    // 设置起始时间,如果不设置,则默认从2020年2月22日开始
    generator.setStartTime(2020, 5, 1, 0, 0, 0);
    // 添加业务空间,如果业务空间不存在,则会注册
    generator.addNamespaces("test1", "test2");
    Long uuid = generator.getUUid("test1");
    System.out.println(uuid);
}
  • 发表于:
  • 本文为 InfoQ 中文站特供稿件
  • 首发地址https://www.infoq.cn/article/cf27b51c9e3cde1b2c585f0ec
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券