第 28 章
把会话分出去
每秒 13,900 条消息,一台消息服务器、一个计数器表已经扛不住。拆成几台以后,徒步群的下一个 seq 由谁来给?
这一章是初稿:作者还在逐章校对,内容和数字可能会改。
到了 v3,每天 1,000 万人用,晚上的高峰每秒 13,900 条消息,全都要经过消息层:去重(第 4 章)、取 seq(第 5 章)、存下、回 ACK。
第 5 章取 seq 的办法,是在写入的同一个事务里给会话的计数器加一。加上第 11 章同一个事务里记的那行待办(第 11 章:先记一行“待办”,后台再照着它去改每个成员的会话记录),一条消息要写三行(消息、计数器、待办):
13,900 × 3 = 每秒 41,700 行,是一台存储每秒 20,000 行的 2.1 倍
消息服务器也一样。假设一台每秒能处理 5,000 条(这是本章的假设),高峰要 3 台,再多 1 台备着坏,就是 4 台。存储也得分成几片,这一章先不管它怎么分。
拆成 4 台以后,徒步群的下一个 seq 由谁来给? 第 5 章的保证要留住:一个会话里的 seq 连续、不重、不往回走。
1. 第一个答案:哪台都行,锁留在存储里
最省事的拆法:消息服务器不存任何状态,前面放一个负载均衡,哪台闲就给哪台。存储按会话分成几片,徒步群的计数器和消息在同一片上。取 seq 仍然是第 5 章那个事务:给计数器那一行加锁、加一、写消息、提交。
这样是对的。计数器只有一个,锁在存储里,4 台服务器谁来写都要排队拿锁,seq 照样连续。存储健康时,这个办法完全够用。
它的代价藏在“排队拿锁”里:一个会话同一时刻只能有一个事务。存储写一次 5 毫秒,一个会话每秒最多 200 条;存储生病、写一次 500 毫秒(第 36 章的假设),就只剩每秒 2 条。这两个数第 5 章算过。
另外两件小事:去重去重dedup同一个消息 ID 再来一次时,返回第一次的结果,不再存一份。网络只能做到“至少送到一次”,去重让每条消息只显示一次。在术语表里查看要的“最近的消息 ID”(第 4 章)不在任何一台服务器的内存里,得放进一个共享的缓存,每条消息多一次往返;同一个会话的两条消息由两台服务器推出去,到手机上可能乱序:手机先收到 8 号、没收到 7 号,就按第 5 章先等 0.5 秒,7 号还没来,再去补拉。
2. 看它坏掉:存储慢下来的 30 秒
存储生病 30 秒,每次写入 500 毫秒。徒步群正热闹,每秒 5 条(假设)。
- 锁在存储里:一个会话一次只能写一条,每秒 2 条。30 秒里来了 150 条,只存下 60 条,还有 90 条在排队。最后一条是第 150 条,第 30 秒到,要排到第 75 秒才写进去,等了 45 秒。150 条里有 148 条等过了第 3 章 1 秒的首次超时,手机开始重发,存储更忙。
- 如果这个会话的消息都在同一台服务器上:它可以把排队的几条攒成一批,一次写进去。500 毫秒一批,每批约 2.5 条,最长等 0.9 秒,没有一条超过 1 秒。
攒成一批的前提,是同一个会话的消息都到同一台服务器。负载均衡随便分,它们散在 4 台上,攒不到一起。
3. 每个会话一个主人
所以换一种分法:每个会话指定一台消息服务器当它的主人,这个会话的消息只由它处理。这就是按会话分片按会话分片sharding by conversation每个会话固定由一台消息服务负责。这样一个会话的序号只由一个人分配,顺序才有保证。在术语表里查看。
主人在内存里记着这个会话的两样东西:
- 计数器:下一条就是计数器加一,不用去存储里加锁。
- 最近的消息 ID:去重在自己内存里查。第 4 章说过,v3 高峰 32 秒内约 44 万个 ID,要分在几台消息服务器上:4 台各约 11 万个、3.5 MB。
一条消息到了主人这里:查重,给 seq,和同一个会话里正在排队的几条一起写进存储,写好了回 ACK(第 3 章的“存好才回”不变),再按 seq 的顺序推出去。一个会话同一时刻只有一批在写,这一批提交了才写下一批,所以 seq 的先后仍是提交的先后(第 5 章)。
计数器那一行不再写,每条消息从三行变成两行。要查一个会话最新的 seq(第 6 章的缓存里没有时),就查消息表里它最大的 seq,(会话, seq)的唯一键正好当索引用。
主人给了号、写入却失败了,这个号就空着,不再拿来给别的消息:那次写入可能其实成功了,只是回复丢了。真没写进去的,手机来补拉,服务端回答“6 号不存在”。第 5 章预告过这件事。
4. 谁当主人:取模,还是哈希环
网关收到 Ana 发往徒步群的消息,要算出主人是谁。最直接的算法是取模:会话 ID 算个哈希,除以服务器台数取余数。4 台时余数是 0 到 3,正好对上。
用户涨了,加第 5 台。除数从 4 变成 5,几乎每个会话的余数都变了:
取模:4 台变 5 台,80% 的会话换了主人
为什么是 80%:哈希值按 20 个一轮看,除以 4 和除以 5 余数相同的,只有 0、1、2、3 这 4 个,五分之一;其余五分之四都换了主人。
换主人不是免费的:新主人要读一次这个会话最后的 seq,内存里的消息 ID 也得重新攒。80% 的会话同时换,等于整个消息层重启一遍。一台坏了、4 台变 3 台,也有 75% 要挪。
一致性哈希(Karger 等,1997)把哈希值排成一个环。每台服务器在环上占一些点,会话的哈希落在环上,顺时针遇到的第一个点属于谁,谁就是主人。加一台服务器,它只从别人手里接过落在自己点前面的那一段:
哈希环:4 台变 5 台,模拟 10 万个会话,挪了 18.1%(理论上是 1/5);一台坏了,只挪它自己的 24.7%
每台只占一个点,环上的段长短不一,最忙的一台分到平均的 1.43 倍;每台占 100 个点,最忙的只有 1.08 倍。
环本身记在一个协调服务里(etcd、ZooKeeper 这一类),每台网关都存一份,自己算出主人。
5. 交接:同一时刻只能有一个主人
最危险的是两个主人同时在。比如主人 A 卡住了几秒,大家以为它挂了,把徒步群交给 B。B 读到最后的 seq 是 4,823,给下一条 4,824;这时 A 醒过来,也给手上的一条 4,824。同一个号给了两条消息。
微信的序列号服务遇到过同样的问题,它的做法是“任意时刻任意 uid 有且仅有一台 AllocSvr 提供服务”,靠的是租约(一份有期限的授权:持有者到期前不续,它就自动作废,别人可以接手;InfoQ, 2016):一台 AllocSvr N 秒内拿不到最新的分配,就自己停止服务;新分到的一段用户(号段),等 N 秒后才开始服务。
我们用同一个道理,N 取 10 秒(假设)。主人每隔几秒向协调服务续一次约,N 秒续不上,就自己停止给号;协调服务 N 秒没收到它的续约,才把它的会话交给别人。旧主人的 N 秒从它发出续约时算起,比协调服务的早。比如旧主人 10:00:00 发出最后一次续约,协调服务 10:00:00.1 收到;旧主人 10:00:10 自己停手,协调服务要到 10:00:10.1 才把会话交给新主人。所以新主人开工时,旧主人已经停了。
交接分两种:
- 计划内(加机器、发布):旧主人先停止接这个会话的新消息,把手上的写完,再放手。新主人在下一条消息到来时读一次最后的 seq,约 5 毫秒。网关手上的环要是还没更新,把消息送到了旧主人那里,旧主人不收,网关重查一次环。
- 意外(机器挂了):只能等租约过期。高峰时一台挂掉,它那四分之一的会话最多停 10 秒:13,900 × 25% × 10 秒,约 34,750 条消息被耽误,手机按第 3 章重发,最后都会存下。
时钟会漂,进程会卡,旧主人停下之前发出去的写入也可能很晚才落地。所以最后还有两道唯一键,都在存储里:
- (会话, seq)(第 5 章):万一两条消息都写成 4,824,第二次写入被拒绝。主人重读最后的 seq;那条消息没有 ACK,手机重发,拿到新的号。
- (发送者, 消息 ID)(第 4 章):新主人内存里的消息 ID 是空的,交接前后的重发它认不出;写入时撞上这个唯一键,就查出原来那条,回同样的 ACK。
6. 算一下
- 存储写入:每条消息从三行变成两行,高峰每秒 27,800 行,仍是一台存储的 1.4 倍。存储也要分片,这一章没有省掉它,只是不再在存储里排队拿锁。
- 挪动:加一台,取模挪 80%,哈希环挪约 20%。
- 意外交接:一台挂了,约 34,750 条消息晚到最多 10 秒。
7. 代价
- 消息层有了状态。 以前消息服务器随便重启;现在重启就要交接,发布要一台一台来(第 35 章)。
- 多一个协调服务。 环和租约都在它那里,它自己也要高可用。
- 一个热闹的会话只能在一台上。 500 人的群没问题;上万人的群、直播间,一台扛不住时是另一套办法(第 40、41 章)。
- seq 可能有空号。 写入失败的号不再使用,手机要接受“这个号不存在”。
8. 其他答案
- 锁留在存储里(第 1 节)。没有交接、没有协调服务,存储健康时够用。
- 微信的 seqsvr(InfoQ, 2016)。它给每个用户发号,“只要求递增,并没有要求连续”:内存里记当前号 cur_seq 和上限 max_seq,用到上限才把上限加一个步长、写一次盘,步长 10000,写盘从每秒约千万次降到约千次;重启时从上限接着发,号会跳一大段。主人不按哈希环定,而由一个仲裁服务把一段段用户分给各台机器。
- Slack 的频道服务器:“每台 CS 按一致性哈希分到一部分频道”,一台坏了,替补“不到 20 秒”就能接手(Slack Engineering, 2023)。
- Discord:“Discord 是靠一致性哈希做成的分布式系统”,用一个环来查某个对象在哪个节点上(Discord, 2017)。
- Telegram 的两种编号(第 6 章提过):Telegram 的公开 API 里,私聊和普通群的消息 ID 按账号编,一个账号的所有私聊和普通群共用一个序列,所以同一条消息在两个人那里 ID 不同;频道和超级群各有自己的序列,谁看到的 ID 都一样(Telegram API:updates)。前一种像微信的 seqsvr 按用户发号,后一种像这一章按会话。服务端由谁发号,它没有公开。
9. 这一章的决定
主人现在要等存储写好才回 ACK。遇到真正的洪峰,比如跨年那一分钟,消息是全天平均的十倍,存储还是跟不上。下一章:存储前的队列。
评论
评论存在 GitHub Discussions,需要 GitHub 账号。