hyperloglog实战 - 你的过滤器选对了吗?

2024-03-11 08:58

本文主要是介绍hyperloglog实战 - 你的过滤器选对了吗?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、业务背景

最近接到一个统计需求,为了监控视频效果,我们每次浏览视频都要记录uv。当量小的时候,没有问题,随着用户量的的增长,占用空间大的问题开始暴露。假如有1000万用户,采用set结构记录UV,我们只存储int类型的用户id,1000万*4byte/1024kb/1024mb=38.14G,这是一个视频一天的数据,很明显存储成本太高,必须找到一种既能满足需求,又很少占用空间的方案。

二、技术选型

经过调研,找到了以下几种技术方案,下面一一分析。

1、flink的state去重

MapState 是 Flink 中 KeyedState 的状态类型,这种方式实现去重是一个精确的去重结果,将设备 ID 保存在 MapState 中。而state 直接存放在 RocksDB 中,RocksDB是类似HBase的kv数据库,本地性能好,维护较大的状态集合问题不大。

这种方案的优点是数据准确定非常高,确定是随着state增长,对checkpoint效率和成功率都有挑战,而且需要定期清理state,无发做到长时间数据去重。

2、bitmap去重

bitmap的原理是使用一个bit来存放某种状态,适用于大规模数据,但是状态又不是很多的情况。假设使用redis的bitmap,首先将用户id通过算法转换为整数,这个整数就是偏移量,每个id占用一位,1是访问过。

这个方案的优点是占用内存小,查询方便,效率高,能够精确去重,缺点是需要计算偏移量,如果偏移量过大就占用很多空间。

3、布隆过滤器

布隆过滤器是由一个很长的二进制向量和一系列随机映射函数。它适合过滤不存的元素场景,如果判断不存在则一定不存在,如果判断存在,则有一定概率不存在。计算puv时,用一个变量计数,用这个过滤器判断计数器是否增加。

这个方案的优点是空间效率高,查询时间短。缺点是有误判率,多个维度时,初始分配的空间一样,会占用较大空间。

4、hyperloglog

hyperloglog是一种算法,目的是做基数统计,可以预估一个集合中不同数据的个数,它不会保存元数据,只记录数量,支持输入非常大体积的数据量。在 redis 中也存在 hyperloglog 类型的结构,能够使用 12k 的内存,允许误差在 0.81%的情况下统计 2^64 个数据。

这个方案的有点事占用空间小,空间不会随着数量的变大而无线变大。缺点是有0.81%的标准误差率,只能用来计数,不能用来查询元素。

综合上面的方案,对于1000万用户,统计上亿视频,允许一定误差率的场景,方案 4 更加合适,内存能够控制在12k以内,查询速度也能满足需求。

三、hyperloglog 原理分析

1、原理说明

HyperLogLog 算法来源于论文 HyperLogLog the analysis of a near-optimal cardinality estimation algorithm,想要了解 HLL 的原理,先要从伯努利试验说起,伯努利实验说的是抛硬币的事。一次伯努利实验相当于抛硬币,不管抛多少次只要出现一个正面,就称为一次伯努利实验。

我们用 k 来表示每次抛硬币的次数,n 表示第几次抛的硬币,用 k_max 来表示抛硬币的最高次数,最终根据估算发现 n 和 k_max 存在的关系是 n=2^(k_max),但同时我们也发现了另一个问题当试验次数很小的时候,这种估算方法的误差会很大,例如我们进行以下 3 次实验:

  • 第 1 次试验:抛 3 次出现正面,此时 k=3,n=1;
  • 第 2 次试验:抛 2 次出现正面,此时 k=2,n=2;
  • 第 3 次试验:抛 6 次出现正面,此时 k=6,n=3。

对于这三组实验来说,k_max=6,n=3,但放入估算公式明显 3≠2^6。为了解决这个问题 HLL 引入了分桶算法和调和平均数来使这个算法更接近真实情况。

分桶算法是指把原来的数据平均分为 m 份,在每段中求平均数在乘以 m,以此来消减因偶然性带来的误差,提高预估的准确性,简单来说就是把一份数据分为多份,把一轮计算,分为多轮计算。

而调和平均数指的是使用平均数的优化算法,而非直接使用平均数。

例如小明的月工资是 1000 元,而小王的月工资是 100000 元,如果直接取平均数,那小明的平均工资就变成了 (1000+100000)/2=50500‬ 元,这显然是不准确的,而使用调和平均数算法计算的结果是 2/(1/1000+1/100000)≈1998 元,显然此算法更符合实际平均数。

2、具体的计算流程

这是hyperloglog的在线计算网站: http://content.research.neustar.biz/blog/hll.html

hy.png

  • 第一步对输入的值3,157,369进行hash获得值2,297,270,962,hash的值转二进制 11100000101001010101001011101110100111010
  • 第二步二进制数的最后6位设置为桶的index(长16,宽4的矩形),为什么是6位呢?因为2的6次方正好等于矩阵数组的个数64,从图中看出index是50,红色的方块是要放入的位置
  • 第三步获取从右向左的第一个1,如图看到是10,也就是2
  • 最后一步多个不同的值,就被分散到不同的桶中去了,且每个桶有其 k_max。然后当要统计出总共有多少的时候,就是一次估算。最终结合所有桶中的 k_max,代入估算公式,便能得出估算值。

四、hyperloglog redis实战

在 Redis 的 HyperLogLog 实现中用到的是 16384 个桶,也就是 2^14,每个桶的 maxbits 需要 6 个 bits 来存储,最大可以表示 maxbits=63,于是总共占用内存就是2^14 * 6 / 8 = 12k字节。\

HyperLogLog 提供了两个指令 pfadd 和 pfcount,根据字面意义很好理解,一个是增加计数,一个是获取计数。pfadd 用法和 set 集合的 sadd 是一样的,来一个用户 ID,就将用户 ID 塞进去就是。pfcount 和 scard 用法是一样的,直接获取计数值。

127.0.0.1:6379> PFADD runoobkey "redis"(integer) 1127.0.0.1:6379> PFADD runoobkey "mongodb"(integer) 1127.0.0.1:6379> PFADD runoobkey "mysql"(integer) 1127.0.0.1:6379> PFCOUNT runoobkey

我们将数据增加到 10w 个,看看总量差距有多大。

public class Test {public static void main(String[] args) {//连接本地的redisJedis jedis = new Jedis("localhost");System.out.println(jedis.getClient().getPort());System.out.println("连接本地的Redis服务器成功");for (int i = 0; i < 100000; i++) {jedis.pfadd("my-user-uv", "user" + i);}long total = jedis.pfcount("my-user-uv");System.out.printf("%d %d\n", 100000, total);jedis.close();}}

差了 275 个,按百分比是 0.275%,对于上面的 UV 统计需求来说,误差率也不算高。然后我们把上面的脚本再跑一边,也就相当于将数据重复加入一边,查看输出,可以发现,pfcount 的结果没有任何改变,还是 99725,说明它确实具备去重功能。

参考资料

  • 优秀的基数统计算
  • Redis HyperLoglog、Bloom Filter 、Bitmap

(转自:https://juejin.cn/post/6992890603503632415)

这篇关于hyperloglog实战 - 你的过滤器选对了吗?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/797334

相关文章

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Golang使用minio替代文件系统的实战教程

《Golang使用minio替代文件系统的实战教程》本文讨论项目开发中直接文件系统的限制或不足,接着介绍Minio对象存储的优势,同时给出Golang的实际示例代码,包括初始化客户端、读取minio对... 目录文件系统 vs Minio文件系统不足:对象存储:miniogolang连接Minio配置Min

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

Servlet中配置和使用过滤器的步骤记录

《Servlet中配置和使用过滤器的步骤记录》:本文主要介绍在Servlet中配置和使用过滤器的方法,包括创建过滤器类、配置过滤器以及在Web应用中使用过滤器等步骤,文中通过代码介绍的非常详细,需... 目录创建过滤器类配置过滤器使用过滤器总结在Servlet中配置和使用过滤器主要包括创建过滤器类、配置过滤

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

滚雪球学Java(87):Java事务处理:JDBC的ACID属性与实战技巧!真有两下子!

咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE啦,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~ 🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!! 环境说明:Windows 10

springboot实战学习(1)(开发模式与环境)

目录 一、实战学习的引言 (1)前后端的大致学习模块 (2)后端 (3)前端 二、开发模式 一、实战学习的引言 (1)前后端的大致学习模块 (2)后端 Validation:做参数校验Mybatis:做数据库的操作Redis:做缓存Junit:单元测试项目部署:springboot项目部署相关的知识 (3)前端 Vite:Vue项目的脚手架Router:路由Pina:状态管理Eleme