周末本来不想学习，看完人民的名义没事干，翻了翻刚买的Redis设计与实现这本书，就像追剧一样把第一部分看完了，这本书写的真是不错。
一、Redis简介
Redis作为著名的非关系型数据库，有着如下几个特点
- 以键值对存储
- 有字符串，列表，哈希，集合和有序集合五中数据类型
- 对这些类型都可以原子操作
- 单进程单线程运行
- 内存中运行，也支持持久化，有RDB和AOF两种方式
对于上面说到的五中数据类型，在redis内部有着不同的实现，也就是说在redis中有着自己定义的数据结构。
二、Redis中的数据结构
redis内部是C语言写的，所以没有仔细阅读源码，但是对于其中比较基础的数据结构还是可以看懂的，redis中的数据结构主要有以下几种：
- 简单动态字符串
- 链表
- 字典
- 跳跃表
- 整数集合
- 压缩列表
1、简单动态字符串SDS
字符串应该是redis中最常用的数据结构了，在C语言中，字符串是以空字符结尾的字符数组。在redis中，没有直接采用C中的字符串，而是自己构建了一种名为简单动态字符串的抽象类型，作为字符串的默认字符表示。
1.1、SDS的实现
SDS全称是Simple Dynamic String，即简单动态字符串，因为redis是C语言写的，所以在里面的数据结构都是通过struct来定义的，因为没怎么用过C语言，所以就不贴代码了，简单的以Java类的角度，分析一下它的内部属性。
SDS中只有两个int属性和一个char[]数组：
- len：记录buf数组中已经使用字节的数量，等于SDS所保存字符串的长度
- free：记录buf数组中未使用字节的数量
- buf数组：字节数组，用于保存字符串
1.2、SDS与C字符串的区别
redis自己定义了SDS而没有直接使用C中的字符串主要是出于以下几点的考虑：
获取字符串长度操作：
通过len属性来记录长度，可以在O(1)时间获取长度，而原始的时间复杂度为O(n)
杜绝缓冲区溢出
因为字符串不记录长度，所以拼接操作的时候可能会造成缓冲区溢出。
而SDS修改前会先检查，如果空间不够则先扩展空间在操作
减少修改字符串带来的内存重分配次数
二进制安全
C中字符串必须符合某种编码，并且除了结尾，中间不能有空字符，导致不能保存图像音频压缩文件等二进制数据。
而SDS则可以保存任意的二进制文件
兼容部分C字符串函数
2、链表
redis中的链表就是一种双端链表，类似于Java中的LinkedList，它是列表建的底层实现之一。
2.1、链表的实现
首先就是链表结点，listNode(在Java中类名都是直接大写的，C中竟然第一个小写)，三个属性:
- prev：指向前置结点
- next：指向后置结点
- value：结点的值，在C中是void的，说明可以保存不同类型的值
然后就是链表list，由多个listNode组成，有一下介个属性和方法：
- head：链表的头结点
- tail：链表的尾结点
- len：链表中结点的数量
- 还有几个函数：复制结点，释放结点和对比结点值
感觉和Java中的LinkedList基本一致。
3、字典
字典是哈希键的底层实现之一，并且它在redis中使用很广泛，因为作为键值对存储的数据库，redis的数据库就是以字典来作为底层实现的。
3.1、字典的实现
redis中字典的实现也是采用拉链法，table数组中存储结点，结点通过next指针指向下一个，和Java中的基本一样，当然也有几点区别，主要介绍下几个有区别的地方：
- 字典结构dict有两个哈希表，ht[0]和ht[1]，前者是正常使用，后者用于rehash也就是扩容的时候使用
- 有一个属性rehashindx，下面再rehash的地方详细介绍
3.2、哈希算法
redis中的hash算法采用的是MurmurHash2算法。
3.3、rehash
rehash就是分为扩展和收缩两个操作，使负载因子维持在一个合理的范围之内。具体的步骤如下：
- 为字典的ht[1]分配空间，空间大小取决于是要扩展还是要收缩，大小保证是2的幂
- 将ht[0]中的所有键值对rehash到ht[1]中
- 当ht[0]中所有键值对都迁移到ht[1]中之后，释放ht[0]的空间，将ht[1]设置为ht[0]，并在ht[1]创建一个空白的哈希表为下次rehash做准备
3.4、渐进式rehash
上面提到的第二个步骤，将ht[0]中的所有键值对rehash到ht[1]中，并不是一次性完成的，而是多次，渐进式完成，类似于Java中的ConcurrentHashMap。虽然不涉及到线程安全，但是由于哈希表里面的数据量可能非常大，一次性复制所有的键值对可能会很长的时间，进而造成服务器在一段时间内停止服务。
渐进式rehash的步骤如下：
- 上面提到字典中有一个变量rehashindx
- 如果它的值为-1，说明rehash不在进行。
- 当它的值为0时，rehash正式开始
- 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作，还会顺带将ht[0]哈希表rehashindx索引上的所有键值对rehash到rehash到ht[1]中，完成后再将rehashindx加一
- 当ht[0]中所有键值对都迁移到ht[1]中之后，程序将rehashindx设置为-1，表示rehash已经完成
采用分而治之的方式，将rehash的工作均摊到每个操作之上，避免了一次性rehash庞大的工作量，有点类似于ConcurrentHashMap中多个线程完成rehash的思想，但是它们之间还是不一样的，因为ConcurrentHashMap是由多个线程共同完成rehash。
还有一点需要注意的就是，在rehash进行过程之中，字典会同时使用ht[0]和ht[1]两个哈希表。
4、跳跃表
跳跃表是有序集合键的底层实现之一。它支持平均O(longN)，最坏O(N)复杂度的结点查找。
4.1、SkipList简介
目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep，这些数据结构都可以实现logn的查找插入性能，但是它们的实现一般都比较复杂，一提到画红黑树我就想到当年的算法课。
而跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。目前开源软件 Redis 和 LevelDB 都有用到它。
跳表的性质
跳表具有如下性质：
- 由很多层结构组成
- 每一层都是一个有序的链表
- 最底层(Level 1)的链表包含所有元素
- 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
- 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
Java中的SkipList
Java中没有定义SkipList，但是在Concurrent包中的ConcurrentSkipListMap和ConcurrentSkipListSet，它们底层都是使用的基于CAS来构建的SkipList。
对于他们的使用：
- ConcurrentSkipListSet，用于存储有序元素
- 如果是单线程，则直接使用TreeMap即可，它是采用红黑树实现的
- 如果多线程并且并发量不大，可以采用Collections.synchronizedSortedMap()来包装TreeMap
- 如果并发量很大，则直接使用ConcurrentSkipListSet毕竟他是专门为这个设计的。
ConcurrentSkipListMap，存储元素不一定有序
- 如果数据量一定，可以用ConcurrentSkipListMap
- 如果数量很大，那么应该采用ConcurrentHashMap
- 毕竟ConcurrentSkipListMap是基于排序的，而ConcurrentHashMap是基于hash的专门用于索引的。从redis中有序集合的底层实现中也可以发现，使用一个字典和一个跳表结合起来，使得查找和范围操作都尽可能的快。
4.2、redis中的跳跃表实现
redis中跳跃表也是基于上面的思想：
由zskiplist和zsliplistNode组成。
zskiplist用于保存跳跃表的头结点、为节点和长度信息
zsliplistNode则用于表示跳跃表的结点，包括层、前进指针、后退指针、跨度、分值和成员对象。
redis中跳跃表的长度固定在1到32之间。
多个结点可以包含相同的分值，但是每个结点的成员对象必须是唯一的
跳跃表按照分之的大小进行排序，如果分值相同，就按照成员对象的大小进行排序
5、整数集合
整数集合是集合键的底层实现之一，当一个集合值包含整数值元素，并且这个集合的元素数量不多时，redis就会使用整数集合作为集合键的底层实现。
整数集合(intset)是redis中用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t，int32_t或者int_64t的整数值，并且保证集合中不会出现重复元素。
5.1、整数集合的实现
intset结构中共有三个成员：
- encoding：编码方式，决定了保存元素的数组中元素的类型
- length：集合包含元素的数量
- contents[]数组：保存元素的数组，元素类型由encoding决定，各个元素按从小到大有序排列，并且不包含重复元素。
5.3、升级与降级
升级就是当向集合中添加一个新的元素，而这个元素所占的空间比现在所有的元素类型都要长，这个时候就要进行升级操作。比如开始数组是16位的，突然加入一个32位的元素后，整个数组都要变成32位的。
这样有两个好处：
- 提升灵活性：保证数组所有元素的类型都相同
- 节省内存：如果数组中元素都比较小，那么就用16位的存储，而不是直接用64位，节省内存。
关于降级，一旦升级以后，就无法降级。
6、压缩列表
压缩列表是列表键和哈希键的底层实现之一。当列表建值包含少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，你们redis就会使用压缩列表来做列表建的底层实现。
所以压缩列表是redis为了节约内存而开发出来的，它由一系列特殊编码的连续内存块组成的顺序性数据结构。一个压缩列表可以包含任意多个结点，每个结点可以保存一个字节数组或者一个整数值。
三、Redis中的对象
在前面介绍了redis内部定义的几种数据结构，但它们并没有直接的构成键值对数据库，redis是基于这些数据结构创建了一个对象系统，也就是用户用到的五中数据结构：
- 字符串对象
- 列表对象
- 哈希对象
- 集合对象
- 有序集合对象
每种对象都用到了至少一种前面介绍的数据结构。
redis使用对象来表示数据库中的键值对，每次当我们创建一个新的键值对时，至少会创建两个对象，键对象和值对象。
1、对象的实现
对象在redis中是用redisObject这种数据结构来表示的，它有很多属性，和保存数据相关的有三个属性：
type：类型
表示对象的类型，键对象都是字符串对象，而值对象可以是上面列出的那五种
上面介绍每个数据结构时都提到是字符串键或者哈希键的底层实现，这里的字符串键，指的就是这个数据库键所对应的值为字符串对象。
| 类型常量 | 对象的名称 |
| ———— | —— |
| REDIS_STRING | 字符串对象 |
| REDIS_LIST | 列表对象 |
| REDIS_HASH | 哈希对象 |
| REDIS_SET | 集合对象 |
| REDIS_ZSET | 有序集合对象 |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 | 跳跃表和字典 |ptr指针：指向底层实现数据结构的指针
每种类型的对象都至少使用了两种不同的编码
| 类型 | 编码 | 对象 |
| ———— | ————————- | —- |
| REDIS_STRING | REDIS_ENCODING_INT | |
| REDIS_STRING | REDIS_ENCODING_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_INTSE | |
| REDIS_SET | REDIS_ENCODING_HT | |
| REDIS_ZSET | REDIS_ENCODING_ZIPLIST | |
| REDIS_ZSET | REDIS_ENCODING_SKIPLIST | |
通过编码的方式，使得每种类型对象都可以灵活选择多种底层实现，根据不同场景使用不同编码，从而优化某一场景下的效率。
下面具体分析一下各种类型对象的编码方式和不同的选择条件。
2、字符串对象
字符串对象的编码有三种：
int
如果这个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象就会将整数值保存在ptr属性，并将编码设置为int
raw
如果保存的是一个字符串值，并且字符串的长度大于39，那么就使用一个SDS来保存，并将编码设置为raw
mbstr
如果保存的是一个字符串值，并且这个字符串的长度小于等于39，那么使用embstr编码来保存这个字符串
embstr是专门用于保存短字符串的一种优化编码方式
- 与SDS相比，它只需要分配一次内存，而SDS需要两次，释放次数也是一样。
- embstr编码的字符串是只读的，无法修改，执行修改命令时，会先变成raw编码的字符串
还有一点，字符串对象是五种类型中唯一一种会被其他四种对象嵌套的对象。
3、列表对象
列表对象的编码有两种：
- ziplist：压缩列表
- linkedlist：双端链表
转换条件：
- 列表对象存放的所有字符串元素的长度都小于64字节
- 列表元素保存的元素数量小于512
同时满足这两个条件时，会使用压缩列表，不然使用双端链表。
4、哈希对象
哈希对象编码也有两种：
ziplist：压缩列表
因为列表并不是键值对类型的数据结构，所以它将每个键和值元素相邻来存储键值对
hashtable：字典
字典中的键和值都是字符串对象
转换条件：
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对的数量小于512个
同时满足这两个条件时，会使用压缩列表，不然使用字典。
5、集合对象
集合对象的编码还是两种：
intset：整数集合
hashtable：字典
键是一个字符串对象，值为NULL
转换条件：
- 集合对象保存的所有元素都是整数值
- 集合对象保存的元素数量不超过512个
同时满足这两个条件时，会使用整数集合，不然使用字典。
6、有序集合对象
有序集合的编码方式也是两种：
ziplist：压缩列表
和保存哈希对象差不多，第一个结点保存元素成员，第二个元素保存元素的分值
skiplist：跳跃表
这里需要注意的是skiplist编码的有序集合使用zset结构作为底层实现，它包括一个字典和一个跳跃表。
理论上，使用字典和跳表之一就可以实现有序集合，但是
- 如果单独用字典：查找可以O(1)，但字典无序，执行范围操作时就需要排序，最少也要O(NlogN)
- 如果单独用跳表：集合有序，但是查找操作可能会从O(1)上升到O(N)
- 所以，将二者结合使用，让有序集合的照抄和防伪操作都尽可能快速的执行。
转换条件：
- 有序集合保存的元素数量小于128
- 有序集合保存的所有元素成员的长度都小于64字节。
同时满足这两个条件时，会使用压缩列表，不然使用skiplist。
总结：
五种对象类型中
- 字符串对象是最常用的，有三种编码方式
- 其他的四种对象，每种都对应两种编码方式，基本思路就是如果保存的元素范围小并且数量少，就用一种节省空间的编码方式来替代
- 压缩列表可以用来替代列表对象，哈希对象和有序集合对象
- 证书集合对象可以用来替代集合对象
- 替代的条件是可以配置的
7、redis的其他特性
7.1、内存回收
C语言并没有自动回收内存的功能，所以redis在自己的对象系统中构建了一个引用计数计数实现的内存回收机制。
7.2、对象共享
引用计数还可以实现对象共享的作用，比如当新建的键的值对象已经存在于内存中，就不必再新建一个相同的值对象，而是直接把新的键指向已经存在的值对象，并将这个对象的引用计数加一。
redis在初始化服务器时，会创建0-9999一万个字符串对象的整数值，如果需要用到这些字符串独享，服务器就会直接使用这些共享对象，而不是创建对象。
对象共享也是有限制的，redis只对包含整数值的字符串对象进行共享。
7.3、redisObject中的属性
redisObject结构中除了前面介绍的三个属性，还有一些其他的属性，比如lru属性。
这个属性作用就是记录对象最后一次被命令程序访问的时间。
给定键的空转时长=当前时间-值对象的lru时间
另一个作用就是服务器打开了maxmemory选项并且内存回收算法为LRU，空转时长较高的那部分键会优先被服务器释放。
四、参考地址
《Redis设计与实现》黄建宏著
http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html