在之前, 我们利用容斥原理实现了hyperloglog的intersect, 接着我们继续分析一下其实现的整体性能.

Hyperloglog分析

测试中,我们采用的日志数据格式如下:

drt=2015-10-24+00:00:00&cl=0&ac=800&ts=0&ise=0&rsd=FbKCPEUrJY&pid=3&cid=guVmoqc8dLjsE&app=1163919&spotid=&chn=0&ip=&ipr=&country=&prv=&cty=&tc=&brd=&mod=&cst=&os=&osv=&av=1.2.2.2&sv=5.1.0&spc=&pn=com.tenziziios.player&ei=865027015117309&si=460023563265538&bd=&mac=3ccb7c80f9d8&apn=wifi&cn=%E4%B8%AD%E5%9B%BD%E7%A7%BB%E5%8A%A8&dd=tcl+p500m&dv=tcl&udid=&ifa=&po=android+4.4.4&rt=1445601593&sw=480&sh=854&sds=1&attr=&bsi=&lat=&lon=&pv=2&ua=&tsort=0&src=&abt=a&code=-2222&bssid=&batsn=&fcsn=&bcsn=&root=&tid=&reqf=1&nshw=0&andid=2548ba53a3e40cc1&slotid=&postyle=&portal=&endpoint=&nt=&region=0&cityc=0

drt=2015-10-24+00:00:00&cl=0&ac=800&ts=0&ise=0&rsd=9GWrDOrPDC&pid=3&cid=ybPbpi3A7zgp&app=27146&spotid=&chn=0&ip=222.137.46.185&ipr=222.137.46.185&country=CN&prv=河南&cty=郑州&tc=2&brd=华为&mod=h60-l02&cst=0&os=3&osv=4.4.2&av=3.2.1&sv=4.0.8&spc=0&pn=com.gale.sanguokill.hd&ei=864103020831944&si=460015541085974&bd=&mac=60e701fdbc86&apn=wifi&cn=%E4%B8%AD%E5%9B%BD%E8%81%94%E9%80%9A&dd=h60-l02&dv=huawei&udid=&ifa=&po=android+4.4.2&rt=1445615998&sw=1196&sh=720&sds=1&attr=&bsi=&lat=&lon=&pv=2&ua=Mozilla%2F5.0+%28Linux%3B+U%3B+Android+4.4.2%3B+zh-cn%3B+H60-L02+Build%2FHDH60-L02%29+AppleWebkit%2F533.1+%28KHTML%2C+like+Gecko%29+Version%2F4.0+Mobile+Safari%2F533.1&tsort=0&src=&abt=a&code=-2007&bssid=&batsn=&fcsn=&bcsn=&root=&tid=&reqf=0&nshw=0&andid=7391ee6ae1856a2c&slotid=&postyle=&portal=&endpoint=&nt=2&region=41&cityc=410100

原始输入数据: 16505217行, 统计得独立用户数: 4114406 .

统计了日志中的字段有: product, pid, app, brd, tc, apn, nt, region, cityc, sv, osv, sw, sh, portal, endpoint, drt, ifa, ei.

存储到reids的hyperloglog的key数:9893个,占用内存: 16.64MB .

len(keys('traffic_uv:pid:*')): 3
pfcount keys('traffic_uv:pid:*'): 4114406
time of pfcount: 0.675916671753ms
time of pfmerge: 0.739097595215ms

len(keys('traffic_uv:drt:*')): 25
pfcount keys('traffic_uv:drt:*'): 4114406
time of pfcount: 2.10809707642ms
time of pfmerge: 1.61290168762ms

len(keys('traffic_uv:region:*')): 36
pfcount keys('traffic_uv:region:*'): 4114406
time of pfcount: 2.68697738647ms
time of pfmerge: 2.25591659546ms

len(keys('traffic_uv:cityc:*')): 347
pfcount keys('traffic_uv:cityc:*'): 4114406
time of pfcount: 19.6759700775ms
time of pfmerge: 14.0299797058ms

len(keys('traffic_uv:sw:*')): 288
pfcount keys('traffic_uv:sw:*'): 4114406
time of pfcount: 5.03301620483ms
time of pfmerge: 5.34081459045ms

len(keys('traffic_uv:sh:*')): 598
pfcount keys('traffic_uv:sh:*'): 4114406
time of pfcount: 5.77092170715ms
time of pfmerge: 5.37204742432ms

len(keys('traffic_uv:app:*')): 6074
pfcount keys('traffic_uv:app:*'): 4114406
time of pfcount: 31.014919281ms
time of pfmerge: 38.4378433228ms

# cityc, sw, sh耗时差异原因
average of traffic_uv:cityc:* length 10026.7348703
average of traffic_uv:sw:* length 1381.75347222
average of traffic_uv:sh:* length 912.285953177

对于上面benchmark的结果中, traffic_uv:sh:*, traffic_uv:sw:*, traffic_uv:cityc:* 的key数量级均为10^2, 而耗时却相差较大, 其原因在于用户在 cityc 字段的分布比较均匀, 导致 traffic_uv:cityc:* 每个key需要分配更多的桶来标记用户.

递归分析

在后续的测试中我们发现，通过利用容斥原理来计算多个hyperloglog的交集，其计算耗时主要在 recurse_intersect上, 随着组合条件的增多, 递归深度剧增。

我们的测试数据:

# 各条件的key数量
len(keys('traffic_uv:pid:*')): 3
len(keys('traffic_uv:nt:*')): 19
len(keys('traffic_uv:sv:*')): 21
len(keys('traffic_uv:osv:*')): 202
len(keys('traffic_uv:sw:*')): 288
len(keys('traffic_uv:sh:*')): 598
len(keys('traffic_uv:brd:*')): 39

当然,以上的每一个条件我们根据筛选参数先pfmerge为一个key, 如: traffic_uv:pid, traffic_uv:nt ……

我们根据容斥原理进行理论上的分析, 设N为组合条件个数, P为pfcount的次数, Q为pfcount的总keys数, 则有:

N=1时, P=1, Q=1

N=2时, P=3, Q=4

N=3时, P=7, Q=12

N=4时, P=15, Q=32

N=5时, P=31, Q=80

N=6时, P=63, Q=92

N=7时, P=127, Q=448

N=8时, P=255, Q=1024

N=9时, P=511, Q=2304

………..

在上面的分析中, 我们已经采用了缓存来减少重复计算量(但仍然存在对对函数的调用和对缓存的读取, 而事实上, 但递归的加深, 这部分的耗时也是不容忽视的, 甚至占用了大部分的耗时).

在接下来的测试中,我们采用了三组数据进行分析, 数据量均为: 原始输入数据: 1600W, 独立用户数: 400W .

8个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080&sh_max=1920&region=11,12,13,33,34,35,41,42,44&brd=10,11,12,13,21,22,23

三次测试中, recurse_intersect调用总的耗时分别为482ms, 554ms, 521ms.其中pfcount操作的总耗时分别为:153ms, 197ms, 170ms ; pfmerge操作耗时: 17ms, 12ms, 16ms

7个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080&sh_max=1920&region=11,12,13,33,34,35,41,42,44

三次测试中, recurse_intersect调用总的耗时分别为212ms, 192ms, 200ms.其中pfcount操作的总耗时分别为:92ms, 73ms, 80ms ; pfmerge操作耗时: 15ms, 22ms, 15ms

6个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080&sh_max=1920
三次测试中, recurse_intersect调用总的耗时分别为63ms, 83ms, 65ms.其中pfcount操作的总耗时分别为:24ms, 41ms, 28ms ; pfmerge操作耗时: 11ms, 15ms, 18ms

5个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2&sw_max=1080
三次测试中, recurse_intersect调用总的耗时分别为40ms, 25ms, 26ms.其中pfcount操作的总耗时分别为:22ms, 14ms, 15ms ; pfmerge操作耗时: 8ms, 8ms, 10ms

4个组合条件:

pid=3&nt=1,2,4&sv_max=511&osv_min=2.3.2
三次测试中, recurse_intersect调用总的耗时分别为6ms, 14ms, 10ms.其中pfcount操作的总耗时分别为:4ms, 11ms, 7ms ; pfmerge操作耗时: 7ms, 8ms, 10ms

在组合条件少于等于4个的时候,耗时已经是比较小了.