losophy

redis数据结构与对象

发表于 更新于

redis数据库每个键值对都是由对象组成。

数据库键总是一个字符串对象；
而数据库键的值则可以是字符串对象、列表对象、哈希对象、集合对象，有序集合对象。

字符串

redis没有直接使用c语言传统字符串，而是自己构建了一种名为简单动态字符串（SDS）的抽象类型。主要是为了解决'\0'的问题。

1
2
3
4
5
struct sdshdr {
　　int len;         // buf 中已占用空间的长度 0
　　int free;       // buf 中剩余可用空间的长度 5
　　char buf[];   // 数据空间，最后一个字节保存空字符 'r''e''d''i''s''%0'
};

这样做的好处（长度、结束都由len判断，分配预留free）:

  • 可以常数复杂度获取字符串长度
  • 杜绝缓冲区溢出
  • 减少修改字符串时带来的内存重分配次数
  • 二进制安全（二进制安全就是输入任何字节都能正确处理, 即使包含零值字节）
  • 兼容部分c字符串函数

链表

链表提供了高效和节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

链表在redis中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，redis就会使用链表为列表键的底层实现。

1
2
3
4
5
typedef struct listNode {
    struct listNode *prev;     // 前置节点
    struct listNode *next;     // 后置节点
    void *value;                  // 节点的值
} listNode;
1
2
3
4
5
6
7
8
9
typedef struct list {
    void *(*dup)(void *ptr);      // 节点值复制函数
    void (*free)(void *ptr);       // 节点值释放函数
    int (*match)(void *ptr, void *key);      // 节点值对比函数

    listNode *head;        // 表头节点
    listNode *tail;          // 表尾节点
    unsigned long len;         // 链表所包含的节点数量
} list;

redis的链表实现的特性：

  • 双端， 获取某个节点的前置节点和后置节点的复杂度都是O(1)
  • 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
  • 带表头表尾指针，获取俩复杂度为O(1)
  • 带链表长度计数器，获取节点数量的复杂度为O(1)
  • 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

字典

redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都比较长的字符串时，redis就会使用字典作为哈希键的底层实现。

哈希

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictEntry {
    void *key;        // 键

    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;                   // 值

    struct dictEntry *next;     // 指向下个哈希表节点，形成链表
} dictEntry;
1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;        // 哈希表数组
    unsigned long size;      // 哈希表大小
    unsigned long sizemask;     // 哈希表大小掩码，用于计算索引值，总是等于 size - 1
    unsigned long used;        // 该哈希表已有节点的数量
} dictht;

字典

1
2
3
4
5
6
7
typedef struct dict {
    dictType *type;         // 类型特定函数
    void *privdata;         // 私有数据
    dictht ht[2];             // 哈希表    
    int rehashidx;    // rehash 索引，当 rehash 不在进行时，值为 -1
    int iterators;     // 目前正在运行的安全迭代器的数量
} dict;

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。
ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
rehashidx它记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。

跳跃表(skiplist)

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

redis使用跳跃表作为有序集合键的底层实现之一。
和链表、字曲等数据结构被广泛地应用在redis内部不同，redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

1
2
3
4
5
6
7
8
9
10
typedef struct zskiplistNode {
    robj *obj;     // 成员对象
    double score;    // 分值
    struct zskiplistNode *backward;    // 后退指针

    struct zskiplistLevel {     
        struct zskiplistNode *forward;         // 前进指针
        unsigned int span;                         // 跨度
    } level[];                                         // 层
} zskiplistNode;                
1
2
3
4
5
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;      // 表头节点和表尾节点
    unsigned long length;                        // 表中节点的数量
    int level;                                         // 表中层数最大的节点的层数
} zskiplist;

整数集合

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

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

压缩列表（为了节约内存）

压缩列表是列表键和哈希键的底层实现之一。
当一个列表键只包含少量列表项，并且每个列表要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做列表键的底层实现。
压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

1
2
3
4
5
6
7
8
9
10
11
12
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1; // ZIPLIST_HEADER_SIZE 是 ziplist 表头的大小， 1 字节是表末端 ZIP_END 的大小
    unsigned char *zl = zmalloc(bytes);    // 为表头和表末端分配空间

    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);    // 初始化表属性
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;

    zl[bytes-1] = ZIP_END;    // 设置表末端

    return zl;
}

redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统。
redis还在这对象系统中构建了一个引用计数技术实现的内存回收机制。

1
2
3
4
5
6
7
typedef struct redisObject {
    unsigned type:4;    // 类型
    unsigned encoding:4;    // 编码
    unsigned lru:REDIS_LRU_BITS;    // 对象最后一次被访问的时间
    int refcount;    // 引用计数
    void *ptr;    // 指向实际值的指针
} robj;

参考

《redis 设计与实现》
Redis 2.9源码

A beber y a tragar, que el mundo se va a acabar.

相关文章