微信序列号生成器架构设计及演变
1. 摘要
微信在立项之初，就已确立了利用数据版本号实现终端与后台的数据增量同步机制，确保发消息时消息可靠送达对方手机，避免了大量潜在的家庭纠纷。时至今日，微信已经走过第五个年头，这套同步机制仍然在消息收发、朋友圈通知、好友数据更新等需要数据同步的地方发挥着核心的作用。而在这同步机制的背后，需要一个高可用、高可靠的序列号生成器来产生同步数据用的版本号。这个序列号生成器我们称之为seqsvr，目前已经发展为一个每天万亿级调用的重量级系统，其中每次申请序列号平时调用耗时1ms，99.9%的调用耗时小于3ms，服务部署于数百台4核CPU服务器上。本文会重点介绍seqsvr的架构核心思想，以及seqsvr随着业务量快速上涨所做的架构演变。
2. 背景
微信服务器端为每一份需要与客户端同步的数据（例如消息）都会赋予一个唯一的、递增的序列号（后文称为sequence），作为这份数据的版本号。在客户端与服务器端同步的时候，客户端会带上已经同步下去数据的最大版本号，后台会根据客户端最大版本号与服务器端的最大版本号，计算出需要同步的增量数据，返回给客户端。这样不仅保证了客户端与服务器端的数据同步的可靠性，同时也大幅减少了同步时的冗余数据。
这里不用乐观锁机制来生成版本号，而是使用了一个独立的seqsvr来处理序列号操作，一方面因为业务有大量的sequence查询需求——查询已经分配出去的最后一个sequence，而基于seqsvr的查询操作可以做到非常轻量级，避免对存储层的大量IO查询操作；另一方面微信用户的不同种类的数据存在不同的Key-Value系统中，使用统一的序列号有助于避免重复开发，同时业务逻辑可以很方便地判断一个用户的各类数据是否有更新。
从seqsvr申请的、用作数据版本号的sequence，具有两种基本的性质：
- 递增的64位整型变量
- 每个用户都有自己独立的64位sequence空间
举个例子，小明当前申请的sequence为100，那么他下一次申请的sequence，可能为101，也可能是110，总之一定大于之前申请的100。而小红呢，她的sequence与小明的sequence是独立开的，假如她当前申请到的sequence为50，然后期间不管小明申请多少次sequence怎么折腾，都不会影响到她下一次申请到的值（很可能是51）。
这里用了每个用户独立的64位sequence的体系，而不是用一个全局的64位（或更高位）sequence，很大原因是全局唯一的sequence会有非常严重的申请互斥问题，不容易去实现一个高性能高可靠的架构。对微信业务来说，每个用户独立的64位sequence空间已经满足业务要求。
目前sequence用在终端与后台的数据同步外，同时也广泛用于微信后台逻辑层的基础数据一致性cache中，大幅减少逻辑层对存储层的访问。虽然一个用于终端——后台数据同步，一个用于后台cache的一致性保证，场景大不相同。但我们仔细分析就会发现，两个场景都是利用sequence可靠递增的性质来实现数据的一致性保证，这就要求我们的seqsvr保证分配出去的sequence是稳定递增的，一旦出现回退必然导致各种数据错乱、消息消失；另外，这两个场景都非常普遍，我们在使用微信的时候会不知不觉地对应到这两个场景：小明给小红发消息、小红拉黑小明、小明发一条失恋状态的朋友圈，一次简单的分手背后可能申请了无数次sequence。微信目前拥有数亿的活跃用户，每时每刻都会有海量sequence申请，这对seqsvr的设计也是个极大的挑战。那么，既要sequence可靠递增，又要能顶住海量的访问，要如何设计seqsvr的架构？我们先从seqsvr的架构原型说起。
3. 架构原型
不考虑seqsvr的具体架构的话，它应该是一个巨大的64位数组，而我们每一个微信用户，都在这个大数组里独占一格8bytes的空间，这个格子就放着用户已经分配出去的最后一个sequence：cur_seq。每个用户来申请sequence的时候，只需要将用户的cur_seq+=1，保存回数组，并返回给用户。
image.png
图1. 小明申请了一个sequence，返回101
3.1 预分配中间层
任何一件看起来很简单的事，在海量的访问量下都会变得不简单。前文提到，seqsvr需要保证分配出去的sequence递增（数据可靠），还需要满足海量的访问量（每天接近万亿级别的访问）。满足数据可靠的话，我们很容易想到把数据持久化到硬盘，但是按照目前每秒千万级的访问量（~10^7 QPS），基本没有任何硬盘系统能扛住。
后台架构设计很多时候是一门关于权衡的哲学，针对不同的场景去考虑能不能降低某方面的要求，以换取其它方面的提升。仔细考虑我们的需求，我们只要求递增，并没有要求连续，也就是说出现一大段跳跃是允许的（例如分配出的sequence序列：1,2,3,10,100,101）。于是我们实现了一个简单优雅的策略：
- 内存中储存最近一个分配出去的sequence：cur_seq，以及分配上限：max_seq
- 分配sequence时，将cur_seq++，同时与分配上限max_seq比较：如果cur_seq > max_seq，将分配上限提升一个步长max_seq += step，并持久化max_seq
- 重启时，读出持久化的max_seq，赋值给cur_seq
image.png
图2. 小明、小红、小白都各自申请了一个sequence，但只有小白的max_seq增加了步长100
这样通过增加一个预分配sequence的中间层，在保证sequence不回退的前提下，大幅地提升了分配sequence的性能。实际应用中每次提升的步长为10000，那么持久化的硬盘IO次数从之前~10^7 QPS降低到~10^3 QPS，处于可接受范围。在正常运作时分配出去的sequence是顺序递增的，只有在机器重启后，第一次分配的sequence会产生一个比较大的跳跃，跳跃大小取决于步长大小。
3.2 分号段共享存储
请求带来的硬盘IO问题解决了，可以支持服务平稳运行，但该模型还是存在一个问题：重启时要读取大量的max_seq数据加载到内存中。
我们可以简单计算下，以目前uid（用户唯一ID）上限2^32个、一个max_seq 8bytes的空间，数据大小一共为32GB，从硬盘加载需要不少时间。另一方面，出于数据可靠性的考虑，必然需要一个可靠存储系统来保存max_seq数据，重启时通过网络从该可靠存储系统加载数据。如果max_seq数据过大的话，会导致重启时在数据传输花费大量时间，造成一段时间不可服务。
为了解决这个问题，我们引入号段Section的概念，uid相邻的一段用户属于一个号段，而同个号段内的用户共享一个max_seq，这样大幅减少了max_seq数据的大小，同时也降低了IO次数。
image.png
图3. 小明、小红、小白属于同个Section，他们共用一个max_seq。在每个人都申请一个sequence的时候，只有小白突破了max_seq上限，需要更新max_seq并持久化
目前seqsvr一个Section包含10万个uid，max_seq数据只有300+KB，为我们实现从可靠存储系统读取max_seq数据重启打下基础。
3.3 工程实现
工程实现在上面两个策略上做了一些调整，主要是出于数据可靠性及灾难隔离考虑
- 把存储层和缓存中间层分成两个模块StoreSvr及AllocSvr。StoreSvr为存储层，利用了多机NRW策略来保证数据持久化后不丢失；AllocSvr则是缓存中间层，部署于多台机器，每台AllocSvr负责若干号段的sequence分配，分摊海量的sequence申请请求。
- 整个系统又按uid范围进行分Set，每个Set都是一个完整的、独立的StoreSvr+AllocSvr子系统。分Set设计目的是为了做灾难隔离，一个Set出现故障只会影响该Set内的用户，而不会影响到其它用户。
image.png
图4. 原型架构图
4. 容灾设计
接下来我们会介绍seqsvr的容灾架构。我们知道，后台系统绝大部分情况下并没有一种唯一的、完美的解决方案，同样的需求在不同的环境背景下甚至有可能演化出两种截然不同的架构。既然架构是多变的，那纯粹讲架构的意义并不是特别大，期间也会讲下seqsvr容灾设计时的一些思考和权衡，希望对大家有所帮助。
seqsvr的容灾模型在五年中进行过一次比较大的重构，提升了可用性、机器利用率等方面。其中不管是重构前还是重构后的架构，seqsvr一直遵循着两条架构设计原则：
- 保持自身架构简单
- 避免对外部模块的强依赖
这两点都是基于seqsvr可靠性考虑的，毕竟seqsvr是一个与整个微信服务端正常运行息息相关的模块。按照我们对这个世界的认识，系统的复杂度往往是跟可靠性成反比的，想得到一个可靠的系统一个关键点就是要把它做简单。相信大家身边都有一些这样的例子，设计方案里有很多高大上、复杂的东西，同时也总能看到他们在默默地填一些高大上的坑。当然简单的系统不意味着粗制滥造，我们要做的是理出最核心的点，然后在满足这些核心点的基础上，针对性地提出一个足够简单的解决方案。
那么，seqsvr最核心的点是什么呢？每个uid的sequence申请要递增不回退。这里我们发现，如果seqsvr满足这么一个约束：任意时刻任意uid有且仅有一台AllocSvr提供服务，就可以比较容易地实现sequence递增不回退的要求。
image.png
图5. 两台AllocSvr服务同个uid造成sequence回退。Client读取到的sequence序列为101、201、102
但也由于这个约束，多台AllocSvr同时服务同一个号段的多主机模型在这里就不适用了。我们只能采用单点服务的模式，当某台AllocSvr发生服务不可用时，将该机服务的uid段切换到其它机器来实现容灾。这里需要引入一个仲裁服务，探测AllocSvr的服务状态，决定每个uid段由哪台AllocSvr加载。出于可靠性的考虑，仲裁模块并不直接操作AllocSvr，而是将加载配置写到StoreSvr持久化，然后AllocSvr定期访问StoreSvr读取最新的加载配置，决定自己的加载状态。
image.png
图6. 号段迁移示意。通过更新加载配置把0~2号段从AllocSvrA迁移到AllocSvrB
同时，为了避免失联AllocSvr提供错误的服务，返回脏数据，AllocSvr需要跟StoreSvr保持租约。这个租约机制由以下两个条件组成：
- 租约失效：AllocSvr N秒内无法从StoreSvr读取加载配置时，AllocSvr停止服务
- 租约生效：AllocSvr读取到新的加载配置后，立即卸载需要卸载的号段，需要加载的新号段等待N秒后提供服务
image.png
图7. 租约机制。AllocSvrB严格保证在AllocSvrA停止服务后提供服务
这两个条件保证了切换时，新AllocSvr肯定在旧AllocSvr下线后才开始提供服务。但这种租约机制也会造成切换的号段存在小段时间的不可服务，不过由于微信后台逻辑层存在重试机制及异步重试队列，小段时间的不可服务是用户无感知的，而且出现租约失效、切换是小概率事件，整体上是可以接受的。
到此讲了AllocSvr容灾切换的基本原理，接下来会介绍整个seqsvr架构容灾架构的演变
5. 容灾1.0架构：主备容灾
最初版本的seqsvr采用了主机+冷备机容灾模式：全量的uid空间均匀分成N个Section，连续的若干个Section组成了一个Set，每个Set都有一主一备两台AllocSvr。正常情况下只有主机提供服务；在主机出故障时，仲裁服务切换主备，原来的主机下线变成备机，原备机变成主机后加载uid号段提供服务。
image.png
图8. 容灾1.0架构：主备容灾
可能看到前文的叙述，有些同学已经想到这种容灾架构。一主机一备机的模型设计简单，并且具有不错的可用性——毕竟主备两台机器同时不可用的概率极低，相信很多后台系统也采用了类似的容灾策略。
5.1 设计权衡
主备容灾存在一些明显的缺陷，比如备机闲置导致有一半的空闲机器；比如主备切换的时候，备机在瞬间要接受主机所有的请求，容易导致备机过载。既然一主一备容灾存在这样的问题，为什么一开始还要采用这种容灾模型？事实上，架构的选择往往跟当时的背景有关，seqsvr诞生于微信发展初期，也正是微信快速扩张的时候，选择一主一备容灾模型是出于以下的考虑：
- 架构简单，可以快速开发
- 机器数少，机器冗余不是主要问题
- Client端更新AllocSvr的路由状态很容易实现
前两点好懂，人力、机器都不如时间宝贵。而第三点比较有意思，下面展开讲下
微信后台绝大部分模块使用了一个自研的RPC框架，seqsvr也不例外。在这个RPC框架里，调用端读取本地机器的client配置文件，决定去哪台服务端调用。这种模型对于无状态的服务端，是很好用的，也很方便实现容灾。我们可以在client配置文件里面写“对于号段x，可以去SvrA、SvrB、SvrC三台机器的任意一台访问”，实现三主机容灾。
但在seqsvr里，AllocSvr是预分配中间层，并不是无状态的。而前面我们提到，AllocSvr加载哪些uid号段，是由保存在StoreSvr的加载配置决定的。那么这时候就尴尬了，业务想要申请某个uid的sequence，Client端其实并不清楚具体去哪台AllocSvr访问，client配置文件只会跟它说“AllocSvrA、AllocSvrB…这堆机器的某一台会有你想要的sequence”。换句话讲，原来负责提供服务的AllocSvrA故障，仲裁服务决定由AllocSvrC来替代AllocSvrA提供服务，Client要如何获知这个路由信息的变更？
这时候假如我们的AllocSvr采用了主备容灾模型的话，事情就变得简单多了。我们可以在client配置文件里写：对于某个uid号段，要么是AllocSvrA加载，要么是AllocSvrB加载。Client端发起请求时，尽管Client端并不清楚AllocSvrA和AllocSvrB哪一台真正加载了目标uid号段，但是Client端可以先尝试给其中任意一台AllocSvr发请求，就算这次请求了错误的AllocSvr，那么就知道另外一台是正确的AllocSvr，再发起一次请求即可。
也就是说，对于主备容灾模型，最多也只会浪费一次的试探请求来确定AllocSvr的服务状态，额外消耗少，编码也简单。可是，如果Svr端采用了其它复杂的容灾策略，那么基于静态配置的框架就很难去确定Svr端的服务状态：Svr发生状态变更，Client端无法确定应该向哪台Svr发起请求。这也是为什么一开始选择了主备容灾的原因之一。
5.2 主备容灾的缺陷
在我们的实际运营中，容灾1.0架构存在两个重大的不足：
- 扩容、缩容非常麻烦
- 一个Set的主备机都过载，无法使用其他Set的机器进行容灾
在主备容灾中，Client和AllocSvr需要使用完全一致的配置文件。变更这个配置文件的时候，由于无法实现在同一时间更新给所有的Client和AllocSvr，因此需要非常复杂的人工操作来保证变更的正确性（包括需要使用iptables来做请求转发，具体的详情这里不做展开）。
对于第二个问题，常见的方法是用一致性Hash算法替代主备，一个Set有多台机器，过载机器的请求被分摊到多台机器，容灾效果会更好。在seqsvr中使用类似一致性Hash的容灾策略也是可行的，只要Client端与仲裁服务都使用完全一样的一致性Hash算法，这样Client端可以启发式地去尝试，直到找到正确的AllocSvr。例如对于某个uid，仲裁服务会优先把它分配到AllocSvrA，如果AllocSvrA挂掉则分配到AllocSvrB，再不行分配到AllocSvrC。那么Client在访问AllocSvr时，按照AllocSvrA -> AllocSvrB -> AllocSvrC的顺序去访问，也能实现容灾的目的。但这种方法仍然没有克服前面主备容灾面临的配置文件变更的问题，运营起来也很麻烦。
6. 容灾2.0架构：嵌入式路由表容灾
最后我们另辟蹊径，采用了一种不同的思路：既然Client端与AllocSvr存在路由状态不一致的问题，那么让AllocSvr把当前的路由状态传递给Client端，打破之前只能根据本地Client配置文件做路由决策的限制，从根本上解决这个问题。
所以在2.0架构中，我们把AllocSvr的路由状态嵌入到Client请求sequence的响应包中，在不带来额外的资源消耗的情况下，实现了Client端与AllocSvr之间的路由状态一致。具体实现方案如下：
seqsvr所有模块使用了统一的路由表，描述了uid号段到AllocSvr的全映射。这份路由表由仲裁服务根据AllocSvr的服务状态生成，写到StoreSvr中，由AllocSvr当作租约读出，最后在业务返回包里旁路给Client端。
image.png
图9. 容灾2.0架构：动态号段迁移容灾
把路由表嵌入到请求响应包看似很简单的架构变动，却是整个seqsvr容灾架构的技术奇点。利用它解决了路由状态不一致的问题后，可以实现一些以前不容易实现的特性。例如灵活的容灾策略，让所有机器都互为备机，在机器故障时，把故障机上的号段均匀地迁移到其它可用的AllocSvr上；还可以根据AllocSvr的负载情况，进行负载均衡，有效缓解AllocSvr请求不均的问题，大幅提升机器使用率。
另外在运营上也得到了大幅简化。之前对机器进行运维操作有着繁杂的操作步骤，而新架构只需要更新路由即可轻松实现上线、下线、替换机器，不需要关心配置文件不一致的问题，避免了一些由于人工误操作引发的故障。
image.png
图10. 机器故障号段迁移
6.1 路由同步优化
把路由表嵌入到取sequence的请求响应包中，那么会引入一个类似“先有鸡还是先有蛋”的哲学命题：没有路由表，怎么知道去哪台AllocSvr取路由表？另外，取sequence是一个超高频的请求，如何避免嵌入路由表带来的带宽消耗？
这里通过在Client端内存缓存路由表以及路由版本号来解决，请求步骤如下：
- Client根据本地共享内存缓存的路由表，选择对应的AllocSvr；如果路由表不存在，随机选择一台AllocSvr
- 对选中的AllocSvr发起请求，请求带上本地路由表的版本号
- AllocSvr收到请求，除了处理sequence逻辑外，判断Client带上版本号是否最新，如果是旧版则在响应包中附上最新的路由表
- Client收到响应包，除了处理sequence逻辑外，判断响应包是否带有新路由表。如果有，更新本地路由表，并决策是否返回第1步重试
基于以上的请求步骤，在本地路由表失效的时候，使用少量的重试便可以拉到正确的路由，正常提供服务。
7. 总结
到此把seqsvr的架构设计和演变基本讲完了，正是如此简单优雅的模型，为微信的其它模块提供了一种简单可靠的一致性解决方案，支撑着微信五年来的高速发展，相信在可预见的未来仍然会发挥着重要的作用。
