Categories: 技术原创

Redis面试八股文-HyperLogLog类型和实战应用(超大数据量基数统计)

HyperLogLog 是什么?

HyperLogLog 是一种基数估算算法, 并非redis独有。
目的是做基数统计,故不是集合,不会保存元数据,只记录数量而不是数值。
消耗空间极小,支持输入非常大体积的数据量。

具体应用场景

说人话,HyperLogLog能用来干啥?

假设我们手机APP需要统计登录页、注册输入账号密码页、填写基本资料页、填写附加资料页、广告推荐页这五个页面的PV和UV。
PV好办,在Redis中直接放5个key,咱们访问哪个页面一次加一次即可;可是UV不行呐,需要区分不同的用户的访问,同一个用户访问1000次都是加1,需要去重。
假设此时我们的用户量非常大,比如说我们先来它一个小目标的,此时以Redis的Hash数据结构为例,我们将0-100000000的数值作为key,value为空,写入Redis,需要占用7.46GB的内存。
是不是非常的不经济?5个统计就需要37.3GB的内存空间,成本炸裂。

如果此时产品经理告诉你不需要绝对精确,允许一定的误差,那么我们就可以使用HyperLogLog这个数据结构来实现UV统计了。

定义5个key分别存储5个页面的访问估算数据

1
2
3
4
5
6
7
pageKeys := []string{
  "RegisterAndLoginPageUVKey",
  "RegisterPageUVKey",
  "BasicProfilePageUVKey",
  "AdditionalProfilePageUVKey",
  "RecommendPageUVKey",
}

每个key造一亿个不同的访客ID

使用二维数组每两千个ID一组,通过pfadd写入对应key

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
visitorIDArray := [5][]string{}

for i := 0; i < 500000000; i++ {
  indexLevel1 := i % 5
  visitorIDArray[indexLevel1] = append(visitorIDArray[indexLevel1], strconv.Itoa(i))
  if i%10000 == 0 && i != 0 {
      for temp, visitors := range visitorIDArray {
          _, err := redisClient.PFAdd(context.Background(), pageKeys[temp], visitors).Result()
          if err != nil {
                  log.Fatalln(err.Error())
          }
      }
      visitorIDArray = [5][]string{}
      fmt.Println("offset:", i)
  }
}

if len(visitorIDArray[1]) > 0 {
  for temp, visitors := range visitorIDArray {
      _, err := redisClient.PFAdd(context.Background(), pageKeys[temp], visitors).Result()
      if err != nil {
          log.Fatalln(err.Error())
      }
  }
  visitorIDArray = [5][]string{}
}

读取数据

通过pfcount计算每个key的估算基数值

1
2
3
4
5
6
7
8
for _, key := range pageKeys {
  count, err := redisClient.PFCount(context.Background(), key).Result()
  if err != nil {
      log.Fatalln(err.Error())
  }

  fmt.Println(key, ":", count)
}

运行结果:

1
2
3
4
5
RegisterAndLoginPageUVKey : 100528967
RegisterPageUVKey : 100506461
BasicProfilePageUVKey : 100966386
AdditionalProfilePageUVKey : 100068496
RecommendPageUVKey : 100136669

从结果可以看到,每个key的估算值都不是非常准确的100000000,但是误差基本都在1%左右,偶尔高于标准误差0.81%。
但是相比于35GB的内存占用,使用HyperLogLog仅用了60KB内存,而且误差也在可接受范围内,还要啥自行车?

计算多个key的总数

填写基本资料页、填写附加资料页两个key做合并计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
  result, err := redisClient.PFMerge(context.Background(), "ProfilePageKey", pageKeys[2], pageKeys[3]).Result()
  if err != nil {
      log.Fatalln(err.Error())
  }

  fmt.Println(result)

  count, err := redisClient.PFCount(context.Background(), "ProfilePageKey").Result()
  if err != nil {
      log.Fatalln(err.Error())
  }

  fmt.Println(count)

运行结果:

1
2
OK
201188552

可以看到并不是两个key值的简单相加,误差近一步增大到了1.1%,但还是在可接受范围内。

总结

1. 根据实践demo可知,在允许误差的情况下,HyperLogLog对于超大量的数据技术计算非常好用,误差基本在0.81%的标准误差范围内,偶尔误差超过1%,但也在可接受范围内,而且对于类似UV这种超大体量但用处不是那么大的数据来说,节约的内存成本是非常可观的。

程序猿老龚(龚杰洪)原创,版权所有,转载请注明出处.

龚杰洪

Recent Posts

GOLANG面试八股文-并发控制

背景 协程A执行过程中需要创建…

1 年 ago

MYSQL面试八股文-常见面试问题和答案整理二

索引B+树的理解和坑 MYSQ…

1 年 ago

MYSQL面试八股文-InnoDB的MVCC实现机制

背景 什么是MVCC? MVC…

1 年 ago

MYSQL面试八股文-索引类型和使用相关总结

什么是索引? 索引是一种用于加…

1 年 ago

MYSQL面试八股文-索引优化之全文索引(解决文本搜索问题)

背景:为什么要有全文索引 在当…

1 年 ago