Redis 的几种数据结构&五种数据类型对象

先看几种数据结构

通过分析底层的数据结构，学习如何根据场景选型和设计

 1，简单动态字符串

    redis使用的字符串SDS有别于C语言中的字符串

   a, 结构

 

    free字段为已分配但未使用的空间

    len为已使用的空间（不计入'\0'）

    buf为char数组

    b, 与C字符串区别

        redis的字符环结构可以理解为将C字符串封装了一层，通过加入的属性字段降低字符串操作的复杂度，提高安全性。

        通过len属性可以在常数复杂度获取字符串的长度，仅通过len属性可直接获取长度，而C语言字符串复杂度需要遍历，长度为O（N）。

        二进制安全的。C字符串是ASCII编码的，以'\0'来判断字符串是否结束，如果数据中包含'\0'字符便会将数据截断，当做两个字符串，因此仅限于保存文本数据。redis字符串通过len属性来获取数据而不是通过遍历寻找结束标志，因此可以存储任意内容的二进制数据。

        兼容C字符串的操作。默认在字符串最后加'\0‘，使用C库字符串的部分操作。

        避免缓冲区溢出。其实原理就是根据redis字符串的特点重写了C可能造成内存溢出的函数，如strcat拼接字符串函数，C语言中需人为保证目标字符串的空间足够大，否会造成溢出，而redis字符串通过free属性来自动判断是否可容纳源字符串，否则会扩展自身内存再拼接。

        减少内存分配次数。空间和效率的问题，redis采用的是牺牲空间来换取效率的提升，避免多次的申请或释放内存。redis是kv型数据库，要求速度快，数据也多为频繁修改，因此牺牲一部分空间是可取的。它提供了两种策略，空间预分配和惰性释放。预分配指的是一个字符串修改后会同时分配一定大小的空间给free预留，避免再次修改分配内存。惰性释放是字符串缩短后不是放空间而是给free记录，避免释放空间。

    预分配和惰性释放在memcache中也使用了，不过它是从内存管理的角度出发的。通过在初始化时对整个内存进行预分配，减少动态申请内存的操作带来的消耗，使用的内存都是连续的，避免了内存碎片，内存也不会回收而是通过内个slab的slot指针数组来保存。关于memcache的内存管理的机制具体见这里

    c, 场景

        该类型是字符串对象的一种实现方式，并用于AOF缓冲区和客户端输入缓冲区。

 

2，链表

    redis使用的联表示标准的双端无环链表

    a, 结构

        其中，head和tail表示链表的表头和表尾节点，len表示链表中节点的数目，dup、free、match分别为复制、释放和对比函数。

    b, 场景

        链表结构的特点是可以快速的在表头和表尾插入和删除元素，但查找复杂度高，是列表的底层实现之一，也因此列表没有提供判断某一元素是否在列表中的借口，因为在链表中查找复杂度高。

 

3，字典

    redis的字典使用哈希表作为底层实现。

    a, 结构

        上图为字典结构图

        dict结构中，type表示是dicttype类型的指针，表示操作特定类型的键值对的函数，privdata是传给特定函数的可选参数。ht是包含两个哈希表的数组，ht[0]表示正常存放数据的hash表，而ht[1]用于rehash，rehashidx是记录了rehash的进度，正常情况下为-1。

        dictht是哈希表，table表示哈希表数组，指针数组，size表示哈希表的大小，used表示已有节点的数目，used/size为负载因子，决定何时进行rehash。sizemask用于计算索引值。

        每个哈希表元素是dictentry结构，key为键，value可以是一个指针或是一个整数。，next为指向下一个的指针。是传统的hash表。

    b, rehash

        redis使用murmurhash算法计算hash值，能有很好的随机分布性，速度也很快。

        当负载因子大于3/2时进行扩容操作，扩容大小为第一个大于ht[0].used*2的2^n，当负载因子小于0.1进行缩容，为第一个大于ht[0].used的2^n。

        redis采用渐进式rehash，将rehash操作分摊到每次增删改查，具体过程见这里

    c, 场景

        字典是数据库和哈希对象的底层实现，数据库中dict存放所有kv，v可能是各种对象，而expire存放有过期时间的k和过期时间。用作hash底层时，k和v都是字符串对象。

4，跳跃表

    跳跃表是一种可以快速访问节点的数据结构，性能接近于平衡术，且实现简单。

    a, 结构

        跳跃链表是一种随机化数据结构，基于并联的链表。跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表。所有操作都以对数随机化的时间进行。

        header和tail指向表头和表尾，level表示最大层级，length表示节点数目（不包括首节点）

        每个节点都包含一个后退指针，用于从尾部遍历，路径唯一。obj为一个对象，score为对应的分值。level是大小随机出来的层级数组，每个层级包含一个前进指针和距离指向节点的跨度。跨度用于计算rank，跨度之和为rank。具体算法这里不介绍，具体见这里

    b, 场景

        跳跃表是有序集合的底层实现之一，跳跃表将指向有序集的 score 值和 member 域的指针作为元素， 并以 score 值为索引， 对有序集元素进行排序。  

        redis根据自己的需求对跳跃表做了更改：

1. score 值可重复。
2. 对比一个元素需要同时检查它的 score 和 memeber 。
3. 每个节点带有高度为 1 层的后退指针，用于从表尾方向向表头方向迭代，当执行ZREVRANGE或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。

5，整数集合

    redis的整数集合实质上是动态的数组。reids的整数集合是可以根据整数的值，自动选择用什么长度来存储。

    a, 结构 

        encoing标会编码方式，8/16/32/64位，length表示集合元素的数量，contents表示数据，元素由小到大排列。 

    b, 升级

        当加入的数大于encoding对应的最大长度时，自动进行升级操作。流程是：首先扩展数组空间的大小。将原数组中的原书进行类型扩展并存储，最后将新插入的数放入对应位置。整数集合不做降级操作。

    c, 场景

        整数集合是redis集合对象的底层实现之一。当键数量小于512并且键值为整数时集合使用整数集合作为底层存储，节约内存。如何保证不重复？（待解决）。

 

6，压缩列表

redis使用压缩列表来存储小整数值或长度比较短的字符串

    压缩列表是为了节省内存开发的，是一系列特殊编码的连续内存块组成的顺序型数据结构。

    a, 结构

        zlbytes记录整个列表所占的内存数

        zltail记录距离尾节点的距离

        zllen记录节点数目

        entry是每个节点

        zlend列表结束标志

        每个节点的组成，previous_entry_length是前一节点的长度，可用于从尾节点向前遍历，encoding记录content的数据类型和长度，content为节点的值。

    b, 连锁更新

        当插入或者删除元素时，会导致previous_entry_length的长度发生变化，如有1子节点为5字节，如果原先本节点的总大小处于250至253之间，会导致笑一个节点的previous..的长度发生变化，可能引起连锁更新的情况。需要不停的重复分配空间来存放增大的大小。

        但redis中假定的是处于临界大小的数据很多并且连续这种情况几率很低，同事假定被更新的节点数目少。

    c, 场景

        redis使用压缩列表来作为列表键和哈希键的底层实现之一，存储小整数值或长度比较短的字符串时使用，previous_entry_length的存在使其可以像链表一样遍历。实现hash时顺序添加相邻接的节点为k和v。

1，redis对象的结构

   

    type记录了对象的类型，可以使字符串，列表，哈希，集合和有序集合对象。

    encoding记录的是type对象对应的底层实现，在redis中每种类型只有少两种底层实现的数据结构。通过不同的编码方式是redis可以根据不同的使用场景来选择不同的实现方式。同时不同编码在满足条件时会触发转换。

    ptr是指向底层实现数据结构的指针。

2，字符串

    字符串对象是使用最广泛的类型，如memcache中的kv的v相似。也是redis其他数据类型嵌套使用的对象类型。有三种编码方式：int、raw、embstr三种。

    a, raw编码方式

       

        字符串对象是大于39字节的字符串时则私用raw编码方式存储，即SDS。

    b, smbstr编码方式

smbstr编码方式是专门保存短字符产的一种编码方式，与raw相似，但会调用一次内存分配函数申请redisobject和sdshdr，连续存储。但它是只读的，当对它修改时类型转换为raw编码方式。

    c, int编码方式

        ptr指向一个整数，当对已int编码方式编码的字符串对象进行append等操作时，会类型转换为sds类型。

    d, 可进行的操作

        在使用命令INCR系列（ INCR, DECR, INCRBY）命令时将字符串作为的原子计数器。

        使用APPEND命令追加字符串。

        将字符串作为GETRANGE 和 SETRANGE的随机访问向量。

        在小空间里编码大量数据, 或者使用 GETBIT 和 SETBIT创建一个Redis支持的Bloom过滤器。

    e, 场景

        String是最常用的一种数据类型，普通的key/value存储都可以归为此类，value其实不仅是String，
也可以是数字。

3，列表

    Redis列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素导列表的头部（左边）或者尾部（右边） LPUSH 命令插入一个新的元素导头部, 而 RPUSH插入一个新元素导尾部.

    redis的列表有两种实现方式ziplist和linkedlist，

    a, ziplist编码方式

        当元素数目小于512个并且每个元素的长度都小于64个字节时使用该编码方式。当插入的元素不满足上述条件则转换为linkedlist编码。

    b, linkedlist是双端链表的实现

    c, 场景分析

        实现最新消息排行等功能。
        Lists的另一个应用就是消息队列，可以利用Lists的PUSH操作，将任务存在Lists中，然后工作线程再用POP操作将任务取出进行执行。

        从时间复杂度的角度来看Redis列表的主要特征是在头和尾的元素插入和删除是固定时间，即便是数以百万计的插入。. 在列表的两端访问元素是非常快的但是如果你试着访问一个非常大的列表的中间的元素是很慢的，因为那是一个O(N)操作。因此list不支持判断某个key是否在列表中这一命令。

4，哈希

    在类似memcache中，结构化的信息打包成 hashmap，在客户端序列化后存储为一个字符串的值（一般是 JSON 格式），比如用户的昵称、年龄、性别、积分等。这时候在需要修改其中某一项时，通常需要将字符串（JSON）取出来，然后进行反序列化，修改某一项的值，再序列化成字符串（JSON）存储回去。操作复杂、也不便于更新修改操作，并发情况。hash完美解决。两种编码方式，ziplist和dict，一个ziplist存放了一个key对应的结构化数据。

    a, ziplist编码方式

       

        类似于列表，档大小和数量不满足时也会转换为dict编码。

    b, dict编码

        这里k和v都是字符串对象

    c, 场景分析

        存储、读取、修改用户的结构化数据

5，集合

    Redis 集合（Set）是一个无序不重复的字符串集合. 你可以以O(1)的时间复杂度 (无论集合中有多少元素时间复杂度都是常量)完成添加，删除，以及测试元素是否存在。有两种编码方式intset和hashtable。

    a, inset编码方式

        所有元素都保存在整数集合中

    b, 场景分析

        多次添加相同的元素，最终在集合里只会有一个元素。因此在添加元素的时候无须检测元素是否存在。

         一个Redis集合支持一些服务端的命令从现有的集合出发去进行集合运算，求交集、并集、差集

         set 的内部实现是一个 value永远为null的HashMap，实际就是通过计算hash的方式来快速排重的，不同于list，可以实现检查某一key是否在set中，因为底层是hashtable，常量复杂度。

        实际应用如计算独立ip，微博共同好友，好友推荐等

6，有序集合

    有序集合是将集合中的元素增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列，集合的成员是唯一的，但是评分可以是重复了。有序集合使用ziplist和skiplist+dict两种编码方式。

    a, ziplist方式

        第一个节点保存元素成员，相邻第二个节点保存score，编码方式类似于哈希的ziplist编码方式。

    b, skiplist+dict编码方式

        zset结构同时包含一个字典和一个跳跃表，skiplist保存了分支从小到大的所有元素，由于跳跃表的查找复杂度较高，因此使用dict结构存成员和分值，查找复杂度为O(1)，而而zrank和zrange命令式则使用skiplist进行范围操作。

     c, 场景分析

        排行榜相关，使用ZADD命令去更新它，使用 ZRANGE命令来得到前多少名的用户，,使用ZRANK命令返回该用户的名词。同时使用ZRANK 和 ZRANGE 可以显示和给定用户分数相同的所有用户。

        来做带权重的队列，如普通消息的score为1，重要消息的score为2，然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行。

        score设为过期时间，需要精准设定过期时间，定期清除过期的数据。

        使用有序集合你可以以非常快的速度（O(log(N))）添加，删除和更新元素。因为元素是有序的, 可以很快的根据评分或者次序来获取一个范围的元素。访问有序集合的中间元素也是非常快的,因此你能够使用有序集合作为一个没有重复成员的智能列表。在有序集合中，可以很快捷的访问一切需要的东西：有序的元素，快速的存在性测试，快速访问集合的中间元素。