快捷導(dǎo)航

Redis鏈表底層實現(xiàn)及生產(chǎn)實戰(zhàn)

更新時間：2023年03月24日 09:56:22 作者：德哥很ok

Redis 的 List 是一個雙向鏈表，鏈表中的每個節(jié)點(diǎn)都包含了一個字符串。是redis中最常用的數(shù)據(jù)結(jié)構(gòu)之一，本文主要介紹了Redis鏈表底層實現(xiàn)及生產(chǎn)實戰(zhàn)，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

底層實現(xiàn)

Redis的list數(shù)據(jù)結(jié)構(gòu)底層實現(xiàn)是基于雙向鏈表實現(xiàn)的。雙向鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個節(jié)點(diǎn)都由一個listNode結(jié)構(gòu)表示，其中包含了一個指向前一個節(jié)點(diǎn)的指針prev、一個指向后一個節(jié)點(diǎn)的指針next和一個存儲值的指針value。在Redis中，每個節(jié)點(diǎn)代表一個元素，節(jié)點(diǎn)之間通過指針連接起來，形成一個雙向鏈表。

雙向鏈表的好處是可以快速地在頭部和尾部進(jìn)行插入和刪除操作。在Redis中，當(dāng)一個新的元素被插入到List的頭部或者尾部時，只需要修改新節(jié)點(diǎn)的prev和next指針以及原來頭部或尾部節(jié)點(diǎn)的prev或next指針即可完成插入操作，時間復(fù)雜度為O(1)。同樣的，當(dāng)一個元素被刪除時，只需要修改前一個節(jié)點(diǎn)的next指針或者后一個節(jié)點(diǎn)的prev指針即可完成刪除操作，時間復(fù)雜度也為O(1)。

除了雙向鏈表，Redis還使用了一些其他的技術(shù)來優(yōu)化List數(shù)據(jù)結(jié)構(gòu)的性能。例如，當(dāng)List中的元素數(shù)量超過一定閾值時，Redis會將List轉(zhuǎn)換為壓縮列表（zip list），這樣可以減少內(nèi)存的使用和提高訪問速度。在對List進(jìn)行迭代操作時，Redis使用了迭代器（iterator）來遍歷List中的元素，這樣可以避免在遍歷過程中對List進(jìn)行修改而導(dǎo)致的錯誤。

Redis的list數(shù)據(jù)結(jié)構(gòu)支持在頭部或尾部插入或刪除元素，以及在指定位置插入或刪除元素。這些操作都可以在常數(shù)時間內(nèi)完成，因為Redis的雙向鏈表實現(xiàn)支持快速訪問頭部和尾部節(jié)點(diǎn)，以及在指定位置插入和刪除節(jié)點(diǎn)。

下面是一些常見的Redis list操作及其時間復(fù)雜度：

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

以上圖片轉(zhuǎn)載至黃建宏的《Redis設(shè)計與實戰(zhàn)》pdf。

源碼實現(xiàn)

Redis List數(shù)據(jù)結(jié)構(gòu)的底層代碼實現(xiàn)demo，使用C語言實現(xiàn)：

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

以上代碼實現(xiàn)了List數(shù)據(jù)結(jié)構(gòu)的基本操作，包括創(chuàng)建List、釋放List、在頭部和尾部插入元素以及刪除元素。這些操作的時間復(fù)雜度都為O(1)。

生產(chǎn)實戰(zhàn)妙用

Redis List 數(shù)據(jù)結(jié)構(gòu)在生產(chǎn)環(huán)境中有很多妙用：

消息隊列：Redis List 可以用作消息隊列，生產(chǎn)者將消息 push 到 List 中，消費(fèi)者通過 blpop、brpop 等命令阻塞式地獲取消息并進(jìn)行處理，從而實現(xiàn)了簡單的消息隊列。
排行榜：Redis List 的 push 和 pop 操作都是 O(1) 的時間復(fù)雜度，可以將用戶的分?jǐn)?shù)作為值存儲在 List 中，然后通過 lrange 命令獲取排行榜。
最近聯(lián)系人列表：可以將用戶最近聯(lián)系人的 ID 存儲在 List 中，每當(dāng)用戶與某個聯(lián)系人進(jìn)行交互時，將該聯(lián)系人的 ID 移動到 List 的頭部，這樣就可以通過 lrange 命令獲取用戶最近聯(lián)系人列表。
分頁查詢：可以將數(shù)據(jù)存儲在 List 中，然后使用 lrange 命令進(jìn)行分頁查詢。
慢日志：Redis 可以記錄執(zhí)行時間超過一定閾值的命令，將這些命令的信息存儲在 List 中，通過 lrange 命令獲取慢日志信息。
聊天室：可以將聊天室中的消息存儲在 List 中，每當(dāng)有新消息時，將其 push 到 List 中，然后通過 lrange 命令獲取最新的消息。
任務(wù)隊列：可以將需要執(zhí)行的任務(wù)存儲在 List 中，然后通過 lpop 命令獲取任務(wù)并執(zhí)行。
實時數(shù)據(jù)統(tǒng)計：可以將實時數(shù)據(jù)存儲在 List 中，然后通過 lrange 命令獲取一定時間范圍內(nèi)的數(shù)據(jù)，并進(jìn)行統(tǒng)計分析。
隊列延遲處理：可以將需要延遲處理的任務(wù)存儲在 List 中，同時將任務(wù)的執(zhí)行時間作為 score 存儲在 Sorted Set 中，然后使用 Redis 的定時任務(wù)功能，每隔一段時間就將 Sorted Set 中過期的任務(wù)移動到 List 中，然后通過 lpop 命令獲取任務(wù)并執(zhí)行。
日志收集：可以將應(yīng)用程序的日志信息存儲在 List 中，然后通過 lrange 命令獲取日志信息進(jìn)行分析和處理。

實戰(zhàn)實例

基于 Redis List 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)消息隊列的 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 出來，使用該類可以方便地實現(xiàn)消息隊列功能。

使用方法如下：

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");

        // 生產(chǎn)者向隊列中添加消息
        queue.enqueue("Hello, Redis!");
        queue.enqueue("How are you?");

        // 消費(fèi)者從隊列中獲取消息
        String message = queue.dequeue();
        while (message != null) {
            System.out.println("Received message: " + message);
            message = queue.dequeue();
        }
    }
}

創(chuàng)建了一個 RedisMessageQueue 對象，并向隊列中添加了兩條消息。然后使用 dequeue 方法從隊列中獲取消息，并輸出到控制臺中。

該示例代碼僅為演示 Redis List 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)消息隊列的思路，實際生產(chǎn)環(huán)境中需要考慮更多的細(xì)節(jié)問題，例如如何處理消息重復(fù)、如何保證消息的可靠性等等。

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

        // 發(fā)布消息到 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();
    }
}

創(chuàng)建了一個 RedisChatRoom 對象，并指定了頻道名為 mychannel 和聊天列表鍵名為 mychatlist。然后調(diào)用 start 方法，開始訂閱 Redis 頻道并發(fā)布消息。最后調(diào)用 printChatList 方法，獲取聊天列表中的所有消息并輸出到控制臺中。

該示例僅僅簡單演示 Redis List 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)聊天室的思路，實際項目中需要更周全的設(shè)計以及考慮。