1. Redis 设计与实现
   1. Redis 的 String 设计
   2. Redis 的链表设计
   3. Redis 的字典实现
   4. Redis 的跳表实现
   5. Redis 的压缩列表实现
   6. Redis 的引用对象实现

Redis 设计与实现

Redis 的 String 设计

redis 对于 String 类型有自己的实现, 这个实现简称 SDS (simple dynamic string).

SDS 的优势：
- 安全性、效率、功能方面的需求
O(1)的获取字符串长度的效率，根据len字段
杜绝缓冲区溢出、根据free字段判断是否扩容

- 内存预分配：
        len小于1M，修改之后的len的长度 = free长度
        大于1M，直接free 1M

- 惰性释放：
        不返还 free 的区域= = 以便下次使用

- 二进制安全：
        \0 作为分隔符时，因为有len判断字符串长度，不会出现问题

    兼容部分C字符串函数

Redis 的链表设计

链表：用于列表键、pub/sub、慢查询、监视器
- 双端：获取前后节点复杂度都O(1)

- 无环：前后NULL节点

- 带head tail

- 表长len

- 多态 void* 保存节点值

Redis 的字典实现

字典：SET 和 HSET
- 使用哈希表错位底层实现，是redis 是数据库的存储方式
- 使用dictht 作为哈希表实现，封装成 dict，内有长度为2的dictht数组，
用来做扩容，标记位为-1时表示不在rehash
dict ｛
dictht[2]
dictType 实现多态的函数，复制对比删除等
rehashindex -1表示不在rehash
｝
扩展 ht[1]大小为 第一次大于ht[0].used*2 的 2^n
收缩 。。。。。。。。。大于ht[0].used 的 2^n
- 渐进式哈希：每次插入删除查找更新都rehash一次

Redis 的跳表实现

跳表：
- 实现有序集数据
- 随机化数据结构、它的查找添加删除都可以在对数期望时间下完成

Redis 的压缩列表实现

压缩列表：
- ziplist结构：
header - entries - end
bytes-tail-len
- entry结构：
prelen - encoding - len - content

Redis 的引用对象实现

redisObject 结构：
- key 对应的是一个 redisObject 结构，用来多态操作
redisObject {
type.
encoding. type 和 encoding 定位底层数据结构
*ptr
}
引用计数回收

• 哈希表默认由压缩列表实现：当某个key/value长度大于64

                    或者 entries 的个数大于 512 
                    会转变成字典实现

• 列表默认也由压缩列表实现：同上；会转变为双端链表

• 阻塞：维持一个server[i]->block_keys列表，key为造成阻塞的key，value为客户端链接
  readyList 用来保存即将离开block队列

• 事务：WATCH MULTI DISCARD EXEC

• 慢日志查询：设置时间和保存数量

     SLOW GET 查看

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 nickchenyx@gmail.com