Redis的5种数据类型

Posted on | In , | | 浏览 次
Words count in article: 2.6k | Reading time ≈ 9

前言

Redis是一个key-value存储系统，由C语言编写。

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键(key对象)，另一个对象用作键值对的值(value对象)。

Redis的每种数据类型全都是套用一种结构的对象(redisObject)。

Redis支持5种对象类型，分别是字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset)，redisObject使用type字段记录自身属于哪种类型。

而每种对象类型至少使用了两种底层数据结构来实现，redisObject使用编码字段（encoding字段）记录了自己使用的是哪种底层数据结构实现。而*ptr指针则会直接指向这个对应的底层数据结构。

每个对象会用到的编码以及对应的数据结构详见下表，即共8种底层数据结构：

Redis中的键，都是用字符串对象来存储的，即对于Redis数据库中的键值对来说，键总是一个字符串对象，而值可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象中的其中一种。

Redis的8种数据结构，我们已经在Redis的8种底层数据结构一文中有过介绍，本文我们来讲Redis支持的5种对象类型

统一的对象——redisObject

Redis的五种数据类型全都是套用一种结构的对象 ：

redisObject对象实现了基于引用计数技术的内存回收机制和对象共享机制。

因为redis是k-v键值对的缓存数据库，所以每一次我们新建一个k-v键值对时，redis都会创建两个redisObject对象，键总是字符串对象。

这几个属性我们拆开一个个讲：

  • Type

    • redisObject对象根据type的不同会有五种类型，这个字段就是用来标记不同类型的对象的。
    • 命令TYPE keyname 可以得到这个type属性。
    • 具体值见下表：
    • Redis基于类型的多态就是根据type字段来判断的，如DEL,EXPIRE等命令可以针对任何类型的键操作，而SET/GET只能针对字符串键操作，HDEL,HSET只能针对哈希键操作等，这种针对特定类型的命令实现，其实就是在执行命令前先检查一下这个type值。

  • Ptr内存指针

    • Ptr是一个指针，用来指向对象的底层数据结构。

  • Encoding

    • 对象ptr指针指向对象的底层实现数据结构，而到底取用哪个数据结构，则在encoding中标记。
    • 后续Redis命令在针对对象进行操作时，也会根据encoding自动选择合适的函数，这是Redis命令的多态。
    • 下面是encoding的字面值和各种数据结构的对应：
    • 上图中值得注意的是 “跳跃表和字典”。其实在redis中，在使用跳跃表时（其实也就用于有序集合），总会辅助一个字典来提升效率的。这时字典的k-v会分别保存一个元素的成员地址和分值地址。跳跃表和字典的指针共同指向一个数据，这样既不会占用内存，也能利用字典实现 常数级的 定位查找。

  • Refcount

    • Refcount是redisObject对象的引用计数器，redis的内存回收是引用计数法，规则如下：

      • 当一个新对象创建时，refcount被设置为1。
      • 当对象被一个程序引用时，refcount +1
      • 不再被某个对象引用时，refcount – 1
      • Refcount为0时，对象被释放

    • Refcount的功能为redis的对象共享提供了可能性，为了节约内存，Redis中大量使用了指针，前面就说过，跳跃表和字典的结合中就大量用到了内存共享。他们相互对应的节点中，指针被指向了同一个对象。

    • 比如为键A新创建了一个整数值为100的字符串对象C，如果键B的值也是100，那么value指针就会指向C，C对象的refcount+1

    • 限于cpu时间的限制，redis只对包含整数值的字符串对象进行共享。

  • Lru

    • Lru属性记录了该对象最后一次被命令访问的时间
    • 通过它，Redis可以得到这个对象的闲置时间，从而在服务器被占用的内存大小超过maxmenmory时，空转时间长的对象会被优先释放。

1 字符串对象

字符串对象的编码可以是int、raw或者embstr。或者说，字符串对象的encoding只能是REDIS_ENCODING_INT，REDIS_ENCODING_EMBSTR和REDIS_ENCODING_RAW。

场景 prt和encoding的值
如果保存的字符串是整数值，并且这个整数值可以用long类型来表示 Ptr属性中，void*会转化成long，encoding改为REDIS_ENCODING_INT
保存的字符串不是整数值，且长度大于39字节（包含可以用long double 类型保存的浮点数） Ptr属性中，void*会转化成SDS，encoding为REDIS_ENCODING_RAW
保存的字符串保存的字符串不是整数值，且长度小于等于39字节 Ptr属性中，void*会转化成embstr，encoding为REDIS_ENCODING_EMBSTR

下图展示了一个当ptr指向SDS时的字符串对象的结构：

注意：当字符串改变，直到不满足上述各自条件时，embstr和int会被转换为raw类型。

注意：Embstr实际上是只读的，因为redis没有为它编写任何的修改函数，所以对它进行任何操作，它都会先转换为raw，然后再执行命令，且不会变回来。

2 列表对象

列表对象的编码可以是压缩链表ziplist或者双端链表linkedlist，encoding取值REDIS_ENCODING_ZIPLIST或者REDIS_ENCODING_LINKEDLIST。

场景 prt和encoding的值
当列表保存的所有字符串元素的长度都小于64字节，且元素的数量小于512 Ptr指向一个ziplist，encoding改为REDIS_ENCODING_ZIPLIST
否则 Ptr指向一个linkedlist，encoding改为REDIS_ENCODING_LINKEDLIST

当列表对象被改变，使其无法满足上述条件时，ziplist会向linkedlist迁移

2.1 列表对象中的Ziplist

  • Ziplist是一种压缩链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。

  • 当列表对象元素不大，每个元素也不大的时候，就采用Ziplist存储。

  • 但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性，插入的复杂度是O(N)，即每次插入都会重新进行realloc。

  • 如下图所示，对象结构中ptr所指向的就是一个Ziplist。整个Ziplist只需要malloc一次，它们在内存中是一块连续的区域。

2.2 列表对象中的Linkedlist

  • linkedlist是一种双向链表。它的结构比较简单，节点中存放pre和next两个指针，还有节点相关的信息。

  • 当每增加一个node的时候，就需要重新malloc一块内存。

3 哈希对象

哈希对象的底层实现可以是ziplist或者dict。Encoding的值可以是压缩链表REDIS_ENCODING_ZIPLIST或者字典REDIS_ENCODING_HT


场景 prt和encoding的值
对象保存的所有键值对的键和值的字符串长度都小于64字节，且键值对数量小于512 Ptr指向一个ziplist，encoding改为REDIS_ENCODING_ZIPLIST
否则 Ptr指向一个dict，encoding改为REDIS_ENCODING_HT

3.1 哈希对象中的ziplist

  • ziplist中的哈希对象是按照key1,value1,key2,value2这样的顺序存放来存储的。

  • 新的键值插入表尾，先是key节点，紧接着value节点。因此同一键值对的两个节点总是紧挨在一起，key在前，value在后。

  • 先添加的k-v靠近表头，后添加的靠近表尾，当对象数目不多且内容不大时，这种方式效率是很高的。

3.2 哈希对象中的dict

之前已经介绍过dict了，字典中，dicht[0] 是用于真正存放数据，dicht[1]一般在哈希表元素过多进行rehash的时候用于中转数据。

dictht中的table用于真正存放元素，每个key/value对用一个dictEntry表示，放在dictEntry数组中。

4 集合对象

集合对象的编码可以是intset或者dict。Encoding可以是整数集合REDIS_ENCODING_INTSET或者字典REDIS_ENCODING_HT。


场景 prt和encoding的值
当集合对象保存的所有元素都是整数值，且元素数量不超过512个 Ptr指向一个intset，encoding改为REDIS_ENCODING_ZIPLIST
否则 Ptr指向一个dict，encoding改为REDIS_ENCODING_HT

注意：当使用哈希表作为集合对象的底层实现时，字典的每一个键都是一个字符串对象，用来保存集合元素，而字段的值都被设置为null。联想一下JAVA的keySet，这方式跟set和hashmap的关系是一样的。

5 有序集合对象

有序集合的编码可能两种，一种是ziplist，另一种是skiplist与dict的结合。


场景 prt和encoding的值
有序集合保存的元素数量小于128，且所有成员的长度都小于64字节 Ptr指向一个ziplist，encoding改为REDIS_ENCODING_ZIPLIST
否则 Ptr指向一个skiplist和dict的结合体，encoding改为REDIS_ENCODING_SKIPLIST

4.1 有序集合对象中的ziplist

  • ziplist作为集合和作为哈希对象是一样的，member和score顺序紧凑的存放。
  • 按照score从小到大顺序排列。它的结构不再复述。

4.2 有序集合对象中的跳跃表和字典合用

前面讲过：
在使用跳跃表时（其实也就用于有序集合），总会辅助一个字典来提升效率的。这时字典的k-v会分别保存一个元素的成员地址和分值地址。跳跃表和字典的指针共同指向一个数据，这样既不会占用内存，也能利用字典实现常数级的定位查找。

例如：

  • 如果我们只使用字典，那么虽然我们可以以O(1)复杂度查找成员的分值，但是因为字典以无序的方式存储，所以在执行注入zrank之类的范围型命令时，还需要重排序。至少需要O(NlogN)的时间复杂度和O(N)的空间复杂度。

  • 反之，我们查找分值这一操作，将需要O(logN)的复杂度。

0%