服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

Mysql|Sql Server|Oracle|Redis|MongoDB|PostgreSQL|Sqlite|DB2|mariadb|Access|数据库技术|

服务器之家 - 数据库 - Redis - Redis链表底层实现及生产实战

Redis链表底层实现及生产实战

2023-03-27 13:47德哥很ok Redis

Redis 的 List 是一个双向链表，链表中的每个节点都包含了一个字符串。是redis中最常用的数据结构之一，本文主要介绍了Redis链表底层实现及生产实战，文中通过示例代码介绍的非常详细，需要的朋友们下面随着小编来一起学习学习

Redis 的 List 是一个双向链表，链表中的每个节点都包含了一个字符串。是redis中最常用的数据结构之一，下面跟大家分享下redis链表的底层实现以及生产实战。

底层实现

Redis链表底层实现及生产实战

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链表底层实现及生产实战

Redis的list数据结构支持在头部或尾部插入或删除元素，以及在指定位置插入或删除元素。这些操作都可以在常数时间内完成，因为Redis的双向链表实现支持快速访问头部和尾部节点，以及在指定位置插入和删除节点。

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链表底层实现及生产实战

以上图片转载至黄建宏的《Redis设计与实战》pdf。

源码实现

Redis List数据结构的底层代码实现demo，使用C语言实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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 代码示例：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 出来，使用该类可以方便地实现消息队列功能。

使用方法如下：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 聊天室示例

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 命令获取聊天列表中的所有消息，并输出到控制台中。

使用方法如下：

?
1
2
3
4
5
6
7
8
9
10
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链表底层实现内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://juejin.cn/post/7213307113111633979

  • redis
  • 链表

    • 延伸 · 阅读

    精彩推荐
    • Redis关于SpringBoot 使用 Redis 分布式锁解决并发问题

      关于SpringBoot 使用 Redis 分布式锁解决并发问题

      针对上面问题，一般的解决方案是使用分布式锁来解决，本文通过场景分析给大家介绍关于SpringBoot 使用 Redis 分布式锁解决并发问题，感兴趣的朋友一起看...

      qhh02058222021-11-24
    • Redis一文搞懂Redis中String数据类型

      一文搞懂Redis中String数据类型

      string 是 redis 最基本的类型，你可以理解成与 Memcached 一模一样的类型，一个 key 对应一个 value。今天通过本文给大家介绍下Redis中String数据类型，感兴趣的...

      毕竟尹稳健6972022-10-13
    • Redis基于redis+lua进行限流的方法

      基于redis+lua进行限流的方法

      这篇文章主要介绍了基于redis+lua进行限流,通过实例代码详细介绍了lua+redis进行限流的做法，开发环境使用idea+redis+lua，本文给大家介绍的非常详细，需要的...

      枯枫叶10592022-07-24
    • RedisRedis入门教程_动力节点Java学院整理

      Redis入门教程_动力节点Java学院整理

      Redis是一款开源的、高性能的键-值存储（key-value store）。下面通过本文大家分享Redis入门教程，感兴趣的朋友参考下吧 ...

      Redis教程网4732019-11-07
    • RedisRedis主从实现读写分离

      Redis主从实现读写分离

      这篇文章主要为大家详细介绍了Redis主从实现读写分离的相关资料 ,具有一定的参考价值，感兴趣的小伙伴们可以参考一下 ...

      KeySilenceM4602019-10-31
    • Redis12 个问题搞懂 Redis

      12 个问题搞懂 Redis

      随着硬件性能的提升，Redis 的性能瓶颈有时会出现在网络 IO 的处理上，也就是说，单个主线程处理网络请求的速度跟不上底层网络硬件的速度，而读写的操...

      不止dotNET8022021-09-14
    • Redis详解使用Redis SETNX 命令实现分布式锁

      详解使用Redis SETNX 命令实现分布式锁

      本篇文章主要介绍了详解使用Redis SETNX 命令实现分布式锁，小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧 ...

      haozlee6142019-11-04
    • RedisRedis字符串原理的深入理解

      Redis字符串原理的深入理解

      这篇文章主要给大家介绍了关于Redis字符串原理的相关资料，文中通过示例代码介绍的非常详细，对大家学习或者使用Redis具有一定的参考学习价值，需要的...

      YangSir3152019-11-24
    最近更新
    编辑推荐
    阅读排行
    热门标签
    16384 　 批量提权 　 intset 　 节点迁移 　 事务机制 　 主从同步 　 十六进制 　 内部数据结构 　 Redis集群 　 Redis集群搭建 　 持久化方案 　 AOF 　 ziplist 　 限流器 　 内存型数据库 　 RDB 　 简介 　 Big 　 批量读写 　 密码认证 　 redis命令 　 未授权 　 访问漏洞 　 redislive 　 发布 　 集合类型 　 列表类型 　 快照模式 　 集群搭建 　 键 　
    © 2019-2023 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图