Redis連結串列底層實現及生產實戰

2023-03-25 06:03:33

底層實現

Redis的list資料結構底層實現是基於雙向連結串列實現的。雙向連結串列是一種常見的資料結構，它由一系列節點組成，每個節點都由一個listNode結構表示，其中包含了一個指向前一個節點的指標prev、一個指向後一個節點的指標next和一個儲存值的指標value。在Redis中，每個節點代表一個元素，節點之間通過指標連線起來，形成一個雙向連結串列。

雙向連結串列的好處是可以快速地在頭部和尾部進行插入和刪除操作。在Redis中，當一個新的元素被插入到List的頭部或者尾部時，只需要修改新節點的prev和next指標以及原來頭部或尾部節點的prev或next指標即可完成插入操作，時間複雜度為O(1)。同樣的，當一個元素被刪除時，只需要修改前一個節點的next指標或者後一個節點的prev指標即可完成刪除操作，時間複雜度也為O(1)。

除了雙向連結串列，Redis還使用了一些其他的技術來優化List資料結構的效能。例如，當List中的元素數量超過一定閾值時，Redis會將List轉換為壓縮列表（zip list），這樣可以減少記憶體的使用和提高存取速度。在對List進行迭代操作時，Redis使用了迭代器（iterator）來遍歷List中的元素，這樣可以避免在遍歷過程中對List進行修改而導致的錯誤。

Redis的list資料結構支援在頭部或尾部插入或刪除元素，以及在指定位置插入或刪除元素。這些操作都可以在常數時間內完成，因為Redis的雙向連結串列實現支援快速存取頭部和尾部節點，以及在指定位置插入和刪除節點。

下面是一些常見的Redis list操作及其時間複雜度：

LPUSH：在頭部插入元素，時間複雜度為O(1)。
RPUSH：在尾部插入元素，時間複雜度為O(1)。
LPOP：刪除頭部元素，時間複雜度為O(1)。
RPOP：刪除尾部元素，時間複雜度為O(1)。
LINDEX：存取指定位置的元素，時間複雜度為O(n)。
LINSERT：在指定位置插入元素，時間複雜度為O(n)。
LREM：刪除指定元素，時間複雜度為O(n)。

以上圖片轉載至黃建宏的《Redis設計與實戰》pdf。

原始碼實現

Redis List資料結構的底層程式碼實現demo，使用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--;
}

以上程式碼實現了List資料結構的基本操作，包括建立List、釋放List、在頭部和尾部插入元素以及刪除元素。這些操作的時間複雜度都為O(1)。

生產實戰妙用

Redis List 資料結構在生產環境中有很多妙用：

訊息佇列：Redis List 可以用作訊息佇列，生產者將訊息 push 到 List 中，消費者通過 blpop、brpop 等命令阻塞式地獲取訊息並進行處理，從而實現了簡單的訊息佇列。
排行榜：Redis List 的 push 和 pop 操作都是 O(1) 的時間複雜度，可以將使用者的分數作為值儲存在 List 中，然後通過 lrange 命令獲取排行榜。
最近聯絡人列表：可以將使用者最近聯絡人的 ID 儲存在 List 中，每當使用者與某個聯絡人進行互動時，將該聯絡人的 ID 移動到 List 的頭部，這樣就可以通過 lrange 命令獲取使用者最近聯絡人列表。
分頁查詢：可以將資料儲存在 List 中，然後使用 lrange 命令進行分頁查詢。
慢紀錄檔：Redis 可以記錄執行時間超過一定閾值的命令，將這些命令的資訊儲存在 List 中，通過 lrange 命令獲取慢紀錄檔資訊。
聊天室：可以將聊天室中的訊息儲存在 List 中，每當有新訊息時，將其 push 到 List 中，然後通過 lrange 命令獲取最新的訊息。
任務佇列：可以將需要執行的任務儲存在 List 中，然後通過 lpop 命令獲取任務並執行。
實時資料統計：可以將實時資料儲存在 List 中，然後通過 lrange 命令獲取一定時間範圍內的資料，並進行統計分析。
佇列延遲處理：可以將需要延遲處理的任務儲存在 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 資料結構實現聊天室的思路，實際專案中需要更周全的設計以及考慮。

總結

Redis List 資料結構的應用場景非常廣泛，可以根據不同的需求進行靈活應用。

到此這篇關於Redis連結串列底層實現及生產實戰的文章就介紹到這了,更多相關Redis連結串列底層實現內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！