1. SDS:简单动态字符串（simple dynamic string)
Redis没有直接使用C语言的字符串，而是自己构建了一种名为简单动态字符串类型，并将SDS用作Redis的默认字符串。
SDS的定义
struct sdshdr { // buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 字节数组 char buf[];};
SDS与C字符串的区别
- SDS获取字符串长度复杂度为O(1), C字符串获取字符串长度复杂度为O(N)；
因为C字符串获取字符串并不记录自身长度，程序必须遍历整个字符串对每个字符串计数。这个操作的复杂度为O(N)
SDS在len属性中记录了SDS本身长度，所以获取字符串长度复杂度为O(1)
- API是安全的，不会造成缓冲区溢出；
C字符串不记录自身长度，如果忘了给字符串扩容执行字符串拼接就会造成溢出
SDS拼接字符串之前会先通过free字段检测剩余空间能否满足需求，不能满足需求的就会扩容。
- 减少修改字符串带来的内存重分配次数；
C字符串底层总是一个N+1个字符数组，所以每次增长或缩短一个字符串，程序总要对这个C字符串进行一次内存重分配。
SDS实现空间预分配和惰性空间释放两种优化策略.
- 二进制安全
C字符串只能保存文本数据
SDS可以保存文本或者二进制数据
** 2. 链表 **
Redis的List（列表）和发布订阅，慢查询，监视器等功能都用到了链表
链表节点实现 adlist.h/listNode结构表示
// listNode 双端链表节点 typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value; } listNode;
该链表为双向链表，由多个listNode结点组成的链表结构图如下：
链表实现 adlist.h/list结构表示
// list 双端链表 typedef struct list { // 在c语言中,用结构体的方式来模拟对象是一种常见的手法 // 表头节点 listNode *head; // 表尾节点 listNode *tail; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值释放函数 void(*free)(void *ptr); // 节点值对比函数 int(*match)(void *ptr, void *key); // 链表所包含的节点数量 unsigned long len; } list;
例：由一个list结构和三个listNode结构组成的链表链表提供表头指针head，表尾指针tail，以及链表长度计数器len，和封装了3个内置函数1.dup函数：复制链表结点所保存的值2.free函数：释放链表结点所保存的值3.match函数：对比链表结点所保存的值和另一个输入值是否相等这三个函数是用于实现多态链表所需的类型特定函数。
Redis链表实现特征总结
1.双端：获取某个结点的前驱和后继结点都是O(1)
2.无环：表头的prev指针和表尾的next指针都指向NULL，对链表的访问都是以NULL为终点
3.带表头指针和表尾指针：获取表头和表尾的复杂度都是O(1)
4.带链表长度计数器：len属性记录，获取链表长度O(1)
5.多态：链表结点使用void*指针来保存结点的值，并且可以通过链表结构的三个函数为结点值设置类型特定函数，所以链表可以保存各种不同类型的值
-
字典
- 字典的实现
哈希节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对。
// dictEntry 哈希表节点 typedef struct dictEntry { // 键 void *key; // 值 union {//值v的类型可以是以下三种类型 void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;
Redis字典使用哈希表有dictht.h/dictht结构定义
typedef struct dictht { // 哈希表数组, 每个元素都是一条链表 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht;
// dict 字典 typedef struct dict { // 类型特定函数 dictType *type; // type里面主要记录了一系列的函数,可以说是规定了一系列的接口 // 私有数据 void *privdata; // privdata保存了需要传递给那些类型特定函数的可选参数 //两张哈希表 dictht ht[2];//便于渐进式rehash //rehash 索引，并没有rehash时，值为 -1 int rehashidx; //目前正在运行的安全迭代器的数量 int iterators; } dict;
* type 属性是一个指向dictType结构的指针，每个dictType结构保存了一族用于操作特定类型键值对的函数，Redis为用途不同的字典设置不同的类型特定函数。* privdata 属性则保存了需要传递给那些类型特定函数的可选参数。* ht是一个包含两个项的数组，数组每个项都是一个dictht哈希表，一般情况下只使用ht[0]哈希表，ht[1]只会对ht[0]哈希表进行rehash时使用。* rehashidx它记录了rehash目前的进度，如果目前没有进行rehash，那么他的值为-1.
// 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;
-
哈希算法
使用字典类型设置的哈希函数击视键key的哈希值
int hash = dict->type->hashFunction(key)
使用哈希表的sizemask的属性和哈希值计算出索引值
index = hash & dict->ht[0].sizemask;
使用哈希表节点next指针构成单向链表解决哈希冲突。
-
扩展和收缩哈希表的恭祝通过执行rehash操作来完成步骤如下
如果执行的是扩展操作，那么扩展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[1]设置为ht[0]，并在ht[1]重新创建一个空哈希表，为下一次rehash做准备。
当以下条件中的任意一个被满足时，程序会自动开始对哈希表进行扩展操作
1）服务器目前没有执行BGSAVE命令或者BGREWRITEOF命令，并且哈希表的负载因子大于等于1.
2）服务器目前正在执行BGSAVE命令或者BGREWRITEOF命令，并且哈希表的负载因子大于等于5.
3) 哈希表的负载因子可以通过公式：load_factor = ht[0].used / ht[0].size;
4) 哈希表的负载因子小于0.1时，自动执行哈希表收缩操作；
-
如果哈希表中有成千上万个键值对，那么要一次性rehash到ht[1]的话，可能会导致服务器一段时间内停止服务。为了避免rehash对服务器性能影响，服务器二十分多次，渐进性的将ht[0]里面的键值对渐进性的rehash。详细步骤：
1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
3) 在rehash进行期间，每次对字典执行添加，删除，查找或者更新操作时，程序除了执行指定的操作外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],完成顺带操作后，程序将rehashidx属性的值加一.
4) 随着字典操作的不断执行，最终在某个时间点，ht[0]的所有键值对会被rehash至ht[1]。这是将rehashidx设置为-1.表示rehash操作已执行完。
经验首页