如何做一个靠谱的发号器

为什么需要一个发号器

在使用数据库时,表的主键经常会使用数据库的自增(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 上的用户信息变化,重新同步用户数据。

小结

发号器看起来简单,但是要实现一个靠谱的,易用的,要考虑到的地方还是很多的。其实很多东西都是这样。我们还做了更多。为了更容易接入落地,我们在数据库中间件中也做了集成。配置后,执行 insert 时,会自动代入配置的自增字段和 id 值,让业务方完全无痛。

知识共享许可协议
如无特殊说明,本文版权归 本文作者及有赞技术团队 所有,采用 署名-非商业性使用 4.0 国际许可协议 进行许可。
转载请注明:来自有赞技术团队博客 http://tech.youzan.com/id_generator/

欢迎关注有赞技术团队微信公众账号
了解更多,保持联系