专栏首页golang+phpredis源码之list结构的实现

redis源码之list结构的实现

关于redis的list的常用命令就不多说了 常用的命令lpush,rpush,lpop,rpop,lrangge等,这个不错过多的演示,相信研究源码的同学应该都知道这些,唯一要说的就是在redis中有BRPOP等命令,这个是通过redisDb中的blocking_keys和ready_keys来实现,当然这个不是咱们这篇文章需要讨论的重点

typedef struct redisDb {
    dict *dict;                /* The keyspace for this DB   字典数据结构,非常重要*/
    dict *expires;             /* Timeout of keys with a timeout set   过期时间*/
    dict *blocking_keys;       /* Keys with clients waiting for data (BLPOP)  list一些数据结构中用到的阻塞api*/
    dict *ready_keys;          /* Blocked keys that received a PUSH */
    dict *watched_keys;        /* WATCHED keys for MULTI/EXEC CAS  事务相关处理 */
    int id;                    /* Database ID */
    long long avg_ttl;         /* Average TTL, just for stats */
    unsigned long expires_cursor;/* Cursor of the active expire cycle. */
    list *defrag_later;        /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

对于redis的list来说,list是一个有序(按照加入的时序来排序)的数据结构,redis采用quicklist(双端链表)和ziplist作为list的底层实现 我们先来看看ziplist的结构图

具体各个属性的含义都在图片中有所说明,其实ziplist就是一个非常紧凑的数据结构,非常节省空间,但是它也存在对应的问题。比如我们在新加一个元素的时候,我们需要重新分配一块内存空间,然后再把数据全部拷贝过来,如果数据量小还好说,数据量大了非常影响性能,所以redis中在处理list的时候引入了quicklist的数据结构

其实quicklist的实现也比较简单,就是用了一个双向链表把各个ziplist给连接了起来。那么问题来了,每个quicklistNode中的ziplist是多大呢?根据什么来拆分呢?在redis.conf中

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2     //单个ziplist节点最多存储8kb,超过则进行分裂,将数据存储在新的ziplist节点中

双向链表的问题就是会造成很多不连续的内存碎片,于是就需要尽量减少list的片段,就需要进行压缩

# Lists may also be compressed.
# Compress depth is the number of quicklist ziplist nodes from *each* side of
# the list to *exclude* from compression.  The head and tail of the list
# are always uncompressed for fast push/pop operations.  Settings are:
# 0: disable all list compression
# 1: depth 1 means "don't start compressing until after 1 node into the list,
#    going from either the head or tail"
#    So: [head]->node->node->...->node->[tail]
#    [head], [tail] will always be uncompressed; inner nodes will compress.
# 2: [head]->[next]->node->node->...->node->[prev]->[tail]
#    2 here means: don't compress head or head->next or tail->prev or tail,
#    but compress all nodes between them.
# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]
# etc.
list-compress-depth 0//0代表所有节点,都不进行压缩,1代表从头节点往后走一个,尾节点往前走一个不用压缩,2、3、4以此类推  这个目的主要是减少内存的碎片

本文分享自微信公众号 - 程序员养成日记(programmer_grow),作者:redis

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • mysql索引原理,看这篇就够啦

    网上已经有了很多相关mysql索引原理的文章,但是都存在一些问题,有的是直接复制别人的比较老的文章,有的直接开篇讲B+Tree的原理,过程不是很清楚,即使原理讲...

    程序员养成日记
  • go语言单元测试相关记录

    参数t上的Log和Logf一般用于记录一些常规信息,以展现测试程序的运行过程以及被测试程序实体的实时状态。 t.Log方法与fmt.Println函数使用方法...

    程序员养成日记
  • redis的两种持久化的机制,你真的了解么?

    AOF(Append-Only File):指所有的命令行记录以redis命令请求协议的格式完全持久化存储保存为AOF文件

    程序员养成日记
  • STL list源码分析以及实现

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

    bear_fish
  • python socket 端口测试

    #coding:utf8 import socket,time,re,thread,os timeout=3 socket.setdefaulttimeout(...

    py3study
  • 学Python,从列表推导到zip()函数,这五种技巧应知应会

    机器之心已经介绍过很多 Python 教程,从非常齐备的长教程:一文掌握 Python 关键代码,到一些好玩的小技巧:Python 技巧 101,它们从不同的层...

    机器之心
  • 学Python,从列表推导到zip()函数,这五种技巧应知应会!

    最开始学 Python 时,如果我能掌握这些方法,那么代码看起来会更加优美。在本文中,作者介绍了 5 种方法,也许在入门阶段时,我们还不太了解它们,但在实战中这...

    1480
  • 学Python,从列表推导到zip()函数,这五种技巧应知应会

    在本文中,作者介绍了 5 种方法,也许在入门阶段时,我们还不太了解它们,但在实战中这 5 个技巧非常实用。

    CDA数据分析师
  • Nodejs 与 Python 的使用对比

    写这篇文章的目的是想记录下NodeJs(后面简称node)与python的使用对比,希望看完之后大家对node跟python有个基本的认识。

    五月君
  • python技巧(2)--碾平列表和列表去重

    碾平列表(flatten list ),即当列表里面嵌套列表,如何将这些子列表给取出来,得到一个不包含子列表的列表,示例如下:

    kbsc13

扫码关注云+社区

领取腾讯云代金券