程序员经验分享-hwhale

redis HyperLogLog原理

2023-11-19

假设现在有一个这样的需求，我们想要实时统计有多少用户访问我们的网站。一个简单的解决方案是用一个set集合来存储用户ID，然后计算任意时刻集合中不同ID的个数即为网站实时访问量。这是一种简单可行的做法，但是假如这个网页访问量很大加上随着时间推移存储集合数据所需要的内存空间越来越大，所需要的统计成本也越来越高。举个例子，假如用一个int类型来保存用户id,当有一千万用户的时候，总共需要38M内存。为了省内存我们还有另一种方案，位图法，我们用bitmap来保存数据，用户访问的时候我们就把对应的bit置1，最后统计这个bitmap总共有几个bit为1来统计访问量。这样，一千万用户就需要一千万个bit，约为1.2M大小。假如我要统计网站每天的用户访问量，那就意味着需要很多个bitmap，每个1.2M还是太大了。那有没有其它更省内存的解决方案呢？这时候我们需要另外一种算法来解决这个问题--hyperloglog算法。redis 中的hyperloglog，不管你的访问量有多大，几千万还是几个亿，最多只需要约12k内存！

首先介绍一下概率论中伯努利试验：伯努利试验（Bernoulli experiment）是指在同样的条件下重复地、相互独立地进行的一种随机试验，其特点是该随机试验只有两种可能结果：发生或者不发生。比如抛硬币，只有正面反面两种结果。
在介绍 HyperLogLog 之前，我们可以考虑这样一个游戏：不断抛硬币，直到第一次出现正面朝上，记录总共抛了多少次。

这个游戏中，假如在某次场景下，前3次都是反面，第4次正面，问这个概率是多少？这个很简单(\frac{1}{2})^{4},那么相当于平均需要玩 2^{4}=16次这个游戏才会出现一次这种场景。反过来说，如果某次游戏要抛到第4次才第一次出现正面朝上，那么可以推出这个游戏已经玩了16回。这个就是hyperloglog的基本原理。

然后我们用“1”来表示正面朝上，“0”表示反面朝上。用“0”，“1”组成的序列来表示某次游戏的结果，比如上面这个例子要抛4次的序列是：0 0 0 1。如果要抛5次就是：0 0 0 0 1，以此类推。

简单来看，其实 HyperLogLog 的基数统计就使用了这样的思想，通过二进制中 ‘1’出现的第一个位置来估算整体的数量。

举个例子，假设上面那个游戏一共玩了N次，其中最多的一次抛了6次硬币才结束，那么它的结果序列是：0 0 0 0 0 1。我们可以推算N=2^{6},即总共玩了64次这个游戏。

这种方法根据某次的结果来估算游戏进行的次数毫无疑问误差会比较大。我们可以对每次游戏的结果求平均值提高估算的精度。

假如依次进行时五次游戏，结果分别是：

  1. "0 0 1"，n1=3;
  2. "0 1'，n2=2;
  3. "1",n3=1;
  4. "0 0 0 0 1",n4=5;
  5. "0 1",n5=2.

 如果直接按n最大的一次计算的话，2^{5}，32次，误差很大。

如果我们按五次游戏的平均值来算，\frac{3+2+1+5+2}{5}，2^{3}=8，精度已经提高了很多。

我们还可以进一步提高精度，上面的均值用的是算术平均，现在我们改用调和平均来算一下.调和平均计算公式如下：

\frac{5}{\frac{1}{3}+\frac{1}{2}+1+\frac{1}{5}+\frac{1}{2}}，2^{2}=4，精度又近了一步，由于算术平均值容易受极值影响，在一些极端场景下误差会比较大。再举一个例子，两次游戏：

  1. “0 0 0 0 0 0 0 0 0 0 0 0 0 0 1”，n1=15;
  2. "1",n2=1;

 如果拿算术平均算的话是2^{8}=256，误差非常大；如果是拿调和平均算，\frac{2}{1+\frac{1}{15}}=2，2^{2}=4，误差就小了很多。

 

关于调和平均和算术平均，再举一个例子:两个人，一个月薪1千，一个月薪十万，那么两人的算术平均工资是50500，调和平均工资是2000，可以明显看出调和平均对消除极值的影响效果更好，所以redis中hyperloglog的实现也是用的调和平均。

我们来进一步优化我们的方案，假设进行了n次游戏，然后把n次游戏分成若干各组，然后根据每个组中的最大抛硬币次数来估算n的值。

比如，一共进行16次游戏，分成2个组，然后估算游戏次数：

第一组8次分别是：“1”, “0 1”,“01” ,“0 01”，"1","0 0 1","0 1","1"那么最大抛币次数是3；

第二组分别是“01”，“0 0 0 01”，“1”, “0 1”,“0 01” ,“0 1”，“0” “01”，最大抛币次数是5.

然后对3和5计算平均值是4，估算结果是2^{4}=16。当然，当数据量比较少的时候误差可能会比较大。根据伯努利大数定律，辛钦大数定律，切比雪夫大数定律，样本越多均值误差就越小。在redis的实现中，是总共分为16384个组。下面开始看一下redis中是如何实现的。

redis实现

redis中是通过pfadd 命令将所有元素参数添加到 HyperLogLog 数据结构中。假设用户ID为123456789的用户访问了www.HyperLogLog.com这个网站.我们可以用一下命令来进行统计

pfadd   www.HyperLogLog.com 123456789

然后redis开始对这个用户进行一次伯努利试验，具体做法通过一个hash函数来对123456789生成一个64bit的值，这里先假设是8888886666666660000，那么他的二进制表示是

0111101101011011101010110101001111110111010111110101000010100000

 

redis的hyperloglog数据结构中共有16384个桶来保存每次伯努利试验的结果。16384=2^{14}，因此需要14个bit来保存 。对于每次hash生成的64位的整形数，取高12位来作为hash桶索引，剩下的50个bit用来作为伯努利试验结果。

上面这个例子中，高12位是0111 1011 0101 10，十进制是7894。低50位的伯努利试验结果中第一次出现1是在第6位，那么它的意思是说这次试验是属于7894组，那么我们就要把这次试验结果6保存到哈希表第7894个桶中。当要把试验结果保存的时候，我们要先看一下这次试验结果6是不是比桶中保存的结果大，只有大于才保存，因为我是用各个分组中最大的结果来进行求均值。对于每次试验，结果最大就是50，2^{6}=64，就是用只需要用6个bit就可以保存这个试验结果。所以redis是用一个长度为16384*6个bit的数组来保存所有的试验结果，大小约为12k字节。

考虑这样一种场景，如果访问量只有几百几千，其实是不需要那么大空间来因为，因为这种情况下16384个桶会有很多桶是空的。比如有一千个连续的桶是空的，那么原本需要6000个bit去表示，占750字节。在redis里边其实只需两个字节就能保存这个信息。

ZERO

一个字节大小，高两位固定为00，剩下六位可以表示64个连续为0的空桶，
XZERO 两个字节大小，高两位固定为01，剩下的14位可以表示16384个连续的空桶
VAL 一个字节，高一位固定为1，中间五位表示值大小，剩下两位表示连续几个相同值的桶

 根据上表，如果要表示连续1000个空桶，可以用XZERO类型表示：01 000011 1110 1000，也就是0x01 00 03e8这个数。

以上只是hyperloglog的大致流程，redis在实际计算的时候是会加上一些修正的。

这个网站可以看hyperloglog的演示动画，可以加深理解：hyperloglog

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Redis

redis HyperLogLog原理 的相关文章

  • 在 Kubernetes/Openshift 中将客户端-服务器流量保持在同一区域的最佳方法？

    我们运行兼容 Kubernetes OKD 3 11 的本地 私有云集群 其中后端应用程序与用作缓存和 K V 存储的低延迟 Redis 数据库进行通信 新的架构设计将在两个地理上分布的数据中心 区域 之间平均划分工作节点 我们可以假设节点

  • 如何将node.js管道传输到redis？

    我有很多数据要插入 SET INCR 到redis DB 所以我正在寻找pipeline http redis io topics pipelining 质量插入 http redis io topics mass insert通过node

  • 无法启动redis.service：单元redis-server.service被屏蔽

    我在 ubuntu 16 04 上安装了 Redis 服务器 但是当我尝试使用启动redis服务时 sudo systemctl start redis 我收到消息 Failed to start redis service Unit re

  • 如何设置和获取Redis中存储的对象？

    我试图在 redis 中存储一个对象 当我获取该对象时 它似乎不起作用 I tried u User new u name blankman redis set test u x redis get test x name error 我想

  • Redis发布/订阅：查看当前订阅了哪些频道

    我目前有兴趣查看我拥有的 Redis 发布 订阅应用程序中订阅了哪些频道 当客户端连接到我们的服务器时 我们将它们注册到如下所示的通道 user user id 这样做的原因是我希望能够看到谁 在线 目前 我在不知道客户端是否在线的情况下盲

  • Lua中按字符分割字符串

    我有像这样的字符串 ABC DEF 我需要将它们分开 字符并将两个部分分别分配给一个变量 在 Ruby 中 我会这样做 a b ABC DEF split 显然Lua没有这么简单的方法 经过一番挖掘后 我找不到一种简短的方法来实现我所追求的

  • Java 将字节转换为二进制安全字符串

    我有一些以字节为单位的数据 我想将它们放入Redis中 但是Redis只接受二进制安全字符串 而我的数据有一些二进制非安全字节 那么如何将这些字节转换为二进制安全字符串以便将它们保存到 Redis 中呢 Base64 对我有用 但它使数据更

  • 2 个具有共享 Redis 依赖的 Helm Chart

    目前 我有 2 个 Helm Charts Chart A 和 Chart B Chart A 和 Chart B 对 Redis 实例具有相同的依赖关系 如Chart yaml file dependencies name redis v

  • StackExchange.Redis Get 函数抛出 TimeoutException

    我在用着StackExchange Redis与 C 和StackExchangeRedisCacheClient Get函数抛出以下异常 myCacheClient Database StringGet txtKey Text myCac

  • 如何将“.csv”数据文件导入Redis数据库

    如何将 csv 数据文件导入 Redis 数据库 csv 文件中包含 id 时间 纬度 经度 列 您能否向我建议导入 CSV 文件并能够执行空间查询的最佳方法 这是一个非常广泛的问题 因为我们不知道您想要什么数据结构 您期望什么查询等等 为

  • 如何使用 Redis 自动删除与模式匹配的键

    在我的 Redis DB 中 我有很多prefix

  • 在 Spring 4 中干掉通用的 RedisTemplate

    我读到你可以拥有 Autowired从 Spring 4 开始泛型 这太棒了 我有一个摘要RedisService我想参加的课程 Autowired一个通用的 RestTemplate 如下所示 public abstract class

  • 如何延长 django-redis 中的缓存 ttl（生存时间）？

    我正在使用 django 1 5 4 和 django redis 3 7 1 我想延长缓存的 ttl 生存时间 当我取回它时 这是示例代码 from django core cache import cache foo cache get

  • 超出 Redis 连接/缓冲区大小限制

    在对我们的应用程序服务器进行压力测试时 我们从 Redis 中得到以下异常 ServiceStack Redis RedisException 无法连接到 redis host 6379 处的 redis 实例 gt System Net

  • 为什么单个 Redis 实例不是线程安全的？

    https github com xetorthio jedis wiki Getting started https github com xetorthio jedis wiki Getting started 在多线程环境中使用Jed

  • Redis 在键过期时更新排序集

    我有一个 Redis 服务器 其中包含一组键值对和一个排序集 提供这些键值对的键的索引 键值对可以进入 已完成 状态 此时需要在 1 小时后删除它们 这可以通过在键上设置到期时间来简单地实现 但从排序集中清除它们似乎更成问题 我可以有一个过

  • 没有适用于机器人的 Laravel 会话

    我在大型 Laravel 项目和 Redis 存储方面遇到问题 我们将会话存储在 Redis 中 我们已经有 28GB 的 RAM 然而 它的运行速度仍然相对较快 达到了极限 因为我们有来自搜索引擎机器人的大量点击 每天超过 250 000

  • 批量将Dictionary中的数据设置到Redis中

    我正在使用 StackExchange Redis DB 插入键值对字典Batch如下 private static StackExchange Redis IDatabase database public void SetAll

  • 在 Rails 应用程序上将 HASH 保存到 Redis

    我刚刚开始使用 Redis 和 Rails 所以这可能是一个愚蠢的问题 我试图将哈希值保存到 Redis 服务器 但是当我检索它时 它只是一个字符串 IE hash field gt value field2 gt value2 redis

  • JedisPoolConfig 不可分配给 GenericObjectPoolConfig

    我有一个基于 Spring 的 Java Web 应用程序托管在 Heroku 上 我正在尝试使用 Redis 实现来利用 Spring 缓存抽象 当服务器启动时 我收到一条错误消息 Type redis clients jedis Jed

随机推荐

  • 区块链数字签名、验签，以及椭圆曲线算法JS库—elliptic的使用

    目录 一 简介 二 椭圆曲线密码elliptic 1 安装elliptic和js sha3 2 Keccak256 3 签名过程 一 简介 数字签名是一种将类似现实世界中物理签名 盖章

  • 更改element button 按钮颜色

    在全局的index scss里面改 显示时按钮样式 el button inblack 需要更改的按钮类型 background 060606 important border color 060606 important color ff

  • AppDomain一——基本原理

    一 问题的提出 技术一定是为了解决某个应用场景的问题而产生的 很多时候 我们都想使用 开发 USB式 热插拔 的应用 例如 开发一个WinForm应用 并且这个WinForm应用能允许开发人员定制扩展插件 我们不能关闭程序 在把新的dll替

  • vue项目部署方式:tomcat部署和nginx部署

    LINUX 发布 VUE项目 关于vue部署 1 nginx转发 一般项目前后端分离得话 都会用nginx作为反向代理转发的 因为项目要兼容ie9 使用axios发ajax请求的时候 不能通过CORS解决跨域的问题 所以尝试部署nginx作

  • 阿里云CDN架构接入WAF应用防火墙案例实践

    文章目录 1 网站架构变化 2 配置WAF应用防火墙 2 1 配置网站接入WAF防火墙 2 2 WAF防火墙生成CNAME地址 2 3 配置WAF防火墙HTTPS证书 2 4 WAF防火墙开启HTTP回源SLB 3 配置CDN加速器回源WA

  • 高德地图之地理编码

    首先申明是地理编码呢 地理编码 又称为地址匹配 是从已知的地址描述到对应的经纬度坐标的转换过程 该功能适用于根据用户输入的地址确认用户具体位置的场景 常用于配送人员根据用户输入的具体地址找地点 既地理编码 地址转坐标 下面一步步来看怎么实现

  • 面试题——Java中的锁

    文章目录 谈谈你对线程安全的理解 1 synchronized 关键字是怎么用的 1 1 构造方法可以使用 synchronized 关键字修饰么 1 2 使用 String 作为锁对象 会有什么问题 1 3 synchronized 的底

  • 单元测试到底是什么？应该怎么做？

    一 什么是单元测试 单元测试 unit testing 是指对软件中的最小可测试单元进行检查和验证 至于 单元 的大小或范围 并没有一个明确的标准 单元 可以是一个函数 方法 类 功能模块或者子系统 单元测试通常和白盒测试联系到一起 如果单

  • 微信小程序open-data组件功能调整

    这里我开源了一个微信小程序的案例 https gitee com xiaoshixiaoran wechat applet 相关后台接口我会有空用SSM重写一遍再挂上去 由于微信小程序官网在2021 12 27号发布了组件功能调整 原来的获

  • 1-100之间的所有能被3整除的数字的和，偶数和奇数的和 ，平均值

    1 求 1 100 之间的所有平均值 需要一个 sum 和的变量 还需要一个平均值average变量 var sum 0 var average 0 for var i 1 i lt 100 i sum sum i average sum

  • 配置SourceTree

    一 从官网下载安装包 二 添加账户 选择这一个 否则看不到private仓库 用户名是自己github的用户名 密码需要在github生成 在这个位置点击 配置权限后就成功了 然后输入密码就行

  • HarmonyOS-开发避坑指南——源码下载和编译，企业级项目实战讲解

    安装文件系统打包工具 运行 mkfs vfat 如果未找到该命令 需要安装 运行 mcopy 如果未找到该命令 需要安装 sudo apt get install dosfstools mtools 官方文档说明的两个文件系统打包工具sud

  • windows终端的bash配置

    个人记录 现在json文件中加入 guid 00000000 0000 0000 ba54 000000000002 closeOnExit true commandline PROGRAMFILES git usr bin bash ex

  • 牛客网左神算法中级班学习笔记（第三章）

    本文是牛客网左神算法中级班学习笔记 分析 宏观考虑 搞两个点A B 起始都在左上角 B往右走 走到最右边就往下走 A往下走 走到最下边就往右走 A B每次一起走一步 打印A B两点连线即可 用一个Boolean控制下 交替打印顺序 publ

  • java简易聊天程序

    目录 项目结构 TCP 窗体组成 server client properties 项目结构 TCP 窗体组成 server package cn itcast chat import javax swing import java awt

  • ChatGPTBox 沉浸式的感受ChatGPT带来的快感

    ChatGPT基础功能 1 自然流畅的对话 ChatGPT通过对海量对话数据的学习 具有自然流畅的对话能力 能够与用户进行逼真的自然语言交互 2 能够理解语境 ChatGPT能够理解语境 不仅能根据上下文生成回答 还能识别当前对话的主题 更

  • LabVIEW 读写和缩放音频文件

    LabVIEW 提供了多种方式来读取和写入 WAV 格式的音频文件 完成本模块后 您将能够使用位于 Programming Graphics Sound Sound Files 中的 Simple Read 和 Simple Write 用

  • 感性是什么意思

    感性是什么意思 2005 09 25 15 55 xinghuali 分类 恋爱 有人说自己很感性 不知到底是什么意思 人在这方面分两种 一种是理性 一种就是感性 理性是很理智的那种 就是做事都依据道理 不会冲动 而感性的就是凭着感觉来的那

  • 如何让学习变得有效率

    最近一直在反思这样一个问题 为什么我的学习如此的没有效率 来提高班近三年的时间 我几乎都在全日制学习中度过 可是我的速度并不快 原因在哪 在这里学习 米老师一遍遍强调 如何学习 如何打包 全局观才是我们在这里真正应该学的 可这些在我这些年的

  • redis HyperLogLog原理

    假设现在有一个这样的需求 我们想要实时统计有多少用户访问我们的网站 一个简单的解决方案是用一个set集合来存储用户ID 然后计算任意时刻集合中不同ID的个数即为网站实时访问量 这是一种简单可行的做法 但是假如这个网页访问量很大加上随着时间推

热门标签