位图、HyperLogLog、布隆过滤器、Geohash

本文主要是介绍位图、HyperLogLog、布隆过滤器、Geohash，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 节衣缩食-位图

　　在平时的开发中，会有一些bool 型数据需要存取，比如用户的签到记录，签了是1，没签是0，要记录365天。如果使用普通的key/value,每个用户需要记录365个，当用户数上亿的时候，需要的存储空间非常大。

　　为了解决这个问题，Redis 提供了位图数据结构，每天的签到记录只占一个位，365天就是365位(46个字节)。位图的最小单位是比特，每个比特的取值只能是0或1。

　　位图不是特殊的数据结构，它的内容其实就是普通的字符串，也就是byte数组。我们可以使用get\set 直接获取和设置整个位图的内容，也可以使用位图操作getbit\setbit 等将byte数组看成"位数组"来处理。

　　Redis 的位数组是自动扩展的，如果设置了某个偏移位置超出了现有的内容范围， 就会自动将位数组进行零扩充。

例如：  用位操作将字符串设置为hello

用python 查看hello的ASCII码的二进制值；

>>> bin(ord('h'))
'0b1101000'
>>> bin(ord('e'))
'0b1100101'
>>> bin(ord('l'))
'0b1101100'
>>> bin(ord('l'))
'0b1101100'
>>> bin(ord('o'))
'0b1101111'

h 字符只需要设置 1/2/4 位设置为1， 其他自动为0
e 字符需要9、10、13、15 位需要设置
l 是17、18、20、21

 设置如下：( 只设置h 字符)

127.0.0.1:6379> setbit s 1 1
(integer) 0
127.0.0.1:6379> setbit s 2 1
(integer) 0
127.0.0.1:6379> setbit s 4 1
(integer) 0
127.0.0.1:6379> get s
"h"

零存零取：使用单个位设置位值，使用单个位操作获取具体位值。

127.0.0.1:6379> getbit s 4
(integer) 1
127.0.0.1:6379> getbit s 3
(integer) 0

整存零取：使用字符串操作批量设置位值，使用单个位操作获取具体位置。

127.0.0.1:6379> set w h
OK
127.0.0.1:6379> getbit w 4
(integer) 1
127.0.0.1:6379> getbit w 3
(integer) 0

统计和查找：bitcount 用来查找某个位置范围内1的个数； bitpos 用来查找指定范围第一个出现0或者1的位置

127.0.0.1:6379> set w hello
OK
127.0.0.1:6379> get w
"hello"
127.0.0.1:6379> bitcount w
(integer) 21
127.0.0.1:6379> bitcount w 0 0 # 第一个字符中1的位数
(integer) 3
127.0.0.1:6379> bitcount w 0 1 # 前两个字符中1的位数
(integer) 7
127.0.0.1:6379> bitpos w 0 #第一个0位
(integer) 0
127.0.0.1:6379> bitpos w 1 #第一个1位
(integer) 1
127.0.0.1:6379> bitpos w 1 1 1  #从第二个字符算起，第一个1位
(integer) 9
127.0.0.1:6379> bitpos w 1 2 2 # 从第三个字符算起，第一个1位
(integer) 17

魔术指令bitfield： 这个是一次操作多个位的操作。bitfield 有三个子指令，分别是get、set、incrby， 最多能操作64个连续的位；超过64位，就得使用多个子指令。

127.0.0.1:6379> bitfield w get u4 0        #从第一个位开始取4个位，结果是无符号数(u)
1) (integer) 6
127.0.0.1:6379> bitfield w get u3 2        #从第三个位开始取3个位，结果是无符号数
1) (integer) 5
127.0.0.1:6379> bitfield w get i4 0        #从第一个位开始取4个位，结果是有符号数(i)
1) (integer) 6
127.0.0.1:6379> bitfield w get i3 2        #从第三个位开始取3个位，结果是有符号数(i)
1) (integer) -3

所谓有符号数是指获取的位数组中第一个位是符号位，剩下的才是值。如果第一位是1，那就是负数。无符号数表示非负数，没有符号位，获取的位数组全部都是值。

所以有了这个数据结构解决上面问题就比较简单，一年的话统计365天中签到的次数(位数为1的个数即可)。

2. HyperLogLog

 　　超日志记录。提供不精确的去重计数方案，虽然不精确，但是也不是非常离谱，标准误差是0.81%。

　　比如一个场景：统计网页每天的UV数据(UV统计用户访问次数，一个用户一天的多次请求只能算一次)。最简单的解决方案是每个页面设置一个set，当一个请求进来时使用sadd 将当前用户ID塞进去。 最后通过scard 取出这个集合的大小，这个大小就是页面的UV。在数据量很多的情况下，比如有几千个页面，每个页面有几千万个UV，那么需要的存储空间也是惊人的。

1. 使用方法

HyperLogLog 提供了两个指令。 pfadd 和 pfcount， 一个用于增加，一个用于计数。例如：

127.0.0.1:6379> pfadd codehole user1
(integer) 1
127.0.0.1:6379> pfadd codehole user2 user3
(integer) 1
127.0.0.1:6379> pfcount codehole
(integer) 3

2. pfadd 中的pf 是什么意思

HyperLogLog数据结构 的发明人是Philippe Flajolet， pf 是他的名字的缩写。

3. pfmerge 合并

　　用于合并两个或多个HyperLogLog

127.0.0.1:6379> pfadd codehole2 user4    # 在创建一个
(integer) 1
127.0.0.1:6379> pfmerge codehole codehole2    #将codehole2合并到codehole
OK
127.0.0.1:6379> pfcount codehole
(integer) 4
127.0.0.1:6379> pfcount codehole2
(integer) 1
127.0.0.1:6379> pfadd codehole user4    #重复添加不会计数
(integer) 0
127.0.0.1:6379> pfcount codehole
(integer) 4

HyperLogLog 是一种概率数据结构，它使用概率算法来统计集合的近似基数。其没有提供pfcontains的功能，也就是如果先判断某个元素是否在HyperLogLog 内部，是无能为力的。

3. 布隆过滤器

　　上面的HyperLogLog 没有提供pfcontains 的功能，也就是无法判断某个元素是否在集合中。

　　布隆过滤器可以理解为一个不精确的set结构。当布隆过滤器说某个值存在，可能不存在； 说某个值不存在就一定不存在。

　　比如说，做一个用户新闻推荐的系统，可以用布隆过滤器保存已经给用户推送过的新闻。但是有可能出现误差，也就是说有可能过滤掉那些用户已经看过的内容； 而且布隆过滤器无法删除元素。

1. redis 中的布隆过滤器

　　Redis4.0 以后官方提供了布隆过滤器。布隆过滤器作为一个插件加载到RedisServer 中， 给Redis 提供了强大的布隆去重功能。

基于docker 安装：

docker pull redislabs/rebloom

然后启动容器

$ docker run -p6379:6379 redislabs/rebloom
1:C 27 Jun 2021 04:12:06.863 # oO0OoO0OoO0Oo Redis is starting oO0OoO0OoO0Oo
1:C 27 Jun 2021 04:12:06.863 # Redis version=6.0.9, bits=64, commit=00000000, modified=0, pid=1, just started
1:C 27 Jun 2021 04:12:06.863 # Configuration loaded
1:M 27 Jun 2021 04:12:06.865 * Running mode=standalone, port=6379.
1:M 27 Jun 2021 04:12:06.865 # WARNING: The TCP backlog setting of 511 cannot be enforced because /proc/sys/net/core/somaxconn is set to the lower value of 128.
1:M 27 Jun 2021 04:12:06.866 # Server initialized
1:M 27 Jun 2021 04:12:06.866 # WARNING overcommit_memory is set to 0! Background save may fail under low memory condition. To fix this issue add 'vm.overcommit_memory = 1' to /etc/sysctl.conf and then reboot or run the command 'sysctl vm.overcommit_memory=1' for this to take effect.
1:M 27 Jun 2021 04:12:06.866 # WARNING you have Transparent Huge Pages (THP) support enabled in your kernel. This will create latency and memory usage issues with Redis. To fix this issue run the command 'echo madvise > /sys/kernel/mm/transparent_hugepage/enabled' as root, and add it to your /etc/rc.local in order to retain the setting after a reboot. Redis must be restarted after THP is disabled (set to 'madvise' or 'never').
1:M 27 Jun 2021 04:12:06.867 * Module 'bf' loaded from /usr/lib/redis/modules/redisbloom.so
1:M 27 Jun 2021 04:12:06.867 * Ready to accept connections

在开启一个窗口进入容器测试布隆过滤器

docker exec -it 57 bash

测试其基本用法：bf.add和bf.exists操作单个；bf.madd、bf.mexists 操作多个

root@5734e47e2acb:/data# redis-cli
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehele user1
(integer) 0
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

其他用法：

127.0.0.1:6379> bf.info codehole    # 查看布隆过滤器信息
 1) Capacity
 2) (integer) 100
 3) Size
 4) (integer) 296
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 6
 9) Expansion rate
10) (integer) 2
127.0.0.1:6379> bf.debug codehole    # 查看布隆过滤器的内部详细信息
1) "size:6"
2) "bytes:144 bits:1152 hashes:8 hashwidth:64 capacity:100 size:6 ratio:0.005"

　　上面使用的布隆过滤器是默认参数的布隆过滤器(默认error_rate 是0.01， initial_size 是100)，它在第一次add的时候会自动创建。Redis 其实还提供了自定义参数的布隆过滤器，需要我们在add 之前使用bf.reserve 指令显示的创建。如果对应的key 已经存在，bf.reserve 会报错。

　　bf.reserve 有三个参数， 分别是key、error_rate(错误率)、initial_size。 error_rate 越低，需要的空间越大。initial_size 表示预计放入的元素的数量，当实际数量超过这个数值时，误判率会上升，所以需要提前设置一个比较大的数字避免超出导致误判率升高。

例如：

127.0.0.1:6379> bf.reserve codehole2 0.08 500
OK
127.0.0.1:6379> bf.add codehole2 user0
(integer) 1
127.0.0.1:6379> bf.info codehole2
 1) Capacity
 2) (integer) 500
 3) Size
 4) (integer) 576
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 1
 9) Expansion rate
10) (integer) 2

注意：initiali_size 设置的过大，会浪费存储空间，设置的过小会影响准确率。    error_rate 越小，需要的存储空间就越大。

2. 布隆过滤器基本原理

每个布隆过滤器到redis 数据结构里面就是一个大型的位数组和几个不一样的无偏hash 函数(比如f\g\h就是这样的hash函数)。所谓无偏函数就是能够把元素的hash 值算得比较均匀，让元素被hash 映射到位数组中的位置比较随机。

 add过程：使用多个hash函数对key 进行函数，得到一个整数索引值，然后对位数组长度进行取模运算得到一个位置，每个hash 函数都会得到一个不同的位置。 再把数组的这几个位置都设为1， 就完成了add 操作

exists 过程：跟add 一样经过hash，然后取模运算得到位置判断是否全部为1， 只要有一个为0 就是不存在；全部为1 就是存在(所以可能出现误判的情况，不同元素的hash 算法的值可能一样)。

3. 使用场景

1. 爬虫系统中，对URL进行去重，已经爬过的网页就可以不用再爬了

2. 解决缓存穿透的问题(过滤器过滤掉大量不存在的row 请求)

3. 邮箱系统的垃圾邮件过滤功能

4. GeoHash

　　Redis3.2 以后增加了地理位置Geo 模块， 意味着我们可以使用redis 来实现类似摩拜单车的"附近的Mobike"、以及"附近的餐馆"这样的功能。

1. 基本用法

1. 增加

127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin
(integer) 1
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
(integer) 2

　　Geo 没有提供删除元素的命令，因为其内部采用的是zset 结构，所以删除元素的时候可以直接使用zrem 指令。

127.0.0.1:6379> zrange company 0 -1 WITHSCORES
 1) "jd"
 2) "4069154033428715"
 3) "xiaomi"
 4) "4069880904286516"
 5) "ireader"
 6) "4069886008361398"
 7) "juejin"
 8) "4069887154388167"
 9) "meituan"
10) "4069887179083478"

2. 距离

geodist 指令可以用来计算两个元素之间的距离。

127.0.0.1:6379> geodist company juejin meituan km
"1.3878"
127.0.0.1:6379> geodist company juejin meituan m
"1387.8166"
127.0.0.1:6379> geodist company juejin jd km
"24.2739"
127.0.0.1:6379> geodist company juejin jd m
"24273.9390"

3. 获取元素位置

geopos 可以获取元素的位置

127.0.0.1:6379> geopos company jd meituan
1) 1) "116.56210631132125854"
   2) "39.78760295130235392"
2) 1) "116.48903220891952515"
   2) "40.00766997707732031"
127.0.0.1:6379> geopos company jd
1) 1) "116.56210631132125854"
   2) "39.78760295130235392"

4. 获取元素的hash 值

geohash 可以获取元素的经纬度编码字符串

127.0.0.1:6379> geohash company jd meituan
1) "wx4fk7jgtf0"
2) "wx4gdg0tx40"
127.0.0.1:6379> geohash company jd
1) "wx4fk7jgtf0"

5. 附近的公司

georadiusbymember 可以查询指定元素附件的其他元素

# 20 公里以内最多3个元素按距离正排， 它不会排除自身
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc
1) "ireader"
2) "juejin"
3) "meituan"
# 20 公里以内最多3个元素按距离倒排
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc
1) "jd"
2) "meituan"
3) "juejin"
# 三个可选参数，withcoord\withdist\withhash 用来携带附加参数
127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc
1) 1) "ireader"
   2) "0.0000"
   3) (integer) 4069886008361398
   4) 1) "116.5142020583152771"
      2) "39.90540918662494363"
2) 1) "juejin"
   2) "10.5501"
   3) (integer) 4069887154388167
   4) 1) "116.48104995489120483"
      2) "39.99679348858259686"
3) 1) "meituan"
   2) "11.5748"
   3) (integer) 4069887179083478
   4) 1) "116.48903220891952515"
      2) "40.00766997707732031"
# 根据坐标值查询附件的元素
127.0.0.1:6379> georadius company 116.514202 39.905409 20 km withdist count 3 asc
1) 1) "ireader"
   2) "0.0000"
2) 1) "juejin"
   2) "10.5501"
3) 1) "meituan"
   2) "11.5748"

　　注意：Redis如果使用Geo 数据，它们会将全部放在一个zset 中。如果在集群环境中，会对集群的迁移工作造成很大影响，而且可能导致先生服务的正常运行。所以建议是Geo 的数据使用单独的redis 实例部署，不使用集群环境。

2. 原理

GeoHash 算法。 业界比较通用的地理位置排序算法是GeoHash 算法。 这个算法将二维的经纬度数据映射到一维的整数，这样所有的元素都将挂载到一条线上。

在redis 里面，经纬度使用52 位的整数进行编码，然后放进zset 里面。 value 是元素的key， score 是GeoHash 的52 位整数值。

在使用redis 进行Geo 查询时，可以把它的内部结构理解为一个zset(skiplist)。 通过zset的score 排序就可以得到坐标附件的其他元素， 通过将score 还原成坐标值就可以得到元素的原始坐标。　　

这篇关于位图、HyperLogLog、布隆过滤器、Geohash的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！