Redis底层数据结构

SDS（Simple Dynamic String）简单动态字符串

• 结构

  
  redis设计与实现
• 执行以下命令

test:0>set msg "hello world"

redis会创建一对键值对
键值对的键是一个字符串对象，它底层保存这一个“msg“的SDS
键值对的键也是一个字符串对象，值的底层保存一个“hello world”的SDS

链表(list)

• 结构

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


/*
 * 双端链表节点
 */
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

redis设计与实现

字典(dict)

• 字典数据结构

/*
 * 字典
 */
typedef struct dict {
    // 类型特定函数  (字典会用到的操作函数)
    dictType *type;
    // 私有数据 (用于传给特定函数的值)
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

每个字典都使用两个哈希表，从而实现渐进式 rehash 。
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    //这边主要是为了解决hash冲突
    struct dictEntry *next;
} dictEntry;

普通状态下的字典(没有进行rehash)

• 哈希算法
  每次有新的键值数据被创建时，都会先用哈希算法计算哈希值

// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
h = dictHashKey(ht, key) & ht->sizemask;

Redis用murmurhash2来实现hash值的计算

• 解决hash冲突
  主要用的是在上面代码dictEntry实体中的next字段。当hash值发生冲突时直接把发生冲突的新节点的next字段指向新节点(这么做的原因是如果链表没有提供指向链表末尾节点的指针，如果把新节点添加到老节点后面，如果老节点后面已经有冲突，可能会一直next寻址下去，增加了寻址时间)

跳跃表(zskiplist)

跳跃表( skiplist) 是一种有序的数据结构, 它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的.

• 结构

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

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

跳跃表图示

整数集合(intset)

整数集合是redis用于保存整数值的集合抽象，他可以保存类型为int16_t，int32_t，int64_t，并列保证不会有重复的

• 结构

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

• 自动升级
  三个类型的上下限分别为：int16_t（-32768，32767），int32_t（-2147483648，2147483647），int64_t
  默认存储为了节省空间，选用的是int16，当需要存储的数据超过int16时（比如存入32777），会自动升级成int32，但是相反的，是不允许降级的，尽管没有超过的数值。

压缩列表(ziplist)

• 压缩列表是由一系列的特殊编码的连续内存块组成的顺序型设计模式

// 源码里的布局说明
 * The general layout of the ziplist is as follows:
 *
 * <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

image.png

/*
 * 保存 ziplist 节点信息的结构
 */
typedef struct zlentry {
    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;
    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小
    unsigned int lensize, len;
    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 当前节点值所使用的编码类型
    unsigned char encoding;
    // 指向当前节点的指针
    unsigned char *p;
} zlentry;

• prevrawlensize 前置节点的长度，该属性用于遍历压缩列表(当前节点的指针-prevrawlensize =上个节点的指针，下面的privious_entry_length即prevrawlensize )

  
  redis设计与实现

快速列表(quicklist)

• redis 3.2后新增的数据结构，原理为双向压缩列表
• 结构

typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    unsigned int sz;
    int offset;
} quicklistEntry;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

encoding判断数据结构源码

char *strEncoding(int encoding) {
    switch(encoding) {
    case OBJ_ENCODING_RAW: return "raw";
    case OBJ_ENCODING_INT: return "int";
    case OBJ_ENCODING_HT: return "hashtable";
    case OBJ_ENCODING_QUICKLIST: return "quicklist";
    case OBJ_ENCODING_ZIPLIST: return "ziplist";
    case OBJ_ENCODING_INTSET: return "intset";
    case OBJ_ENCODING_SKIPLIST: return "skiplist";
    case OBJ_ENCODING_EMBSTR: return "embstr";
    default: return "unknown";
    }
}