Redis数据库实现

数据库作用

完成海量数据的存储

可选数据结构

• 数组，查询速度O(1)
• 链表，查询速度O(n)
• 树，查询速度O(logn)
  Redis是使用数组+链表完成海量数据存储

实现简述

在Redis中，key的存储形式最终会转换成string，借助hash函数，可以将key转换成自然数。
hash(key) -> 自然数，完成数组下标访问。
自然数是一个很大的值，直接使用的话需要给数组开辟一个很大的空间，内存利用率不高。
采用取模方式去开辟空间，例如数据库dict大小size为10，那么此时hash函数为
hash(key) -> 自然数 % dict.size, 结果范围是 0 ~ dict.size - 1
例如：
dict[0] = (k1,v1)
dict[2] = (k2,v2)
dict[3] = (k3,v3)
dict每个下标存储的是第一个kv结构体的指针值

解决哈希碰撞

哈希函数特点：

1. 任意相同的输入，一定能得到相同的输出。
2. 不同的输入，有可能得到相同的输出。

当发生碰撞时，采用链表法解决，头插法。
例如k4,v4得到的哈希值为0，那么
dict[0] -> (k4,v4) -> (k1,v1)
dict[2] = (k2,v2)
...
value之间是以链表形式连接起来。

源码实现

server.h

typedef struct redisDb{
    dict *dict;    // 存储key-value
    dict *expires; // 用于存储过期时间key
    dict *blocking_keys; // 用于阻塞队列，维护key与客户端连接关系
    dict *ready_keys;   // 阻塞队列就绪的key
    int id;            // 数据库id，默认是0~15
...
}redisDb

dict源码

typedef struct dict{
    dictType *type; // 函数哈希函数实现，key冲突时比对等方法 
    void *privdata; // 一般为null
    dictht ht[2];// 存储数据的哈希表，分新旧两个，dict[1]平时为null
    long rehashidx;
}dict

dictht源码

typedef struct dictht{
    dictEntry **table; //  指向k-v实体指针的指针
    unsigned long size;  // hashtable容量
    unsigned long size_mask; // size - 1
    unsigned long used; // hashtable元素个数
}dictht

之所以有两个dictht，是为了实现渐进式hash，当hash冲突过多或者达到容量上限，进行扩容。
扩容是成倍的，产生一个新的dictht。
但扩容并不是一次性把旧的dictht中数据拷过来，因为是单线程的，拷贝是耗时操作，会影响主线程其他操作。 每次访问某些key时，把key移动到新的dictht， 同时也会把部分其他没访问的key也进行移动，直到把所有key移动完毕，旧的dictht释放。

dictEntry源码

typedef struct dictEntry{
   void *key // 指向SDS结构体的指针
   union {
       void *val; // 当作为k-v，指向值类型
       uint64_t u64;
       int64_t s64;
       double d;
    } v 
struct  dictEntry *next;  //     解决hash冲突问题
} dictEntry;

值类型

typedef struct redisObject{
    unsigned type:4 ;      //4 bit，标识数据类型，string，list，set，zset，hash，约束api使用
    unsigned encoding:4;   //4 bit，int，embstr，raw(sds)
    unsigned lru:24;     //4 bit 内存淘汰策略
    int refcount;    //4 bytes 引用计数管理内存
    void* ptr;      //8bytes 指向真正存放数据的位置
} robj; //总空间: 4bit + 4bit + 24bit + 4byte + 8byte = 16byte

redisObject用于存放string，list，set，zset，hash数据对象。
encoding用于表示编码类型，不同的string在底层编码不一样

127.0.0.1:6379> set int 100
OK
127.0.0.1:6379> set key value
OK
127.0.0.1:6379> type int
string
127.0.0.1:6379> type key
string
127.0.0.1:6379> object encoding key
"embstr"
127.0.0.1:6379> object encoding int
"int"

存储整型值：
在64位系统下，ptr占64bit，能表示 2^64-1的长整数，当数字字符串长度<=20时，直接将数字字符串转成整型值并存放在val指针上，减少额外开辟一个地址存放这个值，提升访问速度。

存储小字符串(embstr)：
cpu根据地址去内存获取数据，64位系统下缓存行 cache line大小为64bytes，redisObject结构体本身占16byte，还有48byte可用，为了利用48byte，使用sdshdr8数据类型，再减去4byte，所以剩下44byte，当字符串长度在44byte以内，就可以将整个数据都放入到cache line一次读到。

当长度大于44，就使用raw进行编码

验证：

127.0.0.1:6379> set key aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeee
OK
127.0.0.1:6379> strlen key
(integer) 44
127.0.0.1:6379> object encoding key
"embstr"
127.0.0.1:6379> set key aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeff
OK
127.0.0.1:6379> object encoding key
"raw"