Redis五种数据类型的底层实现

简介

Redis的五种数据类型也叫五个数据对象；之前已经介绍了六种数据结构。Redis没有直接使用这些结构来实现键值对数据库，而是使用这些结构来构建对象系统redisObject。该对象系统包括五个数据对象，即字符串对象、列表对象、哈希对象、集合对象和有序集合对象。这五个对象的底层数据代码可以通过命令OBJECT ENCODING查看。

RedisObject结构

typedef结构redisObject {

//类型

无符号类型：4；

//代码

无符号编码：4；

//指向底层实现数据结构的指针

void * ptr

//.

} robj

Redis将数据存储在键值对中，因此对象分为键对象和值对象，也就是说，存储一个键-值键-值对将创建两个对象，一个键对象和一个值对象。

键对象总是字符串对象，值对象可以是五个主要对象中的任何一个。

Type属性存储对象的类型，即字符串、列表、哈希、集合和zset中的一个，可以使用命令type键查看。encoding属性记录了构造所使用的编码，即使用什么样的数据结构来实现底层对象。

该表列出了基础编码常数和相应的OBJECT ENCODING命令的输出。前三项是字符串结构。

我们在保存键值对的时候不会指定对象的编码，但是Redis会根据不同的使用场景为一个对象设置不同的编码，这样可以节省内存，加快访问速度。

字符串对象(string)

对象字符串的底层数据结构实现为简单动态字符串(SDS)和直接存储，但其编码方式可以是int、raw或embstr，区别在于内存结构不同。

（1）int编码

字符串保存一个整数值，这个可以用long类型形式表示，所以直接存储在redisObject的ptr属性中，编码设置为int，如图：

（2）raw编码

如果字符串包含大于32字节的字符串值，请使用简单动态字符串(SDS)结构，并将编码设置为raw。此时内存结构与SDS结构一致，内存分配次数为2次。创建redisObject对象和sdshdr结构，如图所示：

（3）embstr编码

字符串的存储字符串值小于或等于32字节，也使用简单的动态字符串(SDS结构)，但优化了内存结构以存储擦除的字符串。内存分配只能完成一次，可以分配连续的一块空间，如图：

对象摘要：

在Redis中，长整型和双精度型的浮点数首先转换成字符串，然后存储。raw和embstr的编码效果是一样的，但区别在于内存分配和释放，raw两次，embstr一次。Embstr内存块是连续的，可以更好的利用缓存的优势。如果附加字符串，int编码和embstr编码将转换为原始编码。Embstr编码的对象是只读的，一旦被修改，它们将首先被转码为raw。

列表对象(list)

在3.2版本之前：列表对象的代码可以是ziplist和linkedlist之一。

（1） ziplist编码

ziplist编码的hash random的底层实现是压缩列表，每个压缩列表节点保存一个列表元素。

（2）linkedlist编码

链表编码的底层由双端链表实现，每个双端链表节点保存一个字符串对象和每个字符串对象中的一个列表元素。

对象编码转换：

对列表使用ziplist编码需要满足两个条件：第一，所有字符串的长度小于64字节；第二，元素数量少于512个；如果其中任何一个不满足，将使用linkedlist编码。两个条件的个数可以在Redis的配置文件中。

中修改，list-max-ziplist-value选项和list-max-ziplist-entries选项。

3.2版本之后：列表对象的编码quicklist。

quicklist编码

quickList 是 zipList 和 linkedList 的混合体，它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。

Redis 还会对 ziplist 进行压缩存储，使用 LZF 算法压缩，可以选择压缩深度。
quicklist 默认的压缩深度是 0，也就是不压缩。压缩的实际深度由配置参数list-compress-depth决定。为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。如果深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。
ziplist长度：
quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个 ziplist。
ziplist 的长度由配置参数 list-max-ziplist-size 决定。

哈希对象(hash)

哈希对象的编码可以是ziplist和hashtable之一。

（1）ziplist编码

ziplist编码的哈希对象底层实现是压缩列表，在ziplist编码的哈希对象中，key-value键值对是以紧密相连的方式放入压缩链表的，先把key放入表尾，再放入value；键值对总是向表尾添加。

（2）hashtable编码

hashtable编码的哈希对象底层实现是字典，哈希对象中的每个key-value对都使用一个字典键值对来保存。
字典键值对即是，字典的键和值都是字符串对象，字典的键保存key-value的key，字典的值保存key-value的value。

哈希对象编码转换：

• 哈希对象使用ziplist编码需要满足两个条件：一是所有键值对的键和值的字符串长度都小于64字节；二是键值对数量小于512个；不满足任意一个都使用hashtable编码。
• 以上两个条件可以在Reids配置文件中修改hash-max-ziplist-value选项和hash-max-ziplist-entries选项。

集合对象(set)

集合对象的编码可以是intset和hashtable之一。

（1）intset编码

intset编码的集合对象底层实现是整数集合，所有元素都保存在整数集合中。

（2）hashtable编码

hashtable编码的集合对象底层实现是字典，字典的每个键都是一个字符串对象，保存一个集合元素，不同的是字典的值都是NULL；可以参考java中的hashset结构。

集合对象编码转换：

• 集合对象使用intset编码需要满足两个条件：一是所有元素都是整数值；二是元素个数小于等于512个；不满足任意一条都将使用hashtable编码。
• 以上第二个条件可以在Redis配置文件中修改et-max-intset-entries选项。

有序集合对象(zset)

有序集合的编码可以是ziplist和skiplist之一。

（1）ziplist编码

ziplist编码的有序集合对象底层实现是压缩列表，其结构与哈希对象类似，不同的是两个紧密相连的压缩列表节点，第一个保存元素的成员，第二个保存元素的分值，而且分值小的靠近表头，大的靠近表尾。

（2）skiplist编码

skiplist编码的有序集合对象底层实现是跳跃表和字典两种；
每个跳跃表节点都保存一个集合元素，并按分值从小到大排列；节点的object属性保存了元素的成员，score属性保存分值；
字典的每个键值对保存一个集合元素，字典的键保存元素的成员，字典的值保存分值。

为何skiplist编码要同时使用跳跃表和字典实现

• 跳跃表优点是有序，但是查询分值复杂度为O(logn)；字典查询分值复杂度为O(1) ，但是无序，所以结合连个结构的有点进行实现。
• 虽然采用两个结构但是集合的元素成员和分值是共享的，两种结构通过指针指向同一地址，不会浪费内存。

有序集合编码转换：

• 有序集合对象使用ziplist编码需要满足两个条件：一是所有元素长度小于64字节；二是元素个数小于128个；不满足任意一条件将使用skiplist编码。
• 以上两个条件可以在Redis配置文件中修改zset-max-ziplist-entries选项和zset-max-ziplist-value选项。

应用场景

redis一般应用场景

• 缓存会话（单点登录）
• 分布式锁，比如：使用setnx
• 各种排行榜或计数器
• 商品列表或用户基础数据列表等
• 使用list作为消息对列
• 秒杀，库存扣减等

五种类型的应用场景

• String，redis对于KV的操作效率很高，可以直接用作计数器。例如，统计在线人数等等，另外string类型是二进制存储安全的，所以也可以使用它来存储图片，甚至是视频等。
• hash，存放键值对，一般可以用来存某个对象的基本属性信息，例如，用户信息，商品信息等，另外，由于hash的大小在小于配置的大小的时候使用的是ziplist结构，比较节约内存，所以针对大量的数据存储可以考虑使用hash来分段存储来达到压缩数据量，节约内存的目的，例如，对于大批量的商品对应的图片地址名称。比如：商品编码固定是10位，可以选取前7位做为hash的key,后三位作为field，图片地址作为value。这样每个hash表都不超过999个，只要把redis.conf中的hash-max-ziplist-entries改为1024，即可。
• list，列表类型，可以用于实现消息队列，也可以使用它提供的range命令，做分页查询功能。
• set，集合，整数的有序列表可以直接使用set。可以用作某些去重功能，例如用户名不能重复等，另外，还可以对集合进行交集，并集操作，来查找某些元素的共同点
• zset，有序集合，可以使用范围查找，排行榜功能或者topN功能。

总结

在Redis的五大数据对象中，string对象是唯一个可以被其他四种数据对象作为内嵌对象的；

列表（list）、哈希（hash）、集合（set）、有序集合（zset）底层实现都用到了压缩列表结构，并且使用压缩列表结构的条件都是在元素个数比较少、字节长度较短的情况下；

四种数据对象使用压缩列表的优点：
（1）节约内存，减少内存开销，Redis是内存型数据库，所以一定情况下减少内存开销是非常有必要的。
（2）减少内存碎片，压缩列表的内存块是连续的，并分配内存的次数一次即可。
（3）压缩列表的新增、删除、查找操作的平均时间复杂度是O(N)，在N再一定的范围内，这个时间几乎是可以忽略的，并且N的上限值是可以配置的。
（4）四种数据对象都有两种编码结构，灵活性增加。