redis设计和实现

简单动态字符串

sds定义

1
2
3
4
5
struct sdshdr{
    int len;已经使用的长度,等于sds所保存字符串的长度
    int free;未使用字节的数量
    char buf[]保存字符串
}

sds和c字符串的区别

1
2
3
4
5
1,常数复杂度获取字符串长度
2,杜绝缓冲区溢出
3,减少修改字符串时带来的内存重分配次数
4,二进制安全
5,兼容部分c字符串函数

链表

1
2
3
4
5
6
7
8
9
10
11
12
struct listNode{
    listNode prev;前节点
    listNode next;后节点
    void * value;值
}
struct list{
    listNode head;头
    listNode tail;尾
    long len;数量
    free    释放函数
    match   值对比函数
}

字段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
哈希表
struct dictht{
    dictEntry table;hash数组
    long size;大小
    long sizemask;掩码(size-1)
    long used   使用数量
}
哈希表节点
struct dictEntry{
    void key;
    union{
        val
        uint64_tu64
        int64_ts64
        } 
    dictEntry   next;
}
字典
struct dict{
    dictType type;  类型特定函数
    void privdata   私有数据
    dictht ht[2]    哈希表
    in trahashidx   rehash索引.当rehash不在进行时,值为-1
}


keyhash=dict->type->hashRunction(key)
index=hash&dict->ht[x].sizemask
解决健冲突
hash相同后续链表

rehash
    扩展和收缩
        负载因子=已保存节点数量/哈希表数量
            负载因子需要维持在一个合理的范围
            扩展/收缩(>=1   <0.1)
渐进式rehash
    每次添加,删除,查找或者更新时,都会操作一部分.(rehahsidx-1)每次进行减一
    防止因为太多数据导致复制时耗时太久
1
2
3
4
5
6
7
8
9
10
https://blog.csdn.net/nwpu_geeker/article/details/79695625
redis
单线程渐进式
增删改查   reshahidx-1 操作
逐渐进行操作
concurrenthashmap
多线程渐进式
读->老->新
写/删->旧->操作
       新->扩容->操作

跳跃表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
skiplist 是一种有序结构
支持平均   logn,最坏 n复杂度的节点查找


struct zskiplistNode{
    //层
    zskiplistLevel{
        zskiplistNode forward: 前进指针
        int span    
    }
    zskiplistNode backward: 后退指针
    double score
    robj obj
}

整数集合(intset)

1
2
3
4
5
struct intset{
    uint32_t encoding: 编码方式
    uint32_t length;元素个数
    int8_t  contents[];保存原始的数组
}
1
2
3
4
5
6
7
8
9
升级
    分配新空间
    转换升级后类型
    将新元素添加到底层数组里边
 好处
    提升灵活性
    尽可能节约内存   
降级
    不支持降级

压缩列表

1
zlbytes zltail  entry1  entry2  ... entryN  zlend
1
2
连锁更新
    前边修改长度后,后边需要修改长度引起级联反应重新分配空间

对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
字符串对象
    编码:int raw   embstr
    实现:数字/sds
列表对象
    ziplist/linkedlist
    1,key/val<64字节
    2,size<512   
    1+2=ziplist,其他linkedlist
哈希对象
    ziplist/hashtable
    1,key/val<64字节
    2,size<512   
    1+2=ziplist,hashtable
集合对象
    intset/hashtable
    1,key都是整数
    2,size<512   
    1+2=ziplist,hashtable
有序集合对象
    ziplist/skiplist
    1,size<128
    2,所有成员长度<64   
    1+2=ziplist,skiplist


内存回收
struct redisObject{
    int refcount
}
创建,引用+1
被新程序使用+1
不再使用-1
引用=0,对象释放

对象共享
共享计数+1


对象空转时长
struct redisObject{
    int lru:22      对象最后被使用的时间
}

数据库

过期健删除策略

1
2
3
4
5
6
7
8
9
10
11
定时
    对内存友好,对cpu不友好
    大量过期健,删除需要很多一部分cpu时间,在内存充足,cpu时间浪费在删除上边,会对服务器响应时间和吞吐量造成影响.
惰性
    对内存不友好,对cpu友好
    取出才会检查,当大量过期但不回收,会造成不可用,内存泄露.
定期
    是定时和惰性的整合和折中.
    定期删除策略每隔一段时间执行执行一次删除健操作,并通过限制删除操作执行的时长和频率来减少删除操作对cpu时间打影响
    除此之外,通过定期删除过期健,定期删除策略有效的减少了因为过期健而带来的内存浪费
    难点:确定操作执行的试产和频率
1
惰性+定期

aof rdb 复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
rdb(频率写入)
    生成(save,bgsave)
        save:同步阻塞服务
        bgsave:异步,生成新的线程创建
        过期不会保存rdb内
    载入
        载入期间会一直处于阻塞
        主
            只载入未过期
        从
            全部载入,主从同步时会进行清理
aof(有命令写入)
    生成
        过期会生成删除记录
    重写
        只会重写有效的
    复制
        主
            删除key后会主动向从发送del
        从
            及时碰到过期也不会删除,继续像未过期的健一样处理
            从服务器收到主动del命令后才会删除过期健

事件

1
2
3
redis服务器是一个事件驱动程序,服务器需要处理下面两类时间"
    文件时间:服务器对套接字操作的抽象
    时间事件:在给定的时间点执行

文件事件

1
io多路复用

时间事件

客户端

服务端

复制

1
2
3
4
5
6
7
8
9
旧版:
    同步(sync):将从服务器的数据库状态更新至主服务器当前所处的数据库状态
    命令传播(command propagate):主服务器的数据库状态被修改,导致主从服务器的数据库状态不一致时,让从服务器的数据库重新回到一致状态
  缺陷:
    初次复制:全部复制
    短线后重复制:全部复制
新版:
    完整重同步:全部
    部分重同步:没有发送的才发送

sentinel

集群

1
2
3
4
5
6
7
8
9
10
11
12
13
16384
计算属于哪个槽
crc16(key)&16384

重新分片

在迁移过程中,有一部分键值保存在目标节点
ask错误
源节点不存在,则指向新节点

确定move的情景
ask  移动过程中
move 已经移动完毕