Redis设计与实现
⽂章⽬录
第⼀部分：内部数据结构
简单动态字符串(simple dynamic string)
在 Redis 中，⼀个字符串对象除了可以保存字符串值之外，还可以保存long类型的值
Sds 在 Redis 中的主要作⽤有以下两个：
实现字符串对象（StringObject）；
在 Redis 程序内部⽤作 char* 类型的替代品；
在 C 语⾔中，字符串可以⽤⼀个 \0 结尾的 char 数组来表⽰。它并不能⾼效地⽀持长度计算和追加（append）这两种操作：每次计算字符串长度（strlen(s)）的复杂度为 θ(N) 。
对字符串进⾏ N 次追加，必定需要对字符串进⾏ N 次内存重分配（realloc）。
考虑到这两个原因， Redis 使⽤ sds 类型替换了 C 语⾔的默认字符串表⽰
在前⾯的内容中， 我们⼀直将 sds 作为⼀种抽象数据结构来说明， 实际上， 它的实现由以下两部分组成：
其中，类型 sds 是 char * 的别名（alias），⽽结构 sdshdr 则保存了 len 、 free 和 buf 三个属性。
typedef char*sds;
struct sdshdr {
// buf 已占⽤长度
int len;
// buf 剩余可⽤长度
int free;
// 实际保存字符串数据的地⽅
char buf[];
};
sds.c/sdsMakeRoomFor 函数描述了 sdshdr 的这种内存预分配优化策略， 以下是这个函数的伪代码版本：
def sdsMakeRoomFor(sdshdr,required_len):
# 预分配空间⾜够，⽆须再进⾏空间分配
if (sdshdr.free >= required_len):
return sdshdr
# 计算新字符串的总长度
newlen = sdshdr.len + required_len
# 如果新字符串的总长度⼩于 SDS_MAX_PREALLOC
# 那么为字符串分配 2 倍于所需长度的空间
# 否则就分配所需长度加上 SDS_MAX_PREALLOC 数量的空间
if newlen < SDS_MAX_PREALLOC:
newlen *= 2
else:
newlen += SDS_MAX_PREALLOC
# 分配内存
newsh = zrelloc(sdshdr, sizeof(struct sdshdr)+newlen+1)
# 更新 free 属性
newsh.free = newlen - sdshdr.len
# 返回
return newsh
伪代码解释：如果剩余空间⾜够，则不进⾏内存重新分配。如果不够则会计算当前字符串的长度=原字符串长度+新增的字符串长度。
如果计算的当前字符串的长度没有超过⼀个固定值SDS_MAX_PREALLOC，就分配给他两倍⾃⾝长度的空间，如果超过了就分配⼀个固定值长度的空间。
这个固定值SDS_MAX_PREALLOC⼤⼩为1MB，是能够分配空间的最⼤值。
应⽤举例：
redis> SET msg "hello world"
OK
redis> APPEND msg " again"
(integer)17
redis> GET msg
"hello world again"
当SET这个msg时，会保存到⼀个sdshdr中，记录长度、剩余空间、数据，值得注意的是，SET命令不会分配剩余空间，只有对字符串进⾏追加才时才会分配剩余空间。
struct sdshdr {
len =11;
free =0;
buf ="hello world\0";
}
当执⾏ APPEND 命令时，相应的 sdshdr 被更新，字符串 " again" 会被追加到原来的 “hello world” 之后：它将原本长度为11的字符串加上更新的字符串长度作为新字符串的长度，并且赋给此长度的剩余空间。如果再次执⾏APPEND，添加的字符串长度⼩于剩余空间时，不会再进⾏内存的分配。
struct sdshdr {
len =17;
free =17;
buf ="hello world again\0";// 空⽩的地⽅为预分配空间，共 17 + 17 + 1 个字节
}
这种分配策略会浪费内存吗？
执⾏过 APPEND 命令的字符串会带有额外的预分配空间，这些预分配空间不会被释放，除⾮该字符串所对应的键被删除，或者等到关闭 Redis 之后，再次启动时重新载⼊的字符串对象将不会有预分配空间。
因为执⾏ APPEND 命令的字符串键数量通常并不多，占⽤内存的体积通常也不⼤，所以这⼀般并不算什么问题。
另⼀⽅⾯，如果执⾏ APPEND 操作的键很多，⽽字符串的体积⼜很⼤的话，那可能就需要修改 Redis 服务器，让它定时释放⼀些字符串键的预分配空间，从⽽更有效地使⽤内存。
双端链表
Redis 列表使⽤两种数据结构作为底层实现：
双端链表
压缩列表
因为双端链表占⽤的内存⽐压缩列表要多， 所以当创建新的列表键时， 列表会优先考虑使⽤压缩列表作为底层实现， 并且在有需要的时候， 才从压缩列表实现转换到双端链表实现。
双端链表的实现由 listNode 和 list 两个数据结构构成.
typedef struct listNode {
// 前驱节点
struct listNode *prev;
// 后继节点
struct listNode *next;
// 值
void*value;
} 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;
从这两个数据结构的定义上，也可以了解到⼀些⾏为和性能特征：
listNode 带有 prev 和 next 两个指针，因此，遍历可以双向进⾏：从表头到表尾，表尾到表头。
list 保存了 head 和 tail 两个指针，因此，对链表的表头和表尾进⾏插⼊的复杂度都为 θ(1) —— 这是⾼效实现 LPUSH 、 RPOP 、RPOPLPUSH 等命令的关键。
list 带有保存节点数量的 len 属性，所以计算链表长度的复杂度仅为 θ(1) ，这也保证了 LLEN 命令不会成为性能瓶颈。
字典
Redis 选择了⾼效、实现简单的哈希表，作为字典的底层实现。
字典的主要⽤途有以下两个：
实现数据库键空间（key space）；
⽤作 Hash 类型键的底层实现之⼀；
Redis ⽬前使⽤两种不同的哈希算法：
MurmurHash2 32 bit 算法：这种算法的分布率和速度都⾮常好。
基于 djb 算法实现的⼀个⼤⼩写⽆关散列算法。
命令表以及 Lua 脚本缓存都⽤到了算法 2 。
算法 1 的应⽤则更加⼴泛：数据库、集、哈希键、阻塞操作等功能都⽤到了这个算法。
字典是由键值对构成的抽象数据结构。
Redis 中的数据库和哈希键都基于字典来实现。
redis支持的数据结构Redis 字典的底层实现为哈希表，每个字典使⽤两个哈希表，⼀般情况下只使⽤0号哈希表，只有在 rehash 进⾏时，才会同时使⽤0号和1号哈希表。
哈希表使⽤链地址法来解决键冲突的问题。
Rehash 可以⽤于扩展或收缩哈希表。
对哈希表的 rehash 是分多次、渐进式地进⾏的。
跳跃表
跳跃表是⼀种随机化数据结构，查、添加、删除操作都可以在对数期望时间下完成。
跳跃表⽬前在 Redis 的唯⼀作⽤，就是作为有序集类型的底层数据结构（之⼀，另⼀个构成有序集的结构是字典）。
为了满⾜⾃⾝的需求，Redis 基于 William Pugh 论⽂中描述的跳跃表进⾏了修改，包括：
1. score 值可重复。
2. 对⽐⼀个元素需要同时检查它的 score 和 memeber 。
3. 每个节点带有⾼度为 1 层的后退指针，⽤于从表尾⽅向向表头⽅向迭代。
第⼆部分：内存映射数据结构
整数集合intset
Intset ⽤于有序、⽆重复地保存多个整数值，会根据元素的值，⾃动选择该⽤什么长度的整数类型来保存元素。
当⼀个位长度更长的整数值添加到 intset 时，需要对 intset 进⾏升级，新 intset 中每个元素的位长度，会等于新添加值的位长度，但原有元素的值不变。
升级会引起整个 intset 进⾏内存重分配，并移动集合中的所有元素，这个操作的复杂度为 O(N) 。
Intset 只⽀持升级，不⽀持降级。
Intset 是有序的，程序使⽤⼆分查算法来实现查操作，复杂度为 O(lgN) 。
压缩列表
因为 ziplist 节约内存的性质， 哈希键、列表键和有序集合键初始化的底层实现皆采⽤ ziplist
redis数据类型
对象处理机制(redisObject)
Redis 的每⼀种数据类型，⽐如字符串、列表、有序集， 它们都拥有不只⼀种底层实现（Redis 内部
称之为编码，encoding）， 这说明，每当对某种数据类型的键进⾏操作时， 程序都必须根据键所采取的编码， 进⾏不同的操作。操作数据类型的命令除了要对键的类型进⾏检查之外， 还需要根据数据类型的不同编码进⾏多态处理。
为了解决以上问题， Redis 构建了⾃⼰的类型系统， 这个系统的主要功能包括：
redisObject 对象。
基于 redisObject 对象的类型检查。
基于 redisObject 对象的显式多态函数。
对 redisObject 进⾏分配、共享和销毁的机制。
/*
* Redis 对象
*/
typedef struct redisObject {
// 类型
unsigned type:4;
// 对齐位
unsigned notused:2;
// 编码⽅式
unsigned encoding:4;
// LRU 时间（相对于 server.lruclock）
unsigned lru:22;
// 引⽤计数
int refcount;
// 指向对象的值
void*ptr;
} robj;
这⾥最重要的三个属性是 type、encoding、ptr，type是指五种类型（string,list,hash,set,zset）的⼀种，encoding是对象所保存的值的编码,ptr是⼀个指针，指向实际保存值的数据结构，这个数据结构由 type 属性和 encoding 属性决定。
//encoding存储的编码
#define REDIS_ENCODING_RAW 0            // 编码为字符串
#define REDIS_ENCODING_INT 1            // 编码为整数
#define REDIS_ENCODING_HT 2            // 编码为哈希表
#define REDIS_ENCODING_LINKEDLIST 4    // 编码为双端链表
#define REDIS_ENCODING_ZIPLIST 5        // 编码为压缩列表
#define REDIS_ENCODING_INTSET 6        // 编码为整数集合
#define REDIS_ENCODING_SKIPLIST 7      // 编码为跳跃表
举个例⼦，如果⼀个 redisObject 的 type 属性为 REDIS_LIST ， encoding 属性为 REDIS_ENCODING_LINKEDLIST ，那么这个对象就是⼀个 Redis 列表，它的值保存在⼀个双端链表内，⽽ ptr 指针就指向这个双端链表；
有了 redisObject 结构的存在， 在执⾏处理数据类型的命令时， 进⾏类型检查和对编码进⾏多态操作就简单得多了。
当执⾏⼀个处理数据类型的命令时， Redis 执⾏以下步骤：
根据给定 key ，在数据库字典中查和它相对应的 redisObject ，如果没到，就返回 NULL 。
检查 redisObject 的 type 属性和执⾏命令所需的类型是否相符，如果不相符，返回类型错误。
根据 redisObject 的 encoding 属性所指定的编码，选择合适的操作函数来处理底层的数据结构。
返回数据结构的操作结果作为命令的返回值。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。