这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战」

prefix

分布式锁
延时队列（不如用kafka）
位图（bitset减少资源占用）
hyperLogLog（大批量数据不绝对精确的低资源占用统计）

需要后续学习的内容

hyperLogLog实现原理 zhuanlan.zhihu.com/p/58519480
延时队列
funnel(漏斗限流)

应用1 - 分布式锁

本质：在redis中留个标记，其他线程后续进入的时候放弃或重试。

方案 - setnx

setnx 指令

使用setnx(set if not exists)进行占用。使用完了使用del删除。

csharp复制代码> setnx lock:codehole true
OK
... do something critical ...
> del lock:codehole
(integer) 1

优点：

实现简单

缺点：

如果出现异常导致del没有调用，出现永久占用资源的死锁。

死锁改进方案1.0 - expire

加上过期时间，即使出现异常也不会导致永久死锁。

csharp复制代码> setnx lock:codehole true
OK
> expire lock:codehole 5
... do something critical ...
> del lock:codehole
(integer) 1

缺点：

setnx和expire不是一条原子指令，中间出错还是变成死锁。

死锁改进方案2.0 - set的扩展参数

csharp复制代码> set lock:codehole true ex 5 nx
OK
... do something critical ...
> del lock:codehole

使用扩展参数，讲setnx和expire变成一条原子性语句。

优点：

加锁变成原子性，在执行时间之外不会出现资源永远得不到释放的结果了。

缺点：

如果持有锁的线程/服务正常执行超时了，分布式锁可能会被其他的线程/服务取得，导致分布式锁失效。

超时补救

Redis 分布式锁不要用于较长时间的任务。

超时补救 - 随机数匹配

为value设置随机数，释放时匹配随机数是否一致。否则，只能让本线程删除。

使用lua脚本，保证原子性。

lua复制代码if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

但是依然不能保证锁的超时的问题。

超时补救1.0 - redission看门狗

后台异步启动一个线程定时(默认10s)去检查锁是否过期(锁不需要设置过期时间，默认30s过期)，如果没有过期就延长锁的过期时间，往复循环，知道当前线程释放锁看门狗才会退出

应用2 - 延时队列

//todo

应用3 - 位图

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

因为是字符串，因此：

位层面操作：

+ 使用**setbit** 'keyname' 2 1 ，来将索引位置为2的bit设置为1.
    - 索引位置只能是**非负整数**
    - value只能为0和1
+ 使用 getbit 'keyname' 2 来获取索引位置为2的bit.
    - 不会发生越界的问题

字符串层面操作：

+ 使用set，get来操作，此时和字符串操作相同
+ > 如果对应位的字节是不可打印字符，redis-cli 会显示该字符的 16 进制形式。

统计和查找

位层面下我们可以通过：

bitcount [start,end]统计指定范围内1的出现次数
bitpos [start,end] 0/1统计指定范围内第一个出现的0/1

这里我们需要注意：

start，end指的是字节索引，而不是bit位置的索引，因此start，end指的是从start x8到end x 8 的位置。

批量操作(好像try-redis上用不了，先了解)

可以使用 bitfield，对指定位片段进行读写。

最多处理64个连续的位
可以同时执行多个子指令，有三个子指令：

+ get
+ set
+ incrby

应用4 - HyperLogLog

用来解决类似:

UV统计（客户访问量）的存储和去重问题。

+ 有误差，但是在\*\*1%\*\*以内。
+ 节省存储空间


    - > 计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小
    - 最多只需要12k。

使用

Hyperloglog 提供了2个指令：

pfadd
pfcount

以及一个进阶指令：

pfmerge

指令以及用法

pfadd

+ pfadd 'keyname' 'value'这样子就算是往keyname里丢一个值了，如果重复了就不会增加，否则总数会加1.

pfcount

+ pfcount 'keyname'这个就是计数了。

pfmerge

+ pfmerge 'newHLLName' 'old1' 'old2'


这样子就会获得一个总和为**old1**和**old2**中不重复个数的**newHLLName**
+ pfmerge old1 old2


这样子old1中就会包括了old2中的数据，总和计数仍为不重复的

原理

概率算法，详见：zhuanlan.zhihu.com/p/58519480

应用5 - 布隆过滤器

hyperLogLog可以实现大规模数据不是特别精确的计数的需求，但是无法判断某个值是否已经存在了，布隆过滤器可以满足这部分的功能。

布隆过滤器和HyerLogLog有类似的特性：

节省存储空间
存在误判的可能，具体如下：
- 判断为存在，那么key可能实际上不存在
- 判断为不存在，那么key必然不存在
不允许删除

布隆过滤器在redis４.０提供插件之后才可以使用，作为一个插件，添加到redis server中。

指令

有2个基础指令，2个批量指令，以及一个显式构造过滤器的指令：

bf.add - 添加元素
- bf.add [keyname] [userName]
bf.exists - 查询是否存在
- bf.exists[keyname] [userName]
bf.mexists - 查询多个是否存在
- bf.mexists [keyname] [username1] [username2] […]
bf.madd - 添加多个
- bf.mexists [keyname] [username] […]

布隆过滤器可以使用构造指令进行创建，降低误判的可能性：

bf.reserve [key] [error_rate] [initial_size]

initialSize表示预计放入的元素数量，error_rate表示在达到预计放入元素数量的大小之前，可能出现的最大的误判概率。

元素实际数量超过initialSize时，误判的概率会比error_rate大。
error_rate越小，需要的空间越大。

原理

每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

当一个值被放到bf中，这个值会被其中的hash函数计算出几个不同的数，放到对应的bucket中。

那么，当发生hash冲突的时候，算出的bucket对应的索引，应有的位置上就可能出现原来就有状态存在的情况，这也就解释了：

当容量过大，误判概率会增加
不曾进入bf的元素，也可能会被判断为存在bf中

的两个特性。

应用6，7 - 限流

应用6 - 简单限流

可以使用zset来实现一个简单的限流方式，算法如下：

使用一个滑动窗口来维护一定时间内的访问次数
- 我们使用zset中的score来规定时间窗口大小
- value只需要是固定的就可以
我们对于我们不关心的窗口外的数据直接删除，节约存储成本

优劣如下：

优点：
- 实现简单，不需要额外的数据结构
缺点：
- 消耗大量的存储空间

应用7 - 漏斗限流

漏斗限流是最常用的限流方法之一。

同样，在redis4.0中提供了一个限流模块 redis-cell，提供了原子限流指令。

该数据结构只有一条指令：

markdown复制代码> cl.throttle laoqian:reply 15 30 60 1
                      ▲     ▲  ▲  ▲  ▲
                      |     |  |  |  └───── need 1 quota (可选参数，默认值也是1)
                      |     |  └──┴─────── 30 operations / 60 seconds 这是漏水速率
                      |     └───────────── 15 capacity 这是漏斗容量
                      └─────────────────── key laoqian

应用8 - geoHash

geoHash是一个比较成熟的地理位置距离算法，redis也使用了，一般用于地理位置的计算，在如下场景中可以使用：

附近的人、车等

数据结构

简单地说，geoHash可以粗略地认为是将二维平面上的数添加到了一个一维数组中。

redis中式使用zset来进行geoHash数据的存储，因此相关的维护查询操作，也可以使用zset所提供的方法来进行。

指令

redis提供的geo指令共6个：

添加

geoadd setName 经度维度 name

可以添加多个三元组，如下：

geoadd setName 经度维度 name 经度维度 name1 …

至于删除，geoHash并没有geoDel的删除指令，但可以使用zrem指令来删除。

距离

使用geodist来计算两个元素之间的距离：

geodist setName name1 name2 单位

例如：

geodist company juejin ireader km

单位指的是距离单位，可以是：

m , km ,ml, ft

指的是米，千米，英里，尺

获取元素位置

既然可以存进去，那么相同的也可以取出来：

geopos setName name

例如：

geopos company juejin

“116.48104995489120483”

“39.99679348858259686”

这样子可以获取存进去的经纬度。而由于geohash是将二维坐标映射的是一维的一个数，因此还原出来的经纬度和存进去的数据是有较小的差别的。

获取元素hash值

geohash可以获取到经纬度编码之后的字符串：

geohash setName name

例如：

geohash company ireader

查找附近的元素

对于这个数据结构，最需要的功能就是查找附近的元素。

使用georadiusbymember，来查找该元素附近的其他元素

该指令有以下几种用法：

查找距离内的临近元素

georadiusbymember setName key distance count n asc

指的是在setName中，查找set中距离key，distance范围内，按距离正排（从近到远）n个

这个指令的查询结果，会包含自身，例如：

georadiusbymember company ireader 20 km count 3 asc

这个指令可以做出对应的修改：

同样使用desc可以倒排：

georadiusbymember company ireader 20 km count 3 desc

可以带上withdist可以显示距离，带上withcoord显示经纬度，带上withhash就显示哈希值
georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc

会输出：
1
2
3
4
5
6
7
> > > bash复制代码1) 1) "ireader"
> > >   2) "0.0000"
> > >   3) (integer) 4069886008361398
> > >   4) 1) "116.5142020583152771"
> > >      2) "39.90540918662494363"
> > > 
> > >

同样地，我们也可以对不在数据集中的坐标来进行类似的查询，只是将key替换成经纬度了：

georadius company 116.514202 39.905409 20 km withdist count 3 asc

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

【redis】数据结构及其应用应用1 - 分布式锁应用