V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hansonwang99
V2EX  ›  程序员

Redis 哈希结构内存模型剖析

  •  
  •   hansonwang99 ·
    hansonwang99 · 2018-08-27 08:59:12 +08:00 · 2076 次点击
    这是一个创建于 2265 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Profile

    本文共 1231 字,阅读大约需要 5 分钟 !


    概述

    在前文《 Redis 字符串类型内部编码剖析》之中已经剖析过 Redis最基本的 String 类型的内部是怎么编码和存储的,本文再来阐述 Redis 中使用 最为频繁的数据类型:哈希(或称散列),在 Redis 内部是怎么存的。

    • 实验源码环境:Redis 4.0.10

    注: 本文首发于 My Personal Blog,欢迎光临 小站

    本文内容脑图如下:

    本文内容脑图


    哈希类型内部编码详情

    对于 Redis 的常用 5 种数据类型( String、Hash、List、Set、sorted set ),每种数据类型都提供了 最少两种 内部的编码格式,而且每个数据类型内部编码方式的选择 对用户是完全透明的,Redis 会根据数据量自适应地选择较优化的内部编码格式。

    如果想查看某个键的内部编码格式,可以使用 OBJECT ENCODING keyname 指令来进行,比如:

    127.0.0.1:6379> 
    127.0.0.1:6379> set foo bar
    OK
    127.0.0.1:6379> 
    127.0.0.1:6379> object encoding foo  // 查看某个 Redis 键值的编码
    "embstr"
    127.0.0.1:6379> 
    127.0.0.1:6379> 
    

    对于使用最为频繁的 Hash 类型,其内部编码方式可能有两种:

    • OBJ_ENCODING_ZIPLIST(压缩列表)
    • OBJ_ENCODING_HT(哈希表)

    Redis 会根据数据量的情况来自适应地选择这两种编码方式中 较优 的一种,而这一切对用户完全透明。

    数据条目较少数据值较小 的时候 Redis 会采用 压缩列表( OBJ_ENCODING_ZIPLIST )编码方式进行存储。这里成员"较少",成员值"较小"的标准可以通过如下配置项进行配置:

    hash-max-ziplist-entries 512
    hash-max-ziplist-value 64
    

    Redis 默认给出了默认值,当然用户可根据实际情况自行配置。

    Hash 类型键的字段个数 < hash-max-ziplist-entries 并且 每个字段名和字段值的长度 < hash-max-ziplist-value 时,Redis 会使用 OBJ_ENCODING_ZIPLIST 来存储该键,反之则会转换为 OBJ_ENCODING_HT 的编码方式。

    口说无凭,我们不妨先来做个实验感受一下吧:

    Redis 自适应地选择编码方式

    很明显该实验验证了当 字段值长度大于 64时,编码格式会由 ZIPLIST 方式切换为 Hashtable 方式。

    源码之前,了无秘密,我们再来看一下 Redis 关于这部分切换的源码实现,那就理解得更加清楚了:

    Redis 哈希类型编码选择的源码

    Redis 哈希类型编码选择的源码

    下面详解 OBJ_ENCODING_ZIPLISTOBJ_ENCODING_HT 这两种编码格式的内部存储模型,知道了其各自特点和优缺点,自然也就明白了 Redis 内部使用它们的意图。


    OBJ_ENCODING_ZIPLIST 编码

    Ziplist 压缩列表是一种紧凑编码格式,总体思想是时间换空间,即以部分读写性能为代价,来换取极高的内存空间利用率,因此只会用于 字段个数少,且字段值也较小 的场景。

    压缩列表内存利用率极高的原因与其连续内存的特性是分不开的,其典型的内存结构可以用下图形象地展示出来:

    ZIPLIST 内存模型

    所以如果用 Ziplist 来存储 Redis 的散列类型的话,元素的排列方式就变成了如下图所示的形象示意图:即 key 和 value 都是逻辑连续内存:

    用 Ziplist 来存储 Redis 的散列类型


    OBJ_ENCODING_HT 编码

    OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构,或称为字典结构,其可以实现 O(1)复杂度的读写操作,因此效率很高。

    在 Redis 内部,从 OBJ_ENCODING_HT 类型到底层真正的散列表数据结构是一层层嵌套下去的,关系如下:

    Redis 哈希嵌套关系

    这一关系我们可以从 Redis 哈希表定义部分的源码来看出:

    Redis 哈希表定义部分的源码

    下面来详解一下各个部分:

    • 关于哈希节点( dictEntry )

    dictEntry

    • 关于哈希表( dictht )和字典( dict )

    dictht 和 dict

    • 关于 dictType

    dictType

    • Redis 如何计算 Hash 值

    Redis 计算 Hash 的源代码如下:

    计算 Hash 值

    这是一个 C 语言宏定义,其实幕后真正承担 Hash 值计算的是上面介绍的 dictType结构体中的函数指针 hashFunction

    而该 hashFunction函数指针在初始化时会对应被赋值为一个个真实的计算 Hash 值的实际函数,就像下面这样:

    hashFunction 函数指针赋值

    • Redis 如何计算存取索引 Index 值

    Index 值的计算依赖于上面计算得出的 Hash 值,代码如下:

    Redis 计算索引 Index 值的源码

    到此,还有一个一直非常值得关注的细节:即字典 dict 里总是保存有两个 Hash 表结构 ht[2],以及与其高度相关的 rehash 操作,这在下一篇文章里详解。


    后 记

    由于能力有限,若有错误或者不当之处,还请大家批评指正,一起学习交流!



    3 条回复    2018-08-27 16:49:16 +08:00
    TustMan
        1
    TustMan  
       2018-08-27 10:18:35 +08:00
    感谢分享,很不错
    rookiedev
        2
    rookiedev  
       2018-08-27 10:29:10 +08:00
    虽然我这个菜鸟看不懂,但看得出文章写的很用心了,值得关注
    hansonwang99
        3
    hansonwang99  
    OP
       2018-08-27 16:49:16 +08:00
    感谢阅读
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2326 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 16:03 · PVG 00:03 · LAX 08:03 · JFK 11:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.