[大数据]Redis对象详解

五种基本数据类型

Redis支持五种基本数据类型：String，Hash，List，Set，Zset / Sorted Set

首先，读者需要明白，Redis的数据类型是根据 Value来划分的，Key默认全都是String类型。所以以下的文章全都是针对Redis Key Value对中的Value进行讨论的。

• String: redis最基本的类型，与高级程序设计语言中的String大同小异。

  redis 127.0.0.1:6379> SET key "哈哈哈"
  OK
  redis 127.0.0.1:6379> GET key
  "哈哈哈"
  

• Hash：一个键值对集合，类似Java中的HashMap，每一个Key 对应的 Value就是一个Map，Hash特别适合用于存储对象

  redis 127.0.0.1:6379> DEL key
  redis 127.0.0.1:6379> HMSET key field1 "Hello" field2 "World"
  "OK"
  redis 127.0.0.1:6379> HGET key field1
  "Hello"
  redis 127.0.0.1:6379> HGET key field2
  "World"
  

• List：一个简单的字符串列表，也就是说List中的每一个元素都是String类型（此处的String并不单单可以表示字符串，对象通过序列化的方式也可以转变成字符串，常见的像JSON序列化，Redis原生的序列化），类似于Java的LinkedList，并按照插入顺序排序，你可以添加一个元素到列表的头部或者尾部

  redis 127.0.0.1:6379> DEL runoob
  redis 127.0.0.1:6379> lpush runoob redis
  (integer) 1
  redis 127.0.0.1:6379> lpush runoob mongodb
  (integer) 2
  redis 127.0.0.1:6379> lpush runoob rabbitmq
  (integer) 3
  redis 127.0.0.1:6379> lrange runoob 0 10
  1) "rabbitmq"
  2) "mongodb"
  3) "redis"
  

• Set：Redis的Set是String类型的无序集合，类似Java的HashSet，也就是Set中的每一个元素也是String类型的，他的特点是添加、删除、查找的复杂度都是O(1)

  redis 127.0.0.1:6379> DEL runoob
  redis 127.0.0.1:6379> sadd runoob redis
  (integer) 1
  redis 127.0.0.1:6379> sadd runoob mongodb
  (integer) 1
  redis 127.0.0.1:6379> sadd runoob rabbitmq
  (integer) 1
  redis 127.0.0.1:6379> sadd runoob rabbitmq
  (integer) 0
  redis 127.0.0.1:6379> smembers runoob
  
  1) "redis"
  2) "rabbitmq"
  3) "mongodb"
  

• ZSet：有序集合，类似于Java中的TreeMap，但是底层并不是用红黑树实现的，会根据score排序，并且支持范围查询，socre是一个double类型，member是一个String类型（注意，理论上member可以放任意数据，但是一般生产上仅用来存类似id这种数据，如果存一整个对象的话，有可能发生BigKey问题）

  • 添加元素到有序集合中

  zadd key score member 
  

  • 与TreeMap不同的地方在于ZSet不仅可以 用 score 找对应的 member，也可以用 member 找相应的 value

  • redis 127.0.0.1:6379> DEL runoob
    redis 127.0.0.1:6379> zadd runoob 0 redis
    (integer) 1
    redis 127.0.0.1:6379> zadd runoob 0 mongodb
    (integer) 1
    redis 127.0.0.1:6379> zadd runoob 0 rabbitmq
    (integer) 1
    redis 127.0.0.1:6379> zadd runoob 0 rabbitmq
    (integer) 0
    redis 127.0.0.1:6379> ZRANGEBYSCORE runoob 0 1000
    1) "mongodb"
    2) "rabbitmq"
    3) "redis"
    

Redis对象的组成

既然Redis有这些数据类型，那么Redis内部使用时是如何管理这些数据类型的呢？

Redis底层是C语言，那么肯定会有一个 struct 来管理这些数据类型。Redis中的每一个对象都有一个redisObject 结构来表示（这也是本文把基本数据类型称为对象的原因），该结构的属性保存了和对象有关的信息，此处只介绍三个重要的属性，分别是type属性、encoding属性和ptr属性

typedef struct redisObject {
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
}

• 类型：代表该对象的基本数据类型，通过该类型Redis可以确定该对象是哪种基本数据类型

• 编码：encoding属性记录了对象的底层所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现，这个属性的值可以是下表列出的常量的其中一个

  编码常量	编码所对应的底层数据结构
  REDIS_ENCODING_INT	long 类型的整数
  REDIS_ENCODING_EMBSTR	embstr 编码的简单动态字符串
  REDIS_ENCODING_RAW	简单动态字符串
  REDIS_ENCODING_HT	字典
  REDIS_ENCODING_LINKEDLIST	双端链表
  REDIS_ENCODING_ZIPLIST	压缩列表
  REDIS_ENCODING_INTSET	整数集合
  REDIS_ENCODING_SKIPLIST	跳跃表和字典

  各类型可能对应的编码

  类型	编码	对象
  REDIS_STRING	REDIS_ENCODING_INT	使用整数值实现的字符串对象。
  REDIS_STRING	REDIS_ENCODING_EMBSTR	使用 embstr 编码的简单动态字符串实现的字符串对象。
  REDIS_STRING	REDIS_ENCODING_RAW	使用简单动态字符串实现的字符串对象。
  REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的列表对象。
  REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用双端链表实现的列表对象。
  REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的哈希对象。
  REDIS_HASH	REDIS_ENCODING_HT	使用字典实现的哈希对象。
  REDIS_SET	REDIS_ENCODING_INTSET	使用整数集合实现的集合对象。
  REDIS_SET	REDIS_ENCODING_HT	使用字典实现的集合对象。
  REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的有序集合对象。
  REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳跃表和字典实现的有序集合对象。

  对于上表提到的这些数据结构，我会在下文简略的解释。

意义：Redis通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，极大地提升了Redis的灵活性和效率，因为Redis可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

下文便介绍一下各种数据类型的具体实现。

字符串对象

字符串对象的编码可以是int、raw或者embstr。先简单介绍一下字符串对象

SDS

SDS：Simple Dynamic String，简单动态字符串，是Redis里特有的字符串对象，那么为什么Redis不直接使用C语言的字符串呢?

原因就在于C 语言这种简单的字符串表示方式 不符合 Redis 对字符串在安全性、效率以及功能方面的要求。而Redis的SDS具有一些特殊的属性以及策略，这些使得SDS相比于C语言原生的字符串更符合Redis 追求极致响应速度 以及 操作安全性 和功能方面的要求。

我们来看看String类型的定义

struct sdshdr {
    //记录buf数组中已使用字节的数量
    int len;
    
    //记录buf数组中未使用字节的数量
   	int free;
    
    //字节数组，用于保存字符串
    char buf [];
}

C字符串和SDS之间的区别

• C字符串获取长度需要遍历；SDS具有一个len属性，可以直接获取该属性，时间复杂度从O(N) 降低到 O(1)

• C字符串不能很好的杜绝缓冲区溢出的问题，需要程序员手动判断内存；而SDS字符串的API会自动判断该字符串的可用空间能不能满足相应的操作，如果不能满足，Redis会先拓展SDS的空间，然后才会执行对应的操作，比如说拼接操作。

• C字符串修改一次必定要进行内存重分配，而SDS修改字符串并不一定会进行内存重分配，减少了内存重分配的次数，主要与下面两个策略有关

  • 空间预分配：当SDS需要拓展时，除了分配修改必要的空间，还会分配和字符串同样大小的未使用空间，并用SDS字符串 的 free属性记录
  • 惰性空间释放：当SDS 需要缩短时，并不需要真的回收空余空间，而是使用free属性记录下来，以待下次使用

• C字符串只能保存文本数据；SDS可以保存任意二进制数据，因为其底层是字节数组。

C字符串与SDS之间的共性

1. 同样以空字符结尾，所以SDS字符串也能使用一部分C字符串的库函数。

不同编码的区别

int编码

当字符串对象值为整数，并且整数值可以用long类型来表示的时候，Redis直接使用 整数值来保存一个字符串对象。

embstr 和 raw

这两种编码对应的数据结构都是SDS字符串，但是在内存中的存储方式不太一样。

raw编码会调用两次内存分配函数来分别创建redisObject 结构 和sds 结构

而embstr 编码则只调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject 和 sdshdr两个结构

embstr编码的优点：

• 将创建字符串对象所需的内存分配次数从两次降低为一次
• 释放内存时也只需要调用依次内存释放函数
• 由于数据连续，根据空间连续性原则，可以更好的利用缓存带来的优势

embstr编码的缺点：

• 由于地址空间连续，所以该编码的字符串为只读的，如果要修改，就会变成raw编码
• 由于需要连续的空间，所以只适合长度较小的字符串

Redis如何选择编码

• 整数类型使用 int 编码

• 字符串的长度小于等于 39字节 使用embstr编码

• 字符串长度大于 39字节使用 raw 编码

列表对象

列表对象的编码可以是ziplist 或者 linkedlist

linkedlist编码

如果是linkedlist编码，那么其实和Java中的LinkedList的底层实现很相似，都是使用双向链表作为底层实现的，每个双向链表节点都保存了一个字符串对象，并且具有 pre 和 next 指针。

ziplist编码

如果是ziplist编码，那么底层数据结构就会是ziplist 压缩列表这种数据结构，我简单的介绍一下压缩列表。

压缩列表

压缩列表是Redis为了节约内存而开发的，它不需要指针指向节点的地址，而是使用一组连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

读者肯定会很好奇，为什么压缩列表能代替 双向链表 实现列表对象呢？

主要是和以下三点有关：

1. 内存连续
2. 压缩列表的独特构成
3. 压缩列表节点的构成

下面详细介绍一下

内存连续

这是压缩列表在内存中的组成部分，各个部分都是利用的一块连续的内存空间，由于内存连续，所以如果知道了某一段 的长度，就可以直接跳过该段访问下一段，比如 A -> B ，如果已知 A的长度为 300 ，又已知 A的起始地址为 P，那么B的起始地址就为 P + 300。

压缩列表的构成

• zlend：特殊值，用来标记压缩列表的末端
• zlbytes：记录整个压缩列表占用的内存字节数，可以使用它直接访问到zlend
• zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，可以用它访问表尾节点
• zllen：记录了压缩列表的节点数量，使得获取列表数量的操作时间复杂度简化到O(1)，典型的空间换时间的策略
• entry：表示压缩列表的各个节点

通过这些属性值，我们可以只需要O(1)的时间复杂度，完成许多列表的操作，比如获取节点数量，使用zllen；比如访问表尾节点，用起始地址 + zltail属性即可；至此，我们完成了和双向链表一样的获取表头表尾的操作，获取节点数量的操作，那么如何进行节点的遍历呢？依赖于压缩列表节点的构成。

压缩列表节点的构成

压缩列表节点分为三个部分：

• previous_entry_length：前一个节点的长度，从当前节点的起始地址 - 前一个节点的长度，就能访问到前一个节点的起始地址，类似于双向链表的 pre指针
• encoding：记录了节点保存数据的类型以及长度，已知当前节点的长度，自然就可以使用类似访问前一个节点的方法访问下一个节点
• content：保存节点的值，可以有字节数组和整数等类型，长度由encoding的值保存

至此，我们便可以通过节点的 previous_entry_length 和 encoding 属性来进行列表前后的遍历，那么就基本实现了和双向链表一样的功能。

哈希对象

哈希表的编码可以是ziplist或者hashtable

ziplist编码

这里不再介绍ziplist这种数据结构，主要介绍一下哈希对象如何通过ziplist实现

当哈希对象使用ziplist编码时，保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后。

也就是说，当我想获取一个key对应的value时，我只需要两个节点两个节点的遍历这个压缩列表，就能遍历完所有的key，当找到对应的value。

hashtable编码

使用hashtable编码的Hash对象会使用Redis字典作为底层实现

字典

我们先看看Redis中定义的Hash表

typedef struct dictht {
    // 哈希表数组
    dictEntry ** table;
    
    //哈希表大小
    unsigned long size;
    
    //哈希表掩码，等于size - 1 ， 用来计算索引
    unsigned long sizemask;
    
    //已有节点数量
    unsigned long used;
}

从Hash表的结构上来说，我们可以看出来其实和Java 的HashMap实现大同小异。

1. 底层用数组 + 链表实现哈希表
2. 拉链法解决Hash冲突，但是不会发生树化
3. 获取key在数组中的下标也是通过 节点hash值 & sizemask (size - 1) 的方式实现的

再看看Redis 字典的数据结构

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *private;
    //哈希表数组
    dictht ht[2];
    
    //rehash索引，用来表示rehash进度，为-1时代表没有开始Rehash
    int trehashidx;
}

Redis的字典里主要就是包括了一个容量为2的哈希表数组，以及rehash索引，这也是它与Java HashMap一个关键的不同点，也就是不同的Rehash机制。

Rehash

众所周知，传统Hash算法的Rehash一直都是臭名昭著，由于下标通过取余运算获取，一旦扩容，那么所有的节点都会发生Rehash，如此庞大的计算会使得Hash表在一段时间内完全不可用，这对于单线程的Redis无异于是毁灭性的打击，于是Redis采用了渐进式Rehash的优化方法。

过程：

1. 每次Rehash都只对部分旧数据进行Rehash，下一次Rehash开始的位置通过rehash索引来判断
2. 每个节点Rehash的时候，会从第一张表Rehash到第二张表
3. 在Rehash没有完全完成的时候，Redis针对该字典的操作会针对两张哈希表来操作，删除，修改，查找等操作会先对第一张表操作，增加则会直接在第二张表上增加
4. 当Rehash完成之后，用第二张哈希表置换第一张哈希表，然后再把第二张表的指针置空，用以下次扩容

总结：

1. 两张哈希表保证字典在渐进式Rehash的时候，还能正常对外界提供服务
2. rehash索引则保存了rehash的位置，用以下次rehash时寻找节点

集合对象

集合对象的编码可以是intset 或者 hashtable，intset是一个整数集合，如果一个集合中的对象都是整数，那么就可以使用intset作为底层实现，如果是使用hashtable编码，那么集合对象的实现就和Java中HashSet的实现方式类似。

有序集合对象

有序集合可以使用 ziplist 或者 skiplist实现

ziplist实现

类似Hash对象的实现，将一个集合元素通过两个ziplist节点保存，第一个节点保存member，第二个节点保存score。遍历的时候也是两个节点一跳，就可以找到下一个集合元素。

为了实现zset有序的功能，ziplist中的集合元素按分值从小到大排序，并且在插入的时候，也会保证插入的节点处于对应分值大小的位置。

skiplist实现

对于skiplist编码，显而易见就是用跳跃表作为实现的。除了跳跃表之外，还会使用字典。也就是说，底层是使用跳跃表+字典实现的。

为什么还要使用字典？

如果我们使用跳跃表的话，跳跃表是根据score排序的，并且他的查找逻辑也是通过score进行的查找，也就是说，我们可以通过跳跃表，根据对应的score找到对应的member。但是如果是通过member，查找对应的score，我们就无法利用跳跃表快速查找，只能使用线性查找，O(N)级别的遍历跳跃表，在业务层面上来说，这种类似的需求十分常见，比如在排行榜中获取当前用户的积分，所以说如此低效的实现对于Redis而言无疑是一种灾难。

如果我们使用了字典，使用member 为 key，score为value，那么我们就可以通过字典快速的找到一个member对应的score，典型的空间换时间策略。

注意：Redis底层并不是直接使用score作为value，这会使得score的重复存储，所以Redis仅仅让字典的value保存了跳跃表节点的地址。

skiplist

跳跃表的实现比较复杂，大致思路就是通过一些特殊实现，使得能在一个有序链表上进行类似二分查找的查找算法，查找的时间复杂度是O(logN)级别的。此处不再赘述跳表的实现，感兴趣的可以看这几篇文章。

Skip List–跳表（全网最详细的跳表文章没有之一）
Redis跳跃表的Java简单实现

至于为什么Redis不使用红黑树而是要使用跳表来实现有序集合，这里给出几点原因

• 便于实现范围查询，对于ZSet这种数据类型来说范围查询的场景十分常见
• 代码实现简单
• 更加灵活，可以通过改变索引构建策略（随机策略），有效平衡执行效率和内存消耗

小结

程序员们除了关注Redis的API调用之外，也应该了解一些Redis底层实现，可以更好的帮助我们处理复杂业务的Redis设计，从而使得我们合理且高效的利用缓存这一高并发利器。

参考文献：

1. 《Redis设计与实现》——黄健宏
2. 《Redis开发与运维》——付磊 / 张益军
3. 《菜鸟教程》——Redis基础教程