redis内存模型及数据结构

一、缓存通识

1、缓存类型

缓存类型分为本地缓存、分布式缓存、多级缓存

本地缓存：本地缓存就是在进程的内存中进行缓存，例如JVM的堆中，可以用LRUMap来实现，也可以使用Ehcache来实现。

本地缓存是内存访问，没有远程交互开销，性能最好，但是受限于单机容量，一般缓存较小且无法扩展

分布式缓存：分布式缓存可以很好的解决缓存小和扩展的问题，但是需要远程请求，性能没有本地缓存好

多级缓存：为了平衡性能和扩展的问题，一般在生产中使用多级缓存，即访问频率最高的数据放在本地内存，其他的热点数据放在分布式缓存中。

2、淘汰策略

不管是本地缓存还是分布式缓存，为了保证高性能，因此都使用内存来保存数据，由于成本和内存限制，当存储的数据超过缓存容量限制时，需要对缓存的数据进行剔除

一般的缓存剔除策略有：FIFO（剔除最早的数据）、LRU（剔除最近最少使用的数据）、LFU（剔除最近使用频率最低的数据）

3、Mermcache

• mc处理请求时使用多线程异步IO的方式，可以合理的例用多核cpu的优势，性能非常好

• mc功能简单，使用内存存储数据

• mc对缓存的数据可以设置失效日期，过期后的数据会被清除

• 失效策略使用延迟失效，就是当再次使用的时候会检查缓存是否失效

• 当容量存满时，会对缓存中的数据进行剔除，剔除时，除了会对过期的key进行清除之外，还会以找LRU（最近最少使用）策略对数据进行剔除

除了上述优点外，MC还有一些限制，这些限制在互联网项目中是非常致命的，因此大家一般都选择redis、mongoDB

• key不能超过250个字节

• value不能超过1M

• key的最大失效时间是30天

• 只支持KV数据结构，不支持持久化和主从同步

4、redis

• 与MC不同，redis采用纯单线程模式处理请求，这样做主要是因为：采用了非阻塞的异步事件处理机制、缓存数据都是内存操作，时间不会长，单线程可以避免线程间上下文切换

• redis支持持久化，所以redis不仅仅可以作为缓存使用，同时还可以作为NoSql数据库使用

• redis除了有KV数据格式之外，还提供了其他丰富的数据格式，如List、Hash、Set、SortedSet等

• redis提供了主从同步机制，以及Cluster集群部署能力，能够提高高可用服务

5、redis多线程

1. 为什么redis一开始使用单线程模型

   (1) IO多路复用

   

   FD是一个文件描述符，意思是表示当前文件处于可读、可写还是异常状态，使用多路IO复用机制可以同时监听多个文件描述符的可读和可写操作，类似于拥有了多线程的特点；一旦有网络请求，由于基本上都是内存操作，所以处理速度会非常的快；因此即使有很多网络请求，但是在IO多路复用的处理下，依然可以在内存中高速的处理。

   (2)可维护性高

   多线程虽然在某些方面表现优异，但是却引入了程序执行顺序的不确定性，带来了并发读写的一系列问题，同时还存在线程切换的问题。

   (3)基于内存

   redis是基于内存的操作，能够在一秒内处理10W请求，如果该性能还达不到要求，可以使用redis分片技术，让不同的redis服务器处理。

   而且redis除了要进行AOF备份是IO操作外，其余的都不会涉及IO操作。

   总结：基于内存而且使用多路IO复用技术，单线程速度非常快，且避免了多线程之间的切换问题，同时IO多路复用又保证了多线程的特点

   2. 为什么redis在6.0之后又引入了多线程

      因为网络读写的系统在redis执行期间占用了大部分的CPU时间，如果把网络读写做成多线程，对性能会有很大的提升。

      例如：redis可以使用del命令删除一个元素，如果这个元素非常大，可能占据几十兆或者上百兆，那么在短时间内是不能完成的，这样一来就需要多线程的异步支持。

       

      总结：redis选择使用单线程模型处理客户端请求主要还是因为CPU不是redis服务器的瓶颈，所以使用多线程模型带来的提升并不能抵消其带来的开发成本、维护成本以及多线程间切换的性能问题；redis的性能瓶颈主要在网络IO上，因此redis引入了多线程，对一些大键值对的删除操作，通过多线程非阻塞的方式释放内存空间，同时减少了主线程的阻塞时间，进而提升执行效率

二、redis内存模型

1、redis的内存划分

数据：作为数据库，数据是最重要的部分，这部分数据会存入used_memory中

进程：redis主进程运行需要占用内存，如代码、常量池等；这部分不是由jemalloc分配，因此不会统计在used_memory中

缓冲内存：缓冲内存包括客户端缓冲区、复制积压缓冲区、AOF缓冲区等，其中，客户端缓冲区存储客户端连接的输入输出命令；复制积压缓冲区用于部分复制功能；AOF缓冲区用于在进行AOF重写时，保存最近的写入命令

内存碎片：内存碎片是redis在分配、回收物理内存过程中产生的。

2、内存统计

使用info memory命令可以查看redis的内存统计，几个重要的内存统计信息如下

info memory
# Memory
#redis分配的总内存
used_memory:1356472
#占操作系统的内存，不包括虚拟内存
used_memory_rss:11247616
#内存碎片比例，如果小于0说明使用了虚拟内存
mem_fragmentation_ratio:8.55
#内存碎片字节数
mem_fragmentation_bytes:9932168
#redis使用的内存分配器
mem_allocator:jemalloc-5.1.0

其中used_memory是redis内存分配器分配的内存总量，由于redis的内存可能不够用，因此会使用磁盘作为虚拟内存；used_memory_rss是操作系统分配给redis的内存，这其中包含内存碎片。因此used_memeory可能大于used_memory_rss，也可能小于used_memory_rss；

mem_fragmentation_ratio是指used_memory_rss/used_memory的比值，该比值在刚创建时，由于不会存在虚拟内存，因此肯定大于1，且该值越大，说明内存碎片越多；如果小于1，则说明已经使用了虚拟内存，就需要排查问题原因。

3、redis数据存储细节

（1）存储细节

当我们使用set hello world命令时，所涉及的数据模型如上图所示，每一条数据都是一个dictEntry，其中包含key、value和next三个属性；其中key存储的是一个指向sds文件的指针，value存储的是一个指向redisObject对象的指针，next存储的指向下一个dictEntry的指针；而redisObject对象非常重要，redis对象的类型、内部编码、内存回收、共享对象等功能，都需要redisObject的支持。

（2）redisObject

{ 
    unsigned type:4;//类型 五种对象类型 
    unsigned encoding:4;//编码 
    void *ptr;//指向底层实现数据结构的指针 
    //... 
    int refcount;//引用计数 
    //... 
    unsigned lru:24;
    //记录最后一次被命令程序访问的时间 
    //... 
}robj;

type：表示对象的类型，占4个bit，目前包括REDIS STRING、REDIS LIST、REDIS HASH、REDIS SET、REDIS ZSET。

encoding：表示对象的内部编码，占4个bit；对于redis支持的每种数据类型，都至少有两种内部编码，例如对字符串，有int、emstr、raw三种编码；list有压缩列表和双端列表两种编码方式，如果列表中元素较少，redis倾向于使用压缩表来进行存储，因为压缩列表占用内存更少，而且比双端列表载入更快，当存储的元素较多时，压缩表就会转话为更适合存储大量元素的双端链表；通过encoding属性，redis可以根据不同的使用场景来为对象设置不同的编码，大大提高了redis的灵活和效率。

可以使用object encoding命令来查看编码方式

127.0.0.1:6379> set key1 33
OK
127.0.0.1:6379> object encoding key1
"int"
127.0.0.1:6379> set key1 str1
OK
127.0.0.1:6379> object encoding key1
"embstr"
127.0.0.1:6379> set key1 aaaaabbbbbcccccdddddeeeeefffffggggghhhhhiiiii
OK
127.0.0.1:6379> object encoding key1
"raw"

lru:记录的是对象最后一次被命令程序访问的时间；2.6版本前占用22bit，4.0版本占24bit；通过对比lru时间与当前时间，可以算出某个对象的空闲时间，可以使用object idletime命令显示空闲时间（单为：秒），同时该命令不会改变lru的值。

127.0.0.1:6379> object idletime key1
(integer) 332

同时lru除了通过object idletime命令打印之外，还与redis内存回收有关，如果redis打开了maxmemory选项，且内存回收算法使用的是volatile-lru或allkeys-lru，那么当redis占用内存超过maxmemory指定的值时，redis会优先选择空转时间最长的对象进行回收。

ptr：ptr指向具体的数据。

refcount：refcount记录该对象被引用的次数，当一个对象被创建时，refcount=1，之后如果再有程序使用，则加一，使用完毕后，减一，如果refcount=0，对象占用的内存则会被释放；如果refcount=1，则说明该对象是共享对象。

redis使用共享对象主要是为了解约内存，目前redis只支持数字类型（int类型）的共享对象，因为其要兼顾内存和CPU，数字的对比相等的时间复杂度为O(1)，而字符串对比相等的时间复杂度为O(n)；虽然共享对象只能是整数值的字符串对象，但是五种类型都可能使用共享对象，例如哈希、列表等的元素。

就目前来说，redis服务在初始化时，会创建10000个字符串对象，值分别是0~9999的整数值，当redis需要使用这区间的值时，可以直接使用共享对象。10000个对象可以使用参数REDIS_SHARD_INTEGERS(OBJ_SHARED_INTEGERS)的值进行改变；也可以使用object refcount命令来进行查看

总结：综上所述，redisObject的结构与对象类型、编码、内存回收、共享对象都有关系；一个redisObject对象的大小为16个字节

4bit(type) + 4bit(encoding) + 24bit(lru) + 4Byte + 8Byte = 16Byte

jemalloc

jemalloc作为redis的默认内存分配器，在减小内存碎片方面做的相对比较好，jemalloc在64位系统中，将内存空间划分为小、大、巨大三个范围；每个范围内有划分了许多小的内存单位，当redis存储数据时，会选择大小合适的内存进行存储；具体jemalloc划分的内存单元如下图所示，例如，一个对象占130字节，jemalloc会将其放入160字节的内存中。

（3）SDS

redis没有使用C字符串作为默认字符串，而是使用了SDS（简单字符串）。

SDS与C字符串区别：

• 获取字符串长度：SDS是O(1)，C字符串是O(n)

• 缓存区溢出：使用C字符串API时，如果字符串增加而忘记重新分配内存，很容易造成缓冲区溢出；而SDS由于记录了长度，响应的API在可能造成缓存区溢出时会自动重新分配内存，从而杜绝了缓冲区溢出。

• 修改字符串时内存的重新分配：对于C字符串，如果要修改字符串，必须要重新分配内存，因为如果没有重新分配，字符串长度增大时会造成缓冲区溢出，减少时会造成内存泄漏；而对于SDS而言，由于记录了len和free，因此可以解除字符串长度和空间数组长度之间的关联。

• 存取二进制数据：SDS可以，C字符串不可以，由于C字符串是以空字符串作为字符串结束的标识，因此对于图片等二进制可能包含空字符串的文件，是无法用C字符串读取的。而SDS以字符串长度len来作为结束标识，因此不存在该问题。

3.2之前，sds文件的属性为：buf表示字节数组，len表示buf已使用的长度，free表示buf未使用的长度

struct sdshdr{ 
    //记录buf数组中已使用字节的数量 
    //等于 SDS 保存字符串的长度 
    int len; 
    //记录 buf 数组中未使用字节的数量 
    int free; 
    //字节数组，用于保存字符串 
    char buf[]; 
}

3.2以后

封装了不同长度的sdshdr

三、redis对象类型与内存编码

redis支持5种数据类型，而每种结构都至少有两种编码

类型	编码	object encoding输出	对象
REDIS_STRING	REDIS_ENCODING_INT	int	使用整数数值实现的字符串对象
	REDIS_ENCODING_EMBSTR	embstr	使用embstr实现的简单动态字符串对象；当字符串长度<=44时为embstr
	REDIS_ENCODING_RAW	raw	使用简单动态字符串实现的对象；当字符串长度>44时为raw
REDIS_LIST	REDIS_ENCODING_ZIPLIST	ziplist	使用压缩表实现的列表对象；在3.0及以前使用
	REDIS_ENCODING_LINKEDLIST	linkedlist	使用双端链表实现的列表对象；在3.0及以前使用
	REDIS_ENCODING_QUICKLIST	quicklist	在3.2及以后使用
REDIS_HASH	REDIS_ENCODING_ZIPLIST	ziplist	使用压缩表实现的哈希对象
	REDIS_ENCODING_HT	hashtable	使用字典实现的哈希对象
REDIS_SET	REDIS_ENCODING_INTSET	intset	使用整数集合实现的集合对象
	REDIS_ENCODING_HT	hashtable	使用字段实现的集合对象
REDIS_ZSET	REDIS_ENCODING_ZIPLLIST	ziplist	使用压缩表实现的有序集合对象
	REDIS_ENCODING_SKIPLIST	skiplist	使用调表和字典实现的有序集合对象

1、字符串

字符串是最基础的数据类型，且字符串之外的其他几种复杂类型也都是字符串。

字符串长度不能超过512M

字符串的内存编码有：int、embstr、raw

当值为整数时，则使用int，如果值为非整数且长度<=44时，使用embstr，长度>44字节时，使用raw；embstr和raw的区别在于，embstr的使用只分配一次内存空间，因此redisObject和sds是连续的；因此embstr的优点在于创建时少分配一次空间，删除时少释放一次空间，同时对象的所有数据都在一次，方便寻找；而embstr的缺点也同样明显，如果字符串的长度增加需要重新分配内存时，整个redisObject和sds需要重新分配空间，因此embstr实现为只读。

在这里要说明，在3.2之前，embstr和raw的长度区分时39，在3.2之后，区分长度是44。以3.2以后为例，由于redisObjct长度为16字节，sds长度为4字节，因此当长度为44时，embstr的长度 16 + 4 + 44 = 64，jemalloc正好可以分配64字节的内存单元。而3.2之前是因为SDS的长度为9字节，因此embstr和raw的区分长度为39。

2、列表

redis3.0之前内部使用压缩列表（ziplist）或双端链表（linkedlist），选择的折中方案是两种数据类型转换，但是数据类型转换也是一个比较复杂的操作，因此在3.0之后，引入了quicklist，其结和了压缩列表和双端列表的特点，并且省去了临界条件的数据格式转换。

（1）ziplist

压缩列表是列表key和hash key的底层实现之一，当一个列表只含有少量列表项时，并且每个列表项是小整数或短字符串时，那么redis（3.0之前）底层就会使用压缩表来做底层实现。

压缩表是redis为了节省空间而开发的，是由一系列特殊编码的连续内存块组成的顺序性数据结构，一个压缩表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值，放到一个连续的内存区。

压缩表的每个节点如下所示：

• previous_entry_length：记录压缩表前一个字节的长度

• encoding：记录context中存储内容的类型

• context：保存数据，数据的类型和长度由encoding决定

（2）linkedlist

双端链表如下图所示，其同时保存了表头指针和表尾指针，并且每个节点都有指向前一个节点和后一个节点的指针，链表中保存了链表的长度，dup、free、match为节点值设置了类型特定函数，所以链表可以用于保存不同的数据类型，而链表中每个节点指向的是类型为字符串的redisObject。

（3）quicklist

快速列表简单的说，我们还可以将其看作是一个双像列表，但是列表的每一个节点都是ziplist，其实快速列表就是双向链表和压缩表的结和，quicklist中的每一个节点ziplist都能够存储多个数据元素。

然后可以简单看一下quicklist的数据结构

typedef struct quicklistNode {
    struct quicklistNode *prev;//指向前一个ziplist节点
    struct quicklistNode *next;//指向后一个ziplist节点
    unsigned char *zl;//数据指针，如果没有被压缩，就指向ziplist结构，如果被压缩，则只想quicklistZF结构
    unsigned int sz;             //表示指向ziplist结构的总长度
    unsigned int count : 16;     //表示ziplist中数据项的个数
    unsigned int encoding : 2;   //编码格式，1-ziplist，2-quicklistZF
    unsigned int container : 2;  //预留字段，存放数据方式，1-NONE，2-ziplist
    unsigned int recompress : 1; //解压标记，当查看一个压缩的数据时，需要暂时解压，标记此参数为1，之后再进行重新压缩
    unsigned int attempted_compress : 1;//测试相关
    unsigned int extra : 10; //扩展字段，暂时没用
} quicklistNode;
​
typedef struct quicklistLZF {
    unsigned int sz; 
    char compressed[];
} quicklistLZF;
​
typedef struct quicklist {
    quicklistNode *head;//指向quick的头部
    quicklistNode *tail;//指向quick的尾部
    unsigned long count; //列表中所有数据项的总数
    unsigned int len; //quicklist的节点个数，即ziplist个数
    int fill : 16; //表示不用整个int存储fill，而是只用了其中的16位来存储
    unsigned int compress : 16; //节点压缩深度设置
} quicklist;

3、哈希

redis外层哈希，则是使用K-V键值对所使用的结构，内层哈希，则是说明redis的一种数据类型

内层哈希的内部编码可以是雅座列表（ziplist）或哈希表（hashtable）；外层哈希的内部编码是哈希表。

与哈希表相比，压缩列表用于元素个数少，元素长度短的场景，其优势在于集中存储，节省空间，虽然这样元素操作的时间复杂度由O(1)变成了O(n)，但是由于数据少，因此并没有明显劣势。

哈希表则是由一个dict结构、两个dictht结构、一个dictEntry指针数组和多个dictEntry组成，如下图所示：

一般来说，使用dictht和dictEntry就可以实现普通的哈希表功能，但是在redis实现中，在dictht结构的上层，还有一个dict结构。

dict

typedef struct dict {
    dictType *type;//type里面主要记录了一系列的函数，可以说是规定了一系列的接口
    void *privdata;//保存了需要传递给那些类型特定函数的可选参数
    dictht ht[2];//便于渐进式rehash
    int rehashidx;//rehash索引，当rehash不进行时，为-1
    int iterators;//目前正在运行的安全迭代器数量
}

其中type属性和privdata属性是为了适应不同的键值对，用于创建多肽字典。

ht属性和rehashidx属性则作用于rehash，其中ht分别指向两个dictht，一般情况下，数据存储在ht[0]的dictht中，当需要rehash时，则将dict[0]的数据复制到dict[1]，然后对dict[0]进行扩容，扩容完成后，重新将dict[1]的数据复制到dict[0]，然后清除dict[1]的数据。

dictht

typedef struct dictht{ 
    dictEntry **table; //哈希表数组，每个元素都是一条链表
    unsigned long size; //哈希表大小 
    unsigned long sizemask; // 哈希表大小掩码，用于计算索引值  总是等于 size - 1 
    unsigned long used; // 该哈希表已有节点的数量 
}dictht;

其中各个属性说明如下：

• table属性是一个指针，指向bucket

• size属性记录了哈希表的大小，即bucket的大小

• sizemask值总是size-1，这个属性值和hash值一起决定了一个key在table中的位置

• used记录了已经使用的dictEntry数量

bucket

bucket是一个数组，数组的每个元素都是指向dictEntry结构的指针，redis中的bucket数组大小是大于dictEntry的最小2的次方（例如有1000个dictEntry，那么bucket的大小为1024，有1500个dictEntry，那么bucket的大小为2048）

dictEntry

typedef struct dictEntry {
    void *key;
    union{  //值的类型可以是以下三种
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;//指向下个哈希表节点，形成链表----解决哈希冲突
} dictEntry;

编码转换

如前面所述，redis内层的哈希既可能使用hash表，也可能使用zipllist，那么只有同时满足下面两个条件时，才会使用压缩表：hash中元素数量小于512个 && hash中所有键值对的键和值字符串长度都小于64。

4、集合

集合的内部编码是整数集合（intset）或哈希表（hashtable），hash表前面已经说过，不在多说，但是使用hash表时，value全部为null。

整数集合的定义如下：

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

encoding中存储的是contents中的数据类型，虽然contents是int8_t类型，但实际存储的值可能使int16_t、int32_t、int64_t等，具体的类型还是由encoding来决定。

整数集合适用于集合所有元素都是整数且元素数量较少时；与hash表相比，整数集合的优势在于集中存储，节省空间。

编码转换

只有同时满足以下两个条件时，集合才会使用整数集合：集合中元素数量小于512个 && 集合中所有元素都是整数

5、有序集合

有序集合内部使用压缩表或跳表。

跳跃表是一种有序的数据结构，通过在每个节点中维护多个指向其他节点的指针，从而达到快速访问节点的目的；除了跳跃表，平衡树也是一种典型的有序数据结构，大多数情况下，跳跃表的效率可以和平衡树媲美，同时又比平衡树简单，因此在redis使用跳跃表代替平衡树。

跳跃表实现由zskiplist和zskiplistNode组成，其中zskiplist用于保存跳跃表信息，zskiplistNode用于表示跳跃节点。

数据转换

同时满足以下两种条件，才会使用压缩表：有序集合中的元素小于128 && 有序集合中所有的成员长度都不足64字节；如果有一个不满足，则使用跳跃表，且编码只能由跳跃表转换为压缩表，反之则不可以。

跳跃表

普通的单向链表

跳跃表：

插入

跳跃表的插入是利用了概率算法，首先确定插入的层数，类似抛硬币，如果时正面则层数累加，反面则停止，最后以正面的统计数作为层数，然后从底层插入到K层。

层级计算如下：

// 默认值 p=1/4, MaxLevel=32
    level:= 1
    // random()生成[0, 1)的随机数
    where random() < p and level < MaxLevel do
        level := level+1
    return level

当我们插入-3时，因为只有一个数据，那么只将数据插入L1；当插入2时，由于由于数量为2，那么就是用类似抛硬币的办法，判断是否需要在L2插入，如果是则插入，否则不插入。

查询

从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空

删除

跳表删除元素时，在各个层中找到元素直接删除元素，然后调整元素后的指针即可，如果删除节点后该层只有首尾两个节点，则删除这一层。

跳跃表的底层实现

typedef struct zskiplistNode {
    sds ele;
    double score;//分值
    struct zskiplistNode *backward;//后退的指针
    
    //层
    struct zskiplistLevel {
        struct zskiplistNode *forward;//前进指针  后边的节点
        unsigned int span;//跨度
    } level[];
    
} zskiplistNode;
​
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;//头节点和尾节点
    unsigned long length;//表中节点的数量
    int level;//最大层数
} z