有时候会好奇，为什么redis的string类型的字符串可以实现自增1，还可以实现一些数字相关的计算，而zset又可以实现打分和排名，如果它们仅仅是键值对的形式，还能这么方便的进行操作么？正如List的底层数据结构是双向链表设计一样，redis的所有数据结构也都是基于我们基础数据结构或基础数据结构的封装而实现的。今天这篇blog就来学习下redis的数据结构底层实现。

数据对象与数据编码

Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。所以我们看到的Redis提供的五种数据结构可以理解为五种数据对象，其底层实现实则依赖一些更加具体的数据编码方式。

数据对象

五种数据结构前文已有所涉及【Redis从入门到放弃系列 三】Redis数据结构概述：

• Redis 字符串(String)
• Redis 哈希(Hash)
• Redis 列表(List)
• Redis 集合(Set)
• Redis 有序集合(sorted set)

当然Redis的key都是string类型的，以上各类型说的其实都是value的类型，以下是对象的几个优点：

• 通过这五种不同类型的对象，Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。适配场景
• 使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率，提升效率
• Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放，内存回收
• Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存，节约内存
• Redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了maxmemory功能的情况下，空转时长较大的那些键可能会优先被服务器删除，内存回收

每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。Redis中的每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性：

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

• 对象的type属性记录了对象的类型，REDIS_STRING、REDIS_HASH、REDIS_LIST、REDIS_SET、REDIS_ZSET，对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种
• 对象的encoding属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现，接下来会详细介绍下使用的数据编码
• 对象的ptr指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定

也就是一个对象包含自身的数据结构属性，实际使用的编码类型以及数据对象对实际数据编码的指针。

数据编码

在Redis中会涉及很多数据结构，比如SDS，双向链表、字典、压缩列表、整数集合、跳跃表等。数据编码有如下几种：

数据对象和编码对应关系

每种类型的对象都至少使用了两种不同的编码，在内容长短发生变化的时候数据对象会自动切换适合的数据编码，且切换后不可逆

数据编码的分场景切换

每种数据对象由至少两种数据编码实现，但某个key在同一时间一定是某一个数据编码，数据编码会随着数据对象存储数据的变化而发生不可逆的切换

String类型对象

由上表可知，String类型有三种展现形式：int、embstr的sds实现，raw的sds实现，在不同的场景下使用不同的展现形式

编码类型[int/embstr sds->raw sds]

String类型对象包含如下的几种转换场景：

• 整数场景：如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码设置为int。需要注意的是可以用long double类型表示的浮点数在Redis中也是作为字符串值来保存的
  
  
• embstr的sds场景：如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值
  
  
• raw的sds场景：如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw
  
  

以上提到了两个编码方式embstr和raw，区别是什么呢？

• 相同点：embstr编码是专门用于保存短字符串的一种优化编码方式，这种编码和raw编码一样，都使用redisObject结构和sdshdr结构来表示字符串对象
• 不同点：raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr两个结构

既然创造了embstr，一定是有优势的：

• 内存分配次数少：embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次
• 内存释放快：释放embstr编码的字符串对象只需要调用一次内存释放函数，而释放raw编码的字符串对象需要调用两次内存释放函数
• 缓存利用率高：因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势

编码转换

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换为raw编码的字符串对象

1. int编码的字符串对象，如果我们向对象执行了一些命令，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对象的编码将从int变为raw
2. embstr编码的字符串对象实际上是只读的。当我们对embstr编码的字符串对象执行任何修改命令时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。因为这个原因，embstr编码的字符串对象在执行修改命令之后，总会变成一个raw编码的字符串对象

以下是一些常用操作的对应关系：

List类型对象

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

编码类型[ziplist->linkedlist]

举个例子，如果我们执行以下RPUSH命令，那么服务器将创建一个列表对象作为numbers键的值：

• ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点（entry）保存了一个列表元素。
  
  
• linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点（node）都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素
  
  

linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象，字符串对象是Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

编码转换

当列表对象可以同时满足以下两个条件时，列表对象使用ziplist编码，对于使用ziplist编码的列表对象来说，当使用ziplist编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有列表元素都会被转移并保存到双端链表里面，对象的编码也会从ziplist变为linkedlist

• 列表对象保存的所有字符串元素的长度都小于64字节
• 列表对象保存的元素数量小于512个

不能满足这两个条件的列表对象需要使用linkedlist编码，以上两个条件的上限值是可以通过配置文件修改的。以下是一些常用操作的对应关系：