Redis精确去重计数方法（咆哮位图）
前言
如果要统计一篇文章的阅读量，可以直接使用 Redis 的 incr 指令来完成。如果要求阅读量必须按用户去重，那就可以使用 set 来记录阅读了这篇文章的所有用户 id，获取 set 集合的长度就是去重阅读量。但是如果爆款文章阅读量太大，set 会浪费太多存储空间。这时候我们就要使用 Redis 提供的 HyperLogLog 数据结构来代替 set，它只会占用最多 12k 的存储空间就可以完成海量的去重统计。但是它牺牲了准确度，它是模糊计数，误差率约为 0.81%。
那么有没有一种不怎么浪费空间的精确计数方法呢？我们首先想到的就是位图，可以使用位图的一个位来表示一个用户id。如果一个用户id是32字节，那么使用位图就只需要占用 1/256 的空间就可以完成精确计数。但是如何将用户id映射到位图的位置呢？如果用户id是连续的整数这很好办，但是通常用户系统的用户id并不是整数，而是字符串或者是有一定随机性的大整数。
我们可以强行给每个用户id赋予一个整数序列，然后将用户id和整数的对应关系存在redis中。
$next_user_id = incr user_id_seq set user_id_xxx $next_user_id $next_user_id = incr user_id_seq set user_id_yyy $next_user_id $next_user_id = incr user_id_seq set user_id_zzz $next_user_id
这里你也许会提出疑问，你说是为了节省空间，这里存储用户id和整数的映射关系就不浪费空间了么？这个问题提的很好，但是同时我们也要看到这个映射关系是可以复用的，它可以统计所有文章的阅读量，还可以统计签到用户的日活、月活，还可以用在很多其它的需要用户去重的统计场合中。所谓「功在当代，利在千秋」就是这个意思。
有了这个映射关系，我们就很容易构造出每一篇文章的阅读打点位图，来一个用户，就将相应位图中相应的位置为一。如果位从0变成1，那么就可以给阅读数加1。这样就可以很方便的获得文章的阅读数。
而且我们还可以动态计算阅读了两篇文章的公共用户量有多少？将两个位图做一下 AND 计算，然后统计位图中位 1 的个数。同样，还可以有 OR 计算、XOR 计算等等都是可行的。
问题又来了！Redis 的位图是密集位图，什么意思呢？如果有一个很大的位图，它只有最后一个位是 1，其它都是零，这个位图还是会占用全部的内存空间，这就不是一般的浪费了。你可以想象大部分文章的阅读量都不大，但是它们的占用空间却是很接近的，和哪些爆款文章占据的内存差不多。
看来这个方案行不通，我们需要想想其它方案！这时咆哮位图（RoaringBitmap）来了。
它将整个大位图进行了分块，如果整个块都是零，那么这整个块就不用存了。但是如果位1比较分散，每个块里面都有1，虽然单个块里的1很少，这样只进行分块还是不够的，那该怎么办呢？我们再想想，对于单个块，是不是可以继续优化？如果单个块内部位 1 个数量很少，我们可以只存储所有位1的块内偏移量（整数），也就是存一个整数列表，那么块内的存储也可以降下来。这就是单个块位图的稀疏存储形式 —— 存储偏移量整数列表。只有单块内的位1超过了一个阈值，才会一次性将稀疏存储转换为密集存储。
咆哮位图除了可以大幅节约空间之外，还会降低 AND、OR 等位运算的计算效率。以前需要计算整个位图，现在只需要计算部分块。如果块内非常稀疏，那么只需要对这些小整数列表进行集合的 AND、OR 运算，如是计算量还能继续减轻。
这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。
咆哮位图的位长最大为 2^32，对应的空间为 512M（普通位图），位偏移被分割成高 16 位和低 16 位，高 16 位表示块偏移，低16位表示块内位置，单个块可以表达 64k 的位长，也就是 8K 字节。最多会有64k个块。现代处理器的 L1 缓存普遍要大于 8K，这样可以保证单个块都可以全部放入 L1 Cache，可以显著提升性能。
如果单个块所有的位全是零，那么它就不需要存储。具体某个块是否存在也可以是用位图来表达，当块很少时，用整数列表表示，当块多了就可以转换成普通位图。整数列表占用的空间少，它还有类似于 ArrayList 的动态扩容机制避免反复扩容复制数组内容。当列表中的数字超出4096个时，会立即转变成普通位图。
用来表达块是否存在的数据结构和表达单个块数据的结构可以是同一个，因为块是否存在本质上也是 0 和 1，就是普通的位标志。
但是 Redis 并没有原生支持咆哮位图这个数据结构啊？我们该如何使用呢？
Redis 确实没有原生的，但是咆哮位图的 Redis Module 有。
这个项目的 star 数量并不是很多，我们来看看它的官方性能对比
| OP | TIME/OP (us) | ST.DEV. (us) |
|---|---|---|
| R.SETBIT | 31.89 | 28.49 |
| SETBIT | 29.98 | 29.23 |
| R.GETBIT | 29.90 | 14.60 |
| GETBIT | 28.63 | 14.58 |
| R.BITCOUNT | 32.13 | 0.10 |
| BITCOUNT | 192.38 | 0.96 |
| R.BITPOS | 70.27 | 0.14 |
| BITPOS | 87.70 | 0.62 |
| R.BITOP NOT | 156.66 | 3.15 |
| BITOP NOT | 364.46 | 5.62 |
| R.BITOP AND | 81.56 | 0.48 |
| BITOP AND | 492.97 | 8.32 |
| R.BITOP OR | 107.03 | 2.44 |
| BITOP OR | 461.68 | 8.42 |
| R.BITOP XOR | 69.07 | 2.82 |
| BITOP XOR | 440.75 | 7.90 |
很明显这里对比的是稀疏位图，只有稀疏位图才可以呈现出这样好看的数字。如果是密集位图，咆哮位图的性能肯定要稍弱于普通位图，但是通常也不会弱太多。
下面我们来观察一下源代码看看它的内部结构是怎样的
// 单个块
typedef struct roaring_array_s {
int32_t size;
int32_t allocation_size;
void **containers; // 指向整数数组或者普通位图
uint16_t *keys;
uint8_t *typecodes;
uint8_t flags;
} roaring_array_t;
// 所有块
typedef struct roaring_bitmap_s {
roaring_array_t high_low_container;
} roaring_bitmap_t;
很明显可以看到块存在与否和块内数据都是使用同样的数据结构表达的，它们都是 roaring_bitmap_t。这个结构里面有多种编码形式，类型使用 typecodes 字段来表示。
#define BITSET_CONTAINER_TYPE_CODE 1 #define ARRAY_CONTAINER_TYPE_CODE 2 #define RUN_CONTAINER_TYPE_CODE 3 #define SHARED_CONTAINER_TYPE_CODE 4
看到这里的类型定义，我们发现它不止前面提到的普通位图和数组列表两种形式，还有 RUN 和 SHARED 这两种类型。RUN 形式是位图的压缩形式，比如连续的几个位 101,102,103,104,105,106,107,108,109 表示成 RUN 后就是 101,8（1 后面是 8 个自增的整数），这样在空间上就可以明显压缩不少。在正常情况下咆哮位图内部没有 RUN 类型的块。只有显示调用了咆哮位图的优化 API 才会转换成 RUN 格式，这个 API 是 roaring_bitmap_run_optimize。
而 SHARED 类型用于在多个咆哮位图之间共享块，它还提供了写复制功能。当这个块被修改时将会复制出新的一份。
咆哮位图的计算逻辑还有更多的细节，我们后面有空再继续介绍。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。
相关推荐
-
Docker 部署 SpringBoot 项目整合 Redis 镜像做访问计数示例代码
最终效果如下 大概就几个步骤 1.安装 Docker CE 2.运行 Redis 镜像 3.Java 环境准备 4.项目准备 5.编写 Dockerfile 6.发布项目 7.测试服务 环境准备 系统:Ubuntu 17.04 x64 Docker 17.12.0-ce IP:45.32.31.101 一.安装 Docker CE 国内不建议使用:"脚本进行安装",会下载安装很慢,使用步骤 1 安装,看下面的链接:常规安装方式 1.常规安装方式 Ubuntu 17.04 x64 安装
-
redis实现计数器-防止刷单方法介绍
最近由于双11要来临,公司需要在接口请求上,做一下并发限制的处理,或者做一个防止刷单的安全拦截: 比如:一个接口请求,限制每秒请求总数为200次,超过200次就等待,等下一秒,再次请求,这里用到一个redis作为一个计数器的模式来实现. 调用redis的方法: INCR key 将 key 中储存的数字值增一. 如果 key 不存在,那么 key 的值会先被初始化为 0 ,然后再执行 INCR 操作. 如果值包含错误的类型,或字符串类型的值不能表示为数字,那么返回一个错误. 这是一个针对字符串的
-
Redis的使用模式之计数器模式实例
Redis 是目前 NoSQL 领域的当红炸子鸡,它象一把瑞士军刀,小巧.锋利.实用,特别适合解决一些使用传统关系数据库难以解决的问题.打算写一系列 Redis 使用模式的文章,深入总结介绍 Redis 常见的使用模式,以供大家参考. 常见汇总计数器 汇总计数是系统常见功能,比如网站通常需要统计注册用户数,网站总浏览次数等等. 使用 Redis 提供的基本数据类型就能实现汇总计数器,通过 incr 命令实现增加操作. 比如注册用户数,基本操作命令如下: 复制代码 代码如下: # 获取注册用户数
-
Redis实现唯一计数的3种方法分享
唯一计数是网站系统中十分常见的一个功能特性,例如网站需要统计每天访问的人数 unique visitor (也就是 UV).计数问题很常见,但解决起来可能十分复杂:一是需要计数的量可能很大,比如大型的站点每天有数百万的人访问,数据量相当大:二是通常还希望扩展计数的维度,比如除了需要每天的 UV,还想知道每周或每月的 UV,这样导致计算十分复杂. 在关系数据库存储的系统里,实现唯一计数的方法就是 select count(distinct <item_id>),它十分简单,但是如果数据量很大,这
-
redis通过位图法记录在线用户的状态详解
前言 在进入今天的主题前,先简单地解释下Redis中的位图到底是什么.Redis官方文档对于位图的介绍如下: 位图不是一个真实的数据类型,而是定义在字符串类型上的面向位的操作的集合.由于字符串类型是二进制安全的二进制大对象,并且最大长度是 512MB,适合于设置 2^32个不同的位. 位操作分为两组:常量时间单个位的操作,像设置一个位为 1 或者 0,或者获取该位的值.对一组位的操作,例如计算指定范围位的置位数量. 位图的最大优势是有时是一种非常显著的节省空间来存储信息的方式.例如,在一个系统中
-
Spring之借助Redis设计一个简单访问计数器的示例
为什么要做一个访问计数?之前的个人博客用得是卜算子做站点访问计数,用起来挺好,但出现较多次的响应很慢,再其次就是个人博客实在是访问太少,数据不好看
-
PHP基于redis计数器类定义与用法示例
本文实例讲述了PHP基于redis计数器类定义与用法.分享给大家供大家参考,具体如下: Redis是一个开源的使用ANSI C语言编写.支持网络.可基于内存亦可持久化的日志型.Key-Value数据库,并提供多种语言的API. 这里使用其incr(自增),get(获取),delete(清除)方法来实现计数器类. 1.Redis计数器类代码及演示实例 RedisCounter.class.php <?php /** * PHP基于Redis计数器类 * Date: 2017-10-28 * Aut
-
Redis实现高并发计数器
业务需求中经常有需要用到计数器的场景:譬如一个手机号一天限制发送5条短信.一个接口一分钟限制多少请求.一个接口一天限制调用多少次等等.使用Redis的Incr自增命令可以轻松实现以上需求.以一个接口一天限制调用次数为例: /** * 是否拒绝服务 * @return */ private boolean denialOfService(String userId){ long count=JedisUtil.setIncr(DateUtil.getDate()+"&"+user
-
Redis精确去重计数方法（咆哮位图）
前言 如果要统计一篇文章的阅读量,可以直接使用 Redis 的 incr 指令来完成.如果要求阅读量必须按用户去重,那就可以使用 set 来记录阅读了这篇文章的所有用户 id,获取 set 集合的长度就是去重阅读量.但是如果爆款文章阅读量太大,set 会浪费太多存储空间.这时候我们就要使用 Redis 提供的 HyperLogLog 数据结构来代替 set,它只会占用最多 12k 的存储空间就可以完成海量的去重统计.但是它牺牲了准确度,它是模糊计数,误差率约为 0.81%. 那么有没有一种不怎么
-
Redis使用Bitmap的方法实现
目录 1. Bitmap 是什么 2. 占用存储空间 3. 命令 3.1 SETBIT 3.2 GETBIT 3.3 BITCOUNT 3.4 BITOP 3.5 BITPOS 1. Bitmap 是什么 Bitmap(也称为位数组或者位向量等)是一种实现对位的操作的'数据结构',在数据结构加引号主要因为: Bitmap 本身不是一种数据结构,底层实际上是字符串,可以借助字符串进行位操作. Bitmap 单独提供了一套命令,所以与使用字符串的方法不太相同.可以把 Bitmaps 想象成一个以位为
-
ubuntu 系统上为php加上redis 扩展的实现方法
ubuntu 系统上为php加上redis 扩展的实现方法 最近一个项目,,想用redis 作为数据库,php是不待redis 扩展,必须安装,怎么安装呢?我在网上找的很多资料发现都是预编译的,但都没成功,于是就找了另外一种方法是不需要编译直接安装就可以了. 安装redis 扩展 sudo apt-get install git-core 安装好后重启nginx ,php5-fpm, 重启nginx sudo /etc/init.d/nginx restart 重启php5-fmp sudo /
-
MySQL去重的方法整理
MySQL去重的方法整理 [初级]有极少的重复行 使用distinct查出来,然后手动一行一行删除. [中级]按照单个字段的重复去重 例如:对id字段去重 使用方法:获取id的重复字段的值,利用相同id字段所在的行中,比较出数据不同的字段,删除 除了最小(或最大)的字段所在的该行之外的所有重复的行.一般使用主键来比较,因为主键的值一定是唯一值,绝对不相同. id name 1 a 1 b 2 c 2 a 3 c 结果: id name 1 a 2 a 操作: delete from a_tmp
-
Oracle表中重复数据去重的方法实例详解
Oracle表中重复数据去重的方法实例详解 我们在项目中肯定会遇到一种情况,就是表中没有主键 有重复数据 或者有主键 但是部分字段有重复数据 而我们需要过滤掉重复数据 下面是一种解决方法 delete from mytest ms where rowid in (select aa.rid from (select rowid as rid, row_number() over(partition by s.name order by s.id) as nu from mytest s) aa
-
Laravel框架实现redis集群的方法分析
本文实例讲述了Laravel框架实现redis集群的方法.分享给大家供大家参考,具体如下: 在app/config/database.php中配置如下: 'redis' => array( 'cluster' => true, 'default' => array( 'host' => '172.21.107.247', 'port' => 6379, ), 'redis1' => array( 'host' => '172.21.107.248', 'port'
-
go语言操作redis连接池的方法
本文实例讲述了go语言操作redis连接池的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: func newPool(server, password string) *redis.Pool { return &redis.Pool{ MaxIdle: 3, IdleTimeout: 240 * time.Second, Dial: func () (redis.Conn, error) { c
-
浅析PHP分布式中Redis实现Session的方法
本文介绍的是PHP分布式中Redis实现Session的方法,下面话不多说,直接先来看两个方法是什么 方法一: 找到配置文件php.ini,修改为下面内容,保存并重启服务 session.save_handler = redis session.save_path = "tcp://127.0.0.1:6379" 方法二: 直接在代码中加入以下内容: ini_set("session.save_handler", "redis"); ini_se
-
Python利用正则表达式匹配并截取指定子串及去重的方法
本文实例讲述了Python利用正则表达式匹配并截取指定子串及去重的方法.分享给大家供大家参考.具体如下: import re pattern=re.compile(r'\| (\d+) \| (\d+) \|') numset=set() all=''' | 29266795 | 533 | | 29370116 | 533 | | 29467495 | 533 | | 29500404 | 533 | | 29500622 | 533 | | 29515964 | 530 | | 295160