读书笔记-《Redis设计与实现》（一）数据结构与对象（下）

各位朋友新年快乐~

今天我们来继续学习 Redis 。

01

整数集合

当集合仅包含整数值，并且元素数量不多时，Redis 就会采用整数集合来作为集合键的底层实现。

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    
    // 元素数量
    uint32_t length;
    
    // 数组
    int8_t contents[];
} intset;

可以看到，contents 就是存储元素的地方，各个元素按从小到大排序并且不包含重复值。注意虽然 contents 声明为 int8_t，但实际类型取决于 encoding。

看到上面的数据结构，不难想到一个问题——如果现有的数组编码为 int16_t，然后往里面添加一个 int32_t 的元素，会发生什么？

答案就是升级。整数集合升级包含三个步骤：扩展数组空间、升级旧元素类型并重新放置、放置新元素。

升级的好处是：提升整体灵活性（可以任意地往里面放置不同类型的元素）、尽可能节约内存。

02

压缩列表

当列表键仅包含小整数值和短字符串，并且元素数量不多时，Redis 就会采用压缩列表来作为列表键的底层实现。

压缩列表的结构如下：

zlbytes：记录整个列表所占内存字节数。
zltail：记录表尾节点距离起始位置的偏移量。
zllen：记录节点数量，但最大值为 UINT16_MAX（65535），超过这个值就只能通过遍历才能得到具体数量。
entry：各个节点，结构包括 previous_entry_length、encoding、content。第一个属性顾名思义，记录前一个节点的长度，因此程序可通过当前节点的起始地址来计算出前一个节点的起始地址，进而实现从表尾向表头的遍历；后两个属性分别为节点值的编码和节点的值。
zlend：末端标识符 0xFF。

03

对象

typedef struct redisObject {
    // 类型
    unsigned type:4;
    
    // 编码
    unsigned encoding:4;
    
    // 指向底层数据结构的指针
    void *ptr;
    
    // 引用计数，用于内存回收
    int refcount;
   
    // 记录最后一次被访问的时间，用于计算空转时长
    unsigned lru:22;
    
    // ...
    
} robj;

对象的关键属性如上。众所周知，Redis 包含五个对象类型，分别是字符串、列表、Hash、集合、有序集合。而我们在操作键值对时，键总是一个字符串对象，而值则可以是这五个中的任意一种。

编码则是我们前面学习的各种数据结构，例如 SDS、链表、字典、跳表、整数集合、压缩列表等等。通过这种切换编码的机制，极大提高了 Redis 的灵活性和效率。

五种类型的编码如下：

字符串对象：long 类型时编码为 int，字符串且长度大于39字节时为 raw（即 SDS），字符串且长度小于等于39字节时为 embstr。embstr 的特点是使用连续内存空间存储 redisObject 和 sdshdr 两个结构，减少了内存分配和回收次数，提升了读取速度。
列表对象：所有字符串元素长度较小并且元素总数较少时（具体数值可配置）为 ziplist，否则为 linkedlist。
Hash 对象：所有键值对的键和值字符串长度较小并且元素总数较少时（具体数值可配置）为 ziplist，否则为 hashtable。在使用前者时，键值对会按照顺序存放，例如依次放入键值对“hello-world”、“happy-new year”，则存储的节点顺序为 hello、world、happy、new year。
集合对象：所有元素为整数值且元素总数较少时（具体数值可配置）为 intset，否则为 hashtable。在使用后者时，所有的键均没有值。
有序集合对象：所有元素长度较小且元素总数较少时（具体数值可配置）为 ziplist，否则为 skiplist。特殊的点在于，使用后者时对象的结构为 zset，其同时包含一个字典和一个跳跃表，从而使得该对象在单个元素查询和范围操作时，都有着极低的时间复杂度。