Redis Hash哈希（2）

存储类型

包含键值对的无序散列表。value只能是字符串，不能嵌套其他类型。

同样是存储字符串，Hash与String的主要区别？

1、把所有相关的值聚集到一个key中，节省内存空间

2、只使用一个key，减少key冲突

3、当需要批量获取值的时候，只需要使用一个命令，减少内存/IO/CPU的消耗

Hash不适合的场景：

1、Field不能单独设置过期时间

2、没有bit操作

3、需要考虑数据量分布的问题（value值非常大的时候，无法分布到多个节点）

存储（实现）原理

Redis的Hash本身也是一个KV的结构，类似于Java中的HashMap。

外层的哈希（RedisKV的实现）只用到了hashtable。当存储hash数据类型时，我们把它叫做内层的哈希。内层的哈希底层可以使用两种数据结构实现：

ziplist：OBJ_ENCODING_ZIPLIST（压缩列表）

hashtable：OBJ_ENCODING_HT（哈希表）

1127.0.0.1:6379> hset s1 f aa
2(integer) 1
3127.0.0.1:6379> object encoding s1
4"ziplist"
5
6127.0.0.1:6379> hset s2 a bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
7(integer) 0
8127.0.0.1:6379> object encoding s2
9"hashtable"

ziplist压缩列表

ziplist是一个经过特殊编码的双向链表，它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。

ziplist的内部结构

ziplist.c源码第16行的注释：

1typedef struct zlentry {
2    unsigned int prevrawlensize; /* 上一个链表节点占用长度*/
3    unsigned int prevrawlen;     /* 上一个链表节点的长度数值所需的字节数 */
4    unsigned int lensize;        /* 当前链表节点长度数值所需字节数 */
5    unsigned int len;            /* 当前链表节点占用的长度 */
6    unsigned int headersize;     /* 当前链表节点的头部大小（prevrawlensize + lensize），即非数据域大小 */
7    unsigned char encoding;      /* 编码方式*/
8    unsigned char *p;            /*压缩链表以字符串的形式保存，该指针指向当前节点起始位置 */
9} zlentry;
10
11编码encoding（ziplist.c源码第204行）
12	
13#define ZIP_STR_06B (0 << 6)
14#define ZIP_STR_14B (1 << 6)
15#define ZIP_STR_32B (2 << 6)

什么时候使用ziplist存储？

当hash对象同时满足以下两个条件的时候，使用ziplist编码：

1、所有的键值对的健和值的字符串长度都小于等于64byte（一个英文字母一个字节）

2、哈希对象保存的键值对数量小于512个。

1/*redis.conf配置*/
2hash-max-ziplist-value 64     //ziplist中最大能存放的值长度
3hash-max-ziplist-entries 512  //ziplist中最多能存放的entry节点数量

一个哈希对象超过配置的阈值（键和值的长度有>64byte，键值对个数>512个）时，会转换成哈希表（hashtable）。

hashtable（源码位置：dict.h ）

在Redis中，hashtable被称为字典（dictionary），它是一个数组+链表的结构。

前面我们知道了，Redis的KV结构是通过一个dictEntry来实现的。

Redis又对dictEntry进行了多层的封装。

1typedef struct dictEntry {
2    void *key;         /*Key关键字定义*/
3    union {
4        void *val;
5        uint64_t u64;
6        int64_t s64;
7        double d;
8    } v;
9    struct dictEntry *next;
10} dictEntry;

dictEntry放到了dictht（hashtable里面）

1/* This is our hash table structure. Every dictionary has two of this as we
2 * implement incremental rehashing, for the old to the new table. */
3typedef struct dictht {
4    dictEntry **table;     /*哈希表数组*/
5    unsigned long size;    /*哈希表数组*/
6    unsigned long sizemask;/*掩码大小，用于计算索引值。等于size-1*/
7    unsigned long used;    /*已有节点数*/
8} dictht;

ht放到了dict里面

1typedef struct dict {
2    dictType *type; /*字段类型*/
3    void *privdata; /*私有数据*/
4    dictht ht[2];   /*一个字段有两个哈希表*/
5    long rehashidx; /* rehash索引  */
6    unsigned long iterators; /* 当前正在使用的迭代器数量 */
7} dict;
8

从最底层到最高层dictEntry——dictht——dict——OBJ_ENCODING_HT

哈希的存储结构

为什么要定义两个哈希表呢？ht[2]

redis的hash默认使用的是ht[0]，ht[1]不会初始化和分配空间。

哈希表dictht是用链地址法来解决碰撞问题的。在这种情况下，哈希表的性能取决于它的大小（size属性）和它所保存的节点的数量（used属性）之间的比率：

比率在1:1时（一个哈希表ht只存储一个节点entry），哈希表的性能最好；
如果节点数量比哈希表的大小要大很多的话（这个比例用ratio表示，5表示平均一个ht存储5个entry），那么哈希表就会退化成多个链表，哈希表本身的性能优势就不再存在。

在这种情况下需要扩容。Redis里面的这种操作叫做rehash。

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做准备。

什么时候触发扩容？

负载因子（源码位置：dict.c）

1static int dict_can_resize = 1;
2static unsigned int dict_force_resize_ratio = 5;

ratio=used/size，已使用节点与字典大小的比例dict_can_resize为1并且

dict_force_resize_ratio已使用节点数和字典大小之间的比率超过1：5，触发扩容

扩容判断 _dictExpandIfNeeded（源码dict.c）

1/* Expand the hash table if needed */
2static int _dictExpandIfNeeded(dict *d)
3{
4    /* Incremental rehashing already in progress. Return. */
5    if (dictIsRehashing(d)) return DICT_OK;
6
7    /* If the hash table is empty expand it to the initial size. */
8    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
9
10    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
11     * table (global setting) or we should avoid it but the ratio between
12     * elements/buckets is over the "safe" threshold, we resize doubling
13     * the number of buckets. */
14    if (d->ht[0].used >= d->ht[0].size &&
15        (dict_can_resize ||
16         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
17    {
18        return dictExpand(d, d->ht[0].used*2);
19    }
20    return DICT_OK;
21}

扩容方法dictExpand（源码dict.c）

1/* Expand or create the hash table */
2int dictExpand(dict *d, unsigned long size)
3{
4    /* the size is invalid if it is smaller than the number of
5     * elements already inside the hash table */
6    if (dictIsRehashing(d) || d->ht[0].used > size)
7        return DICT_ERR;
8
9    dictht n; /* the new hash table */
10    unsigned long realsize = _dictNextPower(size);
11
12    /* Rehashing to the same table size is not useful. */
13    if (realsize == d->ht[0].size) return DICT_ERR;
14
15    /* Allocate the new hash table and initialize all pointers to NULL */
16    n.size = realsize;
17    n.sizemask = realsize-1;
18    n.table = zcalloc(realsize*sizeof(dictEntry*));
19    n.used = 0;
20
21    /* Is this the first initialization? If so it's not really a rehashing
22     * we just set the first hash table so that it can accept keys. */
23    if (d->ht[0].table == NULL) {
24        d->ht[0] = n;
25        return DICT_OK;
26    }
27
28    /* Prepare a second hash table for incremental rehashing */
29    d->ht[1] = n;
30    d->rehashidx = 0;
31    return DICT_OK;
32}
33

缩容：server.c

1int htNeedsResize(dict *dict) {
2    long long size, used;
3
4    size = dictSlots(dict);
5    used = dictSize(dict);
6    return (size > DICT_HT_INITIAL_SIZE &&
7            (used*100/size < HASHTABLE_MIN_FILL));
8}