深入浅出Redis（十一）：Geosptial、Hypeloglog、Bitmap、Bloom Filter布隆过滤器

深入浅出Redis（十一）：Geosptial、Hypeloglog、Bitmap、Bloom Filter布隆过滤器

Redis提供丰富的数据结构来解决各种场景下的问题，前段时间的一篇文章深入浅出Redis（一）：对象与数据结构已经深入浅出的说明Redis中的常用基础对象与数据结构

本篇文章将作为那篇文章的补充，深入浅出的解析另外四种数据结构：Geospatial、Hyperloglog、Bitmap以及Bloom Filter布隆过滤器

Geospatial

Geospatial 是一种能够解决地理空间相关场景下的数据结构，它提供的命令能够容易实现两地距离、附近的人等功能

Geospatial 使用GeoHash算法，底层实现使用zset对象 因此也可以使用Zset命令

geoadd 添加

geoadd key 经度 纬度 名称

将指定的地理空间位置（纬度、经度、名称）添加到指定的key中（可添加多个）

有效的经度从-180度到180度

有效的纬度从-85.05112878度到85.05112878度

超出上述经纬度会报错

代码语言：shell复制

 127.0.0.1:6379> geoadd china:city 116.23 40.22 beijing 
 (integer) 1
 127.0.0.1:6379> geoadd china:city 121.48 31.40 shanghai 113.88 22.55 shenzhen 104.10 30.65 chendu
 (integer) 3

geopos 获取

geopos key 成员名...

从key里返回所有给定位置元素的位置（经度和纬度）

代码语言：shell复制

 127.0.0.1:6379> geopos china:city beijing shenzhen
 1) 1) "116.23000055551528931"
    2) "40.2200010338739844"
 2) 1) "113.87999922037124634"
    2) "22.5500010475923105"

geodist 位置间的距离

geodist key member1 member2 [unit]

返回两个给定位置之间的距离

单位：（默认米）：m 表示单位为米，km表示单位为千米，mi 表示单位为英里，ft 表示单位为英尺

代码语言：shell复制

 127.0.0.1:6379> geodist china:city beijing shenzhen
 "1977782.5112"
 127.0.0.1:6379> geodist china:city beijing shenzhen km
 "1977.7825"

georadius 以某点为中心，查找周围x半径之内的member（附近的人）

georadius key longitude latitude radius m|km|ft|mi [withcoord] [withdist] [count]

以给定的经纬度为中心， 返回键包含的位置元素当中， 与中心的距离不超过给定最大距离的所有位置元素

withcoord：获得经纬度坐标

withdist：找到的元素距离中心点的距离

count：限制查到的个数

代码语言：shell复制

 #以经纬度 110，30为中心，半径1500km的范围内的成员
 127.0.0.1:6379> georadius china:city 110 30 1500 km 
 1) "chendu"
 2) "shenzhen"
 3) "shanghai"
 4) "beijing"
 #以经纬度 110，30为中心，半径1500km的范围内的成员 列出成员坐标经纬度
 127.0.0.1:6379> georadius china:city 110 30 1500 km withcoord
 1) 1) "chendu"
    2) 1) "104.09999996423721313"
       2) "30.6499990746355806"
 2) 1) "shenzhen"
    2) 1) "113.87999922037124634"
       2) "22.5500010475923105"
 3) 1) "shanghai"
    2) 1) "121.48000091314315796"
       2) "31.40000025319353938"
 4) 1) "beijing"
    2) 1) "116.23000055551528931"
       2) "40.2200010338739844"
  #以经纬度 110，30为中心，半径1500km的范围内的成员 列出成员坐标经纬度和成员到中心直线距离
 127.0.0.1:6379> georadius china:city 110 30 1500 km withcoord withdist
 1) 1) "chendu"
    2) "570.9717"
    3) 1) "104.09999996423721313"
       2) "30.6499990746355806"
 2) 1) "shenzhen"
    2) "914.3335"
    3) 1) "113.87999922037124634"
       2) "22.5500010475923105"
 3) 1) "shanghai"
    2) "1108.3830"
    3) 1) "121.48000091314315796"
       2) "31.40000025319353938"
 4) 1) "beijing"
    2) "1269.3568"
    3) 1) "116.23000055551528931"
       2) "40.2200010338739844"
 #以经纬度 110，30为中心，半径1500km的范围内的成员 列出成员坐标经纬度 限制只查询一个（直线距离最近的）      
 127.0.0.1:6379> georadius china:city 110 30 1500 km withcoord count 1
 1) 1) "chendu"
    2) 1) "104.09999996423721313"
       2) "30.6499990746355806"
  #以经纬度 110，30为中心，半径1500km的范围内的成员 列出成员坐标经纬度 限制只查询俩个（直线距离最近的）  
 127.0.0.1:6379> georadius china:city 110 30 1500 km withcoord count 2
 1) 1) "chendu"
    2) 1) "104.09999996423721313"
       2) "30.6499990746355806"
 2) 1) "shenzhen"
    2) 1) "113.87999922037124634"
       2) "22.5500010475923105"

georadiusbymember （与georadius类似，它是以member为中心的）

georadiusbymember key member radius m|km|ft|mi [withcoord] [withdist] [count]

这个命令和 georadius命令一样， 都可以找出位于指定范围内的元素， 但是 georadiusbymember 的中心点是由给定的位置元素决定的

代码语言：shell复制

 #以beijing为中心 1500km为半径 查找的成员（会查到自己）
 127.0.0.1:6379> georadiusbymember china:city beijing 1500 km
 1) "shanghai"
 2) "beijing"

geohash

geohash key member...

该命令将返回11个字符的Geohash字符串

代码语言：shell复制

 # 深圳与成都
 127.0.0.1:6379> geohash china:city shenzhen chendu
 1) "ws0br3hgk20"
 2) "wm6n2gem1v0"
 
 # 东莞与深圳
 127.0.0.1:6379> geohash china:city dongguan shenzhen
 1) "ws0fuqwjpn0"
 2) "ws0br3hgk20"

将二维经纬度转化为一维字符串，如果俩个成员距离越近，字符串就会越相似

通过Zset指令来操作geo（因为geo底层实现原理就是Zset）

代码语言：shell复制

 127.0.0.1:6379> zrange china:city 0 -1
 1) "chendu"
 2) "shenzhen"
 3) "dongguan"
 4) "shanghai"
 5) "beijing"
 127.0.0.1:6379> zrem china:city dongguan
 (integer) 1
 127.0.0.1:6379> zrange china:city 0 -1
 1) "chendu"
 2) "shenzhen"
 3) "shanghai"
 4) "beijing"

Hyperloglog

在数据量特别大的情况下，想要统计数量可以选择用哈希表实现的set存储（能够去重），但是哈希表是空间换时间的数据结构，这种情况下会浪费大量空间

hyperloglog使用基数统计算法，用固定且少量的空间，能够实现统计计数，但缺点是有0.81%的错误率

A={1,2,4,5,6,1}

B={1,2,4,5,6}

基数=5（不重复的元素）

命令

• 存: pfadd key element...将指定元素添加到hyperloglog
• 读: pfcount key...统计hyperloglog中的基数数量（一个hyperloglog时）或并集数量（多个hyperloglog时）
• 合并:pfmerge destkey sourcekey...将多个hyperloglog合并成一个hyperloglog并返回并集数量

代码语言：shell复制

 127.0.0.1:6379> pfadd mykey a b c d e f g 
 (integer) 1
 127.0.0.1:6379> pfcount mykey
 (integer) 7
 127.0.0.1:6379> pfadd mykey2 a b c d e f g h i j
 (integer) 1
 127.0.0.1:6379> pfcount mykey mykey2
 (integer) 10
 127.0.0.1:6379> pfmerge newkey mykey2  mykey
 OK
 127.0.0.1:6379> pfcount newkey
 (integer) 10

Bitmap

Bitmap使用位数组中的二进制来进行 状态统计 （只有 0 1）

Bitmap能够有效的大数据量下进行只有俩个状态的统计

比如：统计只有俩个状态的用户信息（活跃，不活跃。登录，未登录。打卡，未打卡）

使用

• setbit key offset value设置key在offset处的bit值（0/1）
• getbit key offset 获得key在offset处的bit值（0/1）
• bitcount key 统计key中有多少位1
• 模拟电影是否被点播情况 key->日期 offset->（电影ID）value->(0为未点播，1为点播)
• 统计每天某部电影是否被点播 getbit 日期 电影ID
• 统计每天有多少部电影被点播 bitcount 日期
• 统计每周/月/年有多少部电影被点播 bitop or 每周日期 记录值后可统计每月，每年 或
• 统计年度哪部电影没被点播 （为0时没被点播）

代码语言：shell复制

  127.0.0.1:6379> setbit 1130 1 1 #11月30日 1号电影 被点播
   (integer) 0
   127.0.0.1:6379> setbit 1130 2 1 #11月30日 2号电影 被点播
   (integer) 0
   127.0.0.1:6379> setbit 1130 3 1 #11月30日 3号电影 被点播
   (integer) 0
   127.0.0.1:6379> setbit 1201 4 1 #12月1日 4号电影 被点播
   (integer) 0
   127.0.0.1:6379> setbit 1201 5 1 #12月1日 5号电影 被点播
   (integer) 0
   127.0.0.1:6379> setbit 1201 1 1 #12月1日 1号电影 被点播
   (integer) 0
   127.0.0.1:6379> bitcount 1130 #11月30日 3部电影被点播
   (integer) 3
   127.0.0.1:6379> bitcount 1201 #12月1日 3部电影被点播
   (integer) 3
   127.0.0.1:6379> bitop and 1130-1201 1130 1200 #统计11月30日 与 12月1日 都点播了的电影
   (integer) 1
   127.0.0.1:6379> getbit 1130-1201 1 #2日都被点播的电影是1号电影
   (integer) 1
   127.0.0.1:6379> bitcount 1130-1201
   (integer) 1

原理

位数组使用sds来实现，sds是二进制安全的，sds存储时逆序存储位数组，逆序存储在扩容时不用修改老数据

（不了解sds的同学可以先看这篇文章深入浅出Redis（一）：对象与数据结构）

setbit ：先计算len是否需要扩容，再计算偏移量在哪个字节上，接着计算偏移量在哪个位上，修改那个位的值并返回旧的值

getbit ：计算偏移量在哪个字节上，接着计算偏移量在哪个位上，再获取

bittop ：and、or、xor都是新建sds 每个字节做位操作结果放入新建sds中 ；not 则是直接取反

bitcount : 数据量小于128位时使用查表，大于128位时使用每次循环4次 swar，每次swar可以计算32位；swar是将32位分成2bit一组与01 （计算低位）再右移一位继续与运算（计算高位），再依次分为4位、8位、16位一组依次操作（jdk的integer.bitcount也是swar算法）

Bloom Filter

布隆过滤器能够使用少量的空间来判断某个元素是否存在于集合中，但存在一定的误判率（不在集合中保存元素）

布隆过滤器适合在大数据场景下，允许一定误判的快速判断元素是否存在集合中

Bloom Filter用于判断元素是否重复在集合中，不保存元素数据，节省空间，有一定误差

原理

Bloom Filter由位数组和多个hash函数组成

添加：将Key经过多个hash函数得到的索引，在位数组对应索引上设置为1

判断是否在集合中：将Key经过多个hash函数得到的索引，查看位数组对应索引上值是否为1，为1则可能存在（该索引上设置为1还有可能是添加其他Key设置的），如果值为0，那么该Key一定不存在集合中

布隆过滤器的误判率与空间大小有关，空间越小就越容易导致误判

使用

安装布隆过滤器插件

代码语言：shell复制

 #下载
 wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz
 #解压
 tar -zxvf v1.1.1.tar.gz
 cd rebloom-1.1.1
 #编译
 make

使用 bf.add添加 bf.exists判断是否存在集合中

代码语言：shell复制

 127.0.0.1:6379> bf.add bloomfilter cl
 (integer) 1
 127.0.0.1:6379> bf.add bloomfilter tcl
 (integer) 1
 127.0.0.1:6379> bf.exists bloomfilter cl
 (integer) 1
 127.0.0.1:6379> bf.exists bloomfilter cl1
 (integer) 0
 127.0.0.1:6379> bf.exists bloomfilter tcl
 (integer) 1

总结

本篇文章深入浅出的解析Redis中四种高级数据结构的使用、适用场景以及原理

Geospatial 使用Geohash算法以及zset对象实现，适用于计算地理空间的场景

Hypeloglog 使用少量固定空间以及基数统计算法，适用于大数据情况下能接收微小出错的统计场景

Bitmap 使用sds实现的位数组，sds逆序存储位数组扩容时不用修改旧数据，适用于大数据情况下只有两个状态的统计场景

Bloom Filter 使用位数组与多个哈希函数实现，适用于在大数据情况下且能接收微小出错的判断元素是否存在集合的场景

redis 腾讯技术创作特训营S9

0 人点赞