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

}

 redis  底层

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就用跳表作为有序集合的底层实现

集群节点中也用到跳表

 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 记录了对象的类型,键总是字符串类型,值可以是五种类型之一:

 redis  底层

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

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

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

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

 redis  底层

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

 redis  底层

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

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

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

ptr 指向底层的数据结构

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

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

相关推荐