首页  思维导图  详情

Redis

2020-07-21 10:12:58   0  举报





AI智能生成

Redis设计与实现

Redis

作者其他创作

大纲/内容

SDS(简单动态字符串)

定义

len

记录buf数组中已使用字节的数量

free

记录buf数组中未使用字节的数量

buf[]

字节数组，用于保存字符串

SDS字符串和C语言字符串区别

获取字符串长度

C语言字符串o(n)

SDS字符串o(1)

SDS杜绝缓冲区溢出

在对SDS进行修改时，API会检测SDS的空间是否满足修改所需的要求

如果SDS空间不足，API会自动将SDS的空间扩展至执行修改所需要的大小

减少修改字符串时带来的内存重分配次数

C语言字符串扩大或缩小的缺点

扩大时可能出现缓冲区溢出

缩小时可能出现内存泄漏

SDS采用两种优化策略

空间预分配

惰性空间释放

二进制安全

SDS的buf时字节数组

数据在写入时是什么样的，它被读取时也是什么样的

Redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据

C语言字符串以'\0'结尾，所以中间不能存储'\0'，而SDS是通过len属性的值来判断字符串的结尾，因此SDS可以存储'\0'

SDS可以保存任意格式的二进制数据

兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但他们一样遵循C字符串以空字符结尾的惯例，这是为了保存文本数据的SDS可以重用一部分string.h库定义的函数

SDS API

sdsnew

创建一个包含给定C字符串的SDS

sdsempty

创建一个不包含任何内容的空SDS

sdsfree

释放给定的SDS

sdslen

返回SDS的已使用的空间字节数

sdsvail

返回SDS的未使用空间字节数

sdsclear

返回SDS的未使用空间字节数

sdsdup

创建一个给定SDS的副本

sdscat

将C字符串拼接到SDS字符串的末尾

sdscatsds

将给定的SDS字符串拼接到另一个SDS字符串的末尾

sdscpy

将给定的SDS字符串复制到SDS里面，覆盖SDS原有的字符串

sdsgrowzero

用空字符将SDS扩展至给定长度

sdsrange

保留SDS给定区间内的数据，不在区间内的数据会被覆盖或清除

sdstrim

接受一个SDS和一个C字符串作为参数，从SDS左右两端分别移除所有在C字符串中出现的字符

sdscmp

对比两个SDS字符串是否相同

链表

因为Redis的实现采用C语言，而C语言没有链表，所以Redis构建了自己的链表实现

应用场景

链表键

发布与订阅、慢查询、监视器等

Redis服务器本身使用链表来保存多个客户端的状态信息

使用链表来构建客户端输出输出缓冲区

链表和链表结点的实现

每个链接节点使用一个listNode结构体

struct listNode * prev;

前置节点

struct listNode * next;

后置节点

void * value;

节点值

使用list来持有链表，操作起来更方便

listNode * head;

表头节点

listNode * tail;

表尾节点

unsigned long len;

链表节点数量

void *(*dup) (void * ptr)

节点复制函数

void (*free)(* void ptr)

节点释放函数

int (*match)(void *ptr, void * key);

节点值对比函数

多态

链表节点使用void *指针来保存节点的值，并且可以通过list结构的dup\free\match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值

链表和链表节点的API

listSetDupMethod

将给定的函数设置为链表节点复制函数

listGetDupMethod

返回链表当前正在使用的节点复制函数

free和match同上

listLength

返回链表的长度

listFirst

返回链表的表头节点

listLast

返回链表的表尾节点

listPrevNode

返回给定节点的前置节点

listNextNode

返回给定节点的后置节点

lsitNodeValue

返回给定节点目前正在保存的值

listCreate

创建一个不包含任何节点的新链表

listAddNodeHead

将一个包含给定值的新节点添加到给定链表的表头

listAddNodeTail

将一个包含给定值的新节点添加到给定链表的表尾

listInsertNode

将一个包含给定值的新节点添加到给定节点的之前或之后

listSearchKey

查找并返回链表中包含给定值的节点

listIndex

返回链表在给定索引上的结点

listDelNode

从链表中删除给定节点

listDelRotate

将链表的表尾节点弹出，然后将被弹出的新疆棉插入到链表的表头，成为新的表头节点

listDup

复制一个给定链表的副本

listRelease

释放给定链表，以及链表中的所有节点

字典(符号表、关联数组或者映射(map))

C语言并没有内置字典所以Redis构建了自己的字典实现

Redis的数据库就是使用字典作为底层实现的，对数据上的增、删、改、查操作也是构建在字典的操作之上的

字典也是哈希键的底层实现之一：当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时

哈希算法

将一个新的键值对添加到字典里面时，程序需要先根据键值对计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈表结点放到哈希表数组的指定索引上面

计算方法：

# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。MurmurHash算法的优点在于：即使输入的键是有规律的，算法仍然能给出一个很好的随机分布性，并且算法的计算速度也非常快

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表结点，而每个哈希表结点就保存了字典里的一个键值对

哈希表

dict.h/dictht定义了字典所使用的哈希表

typedef struct dictht {
// 哈希表数组
dictEntry **table;

// 哈希表大小
unsigned long size;

// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;

// 该哈希表已有节点的数量
unsigned long used;

} dictht;

table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个车键值对

sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键值对应该被放到table数组的哪个索引上面

大小为4的空哈希表

哈希节点

哈希节点使用dictEntry结构表示，每个dictEntry结构保存着一个键值对

typedef struct dictEntry {
// 键
void *key;

// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;

// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;

next属性是指向另一个哈希表节点，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突的问题

通过next指针将索引值相同的键k1和k0连接在一起

字典

字典有dict.h/dict结构表示

typedef struct dict {
// 类型特定函数
dictType *type;

// 私有数据
void *privdata;

// 哈希表
dictht ht[2];

// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定的函数

privdata属性则保存了需要传给那些类型特定函数的可选参数

dictType结构

typedef struct dictType {
// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);

// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);

// 复制值的函数
void *(*valDup)(void *privdata, const void *obj);

// 对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);

// 销毁键的函数
void (*keyDestructor)(void *privdata, void *key);

// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只是使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用

rehashidx记录了了rehash目前的进度，如果目前没变在进行rehash，那么它的值为-1

普通状态下(没有进行rehash)的字典

解决键冲突

使用链地址法来解决键冲突：每个哈希表节点都有一个next指针，多个哈希表节点可以用net指针构成一个单向链表

rehash

背景：

随着操作不断执行，哈希表保存的键值对会逐渐增多或减少，为了让哈希表的负载因子维持在一个合理的范围内，程序需要对哈希表的大小进行相应的扩展或收缩

rehash(重新散列)

为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量

如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used * 2的2^n

如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n

将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上

当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表)，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空白哈希表，为下一次rehash做准备

哈希表的扩展和收缩

扩展时机

服务器目前没有执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1

服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5

收缩时机

当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作

负载因子 = 哈希表已保存节点数量 / 哈希表大小

根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行，服务器执行扩展操作所需的负载因子并不相同，这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中， Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。

渐进式rehash

扩展或收缩哈希表需要将ht[0]里面的所有键值对rehash到ht[1]里面，但是这个rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的

背景：如果ht[0]中的见键值对数量庞大，一次性将这些键值对全部rehash到ht[1]，庞大的计算两可能导致服务器在一段时间内停止服务。为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面exe键值对全部rehash到ht[1]中，而是分多次，渐进式地进行rehash

步骤：

为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表

为字典维持一个索引计数气遍历rehashidx，并将它的值设置为0，表示rehash工作正式开始

在rehash进行期间，每次对自检执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一

随着字典操作的不断进行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]，这时程序将rehashidx设置为-1，表示rehash操作已完成

渐进式rehash执行期间的哈希表操作

在渐进式rehash期间，字典的删除、查找、更新等操作都是在两张表上进行的

要在字典里面查找一个键，程序首先在ht[0]里面进行查找，如果没有找到，就会继续到ht[1]里面查找

新添加一个键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作