Butterfly 简介
雪花算法是 twitter 提出的分布式 id 生成器方案，但是有三个问题，其中前两个问题在业内很常见：
-
时间回拨问题
-
机器 id 的分配和回收问题
-
机器 id 的上限问题
Butterfly（蝴蝶）是一个超高性能的发号器框架。起名 Butterfly 是用世界上没有完全相同的蝴蝶翅膀来表示该算法的唯一性。框架通过引入多种新的方案不仅解决了雪花算法存在的所有问题，而且还能够提供比雪花算法更高的性能。在单机版 QPS 理论值为 51.2(w/s)这种情况下，新的方案在一些机器上可达 1000(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 提高到几十倍甚至更多，自己的小本测试中最高可以达到 1000w/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：zookeeper 中的固定节点 bizType1/bizType2：为对应的命名空间，实际命名空间为用户自定义 config：为每个命名空间中放置配置的节点，其中存储的信息如下，一个是 bit 分配值，一个是命名空间中节点对应的值，bit 分配的值，是为了以后扩展使用，这里先放置在这里
workerx：对应的 workerId 对应的节点，其中有个 session 节点，该节点为临时节点，如果不存在 session 节点，则表示当前节点没被占用，则不判断过期时间，直接在内部创建 session 节点，并将下标 x 作为 workerId 返回。如果被占用，采用的是查看 workerx 中存储的下次过期时间，如果当前过期时间小于当前时间，则认为已经过期，即创建 session 节点，并更新 worker_x 中的信息，并将 x 作为 workerId 使用。
定时上报
每次客户端对应的进程启动，并分配好 workerId 之后，就会定期向该 worker_x 节点上报一次下次过期的时间，目前采用的下次过期时间为 24 小时，也就是说一个进程一旦占用一个节点，一般情况下都是异常断开后最多占用 24 小时。但是正常断开的话，会自动将这些信息清理掉。
db 分配
查找数据
采用 db 方式的话，需要先保证已经创建了butterfly_uuid_generator ，如果没有则先在对应的库中创建
查找数据，这里首先是在对应的命名空间中，查找过期的数据，如果能找到其中 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 模式的纯内存化的无 DB 的服务端
一、使用示例
该框架中“机器 id（workerId）”的分配方式默认有三种方式
1.（单机版）zookeeper 分配
2.（单机版）db 分配
3.（分布式版）通过服务端分配
不同的分配方式就是不同的用法，依赖也是不同。其中单机版和分布式版也要根据场景来自行选择：
-
单机版：无网络消耗，高可靠性，超高性能（单机可达 1000w/s 甚至更高），有 workerId 上限问题
-
分布式版：有网络消耗，高可用，高性能（集群单节点可达 100w/s），无雪花算法任何问题，但是需要维护服务端
zookeeper 分配 workerId
1.添加依赖
2.使用示例
db 分配 workerId
1.添加依赖
2.建表
对应的库中需要包含如下的表，没有则创建
3.使用示例
服务端分配 workerId
1.服务端启动
服务端和客户端采用 dubbo 方式进行通讯，下载 server 包，将如下命令中的 dubbo 注册中心替换即可启动。
java -jar -Ddubbo.registry.address=127.0.0.1:2181 butterfly-server-1.0.0.jar
2.客户端添加依赖
客户端添加依赖