Redis底层原理

Redis是一种key/value型数据库，其中，每个key和value都是使用对象表示的。
Redis共有五种对象的类型，分别是：
* REDIS_STRING                      字符串对象
* REDIS_LIST                        列表对象
* REDIS_HASH                        哈希对象
* REDIS_SET                         集合对象
* REDIS_ZSET                        有序集合对象

Redis对象底层数据结构

底层数据结构共有八种。
* 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           跳跃表和字典

字符串对象

字符串对象的编码可以是int、raw或者embstr。
如果一个字符串的内容可以转换为long，那么该字符串就会被转换成为long类型，对象的ptr就会指向该long，并且对象类型也用int类型表示。
普通的字符串有两种，embstr和raw。embstr应该是Redis 3.0新增的数据结构，在2.8中是没有的。如果字符串对象的长度小于39字节，就用embstr对象。否则用传统的raw对象。
embstr的好处有如下几点：
* embstr的创建只需分配一次内存，而raw为两次(一次为sds分配对象，另一次为object分配对象，embstr省去了第一次)。
* 相对地，释放内存的次数也由两次变为一次。
* embstr的object和sds放在一起，更好地利用缓存带来的优势。
需要注意的是，redis并未提供任何修改embstr的方式，即embstr是只读的形式，对embstr的修改实际上是先转换为raw再进行修改。

列表对象

列表对象的编码可以是ziplist或者linkedlist。
ziplist是一种压缩链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大，每个元素也不大的时候，就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性，插入的复杂度是O（N）,即每次插入都会重新进行realloc。如下图所示，对象结构中ptr所指向的就是一个ziplist。整个ziplist只需要malloc一次，它们在内存中是一块连续的区域。
linkedlist是一种双向链表，它的结构比较简单，节点中存放pre和next两个指针，还有节点相关的信息。当每增加一个node的时候，就需要重新malloc一块内存。

哈希对象

哈希对象的底层实现可以是ziplist或者hashtable。
ziplist中的哈希对象是按照key1，value1，key2，value2这样的顺序存放来存储的。当对象数目不多且内容不大时，这种方式效率是很高的。
hashtable是由dict这个结构来实现的。

集合对象

集合对象的编码可以是intset或者hashtable。
intset是一个整数集合，里面存的为某种同一类型的整数。

有序集合对象

有序集合的编码可能是两种，一种是ziplist，另一种是skiplist与dict的结合。
ziplist作为集合和作为哈希对象是一样的，member和score顺序存放。按照score从小到大顺序排列。
skiplist是一种跳跃表，它实现了有序集合中的快速查找，在大多数情况下它的速度都可以和平衡树差不多。但它的实现比较简单，可以作为平衡树的替代品。它的结构比较特殊。

结尾

简单介绍了Redis的五种对象类型和它们的底层实现。事实上，Redis的高效性和灵活性正是得益于对于同一个对象类型采取不同的底层结构，并在必要的时候对二者进行转换，以及各种底层结构对内存的合理利用。

• 使用skiplist(跳跃表)来存储有序集合对象、查找上先从高Level查起、时间复杂度和红黑树相当，实现容易，无锁、并发性好。
• 使用ziplist存储链表，ziplist是一种压缩链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。