4、Redis高性能的根本原理

1、基于内存读写

内存的读写速度很快

2、采用的多路复用

Epoll模型

3、高效率的数据结构

常用的五大Redis的数据结构，及他们各自的底层实现结构
string hash list set sortset(zset)
string的底层实现是简单动态字符串（SDS -simple dynamic string）
hash的底层实现是hash表或则压缩列表（ziplist）
list的底层实现是双向列表（quicklist）或者压缩列表
set的底层实现是hash表（hashtable）或者整数数组
sortset(zset)的底层实现是压缩列表或者跳表
各个数据结构的底层实现概览

底层实现结构图

底层K-V结构图

底层K-V图

1、String的底层实现（SDS结构）

value是string类型的时候分为三种情况
（1）、当设置的值是整数类型的时候，redis底层会将string类型转化为int来存储
（2）、设置的值小于等于44个字节的时候，使用的编码是embstr

127.0.0.1:6379> set a test
OK
127.0.0.1:6379> object encoding a
"embstr"

（3）、设置的值大于44个字节的时候，使用的编码是raw

127.0.0.1:6379> set a 012345678901234567890123456789012345678901234
OK
127.0.0.1:6379> object encoding a
"raw"

redis是用C语言编写的，在C语言中string类型是用字符数组char[]来实现的。redis实现字符串的底层并没有直接使用C语言中的字符数组的形式，而是进行了改造，构造出了一种SDS的数据结构

redis3.2以前的版本SDS数据结构
struct sdshdr{
  int free; // buf[]数组未使用字节的数量
  int len; // buf[]数组所保存的字符串的长度
  char buf[]; // 保存字符串的数组
}

redis3.2及以后的版本SDS数据结构
（unit8_t 长度为1字节）
（unit16_t 长度为2字节）
（unit32_t 长度为3字节）
（unit64_t 长度为4字节）
存储2^5-1的范围（0-31）
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
存储2^8-1的范围（0-255）
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */ 
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

使用新的SDS结构而不使用C原生字符数组的原因是：

1、提升效率
原来的字节数组计算长度和扩容方面效率都比较低
计算长度需要从头遍历到结束标记\0，才可以求得长度
扩容方面，每次计算扩容字符串长度的时候都需要做内存的重新分配，如果字符串不常修改还可以接受，但是redis中value会经常的修改，所以需要重新设置扩容算法
（1）、空间预分配：修改前检查free的空间是否够用（如果修改后len的值小于1M，则分配free的大小于len相等，如果len的值大于1M，则此时分配的free的大小为1M）
（2）、惰性空间释放：当缩短SDS字符串是，不会立即回收多余的空间，而是增加free的值为以后再次增长操作提供空间

2、保证二进制安全
C语言中的字符数组要求以\0作为结尾，所以字符串中只能保存文本信息，不能存储二进制数据。改造后的SDS使用len来判断字符串的长度，而非\0。所以保证了二进制的安全性，可以存储二进制文件

Redis3.2将SDS结构进一步优化为SDShdr5，SDShdr8，SDShdr16，SDShdr32的目的：

节省存储空间
原来的SDS结构中int类型的len和int类型的free各自分别占4个字节，也就是最大长度可以表示为2^32-1的长度，平常使用的长度很少达到这个长度，所以对长度进行一下优化
SDShdr5结构除去buff数组外只有一个字节长度的flag
SDShdr8结构除去buff数组外只有一个字节长度的flag，各一个字节长度的len和alloc
SDShdr16结构除去buff数组外只有一个字节长度的flag，各两个字节长度的len和alloc
SDShdr32结构除去buff数组外只有一个字节长度的flag，各三个字节长度的len和alloc
其中flag将8个bit位分为高3位和低5位，高3位表示type，低5位表示长度
type为000的时候表示SDShdr5
type为001的时候表示SDShdr8
type为010的时候表示SDShdr16
type为011的时候表示SDShdr32

字节长度超多44的用raw和小于44的用embstr编码
redis在创建一个字符串对象的时候会创建两个对象，一个redisObejct一个是sds
redisObject的结构如下
typedef struct redisObject {
   unsigned type:4;//对象类型（4位=0.5字节）
   unsigned encoding:4;//编码（4位=0.5字节）
   unsigned lru:LRU_BITS;//记录对象最后一次被应用程序访问的时间（24位=3字节）
   int refcount;//引用计数。等于0时表示可以被垃圾回收（32位=4字节）
   void *ptr;//指向底层实际的数据存储结构，如：SDS等(8字节)
} robj;
embstr使用jemalloc内存分配器，在创建的时候会将redisObejct和sds结构创建为一个连续的内存空间
jemalloc最大分配的内存为64字节（CPU的缓存行一次性读取的最大字节也是64，这样只需要一次读取即可，效率最高），除去redisObject所用的（4+3+0.5+0.5+8）的16个字节和sds中len和free所占的8个字节，再加上\0所占用的1个字节，留给buff字符数组最大的长度为（64-8-16-1）=39
所以3.2以前的redis超过39个字节就用raw,39个字节以内使用embstr
但是在redis3.2之后的版本，对SDS结构进行了优化，使用flag``uint8 len和uint8 alloc将8个字节缩短为3个字节，所以buff数组的大小由原来的39个字节增长为44个字节

embstr和raw的区别
embstr在创建的时候创建的是连续的内存空间，所以在回收的时候效率更快，只需要回收一次，而raw在创建的时候不一定创建的是两个连续的空间，需要回收两次
embstr在查找的时候效率更高

2、list的底层实现

list的底层使用快速双向链表quicklist或者压缩链表ziplist来实现的。
list的底层并没有使用传统的双向链表的结构是因为
（1）、双向链表需要有一个前指针和后指针，每个指针占用的空间分别都是8byte，占用内存比较多
（2）、双向链表所通用的一个问题是会形成很多的内存碎片

压缩链表ziplist结构是

ziplist

压缩链表ziplist特点
（1）、是一个连续的内存空间，极大节省内存空间
（2）、在扩容的时候需要重新寻找一大块内存空间
（3）、从头开始遍历的时候，比较麻烦
所以当ziplist很长的时候，就需要使用quicklist来实现list，quicklist会将ziplist分成很多个段

快速双向链表quicklist结构

quicklist结构

通过设置，提高效率
1、list-max-ziplist-size = -2 -2为默认值，表示单个ziplist节点最大能存储8kb，超过这个限制就开始分裂为多个ziplist，其他的设置还有
-5: max size: 64 Kb  <-- not recommended for normal workloads
-4: max size: 32 Kb  <-- not recommended
-3: max size: 16 Kb  <-- probably not recommended
-2: max size: 8 Kb   <-- good
-1: max size: 4 Kb   <-- good
2、list-compress-depth = 0 默认设置为0，表示都不进行压缩，如果为1，则表示从头节点往后1个，尾节点往后一个不用压缩，其他的节点全部压缩（压缩是为了减少内存碎片，quicklist中的多个ziplist也会形成内存碎片）

3、hash的底层实现

hash的底层实现为hashtable或者ziplist。
hashtable的底层实现

hashtable实现

hashtable的扩容

扩容过程

hashtable扩容注意
1、正常扩容和收缩
扩展：ht[1]的大小为第一个大于等于ht[0].used*2。
收缩：ht[1]的大小为第一个大于等于ht[0].used/2 。
2、渐进式扩容
如果key值太多的情况下，redis会采用渐进式扩容。首选需要扩容的话，会先维护一个索引计数器变量rehashidx，设置为0表示开始扩容，然后再每次对字典的增删改操作的同时进行扩容，多次操作之后才能扩容完成，扩容完成之后索引计数器变量就设置为-1

当数据量比较小或者单个元素的时候，底层使用的是ziplist存储，具体可以通过配置来制定

hash-max-ziplist-entries = 512 当ziplist的元素超过512个，将改为hashtable（默认值）
hash-max-ziplist-entries = 64 当单个元素的大小超过64byte时，将改为hashtable（默认值）

127.0.0.1:6379> hset hash-test k1 123456789-123456789-123456789-123456789-123456789-123456789-12345
(integer) 1
127.0.0.1:6379> object encoding hash-test
"hashtable"

127.0.0.1:6379> hset hash-test1 k1 123456789-123456789-123456789-123456789-123456789-123456789-123
(integer) 1
127.0.0.1:6379> object encoding hash-test1
"ziplist"

注意！

1、hashtable是无序的 ziplist是有序的
2、在能使用hash的情况下优先使用hash，不要使用String，因为使用太多的String，则会创建出过多的key,当key大量的时候，就会容易发生hash碰撞，所以就需要频繁的rehash，每次rehash就会创建2倍的内存，造成内存浪费

4、set的底层实现

hash的底层实现为整数数组intset或者hashtable。
当set都为整数的时候，set的底层实现都是使用intset结构实现
如果set中存在字符串的值，则使用hashtable来实现
intset是有序的，hashtable是无序的

127.0.0.1:6379> sadd test-set1 1 2 3 4
127.0.0.1:6379> smembers test-set1
1) "1"
2) "2"
3) "3"
4) "4"
127.0.0.1:6379> object encoding test-set1
"intset"
127.0.0.1:6379> sadd test-set1 a b c
127.0.0.1:6379> smembers test-set1
1) "3"
2) "2"
3) "1"
4) "c"
5) "4"
6) "b"
7) "a"
127.0.0.1:6379> object encoding test-set1
"hashtable"
# 再次删除字符串之后，还是使用hasttable结构存储
127.0.0.1:6379> srem test-set1 a b c
(integer) 3
127.0.0.1:6379> smembers test-set1
1) "1"
2) "2"
3) "4"
4) "3"
127.0.0.1:6379> object encoding test-set1
"hashtable"

5、sortset的底层实现

sortset底层使用压缩列表ziplist或跳表skiplist的结构实现
当数据量小的情况下，使用ziplist实现，当数据量大的情况下使用ziplist实现，具体可以通过配置设置

zset-max-ziplist-entris 128 #元素个数超过128个，将使用skiplist
zset-max-ziplist-value 64 #单个元素大小超多64byte，将使用skiplist

默认设置下的底层结构

127.0.0.1:6379> zadd test-zset 1 a
(integer) 1
127.0.0.1:6379> zrange test-zset 0 -1
1) "a"
127.0.0.1:6379> object encoding test-zset
"ziplist"
127.0.0.1:6379> zadd test-zset 2 123456789-123456789-123456789-123456789-123456789-123456789-12345
(integer) 1
127.0.0.1:6379> zrange test-zset 0 -1
1) "a"
2) "123456789-123456789-123456789-123456789-123456789-123456789-12345"
127.0.0.1:6379> object encoding test-zset
"skiplist"

skiplist的底层实现

查找对应元素的时候，先从最高的索引层找，例如找c 150，则先从L1找，L1的指针指向b，查看b120小于150，则继续往后找，b的指针指向null，则向下一层找，向下一层b的指针指向c，查看c的score为150，所以找到对应的元素c

skiplist结构

skiplist的底层实现

参考资料

1、https://blog.csdn.net/u010710458/article/details/80604740