redis 应用 4： HyperLogLog

我们先思考一个常见的业务问题：如果你负责开发维护一个大型的网站，有一天老板找产品经理要网站每个网页每天的 UV 数据，然后让你来开发这个统计模块，你会如何实现？

img
img

如果统计 PV 那非常好办，给每个网页一个独立的 Redis 计数器就可以了，这个计数器的 key 后缀加上当天的日期。这样来一个请求，incrby 一次，最终就可以统计出所有的 PV 数据。

但是 UV 不一样，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求每一个网页请求都需要带上用户的 ID，无论是登陆用户还是未登陆用户都需要一个唯一 ID 来标识。

你也许已经想到了一个简单的方案，那就是为每一个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时，我们使用 sadd 将用户 ID 塞进去就可以了。通过 scard 可以取出这个集合的大小，这个数字就是这个页面的 UV 数据。没错，这是一个非常简单的方案。

但是，如果你的页面访问量非常大，比如一个爆款页面几千万的 UV，你需要一个很大的 set 集合来统计，这就非常浪费空间。如果这样的页面很多，那所需要的存储空间是惊人的。为这样一个去重功能就耗费这样多的存储空间，值得么？其实老板需要的数据又不需要太精确，105w 和 106w 这两个数字对于老板们来说并没有多大区别，So，有没有更好的解决方案呢？

这就是本节要引入的一个解决方案，Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是 0.81%，这样的精确度已经可以满足上面的 UV 统计需求了。

HyperLogLog 数据结构是 Redis 的高级数据结构，它非常有用，但是令人感到意外的是，使用过它的人非常少。

使用方法

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

bash复制代码127.0.0.1:6379> pfadd codehole user1
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 1
127.0.0.1:6379> pfadd codehole user2
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 2
127.0.0.1:6379> pfadd codehole user3
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 3
127.0.0.1:6379> pfadd codehole user4
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 4
127.0.0.1:6379> pfadd codehole user5
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 5
127.0.0.1:6379> pfadd codehole user6
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 6
127.0.0.1:6379> pfadd codehole user7 user8 user9 user10
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 10

简单试了一下，发现还蛮精确的，一个没多也一个没少。接下来我们使用脚本，往里面灌更多的数据，看看它是否还可以继续精确下去，如果不能精确，差距有多大。人生苦短，我用 Python！Python 脚本走起来！😄

py复制代码# coding: utf-8

import redis

client = redis.StrictRedis()
for i in range(1000):
    client.pfadd("codehole", "user%d" % i)
    total = client.pfcount("codehole")
    if total != i+1:
        print total, i+1
        break

当然 Java 也不错，大同小异，下面是 Java 版本：

java复制代码public class PfTest {
  public static void main(String[] args) {
    Jedis jedis = new Jedis();
    for (int i = 0; i < 1000; i++) {
      jedis.pfadd("codehole", "user" + i);
      long total = jedis.pfcount("codehole");
      if (total != i + 1) {
        System.out.printf("%d %d\n", total, i + 1);
        break;
      }
    }
    jedis.close();
  }
}

我们来看下输出：

markdown复制代码> python pftest.py
99 100

当我们加入第 100 个元素时，结果开始出现了不一致。接下来我们将数据增加到 10w 个，看看总量差距有多大。

css复制代码# coding: utf-8

import redis

client = redis.StrictRedis()
for i in range(100000):
    client.pfadd("codehole", "user%d" % i)
print 100000, client.pfcount("codehole")

Java 版：

java复制代码public class JedisTest {
  public static void main(String[] args) {
    Jedis jedis = new Jedis();
    for (int i = 0; i < 100000; i++) {
      jedis.pfadd("codehole", "user" + i);
    }
    long total = jedis.pfcount("codehole");
    System.out.printf("%d %d\n", 100000, total);
    jedis.close();
  }
}

跑了约半分钟，我们看输出：

markdown复制代码> python pftest.py
100000 99723

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

pfadd 这个 pf 是什么意思？

它是 HyperLogLog 这个数据结构的发明人 Philippe Flajolet 的首字母缩写，老师觉得他发型很酷，看起来是个佛系教授。

img
img

pfmerge 适合什么场合用？

HyperLogLog 除了上面的 pfadd 和 pfcount 之外，还提供了第三个指令 pfmerge，用于将多个 pf 计数值累加在一起形成一个新的 pf 值。

比如在网站中我们有两个内容差不多的页面，运营说需要这两个页面的数据进行合并。其中页面的 UV 访问量也需要合并，那这个时候 pfmerge 就可以派上用场了。

注意事项

HyperLogLog 这个数据结构不是免费的，不是说使用这个数据结构要花钱，它需要占据一定 12k 的存储空间，所以它不适合统计单个用户相关的数据。如果你的用户上亿，可以算算，这个空间成本是非常惊人的。但是相比 set 存储方案，HyperLogLog 所使用的空间那真是可以使用千斤对比四两来形容了。

不过你也不必过于担心，因为 Redis 对 HyperLogLog 的存储进行了优化，在计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，才会占用 12k 的空间。

HyperLogLog 实现原理

HyperLogLog 的使用非常简单，但是实现原理比较复杂，如果读者没有特别的兴趣，下面的内容暂时可以跳过不看。

为了方便理解 HyperLogLog 的内部实现原理，我画了下面这张图

img
img

这张图的意思是，给定一系列的随机整数，我们记录下低位连续零位的最大长度 k，通过这个 k 值可以估算出随机数的数量。 首先不问为什么，我们编写代码做一个实验，观察一下随机整数的数量和 k 值的关系。

py复制代码import math
import random

# 算低位零的个数
def low_zeros(value):
    for i in xrange(1, 32):
        if value >> i << i != value:
            break
    return i - 1


# 通过随机数记录最大的低位零的个数
class BitKeeper(object):

    def __init__(self):
        self.maxbits = 0

    def random(self):
        value = random.randint(0, 2**32-1)
        bits = low_zeros(value)
        if bits > self.maxbits:
            self.maxbits = bits


class Experiment(object):

    def __init__(self, n):
        self.n = n
        self.keeper = BitKeeper()

    def do(self):
        for i in range(self.n):
            self.keeper.random()

    def debug(self):
        print self.n, '%.2f' % math.log(self.n, 2), self.keeper.maxbits


for i in range(1000, 100000, 100):
    exp = Experiment(i)
    exp.do()
    exp.debug()

Java 版：

java复制代码public class PfTest {

  static class BitKeeper {
    private int maxbits;

    public void random() {
      long value = ThreadLocalRandom.current().nextLong(2L << 32);
      int bits = lowZeros(value);
      if (bits > this.maxbits) {
        this.maxbits = bits;
      }
    }

    private int lowZeros(long value) {
      int i = 1;
      for (; i < 32; i++) {
        if (value >> i << i != value) {
          break;
        }
      }
      return i - 1;
    }
  }

  static class Experiment {
    private int n;
    private BitKeeper keeper;

    public Experiment(int n) {
      this.n = n;
      this.keeper = new BitKeeper();
    }

    public void work() {
      for (int i = 0; i < n; i++) {
        this.keeper.random();
      }
    }

    public void debug() {
      System.out.printf("%d %.2f %d\n", this.n, Math.log(this.n) / Math.log(2), this.keeper.maxbits);
    }
  }

  public static void main(String[] args) {
    for (int i = 1000; i < 100000; i += 100) {
      Experiment exp = new Experiment(i);
      exp.work();
      exp.debug();
    }
  }

}

运行观察输出：

复制代码36400 15.15 13
36500 15.16 16
36600 15.16 13
36700 15.16 14
36800 15.17 15
36900 15.17 18
37000 15.18 16
37100 15.18 15
37200 15.18 13
37300 15.19 14
37400 15.19 16
37500 15.19 14
37600 15.20 15

通过这实验可以发现 K 和 N 的对数之间存在显著的线性相关性：

ini
复制代码N=2^K  # 约等于

如果 N 介于 2^K 和 2^(K+1) 之间，用这种方式估计的值都等于 2^K，这明显是不合理的。这里可以采用多个 BitKeeper，然后进行加权估计，就可以得到一个比较准确的值。

py复制代码import math
import random

def low_zeros(value):
    for i in xrange(1, 32):
        if value >> i << i != value:
            break
    return i - 1


class BitKeeper(object):

    def __init__(self):
        self.maxbits = 0

    def random(self, m):
        bits = low_zeros(m)
        if bits > self.maxbits:
            self.maxbits = bits


class Experiment(object):

    def __init__(self, n, k=1024):
        self.n = n
        self.k = k
        self.keepers = [BitKeeper() for i in range(k)]

    def do(self):
        for i in range(self.n):
            m = random.randint(0, 1<<32-1)
            # 确保同一个整数被分配到同一个桶里面，摘取高位后取模
            keeper = self.keepers[((m & 0xfff0000) >> 16) % len(self.keepers)]
            keeper.random(m)

    def estimate(self):
        sumbits_inverse = 0  # 零位数倒数
        for keeper in self.keepers:
            sumbits_inverse += 1.0/float(keeper.maxbits)
        avgbits = float(self.k)/sumbits_inverse  # 平均零位数
        return 2**avgbits * self.k  # 根据桶的数量对估计值进行放大


for i in range(100000, 1000000, 100000):
    exp = Experiment(i)
    exp.do()
    est = exp.estimate()
    print i, '%.2f' % est, '%.2f' % (abs(est-i) / i)

下面是 Java 版：

java复制代码public class PfTest {

  static class BitKeeper {
    private int maxbits;

    public void random(long value) {
      int bits = lowZeros(value);
      if (bits > this.maxbits) {
        this.maxbits = bits;
      }
    }

    private int lowZeros(long value) {
      int i = 1;
      for (; i < 32; i++) {
        if (value >> i << i != value) {
          break;
        }
      }
      return i - 1;
    }
  }

  static class Experiment {
    private int n;
    private int k;
    private BitKeeper[] keepers;

    public Experiment(int n) {
      this(n, 1024);
    }

    public Experiment(int n, int k) {
      this.n = n;
      this.k = k;
      this.keepers = new BitKeeper[k];
      for (int i = 0; i < k; i++) {
        this.keepers[i] = new BitKeeper();
      }
    }

    public void work() {
      for (int i = 0; i < this.n; i++) {
        long m = ThreadLocalRandom.current().nextLong(1L << 32);
        BitKeeper keeper = keepers[(int) (((m & 0xfff0000) >> 16) % keepers.length)];
        keeper.random(m);
      }
    }

    public double estimate() {
      double sumbitsInverse = 0.0;
      for (BitKeeper keeper : keepers) {
        sumbitsInverse += 1.0 / (float) keeper.maxbits;
      }
      double avgBits = (float) keepers.length / sumbitsInverse;
      return Math.pow(2, avgBits) * this.k;
    }
  }

  public static void main(String[] args) {
    for (int i = 100000; i < 1000000; i += 100000) {
      Experiment exp = new Experiment(i);
      exp.work();
      double est = exp.estimate();
      System.out.printf("%d %.2f %.2f\n", i, est, Math.abs(est - i) / i);
    }
  }

}

代码中分了 1024 个桶，计算平均数使用了调和平均 (倒数的平均)。普通的平均法可能因为个别离群值对平均结果产生较大的影响，调和平均可以有效平滑离群值的影响。

img
img

观察脚本的输出，误差率控制在百分比个位数：

复制代码100000 97287.38 0.03
200000 189369.02 0.05
300000 287770.04 0.04
400000 401233.52 0.00
500000 491704.97 0.02
600000 604233.92 0.01
700000 721127.67 0.03
800000 832308.12 0.04
900000 870954.86 0.03
1000000 1075497.64 0.08

真实的 HyperLogLog 要比上面的示例代码更加复杂一些，也更加精确一些。上面的这个算法在随机次数很少的情况下会出现除零错误，因为 maxbits=0 是不可以求倒数的。

pf 的内存占用为什么是 12k？

我们在上面的算法中使用了 1024 个桶进行独立计数，不过在 Redis 的 HyperLogLog 实现中用到的是 16384 个桶，也就是 2^14，每个桶的 maxbits 需要 6 个 bits 来存储，最大可以表示 maxbits=63，于是总共占用内存就是2^14 * 6 / 8 = 12k字节。

本文由 mdnice 多平台发布

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/101977.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Axure RP仿QQ音乐app高保真原型图交互模板源文件

Axure RP仿QQ音乐app高保真原型图交互模板源文件

Axure RP仿QQ音乐app高保真原型图交互模板源文件。本套素材模板的机型选择华为的mate30&#xff0c;在尺寸和风格方面&#xff0c;采用标准化制作方案&#xff0c;这样做出来的原型图模板显示效果非常优秀。 原型中使用大量的动态面板、中继器、母版&#xff0c;涵盖Axure中技…
阅读更多...
【笔记】PyCharm快捷键大全

【笔记】PyCharm快捷键大全

PyCharm是一种Python集成开发环境&#xff08;IDE&#xff09;&#xff0c;由JetBrains公司开发。它被认为是Python开发中最强大、最流行的IDE之一。PyCharm具有完整的Python开发工具链&#xff0c;包括先进的代码编辑器、代码分析工具、集成的调试器、版本控制系统集成、自动化…
阅读更多...
Flink 如何处理反压?

Flink 如何处理反压?

分析&回答 什么是反压&#xff08;backpressure&#xff09; 反压通常是从某个节点传导至数据源并降低数据源&#xff08;比如 Kafka consumer&#xff09;的摄入速率。反压意味着数据管道中某个节点成为瓶颈&#xff0c;处理速率跟不上上游发送数据的速率&#xff0c;而…
阅读更多...
关于Comparable、Comparator接口返回值决定顺序的问题

关于Comparable、Comparator接口返回值决定顺序的问题

Comparable和Comparator接口都是实现集合中元素的比较、排序的&#xff0c;下面先简单介绍下他们的用法。 1. 使用示例 public class Person {private String name;private Integer age;public Person() {}public Person(String name, Integer age) {this.name name;this.ag…
阅读更多...
MySQL高阶语句（三）

MySQL高阶语句（三）

一、NULL值 在 SQL 语句使用过程中&#xff0c;经常会碰到 NULL 这几个字符。通常使用 NULL 来表示缺失 的值&#xff0c;也就是在表中该字段是没有值的。如果在创建表时&#xff0c;限制某些字段不为空&#xff0c;则可以使用 NOT NULL 关键字&#xff0c;不使用则默认可以为空…
阅读更多...
自动化运维工具Ansible之playbooks剧本

自动化运维工具Ansible之playbooks剧本

自动化运维工具Ansible之playbooks剧本 一、playbooks1.playbooks简述2.playbooks剧本格式3.playbooks组成部分 二、实例1.编写脚本2.运行playbook3.定义、引用变量4.指定远程主机sudo切换用户5.when条件判断6.迭代7.Templates 模块8.tags 模块9.Roles 模块 三、编写应用模块1.…
阅读更多...
Oracle数据传输加密方法

Oracle数据传输加密方法

服务器端“dbhome_1\NETWORK\ADMIN\”sqlnet.ora文件中添加 SQLNET.ENCRYPTION_SERVER requested SQLNET.ENCRYPTION_TYPES_SERVER (RC4_256) 添加后新的链接即刻生效&#xff0c;服务器无需重新启动。 也可以通过Net manager管理工具添加 各个参数含义如下&#xff1a; 是…
阅读更多...
uniapp 配置小程序分包

uniapp 配置小程序分包

分包可以减少小程序首次启动时的加载时间 分包页面&#xff08;例如&#xff1a;商品详情页、商品列表页&#xff09;。在 uni-app 项目中&#xff0c;配置分包的步骤如下&#xff1a; 1、右键点击根目录&#xff0c;新建&#xff0c;点击创建分包的根目录&#xff0c;命名为 …
阅读更多...
字符串哈希

字符串哈希

字符串前缀哈希法 str "ABCABCDEHGJK" 预处理每一个前缀的哈希值,如 : h[0] 0; h[1] "A"的哈希值 h[2] "AB"的哈希值 h[3] "ABC"的哈希值 h[4] "ABCA"的哈希值 问题 : 如何定义一个前缀的哈希值 : 将字符串看…
阅读更多...
北京APP外包开发团队人员构成

北京APP外包开发团队人员构成

下面是一个标准的APP开发团队构成&#xff0c;但具体的人员规模和角色可能会根据项目的规模和需求进行调整。例如&#xff0c;一些小型项目或初创公司可能将一些角色合并&#xff0c;或者聘请外包团队来完成部分工作。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公…
阅读更多...
IDEA maven上传速度很慢、解决办法

IDEA maven上传速度很慢、解决办法

maven上传的速度很慢&#xff0c;排除网络原因&#xff0c;需要检查配置 一、项目配置 以下针对于maven仓库不在C盘的情况&#xff1a; File | Settings | Build, Execution, Deployment | Build Tools | Maven 以IDEA为例&#xff0c;打开 File&#xff08;文件&#xff09;…
阅读更多...
WGCNA分析教程 | 代码四

WGCNA分析教程 | 代码四

写在前面 WGCNA的教程&#xff0c;我们在前期的推文中已经退出好久了。今天在结合前期的教程的进行优化一下。只是在现有的教程基础上&#xff0c;进行修改。其他的其他并无改变。 前期WGCNA教程 WGCNA分析 | 全流程分析代码 | 代码一 WGCNA分析 | 全流程分析代码 | 代码二 …
阅读更多...
自然语言处理(二)：近似训练

自然语言处理(二)：近似训练

近似训练 近似训练&#xff08;Approximate Training&#xff09;是指在机器学习中使用近似的方法来训练模型&#xff0c;以降低计算复杂度或提高训练效率。这种方法通常用于处理大规模数据集或复杂模型&#xff0c;其中精确的训练算法可能过于耗时或计算资源不足。 近似训练…
阅读更多...
自定义创建项目

自定义创建项目

基于VueCli自定义创建项目 1.Eslint代码规范 代码规范:一套写代码的约定规则。 比如 赋值符号的左右是否需要空格 一句话结束是否要加&#xff1b; 正规的团队 需要统一的编码风格 https://standardjs.com/rules-zhcn.html 规则查找 https://zh-hans.eslint.org/docs/late…
阅读更多...
mysql:[Some non-transactional changed tables couldn‘t be rolled back]不支持事务

mysql:[Some non-transactional changed tables couldn‘t be rolled back]不支持事务

1. mysql创建表时默认引擎MyIsam&#xff0c;因此不支持事务的操作&#xff1b; 2. 修改mysql的默认引擎&#xff0c;可以使用show engine命令查看支持的引擎&#xff1a; 【my.conf详情说明】my.cnf配置文件注释详解_xiaolin01999的博客-CSDN博客 3. 原来使用MyIsam创建的表…
阅读更多...
微信小程序开发教学系列（12）- 实战项目案例

微信小程序开发教学系列（12）- 实战项目案例

十二、实战项目案例 本章将通过一个简单的实战项目案例来帮助读者巩固之前学习到的知识。我们将搭建一个名为“ToDoList”的微信小程序&#xff0c;实现一个简单的任务清单功能。 项目介绍 ToDoList是一个用于记录和管理任务的小程序。用户可以添加、编辑、完成和删除任务&a…
阅读更多...
springboot web开发springmvc自动配置原理

springboot web开发springmvc自动配置原理

前言 我们也知道springboot启用springmvc基本不用做什么配置可以很方便就使用了但是不了解原理,开发过程中遇到点问题估计就比较头疼,不管了解的深不深入,先巴拉一番再说… 下面我们先看看官网…我的版本是2.3.2版本,发现官网改动也比较大…不同版本自己巴拉下吧,结构虽然变化…
阅读更多...
Lesson4-2:OpenCV图像特征提取与描述---Harris和Shi-Tomas算法

Lesson4-2:OpenCV图像特征提取与描述---Harris和Shi-Tomas算法

学习目标 理解Harris和Shi-Tomasi算法的原理能够利用Harris和Shi-Tomasi进行角点检测 1 Harris角点检测 1.1 原理 H a r r i s Harris Harris角点检测的思想是通过图像的局部的小窗口观察图像&#xff0c;角点的特征是窗口沿任意方向移动都会导致图像灰度的明显变化&#xff…
阅读更多...
java实现粤语歌曲0243填词法

java实现粤语歌曲0243填词法

粤语歌曲填词法 一、前言 转化成数字歌。对每个音符&#xff0c;提供配合广东话声调的字&#xff0c;选出成为歌词。可以在网上创作&#xff0c;或下载到自己电脑中使用。 简谱 3656536&#xff0c;歌词 落花满天蔽月光。 唱起来配合乐曲音调。这叫做‘叶韵’&#xff0c;又叫…
阅读更多...
UE4 植物生长

UE4 植物生长

这个可以改变SplineMesh朝向
阅读更多...
最新文章

Copyright @ 2022~2023