列表( list)类型是用来存储多个有序的字符串,a、b、c、d、e五个元素从左到右组成了一个有序的列表,列表中的每个字符串称为元素(element),一个列表最多可以存储2的32次方-1个元素。在Redis 中,可以对列表两端插入( push)和弹出(pop),还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是一种比较灵活的数据结构,它可以充当栈和队列的角色,在实际开发上有很多应用场景。
列表类型有两个特点:第一、列表中的元素是有序的,这就意味着可以通过索引下标获取某个元素或者某个范围内的元素列表。第二、列表中的元素可以是重复的。
key start end
索引下标特点:从左到右为0到N-1
lrange 0 -1命令可以从左到右获取列表的所有元素
lrem命令会从列表中找到等于value的元素进行删除,根据count的不同分为三种情况:
count>0,从左到右,删除最多count个元素。
count<0,从右到左,删除最多count绝对值个元素。
count=0,删除所有。
返回值是实际删除元素的个数。
: key index newvalue
下面操作会将列表listkey中的第3个元素设置为python
blpop
brpop
list可以命令停在这里,直到有元素才弹出,所以可以用于实现消息队列
blpop 和 brpop 是 lpop 和 rpop 的阻塞版本,除此之外还支持多个列表类型, 也支持设定阻塞时间,单位秒,如果阻塞时间为 0,表示一直阻塞下去。我们以 brpop 为例说明。
注意:brpop 后面如果是多个键,那么 brpop 会从左至右遍历键,一旦有一 个键能弹出元素,客户端立即返回。
如果多个客户端对同一个键执行 brpop,那么最先执行 brpop 命令的客户端 可以获取到弹出的值,其余的客户端依然处于阻塞。
列表类型可以用于比如:
消息队列,Redis 的 lpush+brpop 命令组合即可实现阻塞队列,生产者客户 端使用 lrpush 从列表左侧插入元素,多个消费者客户端使用 brpop 命令阻塞式的 “抢”列表尾部的元素,多个客户端保证了消费的负载均衡和高可用性。
文章列表 每个用户有属于自己的文章列表,现需要分页展示文章列表。此时可以考虑 使用列表,因为列表不但是有序的,同时支持按照索引范围获取元素。
实现其他数据结构
lpush+lpop = Stack(栈)
lpush +rpop = Queue(队列)
lpsh+ ltrim = Capped Collection(有限集合)
lpush+brpop =Message Queue(消息队列)
sinterstore(destination key)[key …]
suionstore(destination key) [key …]
sdiffstore (destination key) [key …]
集合间的运算在元素较多的情况下会比较耗时,所以 Redis 提供了上面三个 命令(原命令+store)将集合间交集、并集、差集的结果保存在 destination key 中,
例如
允许一次删除多个成员。
返回结果为成功删除的个数。
zinterstore destination numkeys key [key …] [weights weight [weight …]]
[aggregate sum / min / max]这个命令参数较多,下面分别进行说明
destination:交集计算结果保存到这个键。
numkeys:需要做交集计算键的个数。
key [key …]:需要做交集计算的键。
weights weight [weight …]:每个键的权重,在做交集计算时,每个键中的每个
member 会将自己分数乘以这个权重,每个键的权重默认是 1。
aggregate sum/ min |max:计算成员交集后,分值可以按照 sum(和)、min(最 小值)、max(最大值)做汇总,默认值是 sum。
不太好理解,我们用一个例子来说明。
zadd u2:gaokao 630 av 610 lison 578 leo 720 mark
zinterstore u_sum 2 u:gaokao u2:gaokao
zrange u_sum 0 -1 withscores
对 u:gaokao 和 u2:gaokao 进行加权平均计算
zinterstore u_avg 2 u:gaokao u2:gaokao weights 0.9 0.1
zrange u_avg 0 -1 withscores
zunionstore destination numkeys key [key …] [weights weight [weight …]]
[ aggregate sunmI minl max]
该命令的所有参数和 zinterstore 是一致的,只不过是做并集计算,大家可以 自行实验。
基于 list
参见 cn.enjoyedu.redis.redismq.ListVer
如果业务需求足够简单,想把 Redis 当作队列来使用,肯定最先想到的就 是使用 List 这个数据类型。 因为 List 底层的实现就是一个「链表」,在头部 和尾部操作元素,时间复杂度都是 O(1),这意味着它非常符合消息队列的模型。 如果把 List 当作队列,产者使用 LPUSH 发布消息,消费者这一侧,使用 RPOP 拉取消息。
而我们在编写消费者逻辑时,一般是一个「死循环」,这个逻辑需要不断地 从队列中拉取消息进行处理。如果此时队列为空,那消费者依旧会频繁拉取消息, 这会造成「CPU 空转」,不仅浪费 CPU 资源,还会对 Redis 造成压力。 怎么 解决这个问题呢? 也很简单,当队列为空时,我们可以「休眠」一会,再去尝 试拉取消息。
这个问题虽然解决了,但又带来另外一个问题:当消费者在休眠等待时,有 新消息来了,那消费者处理新消息就会存在「延迟」。 假设设置的休眠时间是 2s,那新消息最多存在 2s 的延迟。 要想缩短这个延迟,只能减小休眠的时间。 但休眠时间越小,又有可能引发 CPU 空转问题。
所以引入阻塞读 blpop 和 brpop(b 代表 blocking),阻塞读在队列没有数据 的时候进入休眠状态,
一旦数据到来则立刻醒过来,消息延迟几乎为零。 缺点也很明显,做消费者确认 ACK 麻烦,不能保证消费者消费消息后是否 成功处理的问题(宕机或处理异常等),通常需要维护一个 Pending 列表,保证 消息处理确认;不能做广播模式,如消息发布/订阅模型;不能重复消费,一旦 消费就会被删除;不支持分组消费。
基于 zset
参见 cn.enjoyedu.redis.redismq.ZsetVer
Zset 我们更多的是用来实现延时队列,将消息序列化成一个字符串作为 zset 的 value,这个消息的到期处理时间作为 score,然后用多个线程轮询 zset 获取 到期的任务进行处理。
Redis 的 zrem 方法是多线程多进程争抢任务的关键,它的返回值决定了当 前实例有没有抢到任务,因为 获取消息的方法可能会被多个线程、多个进程调 用,同一个任务可能会被多个进程线程抢到,迪过 zrem 来决定唯一的属主。
不过缺点很明显,消费者必须使用轮询的方式。
除了这两种,还有pub/sub发布订阅模式、redis5中的stream模式
bitcount [start] [end]
下面操作计算 08-15 这天的独立访问用户数量
[start]和[end]代表起始和结束字节数
bitop op destkey key [key . …]
bitop 是一个复合操作,它可以做多个 Bitmaps 的 and(交集)or(并 集)not(非)xor(异或)操作并将结果保存在 destkey 中。
bitpos key targetBit [start] [end]
计算 0815 当前访问网站的最小用户 id
除此之外,bitops 有两个选项[start]和[end],分别代表起始字节和结束字节。
本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构 (probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某 样东西一定不存在或者可能存在”。
相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但 是缺点是其返回的结果是概率性的,而不是确切的。
实际上,布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫 网址判重系统等,Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查 找不存在的行或列,以减少磁盘查找的 IO 次数,Google Chrome 浏览器使用了布 隆过滤器加速安全浏览服务。
在很多 Key-Value 系统中也使用了布隆过滤器来加快查询过程,如 Hbase, Accumulo,Leveldb,一般而言,Value 保存在磁盘中,访问磁盘需要花费大量时 间,然而使用布隆过滤器可以快速判断某个 Key 对应的 Value 是否存在,因此可 以避免很多不必要的磁盘 IO 操作。
通过一个 Hash 函数将一个元素映射成一个位阵列(Bit Array)中的一个点。 这样一来,我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就 是布隆过滤器的基本思想。
Hash 面临的问题就是冲突。假设 Hash 函数是良好的,如果我们的位阵列 长度为 m 个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能 容纳 m/100 个元素。显然这就不叫空间有效了(Space-efficient)。解决方法也 简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。
但是布隆过滤器的缺点是什么?
因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个 值 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 这个值存在。比如此时来一个不存在的 URL1000,他 经过哈希计算后。发现 bit 位为下:
但是这些 bit 位已经被 url1,url2,url3 置为 1,程序就会判断 URL1000 值存在。 这就是布隆过滤器的误判现象。所以:布隆过滤器判断存在的不一定存在,但是判断不存在的一定不存在。False is always false. True is maybe true.
布隆过滤器可精确的代表一个集合,可精确判断某一元素是否在此集合中, 精确程度由用户的具体设计决定,达到 100%的正确是不可能的。但是布隆过滤 器的优势在于,利用很少的空间可以达到较高的精确率。
很显然,过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会 返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率, 布隆过滤器越长其误报率越小。
另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的 速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变 高。
布隆过滤器的位数组的大小大小如何确定?
设 bitarray 大小为 m,样本数量为 n,允许失误率为 p,则
如何使得错误率最小,对于给定的 m 和 n,m 指位数组的大小,n 指插入元 素的个数,Hash 函数的个数为 k,错误率的计算公式为:
希望错误率最小,对于给定的 m 和 n,那么合适的 Hash 函数的个数为 k 计 算公式为: