2020快手编程比赛-苟到18名的思路及总结

125 views

作为一名比赛水军,本菜鸟绝对不会放过任何一次有奖品的比赛。今年是快手第一次举办程序设计类的比赛,本次比赛的题目主要为日志分析。即给你差不多十几个G的数据,你怎么快速分析得到相应的指标,并构造高效的函数接口用于查询。本次比赛主要使用Java编程语言,还好大二学过,不然上手有点困难。

德彪嘻嘻

本片博客首先介绍解题的思路,然后介绍编程过程中学到的Java调优经验。

一、解题思路

题目的详细内容为:给定大概14G的日志数据,在8核6G的条件下进行分析,得到每分钟服务粒度和IP粒度的P99及成功率,再利用这些数据,实现如下功能:

  1. 实现一个报警检查程序,输入一组报警规则和一个监控文件路径,触发器负责分析监控数据并返回所有的触发的报警的数据。
  2. 实现一个报警关联分析程序,输入为报警检查程序(上一问)返回的报警触发点信息,输出该报警影响的最长调用链路(可能存在多条最长路径,需要输出全部)

日志数据格式为:


1.1 根据数据得到任务粒度和IP粒度的P99和成功率

P99的计算和成功率的计算所需要的时间并不多,所以分析数据的瓶颈还在于数据读取及解析上面。如果磁盘IO速度很快,那么使用多线程是个正确的选择。如果磁盘IO速度很慢,使用多线程并没有太大的魔法加成,但是我个人觉得多线程还是要比单线程好的。多线程与单线程的流水线时间图如下所示:

多线程和单线程流水线时间图

从上面可以看出,多线程相比于单线程还是存在一定优势的。多线程想要用的好,关键还在于线程之间的独立性。如果多线程总是要同步,那么性能就会大打折扣。

对于多线程读取文件的处理,我用了一个BlockQueue来存储当前文件读到的位置。每个线程从BlockQueue中获取到当前读到的位置,然后使用nio包中的map来获取字节。获取完字节之后,手动从最后一个字节进行倒退判断是不是’\n’(因为我们每次解析数据是按照行为单位的),倒退到最后一个’\n’的位置的时候,然后再将这个位置放入BlockQueue中,其他线程就可以进行读取了。

读取到字节流之后,就要进行最费时间的数据解析了,我是根据字符来进行解析。所以写出来的代码大概就像这样:

据我所知,这应该是最快的数据解析办法了。通过文件解析,我们获得了每行日志的数据:主调服务、主调IP、背调服务、被调IP、消耗时间、成功与否、时间戳。由于主调服务、被调服务、时间戳基本上是后面查询的key,所以我们采用下面的hash表来存储解析的数据:


answerPairMap的第一个键值为主调服务名称,第二个键值为背调服务名称,第三个键值为时间戳,PairList保存了每一分钟的主调IP和被调IP、消耗时间、成功调用的数量级失败调用的数量。这样数据一个萝卜一个坑,直接丢进这个hashmap里面就好了。当然保存消耗时间还有一个trick,因为一分钟的消耗时间是很多的,如果我们采用List来保存,估计内存会爆炸,所以我们可以采用Map来保存每个数出现了多少次。

万里长征第一步,我们的数据解析及计算就完成了。下面要实现报警功能。

对于报警功能,其实没有什么太多的trick,感觉只能老实干。直接针对每条报警规则,对每分钟的数据进行判断,是否满足报警条件,满足报警条件就输出。由于报警条件中有持续时间的限制,所以我们还要判断数据触发阈值持续了多久。这个持续时间的判断是需要注意的地方,比如持续时间达到条件之后,如果下一分钟的数据还是触发阈值,那么下一分钟还是报警点。具体代码如下所示:

这样报警功能已经实现了,下一步就是查询了。查询要做到高性能,基本上就是上数组,并且设计一个好的hash函数让数组索引和查询键值进行对应。我使用了二维数组,最终的查询接口如下所示:

搞完第一个功能,我们还需要提前处理第二个查询的结果,便于快速查询。对于影响最长链路,直接使用dfs找最长路径就好了,这里面的trick我暂时没想到。

好了,这样一个baseline就完成了。整个coding过程并不难,难得只是bug难找,因为线上无法看到准确的错误。

这个版本最终得分为8199分。

二、优化经验

  • 使用HashMap<Integer, Integer>的时候,会产生大量的Interger对象,从而触发GC。其实对于这种简单的数据类型,我们可以自己改一下,弄一个IntHashMap,使用int基本类型,能大大减少内存的使用。
  • 尽量少用String。你可以用StringBuilder代替String,得到真正要用String的时候才用StringBuilder.toString()。同时一个函数如果要多次使用StringBuilder的话,如果能重复使用,就尽量重复使用。
  • 数组比HashMap要快。
  • hashcode是有缓存的,所以多次使用并不会重复计算。
  • Jprofile是个好工具,可以看到哪里慢了,哪里用的内存多了,什么时候GC了,调优的好帮手。

文章就这样流水账式的结束了,但是比赛过程中的Bug以及思考已经深深的留在了我的脑海当中了。

Rating: 5.0/5. From 1 vote.
Please wait...