redis 数据结构
2020-12-04 本文已影响0人
BoBot
Key操作
命令
keys *
keys n*e
keys n?
scan 0
scan 0 match xxx* count 1000
del key1 key2
unlink key1 key2
exists key1
rename a b
expire a 10
ttl a
type a
dbsize
randomkey
debug object key1
flushdb async
flushall async
scan要点
-
count参数代表扫描的槽位数
-
返回为0表示全部扫描完成，否则根据返回游标继续扫描直到返回为0
-
结果里的key可能重复，需要去重
-
高位进位加法
普通加法：右侧加1，依次进位
高位进位加法：左侧添1
解决：避免扫描时扩容或缩容及rehash导致的对遍历过的槽位进行重复遍历。
大key扫描
#每100个scan指令就休息0.1
src/redis-cli --bigkeys -i 0.1
String
使用
set key value [EX seconds] [PX milliseconds] [NX(不存在才成功)|XX（已存在才成功）]
eg: set name imooc EX 10 NX
set name imooc
mset name imooc age 10
get name
mget name1 name2
getset name imooc
del name
incr a
decr a
incrby a 100
decrby a 100
append name zhangsan
setnx name imooc (如果存在key，则失败，返回0)
msetnx name libo age 10 （有一个失败，整个都失败）
setex name 10 libo （设置失效时间）
getrange name 0 5 （截取字符，从索引0到索引5）
原理
- SDS（Simple Dynamic String）
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; //1byte，目前长度
uint64_t alloc; //1byte，分配长度
unsigned char flags; //1byte，使用不同结构体的标志位
char buf[]; //内容
};
- 所有Redis对象的header，共16bytes。
struct RedisObject {
int4 type; // 4bits 类型
int4 encoding; // 4bits 存储格式
int24 lru; // 24bits 记录LRU信息
int32 refcount; // 32bits 引用计数
void *ptr; // 8bytes，64-bit，指向对象内容的指针
} robj;
- 字符串存储形式
embstr：长度小于44（64 - 16 - 3），一次性分配空间，header和sds内存地址连续
raw：长度大于44（64 - 16 - 3），两次分配空间，header和sds内存地址不连续 - 扩容
1M以前，每次X2
1M以后，每次+1M - 优势
1、长度获取，O(1)
2、空间预分配，空间惰性释放
3、二进制安全：可存储任意二进制
Hash
使用
hset myhash username "hello world"
hmset myhash a 1 b 2
hget myhash username
hmget myhash a b
hgetall myhash
hdel myhash a
hdel myhash a b
hincrby myhash a 100
hexists myhash a
hlen myhash
hkeys myhash
hvals myhash
hash里最后一个key移除后自动销毁数据结构
原理
类似Java HashMap，数组+链表
渐进式rehash
List
使用
lpush mylist a b c (insert by left side)
c index:0/-3
b index:1/-2
a index:2/-1
rpush mylist a b c (insert by right side)
a index:0/-3
b index:1/-2
c index:2/-1
lindex mylist 0
lrange mylist 0 -1 (show item from first to the end)
lrange mylist 0 -2 (show item from first to the reciprocal second)
lpop mylist (eject the the left item)
rpop mylist
llen mylist
lpushx mylist x (insert x into the left side when mylist has items)
rpushx mylist x
lrem mylist 0 a (remove all item is a in mylist)
lrem mylist 2 a (remove two a from the beginning)
lrem mylist -2 a (remove two a from the end)
lset mylist 3 x (insert x which the index is 3)
linsert mylist before a x (insert x before the first a)
linsert mylist after a x (insert x after the first a)
rpoplpush mylist mylist2 (eject the right item in mylist and insert it into the left side in mylist2)
blpop key1 key2 timeout（阻塞获取数据）
没有元素自动销毁数据结构
原理
链表
数据少时ziplist：连续内存存储
数据多时quicklist：多个ziplist+双向指针，快速增删
Set
使用
sadd myset a b c
sadd myset a (can not success)
srem myset a b
smembers myset
sismember myset a
sdiff myset1 myset2 (myset1 - myset2)
sinter myset1 myset2 (交集)
sunion myset1 myset2 (并集)
scard myset
srandmember myset
sdiffstore newset1 oldset1 oldset2
sinterstore newset1 oldset1 oldset2
sunionstore newset1 oldset1 oldset2
没有元素自动销毁数据结构
原理
类似Java HashSet，无序，唯一
value为null的字典
IntSet
- set里都是整数且数量少
typedef struct intset {
uint32_t encoding; //决定整数位宽，16位、32位、64位
uint32_t length; //元素个数
int8_t contents[]; //整数数组，可以是16位、32位、64位
} intset;
- 存入非整数
debug结果为hashtable
SortedSet
使用
zadd mysort 70 a 80 b 90 c
zadd mysort 100 a (replace the a's score)
zscore mysort a (show a's score)
zcard mysort （show count）
zrem mysort a b
zrange mysort 0 -1 (show all items by score asc)
zrange mysort 0 -1 withscores （从小到大）
zrevrange mysort 0 -1 withscores （从大到小）
zrangebyscore mysort 0 100 withscores limit 0 2
zrank mysort b (show rank of b，从小到大)
zrevrank mysort b (show rank of b，从大到小)
zremrangebyrank mysort 0 4 (remove by index)
zremrangebyscore mysort 80 100 (remove by score)
zincrby mysort 10 a (add 10 to item a)
zcount mysort 80 90
可以实现需轮询的延迟任务
最后一个value被删除销毁数据结构
原理
跳跃表
指针包含属性跨度span
ziplist（压缩列表）
zset和hash元素较少时采用ziplist存储
连续内存空间
debug结果ziplist
cascade update（字段记录前一个节点的长度且字段占用可变的空间）
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
// ziplist存储2和5
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
| | | | | |
zlbytes zltail entries "2" "5" end
//Hello world的entries部分
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
quicklist（快速列表）
debug结果是quicklist
image
- list-max-ziplist-size -2
配置正数，ziplist里的数据项
| 配置负数 | ziplist大小 |
|---|---|
| -1 | 4kb |
| -2 | 8kb |
| -3 | 16kb |
| -4 | 32kb |
| -5 | 64kb |
- list-compress-depth 0
LZF无损压缩中间节点
| 配置 | 解释 |
|---|---|
| 0 | 没节点压缩 |
| 1 | 两端各1个节点不压缩，中间压缩 |
| 2 | 两端各2个节点不压缩，中间压缩 |
| ... | ...（以此类推） |
listpack
类似ziplist
本entry的长度字段放末尾
消除cascade update
Bitmap
使用
set AB ab
index 0-15
0110,0001; 0110,0000
getbit AB 6
setbit AB 6 1
get AB
bitcount AB （统计值为1的数量）
bitcount AB 0 0 （第一个字符的统计1数量）
bitcount AB 1 1 （第二个字符的统计1数量）
bitop对多个key做位元操作，AND，OR，XOR，NOT
原理
-
buffer[]逆序存储，方便在更高位修改且不移动原有位
例如字符ab
手写顺序
buffer[0] -> b -> 0110,0010
buffer[1] -> a -> 0110,0001
逆序存储顺序
buffer[0] -> a -> 0110,0001
buffer[1] -> b -> 0110,0010 -
bitcount使用查表算法和variable-precision SWAR算法
HyperLogLog
使用
-
count
基数（去重）统计（PV - Page View、UV - Unique View、IP等）。有误差。 -
命令
pfadd key element [element...]
pfcount key
pfmerge destkey sourcekey [sourcekey...]
原理
(较复杂...)
BloomFilter
使用
- contains。
判断结果为included时，可能误判。结果为not-include时，没有误判。
过滤结果为没见过时，可能误判。过滤结果为见过时，没有误判。
Image
-
使用场景
1、爬虫过滤相同url
2、推送过滤相同信息（文章、视频）
3、反垃圾信息（邮件、短信）
4、解决缓存击穿 -
命令
bf.reserve key 0.001 50000
bf.add key value
bf.exists key value
bf.madd key value1 value2
bf.mexists key value1 value2 value3
原理
数据经过多次hash落入位图。
空间占用在线计算：http://krisives.github.io/bloom-calculator/
（较复杂）
详解：https://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html
Geo
使用
- 命令
geoadd
geoadd key longitude latitude member [longitude latitude member ... ]
zrem
zrem key member [member ... ]
geopos
geopos key member [member ... ]
geodist
geodist key member1 member2 [m(米)|km(千米)|ft(英尺)|mi(英里)]
geohash
geohash member [member ... ]
georadius
georadius key longitude latitude distance m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [Count count] [ASC(由近到远)|DESC(从远到近)]
georadiusbymember
类似上面命令
georadius key member distance m|km|ft|mi ......
- 注意点
- 存入后轻微损失精度。
- (按省、市、区）拆分数据防止key对应数据量过大。
原理
- GeoHash原理
- 经度按[-90, 90]对半分，左0右1，不断递归。
- 维度同理，按[-180, 180]对半分，左0右1，不断递归。
- 得到两串编码xxx, yyy，偶数位放经度，奇数位放纬度，得到zzz。
- zzz进行base32编码（转十进制进行字符映射）
- GeoHash空间填充曲线
image
image
- GeoHash注意点
GeoHash解决的是点数据问题，不适合线和面数据。
解决边界问题：同时计算本区域周围8块区域的所有点。
解决空间曲线突变问题：筛选出个别相似编码编码进行计算。
