So implementieren Sie die unterste Ebene der Redis-verknüpften Liste

Zugrunde liegende Implementierung

Die zugrunde liegende Implementierung der Listendatenstruktur von Redis basiert auf einer doppelt verknüpften Liste. Eine doppelt verknüpfte Liste ist eine gemeinsame Datenstruktur, die aus einer Reihe von Knoten besteht. Jeder Knoten wird durch eine listNode-Struktur dargestellt, die einen Zeiger prev, der auf den vorherigen Knoten zeigt, einen Zeiger next, der auf den nächsten Knoten zeigt, und einen Speicher-A-Zeiger enthält Wert schätzen. Die doppelt verknüpfte Liste in Redis besteht aus Knoten. Jeder Knoten stellt ein Element dar und ist durch Zeiger verbunden.

Der Vorteil einer doppelt verknüpften Liste besteht darin, dass Einfüge- und Löschvorgänge am Kopf und am Ende schnell ausgeführt werden können. Wenn in Redis ein neues Element in den Kopf oder das Ende der Liste eingefügt wird, müssen Sie nur die vorherigen und nächsten Zeiger des neuen Knotens und den vorherigen oder nächsten Zeiger des ursprünglichen Kopf- oder Endknotens ändern, um den Einfügevorgang abzuschließen . Die Zeit ist kompliziert. Wenn ein Element gelöscht wird, müssen Sie nur den nächsten Zeiger des vorherigen Knotens oder den vorherigen Zeiger des nächsten Knotens ändern, um den Löschvorgang abzuschließen. Die zeitliche Komplexität beträgt ebenfalls O (1).

Redis verwendet neben der Verwendung doppelt verknüpfter Listen auch andere Techniken, um die Leistung der Listendatenstruktur zu verbessern. Wenn beispielsweise die Anzahl der Elemente in der Liste einen bestimmten Schwellenwert überschreitet, konvertiert Redis die Liste in eine komprimierte Liste (Zip-Liste), was die Speichernutzung reduzieren und die Zugriffsgeschwindigkeit erhöhen kann. Beim Durchlaufen einer Liste verwendet Redis einen Iterator, um die Elemente in der Liste zu durchlaufen, wodurch Fehler vermieden werden können, die durch die Änderung der Liste während des Durchlaufvorgangs verursacht werden.

Die Listentyp-Datenstruktur von Redis ermöglicht das Hinzufügen oder Entfernen von Elementen am Anfang oder Ende der Liste sowie das Einfügen oder Löschen von Elementen an angegebenen Positionen. Diese Vorgänge können in konstanter Zeit abgeschlossen werden, da die doppelt verknüpfte Listenimplementierung von Redis einen schnellen Zugriff auf Kopf- und Endknoten sowie das Einfügen und Löschen von Knoten an bestimmten Standorten unterstützt.

Im Folgenden sind einige gängige Redis-Listenoperationen und ihre zeitliche Komplexität aufgeführt:

• LPUSH : Elemente am Kopf einfügen, die zeitliche Komplexität beträgt O(1).

• RPUSH: Elemente am Ende einfügen, die zeitliche Komplexität ist O(1).

• LPOP: Löschen Sie das Header-Element, die Zeitkomplexität ist O(1).

• RPOP: Löschen Sie die Schwanzelemente, die Zeitkomplexität ist O(1).

• LINDEX: Greifen Sie auf das Element an der angegebenen Position zu, die zeitliche Komplexität beträgt O(n).

• LINSERT: Fügen Sie ein Element an der angegebenen Position ein. Die zeitliche Komplexität beträgt O (n).

• LREM: Löschen Sie das angegebene Element, die zeitliche Komplexität beträgt O(n).

Quellcode-Implementierung

Der zugrunde liegende Code der Redis-Listen-Datenstruktur implementiert die Demo mit C-Sprachimplementierung:

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

Der obige Code implementiert die Grundoperationen der Listendatenstruktur, einschließlich der Erstellung einer Liste, der Freigabe einer Liste, dem Einfügen von Elementen am Kopf und am Ende sowie dem Löschen von Elementen. Die zeitliche Komplexität dieser Operationen beträgt O(1).

Praktische Verwendung in der Produktion

Die Redis-List-Datenstruktur hat viele wunderbare Verwendungsmöglichkeiten in der Produktionsumgebung:

• Nachricht Warteschlange: Redis List kann als Nachrichtenwarteschlange verwendet werden. Der Produzent schiebt Nachrichten an die Liste, und der Verbraucher erhält die Nachrichten und verarbeitet sie blockierend über Befehle wie blpop und brpop, wodurch eine einfache Nachrichtenwarteschlange realisiert wird.

• Rangliste: Die Push- und Pop-Operationen von Redis List haben eine Zeitkomplexität von O(1). Die Punktzahl des Benutzers kann als Wert in der Liste gespeichert werden. und rufen Sie dann die Rangliste mit dem Befehl lrange ab.

• Liste der letzten Kontakte: Die IDs der letzten Kontakte des Benutzers können in der Liste gespeichert werden, und wann immer der Benutzer mit einem Kontakt interagiert, wird die ID des Kontakts verschoben Der Kopf der Liste, sodass die aktuelle Kontaktliste des Benutzers über den Befehl lrange abgerufen werden kann.

• Paging-Abfrage: Sie können die Daten in einer Liste speichern und dann den Befehl lrange verwenden, um eine Paging-Abfrage durchzuführen.

• Langsames Protokoll: Redis kann Befehle aufzeichnen, deren Ausführungszeit einen bestimmten Schwellenwert überschreitet, die Informationen dieser Befehle in der Liste speichern und über den Befehl lrange langsame Protokollinformationen abrufen.

• Chatraum: Sie können die Nachrichten im Chatraum in der Liste speichern, sie in die Liste verschieben und sie dann über abrufen lrange-Befehl Neueste Nachrichten.

• Aufgabenwarteschlange: Sie können die auszuführenden Aufgaben in einer Liste speichern und die Aufgaben dann über den Befehl lpop abrufen und ausführen.

• Echtzeitdatenstatistik: Sie können Echtzeitdaten in der Liste speichern und dann den Befehl lrange verwenden, um Daten innerhalb eines bestimmten Zeitbereichs abzurufen und statistische Analysen durchzuführen .

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die unterste Ebene der Redis-verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!