一、Redis协议
RESP(redis序列化协议)字符串协议
初衷：
1、实现简单
2、快速被计算机解析
3、简单的可以能被人工解析
Redis协议将传输的数据分为5种最小单元类型
1、单元结束时统一加上回车换行符 CRLF="\r\n"；
2、+ 单行字符串以‘+’开头；
3、$ 多行字符串以‘$’开头，后跟字符串长度；
4、: 整数值以‘:’开头，后跟整数的字符串形式；
5、- 错误消息以‘-’开头；
6、* 数组以‘*’开头，后跟数组长度；
Redis在TCP端口6379上监听到来的连接，客户端连接到来时，Redis服务器为此建一个TCP连接，在客户端与服务器端之间传输的每个Redis命令或者数据都以\r\n结尾。redis通信分为以下两种形式：
1：标准形式：
例：
使用RESP协议发送 set mykey myvalue
*3
$3
set
$5
mykey
$7
myvalue
2、内联命令：直接发命令
set mykey myvalue
redis常见的响应：
单行字符串响应：
ping
+PONG
错误响应：
wwwww
-ERR unknown command `wwwww`
整数响应
incr test
:1
多行字符串响应
get mykey
$5
mysql
get www
$-1
set qqqq ''
+OK
get qqqq
$0
"$0\r\n\r\n"
"$-1\r\n"
数组响应
lpush db redis mysql db2
:3
lrange db 0 -1
*3
$3
db2
$5
mysql
$5
redis
二、SDS(simple dynamic string)
Redis将SDS作为默认字符串表示。
结构：
struct sdshdr{
// 记录buf数组中已使用字节的数量
// 等于sds 所保存的字符串长度
int len;
// 记录buf数组中未使用字节的数量
int free;
// 字节数组，用于保存字符串
char buf[];
}
SDS与C字符串比较：
1、常数复杂度获取字符串长度
C字符串获取长度采用遍历，时间复杂度 O(N)，SDS获取字符串长度：O(1):直接返回：len；
2、杜绝缓冲区溢出
c字符串使用 strcat()进行拼接(可能会覆盖原有字符串)，sds首先检查free是否>=要拼接的字符串长度，若不够则扩容buf[]的长度；
3、sds减少字符串带来的内存重分配次数
空间预分配策略：
当free长度>需要拼接的长度，若拼接后的长度<1MB, 扩容为拼接字符串长度的二倍 free = len，若大小>= 1MB，分配1MB的未使用空间；
惰性空间释放策略：
当SDS缩短时，并不会立即回收内存，使用free属性将这些字节的数量记录起来，等待将来使用；
4、SDS是二进制安全的
c字符串：只能够保存文本数据，无法保存图片、音频、视频等二进制数据（程序读到’\0’会自动截断）。
sds: 由len属性决定是否结束，所以sds不仅能够保存文本数据，还能够保存二进制数据；另外，SDS同样遵循以’\0’结尾，这样可以兼容部分C字符串函数。
总结：
c字符串 sds
获取字符串长度复杂度为o(N)。 获取字符串长度复杂度为o(1)
API是不安全的，可能会造成缓冲区溢出。 API是安全的，不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配。 修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据。 可以保存文本或者二进制数据
可与使用所有的<string.h>库中的函数。 可以使用部分<string.h>库中的函数
三、Redis链表
结构如下：
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值(为一个指针，可指向任意类型的值)
void *value;
} listNode;
typedef struct list{
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 链表所包含的节点数量
unsighed long len;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
} list;
Redis链表特性：
1、双端：
链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1);
2、无环：
表头节点的prev指针和表尾节点的next指针都指向NULL, 对链表的访问以NULL为终点;
3、带表头指针和表尾指针
通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1);
4、带链表长度计数器：
程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表节点数量的复杂度为O(1);
5、多态：
链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值;
四、Redis字典的实现–hash
结构如下：
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsighed long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于size-1
unsighed long sizemask;
// 该哈希表已有节点的数量
unsighed long used;
} dictht;
// 哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：
typedef struct dictEntry{
// 键
void *key;
// 值
union{
void *val;
unit64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dicEntry *next;
} dictEntry;
typedef struct dict{
// 类型特定函数
dicType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引
// 当 rehash 不再进行时，值为-1
int rehashidex;
} dict;
hash算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
1、使用字典设置的哈希函数，计算键key的哈希值
hash = dict->type->hashFunction(key);
2、根据哈希表的sizemask属性和哈希值，计算出索引值
index = hash & dict->ht[x].sizemask（根据使用情况不同，ht[x]可以是ht[0]或者 ht[1]）;
解决键冲突
当有两个或者以上数量的键被分配到哈希表数组的同一个索引上面，使用链地址法解决(头插);
rehash
随着操作的不断执行，哈希表保存的键值对会逐渐的增多或或者减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展和收缩;
1、为ht[1]分配空间 扩展：ht[0].used*2(第一个大于等于2的n次方幂)，收缩：ht[0].used(第一个大于等于2的n次方幂)
2、把ht[0]上的所有键值对rehash到ht[1]上;
3、释放ht[0],将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备;
rehash时机选择
负载因子
#负载因子 = 哈希表已保存节点数量/哈希表大小
load_factor = ht[0].used/ht[0].size;
扩展：
未执行bgsave或者bgrewriteaof: 负载因子>1
执行bgsave或者bgrewriteaof：负载因子>5（原因：采用写时复制技术，避免不必要的内存写入操作，节约内存）
收缩：
负载因子<0.1；
渐进式hash
分多次、渐进式完成(rehashidx：记录rehash的位置)
rehash过程中搜索：先ht[0]中查找，再ht[1]中查找；
rehash过程中添加：直接添加进ht[1]；
五、Redis跳跃表
跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表支持平均O(log N)最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来的更为简单，所以有不少程序都使用跳跃表来代替平衡树。
结构如下：
typedef struct zskiplist{
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsighed long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
typedef struct zskiplistNode{
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel{
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsighed int span;
} level[];
} zskiplistNode;
zskiplistNode结构：用于表示跳跃表节点；
zskiplist结构：用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针；
zskiplist包含以下属性：
header: 指向跳跃表的表头节点；
tail：指向跳跃表的表尾节点；
level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）；
length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）；