乐趣区

关于redis:Redis设计与实现

jiezi

概述

字符串

SDC(Simple Dynamic String, 简略动静字符串)作为字符串示意

每个 sds.h/sdshdr 构造示意一个 SDS 值
struct sdshdr{

...

}
len
free
buff

劣势

  1. 常数复杂度获取字符串长度
    数据结构中有 len 属性用于保留字符串的长度
  2. 杜绝缓冲区溢出
    在字符串进行扩大前, 会先检查一下 buff 的长度是否足够, 如果不够的话就会进行扩大, 而后再执行增加字符的操作
  3. 缩小内存调配次数
    SDS 通过两种策略来实现
    3.1 空间预调配
    如果对 SDS 进行批改之后,len 属性小于 1MB, 那么程序调配和 len 同样大小的未应用空间, 即 len 和 free 属性值雷同; 如果大于 1MB, 那么将调配 1MB 未应用空间
    3.2 惰性空间开释
    当 SDS 的 API 须要缩短保留的字符串时,内存重调配 不会立刻开释未应用的空间, 而是将其作为 free 的数量
  4. 二进制平安
    首先须要理解 C,C 的字符串必须合乎某种编码, 例如如果一开始读入空格将被辨认为结尾
    SDS 以二进制模式存储, 文本存进去是什么内容, 拿进去就还是什么内容

  5. 兼容局部 C 字符串函数
    SDS 遵循 C 字符串以空字符结尾, 这样就能重用 /<string.h> 的 stracasecmp 函数

    strcasecpm(sds->buff,"hello world!")

    链表

    数据结构

    双向链表
    typedef struct list{
    …
    }list
    listNode * head;
    温习一下结点的数据结构
    typedef struct listNode{
    struct ListNode * prev;
    struct ListNode * next;
    void * value;
    }
    listNode * tail;
    unsigned long len;
    // 节点复制函数
    void (dup)(void *ptr)

    个性

    双端、无环、带表头和表尾指针、带链表长度计数器和多态
    对于多态这里解释一下, 以复制函数为例, 应用的 void* 指针来保留节点值, 所以能够保留各种不同类型的值

    用处

  6. 列表键、公布与订阅、慢查问、监视器等
    列表键临时不知
    公布与订阅容易音讯失落, 实用于要求不高的场景, 能够从确保音讯不失落的问题从延长
    慢查问临时不知
    监视器临时不知

    字典

    哈希表节点与哈希表数据结构

    键值节点构造

    哈希表构造

    字典构造

    从下面的图里能够看到, 字典中有哈希表构造, 而哈希表中有 key-value 键值节点

    哈希算法

    通过键来计算出哈希值和索引值(通过哈希值和哈希掩码计算出来), 将蕴含新键值对的哈希表节点放在置顶索引下面

    解决键抵触(哈希抵触)

    链表法

    rehash(从新散列)

    说人话就是为了在字典外面的数据减少或者缩小的时候将哈希表的长度管制在肯定范畴内, 防止不够用或者过于节约
    当哈希表减少或者缩减到肯定水平时就会触发 rehash 操作

  7. 如果是减少, 那么 ht[1]的大小等于 ht[0].used* 2 的 2^n^
    如果是缩小, 那么 ht[1]的大小等于 ht[0].used 的 2^n^
  8. 将 ht[0]的所有键值都放到 ht[1]中, 这个过程会从新计算 hash 值和索引值

  9. 开释 ht[0], 而后将 ht[1]设置为 ht[0], 并且在 ht[1]新创建一个空白哈希表, 为下一次的 rehash 做筹备

    渐进式 rehash

    先定义一个 rehashindex 变量, 初始值为 0, 在执行新增、删除、查问时都会将对应 ht[0]的 redisindex 索引处的 key-value 从新散列到 ht[1], 并且在渐进式 rehash 期间, 新增的结点不会进入到 ht[0]中, 就保障了 ht[0]最终会成为空表

    跳跃表

    几个重要的概念

  10. 后退指针
    每个跳跃表结点都有指向下一个结点的指针
  11. 层
    每个跳跃表结点都会有很多层, 至于具体是干什么的当初还不太分明
  12. 后退指针
    最初一个跳跃表结点指向前一个结点
  13. 跨度
    就是从头结点开始到指标结点经验的门路, 有点想图的权

  14. 分值和成员
    分值是一个 double 类型的浮点数, 跳跃表中的所有的结点的分值依照从小大来排序

    对象是一个指针, 它指向一个字符串对象, 而字符串对象中则保留一个 SDS 值
    不太分明一个跳跃表结点是不是只能寄存一个对象, 然而我猜想是这样的

    总结

  15. Redis 的跳跃表实现是由 zkiplist 和 zkiplistNode 两个构造组成, 其中 zkiplist 用于保留跳跃表信息(比方表头节点、表尾节点、长度), 而 zskiplistNode 则用于跳跃表节点

  16. 多个跳跃表节点的分值能够雷同, 然而对象必须惟一

    整数汇合

    整数汇合是汇合键的底层实现之一, 当一个汇合只蕴含整数值元素, 并且这个汇合的元素数量不多时,Redis
    sadd numbers 1 3 5 7 9
    下面的命令用的是 sadd, 阐明用的汇合 set 的根本类型(Redis 对外提供的)

    降级

    先来看数据结构

    typedef strunct intset{unit32_t encoding;}

    下面的 encoding 属性决定以后数组的元素是用什么形式编码, 如果以后是 inset_enc_int16, 此时再增加进一个 64 位编码的元素那么就会执行降级操作
    整数汇合只反对 降级 而不反对降级

    压缩列表

    压缩列表 ziplist 是列表键 (List???) 和哈希键 (Hash???) 的底层实现之一。当一个列表键只蕴含大量列表项, 并且每个列表项要么是小整数值, 要么是长度比拟短的字符串, 那么 Redis 就会应用压缩列表来做列表键的底层实现
    在 3.2 和 5 之后引入了 quicklist 和 listpack, 所以废除了

    对象

    5 种根本类型

    就是入门篇里提到的 5 种类型对象
    注: 因为 Redis 外面都是键对象和值对象, 所以这一章的角度都是从这两个对象登程
    EVAL “for i=1, 128 do redis.call(‘ZADD’, KEYS[1], i, i) end” 1 numbers
    下面这段代码是往一个 zset 外面插入 128 个元素, 从 1 开始
    在开始内容之前须要先看一个数据结构

    typedef struct redisObject{
 // 类型
 unsigned type:4;
 // 编码
 unsigned encoding:4;
 // 指向底层实现数据结构的设计
 void *ptr;    
 // 对象的空转时长
 unsigned lru:22;
 // 援用计数
 int refcount;
}

    不同类型的编码方式

    尽管 Redis 有 5 种根本数据类型, 然而每种数据类型还是的底层还是有至多两种以上的编码方式 (这里说的编码方式和底层用的数据结构不是一个概念)
    这里就不得不提一下多态了, 真的是随处可见, 比如说所有的类型都可能应用命令 DEL
    有些命令是数据类型独有的, 例如 RPUSH、ZADD, 这些命令在执行时, 不同底层编码方式也都会执行这些指令。

    类型查看

    服务器在执行某些命令前, 会先查看给定键的类型可能执行指定的命令, 其实就是查看值对象的类型

    内存回收机制

    对象上有个字段 refcount, 代表以后对象被援用次数, 如果为 0, 则会从内存中删除掉

    内存共享

    0-9999 整数值会事后存好, 就像 Java 的字符串常量池一样

    空转工夫

    越近拜访的值空转工夫会越少

    单机数据库的实现

    抉择数据库

    select 0(index)
    客户端程序中有个数据结构, 其中有个属性保留了以后客户端应用的数据库

    数据库键空间

    数据库键空间是这一章的重点

    对于键值变动时的操作过程

  17. 新增键
  18. 删除键
  19. 更新键

  20. 读写键的保护操作
    服务器中键有命中和不命中次数属性, 是一个统计指标
    键有 ideltime, 用来批示键的闲置工夫
    键有过期时长, 不晓得和这个闲置工夫的属性有什么关系
    键有个属性代表是否被批改, 书上说的是键是不是为 dirty(脏键), 每次批改这个值都会被加 1, 如果客户端应用 WATCH 命令对其进行了监听, 那么客户端程序在执行事务程序时就会留神到。

    设置生存或者过期工夫

    RDB 长久化

    SAVE 和 BGSAVE

    Mac 下应用 Homebrew 装置的 Redis 的 RDB 文件地位

  21. 首先还是得找到 redis.conf 的地位
    应用 brew info redis 命令能够查看到
    /opt/homebrew/etc/redis.conf

  22. 在 redis.conf 找到 dbfilename 和 dir 属性的值来确定文件名称和门路
    db.dump 和 /opt/homebrew/var/db/redis

    AOF 长久化

    AOF 缓冲区

    重写

    AOF 重写缓冲区

    事件

    首先来温习一下多路复用, 没方法用的多有什么辙
    几个要害的记忆点,bind()函数和 accept()函数,socket
    客户端 connect()
    已连贯队列
    多过程模型
    多线程模型
    IO 多路复用模型 select()和 poll()
    IO 多路复用模型 epoll()
    事件机制, 回调函数

    Redis 中的 IO 多路复用

    客户端

    次要内容是服务器外部保留的 redis-client 构造, 对其中的的属性进行解说

    服务端

退出移动版