Redis索引模型

(1) redis整体存储结构

redis索引模型

(2) Redis索引模型

Redis怎么根据key定位到value

(2.1) 哈希函数

Redis使用的siphash.c文件里的siphash

(2.2) 哈希冲突解决

1.Redis的hash表是全局的,所以当写入大量的key时,将会带来哈希冲突,已经rehash可能带来的操作阻塞
2.Redis解决hash冲突的方式,是链式哈希:同一个哈希桶中的多个元素用一个链表来保存
3.当哈希冲突链过长时,Redis会对hash表进行rehash操作。rehash就是增加现有的hash桶数量,分散entry元素。

(2.3) 哈希表扩容-渐进式rehash

dict的渐进式rehash是为了避免扩容时的整体拷贝,这会给内存带来较大压力。

渐进式rehash执行时,除了根据键值对的操作来进行数据迁移,Redis本身还会有一个定时任务在执行rehash,如果没有键值对操作时,这个定时任务会周期性地(例如每100ms一次)搬移一些数据到新的哈希表中,这样可以缩短整个rehash的过程。

1.在进行渐进式 rehash 的过程中, 字典会同时使用 ht[0] 和 ht[1] 两个哈希表

2.在渐进式 rehash 进行期间, 字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行:
比如说, 要在字典里面查找一个键的话, 程序会先在 ht[0] 里面进行查找, 如果没找到的话, 就会继续到 ht[1] 里面进行查找, 诸如此类。

3.在渐进式 rehash 执行期间, 新添加到字典的键值对一律会被保存到 ht[1] 里面, 而 ht[0] 则不再进行任何添加操作: 这一措施保证了 ht[0] 包含的键值对数量会只减不增, 并随着 rehash 操作的执行而最终变成空表。

渐进式rehash


(3) Redis索引模型源码解读

(3.1) Redis服务端结构体-redisServer

// file: /src/server.h

struct redisServer {
    /* General */
    pid_t pid;                  /* 主进程pid */
    pthread_t main_thread_id;   /* 主线程id */
    char *configfile;           /* 配置文件绝对路径,或 NULL */
    char *executable;           /* 可执行文件绝对路径。 */
    char **exec_argv;           /* 可执行 argv 向量(副本)。 */
    int dynamic_hz;             /* 根据客户端数量更改 hz 值。 */
    int config_hz;              /* 配置的 HZ 值。如果启用了动态hz,则可能与实际的“hz”字段值不同。 */
    mode_t umask;               /* 进程启动时的 umask 值 */
    int hz;                     /* serverCron() 调用频率  */
    int in_fork_child;          /* 复制的子进程 */
    redisDb *db;                /* 数据库 */    
    dict *commands;             /* 命令表 */
    ...
};

(3.2) Redis数据库-redisDb

// file: src/server.h

/* Redis数据库表示。
   有多个数据库由从 0(默认数据库)到最大配置数据库的整数标识。
   数据库编号是结构中的“id”字段。 
*/
typedef struct redisDb {
    dict *dict;                 /* 这个数据库存储的key集合 */
    dict *expires;              /* 设置了超时时间的key集合 */
    dict *blocking_keys;        /* 客户端等待数据的key集合 (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

 redis默认有16个db,每个db里保存了

(3.3) dict

// file: /src/dict.h

/**
 * 字典结构体
 */
typedef struct dict {
    dictType *type;  /** 字典类型 */
    void *privdata;  /** 私有数据 */
    dictht ht[2];    /** 全局哈希表 2个 默认使用第0个,扩容时使用第1个 */
    long rehashidx;  /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

(3.4) 哈希表-dictht

Redis里的哈希表数据结构的实现是dictht
哈希函数使用 ``
哈希冲突使用 链地址法

// file: /src/dict.h

/** 
 * 这是哈希表结构。
 * 每个字典都有两个这样的字典,因为我们实现了增量重新哈希,从旧表到新表。 
 */
typedef struct dictht {
    dictEntry **table;   // 一维数组的指针
    unsigned long size;  // 哈希表大小  
    unsigned long sizemask;  // size-1 = (2^n - 1),比2^n少1,用于计算key对应桶的下标
    unsigned long used;  // 已使用个数 
} dictht;

(3.5) dictEntry

// file: src/dict.h

/** 
 * 哈希表节点/Entry实体 
 */
typedef struct dictEntry {
    void *key; // key的指针
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;  // value  联合结构体(不同场景使用不同大小,省内存)
    struct dictEntry *next;  // 链表的下一个节点的指针
} dictEntry;

 dictEntry里保存了key指针next指针,各8字节

(3.6) Redis对象类型-redisObject

/**
 * Redis对象类型
 */
typedef struct redisObject {
    unsigned type:4;  // 数据类型  4个bits
    unsigned encoding:4;  // 编码方式 4个bits
    unsigned lru:LRU_BITS;  // LRU时间(相对于全局 lru_clock) 或 LFU数据(低8位保存频率 和 高16位保存访问时间)。  LRU_BITS为24个bits
    int refcount;  // 引用计数  4字节
    void *ptr;  // 指针 指向对象的值  8字节
} robj;

 redisObject保存了

(3.7) redis查找key方法

(3.7.1) 数据库里找对应的对象

// file: /src/db.c

/**
 * 低级key查找API
 * 实际上并没有直接从应该依赖lookupKeyRead()、lookupKeyWrite()和lookupKeyReadWithFlags()的命令实现中调用。
 *
 * Low level key lookup API, not actually called directly from commands 
 * implementations that should instead rely on lookupKeyRead(),
 * lookupKeyWrite() and lookupKeyReadWithFlags(). 
 */
robj *lookupKey(redisDb *db, robj *key, int flags) {
    // 从db的dict里去找key对应的桶/链表节点
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) { // 如果节点存在
        // 从节点里获取对应的对象
        robj *val = dictGetVal(de);

        /* Update the access time for the ageing algorithm.
         * Don't do it if we have a saving child, as this will trigger
         * a copy on write madness. */
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            // 
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                // 更新lfu
                updateLFU(val);
            } else {
                // 更新lru
                val->lru = LRU_CLOCK();
            }
        }
        // 返回查到的值
        return val;
    } else {
        return NULL;
    }
}

(3.7.2) 字典里找对应的节点

// file: /src/dict.c

/**
 * 从db的dict里去找key对应的节点
 *
 * @param *d 字段
 * @param *key 键
 */
dictEntry *dictFind(dict *d, const void *key)
{
    // 链表节点  可能为空
    dictEntry *he; 
    uint64_t h, idx, table;

    // 字典是空的,字典里两个哈希表都是空的
    if (dictSize(d) == 0) return NULL; 

    // 如果正在rehash,执行一小步rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 计算key的hash
    h = dictHashKey(d, key);
    // 有2个哈希表 ht[0] ht[1],有可能正在rehash,所以都要查,对应代码是 table=0 table<=1
    for (table = 0; table <= 1; table++) {
        // 获取数组索引下标
        idx = h & d->ht[table].sizemask;
        // 桶/链表头结点
        he = d->ht[table].table[idx];
        // 遍历链表
        while(he) {
            // key相同 或 key对比相等
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he; // 返回对应节点
            he = he->next;
        }
        /**  */
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}
// file: dict.h

/** 从节点里获取对应的对象 */
#define dictGetVal(he) ((he)->v.val)

参考资料

[1] redis源码-github