从源码层面解读 Redis 链表实现原理
2023-05-066.1k 阅读
Redis 链表概述
Redis 是一个开源的高性能键值对存储数据库，其丰富的数据结构是其强大功能的基础。链表作为一种常见的数据结构，在 Redis 中有着广泛的应用。Redis 的链表实现不仅用于管理数据，还在很多内部机制中发挥作用，例如在发布订阅、慢查询日志以及监视器等功能中，链表都用于维护相关信息。
Redis 链表是一种双向链表，每个节点包含前驱节点指针、后继节点指针以及节点值。这种双向链表的结构使得在链表的遍历过程中可以双向移动，提高了操作的灵活性。
链表数据结构定义
在 Redis 源码中，链表相关的数据结构定义在 adlist.h 头文件中。主要涉及到三个结构体：listNode、listIter 和 list。
listNode结构体
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
prev指针指向前驱节点，next指针指向后继节点，value指针指向节点存储的值。value被定义为void*类型，这使得链表可以存储各种类型的数据，因为void*可以指向任何类型的数据。
listIter结构体
typedef struct listIter {
listNode *next;
int direction;
} listIter;
next指针用于遍历链表，在迭代过程中指向当前要处理的下一个节点。direction表示遍历方向，它有两个取值：AL_START_HEAD（从表头开始遍历）和AL_START_TAIL（从表尾开始遍历）。
list结构体
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;
head和tail分别指向链表的头节点和尾节点，通过这两个指针可以快速定位链表的两端，方便进行插入和删除操作。len记录链表中节点的数量，这样在获取链表长度时可以直接返回该值，时间复杂度为 O(1)。dup是一个函数指针，用于复制节点的值。当需要复制链表或者在某些操作中需要复制节点数据时，会调用这个函数。free是一个函数指针，用于释放节点的值。当删除节点时，需要通过这个函数来释放节点中存储的数据所占用的内存。match是一个函数指针，用于比较节点的值和给定的键是否匹配。在查找节点等操作中会用到这个函数。
链表操作函数
Redis 提供了一系列操作链表的函数，这些函数在 adlist.c 文件中实现。下面详细介绍几个重要的操作函数。
- 创建链表
list *listCreate(void) {
struct list *list;
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
- 首先通过
zmalloc函数分配list结构体大小的内存空间。zmalloc是 Redis 自定义的内存分配函数，它在内存分配方面有一些额外的处理，例如记录内存使用情况等。 - 初始化链表的头节点
head和尾节点tail为NULL，链表长度len为 0，并且将dup、free和match函数指针初始化为NULL。
- 释放链表
void listRelease(list *list) {
unsigned long len;
listNode *current, *next;
current = list->head;
len = list->len;
while(len--) {
next = current->next;
if (list->free) list->free(current->value);
zfree(current);
current = next;
}
zfree(list);
}
- 从链表头开始遍历链表，对于每个节点，先保存后继节点指针
next。 - 如果链表定义了
free函数指针，则调用该函数释放节点的值所占用的内存。 - 然后使用
zfree释放节点本身所占用的内存。zfree是 Redis 自定义的内存释放函数。 - 最后释放链表结构体本身所占用的内存。
- 在链表头部插入节点
list *listAddNodeHead(list *list, void *value) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->head == NULL) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len++;
return list;
}
- 首先通过
zmalloc分配新节点node的内存空间。 - 如果链表为空（
list->head == NULL），则新节点既是头节点也是尾节点，将其前驱和后继指针都设为NULL。 - 如果链表不为空，将新节点的前驱指针设为
NULL，后继指针指向原头节点，同时更新原头节点的前驱指针指向新节点，最后更新链表的头节点为新节点。 - 更新链表长度
len并返回链表。
- 在链表尾部插入节点
list *listAddNodeTail(list *list, void *value) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->tail == NULL) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
node->next = NULL;
node->prev = list->tail;
list->tail->next = node;
list->tail = node;
}
list->len++;
return list;
}
- 同样先分配新节点
node的内存空间。 - 若链表为空，新节点成为头节点和尾节点，初始化其前驱和后继指针。
- 若链表不为空，新节点的后继指针设为
NULL，前驱指针指向原尾节点，更新原尾节点的后继指针指向新节点，然后更新链表的尾节点为新节点。 - 增加链表长度并返回链表。
- 删除链表节点
void listDelNode(list *list, listNode *node) {
if (node->prev)
node->prev->next = node->next;
else
list->head = node->next;
if (node->next)
node->next->prev = node->prev;
else
list->tail = node->prev;
if (list->free) list->free(node->value);
zfree(node);
list->len--;
}
- 首先处理节点的前驱和后继指针的调整。如果被删除节点有前驱节点，将前驱节点的后继指针指向被删除节点的后继节点；若无前驱节点，说明被删除节点是头节点，则更新链表的头节点为被删除节点的后继节点。
- 类似地，处理后继节点的前驱指针调整。如果被删除节点有后继节点，将后继节点的前驱指针指向被删除节点的前驱节点；若无可后继节点，说明被删除节点是尾节点，则更新链表的尾节点为被删除节点的前驱节点。
- 如果链表定义了
free函数指针，调用该函数释放节点的值所占用的内存。 - 使用
zfree释放节点本身的内存，并更新链表长度。
- 链表遍历
listIter *listGetIterator(list *list, int direction) {
listIter *iter;
if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
if (direction == AL_START_HEAD)
iter->next = list->head;
else
iter->next = list->tail;
iter->direction = direction;
return iter;
}
void listReleaseIterator(listIter *iter) {
zfree(iter);
}
void *listNext(listIter *iter) {
listNode *current = iter->next;
if (current != NULL) {
if (iter->direction == AL_START_HEAD)
iter->next = current->next;
else
iter->next = current->prev;
}
return (void*)current;
}
listGetIterator函数用于创建一个链表迭代器。根据传入的direction参数（AL_START_HEAD或AL_START_TAIL），初始化迭代器的next指针指向链表的头节点或尾节点，并设置遍历方向。listReleaseIterator函数用于释放迭代器所占用的内存。listNext函数用于获取迭代器当前指向的节点，并将迭代器移动到下一个节点。根据遍历方向的不同，更新next指针指向下一个节点。如果当前节点为NULL，则返回NULL。
链表应用场景
-
发布订阅 在 Redis 的发布订阅机制中，链表用于维护每个频道的订阅者列表。当一个消息发布到某个频道时，Redis 需要遍历该频道的订阅者链表，将消息发送给每个订阅者。这种链表结构使得在添加和删除订阅者时可以高效地进行操作，并且可以方便地遍历整个订阅者列表。
-
慢查询日志 Redis 记录慢查询日志时，使用链表来保存慢查询的记录。每次有慢查询发生时，会在链表头部插入新的记录。链表的结构便于按照时间顺序记录慢查询，并且可以方便地根据配置删除旧的慢查询记录，例如通过设置最大记录数，当链表长度超过该值时，从链表尾部删除节点。
-
监视器 在 Redis 的监视器功能中，链表用于维护所有监视器客户端的信息。当有新的监视器客户端连接时，会在链表尾部添加新的节点；当客户端断开连接时，从链表中删除相应的节点。通过遍历链表，Redis 可以将数据库的写命令发送给所有监视器客户端。
链表性能分析
-
时间复杂度
- 插入和删除操作：在链表头部或尾部插入节点的时间复杂度为 O(1)，因为只需要调整几个指针即可。删除节点时，如果已知要删除的节点指针，时间复杂度也是 O(1)，同样通过调整指针来完成。但是如果要通过值来查找节点并删除，由于需要遍历链表，时间复杂度为 O(n)，其中 n 是链表的长度。
- 查找操作：如果通过值来查找节点，由于需要遍历链表，平均时间复杂度为 O(n)。如果已知节点指针获取节点值，时间复杂度为 O(1)。
- 遍历操作：遍历链表的时间复杂度为 O(n)，因为需要依次访问每个节点。
-
空间复杂度 链表的空间复杂度主要取决于节点数量和每个节点所占用的内存空间。每个节点除了存储数据值外，还需要存储前驱和后继指针，因此空间复杂度为 O(n)，其中 n 是链表的节点数量。
总结链表在 Redis 中的特点
Redis 的链表实现具有以下特点：
- 双向链表结构：支持双向遍历，在很多场景下提高了操作的灵活性，例如在发布订阅中既可以从头遍历也可以从尾遍历订阅者列表。
- 通用数据存储：通过
void*类型的value指针，可以存储各种类型的数据，使得链表的应用场景非常广泛。 - 丰富的操作函数：提供了创建、释放、插入、删除、遍历等一系列完整的操作函数，方便开发者使用链表进行各种数据管理。
- 内存管理：使用 Redis 自定义的内存分配和释放函数（
zmalloc和zfree），有助于统一管理内存，并且可以在内存分配和释放时进行一些额外的操作，例如记录内存使用情况等。
在实际应用中，理解 Redis 链表的实现原理对于优化 Redis 的使用以及开发与 Redis 相关的应用非常有帮助。无论是在设计数据结构还是在处理数据的增删改查操作时，都可以借鉴 Redis 链表的实现思路，以提高程序的性能和可维护性。同时，在处理大量数据时，需要根据链表的性能特点合理选择操作方式，以避免出现性能瓶颈。例如，尽量避免频繁地通过值查找节点并删除的操作，因为这种操作的时间复杂度较高。如果可能，可以在插入节点时记录一些辅助信息，以便更高效地进行查找和删除操作。总之，深入理解 Redis 链表的实现原理是掌握 Redis 高级特性和优化应用性能的重要基础。