当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步骤:
- 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表;
- 定时维护一个索引计数器变量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过程
