获得第三届阿里中间件性能大赛冠军

发表于 更新于 Disqus：

一不小心拿到了天池阿里中间件性能大赛的冠军，准确的说还有个 24 小时即刻挑战赛（个人赛）的亚军。

Emmm... 过去太久了，不知道说什么感言了。以下是是比赛的题目以及我的解答，备忘。

第一赛季：消息中间件

题目大意（完整的请点这里）

设计一个消息中间件，它支持 Topic 和 Queue，每个 Topic 可以被一个或多个 Queue 订阅。显然，发往 Topic 的消息会被所有的订阅者接收到，而发往某个特定 Queue 的消息只会被它接收到。

消息不能丢失，且对于各个 Queue 消息要保持有序。在此前提下，吞吐量最优者获胜。

要注意的是，生产和消费是分两个阶段进行的：先进行生产，结束后再进行消费。

我的思路很简单，对于每个 Topic 或者 Queue，把所有消息序列化后写入对应的一个文件中。消费时，从磁盘中顺序读取即可。

本题最后瓶颈落在了磁盘 IO 上，所以很多优化也变得无关紧要了。为了充分利用磁盘 IO，一定要确保两点：

  • 顺序写入和读取（参见我的这篇文章）
  • 使用 Linux 内存映射（mmap）技术，也就是 Java nio 包里的 MappedByteBuffer

此外，序列化的过程中尽可能减少内存拷贝，以及避免不必要的 String 序列化、反序列化。

做到以上几点，进入前 20 不是问题。初赛只要前 200 名就可以晋级了（吐槽：那很容易啊！！但是一开始不知道初赛成绩也要计入最后评分的）

代码托管在阿里云 code 上。

第二赛季：数据库同步

题目大意（完整的请点这里）

模拟数据库的主备复制。给定一批 binlog 文本数据，你的任务是重放所有 binlog 从而得到数据表的最新状态（假设原本状态是空的）。重放的操作包含 Insert/Update/Delete 三种操作，注意主键也可能被更新！

验证结果的方式是，客户端给定一个 PK 的区间，输出该区间的所有行。

注意，程序分 Server 和 Client 端，机器配置都很高（16核CPU），但是 JVM 的堆大小被限制为 1G 新生代 + 2G 老年代。此外，必须顺序读取 binlog。

思路如下：并行化是一定要的，如何并行呢？答案（当然）是按主键哈希分桶。然而这样主键更新怎么处理？这是最大的难点。

为此我们想出了一种并行化的算法——可以说这就是最终获得冠军的原因。具体思路在决赛答辩 PPT 里写的很清楚啦。

答辩PPT（包括完整的解题思路）：

这题思考了很久，最后交出的答卷含金量也很高。哈希分桶作为经典算法中常见的一种模式，在很多分布式系统中都有应用。

此外，比赛初期还没有加上“必须顺序读取”这个条件。如果没有这个条件又会有别的奇思妙想的算法来解决。留给读者自己思考（喵）

代码 托管在阿里云上，同时还有 设计文档 也很有帮助（如果你觉得 PPT 还不够细致）。

24 小时极客 PK 赛

题目大意（完整的请点这里）

分页排序。给定一批数据，求解按顺序从小到大，顺序排名从第k下标序号之后连续的n个数据，类似于 order by id limit k, n，n 会很大，k <= 100

数据是文本文件，每行是一个长度在 256 字符以内的字符串。排序的方式是：先按长度从小到大、再按字典序。

注意一共有 2 台 Worker 和 1 台 Master，Worker 上分别放了 5G 的数据，最后 Master 要请求到完整的排序结果。

和之前的两场比赛不同，24小时赛的成绩是不计入最后评价的，而且是以个人名义参赛。奖品是去硅谷开（玩）会（耍）！（PS. 然而不能带女朋友，最后去了一帮基佬啊摔！）

外排序是很容易想到的思路，然而十分复杂，也不能很好的并行。那怎么办？依然是分桶，Bucket Sort。

假设字符串长度的分布是均匀的，字符出现的概率也是相近的，则我们可以用以下的值作为每个字符串的 key：

1
<length> <text[0]> <text[1]> <text[2]>

（如果长度小于 3 就用 '\0' 填充一下）

这样我们就能对每个 key 做统计了——有多少个字符串是在这个桶里呢？假设这个结果放在数组 count 中，那再对 count 求一个累计和，就能用二分查找找到第 N 个数应该位于哪一个桶里。

同样的也可以找到第 N+K-1 个数应该位于哪个桶里。然后就简单了，把区间内的桶里的值都取出来，让 Master 排个序就好了。

把区间内的桶里的值都取出来？——这个过程可以扫描整个文件。也可以做个预处理的优化：把每个字符串的 key 和 offset 分别存到两个数组里，比如 keys[] 和 offsets[]，这样只要扫描数组就可以了！

然而我并没有想到这个优化，所以是第二名。哈哈哈！

代码托管在阿里云上。

后记

  1. 算法是好的，要多刷 HackerRank
  2. 阿里搞的这个比赛啊，Excited ！