Redis

本文用于记录 Redis 相关知识，以备查阅。 01 Redis 数据结构Redis 数据类型是其值的数据类型，这些数据类型会使用相应的数据结构来实现，对应关系如下： Redis 本身使用了哈希表来保存所有的数据，哈希桶存放的是键值对的指针，指针的类型都通过对象结构来解码，里面包含了 type，encoding，ptr 等信息，整个映射过程如下： SDS：保存为 (len, alloc, flags, buf[]) ，其有以下优点：常量时间复杂度内获取字符串长度，二进制安全，不会发生缓冲区溢出，节省内存空间，另外为了节省空间，使用了 __attribute__ ((packed)) 双向链表：实现为具有头节点的双向链表，能够快速获取到头尾节点和链表长度等信息，但是存在无法很好利用 CPU 缓存和在数据较小时，内存开销较大的问题 压缩列表：内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，节省内存空间。但是其不能保存过多的元素，并且新增或者修改元素时，可能引发连锁更新的问题（通过 prevlen 长度改变造...

本文章是对《Redis 设计与实现》书籍的一个整理笔记，记录了其中个人认为比较重要的部分。 第二章 简单动态字符串 SDS 定义： SDS 与 C 字符串的区别： 常数复杂度获取字符串的长度 杜绝缓冲区溢出 减少修改字符串时带来的内存分配的次数，包括空间预分配和惰性空间释放 二进制安全 兼容部分 C 字符串函数 第二章 链表 Redis 的链表实现的特性可以总结如下： 双端 无环 带表头指针和表尾指针 带链表长度计数器 多态：链表节点使用 void*指针来保存节点值，并且可以通过 list 结构的 dup，free，match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值 第三章 字典 Redis 普通状态下的字典： 哈希算法：首先计算哈希值，然后计算出索引值 Redis 使用的 MurmurHash 算法计算建的哈希值，该算法的优点在于即使输入的键时有规律的，算法仍然能给出一个很好的随机分布性。 解决键冲突：使用链地址法解决键冲突，使用头插法进行插入。 rehash：当负载因子过大的时候，就会开始进行相应的扩展或...