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

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

alibaba-praise

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 !