Redis字典的扩展与自定义

Redis 字典基础

Redis 是一个基于内存的高性能键值对存储数据库，其内部使用了多种数据结构来实现不同的数据类型。字典（dict）是 Redis 中非常重要的数据结构之一，用于实现 Redis 的数据库以及哈希表等功能。

Redis 的字典采用了哈希表（hash table）的实现方式。哈希表是一种根据关键码值（key）直接进行访问的数据结构，它通过一个哈希函数将键映射到一个哈希值，然后根据这个哈希值来确定数据在表中的存储位置。

在 Redis 中，字典由 dict 结构体表示，其定义如下：

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

• type 字段指向一个 dictType 结构体，该结构体定义了操作字典键值对的一系列函数，例如计算哈希值的函数、比较键的函数等。
• privdata 字段是一个指针，用于传递给 dictType 中函数的可选参数。
• ht 是一个包含两个 dictht 结构体的数组，dictht 表示哈希表。一般情况下，只使用 ht[0]，当进行 rehash 操作时，会同时使用 ht[0] 和 ht[1]。
• rehashidx 用于记录 rehash 的进度，当 rehashidx == -1 时，表示当前没有进行 rehash 操作。
• iterators 记录当前正在运行的迭代器数量。

dictht 结构体的定义如下：

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

• table 是一个指向 dictEntry 结构体指针数组的指针，dictEntry 结构体用于存储键值对。
• size 表示哈希表的大小，即 table 数组的长度。
• sizemask 是 size - 1，用于计算哈希值在 table 数组中的索引位置。
• used 记录哈希表中已使用的槽位数量。

dictEntry 结构体的定义如下：

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

• key 是键，v 是值的联合体，可以存储不同类型的值。
• next 指针用于解决哈希冲突，采用链地址法（separate chaining）来处理冲突。当不同的键计算出相同的哈希值时，这些键值对会通过 next 指针链接成一个链表。

Redis 字典的基本操作

插入操作

在 Redis 字典中插入一个键值对时，首先会根据键计算其哈希值，然后通过哈希值与 sizemask 进行按位与运算，得到该键值对在 table 数组中的索引位置。如果该位置已经有其他键值对（即发生了哈希冲突），则会通过 next 指针将新的键值对插入到链表的头部。

以下是简化的插入操作伪代码：

hash = dictHashFunction(key)
index = hash & dict->ht[x].sizemask
entry = dict->ht[x].table[index]
while entry != NULL:
    if dictCompareKeys(entry->key, key) == 0:
        // 键已存在，更新值
        dictSetVal(dict, entry, value)
        return
    entry = entry->next
newEntry = createDictEntry(key, value)
newEntry->next = dict->ht[x].table[index]
dict->ht[x].table[index] = newEntry
dict->ht[x].used++

删除操作

删除操作首先根据键计算哈希值并找到对应的索引位置，然后遍历链表查找要删除的键值对。如果找到，则将其从链表中移除，并调整相关指针。

以下是简化的删除操作伪代码：

hash = dictHashFunction(key)
index = hash & dict->ht[x].sizemask
prev = NULL
entry = dict->ht[x].table[index]
while entry != NULL:
    if dictCompareKeys(entry->key, key) == 0:
        if prev == NULL:
            dict->ht[x].table[index] = entry->next
        else:
            prev->next = entry->next
        freeDictEntry(entry)
        dict->ht[x].used--
        return
    prev = entry
    entry = entry->next

查找操作

查找操作同样根据键计算哈希值并找到对应的索引位置，然后遍历链表查找目标键值对。

以下是简化的查找操作伪代码：

hash = dictHashFunction(key)
index = hash & dict->ht[x].sizemask
entry = dict->ht[x].table[index]
while entry != NULL:
    if dictCompareKeys(entry->key, key) == 0:
        return entry->v
    entry = entry->next
return NULL

Redis 字典的 rehash

随着键值对的不断插入和删除，哈希表的负载因子（used / size）会发生变化。当负载因子过高（默认情况下，当 ht[0].used / ht[0].size >= 1 时），为了保证字典的性能，Redis 会进行 rehash 操作。rehash 操作的主要步骤如下：

1. 分配新的哈希表：在 ht[1] 中分配一个大小为 ht[0].size * 2 的新哈希表。
2. 将旧哈希表的数据迁移到新哈希表：逐个将 ht[0] 中的键值对重新计算哈希值并插入到 ht[1] 中。
3. 释放旧哈希表：当所有数据迁移完成后，释放 ht[0]，并将 ht[1] 赋值给 ht[0]，然后为 ht[1] 重新分配一个空的哈希表，用于下一次 rehash。

为了避免在 rehash 过程中字典性能急剧下降，Redis 采用了渐进式 rehash 的方式。在渐进式 rehash 过程中，rehashidx 记录了当前 rehash 的进度。每次对字典进行插入、删除、查找或更新操作时，除了执行相应的操作外，还会顺带将 ht[0] 中 rehashidx 位置的键值对迁移到 ht[1] 中，并将 rehashidx 加一。这样，在一段时间内，会逐步将 ht[0] 中的数据全部迁移到 ht[1] 中。

Redis 字典的扩展

自定义哈希函数

Redis 允许用户自定义哈希函数，通过修改 dictType 结构体中的 hashFunction 字段来实现。例如，假设我们有一个自定义的哈希函数 myHashFunction：

unsigned long myHashFunction(const void *key) {
    // 自定义哈希函数逻辑
    // 例如简单的字符串哈希函数
    const char *str = (const char *)key;
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

然后可以创建一个新的 dictType 结构体，并将 hashFunction 设置为 myHashFunction：

dictType myDictType = {
   .hashFunction = myHashFunction,
   .keyDup = NULL,
   .valDup = NULL,
   .keyCompare = NULL,
   .keyDestructor = NULL,
   .valDestructor = NULL
};

最后创建字典时使用这个自定义的 dictType：

dict *myDict = dictCreate(&myDictType, NULL);

自定义键比较函数

除了自定义哈希函数，还可以自定义键比较函数。通过修改 dictType 结构体中的 keyCompare 字段来实现。例如，假设我们有一个自定义的键比较函数 myKeyCompare，用于比较两个字符串键是否相等：

int myKeyCompare(void *privdata, const void *key1, const void *key2) {
    return strcmp((const char *)key1, (const char *)key2) == 0;
}

然后更新 dictType 结构体：

dictType myDictType = {
   .hashFunction = myHashFunction,
   .keyDup = NULL,
   .valDup = NULL,
   .keyCompare = myKeyCompare,
   .keyDestructor = NULL,
   .valDestructor = NULL
};

这样在创建字典时，就会使用这个自定义的键比较函数来判断键的相等性。

自定义键值对复制与销毁函数

在某些情况下，我们可能需要自定义键值对的复制和销毁函数。通过 dictType 结构体中的 keyDup、valDup、keyDestructor 和 valDestructor 字段来实现。

例如，假设我们有自定义的键复制函数 myKeyDup 和键销毁函数 myKeyDestructor：

void *myKeyDup(void *privdata, const void *key) {
    size_t len = strlen((const char *)key) + 1;
    char *newKey = (char *)malloc(len);
    if (newKey) {
        strcpy(newKey, (const char *)key);
    }
    return newKey;
}

void myKeyDestructor(void *privdata, void *key) {
    free(key);
}

同样可以定义值的复制和销毁函数。然后更新 dictType 结构体：

dictType myDictType = {
   .hashFunction = myHashFunction,
   .keyDup = myKeyDup,
   .valDup = NULL,
   .keyCompare = myKeyCompare,
   .keyDestructor = myKeyDestructor,
   .valDestructor = NULL
};

这样在字典操作过程中，涉及到键的复制和销毁时，就会调用我们自定义的函数。

Redis 字典自定义的应用场景

特定数据类型的高效存储

假设我们有一个应用场景，需要存储大量的自定义结构体对象，并且这些对象的某些字段作为键。通过自定义哈希函数和键比较函数，可以针对这些结构体的特点进行优化，提高字典操作的效率。例如，结构体中有一个唯一标识的整数字段，我们可以编写一个专门针对这个整数字段的高效哈希函数，而不是使用默认的通用哈希函数。

安全敏感数据处理

在处理安全敏感数据时，可能需要自定义键值对的销毁函数，确保在数据不再使用时能够安全地释放内存，避免数据泄露。例如，存储用户密码哈希值时，在删除键值对时，自定义的销毁函数可以将密码哈希值所在的内存区域清零，然后再释放内存。

分布式系统中的数据一致性

在分布式系统中，不同节点可能需要对相同的数据进行字典操作。通过自定义哈希函数和键比较函数，可以保证在不同节点上对相同键值对的处理一致性。例如，使用一致性哈希算法作为自定义哈希函数，使得数据在不同节点上的分布更加均匀和可预测。

示例代码完整实现

下面是一个完整的示例代码，展示了如何使用自定义的哈希函数、键比较函数以及键值对复制和销毁函数来创建和操作 Redis 字典。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 自定义哈希函数
unsigned long myHashFunction(const void *key) {
    const char *str = (const char *)key;
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

// 自定义键比较函数
int myKeyCompare(void *privdata, const void *key1, const void *key2) {
    return strcmp((const char *)key1, (const char *)key2) == 0;
}

// 自定义键复制函数
void *myKeyDup(void *privdata, const void *key) {
    size_t len = strlen((const char *)key) + 1;
    char *newKey = (char *)malloc(len);
    if (newKey) {
        strcpy(newKey, (const char *)key);
    }
    return newKey;
}

// 自定义键销毁函数
void myKeyDestructor(void *privdata, void *key) {
    free(key);
}

// 自定义值复制函数
void *myValDup(void *privdata, const void *val) {
    size_t len = strlen((const char *)val) + 1;
    char *newVal = (char *)malloc(len);
    if (newVal) {
        strcpy(newVal, (const char *)val);
    }
    return newVal;
}

// 自定义值销毁函数
void myValDestructor(void *privdata, void *val) {
    free(val);
}

// 自定义字典类型
dictType myDictType = {
   .hashFunction = myHashFunction,
   .keyDup = myKeyDup,
   .valDup = myValDup,
   .keyCompare = myKeyCompare,
   .keyDestructor = myKeyDestructor,
   .valDestructor = myValDestructor
};

int main() {
    dict *myDict = dictCreate(&myDictType, NULL);

    // 插入键值对
    dictAdd(myDict, "key1", "value1");
    dictAdd(myDict, "key2", "value2");

    // 查找键值对
    dictEntry *entry = dictFind(myDict, "key1");
    if (entry) {
        printf("Found key1, value: %s\n", (char *)dictGetVal(entry));
    } else {
        printf("Key1 not found\n");
    }

    // 删除键值对
    dictDelete(myDict, "key2");

    // 释放字典
    dictRelease(myDict);

    return 0;
}

在这个示例代码中，我们首先定义了自定义的哈希函数、键比较函数、键值对复制和销毁函数。然后创建了一个自定义的 dictType 结构体，并使用这个结构体创建了 Redis 字典。接着进行了插入、查找和删除操作，最后释放了字典。

注意事项

1. 性能考虑：在自定义哈希函数和键比较函数时，要注意函数的性能。一个低效的哈希函数可能导致哈希冲突频繁发生，从而降低字典的操作效率。同样，复杂度过高的键比较函数也会影响查找、插入和删除的速度。
2. 内存管理：自定义的键值对复制和销毁函数需要正确处理内存分配和释放。如果内存管理不当，可能会导致内存泄漏或悬空指针等问题。
3. 兼容性：当在 Redis 环境中使用自定义字典功能时，要确保自定义的函数与 Redis 的其他部分兼容。例如，自定义的键比较函数应该与 Redis 中其他依赖键比较的操作（如排序等）保持一致。

通过对 Redis 字典的扩展与自定义，我们可以根据具体的应用场景对字典的行为进行优化，提高 Redis 在特定场景下的性能和适用性。无论是处理特殊数据类型、保证数据安全还是在分布式系统中实现数据一致性，自定义字典功能都提供了强大的工具。