« 谈谈陌陌争霸在数据库方面踩过的坑(前篇) | 返回首页 | 谈谈陌陌争霸在数据库方面踩过的坑(芒果篇) »

谈谈陌陌争霸在数据库方面踩过的坑(排行榜篇)

为什么大部分网络服务都需要一个数据库在后台支撑整个系统?

这通常是因为大部分系统的一个运行周期都很短,对于传统的网站服务来说,从收到一个 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

虽然redis的sorted set有天然算法可用,但其缺陷在于,对于相同分数的排名是以字典排序,但通常榜单都是要以时间序来排的,这个云风有考虑过怎么处理吗?

我晕,一个榜单而已,mysql搞一下就够了吧。

一分一个桶的方法确实不错,学习了。说起劲舞团,当时项目组确实对MongoDB了解不深,过于依赖数据库了,主要数据是用户信息变更、歌曲分数记录、还有日志,排行榜其实是经过设计的,当时采用的是类似一分一个桶的一段一个桶,排行榜不能算是系统性能最大的问题,后来跟陌陌一起改成redis了。

感慨啊,程序猿们本来都是学过算法和数据结构的,但工作用过几年数据库之后,竟然忘记了自己还会算法和数据结构!真是学会用榔头,到处都是钉子!从某种意义上说,数据库也不过是一种数据结构,如果这种数据结构不适合你的程序,就选用合适的数据结构即可,没必要非抱着数据库不放。

学习了一个很不错的排行方式。谢谢风云老师。

这个排行榜处理方式太好了,解决了大数据量的排行榜问题,谢谢云风

这个排行榜算法真的很不错,学习了!

深受启发~~~

#19 哪只眼睛看到云风说哪个数据库不好……说的是不同的人对数据库熟悉情况不同,不熟悉数据库的人用不出数据库的性能
#20-#22 当玩家分数变迁,把原来的桶减一,新的桶加一。不管是增加还是减少,有区别么

#19 哪只眼睛看到云风说哪个数据库不好……说的是不同的人对数据库熟悉情况不同,不熟悉数据库的人用不出数据库的性能
#20-#22 当玩家分数变迁,把原来的桶减一,新的桶加一。不管是增加还是减少,有区别么

请问分数是会减少的吗,这种做法不适合会减少的分数

请问分数是会减少的吗,这种做法不适合会减少的分数

请问分数是会减少的吗,这种做法不适合会减少的分数

请问分数是会减少的吗,这种做法不适合会减少的分数

感觉博主的风格就是中国程序员的风格,只是臆想,没有测试环境的测试数据做依据,就认为数据库不好。

其实有时候程序员对与数据库的依赖, 是因为他们不知道在不用数据库的情况下如何能保证数据的正确持久化;或者说, 他们没有这个信心...不过我觉得, 只要这部分数据是可以"对账"的, 就可以大胆放心的做;

排行榜这个东西的确很多地方使用,我们采用的方式也不是使用数据库排序 ,而是使用堆排序,全放内存,堆里只需要放top k个,可以快速响应读取,备选 数据全放在一个map,将要新的高分大于这个堆的时候,才放进堆里排序,其余都是放在map里等待。

以前设计的用户排名也是这个办法,千万级的,似曾相识

我也做过游戏里的排行榜,根本算法也是插入,也就是最基本的思路,可以说是完全依据数据库做的。
云风这个实现确实无论是效率还是内存占用方面都是优异,这个算法立足点之一是分数范围是0-5000,如果上限提高,桶的做法就有待商榷了。
但是这实现方式确实让我学习到如何脱离数据库针对需求,采用相应方式统计数据

记下了,看来处理大数据的时候要另辟新路才好走。

最近这两篇都没什么技术含量,像小学生似的记流水账,外加对臆测而来的结果进行所谓分析。再次谴责标题党,两大篇洋洋洒洒近万字了,那坑爹的坑还没影呢。

积分无上限的话,树形分区设计可以解决。[0,n) -- [0, n/2) & [n/2,n) ...每个区段保存该区段用户数,玩家积分更新的幅度越小,所更新的结点层级越低

内行看门道,外行看热闹。即使是八卦也很有意思[good]

经常要遇到排行榜,现在用的都是Redis 对这个的熟悉程度并不高 但他做排行用起来确实方便 也就一直在用,对他的操作简单一点,做几个最基本的输入输出函数,在这上面的业务尽量简明,就好了

@tonanso

没有上限的话…… 第一反应是二维线段树或者树状数组

据说某公司的DBA,如果那个项目使用MongoDB ,一律打回

那个八卦感觉就是在谈过载保护么,呵呵

其实这个篇文章主要是想让大家明白,计算好模块输入和处理的匹配度吧??

xuexi

我想表达的不是怎么利用数据库做排名,实际我们的排名系统和数据库一点关系都没有。

无非是提出需求,分析需求,然后找到合理的算法和数据结构实现出来罢了。

程序员手里的工具依旧是算法和数据结构。如果现有的数据库内置了你需要的东西,而你又熟悉它们,那就用;否则也不用在数据库怎么用上吊死。

赞啊,昨天还在问排名系统的实现今天就出来了, 另外有个问题是 如果分数没有上限,这个排名系统该怎么优化呢?

这是大部分UGC系统常用的累计更新和预缓存手法,这样的系统如果出现更新操作错误,就会累积起来很难修复,多半需要重建缓存

Post a comment

非这个主题相关的留言请到:留言本