这个面试题主要想了解我们对Redis有没有去深入的了解和理解它底层的原理。

Redis是由C语言编写的。Redis支持5种数据类型，以K-V形式进行存储，K是String类型的，V支持5种不同的数据类型，分别是：string，list，hash，set，sorted set，每一种数据结构都有其特定的应用场景。从内部实现的角度来看是如何更好的实现这些数据类型。Redis底层数据结构有以下数据类型：简单动态字符串（SDS），链表，字典，跳跃表，整数集合，压缩列表，对象。接下来，了解下Redis是怎么通过这些数据结构来实现value的5种类型的。

简单动态字符串（simple dynamic string SDS）

String的数据类型是由SDS实现的。Redis并没有采用C语言的字符串表示，而是自己构建了一种名为SDS的抽象类型，并将SDS作为Redis的默认字符串表示。

redis>SET msg "hello world"
OK

上边设置key=msg，value=hello world的键值对，它们的底层存储是：键（key）是字符串类型，其底层实现是一个保存着“msg”的SDS。值（value）是字符串类型，其底层实现是一个保存着“hello world”的SDS。

注意：SDS除了用于实现字符串类型，还被用作AOF持久化时的缓冲区。

为什么要使用SDS：

我们一定会思考，redis为什么不使用C语言的字符串而是费事搞一个SDS呢，这是因为C语言用N+1的字符数组来表示长度为N的字符串，这样做在获取字符串长度，字符串扩展等操作方面效率较低，并且无法满足redis对字符串在安全性、效率以及功能方面的要求。

1.获取字符串长度（SDS O（1））

在C语言字符串中，为了获取一个字符串的长度，必须遍历整个字符串，时间复杂度为O(1)，而SDS中，有专门用于保存字符串长度的变量，所以可以在O（1）时间内获得。

2.防止缓冲区溢出

C字符串，容易导致缓冲区溢出，假设在程序中存在内存紧邻的字符串s1和s2，s1保存redis，s2保存MongoDB

如果我们现在将s1 的内容修改为redis cluster，但是又忘了重新为s1 分配足够的空间，这时候就会出现以下问题：

因为s1和s2是紧邻的，所以原本s2 中的内容已经被S1的内容给占领了，s2 现在为 cluster，而不是“Mongodb”。而Redis中的SDS就杜绝了发生缓冲区溢出的可能性。

当我们需要对一个SDS 进行修改的时候，redis 会在执行拼接操作之前，预先检查给定SDS 空间是否足够（free记录了剩余可用的数据长度），如果不够，会先拓展SDS 的空间，然后再执行拼接操作。

3.减少扩展或收缩字符串带来的内存重分配次数

当字符串进行扩展或收缩时，都会对内存空间进行重新分配。

1. 字符串拼接会产生字符串的内存空间的扩充，在拼接的过程中，原来的字符串的大小很可能小于拼接后的字符串的大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。

2. 字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出来的空间就成为了内存泄露。

比如：字符串"redis"，当进行字符串拼接时，将redis+cluster=13，会将SDS的长度修改为13，同时将free也改为13，这意味着进行预分配了，将buffer大小变为了26。这是为了如果再次执行字符串拼接操作，如果拼接的字符串长度<13,就不需要重新进行内存分配了。

通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。通过惰性空间释放，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能有的增长操作提供了优化。

4.二进制安全

C字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。

但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。但是，SDS依然可以兼容部分C字符串函数。

链表

链表是list的实现方式之一。当list包含了数量较多的元素，或者列表中包含的元素都是比较长的字符串时，Redis会使用链表作为实现List的底层实现。此链表是双向链表：

typedef struct listNode{
 struct listNode *prev;
 struct listNode * next;
 void * value; 
}
typedef struct list{
 //表头节点
 listNode * head;
 //表尾节点
 listNode * tail;
 //链表长度
 unsigned long len;
 //节点值复制函数
 void *(*dup) (void *ptr);
 //节点值释放函数
 void (*free) (void *ptr);
 //节点值对比函数
 int (*match)(void *ptr, void *key);
}

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

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。

在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。在C语言中，并没有这种数据结构，但是Redis 中构建了自己的字典实现。

redis > SET msg "hello world"
OK

Redis本身的K-V存储就是利用字典这种数据结构的，另外value类型的哈希表也是通过这个实现的。

哈希表dicy的定义为：

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

我们可以想到对比Java hashMap的实现方式，在dictht中，table数组的类型是：

typeof struct dictEntry{
 //键
 void *key;
 //值
 union{
 void *val;
 uint64_tu64;
 int64_ts64;
 }
 struct dictEntry *next;
 
}

我们存入里面的key 并不是直接的字符串，而是一个hash 值，通过hash 算法，将字符串转换成对应的hash 值，然后在dictEntry 中找到对应的位置。

这时候我们会发现一个问题，如果出现hash 值相同的情况怎么办？Redis 采用了链地址法来解决hash冲突。这与hashmap的实现类似。

注意：Redis又在dictht的基础上，又抽象了一层字典dict，其定义为：

typedef struct dict {
 // 类型特定函数
 dictType *type;
 // 私有数据
 void *privedata;
 // 哈希表
 dictht ht[2];
 // rehash 索引
 in trehashidx;
 
}

type 属性 和privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。

ht 属性是一个包含两个项（两个哈希表）的数组，如图：

解决hash冲突：采用链地址法来实现。

扩充Rehash：　随着对哈希表的不断操作，哈希表保存的键值对会逐渐的发生改变，为了让哈希表的负载因子维持在一个合理的范围之内，我们需要对哈希表的大小进行相应的扩展或者压缩，这时候，我们可以通过 rehash（重新散列）操作来完成。其实现方式和hashmap略有不同，因为dict有两个hash表dictht，所以它是通过这两个dictht互相进行转移的。

比如：

上图这种情况，代表要进行扩容了，所以就要将ht[0]的数据转移到ht[1]中。ht[1]创建为2*ht[0].size大小的，如下图：

将ht[0]释放，然后将ht[1]设置成ht[0]，最后为ht[1]分配一个空白哈希表：

其实上边的扩容过程和Java 的HashMap具体的扩容实现方式还是挺像的。

渐进式rehash：在实际开发过程中，这个rehash 操作并不是一次性、集中式完成的，而是分多次、渐进式地完成的。采用渐进式rehash 的好处在于它采取分而治之的方式，避免了集中式rehash 带来的庞大计算量。

渐进式rehash 的详细步骤：

1、为ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表

2、在几点钟维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash 开始

3、在rehash 进行期间，每次对字典执行CRUD操作时，程序除了执行指定的操作以外，还会将ht[0]中的数据rehash 到ht[1]表中，并且将rehashidx加一

4、当ht[0]中所有数据转移到ht[1]中时，将rehashidx 设置成-1，表示rehash 结束

跳跃表

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键（sorted Sets），另外一个是在集群节点中用作内部数据结构。

其实跳表主要是来替代平衡二叉树的，比起平衡树来说，跳表的实现要简单直观的多。

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速查找访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 ——查找、删除、添加等操作都可以在O（logn）期望时间下完成。

Redis 的跳跃表 主要由两部分组成：zskiplist（链表）和zskiplistNode （节点）：

typedef struct zskiplistNode{
　　　//层
 struct zskiplistLevel{
　　　　　//前进指针
 struct zskiplistNode *forward;
　　　　//跨度
 unsigned int span;
 } level[];
　　//后退指针
 struct zskiplistNode *backward;
　　//分值
 double score;
　　//成员对象
 robj *obj;
}

1、层：level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。level数组的每个元素都包含：前进指针：用于指向表尾方向的前进指针，跨度：用于记录两个节点之间的距离

2、后退指针：用于从表尾向表头方向访问节点

3、分值和成员：跳跃表中的所有节点都按分值从小到大排序（按照这个进行排序的，也就是平衡二叉树（搜索树的）的节点大小）。成员对象指向一个字符串，这个字符串对象保存着一个SDS值（实际存储的值）

typedef struct zskiplist {
 //表头节点和表尾节点
 structz skiplistNode *header,*tail;
 //表中节点数量
 unsigned long length;
 //表中层数最大的节点的层数
 int level;
 
}zskiplist;

从结构图中我们可以清晰的看到，header，tail分别指向跳跃表的头结点和尾节点。level 用于记录最大的层数，length 用于记录我们的节点数量。

• 跳跃表是有序集合的底层实现之一
• 主要有zskiplist 和zskiplistNode两个结构组成
• 每个跳跃表节点的层高都是1至32之间的随机数
• 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的对象必须是唯一的
• 节点按照分值的大小从大到小排序，如果分值相同，则按成员对象大小排序

怎么使用跳表来实现O（logn）的增删改查？？

其实跳表的实现原理，我们可以结合二分法来看。

比如上图，我们要查找55，如果通过遍历，则必须得从头遍历到最后一个才能找到，所以在数组实现中，我们可以使用二分法来实现，但是在链表中，我们没办法直接通过下标来访问元素，所以一般我们可以用二叉搜索树，平衡树来存储元素，我们知道跳表就是来替代平衡树的，那么跳表是如何快速查询呢？看下图：

从上图我们可以看到，我们通过第4层，只需一步便可找到55，另外最耗时的访问46需要6次查询。即L4访问55，L3访问21、55，L2访问37、55，L1访问46。我们直觉上认为，这样的结构会让查询有序链表的某个元素更快。这种实现方式跟二分很相似，其时间复杂度就是O(logn)。其插入，删除都是O（logn）。

我们可以看到，redis正是通过定义这种结构来实现上边的过程，其层数最高为32层，也就是他可以存储2^32次方的数据，其查找过程与上图很类似。

整数集合（Intset）

Redis 设计与实现》 中这样定义整数集合：“整数集合是集合建(sets)的底层实现之一，当一个集合中只包含整数，且这个集合中的元素数量不多时，redis就会使用整数集合intset作为集合的底层实现。”

我们可以这样理解整数集合，他其实就是一个特殊的集合，里面存储的数据只能够是整数，并且数据量不能过大

typedef struct intset{
 //编码方式
 uint32_t enconding;
 // 集合包含的元素数量
 uint32_t length;
 //保存元素的数组 
 int8_t contents[];
 
}

整数集合是集合建的底层实现之一

整数集合的底层实现为数组，这个数组以有序，无重复的范式保存集合元素，在有需要时，程序会根据新添加的元素类型改变这个数组的类型.

压缩列表

压缩列表是列表键（list）和哈希键（hash）的底层实现之一。当一个列表键只有少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，那么Redis 就会使用压缩列表来做列表键的底层实现。

1、zlbytes:用于记录整个压缩列表占用的内存字节数

2、zltail：记录要列表尾节点距离压缩列表的起始地址有多少字节

3、zllen：记录了压缩列表包含的节点数量。

4、entryX：要说列表包含的各个节点

5、zlend：用于标记压缩列表的末端

压缩列表是一种为了节约内存而开发的顺序型数据结构

压缩列表被用作列表键和哈希键的底层实现之一

压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值

添加新节点到压缩列表，可能会引发连锁更新操作

转载自：

https://blog.csdn.net/u013679744/article/details/79195563