Redis -- 基础数据结构

数据结构

Redis所有的数据结构都是以唯一的key字符串作为名称,然后通过该唯一key值来获取相应的value值

string

  1. Redis的字符串是动态字符串,是可以修改的字符串,内部结构实现上类似与Java的ArrayList
    • 采用预分配冗余空间的方式来减少内存的频繁分配
  2. 当字符串长度小于1M时,扩容都是加倍现有的空间,如果超过1M,扩容时一次只会多扩1M的空间
    • 字符串最大长度为512M

键值对

1
2
3
4
5
6
7
8
9
10
> set name zhongmingmao
OK
> get name
"zhongmingmao"
> exists name
(integer) 1
> del name
(integer) 1
> get name
(nil)

批量键值对

批量对多个字符串进行读写,节省网络开销

1
2
3
4
5
6
7
8
9
10
11
12
13
14
> set name1 zhongmingmao
OK
> set name2 zhongmingwu
OK
> mget name1 name2 name3
1) "zhongmingmao"
2) "zhongmingwu"
3) (nil)
> mset name1 a name2 b name3 unknown
OK
> mget name1 name2 name3
1) "a"
2) "b"
3) "unknown"

过期和set命令扩展

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
> set name zhongmingmao
OK
> get name
"zhongmingmao"
> expire name 5
(integer) 1
> get name # 等5S后
(nil)
> setex name 5 zhongmingmao
OK
> get name
"zhongmingmao"
> get name # 等5S后
(nil)
> setnx name zhongmingmao
(integer) 1
> get name
"zhongmingmao"
> setnx name zhongmingwu
(integer) 0 # name已存在,set失败
> get name
"zhongmingmao" # 结果不变

计数

如果value是一个整数,可以对其进行自增操作,自增是有范围的,即signed long的最大值和最小值

1
2
3
4
5
6
7
8
9
10
11
12
> set age 30
OK
> incr age
(integer) 31
> incrby age 5
(integer) 36
> incrby age -5
(integer) 31
> set age 9223372036854775807 # Long.Max
OK
> incr age
(error) ERR increment or decrement would overflow

list

  1. Redis的列表相当于Java的LinkedList插入删除的时间复杂度为O(1),但索引定位的时间复杂度为O(n)
  2. 当列表弹出最后一个元素后,该数据结构自动被删除,内存被回收

队列

1
2
3
4
5
6
7
8
9
10
11
12
> rpush books python java golang
(integer) 3
> llen books
(integer) 3
> lpop books
"python"
> lpop books
"java"
> lpop books
"golang"
> lpop books
(nil)

1
2
3
4
5
6
7
8
9
10
> rpush books python java golang
(integer) 3
> rpop books
"golang"
> rpop books
"java"
> rpop books
"python"
> rpop books
(nil)

慢操作

  1. index相当于Java链表的get(int index)方法,需要对链表进行遍历,性能随着参数index增大而变差
    • index可以是负数index=-1表示倒数第一个元素
  2. ltrim start_index end_index定义了一个区间,在这个区间内的值要保留
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> rpush books python java golang
(integer) 3
> lindex books 1 # O(n)
"java"
> lrange books 0 -1 # O(n)
1) "python"
2) "java"
3) "golang"
> ltrim books 1 -1 # O(n)
OK
> lrange books 0 -1
1) "java"
2) "golang"
> ltrim books 1 0 # 清空整个列表,因为区间范围长度为负
OK
> llen books
(integer) 0

快速列表

  1. 列表元素较少的情况下会使用一块连续的内存存储,该结构称为ziplist,即压缩列表
  2. 数据比较多的时候,才会改成quicklist
  3. 这是因为普通的链表需要的附加指针空间太大,会比较浪费空间,而且会加重内存的碎片
  4. Redis将链表ziplist结合起来组成quicklist
    • 将多个ziplist使用双向指针串联,这样即能满足快速的插入删除性能,又不会出现太大的空间冗余

hash

  1. Redis中的字典相当于Java中HashMap,是无序字典,同样使用数组+链表实现
  2. 但Redis的字典的值只能是字符串rehash的方式也不一样
    • Java的HashMap在字典很大时,rehash非常耗时,因为需要一次性全部rehash
    • Redis为了高性能,不阻塞服务,采用渐进式rehash策略
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
> hset books java 'think in java'
(integer) 1
> hset books golang 'concurrency in go'
(integer) 1
> hset books python 'python cookbook'
(integer) 1
> hgetall books
1) "java"
2) "think in java"
3) "golang"
4) "concurrency in go"
5) "python"
6) "python cookbook"
> hlen books
(integer) 3
> hget books java
"think in java"
> hset books golang 'learning go programming' # 因为是更新操作,所以返回0
(integer) 0
> hget books golang
"learning go programming"
> hmset books java 'effective java' python 'learning python' golang 'modern golang programming' # 批量set
OK
> hincrby zhongmingmao age 18
(integer) 18
> hget zhongmingmao age
"18"

渐进式rehash

  1. 渐进式rehash会在rehash的同时,保留新旧两个hash结构,查询时会同时查询两个hash结构
  2. 在后续的定时任务中以及hash操作指令中,循序渐进地将旧hash的内容迁移到新的hash结构中
  3. 当搬迁完成后,就会使用新的hash结构,当hash移除最后一个元素后,该数据结构会被自动删除,内存被回收

set

  1. Redis的集合相当于Java的HashSet,内部的键值对是无序且唯一
  2. 内部实现相当于一个特殊的字典,字典中所有的value都是一个值NULL
  3. 当集合中最后一个元素被移除后,数据结构自动删除,内存被回收
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> sadd books python
(integer) 1
> sadd books python
(integer) 0 # 重复
> sadd books java golang
(integer) 2
> smembers books # 无序
1) "golang"
2) "java"
3) "python"
> sismember books java # contains
(integer) 1
> sismember books rust
(integer) 0
> scard books # count
(integer) 3
> spop books
"golang"

zset

  1. Redis的有序集合类似于Java的SortedSetHashMap的结合体
    • 一方面zset是一个set,保证内部value的唯一性
    • 另一方面zset给每个value赋予了一个score,代表value的排序权重
  2. zset中最后一个value被移除后,数据结构自动删除,内存被回收
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
> zadd books 9.0 'think in java'
(integer) 1
> zadd books 8.9 'java concurrency'
(integer) 1
> zadd books 8.6 'java cookbook'
(integer) 1
> zrange books 0 -1
1) "java cookbook"
2) "java concurrency"
3) "think in java"
> zrevrange books 0 -1
1) "think in java"
2) "java concurrency"
3) "java cookbook"
> zcard books # count
(integer) 3
> zscore books 'java concurrency'
"8.9000000000000004" # double存储,存在精度问题
> zrank books 'java concurrency'
(integer) 1
> zrangebyscore books 0 8.91
1) "java cookbook"
2) "java concurrency"
> zrangebyscore books -inf 8.91 withscores
1) "java cookbook"
2) "8.5999999999999996"
3) "java concurrency"
4) "8.9000000000000004"
> zrem books 'java concurrency'
(integer) 1
> zrange books 0 -1
1) "java cookbook"
2) "think in java"

跳跃表

  1. zset内部的排序功能是通过跳跃表来实现的
  2. 跳跃表之所以跳跃,是因为内部的元素可能身兼数职
    • 下图中间的元素,同时处于L0、L1和L2层,可以快速在不同层次之间进行跳跃
  3. 定位插入点时,先在顶层进行定位,然后下潜到下一层定位,一直下潜到最底层找到合适的位置,将新元素插进去
  4. 跳跃表采用随机策略来决定新元素可以兼职到第几层
    • L0层为100%的概率,L1层为50%的概率,L2层为25%的概率,L3层为12.5%的概率,一直随机到最顶层L31

通用规则

  1. list/hash/set/zset都是容器型数据结构,有两条通用规则
  2. create if not exists !!
  3. drop if no elements !!

过期时间

  1. 过期是以对象为单位的,如一个hash结构的过期是整个hash对象的过期,而不是其中的某个子key过期
  2. 如果一个字符串已经设置了过期时间,然后再调用set方法修改了它,那么它的过期时间会消失
1
2
3
4
5
6
7
8
9
10
> set name zhongmingmao
OK
> expire name 600
(integer) 1
> ttl name
(integer) 597
> set name zhongmingwu
OK
> ttl name
(integer) -1
0%