Redis Hash数据结构探秘

这篇具有很好参考价值的文章主要介绍了Redis Hash数据结构探秘。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在网上看了不少文章都是指导使用方式,要不就是老版本的redis结构,干脆我就自己看源码瞅瞅怎么个事。
本文主要说明的是数据结构和hash的基本操作原理,不是API文档,有想知道的API请自行查阅文档和代码。
关键词: ziplist、hashtable、listpack、rehash、dict。

数据结构

先说明 ziplist 和 listpack 的关系,Redis版本导致直接使用的数据结构不同,ziplist废弃了!
顺便说一句,ziplist是 老版本 hash/list/zset 底层结构,同时废弃的还有 zipmap(hash),linkedlist(list)。

Ziplist

从 ziplist 的注释中可以得到这些信息,已经说的很完善了,我来翻译一下。
数据结构成下表所示的紧凑排列,ziplist 信息均为无符号数 unsigned,全都按小端序(低位存低地址)排列。

zlbytes zltail zllen entry entry …… entry zlend
zlbytes(u32int) 用于存储ziplist占用的字节数,包括 zlbytes 字段本身的四个字节。
zltail(u32int) 指向 ziplist entry 尾部的偏移量,用来操作末尾元素。
zllen(u16int) 元素数量,占 2 Bytes。所以最多只能存65535,如果有更多元素的话只能遍历才知道具体数量了(注: 所以别配置那么大)。
zlend(u8int) 指向 ziplist 末尾,只有这个变量是单字节255。

Entry

主要由前两段来作为描述 entry 的元数据,特殊情况下 encoding 直接描述 data,例如small int,这时就不存在data部分。

prevlen encoding [entry-data]
变量 解释
prevlen 表示前面的entry length, 用来倒序遍历。大小为 0-253,那就是单字节u8int。不然就会消耗 5 字节,第一个字节设置为 0xFE(254) 表示后续有大数字长度,后面 4 个字节表示长度。
encoding data 的编码方式,即 type,如果是string 则会表示string的payload。
第一个字节是type,特殊type值255是zlend。
第二个字节如果是string可能会表达大小,后续字节表示数据。
如果是int的话,第一个字节表示 type 就足够了,后面跟着数据字节。具体编码规则请参考文档。

示例↓
Redis Hash数据结构探秘,知识分享,redis,哈希算法,数据结构,c++

Listpack

hash 的新结构,代替了 ziplist。原因大概就是由于一个crash,大家发现ziplist太复杂了,有点臃肿难以审查,干脆换个结构吧,于是 listpack 诞生了。
<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>
同样采用小端序。

变量 解释
tot-bytes u32int,表示整个结构的大小包括自身。这个变量是为了能倒序访问。
num-elements u16int,表示元素数量。和zllen一样,只能表达65535,多了就得遍历才知道。

Element(Entry)

Redis Hash数据结构探秘,知识分享,redis,哈希算法,数据结构,c++
和 ziplist 类似,如果 data 太小也会存在于 encoding 中,从而只有两段。

变量 解释
encoding-type 高位4bits用来表示类型,如果太小可能用不到4bits。后面表示数据和ziplist的大致相似,具体类型编码请参考文档。同时encoding也充当正序访问的len使用,解析encoding可以得到entry大小。
element-tot-len 表示element大小,用来倒序访问。由特殊的大端序存储多字节大小,具体编码方式参考文档。

HashTable

hash结构包括了以下几种结构。

dictEntry

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
};

typedef struct {
    void *key;
    dictEntry *next;
} dictEntryNoValue;

可以看到entry基本由kv和next指针构成。使用链表法来解决hash冲突

dict

struct dict {
  	// 这里存储这一些表信息。例如是否有value
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
    void *metadata[];
};

dict结构我们可以看到,其中包含了类型、两个table、rehash状态标志位、两个table已使用的节点数和元数据。两个表是因为是渐进式rehash,简单来说就是扩容时慢慢迁移表,避免大规模的数据迁移。

dict Iterator

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    unsigned long long fingerprint;
} dictIterator;

其中safe标志位表示这个迭代器是否为安全迭代器。安全迭代器不会进行rehash且不能操作数据。

(非)安全迭代器

直接看注释可以知道安全迭代器可以正常操作数据,而非安全迭代器只能查看。
google了一下大佬的回答大概是这个意思: redis 基于 Copy-On-Write 进行 dump,如果任何地方发生改动就会触发副本,所以这个时候就需要非安全迭代器进行访问,来将数据迁移完成,避免不必要的复制出现。

Hash 逻辑构成

数据结构切换

Redis Hash数据结构探秘,知识分享,redis,哈希算法,数据结构,c++
根据配置的参数可以决定什么时候发生紧凑结构 ziplist/listpack => hashtable 的转换,只要达到 entry 数量或者是 value 大小,都会立刻触发不可逆的转向 hashtable。下图就可以看出。
Redis Hash数据结构探秘,知识分享,redis,哈希算法,数据结构,c++
直接看注释

void hashTypeConvertListpack(robj *o, int enc) {
    serverAssert(o->encoding == OBJ_ENCODING_LISTPACK);

    if (enc == OBJ_ENCODING_LISTPACK) {
        /* Nothing to do... */

    } else if (enc == OBJ_ENCODING_HT) {
        hashTypeIterator *hi;
        dict *dict;
        int ret;
        // 初始化一个dict
        hi = hashTypeInitIterator(o);
        dict = dictCreate(&hashDictType);

        /* Presize the dict to avoid rehashing */
        dictExpand(dict,hashTypeLength(o));

      	// 开始迁移数据
        while (hashTypeNext(hi) != C_ERR) {
            sds key, value;
          	// 通过listpackAPI获取KV后迁移到dict
            key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY);
            value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);
            ret = dictAdd(dict, key, value);
            if (ret != DICT_OK) {
                // 异常记录
                sdsfree(key); sdsfree(value); /* Needed for gcc ASAN */
                hashTypeReleaseIterator(hi);  /* Needed for gcc ASAN */
                serverLogHexDump(LL_WARNING,"listpack with dup elements dump",
                    o->ptr,lpBytes(o->ptr));
                serverPanic("Listpack corruption detected");
            }
        }
        // 释放内存
        hashTypeReleaseIterator(hi);
        zfree(o->ptr);
        // 更新结构指针和标识成Hash,至此完成转换
        o->encoding = OBJ_ENCODING_HT;
        o->ptr = dict;
    } else {
        serverPanic("Unknown hash encoding");
    }
}

Rehash

redis 的渐进式 rehash 是通过多个每次至多 1ms 的 rehash 组成。
Redis Hash数据结构探秘,知识分享,redis,哈希算法,数据结构,c++

触发条件

rehash调用也是有条件的,还记得前文dict的pauserehash吗,这个变量就是标记能否进行rehash的变量,
rehash还需要确定rehash的许可,目前有三种状态: Enable(默认)、ForbidAVOID
其中Forbid是由于是 fork 线程所以不需要进行 hash ,AVOID是被 fork 的线程所在的状态,但是也判断如果两个表的大小是否在5倍以内的话不进行 rehash,因为是基于 Copy-On-Write 模式的,不过差距太大还是得进行 rehash。

函数执行过程

核心方法: int dictRehash(dict *d, int n) 返回1表示 rehash 进行中,0表示已完成。n是单次迁移的bucket数量,目前只有1和100,前者是主动修改了kv由迭代器触发,后者是渐进rehash的固定数量。文章来源地址https://www.toymoban.com/news/detail-829531.html

  1. 首先会根据 hash表的 resize 状态来判断能否进行 rehash。
  2. 对于比较稀疏的hash表来说,访问空节点是一种浪费。所以每次rehash最多访问 n*10 个空节点就会提前结束。
  3. 通过rehashidx继续 rehash
  4. 每次搬一个 bucket 节点,搬的过程中处理两个表的大小。rehash不仅仅是扩容也可能是缩容。
  5. 如果 rehash 全部完成了就释放空表内存并且重置标记位否则就return 1表示还得继续
/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]);
    unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]);
    if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;
    if (dict_can_resize == DICT_RESIZE_AVOID && 
        ((s1 > s0 && s1 / s0 < dict_force_resize_ratio) ||
         (s1 < s0 && s0 / s1 < dict_force_resize_ratio)))
    {
        return 0;
    }

    while(n-- && d->ht_used[0] != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
        while(d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht_table[0][d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = dictGetNext(de);
            void *key = dictGetKey(de);
            /* Get the index in the new hash table */
            if (d->ht_size_exp[1] > d->ht_size_exp[0]) {
                h = dictHashKey(d, key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
            } else {
                /* We're shrinking the table. The tables sizes are powers of
                 * two, so we simply mask the bucket index in the larger table
                 * to get the bucket index in the smaller table. */
                h = d->rehashidx & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
            }
            if (d->type->no_value) {
                if (d->type->keys_are_odd && !d->ht_table[1][h]) {
                    /* Destination bucket is empty and we can store the key
                     * directly without an allocated entry. Free the old entry
                     * if it's an allocated entry.
                     *
                     * TODO: Add a flag 'keys_are_even' and if set, we can use
                     * this optimization for these dicts too. We can set the LSB
                     * bit when stored as a dict entry and clear it again when
                     * we need the key back. */
                    assert(entryIsKey(key));
                    if (!entryIsKey(de)) zfree(decodeMaskedPtr(de));
                    de = key;
                } else if (entryIsKey(de)) {
                    /* We don't have an allocated entry but we need one. */
                    de = createEntryNoValue(key, d->ht_table[1][h]);
                } else {
                    /* Just move the existing entry to the destination table and
                     * update the 'next' field. */
                    assert(entryIsNoValue(de));
                    dictSetNext(de, d->ht_table[1][h]);
                }
            } else {
                dictSetNext(de, d->ht_table[1][h]);
            }
            d->ht_table[1][h] = de;
            d->ht_used[0]--;
            d->ht_used[1]++;
            de = nextde;
        }
        d->ht_table[0][d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht_used[0] == 0) {
        if (d->type->rehashingCompleted) d->type->rehashingCompleted(d);
        zfree(d->ht_table[0]);
        /* Copy the new ht onto the old one */
        d->ht_table[0] = d->ht_table[1];
        d->ht_used[0] = d->ht_used[1];
        d->ht_size_exp[0] = d->ht_size_exp[1];
        _dictReset(d, 1);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

参考资料

  1. Redis源码: v7.2.x unstable
  2. listpack/listpack.md at master · antirez/listpack
  3. what’s the difference of safe/non-safe dict itereator in redis’ dict implementation?

到了这里,关于Redis Hash数据结构探秘的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Redis Redis的数据结构 - 通用命令 - String类型命令 - Hash类型命令

    目录 Redis的数据结构: Redis命令: 通用命令:(通用指令是部分数据类型的,都可以使用的指令) KEYS查询命令: DEL删除命令: EXISTS判断命令: EXPIPE有效期设置命令: TTL查看剩余期限命令: String类型: String的3种类型: String类型的常见命令: SET插入数据命令: MSET多重插

    2024年02月09日
    浏览(46)
  • 【redis】redis获取hash结构的海量数据,hgetAll、hscan、hkeys 性能大比拼

    根据上一篇文章:【Redis】 redis hash getKey getValue 两个的性能差别 我们知道hgetAll的性能是极差的,然后我们优化成hkeys的,但是hkeys真的好吗? 下面我们来说一下我们的现场,就是现场我们

    2024年01月22日
    浏览(34)
  • Redis追本溯源(二)数据结构:String、List、Hash、Set、Zset底层数据结构原理

    Redis 并没有直接用 C 语言的字符串,而是自己搞了一个 sds 的结构体来表示字符串,这个 sds 的全称是 Simple Dynamic String,翻译过来就是“简单的动态字符串”。 安全的二进制存储 资源。关于sds的扩容和缩容下面会进行详细的介绍,这里先不赘述了。 在一些情况中,我们需要

    2024年02月16日
    浏览(55)
  • 本文通过实例介绍了Redis的基础知识、数据类型、数据结构以及典型应用场景 值得一看!

    作者:禅与计算机程序设计艺术 2017年,Redis是基于MIT许可发布的一个开源的高性能键值数据库,其开发语言为C语言。它提供了多种数据类型(strings、hashes、lists、sets、sorted sets等),分布式支持(可横向扩展),内存存储,持久化功能,事务处理功能等。作为一种高性能的

    2024年02月06日
    浏览(71)
  • Redis学习路线(2)—— Redis的数据结构

    一、Redis的数据结构 Redis是一个Key-Value的数据库,key一般是String类型,不过Value的类型却有很多: String: Hello World Hash: {name: \\\"jack\\\", age: 21} List: [A - B - C - C] Set: {A, B, C} SortedSet: {A: 1, B: 2, C: 3} GEO: {A: (120.3, 30.5)} BitMap: 0110110101110101011 HyperLog: 0110110101110101011 由于Redis对数据

    2024年02月15日
    浏览(43)
  • 【Redis】Redis中的数据结构和内部编码

    type命令实际返回的就是当前键的数据结构类型,它们分别是:string(字符串)、list(列表)、hash(哈希)、set(集合)、zset(有序集合),但这些只是Redis对外的数据结构, 实际上Redis针对每种数据结构都有⾃⼰的底层内部编码实现,⽽且是多种实现,这样Redis会在合适的

    2024年02月07日
    浏览(42)
  • redis1之安装redis,启动,常用数据结构

      目录 redis安装与启动、常见数据结构 启动  Redis客户端 数据结构与常见的命令  redis的通用命令  String类型的用法 Hash命令的用法  List命令  Set命令  SortedSet类型用法 1,在linux上安装上gcc的依赖,我这里是centos7.6,gcc是4.5 我们在LInux上查看一下我们的系统信息  我这里安装

    2024年02月06日
    浏览(48)
  • Redis的数据结构

    Redis是一款高性能的键值存储数据库,支持多种数据结构。在Redis中,数据结构是指在Redis中存储和操作数据的方式。Redis支持的数据结构包括字符串、哈希表、列表、集合和有序集合。 字符串是Redis中最基本的数据结构,可以存储任何类型的数据,包括数字、文本和二进制数

    2024年02月09日
    浏览(40)
  • redis核心数据结构

    redis下载地址:Download | Redis linux进入redis目录首先使用make命令进行c++的编译,修改redis.conf文件: 启动退出相关命令: redis五种数据结构图: 1、常用命令 2、应用场景 1)、单值缓存 2)、对象缓存 3)、分布式锁  4)、计数器 5) 、计数器 6) 、分布式系统全局序列号 1、

    2024年02月09日
    浏览(40)
  • Redis底层数据结构

    SDS全称是Simple Dynamic String,具有如下显著的特点: 常数复杂度获取字符串长度:C语言获取一个字符串的长度需要遍历整个字符串时间复杂度为O(N),而SDS在属性len中记录了字符串长度,获取字符串长度的时间复杂度为O(1)。 杜绝缓冲区溢出:C字符串在执行拼接字符串时,如果

    2024年02月13日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包