简单动态字符串(SDS)

适用场景

1. 包含字符串的底层实现
2. 用作缓存区
   • AOF模块中的AOF缓存区
   • 客户端状态中的输入缓存区

SDS的定义

struct sdshdr {
    // 记录buf数组中已使用字节的数量,等于SDS所保存字符串的长度 
    int len; 
    // 记录buf数组中未使用字节的数量
    int free; 
    // 字节数组,用于保存字符串 
    char buf[];
};

SDS 与 C字符串的区别

1. 常数复杂度获取字符串的长度

   len 属性记录了SDS本身的长度，设置和更新SDS长度的工作有SDS的API执行时自动完成

2. 杜绝缓存区溢出

   SDS空间分配策略杜绝了发生缓存区溢出的可能性，先申请空间然后执行实际的操作

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

   • 空间预分配

     当SDS的API对一个SDS进性修改时，并且需要进行空间扩展时，不仅分配SDS所必须要的空间，还会分配额外的未使用空间

   • 惰性空间释放

     当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节, 而是使用free属性将这些字节的数量记录起来,并等待将来使用。

4. 二进制安全

   C字符串中的字符必须符合某种编码，且不能包含空字符串，而SDS确保写入的和读取的一样

链表

适用场景

1. 列表键
2. 发布与订阅
3. 慢查询
4. 监视器

列表定义

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;

// 双端队列 无环  带有头指针和尾指针  带表长计数器

字典

适用场景

1. 数据库
2. 哈希键

哈希表的定义

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    // 当 rehashidx == -1 时不进行rehash
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictht { 
    // 哈希表数组 
    dictEntry ** table; 
    // 哈希表大小 
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值总是等于size-1 
    unsigned long sizemask; 
    // 该哈希表已有节点的数量
    unsigned long used; 
} dictht;

typedef struct dictEntry { 
    // 键 
    void *key;
    // 值 可以是一个指针 或者是uint64_t 或者是 int64_t
    union{ 
        void *val;
        uint64_t u64; 
        int64_t s64; 
    } v; 
    // 指向下个哈希表节点，形成链表解决键冲突
    struct dictEntry *next; 
} dictEntry;

typedef struct dictType {
    // 计算hash的函数
    uint64_t (*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;

渐进式rehash

rehash动作并不是一次性、集中式地完成，而是分多次、渐进式地完成的

rehash 步骤

1. 为新的ht 分配空间，让字典同时持有新旧ht 两个hash表
2. 在字典中维持一个索引计数器变量rehashindex将值置为0，表示rehash 工作开始
3. 在rehash进行期间，每次对字典执行添加 、删除、查找或者更新操作时，程序除了执行指定的操作以外，同时将旧的ht在rehashidx索引上的所有键值对rehash到新的ht中， 当rehash工作完成之后程序将rehashidx属性的值增一。
4. 随着字典操作的不断执行，最终在某个时间点上，旧的ht的所有键值对都会被rehash至新的ht，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。
5. 在rehash过程中，查找会在两个ht中进行，新添加的数据被添加到新的ht中，旧ht不执行任何的增加操作

跳跃表

适用场景

1. 有序集合键的底层实现之一

跳跃表定义

// 跳跃表节点
typedef struct zskiplistNode {
    // 保存一个SDS值
    sds ele;
    // 分值 跳跃表中的几点都按分值从小到大排序
    double score;
    // 后退指针 从表尾向表头访问节点  每个节点只有一个 每次只能后退至前一个指针
    struct zskiplistNode *backward;
    // 层 可以包含多个元素，每个元素都指向其他节点的指针
    struct zskiplistLevel {
        // 前进指针 从表头向表尾访问节点
        struct zskiplistNode *forward;
        // 跨度 记录两个节点之间的距离
        unsigned long span;
    } level[];
} zskiplistNode;
// 跳跃表
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点数量
    unsigned long length;
    // 表中最大的节点的层数
    int level;
} zskiplist;

// 每个跳跃表节点的层高是1-32 之间的随机数
// 同一个跳跃表中，多个节点可以包含相同的分值，但是每个节点的 ele 值必须唯一
// 按分值大小排序，如果分值相同时，节点按照 ele对象的大小排序

整数集合

适用场景

1. 集合键的底层实现之一

整数集合的定义

typedef struct intset {
    // 编码方式  决定contents 元素的类型
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

升级

1. 根据新元素的类型，扩展整数集合底层数组的空间大小并为新元素分配空间。
2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正 确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
3. 将新元素添加到底层数组里面。

升级的优点

1. 提升灵活性

   可以将int16_t int32_t int64_t 类型的数据添加到同一数据结构里

2. 节约内存

   确保升级操作只会在有需要的时候进行，这可以尽量节省内存。

降级

1. 一旦升级变不能降级

压缩列表

适用场景

1. 列表键底层
2. 哈希键底层

压缩列表实现

// ziplist的总体布局如下 如果没有另外指定，所有字段都以小端存储
// <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
/**
 * <zlbytes> 是一个无符号整数，用于保存字节数 
 * <zltail> 是列表中最后一个条目的偏移量
 * <zllen> 是条目数
 * <zlend> 是表示ziplist结尾的特殊条目
 */
// <prevlen> <encoding> <entry-data>
/**
 * <prevlen> 存储前一个条目的长度
 * <encoding> 条目编码
 * <entry-data> 有时编码表示条目本身 <entry-data>部分缺失
 */
// <prevlen> <encoding>
typedef struct zlentry {
    unsigned int prevrawlensize; 
    unsigned int prevrawlen; 
    unsigned int len;
    unsigned int headersize;   
    unsigned char encoding;      
    unsigned char *p;
} zlentry;

连锁跟新

由于添加大节点导致prevlen大于等于254则 后一个节点空间扩展 导致之后的所有节点进行真写操作，同时删除节点也会导致连锁更新

对象

Redis 没有直接使用数据结构来直接实现键值对，而是基于这些数据结构创建了一个对象系统，包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。

对象的实现

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    /* LRU time (relative to global lru_clock) or
     * LFU data (least significant 8 bits frequency
     * and most significant 16 bits access time).
     */
    // 记录了最后一次被访问的时间
    unsigned lru:LRU_BITS; 
    // 引用计数 用于对象回收
    int refcount;
    // 指向底层实现的数据机构的指针
    void *ptr;
} robj;

类型

类型常量	对象名称
REDIS_STRING	字符串对象
REDIS_LIST	列表对象
REDIS_HASH	哈希对象
REDIS_SET	集合对象
REDIS_ZSET	有序集合对象

对象编码和底层实现

编码常量	底层数据结构
REDIS_ENCODING_INT	long类型整数
REDIS_ENCODING_EMBSTR	embstr编码的简单动态字符串
REDIS_ENCODING_ROW	简单动态字符串
REDIS_ENCODING_HT	字典
REDIS_ENCODING_LINKEDLIST	双端链表
REDIS_ENCODING_ZIPLIST	压缩链表
REDIS_ENCODING_INTSET	整数集合
REDIS_ENCODING_SKIPLIST	跳跃表

类型和编码对象

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT	使用整数值实现的字符串对象
REDIS_STRING	REDIS_ENCODING_EMBSTR	使用embstr编码的SDS实现的字符串对象
REDIS_STRING	REDIS_ENCODING_ROW	使用SDS实现的字符串对象
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用双端列表实现的链表对象
REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的链表对象
REDIS_HASH	REDIS_ENCODING_HT	使用字典实现的哈希对象
REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的哈希对象
REDIS_SET	REDIS_ENCODING_INTSET	使用整数集合实现的集合对象
REDIS_SET	REDIS_ENCODING_HT	使用字典实现的集合对象
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用压缩表实现的有序集合对象
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳跃表实现的有序集合对象

字符串对象

存储

1. 字符串对象保存的是整数，且整数值能用long类型表示，则编码设置为int
2. 字符串对象保存的是字符串值，且长度小于等于32个字节，使用embstr方式保存值，编码设置为embstr
3. 字符串对象保存的是字符串值，且长度大于32个字节，使用SDS保存值，编码设置为raw

编码的转化

1. 执行命令使其不再是整数值，则从int转化为raw
2. embstr 是只读的如果有修改操作命令时，则转化为raw

使用embstr 编码的好处

1. 将创建的字符串对象所需的内存次数从raw编码的两次降为一次
2. 释放embstr编码字符串对象只需要调用一次内存释放函数

列表对象

存储

1. 使用ziplist编码
2. 使用linkedlist编码的列表对象使用双端列表作为底层实现

编码转化

1. 列表对象保存的所有的字符串的长度都小于64字节，列表对象保存的元素数量小于512个
2. 不能满足这两个条件的对象需要使用linkedlist编码

哈希对象

存储

1. 使用ziplist

   保存了同一对象的两个节点总是紧挨着，键节点在前面，保存值节点在后面；先添加到哈希对象会被放到表头方向，后来的对象添加到表尾方向

2. 使用hashtable

   字典的每个键都是一个字符串对象，对象保存了键；字典的每个值都是一个字符串对象，对象保存了值

编码转换

1. 哈希对象保存的所有的键值对的键和值的字符串的长度都小于64字节，哈希对象保存的元素数量小于512个
2. 不能满足这两个条件的对象需要使用hashtable编码

集合对象

存储

1. intset

   intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。

2. hashtable

   hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素 而字典的值则全部被设置为NULL。

编码转化

1. 集合对象保存的所有元素都是整数值；集合对象保存的元素数量不超过512个 使用inset。
2. 不满足这两种条件的使用hashtable

有序集合对象

存储

1. ziplist

   每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，而第二个元素则保存元素的分值。分值小的在头，分值大的在表尾

2. skiplist

skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。

编码转化

1. 有序集合保存的元素数量小于128 个；有序集合保存的所有元素成员的长度都小于64字节
2. 不能满足以上两个条件的有序集合对象将使用skiplist编码。

类型检测与命令多态

1. 针对特定类型的键执行，在执行命令之前先检测输入的类型是否正确，然后在进行相关的操作，通过redisObject结构的type来执行
2. 根据编码方式，选择正确的命令实现代码来执行命令

内存回收

采用引用计数实现的内存回收机制，创建对象用引用计数初始化为1，被一个新程序使用时，计数加1，不再被一个程序使用时，引用计数减1，当对象的引用计数为0时，对象所占的内存空间被释放

对象共享

1. 将数据库的键指针指向一个现在的值对象
2. 将被共享的值对象的引用计数增1

对象的空转时长

记录了对象最后一次被命令程序访问的时间 使用OBJECT IDLETIME key 打印空转时长，不会修改LRU的值，如果服务器打开maxmemory的选项，当服务器占用的内存数超过了maxmemory选项上限时，空转时间较长的那部分被优先回收