第五届中间件性能挑战赛

发表于 | 更新于: | 分类于 | |

感想

这是19年8月参加的比赛，也是我第一次参加这种比较正式的比赛。这次比赛，初赛参加队伍为4095支（个人感觉里面好多僵尸队），复赛参加队伍为200支。我们队初赛成绩为127名，复赛成绩为59名，其实成绩并不好，但是的确花了很多精力去做这个事。记得比赛的时候，满脑子想的都是如何优化，甚至能凌晨起来码代码。之前一直说想着写个总结，现在也算是实现自己这个想法。

初赛

详细的比赛内容可看初赛说明。
初赛的内容是负载均衡，简单来说客户端通过HTTP访问Gateway服务，Gateway按照选手设计的负载均衡算法选择一个Provider进行调用，并将Provider返回的结果返回给客户端。

public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException {

}

我们的任务其实就是填写这个函数（当然还有其他接口可以使用）整个测试环境包括3台不同处理能力的Provider组成，并且依赖dubbo框架啊，最后根据成功请求数计算排名。

  1. 一开始git下来的代码自带简单的实现，就是随机选择一个Provider，成功请求数为111w。
  2. 我们想到的是对于每个Provider设置一个周期性变化的权重，然后使用基于权重的轮询负载均衡算法。权重的计算由成功请求数决定，即权重=一定时间内发往该Provider的请求总数-这段时间内失败的请求数，成功请求数达到125w。
  3. 想到只根据成功请求数进行权重计算，可能会滞后于Provider的处理能力变化，所以采用成功请求数+请求成功率结合的方法，成功请求数能达到127w。
    1. 基于假设：当成功率为100%时，说明Provider负荷未打满，还有充足的处理余地，所以适当提升权重；当成功率低于100%时，说明Provider负荷已打满，适当降低权重。
    2. 具体做法：当成功率=100%，权重=成功数乘以1.1；当成功率<100%时，权重=成功率乘以成功率。这样能更快适应Provider的动态处理能力。
    3. 降低采样率，即不统计所有的请求，而是以50%的采样率进行采样，即两个请求选择一个进行统计。

由于达到127w后已经进入了前200名，可以进复赛了，我们之后就没继续改了。后来看排行榜，初赛最高分达到了131w。详细可见初赛代码。

复赛

复赛的详细说明可见复赛说明。
简单来说，就是要实现一个消息中间件，并且满足下列功能：

  • 发送消息功能
  • 根据一定的条件做查询或聚合计算，包括
    1. 查询一定时间窗口内的消息
    2. 对一定时间窗口内的消息属性某个字段求平均

每个消息包括两个字段，一个业务字段a（8字节），一个时间戳（8字节），以及一个消息主体body（34字节）。实际存储格式由参赛者决定。最后的成绩每个阶段的消息总数和消耗时间共同决定。

发送阶段是由多个线程并发调用消息中间件的put方法，其中有个潜在特征，即每个线程发送的消息时间戳都是升序的。

  1. 首先想到的是在发送阶段就对消息根据时间戳进行排序，然后后续的查询阶段就方便多了，提后后成绩为3583分。
    1. 每个线程在调用put方法时，利用ThreadLocal存入线程内部的缓冲块，待缓冲块存满后交由缓冲块排序器进行排序。考虑到读写速度的最大化，这里设置缓冲块的大小为32M。另外，由于缓冲块的重复创建会带来一定开销，并且可能会引发JVM的垃圾清除，所以这里使用缓冲池来进行缓冲块的分配。
    2. 缓冲块排序器会检查所有的发送线程是否至少写满了一个缓冲区，若是，就会对多个缓冲块内的消息进行排序，并将排序后的消息存入写缓冲区，并分配文件名，最小时间戳，最大时间戳。这个排序过程其实就是多路归并排序。
    3. 待发送阶段结束后，对于剩下的缓冲块进行排序。此时得到了一串根据最小时间戳排序的文件列表，查询阶段就可以筛选合适的文件进行消息遍历。
  2. 考虑到时间戳是升序，如果能够用2个字节表示时间戳，那么读写磁盘的开销就会降低很多。另外，考虑到第三阶段是查询满足条件的a字段的平均值，并不需要查询消息的byte数组。针对此，进行优化，优化后第三阶段分数上升，总成绩为7887分。具体做法如下：
    1. 将消息的时间戳和字段a写入一个文件，将body写入另一个文件。这样在第三阶段将大大节约磁盘读取量。
    2. 另外按照10000的时间戳范围进行存取，即0-10000时间戳内的消息存入一个文件，10000-20000之间的消息存入另一个文件，这样做的好处是可以将消息的时间戳减少为2字节，即时间戳为10001990的消息可存入10000000-10010000的文件，该消息的时间戳=实际时间戳-该文件最小时间戳（偏移表示法），即1990，这样做相当于将原本50个字节的消息压缩成了44个字节。
  3. 怀疑发送阶段的线程并发模型太过粗糙，影响了成绩。原先的做法是每个线程发送消息超过8个缓冲块时将会暂停当前线程，原因在于生产者发送消息，消费者对消息进行排序并写入磁盘。相对来讲生产速度远大于消费速度，如果不加限制，将很快耗尽内存。所以原先使用Thread.yield方法来维持线程间的协作关系。但是使用yield方法还是会导致线程间的竞争，花费无用的时间。所以使用wait和notify来维持线程间的协作，当生产者发送消息过快时，就wait；而消费者每消费掉一个缓冲块，就可以唤醒相应线程继续生产。通过该优化，成绩达到11380分。

具体可见复赛代码。能够看到成绩提升的优化如上所述，另外，我们还尝试了将部分消息缓存在内存中，或者将缓冲块的统计信息记录在内存中（方便查询时筛选）但都收效甚微。后来从排行榜看到，第一页的大佬们都猛得很，第一名甚至达到5w分。