谈谈陌陌争霸在数据库方面踩过的坑(排行榜篇)
为什么大部分网络服务都需要一个数据库在后台支撑整个系统？
这通常是因为大部分系统的一个运行周期都很短，对于传统的网站服务来说，从收到一个 HTTP 请求开始，到终端用户收到这个请求的结果为止，就是一个运行周期。而其间可能处理的数据集是很大的，通常没有时间（甚至没有空间）把所有数据都加载到内存，处理其中涉及的一小部分，然后保存在磁盘上再退出。
当数据量巨大时，任何对数据的操作的算法和数据结构都需要精心设计，这不是随便一个程序员就可以轻松完成的任务。尤其是数据量大到超过内存容量时，很多算法和数据结构对大部分非此领域的程序员来说都是陌生的。本着专业的事情交给专业的人来做的原则，一般系统都会把这部分工作交给独立的数据库来完成。
对数据的操作只有抽象的足够简单，系统才能健壮，这便有了 SQL 语言做一层抽象，让数据管理的工作可以独立出来。甚至于你想牺牲一部分的特性来提高性能，还可以选用近年来流行的各种 NOSQL 数据库。
可在 MMO 游戏服务器领域，事情发生了一点点变化。
数据和业务逻辑是密切相关的，改变非常频繁。MMO 服务器需要持续快速的响应用户的请求。我们几乎不可能把一切数据都放在独立的数据库中，比如玩家在虚拟世界中的位置，以及他所影响的其他玩家的列表；玩家战斗时的各种属性变化，还有和玩家互动的那些 NPC 的状态改变……
最大的矛盾是：MMO 游戏中数据集的改变不再是简单的 SQL 可以表达的东西，不可能交给数据库服务期内部完成。无论什么类型的数据库，都不是为这种应用设计的。如果你硬要套用其它领域的应用模式的话，游戏服务器只能频繁的把各种数据从数据库中读出来，按游戏逻辑做出改变，再写回去。数据库变成了一个很低效的数据中转中心，无论你是否使用内存数据库，都改变不了这个低效的本质。
我听过无数从别的领域转行到游戏领域做开发的程序员设计出来的糟糕系统。他们最终仅仅把数据库当成一个可靠的数据储存点和中转点，认为把所谓重要的数据写进数据库就万事大吉，然后再别扭的从另一个位置把数据从数据库读出来使用。系统中充满了对数据库的奇怪异步回调用来改善系统的反应速度，而系统却始终步履阑珊。能做对已经是极限了，更何况游戏系统不仅仅是输入输出正确就是正确，如果超过了应用的响应时间，一切都是不正确的。
为了让系统健壮，构架师在构架系统时，一定会把系统隔离成不同的模块，并尽量简化模块间的沟通规则。这样你可以单独校验每个模块的质量，必要的时候可以更换。几乎没有人会因为效率或开发方便等原因而把应用代码写到 OS 内核中去跑就是这个道理。
每个模块只对输入它的数据负责，保证输出的正确。通常测试也只对这个正确性负责。同学们最容易忽略的一点是，每个模块都对它输入数据的处理速度有一个上限，也就是它的吞吐量。
一旦输入速度大于处理速度，模块实现的再正确也是白搭。因为永远都不会有输出了。
对于大部分模块，只要内存管够，这都不是问题。实际运作的系统中很少有持续大数据量的输入的，从一个较长的时间看，总的数据输入是小于处理能力的，暂时没能处理的数据堆积在内存就行了。
凡事都有例外。一个健壮的系统都需要对例外做处理。一个工作在 server 模式的数据库是这样解决这个例外的：它会支持查询连接的并发，并发的查询相互间对计算资源的占用是公平的，相互不影响（至少是设计上的理想）。而操作系统或数据库本身会限制并发的连接数，一旦达到最高连接数，系统会拒绝服务；这样就把超过处理能力的输入挡在了模块外面。按这种设计，就不会有输入（只要能抵达）永远没有回应了。
可惜，这样做的代价是，你必须在模块间加入请求失败的处理。一个设计不谨慎的系统最容易在错误处理上栽跟头。他们总是期望任何一个模块都能正确处理上级的请求。
btw, 为什么 12306 的订票系统在高负载的情况下完全不可用？就是这点没处理好。我指的是，一个实现正确的系统，一定不会连网页的刷不出来，不给用户正确的提示，哪怕只是错误提示；也不应该在高负载下，有效处理能力急剧下降。我指的是，一旦用户能进入正常流程，就应该顺利把至少一个环节顺利完成，而不是突然就卡在那里没有任何回应。
快跑题了。我谈到这点，其实是想表达，说的容易，做起来是很难的。下一篇我会写到我们在过年前出的一个事故和这个就有一些关系。
八卦时间：
陌陌劲舞团是陌陌游戏平台上线的第 2 款游戏。我们的陌陌争霸还在开发的时候，这款游戏就打算上线了。我对这个产品有限的了解都是道听途说，所以如果有更清楚内情的同学发现说的不对，也请谅解。对于技术问题，我想八卦的真相就并不那么重要了，有则改之，无则嘉勉。
劲舞团这个品牌原本是属于韩国人的，但这款游戏在国内曾经异常火爆，在国内代理它的久游也就买下来 IP ，自己制作手机版。据我所知，陌陌劲舞团完全是在上海开发的，没韩国人什么事。
这是个比较简单的游戏，至少服务器部分很简单，也就是统计下分数，查查排名，以及解决一下收费问题而已。刨掉这些部分，它就是个单机游戏，根本不需要服务器。
因为劲舞团的品牌名气，以及陌陌巨大的用户群，游戏一上线就在 ios 免费榜飚上去了。如果不是企鹅公司看不顺眼，立刻上线了节奏大师，估计还会在榜单上更火一些。事后证明节奏大师的上线也很仓促，完全是为了打击竞争对手抢着上的，因为后者的服务器也不稳定，很快就挂掉了，完全不像一个大公司应有的质量。
陌陌劲舞团顺利拉来了用户后，第一天服务器就出了状况，重启了几次后完全不解决问题。所以决定停服休整。一停就是三天。当时我就纳闷了，哪有修个小 bug 预计要三天的？这肯定是有结构性问题了。当时我们的项目按计划也就最后半个月的时间了，本来陌陌的人督的我们很紧的，一下子人全飞去了上海。
一周后陌陌劲舞团才重新上线，远超过当初预计的 3 天。事情一解决，陌陌的技术班底，从 CTO 到下面大多数人，全部飞到广州和我们开会，让我们重视服务器稳定性问题。会议内容主要是强调陌陌平台初期导入用户瞬间爆发量巨大，以及了解一下我们的设计细节确保没有大的问题。我所了解到的八卦就是在这段时间听来的。
陌陌劲舞团使用的是 MongoDB 。似乎这玩意很受游戏开发者喜爱。我想主要是因为用起来简单直接吧。游戏从业者如果之前没有别的领域的开发经验，对数据库这东西一知半解的人居多。尤其是从客户端开发过来的人，他们通常的习惯就是看 API 文档，了解怎么用看起来正确就够了。然后上线测试一下，好像也对，工作似乎就结束了。就算有压力测试，也很难做到和生产环境一致。
上线前，据说双方沟通过。陌陌方想确认系统能不能横向扩展，得到的答复是可以：加硬件即可。我想陌陌劲舞团开发方的思路是这样的：我们的服务器系统很简单，不都是过一下数据库么？MongoDB 是被很多人验证过的，不会在这么简单的业务中出问题吧。至于负载，不是还有 mongos 么？放心啦，没事的。
最终的直接问题出在排行榜上。当有两万人在线时（没错，才两万人而已），大量用户的排行榜查询阻塞了数据库。导致不仅仅是排行榜刷不出来，连冲值业务也受到了影响。土豪们充不进去钱，谈什么玩游戏啊。最终产生了雪崩，整个数据库都不正常使得游戏系统工作不起来。
为啥用了这么长时间才修好这个 bug ？
负责陌陌劲舞团的服务器开发的人在项目做完就离职了。想想一个设计有问题的系统交给非设计者维护有多糟糕吧？任何清醒的程序员都知道，这个时候即使是重写也比改问题简单。陌陌的同学做了个正确的决定，直接派自己的人驻留在上海，把服务器重新写了一遍。
陌陌的技术背景是 Redis 的，他们的系统用 redis 构建，所以重写就用了 redis 取代 mongodb 。写到这里，我完全没有 redis 和 mongodb 谁好谁差的意思。关键在人，你对什么熟悉就用什么，哪种数据库都能对付这点小业务，关键看你能不能用对。
Redis 里正好有一个有序集(Sorted Set) 的数据结构，你用 ZADD 插入完数据后，它就天然有序了。这个插入是 O( M * log(N)) 的时间复杂度，基本可以满足需求。而用 ZRANGE 查询榜单仅需 O(log(N)+M) 的时间复杂度。
那么使用 Redis ，利用 sorted set 做排行榜系统是我们的唯一选择么？绝对不是。我们也不可能为了这个特性必须选择 redis 做数据库。但这个例子可以说明：如果数据库提供内在的特性可以对数据集做一些操作，我们就直接用，但需要了解这种操作的性能。它需要和整个系统对它的性能期望匹配。
陌陌劲舞团使用 mongodb 内置的排序功能去做排行榜本也不是大问题。或许仅仅只是实现的人对 mongo 不熟悉造成的性能低下。这些随着系统重建已经无法深究了。但核心问题是，仅仅一个排行榜系统的错误实现为何会影响整个系统的稳定性？
下面就是我的猜测了：
许多程序员为了提高数据库的吞吐量，并不是一个事务就给数据库建一个连接，用完就关掉的。因为新建 TCP 连接是个开销较大的操作。维持太多连接对系统也是一个开销。同学们喜欢做一个叫做连接池的东西，在系统其它部分和数据库对接的地方走这个连接池。只要一个旧有连接没有断开，就一直把对数据库的请求通过固定连接发给数据库，等待返回。
在数据库的吞吐量满足系统需求的时候，这个模块很容易实现正确。但一旦超出需求，连接池上的数据就会越积越多，数据库查询越来越慢。而调用数据库的模块却不觉得这是问题。
正确的行为应该是让连接池快速反馈，断开并扔掉不可能处理完的请求，让请求方把这个不能处理的错误反馈到上个环节，直到流量被限制在合理的范围内。整个系统才能不至于崩溃。当错误被迫反馈到玩家那里时，他顶多看到的是查询失败，而不太会影响到别的功能。
陌陌争霸怎样做排行榜的？
在上一篇里就有同学问道，如果你们不用数据库，怎么做排行榜呢？ 其实我在上一篇正文里就有解答：
“服务器只是在不断的创造新数据并让这些数据在内存中流通而已，它没有任何需要从外部读取数据。如果内存无限大，且服务器永远不会当机，数据库这个设施没有存在的必要。”
排行榜单也是数据之一，游戏服务器开服一刻起，没有任何玩家有排名信息。随着玩家名次更替，榜单才逐步形成。我们只需要在玩家分数变化的时候同步榜单的变化即可。而玩家查询仅仅是取走有序的榜单而已。
你看，这个过程和数据库无关不是？需要设计的是调整榜单的算法，和榜单的数据结构以保证维持榜单的性能足够强就好了。因为玩家名词更替的频率远小于玩家网络包的频率，那么这个模块的处理能力所需要的下限很容易满足。我们不用考虑处理不过来的情况。
针对陌陌争霸我们是这样做的：
陌陌争霸中用于排名的分数区间不大，也就是 0 分到 5000 分。而参与排名的人数众多，数以百万计。对百万用户做插入排序，每个插入即使是 O(N) 的也不可接受。可事实是大量玩家的分数相同，都是并列排名的。所以我们只需要做 5000 个桶，每个桶里仅记录这个分数有多少个人就可以了。
当玩家分数变迁，把原来的桶减一，新的桶加一。这个操作就是 O(1) 的。
而排行榜的查询仅需要把当前分数靠前的桶累加，就能获知查询者的名次。对于上百万玩家，看到哪些人和你并列的人的名字是没有意义的。这个查询虽然是 O(n) 复杂度，但 n 只有区区 5000 ，还可以做 cache 以应对查询频率远高于更新频率的情况。
真正需要精确知道人名的是榜单的前 200 个人，而对前 200 个人做插入排序也很快，所以并不会造成性能问题。
我们在系统的单点做排行榜的维持，完全没有外部数据库操作，它只是一小段操作普通内存结构的 c 代码。而这个单点远远成为不了整个系统的热点。
我们在系统临时退出时，把已经排好的榜单落地，下次启动的时候恢复。但也不必完全信任落地的数据，可以用离线脚本检索整个数据库重新生成一份正确的榜单。所以数据库中的榜单只是被 cache 起来而已，系统运行期间是不需要写入数据库的，也不用担心数据丢失。
好吧，还是没谈到我们自己踩的坑，就又到了吃饭时间 :( 。明天我将写写陌陌争霸在运营期间遇到的第一起数据库事故，它和 mongos 有关。同时也会谈谈我们在代理狂刃期间帮狂刃填的一些和 mongodb 有关的坑。
Comments
Posted by: lx | (33) July 27, 2017 09:02 PM
Posted by: Anonymous | (32) May 29, 2015 10:49 AM
Posted by: bombless | (31) February 12, 2015 01:58 AM
Posted by: york | (30) February 11, 2015 03:23 PM
Posted by: steve | (29) June 4, 2014 02:57 PM
Posted by: 英式没品笑话百科 | (28) April 18, 2014 02:51 PM
Posted by: joneechu | (27) March 25, 2014 03:15 PM
Posted by: davis.lee | (26) March 24, 2014 07:32 PM
Posted by: more | (25) March 21, 2014 09:24 AM
Posted by: wuspring | (24) March 14, 2014 08:44 AM
Posted by: wuspring | (23) March 14, 2014 08:44 AM
Posted by: 卡卡西0旗木 | (22) March 4, 2014 10:14 PM
Posted by: 卡卡西0旗木 | (21) March 4, 2014 10:14 PM
Posted by: 卡卡西0旗木 | (20) March 4, 2014 10:14 PM
Posted by: 卡卡西0旗木 | (19) March 4, 2014 10:14 PM
Posted by: hi | (18) March 4, 2014 05:27 PM
Posted by: Anonymous | (17) March 4, 2014 10:06 AM
Posted by: yzy | (16) March 4, 2014 12:47 AM
Posted by: 西风 | (15) March 3, 2014 08:25 PM
Posted by: Saber_fans | (14) March 3, 2014 02:43 PM
Posted by: lite3 | (13) March 3, 2014 02:13 PM
Posted by: Liigo | (12) March 3, 2014 01:52 PM
Posted by: wesom | (11) March 2, 2014 10:25 PM
Posted by: hangcom | (10) March 2, 2014 09:54 PM
Posted by: 黄牛 | (9) March 2, 2014 09:32 PM
Posted by: 纳米黑客 | (8) March 2, 2014 06:54 PM
Posted by: 聪聪 | (7) March 2, 2014 05:40 PM
Posted by: billow | (6) March 2, 2014 04:18 PM
Posted by: Anonymous | (5) March 2, 2014 03:43 PM
Posted by: 云南 | (4) March 2, 2014 03:30 PM
Posted by: Cloud | (3) March 2, 2014 02:59 PM
Posted by: toanso | (2) March 2, 2014 02:38 PM
Posted by: pi1ot | (1) March 2, 2014 02:36 PM