分布式id生成器：彻底解决雪花算法时间回拨问题
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生成器方案，也叫发号器方案。这里简单介绍下雪花算法
image.png
这个就是原生的雪花算法分配
- 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。
image.png
将其中“机器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中的固定节点bizType_1/bizType_2：为对应的命名空间，实际命名空间为用户自定义config：为每个命名空间中放置配置的节点，其中存储的信息如下，一个是bit分配值，一个是命名空间中节点对应的值，bit分配的值，是为了以后扩展使用，这里先放置在这里
{
"currentMaxMachine":16,
"sequenceBits":9,
"timestampBits":41,
"workerBits":13
}
worker_x：对应的workerId对应的节点，其中有个session节点，该节点为临时节点，如果不存在session节点，则表示当前节点没被占用，则不判断过期时间，直接在内部创建session节点，并将下标x作为workerId返回。如果被占用，采用的是查看worker_x中存储的下次过期时间，如果当前过期时间小于当前时间，则认为已经过期，即创建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);
}
