深入学习Redis(三),基本类型【Hash】剖析

作者:ToBeTopJavaer / 公众号:javaer000000 发布时间:2019-11-01

喜欢就点关注吧!
接下来我们要剖析的基本类型是Hash,相信大家对Hash都不会陌生吧,下面我们将深入源码剖析Redis中Hash的实现。
首先我们看一张图:
存储类型
包含键值对的无序散列表。value 只能是字符串,不能嵌套其他类型。
同样是存储字符串,Hash 与 String 的主要区别?
1、把所有相关的值聚集到一个 key 中,节省内存空间
2、只使用一个 key,减少 key 冲突
3、当需要批量获取值的时候,只需要使用一个命令,减少内存/IO/CPU 的消耗
Hash 不适合的场景:
1、Field 不能单独设置过期时间
2、没有 bit 操作
3、需要考虑数据量分布的问题(value 值非常大的时候,无法分布到多个节点)
操作命令
存储(实现)原理
Redis 的 Hash 本身也是一个 KV 的结构,类似于 Java 中的 HashMap。
外层的哈希(Redis KV 的实现)只用到了 hashtable。当存储 hash 数据类型时,
我们把它叫做内层的哈希。内层的哈希底层可以使用两种数据结构实现:
ziplist:OBJ_ENCODING_ZIPLIST(压缩列表)
hashtable:OBJ_ENCODING_HT(哈希表)
如下图所示:
问题一、那么在什么时候会用到ziplist,什么时候用到hashtable呢?
在redis.conf我们可以看到:
在源码中:
if (hashTypeLength(o) >server.hash_max_ziplist_entries)    hashTypeConvert(o, OBJ_ENCODING_HT);for (i = start; i <= end; i++) {    if (sdsEncodedObject(argv[i]) &&    sdslen(argv[i]->ptr) >      server.hash_max_ziplist_value){    hashTypeConvert(o, OBJ_ENCODING_HT);    break;}}
从而我们可以得知,当 hash 对象同时满足以下两个条件的时候,使用 ziplist 编码:
1)所有的键值对的键和值的字符串长度都小于等于 64byte(一个英文字母
一个字节);
2)哈希对象保存的键值对数量小于 512 个。
一个哈希对象超过配置的阈值(键和值的长度有>64byte,键值对个数>512 个)时,
会转换成哈希表(hashtable)。
问题二、什么是ziplist压缩列表
ziplist 压缩列表ziplist 压缩列表是什么?
ziplist 是一个经过特殊编码的双向链表,它不存储指向上一个链表节点和指向下一
个链表节点的指针,而是存储上一个节点长度和当前节点长度,通过牺牲部分读写性能,
来换取高效的内存空间利用率,是一种时间换空间的思想。只用在字段个数少,字段值
小的场景里面。ziplist 的内部结构?
总体架构如下图所示:
entry对象定义的源码如下:
typedef struct zlentry {unsigned int prevrawlensize; unsigned int prevrawlen; unsigned int lensize; unsigned int len; unsigned int headersize; unsigned char encoding; unsigned char *p; } zlentry;
问题三、什么是hashtable( dict)?hashtable是什么?
在 Redis 中,hashtable 被称为字典(dictionary),它是一个数组+链表的结构。
前面我们知道了,Redis 的 KV 结构是通过一个 dictEntry 来实现的。
Redis 又对 dictEntry 进行了多层的封装。
dictEntry 定义如下:
typedef struct dictEntry {  void *key;  union {    void *val; uint64_t u64;    int64_t s64; double d;  } v;  struct dictEntry *next; } dictEntry
dictEntry 放到了 dictht(hashtable 里面):
typedef struct dictht {  dictEntry **table;  unsigned long size;  unsigned long sizemask;  unsigned long used; } dictht;
dictht 放到了 dict 里面:
typedef struct dict {  dictType *type;  void *privdata;  dictht ht[2];  long rehashidx;  unsigned long iterators; } dict;
从最底层到最高层 dictEntry——dictht——dict——OBJ_ENCODING_HT
哈希的总体存储结构如下:
注意:dictht 后面是 NULL 说明第二个 ht 还没用到。dictEntry*后面是 NULL 说明没有 hash 到这个地址。dictEntry 后面是NULL 说明没有发生哈希冲突。
问题三、为什么要定义两个hash表呢?ht[2]?
redis 的 hash 默认使用的是 ht[0],ht[1]不会初始化和分配空间。
哈希表 dictht 是用链地址法来解决碰撞问题的。在这种情况下,哈希表的性能取决于它的大小(size 属性)和它所保存的节点的数量(used 属性)之间的比率:
1. 比率在 1:1 时(一个哈希表 ht 只存储一个节点 entry),哈希表的性能最好;
2. 如果节点数量比哈希表的大小要大很多的话(这个比例用 ratio 表示,5 表示平均一个 ht 存储 5 个 entry),那么哈希表就会退化成多个链表,哈希表本身的性能优势就不再存在。
在这种情况下需要扩容。Redis 里面的这种操作叫做 rehash。
1、为字符 ht[1]哈希表分配空间,这个哈希表的空间大小取决于要执行的操作,以及 ht[0]当前包含的键值对的数量。
扩展:ht[1]的大小为第一个大于等于 ht[0].used*2。
2、将所有的 ht[0]上的节点 rehash 到 ht[1]上,重新计算 hash 值和索引,然后放入指定的位置。
3、当 ht[0]全部迁移到了 ht[1]之后,释放 ht[0]的空间,将 ht[1]设置为 ht[0]表,并创建新的 ht[1],为下次 rehash 做准备。
问题四、什么时候触发扩容?
关键因素:负载因子
定义源码如下:
static int dict_can_resize = 1;static unsigned int dict_force_resize_ratio = 5;
ratio = used / size,已使用节点与字典大小的比例。
dict_can_resize 为 1 并且 dict_force_resize_ratio 已使用节点数和字典大小之间的比率超过 1:5,触发扩容。
扩容判断 _dictExpandIfNeeded源码如下:
if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)){    return dictExpand(d, d->ht[0].used*2);}return DICT_OK;
扩容方法 dictExpand源码如下:
static int dictExpand(dict *ht, unsigned long size) {dict n; unsigned long realsize = _dictNextPower(size), i;if (ht->used > size) return DICT_ERR;_dictInit(&n, ht->type, ht->privdata);n.size = realsize;n.sizemask = realsize-1;n.table = calloc(realsize,sizeof(dictEntry*));n.used = ht->used;for (i = 0; i < ht->size && ht->used > 0; i++) {dictEntry *he, *nextHe;if (ht->table[i] == NULL) continue;he = ht->table[i];while(he) {unsigned int h;nextHe = he->next;h = dictHashKey(ht, he->key) & n.sizemask;he->next = n.table[h];n.table[h] = he;ht->used--;he = nextHe;}}assert(ht->used == 0);free(ht->table);*ht = n;return DICT_OK;}
缩容源码如下:
int htNeedsResize(dict *dict) {  long long size, used;  size = dictSlots(dict);  used = dictSize(dict);  return (size > DICT_HT_INITIAL_SIZE &&(used*100/size < HASHTABLE_MIN_FILL));}
应用场景
String
String 可以做的事情,Hash 都可以做。
存储对象类型的数据
比如对象或者一张表的数据,比 String 节省了更多 key 的空间,也更加便于集中管理。
购物车
key:用户 id;
field:商品 id;
value:商品数量。
+1:hincr。
-1:hdecr。
删除:hdel。
全选:hgetall。
商品数:hlen。
今天我们从底层源码剖析了基本数据类型Hash,接下来我们将会对剩下的几个常用的基本类型的深入探讨,敬请期待。

     扫码关注最新动态,更有价值数万元的精品课程免费送哦!

关注ToBeTopJavaer微信公众号,获取更多图文精彩内容


其他栏目