如何做一个靠谱的发号器

安宇雨 - 随手采集
2019-09-26 17:36:40
随手采集
0000-未整理-等待研究

为什么需要一个发号器

在使用数据库时，表的主键经常会使用数据库的自增（auto_increment）来产生。这当然很方便也很高效。但是使用自增也会带来一些麻烦。如果从一个数据库以外的地方，也就是发号器来产生全局唯一 ID，这些问题就可以得到解决，生活就可以更美好。

难以适应分片场景
在采用数据库分片时，如果使用数据库自增 ID，不同分片上会产生相同的 ID。单靠 ID 无法唯一标示一个对象，还需要额外加上分片字段才行。如果需要将 ID 用于其他对象的关联时，会麻烦很多。而采用发号器生成的是全局唯一的 ID，单靠 ID 就能实现关联。同时，这也使得采用 ID 作为分片字段成为可能。
主备切换时数据冲突
在 MySQL 集群发生主备切换时，异步复制无法确保主从完全同步。在备库开放写入后，备库上产生的自增 ID 会和尚未同步的主库上的数据冲突。这样一来，即使原来的主库恢复了，也无法重新加入集群。数据修复也变成了一件非常困难的事情。引入发号器以后，备库上插入的 ID 和原来主库上的 ID 是不会重复的。因此，未复制的新增数据和对这些新增数据的修改就不会在备库发生冲突。
网络异常时无法判断插入是否成功
当插入记录时，如果使用数据库自增 ID，在完成插入后，才能得到产生的 ID。如果在执行语句时发生网络中断，客户端无法知道事务是否成功，即使成功，也无法再获得产生的 ID。如果使用发号器，就可以在插入之前预先产生 ID。如果碰到网络中断，可以用已经获得的 ID 去尝试查询来判断之前的插入是否成功。

此外，一些业务 ID 会需要一个全局唯一的整数作为它的组成部分。其他的分布式系统可以用全局单调的唯一 ID 作为事务号。有一个现成的服务就不用各自实现了。

发号器的必要特性

既然叫发号器，首先就得保证 ID 的全局唯一。就是说保证无论什么情况下都不会发出重复的 ID。这看起来很简单，但是事实上，很多实现却上并没有做到这点。要真正做到全局唯一，发号器必须要实现 crash safe，并不受外部环境变化影响。

crash safe
首先是 crash safe。即得保证在服务崩溃重新恢复后，不会产生已经发过的 ID。在服务彻底完蛋时，也要能够在其他地方恢复出一个一定能用的。有的实现定期保存或者异步保存已经发过的 ID。如果发生崩溃，如果直接用保存过的 ID 继续发，就会发出已经发过的号。有的实现采用 MySQL 或 Redis 来产生 ID。由于 MySQL 和 Redis 的复制本身难以保证强一致，在发生主备切换时，备机尚未完全同步的话，还是会发出重复的 ID 来。有的实现没有使用副本，单纯靠分片来实现负载均衡和高可用，这时如果某个实例完蛋了，想要重新恢复一个就没法了。
不受外部环境变化影响
很多发号器实现是基于时间戳的。但是有些实现直接采用了机器上的时间戳作为 ID 的一部分。如果机器时间发生回跳（不要认为这不可能），就会造成 ID 重复。使用时间戳同时也对机器时间的精度有了依赖。

要让发号器能真正有用，还得实现高可用，并能支撑足够大的吞吐量。不然发号器本身也会成为一个单点或瓶颈。

如何设计发号器

有赞同样有对发号器的需求。经过对现有实现的考察后，我们还是打算实现一个自己的发号器，我给它起了个名字：March。我们的发号器同样要解决这些问题。

持久化

要满足真正的全局唯一，持久化是必须的。而且持久化还必须是不会丢失的，强一致的。

如果发号器实现是分散在各个应用服务器上的，由于应用服务器的持久化能力是难以保证的，可靠性就会受影响。而且这样一来，每个应用服务器也要有一个终身及死后也全局唯一的 ID 作为产生的 ID 的一部分，来满足全局唯一，这就大大提高了部署和运维的门槛。所以，我们认为发号器最好还是集中式的。

在采用集中式的前提下，持久化的副本也是不可少的。要自己实现这样的一个持久化系统是很难的。所以，在持久化方案上，我们选择了现成的 etcd。etcd 能满足不会丢失的，多副本，强一致的全部需求。持久化就可以全部放到 etcd 中，发号器本身就可以是无状态的，这样一来，高可用的实现也会容易一些。

是否全局单调

是否全局单调其实是个权衡。在确定要高可用的前提下，全局单调和负载均衡是不可兼得的（可以想想为什么）。我们最终还是选择实现全局单调。全局单调的 ID 有额外的好处。作为主键时，可以直接代替时间字段排序。由于 MySQL 二级索引是指向主键的，使用主键排序通常可以避免排序操作，直接利用索引就能完成。另外，如果要实现一些分布式一致性系统，一个全局单调的 ID 生成器也是一个必备的组件。

高可用

由于采用了全局单调，高可用方案就只能是主备的。一个集群内，同时只能有一个实例对外提供服务。这时候就要考虑怎么实现选主和故障切换。既然我们用了 etcd，实现高可用的时候也正好可以用上它的 TTL、Watch 这些特性。然后也要能让客户端知道哪个实例才是主实例，可以自动切换访问路径。

ID 的形式

发号器产生的 ID 一般都是 64 位整数，这样对数据库比较友好，容量也能满足业务需求，不会哪天爆了。通常产生的 ID 可以分成两大类。一类是单纯的 Sequence，即一个不断递增的整数。另一类是基于 Timestamp 的，由于机器时间的精度限制，通常都会额外再加一段 Sequence。为了分布式，还经常会加上各种不同的标示实例的位。不同的实现无非就是这些东西的组合以及各段的长短的变化。有赞之前已经有了几个实现。新的发号器要落地，也得兼容现有的。所以不同的 ID 的形式还是都得支持。但是具体实现细节上，可以比原有的更进一步。

认证和权限控制

使用发号器的业务方会有很多。为了信息安全，和避免相互干扰，认证和权限控制功能也有了需求。March 可以设置多个用户，为每个用户分配访问不同的发号器的权限，以及其他的创建，管理类权限。用户信息同样不能丢，所以也持久化在 etcd 中。

通信协议

作为一个服务，就会有和客户端交互。有交互，就要有一个协议。我们希望尽量能采用一个现成的协议。这样对实现不同语言的客户端会方便很多。同时这个协议要足够轻量高效，也能具备扩展性。我们最后选择了 Redis 协议。Redis 协议很简单，协议本身的负担小。由于是个广泛使用的东西，各种语言都有它的库。这样在实现客户端 SDK 的时候，就有了个很好的起点。现成的一些命令，如 INCR，INCRBY，GET 等本身也很适合用于发号器。在需要一些特殊的功能时，也可以自己添加新命令。高可用方面，Redis Cluster 的协议也可以用上。这样客户端的自动切换就不用自己实现了。对于服务端，好几个语言也都有现成的库。

发号器的实现

有赞的发号器 March 是用 Go 语言实现的。语言选择上其实没太大讲究。不过对于这类项目，Go 在开发效率，部署简便，和倾向低延迟的 gc 优化还是有一些优势。

ID生成

前面说过，发号器产生的 ID 可以分成两大类。一类是 Sequence，一类是基于 Timestamp 的。这两类有各自的实现。

Sequence
March 在启动时会从 etcd 中载入之前持久化的已经发过的 id 作为起点。然后执行一次持久化，将起始 id + batch 保存下来。 [ id, id + batch ) 的区间就是缓存。客户端请求时，下发的 id 都是从这个缓存中取的。同时启动一个 goroutine 来做持久化。在这个缓存的容量低于水位线（默认是 50%）时，会异步通知这个持久化 goroutine 进行持久化，将 id + batch 2 保存下来。此时，缓存的上界就扩容到了 id + batch 2，以此类推。由于持久化是异步的，所以一般情况下，并不会阻塞请求，造成请求延迟增大。但是有突发的并发时，在持久化没进行完，缓存就已经耗尽的情况下，为了保证正确性，才会发生阻塞，等待持久化完成。所以，对于高并发的应用，配置一个大的缓存区间可以获取更高的性能。比如将 batch 设为 10000，平均发出 10000 个号才需要持久化一次。备机平时是不提供服务的，在发生主备切换时，备机才会从持久化中重新载入配置。所以备机提升为主机以后，也可以保证不会发重，只是从客户端看来，会跳空一段 id。不过这也算不上什么问题。
Timestamp
Timestamp 类型的 ID 分成 3 段：node，timestamp，sequence。通过配置各个段的长度和偏移，以及时间戳的精度，就可以兼容各种已有的基于时间戳的发号器实现。多个请求到来时，如果 timestamp 相同，会增长 sequence。timestamp 改变时，就清零 sequence。有一点特别的地方是，我们允许 sequence 段溢出。溢出的部分会加到 timestamp 段上去。这样即使在时间戳精度范围内 sequence 耗尽了，也不用阻塞请求。Timestamp 类型持久化的是时间，保存的是当前的 timestamp + 提前量。这里的 timestamp 是包含 sequence 溢出的部分。Timestamp 类型的持久化是定时进行的。由于已持久化的时间戳总是大于当前时间的，因此等待持久化而造成的阻塞基本上是不会发生的。March 启动时，如果获取的当前时间大于保存的时间，就使用当前时间作为起点，否则就使用已保存的时间作为起点。每次请求获取时间时也是类似。如果发现获取的时间小于已经发过的 timestamp，就继续使用当前 timestamp。这样就确保了即使机器时间跳变时，发出的 id 也是单调增长的，绝对不会重复。同时由于允许溢出，也不会因为时间回跳而阻塞。当然这种方式带来的一个影响是，如果从获取的 id 里解析出时间，可能并不是准确的时间。由于切换或溢出，看到的时间可能会提前。不过本来也不应该依赖这些细节不是么。

高可用

March 的高可用是利用 etcd 的 ttl 和 watch 实现的。启动时，先尝试创建一个新的带 ttl 的 Node。如果成功，就成为了主节点；如果由于已存在而失败，就成为了备节点。

主节点
定时用前一次请求返回的 index 刷新 Node 的 ttl，保持自己的主节点角色。发现刷新失败时，说明主节点角色已经被抢走，从抢主节点过程重新开始。与此同时，还会等待 demote 请求。收到 demote 请求时，会等待新的主节点信息，然后将自己置为备节点。
备节点
先查询主节点的信息。在备节点收到发号请求时，会按 Redis Cluster 协议重定向到主节点。之后就开始 Watch Node 的变化。检测到变化后，也开始抢主节点过程。

这样，可以做到在主节点发生故障时，最多等待一个 ttl 就能检测到，并完成切换。而在主动切换时，结合客户端，可以做到完全无损，只有毫秒级的阻塞。

此外，每个节点都会存保存各自的带 ttl 的节点信息，同时定时刷新，用于返回给客户端集群信息。每个发号器在每次持久化时，也会携带上上一次持久化获得的 index。一旦不匹配出错，也会将自身重置为备节点。这可以避免网络堵塞或进程僵死造成原主失效而自身却不知道。在发生非预期错误时，HA goroutine 会等待 2 * ttl，以免不断出错造成死循环。此外，备节点也需要能够完成用户认证。但因为认证是不能重定向的，所以还需要检测 etcd 上的用户信息变化，重新同步用户数据。