我发现一篇讲述谷歌云如何协助它的客户解决排名系统难题的文章，这篇文章里面涉及了算法和工程的优秀结合，非常值得一读。但对于部分读者来说，里面包含了不少谷歌云的细节以及非常规的数据结构，所以我决定通过我的理解，重新整理并阐述这篇文章，其中加上我自己的注释，希望大家能够从中得到启发。
故事的开始都是一样，谷歌的一名大客户 Applibot 在开发游戏 Legend of the Criptids 的过程中遇到一个显示排名的难题。
- 游戏中有数十万甚至更多的玩家
- 当一个玩家击倒敌人（或者其他行为）的时候，它们的分数会改变
- 问题是：如何在游戏中显示最新的玩家排名
像大部分程序员一样，Tomoaki 想找一个快速可靠的，可以接受每秒 300次 更新并且能在数百毫秒内返回结果的排名系统方案。这个时候，Tomoaki 找到 Kaz Sato，谷歌的方案架构师，希望他可以帮助解决这个问题。Kaz Sato 知道排名是一个在大型分布式系统中经典而且难解的问题，他开始去谷歌云以及其他非关系型数据库中去找寻解决方案。
一开始的方案，数据库查询需要扫描一遍所有的玩家的得分才能计算出排名，（注释：虽然数据库能提供缓存，但是由于游戏系统中，玩家的得分更新很快。所以使用缓存会得到不准确的排名。）它的算法时间复杂度为 O(n)，也就是说随着玩家越来越多，运行时间也会同比增长。所以，我们需要一个 O(log n) 或者更快的算法，让运行时间仅仅以对数级别增长。如果你曾经学过计算机科学，这时候可能就会想到树算法，例如二叉树，红黑树或者 B 树，能够在 O(log n) 的时间内找到一个元素。并且通过在节点中存储数据可以进行计数，极值查找，平均值查找。使用树结构可以在 O(log n) 时间内实现这个排名系统，kaz 接下来找到一个谷歌的开源项目，这个开源库实现了两个功能：
- 设定玩家的分数
- 获取分数对应的排名
Kaz 使用了 Apache JMeter 作为压测工具对这个开源库进行测试，发现使用这个树算法之后，更新分数和查找排名都能在数百毫秒内完成。
注释：这个开源项目实现了一个 N-ary 树，类似 Segment 树的变形。每个节点存储三个对应的区间内的分数，不过这里我们并不讨论这个方案，因为这种数据结构实在太特殊，一般编程语言都没有实现。我们尝试使用另外一个常见的数据结构，二叉平衡树来解决这个问题。为什么不使用堆呢？堆也有排序以及找第 k 大元素的作用，不过堆要找第 k 个元素的话需要 pop k 次，之后还要把 pop 的元素添加回来。对于需要频繁更新的元素来说并不合适。
- 初始化，建立一个哈希表，键为玩家 ID，值为分数对象，ID-> 分数对象，时间为 O(n)。接下来，建立一个以（分数对象，ID）为大小的全部玩家数量 n 的二叉平衡树，其中每个节点额外记录左右子树的节点数量。时间为 O(nlog(n))。
- 要找到某个玩家的排名，我们只需要在哈希表中查找对应 ID 的分数对象的值 ，然后在二叉平衡树中根据其左节点以及父节点的左节点数量递归找到对应排名，时间为 O(log(n))。
- 要找到某个区间内的排名，例如第 101 到 第 200 名，我们需要查找 100 次对应排名的玩家，时间为 O( k(log(n))，其中 k 为区间的大小。
- 更新玩家分数：更新哈希表，并且更新二叉平衡树的节点，时间为 O(log(n))。
但是在压力测试的过程中， Kaz 发现了开源库的一个问题，它对于并发更新的可扩展性非常弱，当他尝试着把请求压力提高到每秒 3次 更新的时候，更新就开始返回错误异常了。很明显，这与 Applibot 要求的能支持每秒 300次 更新还有很大的距离。那么原因是什么呢？一般来说，树结构并不是线性安全的，所以此开源库需要维护树结构的强一致性，也就是保证每次只更新一个节点。而由于整个解决方案基于谷歌的 Datastore，一个高性能的非关系型数据库，（注释：树结构都存储在这个数据库中）。Datastore 使用事务来保证强一致性，每个对象最多只能支持每秒 1次事务执行，当有高并发更新请求的时候，每次更新都需要执行一次事务，最后导致吞吐量非常低。
Kaz 想起之前 Datastore 团队提出过的一个方案，与其每次更新都执行 1次 事务，可以尝试把多个更新操作合并一起再执行 1次 事务。不过这样每个事务可能包含大量的更新，花费的时间也更久，而在 1次 事务中执行多个更新的话，会增加了并发冲突的可能性。有鉴于此，Datastore 团队提出了另外一个方案，基于队列的任务合并，这个设计模式在 VoltDb 和 Redis 都能看到，简单来说，就是使用单线程在一次事务中按顺序执行这些更新，既然是单线程，那么就不会有并发冲突的问题。不过，也因为每次只有一个线程在执行任务，更新的速度就取决于这个线程执行更新的速度，需要使用工具测试能否支持每秒 300 次更新。基于这个方案，Kaz 实现了任务合并方案的代码，包括以下几部分：
- 前端：接受请求，并把任务放到队列
- 队列：持续接受保存前端发过来的请求
- 后端：使用单线程无限循环，不断把队列里的请求拿出来进行合并，然后使用开源库执行，每次执行都是 1次 事务。
Kaz 再次使用 JMeter 进行测试，他证明了这个方案能够支持每秒 200次 更新，每次事务执行 500 到 600 次更新。（注释：每个事务可能会执行超过一秒钟）
但是 Kaz 发现了另外一个问题，但他使用这个方案运行测试几分钟的时候，发现队列的吞吐量偶尔会大范围波动（如下图），尤其是持续几分钟，每秒放入队列 200 个任务的时候。队列突然停止分发任务给后端了，致使响应时间大幅提高。
- 把任务放到 10个 队列中
- 使用另外一个方法 从队列中获取任务并且合并，分发给后端
- 从队列中删除执行成功的任务
第一步，每一个队列最多存放 1000个 任务，每个任务里面包含了玩家名和分数，我们从队列中拿到信息后，把这些信息中包含的玩家和分数的组合合并放到一个字典（合并更新）。第二步，使用开源库的更新操作来进行更新树结构，开源库会开启一个事务执行这些操作并把他们存储在 Datastore 里面。如果任务执行成功的话，那么就把任务从队列中删除。如果任务执行失败的话，更新操作还会留在队列中，之后还可以重新执行一次。在实际环境中，你可能需要类似 Watchdog 这样的工具来监控更新情况。下图显示了这个新方案的实现效果，它能最大程度地利用资源并且能持续多个小时支持每秒 300次更新，这个最终方案达到了 Applibot 原本的所有要求：
- 能支持数十万甚至更多的玩家
- 能够保证持久化以及一致性，因为所有更新都是通过 Datastore 的事务进行更新。
- 能支持每秒 300次更新
优点:
- 高效快速：能在数百毫秒内找到玩家排名以及进行更新
- 强一致性以及持久化
- 排名准确
- 可以扩展到任意数量的玩家
缺点：
- 吞吐量有限制，只能支持约每秒 300次更新。因为这个解决方案依赖于一个单线程执行合并之后的更新。
如果你需要支持更高的并发更新量，你可以对树结构进行分片，同时需要对系统进行一些修改，例如指定某些队列专门更新某个树结构的分片。在最简单的情况下， 更新会随机分配给一个队列，使用分片后的三棵树的话，能够提高三倍的吞吐量（注释：按照我的理解以及对开源库源码的分析， 是需要先找到对应的玩家所在的树然后进行更新的）。相应的产生的问题是，在调用 计算排名的时候，需要查找三棵树最后把排名加起来。例如 可能会在三棵树分别排名在 124，183 以及 156。代表三棵树分别有那么多玩家分数比 865 高。所以这个分数的最终排名应该是 124 + 183 + 156 = 463。这种方式并不适合所有的分布式系统，但是因为排名是可累计的，所以能够这样设计。
排名是一个典型的，难解决的问题，这里讨论的解决方案，任务合并以及基于队列的更新，能够适用于每秒更新量在几百范围内的系统，并且能够保证一致性以及持久化。