搞懂Redis（二）-3：Hash数据结构

当Hash的数据项较少时,Hash底层才会用压缩列表zipList进行存储数据.数据增加,底层的zipList会转成dict,
具体配置如下

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

dict的数据结构:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
    //指针数组，这个hash的桶
    dictEntry **table;
    //元素个数
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

dictEntry大家应该熟悉，在上面有讲，使用来真正存储key->value的地方
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        // 指向具体redisObject
        void *val;
        // 
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
    //指针数组，这个hash的桶
    dictEntry **table;
    //元素个数
    unsigned long size;
    unsigned long sizemask;
    unsig-2ned long used;
} dictht;

dictEntry大家应该熟悉，在上面有讲，使用来真正存储key->value的地方
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        // 指向具体redisObject
        void *val;
        // 
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

由此可见,每个dict中有两个hashtable
结构图如下:

hash结构图
虽然dict结构有两个hashtable,但通常只有一个hashtable有值.但当dict扩容缩容时,需要重新分配新的hashtable. 然后进行渐进式搬迁,这时两个hashtable存储的旧hashtable和新的hashtable.搬迁结束后旧的hashtable删除,新的取而代之.

渐进式rehash

指大字典扩容较耗时,需重新申请新的数组,然后将旧字典所有链表的元素重新挂接到新的数组下面,是一个O(n)的操作.
因为Redis是单线程的,无法承受这样的耗时过程,所以采用渐进式rehash小步搬迁,虽然慢一点,但可以搬迁完毕.

扩容条件

扩容一般在hash表中的元素个数等于第一维数组长度时,开始扩容. 扩容大小是原数组的两倍.不过在Redis做bgsave(RDB持久化操作的过程),为了减少内存页的过多分离(copy on write),Redis不会去扩容. 但如果hash表的元素个数已经达到了第一维数组长度的5倍时,就会强制扩容,无论是否在持久化.

不扩容主要是为了尽可能减少内存页过多分离,系统需要过多的开销去回收内存 .

缩容条件

当我们的hash表元素逐渐删除越来越少时,redis于是就会对hash表进行缩容来减少第一维数组长度的空间占用. 缩容条件是元素个数低于数组长度的10%,并且缩容不考虑是否在持久化.

不用考虑bgsave主要是因为我们的缩容的内存都是已经使用过的,缩容的时候可以直接置空,而且由于申请的内存比较小,提示会释放一些已经使用的内存,不会增大系统的压力.

rehash步骤:

1. 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表;
2. 定时维护一个索引计数器变量rehashIdx,并将值设为0,表示rehash开始.
   3.在rehash进行期间,每次对字典执行CRUD操作时,程序除了执行指定操作外,还会将ht[0]中的数据rehash到ht[1]表中,并且将rehashIdx+1
   4.当ht[0]中所有元素转移到ht[1]中时,将rehashidx设置为-1,表示rehash结束
   (采用渐进式rehash的好处:--分而治之,避免集中rehash带来的庞大计算量.特别在进行rehash时只能对ht[0]元素减少的操作. 如查询和删除;而查询是在两个哈希表中查找的,而插入只能在ht[1]中进行,ht[1]也可以查询和删除.)
   5.将ht[0]释放,然后将ht[1]设置为ht[0],最后为ht[1]分配一个空白的哈希表.

过程图如下:

rehash过程