Comment implémenter la couche inférieure de la liste chaînée Redis

Implémentation sous-jacente

L'implémentation sous-jacente de la structure de données de liste de Redis est basée sur une liste doublement chaînée. Une liste doublement chaînée est une structure de données commune composée d'une série de nœuds. Chaque nœud est représenté par une structure listNode, qui contient un pointeur prev pointant vers le nœud précédent, un pointeur next pointant vers le nœud suivant et un pointeur de stockage A. pour valoriser la valeur. La liste doublement chaînée dans Redis est composée de nœuds, chaque nœud représente un élément et est connecté via des pointeurs.

L'avantage d'une liste doublement chaînée est que les opérations d'insertion et de suppression peuvent être effectuées rapidement en tête et en queue. Dans Redis, lorsqu'un nouvel élément est inséré dans la tête ou la queue de la liste, il vous suffit de modifier les pointeurs précédent et suivant du nouveau nœud et le pointeur précédent ou suivant du nœud de tête ou de queue d'origine pour terminer l'opération d'insertion. . Le temps est compliqué. Le degré est O(1). De même, lorsqu'un élément est supprimé, il vous suffit de modifier le pointeur suivant du nœud précédent ou le pointeur précédent du nœud suivant pour terminer l'opération de suppression, et la complexité temporelle est également O(1).

Redis utilise d'autres techniques pour améliorer les performances de la structure de données List, en plus d'utiliser des listes doublement chaînées. Par exemple, lorsque le nombre d'éléments dans la liste dépasse un certain seuil, Redis convertira la liste en une liste compressée (liste zip), ce qui peut réduire l'utilisation de la mémoire et augmenter la vitesse d'accès. Lors d'une itération sur une liste, Redis utilise un itérateur pour parcourir les éléments de la liste, ce qui peut éviter les erreurs causées par la modification de la liste pendant le processus de parcours. La structure de données de type liste de

Redis permet d'ajouter ou de supprimer des éléments au début ou à la fin de la liste, et d'insérer ou de supprimer des éléments à une position spécifiée. Ces opérations peuvent être effectuées en temps constant car l'implémentation de liste doublement chaînée de Redis prend en charge un accès rapide aux nœuds de tête et de queue, ainsi que l'insertion et la suppression de nœuds à des emplacements spécifiés.

Voici quelques opérations de liste Redis courantes et leur complexité temporelle :

• LPUSH : Insérez des éléments en tête, la complexité temporelle est O(1).

• RPUSH : Insérez des éléments à la queue, la complexité temporelle est O(1).

• LPOP : Supprimez l'élément d'en-tête, la complexité temporelle est O(1).

• RPOP : Supprimez les éléments de queue, la complexité temporelle est O(1).

• LINDEX : Accédez à l'élément à la position spécifiée, la complexité temporelle est O(n).

• LINSERT : Insérez un élément à la position spécifiée, la complexité temporelle est O(n).

• LREM : Supprimez l'élément spécifié, la complexité temporelle est O(n).

Implémentation du code source

Le code sous-jacent de la structure de données Redis List implémente la démo, en utilisant le langage C :

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--;
}

Le code ci-dessus implémente les opérations de base de la structure de données List, y compris la création d'une liste, la publication Liste et ajout de données à l'insertion et à la suppression d'éléments d'en-tête et de queue. La complexité temporelle de ces opérations est O(1).

Utilisations pratiques en production

La structure de données Redis List a de nombreuses utilisations merveilleuses dans l'environnement de production :

• File d'attente de messages : Redis List peut être utilisée comme file d'attente de messages. Les producteurs envoient des messages à la liste et les consommateurs utilisent blpop. , brpop, etc. La commande obtient des messages et les traite de manière bloquante, implémentant ainsi une simple file d'attente de messages.

• Liste principale : les opérations push et pop de Redis List ont toutes deux une complexité temporelle O(1). Vous pouvez stocker le score de l'utilisateur en tant que valeur dans la liste, puis obtenir la liste de classement via la commande lrange.

• Liste de contacts récents : l'ID des contacts récents de l'utilisateur peut être stocké dans la liste Chaque fois que l'utilisateur interagit avec un contact, l'ID du contact est déplacé en tête de la liste, afin d'obtenir les informations récentes de l'utilisateur. liste de contacts via la commande lrange.

• Requête de pagination : vous pouvez stocker des données dans une liste, puis utiliser la commande lrange pour effectuer une requête de pagination.

• Journal lent : Redis peut enregistrer les commandes dont le temps d'exécution dépasse un certain seuil, stocker les informations de ces commandes dans List et obtenir des informations de journal lent via la commande lrange.

• Salle de discussion : vous pouvez stocker les messages de la salle de discussion dans la liste. Chaque fois qu'il y a un nouveau message, transférez-le dans la liste, puis obtenez le dernier message via la commande lrange.

• File d'attente des tâches : vous pouvez stocker les tâches qui doivent être exécutées dans une liste, puis obtenir les tâches via la commande lpop et les exécuter.

• Statistiques de données en temps réel : vous pouvez stocker des données en temps réel dans List, puis utiliser la commande lrange pour obtenir des données dans une certaine plage de temps et effectuer une analyse statistique.

• 队列延迟处理：可以将需要延迟处理的任务存储在 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 数据结构实现聊天室的思路，实际项目中需要更周全的设计以及考虑。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!