redis 底层

简单动态字符串 ( simple dynamic string，SDS)

SDS的应用

在redis里，c字符串只会用作字面量，用在不会更改的地方，例如打印日志。

需要修改的字符串，用SDS表示

set msg "hello world"

redis将创建一个键值对，键是一个字符串对象，对象的底层实现是保存着字符串"msg"的SDS

值也是字符串对象，对象的底层实现是保存着字符串"hello world"的SDS

rpush fruits "apple" "banana" "cherry"

键是一个字符串对象，对象的底层实现是保存着字符串"fruits"的SDS

值是一个列表对象，列表对象包含三个字符串对象，字符串对象的底层是三个SDS

AOF缓冲区和客户端的输入缓冲区，也是由SDS实现的

SDS的实现与优点

struct sdshdr{

int len; //buf数组中已使用字节的数量，即字符串长度，不包括 ‘\0‘

int free; //buf数组中未使用字节的数量，也不考虑 ‘\0‘，len=free=5，buf实际长度为11

char buf[]; //字节数组，c风格字符串，末尾是‘\0‘，好处是复用c的字符串函数

};

获取字符串长度O(1)

不会发生缓冲区溢出，例如拼接字符串的时候

二进制安全

可复用部分C字符串函数

减少内存重分配的次数，c字符串的长度增加或减少时都要对内存进行重分配

SDS空间预分配：长度增加时，如果len<1MB，则free=len；如果len>=1MB，则free=1MB。

这样可以减少连续执行字符串长度增加操作所需的内存重分配次数

SDS惰性空间释放：长度减少时，不进行内存重分配，而是记录到free里，

同时也提供了API来真正释放内存，不必担心内存浪费

链表

list元素较多时，或者list元素都是长字符串时，redis就用链表作为list的底层实现，

发布与订阅、慢查询、监视器、保存客户端状态信息、客户端输出缓冲区等都用到了链表

typedef struct listNode{ //双向无环链表节点

struct listNode *prev; //第一个节点的 prev==null

struct listNode *next; //最后一个节点的 next==null

void *value; //void* 可保存各种类型的值

}listNode;

typedef struct list{

listNode *head; //表头

listNode *tail; //表尾

unsigned long len; //节点数量

void *(*dup)(void *ptr); //节点值复制函数

void (*free)(void *ptr); //节点值释放函数

int (*match)(void *ptr, void *key); //节点值对比函数

}list;

字典 (又称 符号表symbol table、关联数组associative array、映射map)

redis数据库的底层实现就是字典，

当Hash的元素较多时，或者键或值是长字符串时，redis就用字典作为hash的底层实现

实现：

typedef struct dictht{

dictEntry **table; //哈希表数组

unsigned long size; //哈希表大小

unsigned long sizemask; //掩码，sizemask=size-1

unsigned long used; //已有节点数量

} dictht;

typedef struct dictEntry{

void *key; //键

union{

void *val;

uint64_tu64;

int64_ts64;

} v; //值

struct dictEntry *next; //下个哈希表节点

}

typedef struct dict{

dictType *type; //类型特定函数

void *privdata; //私有数据

dictht ht[2]; //哈希表 平时使用ht[0] rehash时使用ht[1]

in trehashidx; //rehash的进度 不在rehash时值为-1

}

hash算法

当字典用作redis数据库的底层实现，或者Hash键的底层实现时，redis使用MurmurHash2来计算哈希值，这种算法的优点在于即使输入的键是有规律的，算法仍能给出一个很好的随机性，且速度很快。

解决冲突

解决哈希冲突的两种方法：开散列法(又称拉链法，链地址法) 和 闭散列法(开地址法)，redis里用的是开散列法。新节点总是添加到链表的表头位置O(1)。

rehash

为ht[1]分配空间，将ht[0]的所有键值对rehash到ht[1]上，然后销毁ht[0]，将ht[1]作为新的ht[0]，并创建一个新的空白ht[1]

哈希因子 = used / size

当不在执行bgSave或bgRewriteAof命令且哈希因子>=1，或者正在执行bgSave或bgRewriteAof命令且哈希因子>=5时，执行扩展操作

当哈希因子<=0.1时，执行收缩操作

执行bgSave或bgRewriteAof命令时，会创建子进程，操作系统采用写时复制技术，所以此时尽量不要rehash

渐进式rehash

rehash不是一次性集中完成的，rehashidx指向ht[0]已完成rehash的位置，查找时先查ht[0]再查ht[1]，添加时只往ht[1]里添加

跳表

平均O(lgn)，最坏O(n)，

当有序集合的元素数量较多时，或者元素都是长字符串时，redis就用跳表作为有序集合的底层实现

集群节点中也用到跳表

左侧zskiplist结构，包含以下属性：

header指向表头节点

tail指向表尾节点，程序定位表头和表尾的复杂度为O(1)

level记录目前跳表内，层数最大的节点的层数(不包括表头节点)

length记录跳表长度(不包括表头节点)，计算跳表长度的复杂度为O(1)

右侧zskiplistNode节点，包含以下属性：

层：L1表示第一层，L2表示第二层...每个层包含前进指针和跨度，图中的数字即为跨度，

跨度记录了前进指针指向的节点和当前节点的距离

每次创建一个新节点时，会根据幂次定律(越大的数出现的概率越小)，

随机生成一个介于1到32之间的值作为level数组的大小，即层高。

跨度的作用是计算节点的排位

后退指针：BW表示后退指针，指向相邻的前一个节点，用于从后向前遍历

分值(double型)：1.0 2.0 3.0表示分值，从小到大排列

成员对象：o1 o2 o3表示节点保存的成员对象。成员对象是一个指针，指向一个字符串对象，

字符串对象保存一个SDS值。成员对象必须是唯一的，

分值可以相同，相同分值的节点按成员对象的字典序排列

表头节点也有后退指针、分值、成员对象，但不会被用到，所以图中未画出。

整数集合

当集合只包含整数，且元素数量不多时，redis就用整数集合作为集合键的底层实现。

typedef struct intset{

uint32_t encoding; //编码方式

uint32_t length; //元素数量

int8_t contents[]; //保存元素的数组，从小到大排列，不会重复

} intset;

压缩列表

当list或hash的元素数量较少，且每个list项或者每个hash的键和值都是小整数值或者短字符串，redis就用压缩列表作为list或hash的底层实现

对象

typedef struct redisObject {

unsigned type:4; //类型

unsigned encoding:4; //编码

void *ptr; //指向底层实现数据结构的指针

int refcount; //引用计数

unsigned lru:22; //最后被访问的时间

} robj;

type 记录了对象的类型，键总是字符串类型，值可以是五种类型之一：

当称呼一个数据库键为“列表键”时，指的是这个键对应的值为列表对象

对键执行TYPE命令，返回的是对应的值对象的类型

特定类型的命令在执行前会检查值对象的type属性，如果不匹配就拒绝执行并返回错误

encoding 记录了对象所使用的底层数据结构：

每种类型的对象都至少有两种编码：

使用object encoding命令，可以查看键对应的值对象的编码

redis可以根据不同情况，使用不同的底层对象，极大提高了灵活性

多态命令：redis根据encoding，选择命令的正确实现代码

ptr 指向底层的数据结构

refcount 引用计数，可以用于内存回收和对象共享，例如redis会在启动时，创建一万个字符串对象，包含了0~9999的整数值，当要用到值为0~9999的字符串时，就可以使用这些共享对象

lru 用于统计键的空转时长，object idletime命令可打印lru，且该命令不会刷新lru的值