Redisリンクリストの最下層を実装する方法

基礎的な実装

#Redis のリスト データ構造の基礎的な実装は、二重リンク リストに基づいています。二重リンク リストは、一連のノードで構成される一般的なデータ構造です。各ノードは、前のノードを指すポインタ prev、次のノードを指すポインタ next、およびストレージ A ポインタを含む listNode 構造によって表されます。価値を大切にすること。 Redis の二重リンク リストはノードで構成され、各ノードは要素を表し、ポインターを介して接続されます。

二重リンクリストの利点は、先頭と末尾で挿入と削除の操作を素早く実行できることです。 Redis では、新しい要素がリストの先頭または末尾に挿入されるとき、挿入操作を完了するには、新しいノードの prev ポインターと next ポインター、および元の先頭ノードまたは末尾ノードの prev ポインターまたは next ポインターを変更するだけで済みます。 . 時間が複雑です。次数は O(1) です。同様に、要素を削除する場合、前のノードの next ポインタまたは次のノードの prev ポインタを変更するだけで削除操作が完了し、時間計算量も O(1) になります。

Redis は、二重リンク リストの使用に加えて、リスト データ構造のパフォーマンスを向上させるために他のテクノロジを使用します。たとえば、リスト内の要素の数が特定のしきい値を超えると、Redis はリストを圧縮リスト (zip リスト) に変換します。これにより、メモリ使用量が削減され、アクセス速度が向上します。 List を反復処理する場合、Redis は反復子を使用して List 内の要素を走査します。これにより、走査プロセス中に List を変更することによって発生するエラーを回避できます。

#Redis のリスト型データ構造では、リストの先頭または末尾に要素を追加または削除したり、指定した位置に要素を挿入または削除したりすることができます。 Redis の二重リンク リストの実装は、先頭ノードと末尾ノードへの高速アクセス、および指定された場所でのノードの挿入と削除をサポートしているため、これらの操作は一定時間で完了できます。

一般的な Redis リスト操作とその時間計算量を以下に示します。

• LPUSH: 先頭に要素を挿入します。複雑さは O(1) です。

• RPUSH: 要素を最後に挿入します。時間計算量は O(1) です。

• LPOP: ヘッダー要素を削除します。時間計算量は O(1) です。

• RPOP: 末尾の要素を削除します。時間計算量は O(1) です。

• LINDEX: 指定された位置にある要素にアクセスします。時間計算量は O(n) です。

• LINSERT: 指定された位置に要素を挿入します。時間計算量は O(n) です。

• LREM: 指定された要素を削除します。時間計算量は O(n) です。

ソース コードの実装

Redis List データ構造の基礎となるコードは、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 リストのデータ構造は、本番環境で多くの素晴らしい用途があります:

• メッセージ キュー: Redis リストを使用できます。プロデューサはメッセージを List にプッシュし、コンシューマはメッセージを取得して、blpop や brpop などのコマンドを通じてブロック的に処理することで、単純なメッセージ キューを実現します。

• ランキング リスト: Redis リストのプッシュ操作とポップ操作は両方とも O(1) の時間計算量を持っています。ユーザーのスコアはリストに値として保存され、その後、 lrangeコマンド. ランキング一覧。

• 最近の連絡先リスト: ユーザーの最近の連絡先の ID をリストに保存でき、ユーザーが連絡先と対話するたびに、連絡先の ID がリストの先頭に移動されます。これにより、ユーザーの最近の連絡先リストを lrange コマンドを通じて取得できるようになります。

• ページング クエリ: データを List に保存し、lrange コマンドを使用してページング クエリを実行できます。

• スロー ログ: Redis は、実行時間が特定のしきい値を超えたコマンドを記録し、そのコマンドの情報を List に保存し、lrange コマンドを通じてスロー ログ情報を取得できます。

• チャット ルーム: チャット ルームのメッセージをリストに保存できます。新しいメッセージがあるたびにリストにプッシュし、lrange を通じて最新のメッセージを取得します。指示。

• タスク キュー: 実行する必要があるタスクをリストに保存し、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リンクリストの最下層を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。