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

也就是我们常说的Redis中的String类型，它的数据结构为：

struct sdshdr {
    // 标识当前字符串的实际长度  
    int len;

    // 标识剩余空间
    int free;

    // 存储字符数据的char数组
    char buf[];
}

基于这种设计的SDS有如下特性：

• 记录了字符串长度，获取字符串长度的复杂度为O(1)
• 通过预分配策略，杜绝了缓冲区溢出
• 通过预分配和惰性空间释放策略减少了修改字符串时带来的内存重分配次数
• 二进制安全，可以保存图片、音频、视频、压缩文件等二进制数据

链表（List）

Redis实现的链表有如下特性：

• 双端
• 无环
• 带链头指针和链尾指针
• 带链表长度计数器
• 链节点使用void*指针来保存节点值，可以保存各种不同数据类型的值

其数据结构如下：

typedef struct listNode {
    // 前置节点
    struct listNode* prev;

    // 后置节点
    struct listNode* next;

    // 节点值
    void* value;
} listNode;

typedef struct list {
    // 链头节点
    listNode* head;

    // 链尾节点
    listNode* tail;

    // 节点数量
    unsigned long len;

    // 节点值复制函数
    void* (*dup)(void* ptr);

    // 节点释放函数
    void (*free)(void* ptr);

    // 节点值比对函数
    int (*match)(void *ptr, void* key);
} list;

字典

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希节点，而每个哈希节点保存了字典中的一个键值对。

哈希表

Redis哈希表数据结构如下：

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

table属性是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。

哈希表节点

哈希表节点dictEntry结构如下：

typedef struct dictEntry {
    // 键
    void* key;

    // 值
    union {
        void* val;
        uint64_tu64;
        int64_ts64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry* next;
} dictEntry;

key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_tu64整数，又或者是一个int64_ts64整数。

字典

Redis中的字典由dict结构表示：

typedef struct dict {
    // 类型特定函数
    dictType* type;

    // 私有数据
    void* privdata;

    // 哈希表
    dictht ht[2];

    // rehash索引
    // 当rehash不在进行时，值为-1
    int rehashidx;
} dict;

type：指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
privdata：保存了需要传给类型特定函数的可选参数。
ht：包含两个dictht哈希表的数组，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
rehashidx：记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。

字典类型

typedef struct dictType {
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void* key);

    // 复制键的函数
    void* (*keyDup)(void* privdata, const void* key);

    // 复制值的函数
    void* (*valDup)(void* privdata, const void* obj);

    // 对比键的函数
    int (*keyCompare)(void* privdata, const void* key1, const void* key2);

    // 销毁键的函数
    void (*keyDestructor)(void* privdata, void* key);

    // 销毁值的函数
    void (*valDestructor)(void* privdata, void* obj);
} dictType;

哈希算法

计算步骤：

1、使用字典设置的哈希函数，计算Key的哈希值
hash = dict->type->hashFunction(key);

2、使用哈希表的sizemask属性和哈希值，计算出索引值

3、根据情况不同，ht[x]可以是ht[0]或者ht[1]
index = hash & dict->ht[x].sizemask;

Redis使用MurmurHash2算法来计算键的哈希值。这种算法的优点在于：即使输入的键是有规律的，也仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。

关于MurmurHash算法更多的信息可以参考：http://code.google.com/p/smhasher

解决键冲突

Redis使用链地址法来解决Hash冲突

扩容

采用渐进式rehash来应对成百上千键值对rehash的问题。

当索引计数器变量rehashidx设置为0时，表示rehash工作正式开始。在rehash进行期间，每次对字典执行CRUD操作时，会顺带将ht[0]哈希表在hashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性值增一。

当ht[0]的所有键值对都被rehash至ht[1]时，程序将rehashidx值设为-1。

另外，需要注意的是：rehash期间，新增的键值对不再写入ht[0]中。

---

• ← Previous Post
• Next Post →