Redis内存模型原理

Redis的对象类型与内部编码

Redis支持5种对象类型，而每种结构都有至少两种编码;

这样做的好处在于:

一方面接口与实现分离，当需要增加或改变内部编码时，用户使用不受影响;
另一方面可以根据不同的应用场景切换内部编码，提高效率。
Redis各种对象类型支持的内部编码如下图所示(只列出重点的):

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNzM5Nzk1ODY_size_16_color_FFFFFF_t_70
关于Redis内部编码的转换，都符合以下规律：编码转换在Redis写入数据时完成，且转换过程不可逆，只能从小内存编码向大内存编码转换。

Redis数据存储的细节

关于Redis数据存储的细节，涉及到内存分配器(如jemalloc)、简单动态字符串(SDS)、5种对象类
型及内部编码、redisObject。在讲述具体内容之前，先说明一下这几个概念之间的关系。下图是执行set hello world时，所涉及到的数据模型。

在这里插入图片描述

dictEntry：Redis是Key-Value数据库，因此对每个键值对都会有一个dictEntry，里面存储了指向 Key和Value的指针;next指向下一个dictEntry，与本Key-Value无关。
Key：图中右上角可见，Key(”hello”)并不是直接以字符串存储，而是存储在SDS结构中。
redisObject：Value(“world”)既不是直接以字符串存储，也不是像Key一样直接存储在SDS中，而是存储在redisObject中。实际上，不论Value是5种类型的哪一种，都是通过redisObject来存储的;而 redisObject中的type字段指明了Value对象的类型，ptr字段则指向对象所在的地址。不过可以看出，字符串对象虽然经过了redisObject的包装，但仍然需要通过SDS存储。
实际上，redisObject除了type和ptr字段以外，还有其他字段图中没有给出，如用于指定对象内部编码的字段;后面会详细介绍。
jemalloc：无论是DictEntry对象，还是redisObject、SDS对象，都需要内存分配器(如 jemalloc)分配内存进行存储。以DictEntry对象为例，有3个指针组成，在64位机器下占24个字节， jemalloc会为它分配32字节大小的内存单元。

dictEntry结构用于保存键值对，结构定义如下:

typedef struct dictEntry{ 
    void *key;
    union{ 
        void *val;
        uint64_tu64;
        int64_ts64;
    }v;
    struct dictEntry *next;
}dictEntry;

其中，各个属性的功能如下:

key：键值对中的键
val：键值对中的值，使用union(即共用体)实现，存储的内容既可能是一个指向值的指针，也可能是64位整型，或无符号64位整型;
next：指向下一个dictEntry，用于解决哈希冲突问题
在64位系统中，一个dictEntry对象占24字节(key/v/next各占8字节)。

jemalloc

Redis在编译时便会指定内存分配器;内存分配器可以是 libc 、jemalloc或者tcmalloc，默认是 jemalloc。

jemalloc作为Redis的默认内存分配器，在减小内存碎片方面做的相对比较好。jemalloc在64位系统中，将内存空间划分为小、大、巨大三个范围;每个范围内又划分了许多小的内存块单位;当Redis存储数据时，会选择大小最合适的内存块进行存储。

jemalloc划分的内存单元如下图所示：
在这里插入图片描述
例如，如果需要存储大小为130字节的对象，jemalloc会将其放入160字节的内存单元中。

redisObject

前面说到，Redis对象有5种类型;无论是哪种类型，Redis都不会直接存储，而是通过redisObject对象进行存储。
redisObject对象非常重要，Redis对象的类型、内部编码、内存回收、共享对象等功能，都需要 redisObject支持，下面将通过redisObject的结构来说明它是如何起作用的。
redisObject的定义如下(列出了与保存数据有关的三个属性):

`typedef` `struct` `redisObject { `` 
    unsigned type:4;``
    unsigned encoding:4;``
    unsigned lru:REDIS_LRU_BITS; ``
/* lru time (relative to server.lruclock) */`` ` 
    `int` `refcount;``
    ``void` `*ptr;``
} robj;`

redisObject的每个字段的含义和作用如下:

type字段表示对象的类型，占4个比特;
目前包括REDIS_STRING(字符串)、REDIS_LIST (列表)、 REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。
encoding encoding表示对象的内部编码，占4个比特。
对于Redis支持的每种类型，都有至少两种内部编码，例如对于字符串，有int、embstr、raw三种编码。通过encoding属性，Redis可以根据不同的使用场景来为对象设置不同的编码，大大提高了Redis 的灵活性和效率。以列表对象为例，有压缩列表和双端链表两种编码方式;如果列表中的元素较少， Redis倾向于使用压缩列表进行存储，因为压缩列表占用内存更少，而且比双端链表可以更快载入;当列表对象元素较多时，压缩列表就会转化为更适合存储大量元素的双端链表。
lru记录的是对象最后一次被命令程序访问的时间，占据的比特数不同的版本有所不同(如4.0版本占24 比特，2.6版本占22比特)。
通过对比lru时间与当前时间，可以计算某个对象的闲置时间;object idletime命令可以显示该闲置时间 (单位是秒)。object idletime命令的一个特殊之处在于它不改变对象的lru值。
refcount记录的是该对象被引用的次数，类型为整型。refcount的作用，主要在于对象的引用计数和内存回收。当创建新对象时，refcount初始化为1;当有新程序使用该对象时，refcount加1;当对象不再被一个新程序使用时，refcount减1;当refcount变为0时，对象占用的内存会被释放。
Redis服务器在初始化时，会创建10000个字符串对象，值分别是0~9999的整数值;当Redis需要使用值为0~9999的字符串对象时，可以直接使用这些共享对象。10000这个数字可以通过调整参数REDIS_SHARED_INTEGERS(4.0中是OBJ_SHARED_INTEGERS)的值进行改变。

综上所述，redisObject的结构与对象类型、编码、内存回收、共享对象都有关系;
一个redisObject对象的大小为16字节: 4bit+4bit+24bit+4Byte+8Byte=16Byte。

字符串

Redis 没有直接使用 C 字符串(即以空字符’\0’结尾的字符数组)作为默认的字符串表示，而是使用了SDS。SDS 是简单动态字符串(Simple Dynamic String)的缩写。

它是自己构建了一种名为简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为
Redis的默认字符串表示。

SDS 定义：

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

len 保存了SDS保存字符串的长度
buf[] 数组用来保存字符串的每个元素
free 记录了 buf 数组中未使用的字节数量

在这里插入图片描述

通过SDS的结构可以看出，buf数组的长度=free+len+1(其中1表示字符串结尾的空字符);所以，一个SDS结构占据的空间为：free所占长度+len所占长度+ buf数组的长度 =4+4+free+len+1=free+len+9。

SDS 在 C 字符串的基础上加入了 free 和 len 字段，带来了很多好处：

获取字符串长度：SDS 是 O(1)，C 字符串是 O(n)。
缓冲区溢出：使用 C 字符串的 API 时，如果字符串长度增加（如 strcat 操作）而忘记重新分配内存，很容易造成缓冲区的溢出。
而 SDS 由于记录了长度，相应的 API 在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。
修改字符串时内存的重分配：对于 C 字符串，如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。
而对于 SDS，由于可以记录 len 和 free，因此解除了字符串长度和空间数组长度之间的关联，可以在此基础上进行优化。
空间预分配策略（即分配内存时比实际需要的多）使得字符串长度增大时重新分配内存的概率大大减小；惰性空间释放策略使得字符串长度减小时重新分配内存的概率大大减小。
存取二进制数据：SDS 可以，C 字符串不可以。因为 C 字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等）。
内容可能包括空字符串，因此 C 字符串无法正确存取；而 SDS 以字符串长度 len 来作为字符串结束标识，因此没有这个问题。
此外，由于 SDS 中的 buf 仍然使用了 C 字符串（即以’\0’结尾），因此 SDS 可以使用 C 字符串库中的部分函数。
但是需要注意的是，只有当 SDS 用来存储文本数据时才可以这样使用，在存储二进制数据时则不行（’\0’不一定是结尾）。

内部编码

int：8个字节的长整型。字符串值是整型时，这个值使用long整型表示。
embstr：<=44字节的字符串。embstr与raw都使用redisObject和sds保存数据，区别在于， embstr的使用只分配一次内存空间(因此redisObject和sds是连续的)，而raw需要分配两次内存空间(分别为redisObject和sds分配空间)。因此与raw相比，embstr的好处在于创建时少分配一次空间，删除时少释放一次空间，以及对象的所有数据连在一起，寻找方便。而embstr的坏处也很明显，如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间，因此redis中的embstr实现为只读。
raw：大于44个字节的字符串。

列表

链表在Redis中的应用非常广泛，列表(List)的底层实现之一就是双向链表。此外发布与订阅、慢查询、
监视器等功能也用到了链表。

一个列表可以存储2^32-1个元素。 Redis中的列表支持两端插入和弹出，并可以获得指定位置(或范围)的元素，可以充当数组、队列、栈等。

在这里插入图片描述

typedef struct listNode { 
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode
typedef struct list { 
    //表头节点
    listNode.head;
    //表尾节点
    listNode.tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void *(*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *ptr,void *key);
} list;

Redis链表优势：

双向：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。
与传统链表（单链表）相比，Redis链表结构的优势有：
普通链表（单链表）：节点类保留下一节点的引用。链表类只保留头节点的引用，只能从头节点插入删
除
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL
结束。
带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。
多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

内部编码

列表的内部编码可以是压缩列表(ziplist)或双端链表(linkedlist)。

编码转换

只有同时满足下面两个条件时，才会使用压缩列表:

列表中元素数量小于512个;
列表中所有字符串对象都不足64字节。

如果有一个条件不满足，则使用双端列表;且编码只可能由压缩列表转化为双端链表，反方向则不可能。

哈希

在这里插入图片描述

字典又称为符号表或者关联数组、或映射（map），是一种用于保存键值对的抽象数据结构。
字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。
Redis 的字典使用哈希表作为底层实现。
哈希（作为一种数据结构），不仅是 Redis 对外提供的 5 种对象类型的一种（hash），也是 Redis 作
为 Key-Value 数据库所使用的数据结构。

typedef struct dictht{ 
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于 size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
} dictht
/*哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构， dictEntry 结构定义如下： */
typedef struct dictEntry { 
    //键
    void *key;
    //值
    union{ 
    void *val;
    uint64_tu64;
    int64_ts64;
} v;
//指向下一个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry

内部编码

内层的哈希使用的内部编码可以是压缩列表(ziplist)和哈希表(hashtable)两种;
Redis的外层的哈希则只使用了hashtable。

编码转换

如前所述，Redis中内层的哈希既可能使用哈希表，也可能使用压缩列表。只有同时满足下面两个条件时，才会使用压缩列表:

哈希中元素数量小于512个;
哈希中所有键值对的键和值字符串长度都小于64字节。

如果有一个条件不满足，则使用哈希表;且编码只可能由压缩列表转化为哈希表，反方向则不可能。

集合（set）

集合(set)与列表类似，都是用来保存多个字符串，但集合与列表有两点不同:集合中的元素是无序的，因此不能通过索引来操作元素;集合中的元素不能有重复。

一个集合中最多可以存储2^32-1个元素;除了支持常规的增删改查，Redis还支持多个集合取交集、并集、差集。

typedef struct intset{ 
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

内部编码

集合的内部编码可以是整数集合(intset)或哈希表(hashtable)。

编码转换

只有同时满足下面两个条件时，集合才会使用整数集合:

集合中元素数量小于512个;
集合中所有元素都是整数值。

如果有一个条件不满足，则使用哈希表;且编码只可能由整数集合转化为哈希表，反方向则不可能。

有序集合（zset）

普通单链表查询一个元素的时间复杂度为O(n)，即使该单链表是有序的。

在这里插入图片描述
查找46 ： 55—21—55–37–55–46

typedef struct zskiplistNode { 
    //层
    struct zskiplistLevel{ 
    //前进指针
    struct zskiplistNode *forward;
    //跨度
    unsigned int span;
    }level[];
    //后退指针
    struct zskiplistNode *backward;
    //分值
    double score;
    //成员对象
    robj *obj;
} zskiplistNode
//链表
typedef struct zskiplist{ 
    //表头节点和表尾节点
    structz skiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点的层数
    int level;
} zskiplist;

在这里插入图片描述

搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下
找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节
点，如果找到则返回，反之则返回空。
插入：首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反
面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到从底层
到k层。
删除：在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩
下头尾两个节点，则删除这一层。

内部编码

有序集合的内部编码可以是压缩列表(ziplist)或跳跃表(skiplist)。ziplist在列表和哈希中都有使
用。

编码转换

只有同时满足下面两个条件时，才会使用压缩列表:

有序集合中元素数量小于128个;
有序集合中所有成员长度都不足64字节。

如果有一个条件不满足，则使用跳跃表;且编码只可能由压缩列表转化为跳表，反方向则不可能。

缓存淘汰策略

最大缓存

在 redis 中，允许用户设置最大使用内存大小maxmemory，默认为0，没有指定最大缓存，如果有新的数据添加，超过最大内存，则会使redis崩溃，所以一定要设置。
redis 内存数据集大小上升到一定大小的时候，就会实行数据淘汰策略。

淘汰策略

redis淘汰策略配置：maxmemory-policy voltile-lru，支持热配置

redis 提供 6种数据淘汰策略：

volatile-lru：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰
volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰
volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰
allkeys-lru：从数据集（server.db[i].dict）中挑选最近最少使用的数据淘汰
allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
no-enviction（驱逐）：禁止驱逐数据

LRU原理

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心
思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
在这里插入图片描述

新数据插入到链表头部；
每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
当链表满的时候，将链表尾部的数据丢弃。
在Java中可以使用LinkHashMap去实现LRU

事务

事务中命令按顺序执行，中途有命令出错后续命令仍执行，如果是语法错误则事务无法提交。

Redis事务没有隔离级别：
Redis事务执行命令会放入队列中，事务未提交时不会被执行，也就不存在事务内的查询要看到事务里的更新，事务外查询不能看到。
Redis不保证原子性：
Redis中单条命令是原子性执行的，但事务不保证原子性，且没有回滚。事务中任意命令执行失败，其余的命令仍会被执行。

redis 127.0.0.1:6379> MULTI
OK

redis 127.0.0.1:6379> SET book-name “Hello World”
QUEUED

redis 127.0.0.1:6379> GET book-name
QUEUED

redis 127.0.0.1:6379> SADD tag “java” “go” “c”
QUEUED

redis 127.0.0.1:6379> SMEMBERS tag
QUEUED

redis 127.0.0.1:6379> EXEC
1) OK
2) “Hello World”
3) (integer) 3
4) 1) “c”
2) “go”
3) “java”