c语言做网站吗,四个商城建设,沙河网站建设,wordpress 第三方Redis核心技术与实战学习笔记
最近想沉下心来看下redis#xff0c;买了蒋德钧老师的《Redis 核心技术与实战》,这里记录一些学习笔记 希望能够坚持下去有想一起学习的童鞋#xff0c;可以点击跳转到文章尾部获取学习资源,仅供学习不要用于任何商业用途!!!
redis知识全景图 …Redis核心技术与实战学习笔记
最近想沉下心来看下redis买了蒋德钧老师的《Redis 核心技术与实战》,这里记录一些学习笔记 希望能够坚持下去有想一起学习的童鞋可以点击跳转到文章尾部获取学习资源,仅供学习不要用于任何商业用途!!!
redis知识全景图 学习要有一个全局的系统观念
redis问题画像图
redis问题可以多套到这个图中分析形成统一的印象问题 -- 主线 -- 技术点
SimpleKV需要考虑的问题 存什么样的数据 KV对 key为stringvalue为基本类型 数据有哪些操作 增删改查 PUT/GET/DEL/Scan不论是增删改查都涉及到索引问题因为要先定位到key对应的内存位置再读写 这里有涉及到索引 可以考虑全局hash 这里如果value是复杂结构 hash后还要再次用到不同的索引算法 如果是增和删除 又涉及到内存管理 因为需要分配内存或者释放内存如果value大小不一致 内存分配算法至关重要 数据存在哪里 存在内存比较快 但内存没了容易丢失所以还要解决持久化的问题每次都落地则性能不行可定时落地到文件 客户端怎么访问 .so动态连接库 单机访问socket连接 可以跨机器 但要解决连接管理协议解析多个客户端并发访问 如何高性能 涉及到IO模型 容灾怎么来做 涉及到主从或者集群 重启后怎么快速初始化或者恢复 也是涉及到持久化
redis数据结构
值的数据类型
String、List、Hash、Set、sortedSet
KV保存用到的数据结构
整体图示 在 Redis 3.0 版本中 List 对象的底层数据结构由「双向链表」或「压缩表列表」实现但是在 3.2 版本之后List 数据类型底层数据结构是由 quicklist 实现的 在最新的 Redis 代码还未发布正式版本中压缩列表数据结构已经废弃了交由 listpack 数据结构来实现了
全局Hash索引示意 hash冲突解决办法 链式hash 冲突的时候用链表的方式保存冲突的数据所以多个冲突的数据要遍历就要逐个遍历了 2个全局hash渐进式rehash 直接全量rehash涉及大量内存复制操作可能阻塞客户端请求处理所以采取的是渐进式rehash
redis数据结构全景图_xiaolin redisDb 结构表示 Redis 数据库的结构结构体里存放了指向了 dict 结构的指针 dict 结构结构体里存放了 2 个哈希表正常情况下都是用「哈希表1」「哈希表2」只有在 rehash 的时候才用具体什么是 rehash我在本文的哈希表数据结构会讲 ditctht 结构表示哈希表的结构结构里存放了哈希表数组数组中的每个元素都是指向一个哈希表节点结构dictEntry的指针 dictEntry 结构表示哈希表节点的结构结构里存放了 void * key 和 void * value 指针 *key 指向的是 String 对象而 *value 则可以指向 String 对象也可以指向集合类型的对象比如 List 对象、Hash 对象、Set 对象和 Zset 对象 void * key 和 void * value 指针指向的是 Redis 对象
redisObject数据结构示意 type标识该对象是什么类型的对象String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对象 encoding标识该对象使用了哪种底层的数据结构 ptr指向底层数据结构的指针
简单字符串SDS(simple dynamic string)
SDS数据结构
struct SDS{len //这样获取字符串长度的时候只需要返回这个成员变量值就行时间复杂度只需要 O1alloc //分配空间长度 类似capicity 分配给字符数组的空间长度。这样在修改字符串的时候可以通过 alloc - len 计算出剩余的空间大小可以用来判断空间是否满足修改需求如果不满足的话就会自动将 SDS 的空间 扩展至执行修改所需的大小然后才执行实际的修改操作所以使用 SDS 既不需要手动修改 SDS 的空间大小也不会出现前面所说 的缓冲区溢出的问题当判断出缓冲区大小不够用时Redis 会自动将扩大 SDS 的空间大小小于 1MB 翻倍扩容大于 1MB 按 1MB 扩容flag //用来表示不同类型的 SDS。一共设计了 5 种类型分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64每种类型占用内存不一样 更加灵活 而且是禁止内存字节对齐的节省内存buf[] 字符数组用来保存实际数据。不仅可以保存字符串也可以保存二进制数据
}链表List
typedef struct listNode {//前置节点struct listNode *prev;//后置节点struct listNode *next;//节点的值void *value;
} listNode;
在这个基础上增加
typedef struct list {//链表头节点listNode *head;//链表尾节点listNode *tail;//节点值复制函数void *(*dup)(void *ptr);//节点值释放函数void (*free)(void *ptr);//节点值比较函数int (*match)(void *ptr, void *key);//链表节点数量unsigned long len;
} list; Redis 的链表实现优点如下
listNode 链表节点的结构里带有 prev 和 next 指针获取某个节点的前置节点或后置节点的时间复杂度只需O(1)而且这两个指针都可以指向 NULL所以链表是无环链表list 结构因为提供了表头指针 head 和表尾节点 tail所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)list 结构因为提供了链表节点数量 len所以获取链表中的节点数量的时间复杂度只需O(1)listNode 链表节使用 void* 指针保存节点值并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数因此链表节点可以保存各种不同类型的值
链表的缺陷也是有的
链表每个节点之间的内存都是不连续的意味着无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组因为数组的内存是连续的这样就可以充分利用 CPU 缓存来加速访问。还有一点保存一个链表节点的值都需要一个链表节点结构头的分配内存开销较大。
因此Redis 3.0 的 List 对象在数据量比较少的情况下会采用「压缩列表」作为底层数据结构的实现它的优势是节省内存空间并且是内存紧凑型的数据结构。
不过压缩列表存在性能问题具体什么问题下面会说所以 Redis 在 3.2 版本设计了新的数据结构 quicklist并将 List 对象的底层数据结构改由 quicklist 实现。
然后在 Redis 5.0 设计了新的数据结构 listpack沿用了压缩列表紧凑型的内存布局最终在最新的 Redis 版本将 Hash 对象和 Zset 对象的底层数据结构实现之一的压缩列表替换成由 listpack 实现。
压缩列表
压缩列表的最大特点就是它被设计成一种内存紧凑型的数据结构占用一块连续的内存空间不仅可以利用 CPU 缓存而且会针对不同长度的数据进行相应编码这种方法可以有效地节省内存开销。
但是压缩列表的缺陷也是有的
不能保存过多的元素否则查询效率就会降低新增或修改某个元素时压缩列表占用的内存空间需要重新分配甚至可能引发连锁更新的问题。
因此Redis 对象List 对象、Hash 对象、Zset 对象包含的元素数量较少或者元素值不大的情况才会使用压缩列表作为底层数据结构。 *zlbytes*记录整个压缩列表占用对内存字节数 *zltail*记录压缩列表「尾部」节点距离起始地址由多少字节也就是列表尾的偏移量 *zllen*记录压缩列表包含的节点数量 *zlend*标记压缩列表的结束点固定值 0xFF十进制255。 *prevlen*记录了「前一个节点」的长度 *encoding*记录了当前节点实际数据的类型以及长度 *data*记录了当前节点的实际数据 当我们往压缩列表中插入数据时压缩列表就会根据数据是字符串还是整数以及数据的大小会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息这种根据数据大小和类型进行不同的空间大小分配的设计思想正是 Redis 为了节省内存而采用的。 分别说下prevlen 和 encoding 是如何根据数据的大小和类型来进行不同的空间大小分配。 压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」而且 prevlen 属性的空间大小跟前一个节点长度值有关比如 如果前一个节点的长度小于 254 字节那么 prevlen 属性需要用 1 字节的空间来保存这个长度值如果前一个节点的长度大于等于 254 字节那么 prevlen 属性需要用 5 字节的空间来保存这个长度值 encoding 属性的空间大小跟数据是字符串还是整数以及字符串的长度有关 如果当前节点的数据是整数则 encoding 会使用 1 字节的空间进行编码。如果当前节点的数据是字符串根据字符串的长度大小encoding 会使用 1 字节/2字节/5字节的空间进行编码。 连锁更新 压缩列表除了查找复杂度高的问题还有一个问题。 压缩列表新增某个元素或修改某个元素时如果空间不不够压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时可能会导致后续元素的 prevlen 占用空间都发生变化从而引起「连锁更新」问题导致每个元素的空间都要重新分配造成访问压缩列表性能的下降。 前面提到压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配 如果前一个节点的长度小于 254 字节那么 prevlen 属性需要用 1 字节的空间来保存这个长度值如果前一个节点的长度大于等于 254 字节那么 prevlen 属性需要用 5 字节的空间来保存这个长度值 现在假设一个压缩列表中有多个连续的、长度在 250253 之间的节点 因为这些节点长度值小于 254 字节所以 prevlen 属性需要用 1 字节的空间来保存这个长度值 这时如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点即新节点将成为 e1 的前置节点
e1 原本的长度在 250253 之间因为刚才的扩展空间此时 e1 的长度就大于等于 254 了因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。
正如扩展 e1 引发了对 e2 扩展一样扩展 e2 也会引发对 e3 的扩展而扩展 e3 又会引发对 e4 的扩展…. 一直持续到结尾。
这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」就像多米诺牌的效应一样第一张牌倒下了推动了第二张牌倒下第二张牌倒下又推动了第三张牌倒下….
压缩列表的缺陷
空间扩展操作也就是重新分配内存因此连锁更新一旦发生就会导致压缩列表占用的内存空间要多次重新分配这就会直接影响到压缩列表的访问性能。
所以说虽然压缩列表紧凑型的内存布局能节省内存开销但是如果保存的元素数量增加了或是元素变大了会导致内存重新分配最糟糕的是会有「连锁更新」的问题。
因此压缩列表只会用于保存的节点数量不多的场景只要节点数量足够小即使发生连锁更新也是能接受的。
虽说如此Redis 针对压缩列表在设计上的不足在后来的版本中新增设计了两种数据结构quicklistRedis 3.2 引入 和 listpackRedis 5.0 引入。这两种数据结构的设计目标就是尽可能地保持压缩列表节省内存的优势同时解决压缩列表的「连锁更新」的问题。
仅供学习 切记用于任何商业用途 关注 _微_信_公_众_号 疯子爱淡定 回复 Redis核心技术学习 Hash
typedef struct dict {…//两个Hash表交替使用用于rehash操作dictht ht[2]; …
} dict;
----------------------------
typedef struct dictht {//哈希表数组dictEntry **table;//哈希表大小unsigned long size; //哈希表大小掩码用于计算索引值unsigned long sizemask;//该哈希表已有的节点数量unsigned long used;
} dictht;
----------------------------
typedef struct dictEntry {//键值对中的键void *key;//键值对中的值union {void *val;uint64_t u64;int64_t s64;double d;} v;//指向下一个哈希表节点形成链表struct dictEntry *next;
} dictEntry;
负载因子已保存节点数量/hash表大小当负载因子大于等于 1 并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令也就是没有执行 RDB 快照或没有进行 AOF 重写的时候就会进行 rehash 操作。当负载因子大于等于 5 时此时说明哈希冲突非常严重了不管有没有有在执行 RDB 快照或 AOF 重写都会强制进行 rehash 操作
