专栏首页Redis源码学习系列Redis源码学习之列表对象
原创

Redis源码学习之列表对象

列表对象的底层实现可以是【压缩列表】或者【双端链表】,Redis会通过用户对于压缩列表单个节点值长度(list_max_ziplist_value)和键值对个数(list_max_ziplist_entries)的配置进行选择。

一.压缩列表编码

当Redis创建列表对象时,默认选择的实现方式是压缩列表结构,如push操作的底层实现方法:

可以看到lobj通过createZiplistObject方法创建一个指向空压缩列表的对象:

当我们执行命令:

127.0.0.1:6379> lpush test x

在createZiplistObject方法后打印断点可以观察lobj如下图所示:

可以看到,初始化后的lobj编码为压缩列表(5),此时lobj在内存中如下示意图所示(空压缩列表):

二.双端链表编码

前文中说到,列表对象在初始化时默认使用压缩列表作为底层实现,那么什么时候才会用到双端链表实现呢?这需要下列条件:

这里会有一个疑问,为什么对于INT编码的字符串对象不做长度检查,看了之前文章的同学应该了解,INT编码的字符串对象本身已经保证其长度不会太大,因此也不需要再检验了。

底层的插入操作通过listTypePush方法实现:

当我们实现如下命令时:

lpush test alsjflkasdljf9328904124jljlkajsdfjalskjdflajsf902839084234232234234

我们在listTypush前后打印断点可以看到编码从压缩列表(4)转换为双端链表(5)

具体的转换代码实现如下图所示,底层实现listTypeConvert方法:

这里需要强调一点,列表对象编码的转换是单向的,即只能有压缩列表->双端链表,而不会逆向操作,比如我们将刚才超长的字符串pop出来,再push进去y、z两个字符串,而列表对象依然使用双端链表编码:

三.阻塞操作

列表对象有几个阻塞操作,如blpop\brpop\brpoplpush。以blpop为例,其在官网的描述如下图所示:

这里主要是两点:

  1. 如果队列中有元素,则直接pop返回(同lpop效果)
  2. 如果队列中没有元素,则一直阻塞,直到队列中有元素或者达到超时时间

对于生产者-消费者模式来说,这种方式可以提高消费者获取消息的速度。但是我们都知道Redis是单进程单线程实现的,那么它是如何实现这种阻塞操作的呢?

我们首先来看blockForKeys方法,当客户端使用blpop调用某个空队列(或不存在的队列)时,就会触发该方法:

Redis数据库会记录该链表key作为键,阻塞的客户端链表作为值存到blocking_keys字典中。并且在blockClient方法中设置阻塞状态:

当客户端有Push行为时,会触发signalListAsReady方法:

当有客户端正在因为该队列而阻塞时,就把这个链表key放到server.ready_keys链表中,同时也放到ready_keys字典中防止重复操作。

而在Redis的处理命令的方法processCommand中(这里涉及到Redis的事件处理模型,后面还会细说):

会通过检测sever.ready_keys列表来决定是否需要处理阻塞客户端,而之后的操作就很明了了,从ready_keys中取出就绪列表,从blocking_keys中取出阻塞客户端,以“先阻塞先服务”的顺序依次执行阻塞客户端请求,并释放客户端阻塞状态,没有获得响应的客户端依旧阻塞。Redis将就绪列表分摊到多次EventLoop事件中去,从而实现命令的快速响应。

四.总结(思维导图)

欢迎关注我的公众账号

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis源码学习之链表

    Redis实现的是双端无环链表,pre指针指向其前置节点,next指针指向其后置节点,表头节点的pre属性和表尾节点的next属性为nil,节点值...

    里奥搬砖
  • Redis源码学习之字符串对象

    前文中提到,Redis的字符串对象的底层数据结构有三种,分别是整数编码、EMBSTR编码和SDS编码。在不同使用场景下进行相互切换,起到节约内存的作用。

    里奥搬砖
  • Redis源码学习之跳表

    跳跃链表简称为跳表(SkipList),它维护了一个多层级的链表,且第i+1层链表中的节点是第i层链表中的节点的子集。跳表作为一种平衡数据结构,经常和平衡树进行...

    里奥搬砖
  • 4300 字Python列表使用总结,用心!

    即从列表最后一个元素往前访问,此时索引依次被标记为-1,-2,...,-5 ,注意从-1开始。

    double
  • Redis系列(二)底层数据结构之双端链表

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • Redis源码分析(二)——Redis数据结构-链表

    数据结构——节点 typedef struct listNode{ struct listNode *prev; struct listNode *n...

    大闲人柴毛毛
  • 这次妥妥地拿下散列表---基础、如何设计以及扩展使用(LRU)

    大家好,我是多选参数的程序锅,一个正在”捣鼓“操作系统、学数据结构和算法以及 Java 的硬核菜鸡。

    syy
  • python基础1| 索引与切片

    看似简单的索引,有的人不以为然,我们这里采用精准的数字索引,很容易排查错误。若索引是经过计算出的一个变量,就千万要小心了,否则失之毫厘差之千里。

    统计学家
  • 10 个让你相见恨晚的 Python 骚操作

    众所周知,Python 以语法简洁著称,同样实现一个功能,Java 可能要十来行,Python 一行就可以搞定。

    纯洁的微笑
  • Python 10 个极简用法,第五期

    Python 无栈(stack)这一数据结构,但 Python列表实当栈用极为方便。

    double

扫码关注云+社区

领取腾讯云代金券