redis中的数据结构和编码详解

 更新时间:2021年1月15日 13:19  点击:2529

redis中的数据结构和编码:

    背景:

  •         1>redis在内部使用redisObject结构体来定义存储的值对象。
  •         2>每种类型都有至少两种内部编码,Redis会根据当前值的类型和长度来决定使用哪种编码实现。
  •         3>编码类型转换在Redis写入数据时自动完成,这个转换过程是不可逆的,转换规则只能从小内存编码向大内存编码转换。

    源码:

        值对象redisObject:

            typedef struct redisObject {
                unsigned type:4;                /* 对象类型 */
                unsigned encoding:4;            /* 内部编码 */
                unsigned lru:LRU_BITS;     /* lru time (relative to server.lruclock) */
                int refcount;                    /* 引用计数器,内存回收机制就是基于该值实现的 */
                void *ptr;                        /* 若要存储的是整数值则直接存储数据,否则表示指向数据的指针 */
            } robj;

        类型type:

            说明:查看当前键的类型:type key

            #define OBJ_STRING 0     /*字符串对象*/
            #define OBJ_LIST 1        /*列表对象*/
            #define OBJ_SET 2        /*集合对象*/
            #define OBJ_ZSET 3        /*有序集合对象*/
            #define OBJ_HASH 4        /*哈希对象*/

        编码encoding;

            说明:查看当前键的编码:object encoding key

            #define OBJ_ENCODING_RAW 0             /*Raw representation 简单动态字符串*/
            #define OBJ_ENCODING_INT 1             /*Encoded as integer long long类型整数*/
            #define OBJ_ENCODING_HT 2            /* Encoded as hash table 字典*/
            #define OBJ_ENCODING_ZIPMAP 3        /* Encoded as zipmap 压缩map*/
            #define OBJ_ENCODING_LINKEDLIST 4     /* Encoded as regular linked list 双端链表*/
            #define OBJ_ENCODING_ZIPLIST 5         /* Encoded as ziplist 压缩列表*/
            #define OBJ_ENCODING_INTSET 6         /* Encoded as intset 整数集合*/
            #define OBJ_ENCODING_SKIPLIST 7     /* Encoded as skiplist 跳跃表*/
            #define OBJ_ENCODING_EMBSTR 8         /* Embedded sds string encoding embstr编码的简单动态字符串*/
            #define OBJ_ENCODING_QUICKLIST 9     /* 基于压缩列表的双端列表实现的 快速表*/

        最后被访问的时间lru:

            概念:记录对象最后一次被访问的时间。
            说明:
                1>查看当前键的空闲时间(该命令不会更新lru字段);object idletime key 。可以通过scan + object idletime key 来收集长时间未被访问的数据,然后手动清理。
                2>当配置了maxmemory和maxmemory-policy=volatile-lru或者allkeys-lru时,若内存超过了上限(maxmemory)后,则优先回收长时间没有被访问的数据,从而回收内存。

        引用计数器refcount:    

            概念:记录当前对象被引用的次数,当refcount=0时,可以安全回收当前对象空间。
            说明:获取当前对象引用:object refcount key

    类型对应的编码:

        字符串:
            int:存放整形值的字符串。
            embstr:存放字符的短字符串(大小不超过44个字节)。
            raw:存放字符的长字符串(大小不超过44个字节)。
           
            embstr和raw的比较:
                raw调用2次内存分配函数,释放时当然也需要释放两次。
                embstr调用1次内存分配函数,分配一块连续的内存,释放时只需释放一次。

        列表(list):

            压缩列表(ziplist):
                结构:所有数据都是采用线性连续的内存结构(大致可类比数组),目的是为了减少内存的占用,追求空间和时间的平衡。
                    1>以O(1)时间复杂度入队和出队。
                    2>读写操作涉及复杂的指针移动,最坏时间复杂度为O(n2),故列表的元素不易太多。
                    3>新增删除操作涉及内存重新分配,加大了操作的复杂性。

                优点:占用内存较少,且占用的是一块连续的内存,故加载的速度相对更快一些。
                缺点:当元素的个数较大时,访问元素的时间较长。

                应用:

                   适合存储小对象和长度有限(即使O(n2)的复杂度也不会太大)的数据。
                    当元素个数小于list-max-ziplist-entries(默认512) 且 所有元素值的大小都小于list-max-ziplist-value(默认64字节)时,使用ziplist作为列表的内部实现。

            双端链表(linkedlist):

                优点:元素的个数较多时,访问元素的时间比压缩列表更快一些。
                缺点:因为是双向链表,故维护了前置指针、后置指针等结构,占用了更多的内存,且内存不是连续的,容易产生内存碎片。
                说明:当无法满足ziplist的条件时,使用linkedlist作为列表的内部实现。
                应用:当列表对象元素较多时,压缩列表就会转化为更适合存储大量元素的双端链表。
               
            注意:只能小内存编码向大内存编码转换。(若当元素增删频繁时,数据向压缩编码转换是非常消耗CPU的,得不偿失)

            快速列表(quicklist):

                结构:一个双向链表,链表的每一个节点都是一个ziplist,故quicklist结合了双向链表和压缩列表的优点。
                Redis3.2开始,列表采用quicklist进行编码。

        哈希(hash):

            压缩列表(ziplist):

                应用:当元素个数小于hash-max-ziplist-entries(默认512) 且 所有元素value的大小都小于hash-max-ziplist-value(默认64字节)时,使用ziplist作为哈希的内部实现。

            哈希表(hashtable):

                优点:读写时间复杂度O(1)
                缺点:占用内存较多。
                应用:当无法满足ziplist的条件时,hashtable作为哈希的内部实现。

            hash算法:与传统hash算法类似,根据key计算得到在哈希表中的位置,采用单链表解决冲突,达到加载因子时进行扩展,进而引发重哈希。

            rehash:采用增量式重哈希:

                概念:在扩容时不会一次性对所有的key进行rehash,而是将key的rehash操作分散延迟到其它操作(哈希表的查找、更新、删除)中。
                优点:避免由于大量的key在同一时间段进行rehash操作导致服务短暂无响应的问题。
                过程:在增量式的rehash过程中,会使用到两张哈希表:
                    查找:先从老表中查找,再从新表中查找,此外还会对一些key进行rehash操作。
                    新增:新增的键值对添加到新表中。

        集合(set):

            整数集合(intset):
                结构:有序、不重复的整数集。
                    1>查找时间复杂度为O(logn)
                    2>插入时间复杂度为O(n)
                优点:占用的内存远小于hashtable,
                应用:当元素都是整数 且 元素个数小于set-max-intset-entries(默认512)时,使用intset作为集合的内部实现。

            哈希表(hashtable):当无法满足intset的条件时,使用hashtable作为集合的内部实现。

        有序集合(zset):

            说明:redis给有序集合中的每个元素设置一个分数(score)作为排序的依据。
           
            压缩列表(ziplist):
                应用:当元素个数小于zset-max-ziplist-entries(默认128个) 且 每个元素的值都小于zset-max-ziplist-value(默认64字节)时,使用ziplist作为有序集合的内部实现。
               
            跳跃表(skiplist):
                结构:跳跃表通过在每个节点中(基于层和跨度等)维持多个指向其它节点的指针来实现快速访问。
                    查找时间复杂度平均O(logn)、最坏O(n)。
                应用:当不满足ziplist条件时,使用skiplist作为内部实现。

    内存优化:

        场景:有海量key和value都比较小的数据,在redis中如何存储才更省内存。
        原理:通过大幅减少key的数量来降低内存的消耗。
        实现:在客户端通过分组将海量的key根据一定的策略映射到一组hash对象中,由于value较小,故hash类型的对象会使用占用内存较小的ziplist编码。
            eg:如存在100万个键,可以映射到1000个hash中,每个hash保存1000个元素。

以上就是redis中的数据结构和编码详解的详细内容,更多关于redis中的数据结构和编码的资料请关注猪先飞其它相关文章!

[!--infotagslink--]

相关文章

  • 详解如何清理redis集群的所有数据

    这篇文章主要介绍了详解如何清理redis集群的所有数据,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-18
  • Redis连接池配置及初始化实现

    这篇文章主要介绍了Redis连接池配置及初始化实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-29
  • 详解redis desktop manager安装及连接方式

    这篇文章主要介绍了redis desktop manager安装及连接方式,本文图文并茂给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-15
  • 浅谈redis key值内存消耗以及性能影响

    这篇文章主要介绍了浅谈redis key值内存消耗以及性能影响,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-07
  • C#数据结构之队列(Quene)实例详解

    这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
  • lua读取redis数据的null判断示例代码

    最近在工作中遇到了一个问题,通过查找相关资料才得知原因是因为返回结果的问题,下面这篇文章主要给大家介绍了关于lua读取redis数据的null判断的相关资料,文中通过示例代码介绍的非常详细,需要的朋友可以参考下...2020-06-30
  • SpringBoot集成Redis实现消息队列的方法

    这篇文章主要介绍了SpringBoot集成Redis实现消息队列的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-10
  • redis setIfAbsent和setnx的区别与使用说明

    这篇文章主要介绍了redis setIfAbsent和setnx的区别与使用,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-08-04
  • Redis的Expire与Setex区别说明

    这篇文章主要介绍了Redis的Expire与Setex区别说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-15
  • 查看Redis内存信息的命令

    Redis 是一个开源、高性能的Key-Value数据库,被广泛应用在服务器各种场景中。本文介绍几个查看Redis内存信息的命令,包括常用的info memory、info keyspace、bigkeys等。...2021-01-15
  • Redis的持久化方案详解

    在本篇文章里小编给大家整理的是关于Redis的持久化方案详解,有兴趣的朋友们可以参考下。...2021-01-15
  • JAVA中 redisTemplate 和 jedis的配合使用操作

    这篇文章主要介绍了JAVA中 redisTemplate 和 jedis的配合使用操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-13
  • @CacheEvict + redis实现批量删除缓存

    这篇文章主要介绍了@CacheEvict + redis实现批量删除缓存方式,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-10-12
  • redis 交集、并集、差集的具体使用

    这篇文章主要介绍了redis 交集、并集、差集的具体使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
  • C#常用数据结构和算法总结

    这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
  • 解决redisTemplate中leftPushAll隐性bug的问题

    这篇文章主要介绍了解决redisTemplate中leftPushAll隐性bug的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-13
  • Redis集群水平扩展、集群中添加以及删除节点的操作

    这篇文章主要介绍了Redis集群水平扩展、集群中添加以及删除节点的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-25
  • 解决Redis开启远程访问及密码问题

    这篇文章主要介绍了Redis开启远程访问及密码的教程,文中给大家提到了Redis启动报错解决方法,需要的朋友可以参考下...2021-01-15
  • 利用Redis如何实现自动补全功能

    这篇文章主要给大家介绍了关于如何利用Redis如何实现自动补全功能的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用Redis具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧...2020-04-17
  • 深入理解redis中multi与pipeline

    pipeline 只是把多个redis指令一起发出去,redis并没有保证这些指定的执行是原子的;multi相当于一个redis的transaction的,保证整个操作的原子性,避免由于中途出错而导致最后产生的数据不一致。本文详细的介绍,感兴趣的可以了解一下...2021-06-02