Redis RU101课程 Introduction to Redis Data Structures 第2周学习笔记

Capped Collections & Set Operations

Cardinality & Capped Collections

首先谈到了基数(cardinality)的概念，对于List使用"LLEN"，Set使用"SCARD"，Sorted Set使用"ZCARD"。

由于List并不唯一，所有可以认为是近似的基数。

capped collection是常用的数据结构，可用于排行榜(Sorted Set)，最近活动(List)等。

在MongoDB中的定义如下：

Capped collections are fixed-size collections that support high-throughput operations that insert and retrieve documents based on insertion order. Capped collections work in a way similar to circular buffers: once a collection fills its allocated space, it makes room for new documents by overwriting the oldest documents in the collection.

用List的L/RPUSH + LTRIM可实现capped collection，如activity stream(最近3个帖子):

127.0.0.1:6379> RPUSH list1 a b c d e
(integer) 5
127.0.0.1:6379> ltrim list1 0 2
OK
127.0.0.1:6379> lrange list1 0 -1
1) "a"
2) "b"
3) "c"
127.0.0.1:6379> llen list1
(integer) 3
127.0.0.1:6379> lpush list1 f
(integer) 4
127.0.0.1:6379> ltrim list1 0 2
OK
127.0.0.1:6379> lrange list1 0 -1
1) "f"
2) "a"
3) "b"

用Sorted Set的ZADD + ZREMRANGEBYRANK可实现capped collection，如排行榜(前3名):

127.0.0.1:6379> zadd set1 1 a 2 b 3 c 4 d
(integer) 4
127.0.0.1:6379> zremrangebyrank set1 0 0
(integer) 1
127.0.0.1:6379> zrange set1 0 -1
1) "b"
2) "c"
3) "d"
127.0.0.1:6379> zadd set1 26 z
(integer) 1
127.0.0.1:6379> zremrangebyrank set1 0 0
(integer) 1
127.0.0.1:6379> zrange set1 0 -1
1) "c"
2) "d"
3) "z"

有两点需要注意:

所有的index都是从0开始，-1表示最右边的元素，0表示最左边
LTRIM是截取并保留其中的一段，而ZREMRANGEBYRANK是截取并去除其中的一段

Set Operations with Sets and Sorted Sets

zinterstore在集合操作的同时，还可以做聚合操作，如汇总：

127.0.0.1:6379> zadd sales:food 1000 user1 2000 user2 3000 user3
(integer) 3
127.0.0.1:6379> zadd sales:cloth 100 user2 300 user3 400 user4
(integer) 3
127.0.0.1:6379> zinterstore sales:both 2 sales:food sales:cloth aggregate sum
(integer) 2
127.0.0.1:6379> zrange sales:both 0 -1 withscores
1) "user2"
2) "2100"
3) "user3"
4) "3300"

Sorted Set和Set之间也可以做集合操作，如下例，weights参数赋予每一个集合权重，对于Sorted Set，需要乘以权重，对于Set，权重就是Score。最后max指定最大值：

127.0.0.1:6379> sadd sales:book user1 user2 user3
(integer) 3
127.0.0.1:6379> zinterstore sales:both 3 sales:food sales:cloth sales:book weights 1.2 0.8 2500 aggregate max
(integer) 2
127.0.0.1:6379> zrange sales:both 0 -1 withscores
1) "user2"
2) "2500"
3) "user3"
4) "3600"

zunionstore也可以结合聚合操作，下例为会议厅可容纳人数，已报名用户数，最终为余下的座席：

127.0.0.1:6379> zadd rooms:capacity 100 "room1" 120 "room2" 80 "room3"
(integer) 3
127.0.0.1:6379> zadd rooms:attendee -50 "room1" -80 "room2"
(integer) 2
# 以下命令中的2，表示有2个集合
127.0.0.1:6379> zunionstore rooms:free 2 rooms:capacity rooms:attendee aggregate sum
(integer) 3
127.0.0.1:6379> zrange rooms:free 0 -1 withscores
1) "room2"
2) "40"
3) "room1"
4) "50"
5) "room3"
6) "80"

Use Case: Faceted Search

Use Case Overview

属性搜索的3方法:

Object inspection
Faceted search
Hashed index

我们设定的场景是搜索大会中感兴趣的活动，最终返回活动地点:

是否允许访问：yes/no
medal event(奖牌项目): yes/no
活动地点: 字符串

为提高读取性能，传统的方式是secondary index和full text search(如Solr和Lucene)。前者有存储和维护(更新统计信息等)开销，后者较复杂，并且有最终一致性问题。

“there are lies, damned lies and then there are statistics”，谎言，该死的谎言，还有统计数字 - 马克吐温。

redis的方法是faceted search，也称为inverted search。

What is Faceting?

Redis没有索引。

以下的例子中，会用到JSON，因此定义key时需要用\转义：

127.0.0.1:6379> set key01 "{\"name\": \"grace\", \"married\" : true}"
OK
127.0.0.1:6379> get key01
"{\"name\": \"grace\", \"married\" : true}"

Method 1: Object Inspection

此方式遍历所有对象，然后比较属性。可以用SCAN CURSOR实现:

127.0.0.1:6379> scan 0 match uc01:event:* count 10000
1) "6861"
2) 1) "uc01:event:320-GHI-921"2) "uc01:event:123-ABC-723"
127.0.0.1:6379> scan 6861 match uc01:event:* count 10000
1) "0"
2) 1) "uc01:event:737-DEF-911"127.0.0.1:6379> get uc01:event:320-GHI-921
"{\"sku\": \"320-GHI-921\", \"name\": \"Womens Judo Qualifying\", \"disabled_access\": false, \"medal_event\": false, \"venue\": \"Nippon Budokan\", \"category\": \"Martial Arts\"}"

SCAN这一组命令还包括SSCAN, HSCAN和ZSCAN。用来遍历key和set中的元素。参数中count指定每次遍历的数量，match则是匹配。

SCAN命令使用cursor指定开始遍历的位置，从0开始，到0结束。

time complexity(时间复杂度)，例如O(1)表示无论有多少key，获取单个key的时间复杂度是一样的。当然，时间复杂度和时间不一样，例如key是1个字节和512M字节获取时间是不一样的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GZPE7gNQ-1606992662239)(https://upload.wikimedia.org/wikipedia/commons/7/7e/Comparison_computational_complexity.svg)]

上图来自Wiki, O(1)表示常数，O(n)是线性的，其中的n表示数据量，也就是数据增长n倍，耗时也增长n倍。

示例程序位于：

$ cd redisu/ru101/uc01-faceted-search
$ python search.py

Python示例程序就不说了，大致的意思就是遍历所有key，然后查询其中的元素看是否有匹配，显然这是最慢的。

此方式的限制因素是：The number of keys that have to be matched and inspected

Method 2: Set Intersection

此方式即faceted搜索，的原理是将属性直接变成了集合，集合的元素为属性的所有取值：

127.0.0.1:6379> type fs:medal_event:False
set
127.0.0.1:6379> smembers fs:medal_event:True1) "UNPP-AFLY-OBAS-DROW"2) "ESBH-EXHY-UEHW-BJAV"
...
127.0.0.1:6379> smembers fs:medal_event:False1) "YWMH-CRYC-AIEW-DVTG"2) "POPA-WMEI-PYLB-TROD"
...
127.0.0.1:6379> smembers fs:disabled_access:True1) "IQUO-UECK-JHFT-VJMU"2) "CDDW-AYPH-TWHN-GDSE"
...
127.0.0.1:6379> smembers fs:disabled_access:False1) "CNES-UCOW-QIPX-SJUR"2) "YWMH-CRYC-AIEW-DVTG"
...

然后用集合操作即可得出两个条件均满足的成员：

127.0.0.1:6379> sinter fs:medal_event:True fs:disabled_access:True1) "WKVM-YBPQ-YKBP-NYTP"2) "NXJO-WCKP-ZNGO-GSPM"

SINTER的时间复杂度为最小集合的基数/尺寸和参与intersect的集合数。即O(N*M)

此方式的限制因素是：

The data distribution of the attribute values being matched
The number of attributes that have to be matched

Method 3: Hashed Keys

这种方式也叫做hashed faceted搜索。

首先提到了compounded index(复合索引)的概念，因为此方式其实是将所有搜索属性取值的组合变成集合，然后存放满足条件的元素。

然后复合索引的顺序是有关系的，例如索引(A, B, C)建立后，你可以搜索(A), (A, B)但不能搜索(B, C)，也就是要从头部开始匹配，所以访问模式需确定。

127.0.0.1:6379> scan 0 count 100 match uc01:hfs*
1) "0"
2) 1) "uc01:hfs:ff9f5140ff7b21b914a51a069a027180e184b87ca1824ec2de840c165716b1d7"2) "uc01:hfs:ccbd52068232875862cafc74eeee36c7dee321c0b1930d1fa35d13ae6b17d4d4"3) "uc01:hfs:fdd9a1369ce6c21d3e79df407275e059918f76b990eb4cdb261a7b64aa5e5bc5"4) "uc01:hfs:07155e9fc74fbe3ac122d90a53cba8ff2f7e3667206149f5f644d476b87cc11b"5) "uc01:hfs:4b9b25e7307f27d0aa0ba51e98f5e6350955d1aa86ef5dc3d1fdc46ddaf5c5e5"6) "uc01:hfs:2d2b450a5c4329bf03b4b4ad9171120d31b91b61c555e82bfa5739d4f4329e57"7) "uc01:hfs:53f665a5a010ec42a900ee9e762cd8226dfd635b051882e32f8d04ed7c09201d"8) "uc01:hfs:2466461538f464dbc1d13033d3e9b1b4ab685c937d02e542a766b2686f301d80"
127.0.0.1:6379> get "uc01:event:123-ABC-723"
"{\"sku\": \"123-ABC-723\", \"name\": \"Men's 100m Final\", \"disabled_access\": true, \"medal_event\": true, \"venue\": \"Olympic Stadium\", \"category\": \"Track & Field\"}"
127.0.0.1:6379> get "uc01:event:737-DEF-911"
"{\"sku\": \"737-DEF-911\", \"name\": \"Women's 4x100m Heats\", \"disabled_access\": true, \"medal_event\": false, \"venue\": \"Olympic Stadium\", \"category\": \"Track & Field\"}"
127.0.0.1:6379> get "uc01:event:320-GHI-921"
"{\"sku\": \"320-GHI-921\", \"name\": \"Womens Judo Qualifying\", \"disabled_access\": false, \"medal_event\": false, \"venue\": \"Nippon Budokan\", \"category\": \"Martial Arts\"}"127.0.0.1:6379> smembers "uc01:hfs:ff9f5140ff7b21b914a51a069a027180e184b87ca1824ec2de840c165716b1d7"
1) "737-DEF-911"
127.0.0.1:6379> smembers "uc01:hfs:ccbd52068232875862cafc74eeee36c7dee321c0b1930d1fa35d13ae6b17d4d4"
1) "123-ABC-723"
127.0.0.1:6379> smembers "uc01:hfs:07155e9fc74fbe3ac122d90a53cba8ff2f7e3667206149f5f644d476b87cc11b"
1) "737-DEF-911"
127.0.0.1:6379> smembers "uc01:hfs:4b9b25e7307f27d0aa0ba51e98f5e6350955d1aa86ef5dc3d1fdc46ddaf5c5e5"
1) "320-GHI-921"
127.0.0.1:6379> smembers "uc01:hfs:2d2b450a5c4329bf03b4b4ad9171120d31b91b61c555e82bfa5739d4f4329e57"
1) "320-GHI-921"
127.0.0.1:6379> smembers "uc01:hfs:53f665a5a010ec42a900ee9e762cd8226dfd635b051882e32f8d04ed7c09201d"
1) "320-GHI-921"

以上输出中有8个key，是因为3个属性，每个属性只有2种取值(前两个属性是Bool，最后一个只有两个地点)。因此2*2*2=8。

key的名字是以下字符串的哈希值：

[('disabled_access', True)]
[('disabled_access', True), ('medal_event', True)]
[('disabled_access', True), ('medal_event', True), ('venue', 'Olympic Stadium')]
[('disabled_access', True)]
[('disabled_access', True), ('medal_event', False)]
[('disabled_access', True), ('medal_event', False), ('venue', 'Olympic Stadium')]
[('disabled_access', False)]
[('disabled_access', False), ('medal_event', False)]
[('disabled_access', False), ('medal_event', False), ('venue', 'Nippon Budokan')]

根据复合索引的规则，属性的顺序是固定的。

可以看一下哈希值如何生成的，集合中存的是SKU。

$ echo -n "[('disabled_access', True)]"|sha256sum
2466461538f464dbc1d13033d3e9b1b4ab685c937d02e542a766b2686f301d80  -
127.0.0.1:6379> smembers "uc01:hfs:2466461538f464dbc1d13033d3e9b1b4ab685c937d02e542a766b2686f301d80"
1) "123-ABC-723"
2) "737-DEF-911"$ echo -n "[('disabled_access', True), ('medal_event', True)]" | sha256sum
fdd9a1369ce6c21d3e79df407275e059918f76b990eb4cdb261a7b64aa5e5bc5  -
127.0.0.1:6379> smembers "uc01:hfs:fdd9a1369ce6c21d3e79df407275e059918f76b990eb4cdb261a7b64aa5e5bc5"
1) "123-ABC-723"

搜索时，只需计算组合属性的哈希值，就得到了集合的key，然后返回集合中所有元素即可（使用SSCAN，时间复杂度为O(N)）。

这种方式适合于数据变化量不大的场景。

限制因素：The number of matches for any given attribute combination correct

Big O Notation and Redis Commands

为保证命令的原子性，Redis在服务器端使用单线程顺序执行这些命令。这样，最后执行的命令需要等待之前的命令执行完，因此命令的执行时间就很重要了。

Big O表示法，是德国数学家Edmund Landau和Paul Bachmann发明的，O是德语Ordung，就是order of的意思。

APPEND, EXISTS, GET, SET, HGET, LPUSH,RPOP 等的时间复杂度都是O(1)。

你会注意到，在redis的命令帮助中，都说明了时间复杂度，例如DEL。
删除1个元素时是O(1)，删除N个时是O(N)。如果是删除list，set等，则是O(M)，M是集合中的元素。

SINTER的时间复杂度是O(N*M), N表示最小集合的技术，M表示参与intersection的集合数。

LRANGE的时间复杂度是O(S+N), N是指定的range。对于小列表，S表示到头部的距离，对于大列表，S从到头和尾距离中取小的一个。

, LPUSH,RPOP 等的时间复杂度都是O(1)。

SINTER的时间复杂度是O(N*M), N表示最小集合的技术，M表示参与intersection的集合数。

LRANGE的时间复杂度是O(S+N), N是指定的range。对于小列表，S表示到头部的距离，对于大列表，S从到头和尾距离中取小的一个。

即使时间复杂度一样，但并不表示其执行时间是不变/一样的，因为还取决于数据的大小，网络等，基数，数据在集合中的位置，数据结构等。具体取决于测试。