How to implement the bottom layer of Redis linked list

Underlying implementation

#The underlying implementation of Redis's list data structure is based on a doubly linked list. A doubly linked list is a common data structure that consists of a series of nodes. Each node is represented by a listNode structure, which contains a pointer prev pointing to the previous node, a pointer next pointing to the next node and a storage A pointer to value value. The doubly linked list in Redis is composed of nodes, each node represents an element and is connected through pointers.

The advantage of a doubly linked list is that insertion and deletion operations can be performed quickly at the head and tail. In Redis, when a new element is inserted into the head or tail of the List, you only need to modify the prev and next pointers of the new node and the prev or next pointer of the original head or tail node to complete the insertion operation. The time is complicated. The degree is O(1). Similarly, when an element is deleted, you only need to modify the next pointer of the previous node or the prev pointer of the next node to complete the deletion operation, and the time complexity is also O(1).

Redis uses other technologies to improve the performance of the List data structure, in addition to using doubly linked lists. For example, when the number of elements in the List exceeds a certain threshold, Redis will convert the List into a compressed list (zip list), which can reduce memory usage and increase access speed. When iterating over a List, Redis uses an iterator to traverse the elements in the List, which can avoid errors caused by modifying the List during the traversal process.

#Redis' list type data structure allows adding or removing elements at the beginning or end of the list, and inserting or deleting elements at specified positions. These operations can be completed in constant time because Redis's doubly linked list implementation supports fast access to head and tail nodes, as well as insertion and deletion of nodes at specified locations.

The following are some common Redis list operations and their time complexity:

• LPUSH: insert elements at the head, time The complexity is O(1).

• RPUSH: Insert elements at the end, the time complexity is O(1).

• LPOP: Delete the header element, the time complexity is O(1).

• RPOP: Delete the tail elements, the time complexity is O(1).

• LINDEX: Access the element at the specified position, the time complexity is O(n).

• LINSERT: Insert an element at the specified position, the time complexity is O(n).

• LREM: Delete the specified element, the time complexity is O(n).

Source code implementation

The underlying code of the Redis List data structure implements demo, using C language:

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

typedef struct list {
    listNode *head;
    listNode *tail;
    unsigned long len;
} list;

list *listCreate(void) {
    list *l;

    if ((l = malloc(sizeof(*l))) == NULL) return NULL;
    l->head = l->tail = NULL;
    l->len = 0;
    return l;
}

void listRelease(list *list) {
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        free(current);
        current = next;
    }
    free(list);
}

listNode *listAddNodeHead(list *list, void *value) {
    listNode *node;

    if ((node = malloc(sizeof(*node))) == NULL) return NULL;
    node->value = value;
    if (list->len == 0) {
        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 node;
}

listNode *listAddNodeTail(list *list, void *value) {
    listNode *node;

    if ((node = malloc(sizeof(*node))) == NULL) return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return node;
}

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;
    free(node);
    list->len--;
}

The above code implements the basic operations of the List data structure, including creating List, releasing List, inserting elements at the head and tail, and deleting elements. The time complexity of these operations is O(1).

Practical Uses in Production

The Redis List data structure has many wonderful uses in the production environment:

• Message Queue: Redis List can be used as a message queue, The producer pushes the message into the List, and the consumer obtains the message and processes it blockingly through commands such as blpop and brpop, thus realizing a simple message queue.

• Ranking list: The push and pop operations of Redis List both have time complexity of O(1). The user's score can be stored in the List as a value and then obtained through the lrange command. Ranking list.

• Recent Contact List: The ID of the user's recent contacts can be stored in the List, and whenever the user interacts with a contact, the ID of the contact is moved to The head of the List, so that the user's recent contact list can be obtained through the lrange command.

• Paging query: You can store the data in List, and then use the lrange command to perform paging query.

• Slow log: Redis can record commands whose execution time exceeds a certain threshold, store the information of these commands in List, and obtain slow log information through the lrange command.

• Chat room: You can store the messages in the chat room in a List. Whenever there is a new message, push it to the List, and then get the latest message through the lrange command.

• Task queue: You can store the tasks that need to be executed in a List, and then obtain the tasks through the lpop command and execute them.

• Real-time data statistics: You can store real-time data in List, and then use the lrange command to obtain data within a certain time range and perform statistical analysis.

• 队列延迟处理：可以将需要延迟处理的任务存储在 List 中，同时将任务的执行时间作为 score 存储在 Sorted Set 中，然后使用 Redis 的定时任务功能，每隔一段时间就将 Sorted Set 中过期的任务移动到 List 中，然后通过 lpop 命令获取任务并执行。

• 日志收集：可以将应用程序的日志信息存储在 List 中，然后通过 lrange 命令获取日志信息进行分析和处理。

实战实例

基于 Redis List 数据结构实现消息队列的 Java 代码示例：

import redis.clients.jedis.Jedis;

public class RedisMessageQueue {
    private Jedis jedis;
    private String queueKey;

    public RedisMessageQueue(Jedis jedis, String queueKey) {
        this.jedis = jedis;
        this.queueKey = queueKey;
    }

    public void enqueue(String message) {
        jedis.rpush(queueKey, message);
    }

    public String dequeue() {
        return jedis.lpop(queueKey);
    }
}

示例中，定义了一个 RedisMessageQueue 类，包含一个 Jedis 对象和一个队列键名 queueKey。enqueue 方法用于将消息 push 到队列中，dequeue 方法用于从队列中获取消息并将其 pop 出来，使用该类可以方便地实现消息队列功能。

使用方法如下：

import redis.clients.jedis.Jedis;

public class TestRedisMessageQueue {
    public static void main(String[] args) {
        Jedis jedis = new Jedis("localhost");
        RedisMessageQueue queue = new RedisMessageQueue(jedis, "myqueue");

        // 生产者向队列中添加消息
        queue.enqueue("Hello, Redis!");
        queue.enqueue("How are you?");

        // 消费者从队列中获取消息
        String message = queue.dequeue();
        while (message != null) {
            System.out.println("Received message: " + message);
            message = queue.dequeue();
        }
    }
}

我已经构建了一个 RedisMessageQueue 实例，并向队列中添加了两条信息。接着，调用 dequeue 方法从队列中取出消息，并将其输出到控制台。

该示例代码仅为演示 Redis List 数据结构实现消息队列的思路，实际生产环境中需要考虑更多的细节问题，例如如何处理消息重复、如何保证消息的可靠性等等。

Redis 聊天室示例

import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPubSub;

import java.util.Scanner;

public class RedisChatRoom {
    private Jedis jedis;
    private String channel;
    private String chatListKey;

    public RedisChatRoom(Jedis jedis, String channel, String chatListKey) {
        this.jedis = jedis;
        this.channel = channel;
        this.chatListKey = chatListKey;
    }

    public void start() {
        // 订阅 Redis 频道
        jedis.subscribe(new JedisPubSub() {
            @Override
            public void onMessage(String channel, String message) {
                System.out.println("Received message: " + message);
                // 将消息添加到聊天列表中
                jedis.rpush(chatListKey, message);
            }
        }, channel);

        // 发布消息到 Redis 频道
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.print("Enter message: ");
            String message = scanner.nextLine();
            jedis.publish(channel, message);
        }
    }

    public void printChatList() {
        // 获取聊天列表中的所有消息并输出到控制台
        System.out.println("Chat list:");
        for (String message : jedis.lrange(chatListKey, 0, -1)) {
            System.out.println(message);
        }
    }
}

示例中，RedisChatRoom 类中添加了一个聊天列表 chatListKey，用于存储聊天室中的所有消息。在订阅 Redis 频道时，通过 JedisPubSub 的 onMessage 方法将收到的消息添加到聊天列表中。在 printChatList 方法中，通过 lrange 命令获取聊天列表中的所有消息，并输出到控制台中。

使用方法如下：

import redis.clients.jedis.Jedis;

public class TestRedisChatRoom {
    public static void main(String[] args) {
        Jedis jedis = new Jedis("localhost");
        RedisChatRoom chatRoom = new RedisChatRoom(jedis, "mychannel", "mychatlist");
        chatRoom.start();
        chatRoom.printChatList();
    }
}

创建了一个 RedisChatRoom 对象，并指定了频道名为 mychannel 和聊天列表键名为 mychatlist。执行 start 方法即可开始 Redis 频道的订阅并发布消息。在最后一步中，使用 printChatList 方法从聊天列表中获取所有消息并输出到控制台上。

该示例仅仅简单演示 Redis List 数据结构实现聊天室的思路，实际项目中需要更周全的设计以及考虑。

The above is the detailed content of How to implement the bottom layer of Redis linked list. For more information, please follow other related articles on the PHP Chinese website!