3. redis数据结构与对象

redis对外支持数据结构

• 字符串 （string）
• 字符串列表（list）
• 字符串集合（sets）
• 有序字符串集合（sorted sets）
• 哈希（hash）

redis内部数据结构

1. 字符串

简单动态字符串 - 外部字符串数据格式的底层实现

// sds.h/sdshdr结构
struct sdshdr {
   int len;    // 字符串长度 即已使用的字符串长度
   int free;   // 未使用的字节长度
   char buf[]; // 字节数组 保存字符串
};

2. 链表

链表 - 外部字符串列表数据格式的底层实现

// adlist.h/listNode结构
typedef struct listNode {
   struct listNode *prev;
   struct listNode *next;
   void *value; // 节点的值
}listNode;

// adlist/list结构
typedef struct list {
    listNode *head;
    listNode *tail;
    unsigned lone len; // 链表包含节点数量
    void *(dup)(void *ptr);    // 节点值复制函数
    void *(*free)(void *ptr);  // 节点值释放函数
    void *(match)(void *ptr, void *key); // 节点值对比函数
}list;

3. 字典

字典，又称符号表，关联数组，映射。用于保存键值对的抽象数据结构。 - 数据库的增删改查和哈希键的底层实现

哈希表

// dict.h/dictEntry结构
typedef struct dictEntry {
    void *key;      
    union {  
        void *val;
        uint64_t u64;
        int64_t  s64;
    }v;
    struct dictEntry *next;
} dictEntry;

// dict.h/dictht结构
typedef struct dictht {
    dictEntry **table;      // 哈希数组
    unsigned long size;     // 哈希表数组大小
    unsigned long sizemask; // 哈希表数组大小掩码，总是size - 1
    unsigned long used;     // 哈希表已有节点数量
}dictht;

字典

// dict.h
typedef struct dict {
    dictType *type;     // 类型特定函数
    void *privdata;     // 私有数据
    dictht ht[2];       // 哈希表, 一个正常哈希，一个用于rehash
    int trehashidx;     // rehash索引 当rehash不再进行时 值为-1
} dict;

typedef struct dictType {
    // 计算哈希值函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*objDup)(void *privdata, const void *key);
    // 对比键的函数
    void *(keyCompare)(void *provdata, const void *key1, const void *key2);
    // 销毁键的函数
    void *(keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void *(valDestructor)(void *privdata, void *key);
} dictType;

3. 跳跃表

跳跃表 - 字符串有序集合数据格式的底层实现

还用在集群节点中用作内部结构

// redis.h
typedef struct zskiplistNode {
    struct zskiplistNode *backward; // 后退指针
    double score;   // 分值
    robj   obj;     // 成员对象
    struct zskiplistLevel {     // 层
        struct zskiplistNode *forward; // 前进指针
        unsigned int span;      // 跨度
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;   // 表节点的数量
    int level;              // 表中层数最大的节点层数
} zskiplist;

每个跳跃表节点的层高都是1~32之间的随机数

在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的

跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序

5. 整数集合

整数集合 - 集合键的底层实现

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

/*
其中 encoding属性取值为：指明conetens数组元素单元的大小
    INTSET_ENC_INT16  
    INTSET_ENC_INT32 
    INTSET_ENC_INT64
可自动升级操作
*/

6. 压缩列表

压缩列表 - 是列表键哈哈希键的底层实现之一

压缩列表可以保存多个节点，每个节点可以保存一个字节数组或整数值

结构如下：

• zlbtyes：记录整个压缩列表暂用的内存字节数
• zltail：压缩列表起始地址加上这个偏移量可以确定entryN表尾节点的地址
• zllen：记录压缩列表节点个数
• zlend：特殊值0xFF, 用于标记压缩列表的末端
• entryN：

• previous_entry_length：记录压缩列表前一个节点的长度；1字节或者5字节

若前一个字节长度小于254，该字段占1字节；

否则占5字节，这时候第一个字节设置为0xFE, 剩下4个字节表示前一个节点的长度

• encoding：记录了节点content属性所保存数据的类型及长度

有点复杂 - 先不了解 见《redis设计与实现》

• content：保存节点的值

连锁更新 ----> 见《redis设计与实现》

添加新节点到压缩列表或删除节点可能会引发连锁更新操作，但是这种机率并不高

7. 对象

对象就是上面所说的redis对外支持的数据结构，这里是用对象更为合适吧

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

还实现了基于引用计数的内存回收机制，当程序不再使用某个对象时，这个对象所占用的内存会被释放

还通过这个引用计数实现对象共享机制

typedef struct redisObject {
    unsigned type:4;        // 类型
    unsigned encoding:4;    // 编码
    void *ptr;              // 指向底层数据结构指针
    ...
} robj;

/*
type:   五种对象类型
    REDIS_STRING    ->  string
    REDIS_LIST      ->  list
    REDIS_HASH      ->  hash
    REDIS_SET       ->  set
    REDIS_ZSET      ->  zset
*/


/*
encoding:   底层实现的数据结构
    REDIS_ENCODING_INT          ->  long类型的整数                                   
    REDIS_ENCODING_EMBSTR       ->  embstr编码的简单动态字符串
    REDIS_ENCODING_RAW          ->  简单动态字符串
    REDIS_ENCODING_HT           ->  字典          
    REDIS_ENCODING_LINKEDLIST   ->  双端链表      
    REDIS_ENCODING_ZIPLIST      ->  压缩列表      
    REDIS_ENCODING_INTSET       ->  整数集合      
    REDIS_ENCODING_SKIPLIST     ->  跳跃表和字典
*/

• 字符对象 可以是 整数数值 或 emstr 或 简单动态字符串实现
• 列表对象 可以是 压缩列表 或 双端队列
• 哈希对象 可以是 压缩列表 或 字典实现
• 集合对象 可以是 整数集合 或 字典实现
• 有序集合对象 可以是 跳跃表 或 字典实现、

7.1 字符串对象

如果字符串对象是整数值，且可以用long类型表示 采用编码方式是int

如果字符串对象是字符串值，且字符串长度超过39个字节，采用编码方式是raw

如果字符串对象是字符串值，且字符串长度小于等于39个字节，采用编码方式是embstr

区别raw与embstr两种类型的简单动态字符串

编码转换

int编码的字符串对象 和 embstr编码的字符串对象 在条件满足的情况下， 会被转换成 raw编码的字符串对象

7.2 列表对象

当列表同时满足以下两个条件时，采用编码方式为ziplist，否则为linklist

1. 列表对象保存的所有字符串元素长度都小于64字节（可配）
2. 列表对象保存的元素数量小于512个（可配）

编码转换

当以上两个条件被破坏时，ziplist编码会转换成linklist编码

7.3 哈希对象

当哈希同时满足以下两个条件时，采用编码方式为ziplist，否则为hashtable

1. 哈希对象保存的所有字符串元素长度都小于64字节（可配）
2. 哈希对象保存的元素数量小于512个（可配）

编码转换

当以上两个条件被破坏时，ziplist编码会转换成hashtable编码

7.4 集合对象

当集合同时满足以下两个条件时，采用编码方式为intset，否则为hashtable

1. 集合对象保存的所有元素都是整数值
2. 集合对象保存的元素数量小于512个（可配）

编码转换

当以上两个条件被破坏时，ziplist编码会转换成hashtable编码

7.5 有序集合对象

typedef struct zset {
    zskiplist *zsl;
    dict      *dict;
} zset;

当有序集合同时满足以下两个条件时，采用编码方式为intset，否则为skiplist

1. 有序集合对象保存的所有元素成员的长度都小于64个字节（可配）
2. 有序集合对象保存的元素数量小于128个（可配）

编码转换

当以上两个条件被破坏时，ziplist编码会转换成skiplist编码

7.6 内存回收

在对象结构中增加一个引用计数技术实现内存回收机机制

typedef struct redisObject {
    ...
    int refcount;   // 引用计数
    ...
} robj;

/*
    当创建新对象时，引用计数加1
    当对象被一个新程序使用时，引用计数加1
    当对象不再被一个程序使用时，引用计数减1
    当引用计数数值为0时，对象所占用的内存会被释放
*/

7.7 对象共享

引用计数除了可以实现内存回收机制，还可以带有对象共享的作用

--- 节约内存

7.8 对象的空转时长

reidsObject结构还有一个字段lru属性，该属性记录例如对象最后一次被命令程序访问的时间

#define LRU_BITS 24     
typedef struct redisObject {
    ...
    unsigned lru:LRU_BITS;   // 引用计数
    ...
} robj;

参考：
黄键宏老师的《redis设计与实现》，机械工业出版社