数据结构与对象

1. 数据结构

1.1 简单动态字符串

SDS，simple dynamic strig，简单动态字符串，redis中的sds是对C语言中字符串的优化。

关于sds的定义如下述代码所示，src/sds.h

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

len：已经使用的空间
alloc：总共可用的字符串大小=buf大小-1
flag：标志位，主要用来标识这是sdshrd几
buf：存储字符串的数组

1.1.1 sds和c字符串的区别

1.1.1.1 O(1)获取字符串长度

c字符串本身不记录自身的长度信息，如果需要获取长度，则必须遍历整个字符串，复杂度为O(N)。
sds使用len就能获得长度，复杂度O(1)。

1.1.1.2 杜绝缓冲区溢出

char strcat(char dest, const char src)
strcat函数可以将str的字符串的内容拼接到dest字符串的末尾。因为c字符串不记录自身的长度，所以strcat假定用户已经为dest分配了足够多的内存，可以容纳src中的所有内容，但是如果这个假定不成立，就会产生*缓冲区溢出。比如字符串A和B在内存中紧邻，那么在strcat执行之后，会导致B的内容被修改。

sds的空间分配策略完全杜绝了缓冲区溢出的可能性，当需要对sds进行修改时，api会先检查sds的空间是否满足修改所需的要求，如果不满足的话，api会自动将sds的空间扩展至修改所需的大小，然后再执行修改操作。

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

频繁修改一个字符串，会涉及到内存的重分配，比较耗费性能。redis采用空间预分配和惰性空间释放来减少重分配的次数。

1.1.1.4 二进制安全

二进制安全，简单来说就是，二进制数据在写入时是怎么样的，读取时就是怎么样。
c字符串根据空字符来判断结尾，字符串里如果包含空字符，c字符串就会忽略掉空字符后面的内容。

sds对每个字符都公平对待，不特殊处理某一个字符。

1.2 链表

双端、无环、带头尾指针、长度计数、多态。
其他没啥好说

1.3 字典

存储键值对的数据结构，即哈希表（咋实现的不写了，懂的都懂），redis的字典使用链表法解决hash冲突，使用MurmurHash2计算哈希值。
需要注意的是，字典中使用哈希表的字段是个数组，该数组包含两个哈希表 ht[0], ht[1] 。ht[0] 用来存储数据，ht[1] 在对 ht[0] 进行rehash时使用。

rehash

步骤：

1. 为 ht[1] 分配空间
2. 将 ht[0] 上的所有键值对rehash到 ht[1] 上
3. 当 ht[0] 上的所有键值对都迁移到 ht[1] 之后，释放 ht[0]，将 ht[1] 设置为 ht[0]，并为 ht[1] 新创建一个空白的哈希表，为下一次rehash做准备

rehash需要把所有的键值对都迁移到 ht[1] ，这个操作并不是一次就完成的，而是分多次、渐进式地完成，这就是渐进式rehash。
字典中维护了一个索引计数器遍历 rehashidx，默认为-1，当rehash工作开始时，会将其置为0；在rehash进行期间，每次对字典执行crud操作，程序都会顺带将 ht[0] 哈希表上 rehashidx 索引上的 所有键值对rehash到 ht[1]，当该索引的rehash工作完成之后，rehashidx++。当所有的rehash操作完成之后，rehashidx被重置为-1。

在渐进式rehash的过程中，字典的删除、查找、更新等操作会在两个哈希表上进行。例如要查找一个键，会现在ht[0] 找，没找到继续去 ht[1] 找。另外新添加的键值对会被添加到 ht[1]。

扩容和收缩的条件

负载因子 = 哈希表已保存节点数 / 哈希表大小

1. 服务器没在执行BGSAVE或者BGREWRITEAOF，负载因子大于1时进行扩容
2. 服务器在执行BGSAVE或者BGREWRITEAOF，负载因子大于5时进行扩容
3. 负载因子小于0.1时，进行收缩

1.4 跳表

跳跃表，一种有序的数据结构，它通过在一个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。复杂度：平均O(logN)，最坏O(N)。

1.5 整数集合

整数集合是集合键的底层实现之一，当一个集合只包含整数值的元素，并且这个几个的元素不多时，会使用整数集合来作为底层实现。

1.6 压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来作为列表键的底层实现。

2. 对象

上文介绍了redis的6种基本数据结构，但是redis并没有直接使用这些数据结构来实现数据库，而是在这些数据结构的基础上创建了一个对象系统，主要包含：

• 字符串对象
• 列表对象
• 哈希对象
• 集合对象
• 有序集合对象

这五种类型的对象，是有上述的6种基本数据结构实现的。

redis使用对象来表示数据库中的键值对，在新建一个键值对时，会新建两个对象，分别是键对象、值对象。redis中的每个对象都由下面的redisObject结构表示。

typedef struct redisObject {
    // 对象的类型，字符串/列表/集合/哈希表
    unsigned type:4;
    // 编码的方式，Redis 为了节省空间，提供多种方式来保存一个数据
    unsigned encoding:4;
    // 数据指针
    void *ptr;
    ....
} robj;