Redis数据结构

redis有六种主要的数据类型，下面从调用API以及底层实现原理对于Redis中主要数据类型进行总结和整理，主要内容来自redis文档和《Redis设计与实现》。

底层数据结构

字符串(simple dynamic string)

字符串是Redis中最基本的数据类型，键和值的类型均为字符串类型，底层基于支持动态扩容的简单动态字符串（simple dynamic string,SDS）实现，其数据结构示例如下：

len：buf数组中已经使用的长度，遵循C语言字符串末尾添加空字符\0的习惯
free：buf数组中还剩余的长度

struct sdshdr{
    int len;
    int free;
    char buf[];
}

SDS的动态扩容机制类似于java中的ArrayList，当剩余空间不足以装下追加字符串时，SDS回进行扩容操作，多余的空间在有需要时，通过对应API可进行释放：

若追加后的SDS长度（len）小于1MB，分配和len大小相同的空间
若追加后的SDS长度（len）大于1MB，只分配1MB空间

A binary-safe function is one that treats its input as a raw stream of bytes and ignores every textual aspect it may have. The term is mainly used in the PHP programming language to describe expected behaviour when passing binary data into functions whose main responsibility is text and string) manipulating, and is used widely in the official PHP documentation

区别于C字符串，操作SDS的API将其视为二进制数据进行存储和处理，因此Redis字符串可以保存任意大小不超过512MB的二进制数据。

实现：键值

除去基本的get、set外，字符串类型还支持获取以及覆盖子串操作：

127.0.0.1:6379> get strKey
"newValue"
127.0.0.1:6379> getrange strKey 1 3
"ewV"
127.0.0.1:6379> setrange strKey 4 wwwc
(integer) 8
127.0.0.1:6379> get strKey
"newVwwwc"

链表(linkedlist)

Redis实现了双向无环链表，链表的每个节点存储一个字符串类型的值，最大长度 2^32 - 1 (4,294,967,295)，其数据结构实现示例如下：

typedef struct listNode{
    struct listNode *pre;
    struct listNode *next;
    void *value;
}

Reedis列表键、发布订阅监视器等功能都用到了链表实现。

实现：List(列表)

与其说是列表，不如说时双端队列，并不支持随机访问，添加删除API包括l/rpush,l/rpop,lrange,ltrim：

127.0.0.1:6379> lpush listKey left1 left2 left 3
(integer) 4
127.0.0.1:6379> rpush listKey right1 right2 right3
(integer) 7
127.0.0.1:6379> llen listKey
(integer) 7
127.0.0.1:6379> lrange listKey 1 3
1) "left"
2) "left2"
3) "left1"
127.0.0.1:6379> lpop listKey
"3"
127.0.0.1:6379> rpop listKey
"right3"

支持阻塞删除操作，即等到列表中存在元素能够删除返回元素

blpop
brpop

字典(hashtable)

redis字典即哈希表，基于链地址法解决冲突的哈希表实现，当哈希表的负载因子小/大到一定返回，Redis回进行rehash操作，重新开辟合适大小的哈希表，讲原哈希表上的键值对转移到新hash表上，其rehash的时机为：

当前服务器没有执行BGSAVE命令或者BGREWRITEAOF命令，且哈希表负载因子大于等于1
正在执行对应命令，且负载因子大于等于5
负载因子小于0.1

负载因子$\alpha$（load factor）的定义为:

n为哈希表总元素个数，k为哈希表长度

$load factor(\alpha) = \frac{n}{k}$

由于哈希表中可能存储成千上万个键值对，一次性完成rehash操作成本过高，Redis采用了渐进式的方式实现

记录当前rehashindex，指向当前即将rehash的位置，不进行rehashindex时设置为-1
每次对字典执行增删改查操作时，将rehashindex对应位置键值链表转移到新哈希表上
在rehash过程中，一次键值对访问可能需要访问两个哈希表（不在旧，但是在新）

rehash开辟新的hash表空间规则如下：

若是扩展操作，则新哈希表的大小为大于$n * 2$的最小2的幂次，其中n为原哈希表中元素个数
若是缩小操作，则i性能哈希表大小为大于n的最小2的幂次

实现：hashes(哈希表)

当哈希键包含的键值比较多，或者键值对中的元素都是比较长的字符串时，hashes底层实现基于字典

hashes对于key的数量没有约束，取决于当前是否存在剩余空间

常用API有：

127.0.0.1:6379> hset hashKey a 1 b 2 c 3
(integer) 3
127.0.0.1:6379> hget hashKey a
"1"
127.0.0.1:6379> hmget hashKey a b c
1) "1"
2) "2"
3) "3"
127.0.0.1:6379> hexists hashKey a
(integer) 1
127.0.0.1:6379> hkeys hashKey
1) "a"
2) "b"
3) "c"
127.0.0.1:6379> hvals hashKey
1) "1"
2) "2"
3) "3"

跳跃表(skiplist)

跳跃表是Redis有序集合的底层实现之一，数据结构原理不再总结，列几条Redis实现细节

Redis中每个跳表节点层高范围为1-32，在节点创建时随机确定
跳跃表中的节点大小按照score后key的方式确定

实现：sorted sets(有序集合)

当有序集合中的元素数量比较多，或者元素成员为较长的字符串时，有序集合就会采用跳表实现（总结就是“大”），支持的操作和集合基本一致：

增加元素：zadd
集合操作：zinter,zdiffer,zunion
优先队列操作：zpopmin，zpopmax

整数集合(intset)

整数集合是Redis Set的底层实现之一，其存储结构示意如下：

typedef struct intset{
	unit32_t encoding;
	uint32_rt length;
	int8_t contents[];
}

同时该数据结构支持集合的类型的自动升级和扩容：

encoding属性存储当前集合中的数据类型，当插入大于当前数据类型元素时，集合自动升级
自动升级方式为：首先将原有数据升级到对应类型（开辟空间，位置右移），再将新插入的值放在开头或者末尾。

书里没讲清楚的几点是：

扩容大小是扩容到刚好可以存储所有元素，还是类似于字典的扩容机制？
是否能向集合中插入字符串，由于set可以插入，如果可以插入，对应的升级机制是什么？

实现：Set（集合）

当Set中只包含整数且元素数量较少时，Redis使用整数集合作为Set的底层数据结构

压缩列表（ziplist）

压缩列表(ziplist)是列表和哈希表键值对类型的底层实现之一，其类似于一个内存上连续存储的链表：

每个元素不仅存储当前元素的数据，还存储前置元素的字节长度，元素与元素之间不存在间隔，通过字节长度确定元素位置。
列表头有三个字段：zlbytes,zltail,zllen分别记录压缩列表字节长度、压缩列表尾节点偏移量、压缩列表节点个数。

上述实现机制导致了压缩链表自能从尾向头遍历，首先访问ztail确定尾部元素位置，之后再不断的根据每个元素存储的前置元素长度，确定前置元素位置向前遍历。

记录前置元素长度的字段previous_entry_length的长度会基于前置元素长度改变：

当前置元素长度小于254byte时，使用1byte存储。
当前置元素长度大于等于254byte时，使用5byte存储，其中第一个byte存储254作为标识符，方便与情况1区别。

由于列表中的元素长度可修改，导致需要修改对应后置元素previous_entry_length长度变化，可能导致连锁更新问题

底层与实现之间的关系

Redis中共有5种常用数据类型，6种底层实现，两种之间通过抽象对象关联起来，定义结构如下：

k-v键值对类型为对象，对象内ptr指针指向具体的底层实现

typedef struct redisObject{
    unsigned type;
    unsigned encoding;
    vord *ptr;
}

通过对象这一层实现底层数据结构的抽象隔离，使得Redis能够数据结构以及内存管理更加灵活：

同一种kv值类型根据存储需求不同，可以对应不同的底层实现（数据量小使用小类型，数据量大使用正常类型，中间涉及到转换问题）
- string类型：int，emdstr，raw
- list类型：ziplist，quicklist(双向链表)
- set类型：intset，hashtable
- zset类型：ziplist，hashtable+skiplist
- hash类型：ziplist，hashtable
基于引用计数（refcount）的内存回收和常量共享机制
- 类型对象设置refcount属性，初始化为1，当程序使用/不再使用时对应加一减一，当refcount = 0时，对象占用内存会被释放
- 基于上述机制，Redis对包含整数值的字符串对象进行共享，即不创建新的，只是对refcount+1

其他数据类型

Bitmaps

string类型的一种拓展，将string当作一个bit数组，执行位操作，类似于动态规划中的状态压缩，通过bit代替原来占用空间更大的状态，实现空间上的压缩，支持的常用API包括

基本操作：setbit，getbit,bitcount
二进制的逻辑操作：bitop and/or/xor/not

bitmap存储格式为raw即动态字符串，长度似乎是动态分配的，初始化只有1byte，分配基本单位为byte

127.0.0.1:6379> setbit bitKey 1 1
(integer) 0
127.0.0.1:6379> bitcount bitKey
(integer) 1
127.0.0.1:6379> object encoding bitKey
"raw"
127.0.0.1:6379> setbit bitKey 100 1
(integer) 0
127.0.0.1:6379> bitop not newBit bitKey
(integer) 13
127.0.0.1:6379> bitcount newBit
(integer) 102

HyperLogLog

为了解决涉及到计数场景下的内存占用与元素个数呈线性关系的基数计数问题（cardinality counting），提出的一种基于统计的计数结构。

例如：统计一个页面在一段时间内不同IP数量，如果使用set，hashtable等类型，如果访问IP数量过多，会导致去重集合占用巨大的空间。
HyperLogLog是一种基于概率的近似算法，首先对计数元素进行hash，选取二进制首位1作为对应标志位置，判断是否重复（更深入理解见博客）

底层实现数据结构为raw即动态字符串，基本的操作包括:PFADD,PFCOUNT,PFMERGE

Geospatial

以经纬度方式存储和查询数据，类似于一个二维的sortedset，支持的结构包括

插入和查询：GEOADD,GEODIST,GEOPOS,GEOHASH
范围查询：GEOSEARCH,GEORADIUS

存储类型为ziplist,使用示例：

127.0.0.1:6379> geoadd henan:city 113.62 34.75 zhengzhou 114.78 34.55 kaifeng 112.47 34.15 luoyang 113.18 33.77 pingdingshan
(integer) 4
127.0.0.1:6379> object encoding henan:city
"ziplist"
127.0.0.1:6379> geopos henan:city zhengzhou
1) 1) "113.62000197172164917"
   2) "34.74999926510690784"
127.0.0.1:6379> georadius henan:city 113.62 34.75 100 km
1) "zhengzhou"
127.0.0.1:6379> georadius henan:city 113.62 34.75 1000 km
1) "pingdingshan"
2) "kaifeng"
3) "zhengzhou"