1. 9IM首页
  2. 热点

谈谈对Redis中hash对象的理解

在Redis中,value可以是一个hash表,底层编码可以是ziplist,也可以是hashtable(默认情况下,当元素小于512个时,底层使用ziplist存储数据)

ziplist

元素保存的字符串长度较短且元素个数较少时(小于64字节,个数小于512),出于节约内存的考虑,hash表会使用ziplist作为的底层实现,ziplist是一块连续的内存,里面每一个节点保存了对应的key和value,然后每个节点很紧凑地存储在一起,优点是没有冗余空间,缺点插入新元素需要调用realloc扩展内存。(可能会进行内存重分配,将内容拷贝过去,也可能在原有地址上扩展)。

hashtable

元素比较多时就会使用hashtable编码来作为底层实现,这个时候RedisObject的ptr指针会指向一个dict结构,dict结构中的ht数组保存了ht[0]和ht[1]两个元素,通常使用ht[0]保存键值对,ht[1]只在渐进式rehash时使用。hashtable是通过链地址法来解决冲突的,table数组存储的是链表的头结点(添加新元素,首先根据键计算出hash值,然后与数组长度取模之后得到数组下标,将元素添加到数组下标对应的链表中去)。

struct dict {
    int rehashindex;
    dictht ht[2]; 
}
struct dictht {
    dictEntry** table; // 二维
    long size; // 第一维数组的长度 
    long used; // hash 表中的元素个数 ...
}
typedef struct dictEntry {
  //键  
  void *key;
  //值,可以是一个指针,也可以是一个uint64_t整数,也可以是int64_t的整数
  union {
    void *val;
    uint64_tu64;
    int64_ts64;
  } v;
  //指向下一个节点的指针
  struct dictEntry *next;
} dictEntry;

渐进式rehash

进行当负载因子>=1时,会进行哈希表扩展操作(如果是在执行BGSAVE或BGREWRITEAOF命令期间,那么需要>=5才会进行扩展)。

进行当负载因子<0.1时,会进行哈希表收缩操作。

因为直接一次性完成rehash会对性能产生影响,所以可以渐进式rehash,具体执行步骤是:

初始化

1.首先将对dict结构中ht[1]哈希表分配空间(大小取决于最接近实际使用空间的2的n次方幂),然后将rehashindex属性设置为0。

转移

2.然后每次对ht[0]中的元素查找,修改,添加时,除了执行指定操作外,还会将对应下标的所有键值对rehash到ht[1],并且会将rehashindex+1。

更改指针指向

3.当ht[0]中所有键值对都是rehash到ht[1]中后,那么会ht[1]和ht[0]的指针值进行交换,将rehashindex设置为-1,代表rehash完成。 (整个rehash期间,查找,更新,删除会先去ht[0]中执行,没有才会到ht[1]中执行,新添加键值对是会被保存到ht[1]中)。

原创文章,作者:9IM,如若转载,请注明出处:https://www.9im.cn/645.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注