使用布隆过滤器降低 YoungGC 耗时

Java BloomFilter GC jstat mat nginx tomcat

过去的一周推荐系统的服务出现了些问题。 顺带也暴露出服务的性能问题——YoungGC 耗时过长。 使用 jstat 监控, 发现每次 YoungGC 耗时从400ms ~ 1.5s 不等。

后面使用 BloomFilter 替换了原有的数据结构, 将 GC 耗时减低至 60 ms。

相关流程

为了说明 GC 的问题, 先了解下现在的服务的逻辑流程:

推荐系统请求处理流程

每次推荐请求由规则处理器负责调度。 调度器会从相关的算法候选集中召回数据。 召回的数据依次需要经过 黑名单过滤器曝光过滤器的处理。 最终才能将数据返回给用户。

YOUNG GC 耗时过长

GC 的问题第一次引起我注意, 是因为线上 nginx 会出现一些错误日志:

2017/03/07 23:12:26 [error] 3041#0: *10088243 connect() failed (110: Connection timed out) while connecting to upstream,
client: 10.33.1.183, server: xxxxx.xxxxx.net, request: "POST /rule/api/B8763FC5F4E0ASOQ HTTP/1.1",
 upstream: "http://10.33.7.100:7001/rule/api/B8763FC5F4E0ASOQ", host: "10.33.7.101"

显示 nginx 转掉应用服务器的时候出现了连接超时。 程序使用的容器是 tomcat, 负责底层的网络通信。 它是成熟的组件,不应该出现这么明显的问题。

并且 tcp 的 connect是由操作系统实现的。 所以一般应用层的错误也不可能导致 connect 超时。

通过观察错误日志, 以及应用服务的 gc 日志。发现 gc 耗时超过 1s 的时候,就有可能出现 nginx connect 超时的错误日志。 由此得出结论: nginx connect 超时是由于服务 gc 时间过长导致的。 Java 垃圾收集器确实是会导致整个进程卡顿的, 从而导致操作系统没有 资源处理网络请求。

什么导致 GC 耗时过长

服务处理请求一般都是无状态的。请求处理过程中可能会有很多对象生成, 但是请求完成后,这些对象也就没有作用了。基于标记复制的垃圾回收算法会比较高效。 目前推荐系统的服务使用的是 CMS , YoungGC 垃圾收集使用的基于标记复制算法。

标记复制算法适合处理大量朝生夕灭的对象, 如果有大量对象不能马上销毁。 那么就会导致 GC 时,需要拷贝大量的数据。

分析现在的推荐系统的服务, 有以下几个部分会导致大量对象不能释放。

  1. 对算法候选集的缓存

    为了减少服务与数据库之间的网络通信, 需要缓存很多数据,包括个性化的推荐结果

  2. 曝光过滤器,

    在测试期间大概100qps, 保存了 58w 的记录,占用内存85M。

  3. 黑名单过滤器

    有10w 条黑名单记录, 占用内存达到 53 M。

对个性化算法候选集的缓存是不合理的,应该由专门的缓存服务来实现。 由于现在缓存服务存在短暂的卡顿现象,所以这部分目前不能够少。

使用布隆过滤器优化过滤器

过滤器做的一件事,就是判断某一项数据是否存在。 通常会使用 map 或者 set 这两种数据结构实现。 但在数据量大的情况下,需要消耗大量内存。 如果,数据经常改变,不能进入到老年代,对 GC 的负担也是不少。

经过分析,以上两个过滤器都可以使用布隆过滤器来实现。 使用布隆过滤器,可以将需要的内存直接放到老年代中,从而减少 YoungGC 的负担。 布隆过滤器的数据是存储在一块连续的内存里。在 jvm 中可以通过-XX:PretenureSizeThreshold设置超过一定大小的 对象直接进入到老年代。

布隆过滤器参考:

  1. 布隆过滤器
  2. 布隆过滤器详解

曝光过滤器

如最上面的流程, 服务会将返回给用户的数据记录起来。 下次如果请求到相同的数据时,会直接被过滤掉。 由于服务的存储空间有限, 只能过滤最近一段时间的曝光数据(目前是最近的10分钟)。

因此在简单的布隆过滤器之上,封装了一个时间环的复杂布隆过滤器。 实现了可以过滤最近一段时间的曝光滤重。

TimeRingBloomFilter

如上图, 如果需要过滤最近 n 分钟的曝光数据, 则会有 n + 1 个布隆过滤器。 每个布隆过滤器会有下了几种不同的状态:

  1. clean, 所有过滤器的初始状态,表示没有存储任何数据
  2. current, 当前这分钟新写入的数据会保存到该过滤器中
  3. dirty, 表示之前已经写过数据, 该状态下的布隆过滤器需要提供查询功能
  4. invalidate, 该过滤器的数据需要被清空, 清空后该过滤器又会回到 clean 状态

TimeRingBloomFilter State

黑名单过滤器

这个则相对简单, 是一个固定大小的布隆过滤器。

优化效果

优化后, gc 稳定期间, YoungGC 耗时降至 60 ms,原来则可能有500~600ms。GC 耗时下降了近10倍。

吕飞

锲而舍之,朽木不折;锲而不舍,金石可镂