redis相关底层数据结构及原理
基础数据结构
简单动态字符串（simple dynamic string，SDS）：redis默认字符串表示，SDS定义:
struct sdshdr {
//记录buf中已使用数组的数量，即sds所保存的字符串的长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
}SDS实现了空间预分配和惰性空间释放两种优化策略。
（1）空间预分配：SDS字符串增长后长度<1M，则预分配和len属性同样大小的未使用空间，如果修改后SDS长度>=1M时，固定分片1M大小的未使用空间。
（2）惰性空间释放：SDS字符串缩短后，程序不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。
链表：提供高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过节点来灵活地调整链表的长度。定义如下：
//每个链表节点定义如下：
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;链表结构如下：
图一 链表
字典：又称为符号表、关联数组或映射，是一种用于保存键值对（key-value pair）的抽象数据结构。Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有很多哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
//哈希表
typedef struct dictht {
//哈希表数组
dicEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值，总数等于size-1
unsigned long sizemask;
//该哈希表已有节点数量
unsigned long used;
} dictht;
//哈希表节点
typedef struct dicEntry {
//键
void *key;
//值
union {
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下个哈希表节点，形成链表
struct dicEntry *next;
} dicEntry;
//字典
typedef struct dict {
//类型特定函数
dicType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
//rehash索引，当rehash不在进行时，值为-1
int rehashidx;
}dict;字典结构如下：
图二 普通状态下的字典
跳跃表skiplist：是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素比较多，或有序集合中元素成员（member）是比较长的字符串时，Redis就会使用跳跃表作为有序集合键的底层实现。
跳跃表的结构定义如下：
//跳跃表节点
typedef struct zskiplistNode {
//层
struct zskiplistLevel {
//前进指针
struct zskiplistNode *forword;
//跨度
unsigned int span;
}level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
}zskiplistNode;
//跳跃表
typedef struct zskiplist{
//表头节点和表尾节点
struct zskiplistNode *header,*tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}zskiplist;图三 带有skiplist结构的跳跃表
每个跳跃表节点的层高都是1~32之间的随机数，同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
整数集合intset：是集合键的底层实现之一，当一个集合只包含整数元素，且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
集合键的结构定义：
typedef struct intset{
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
}intset;整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加的元素的类型，改变这个数据的类型。升级操作为整数集合带来了操作上的灵活性，并且尽可能的节约了内存。整数集合只支持升级操作（如int8_t->int16_t->int32_t->int64_t），不支持降价操作。
压缩列表ziplist：是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做列表键的底层实现。压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。
持久化
复制
同步操作用于将slave服务器的数据库状态更新至master当前所处的数据库状态。
命令传播操作则用于在master的数据库状态被修改，导致master与slave数据库状态不一致时，让master与slave数据库重新回到一致状态。
同步状态分为完整重同步和部分重同步：
完整重同步：用于处理初次复制和状态未持久化场景，通过让主服务器创建并发送RDB文件，以及向从服务器发送保存在缓存区里面的写命令进行同步。
部分重同步：当从服务器在断线后重新连接主服务器时，如果条件允许，主服务器可以将主从服务器连接断开期间执行的命令发送给从服务器，从服务器只要接收并执行这些命令，就可以将数据库更新至主服务器当前所处的状态。
Sentinel
图四 服务器与Sentinel系统
在已下线的主服务器属下的所有从服务器里面，挑选出一个从服务器，并将其转换为主服务器（发送slaveof no one命令，并1s发送一次info检查角色是否变为master）。
让已下线的主服务器属下所有从服务器改为复制新的主服务器（发送slaveof newIP newPort命令）。
将已下线的主服务器设置为新的主服务器的从服务器，当这个旧的主服务器重新上线时，它就会成为新的主服务器的从服务器（发送slaveof newIP newPort命令）。
事件与ServerCron函数
lua脚本、发布与订阅
图五 Lua脚本执行Redis命令时的通信步骤
过期字典删除
E N D