【Redis学习4】redis底层核心设计原理

发表于 | |

SDS

simple dynamic string
redis 3.2以前

1
2
3
4
5
6
7
struct sdshdr {
    int len; //32 bit 0-2 32次方-1
    int free;
    char buf[];
};

typedef char *sds

redis3.2以后

1
2
3
4
5
6
typedef char *sds;
sdshdr5
sdshdr8
sdshdr16
sdshdr32
sdshdr64

对sdshdr做了优化和细分;
内存对齐：
图片

key类型

string

值类型

string,hash,set, sorted set,list

  • K-V: 是一个dict数据类型。
    海量数据的存储：
  1. 数组: O(1)
  2. 链表: O(N)
  3. 树： long(N)

arr[4]
hash(key) -> 自然数%4 。变成索引。

hash(k1) % 4 = 0
hash(k2) % 4 = 1
hash(k3) % 4 = 1

arr[0] -> (k1, v1,next -> null)
arr[1,2] -> (k3, v3, next -> k2) (k2, v2, next -> null)

当数组容量很大时，hash碰撞加剧。数据结构由数组变成了链表，时间复杂度从O(1)退化成
O(N) 此时需要进行扩容。

k2,k3碰撞了怎么办？

  1. 开放地址法。
  2. 链表法
  3. 头插法（redis使用的方式）

redisDB的设计
redis总共16个Db 索引从0-15

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
43
44
45
46
typedef struct redisDb {
    dict *dict;
    dict *expires;
    dict *blocking_keys;
    dict *watched_keys;
    int id;
    long long avg_ttl;
    unsigned long expires_cursor;
    list *defrag_later;
} redisDb;

_typedef struct dict {_
    dictType *type;
    void *privdata;
    dictht ht[2];//ht : hashTable的缩小
    long rehashidx;
    unsigned long iterators;
} dict;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdate, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
}

typedef struct dictht {
    dictEntry **table;
    unsigned long size; // hashtable 容量
    unsigned long sizemask; //size - 1
    unsigned long used; //hashtable元素个数 used/size = 1
} dictht;
//redis值类型对象封装 string,list,set,hash, zset
typedef struct redisObject {
    //约束能够对redis key进行的操作 lpush，get什么的
    unsiged type:4;  // 4bit,string hash
    //object encoding key 支持。对应的值在redis底层用的编码形式
    unsigned encoding:4; // 4bit
    unsigined lru:LRU_BITS;
    //管理内存，引用计数法！这里表示引用的数量。0的时候可以进行回收。
    int refcount;  //4 byte
    //指向数据的地址
    void *ptr;      //8byte
} robj;

扩容方法 。原有容量 *2.
rehash迁移方式：1. 渐进式迁移。2. 定时迁移。

set xxx // set是对 string操作。所以 type xxx也是string
lpush xxx // lpush 操作 type xxx 是list