为什么需要一个发号器
在使用数据库时，表的主键经常会使用数据库的自增（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 值，让业务方完全无痛。
