redis源码阅读之基本数据结构

基本数据结构

动态字符串(dynamic string)

  • sds.h
  • sds.c

存储在 heap 上,只是比 c 中的字符串类型多了一个结构头, 在结构头里有 len 和 size 属性,实现了二进制安全。

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

双向链表(doubly linked list)

  • adlist.h
  • adlist.c

与教科书上面讲的几乎没什么差别:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

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;

字典(Hash Table)

  • dict.h
  • dict.c

利用链地址法来解决字典 hash 碰撞。

redis 中的 dict 的 rehash 是渐进式, 也就是说 rehash 过程不是一下子就完成的, 起初只是将 dict 状态修改为正处于 rehashing 中, 而是在之后的每一次 dict 访问时,都会转移几个 key-value 对, 直到 rehash 完毕,再次修改 dict 状态为已 rehashing 完毕。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators;
} dict;

跳跃表

  • redis.h
  • t_zset.c

跳跃表其实就是有序链表的一个变种,查找、删除和添加元素的速度和平衡二叉树相近,但实现起来更直观一些。

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

整数集合

  • intset.h
  • intset.c

就是用一个数组存放有序整数的集合,根据存放整数的大小来确定集合中各个整数所占用的字节数。

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

压缩列表

  • ziplist.h
  • ziplist.c

压缩列表也是一个列表,列表根据各元素的性质来决定使用何种方式、大小来存放元素, 其实就是一段连续内存,其结构如下:

<zlbytes><zltail><zllen><entry><entry><zlend>

entry 可以存放的类型有:

  • 4bit 无符号数
  • 1byte 符号整数
  • 3byte 有符号整数
  • int16_t 整数
  • int32_t 整数
  • int64_t 整数
  • 长度小于等于 63(2^6 - 1) 字节的字符数组
  • 长度小于等于 16383(2^14 - 1) 字节的字符数组
  • 长度小于等于 4294967295(2^32 - 1) 字节的字符数组

ziplist 中的 entry 的定义如下:

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;
    unsigned char *p;
} zlentry;

基本类型

redis 支持的基本类型及它们在内存中的表现形式:

  • string 类型 

    • long
    • 动态字符串
  • list 类型

    • 压缩列表
    • 双向类表
  • set 类型

    • 整数集合
    • 字典
  • zset 类型

    • 跳跃表
    • 双向链表
  • hash 类型

    • 压缩列表
    • 字典