细品Redis高性能数据结构之hash对象

背景

上一节讲Redis的高性能字符串结构SDS，今天我们来看一下redis的hash对象。

Hash对象

简介

• redis的hash对象有两种编码（底层实现）方式，字典编码和压缩列表编码。在使用字典编码的时候程序就是将hash表的key存为字典的键，hash的value作为字典的值，字典的键值都是用的是字符串类型。
• 在哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节和哈希对象保存的键值对数量小于 512 个使用的是ziplist，不能满足这个的使用的是hashtable（字典编码）

深度理解

ZipList（压缩列表）

1. redis 的压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空间
2. 源码

struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个
节点
int16 zllength; // 元素个数
T[] entries; // 元素内容列表，挨个挨个紧凑存储
int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}


/**
*entry对象源码
*/
struct entry {
int<var> prevlen; // 前一个 entry 的字节长度
int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}

1. 压缩列表是支持双向遍历，所以才会有zltail_offset这个字段的，可以进行快速定位到最后一个元素。然后倒序查找(O(1))
2. prevlen 表示的是前一个字段的长度，有人就有疑问了，为什么是前一个entry的长度，为什么不是自己的呢，其实他还有一个作用是在压缩列表倒叙遍历的时候，需要通过这个字段来快速定位到下一个元素的位置，由于他是一个连续的存储空间，已经知道当前元素的位置+这个空间地址就可以确定写一个entry的位置。为什么会这样呢？因为entry的大小是不一样的。如果是一样的话就可以根据下表进行行为（个人理解，有错误还请指出），且prevlen 是一个变长的整数，redis的常规操作，将不同长度使用不同的数据类型。节省内存
3. encoding的意思是元素的编码类型，有了这个字段就可以决定元素内容的设定，内存大小的分配。防止内存分配浪费的一种方式。具体内容查看下面

1、00xxxxxx 最大长度位 63 的短字符串，后面的 6 个位存储字符串的位数，剩余的字
节就是字符串的内容。
2、01xxxxxx xxxxxxxx 中等长度的字符串，后面 14 个位来表示字符串的长度，剩余的
字节就是字符串的内容。
3、10000000 aaaaaaaa bbbbbbbb cccccccc dddddddd 特大字符串，需要使用额外 4 个字节
来表示长度。第一个字节前缀是 10，剩余 6 位没有使用，统一置为零。后面跟着字符串内
容。不过这样的大字符串是没有机会使用的，压缩列表通常只是用来存储小数据的。
4、11000000 表示 int16，后跟两个字节表示整数。
5、11010000 表示 int32，后跟四个字节表示整数。
6、11100000 表示 int64，后跟八个字节表示整数。
7、11110000 表示 int24，后跟三个字节表示整数。
8、11111110 表示 int8，后跟一个字节表示整数。
9、11111111 表示 ziplist 的结束，也就是 zlend 的值 0xFF。
10、1111xxxx 表示极小整数，xxxx 的范围只能是 (0001~1101), 也就是 1~13，因为
0000、1110、1111 都被占用了。读取到的 value 需要将 xxxx 减 1，也就是整数 0~12 就是
最终的 value。

1. 之前有讲到hash对像选用压缩列表的两个前提条件，其中之一是键值的大小都小于64，具体为什么小于64和简=键值对小于512就不具体说了，可以结合一下SDS中的扩容方式思考一下，压缩列表没有冗余空间，在进行扩容的时候会出现频繁扩容，再加上占用空间大了后进行copy数据就很浪费性能了。所以当数据量大了后，就选择了另一种数据结构那就是hashtable（字典）

HashTable（字典）

简介

• redis 的hashtable和java中的hashMap实现方式是类似的，都是通过数组和链表实现的。也就是key-value形式。当然它解决hash冲突的方式也是使用链地址法（解决hash冲突的几种方法可以想一下），当不同的key创建出了相同的hash值时将vlue就放入链表上，如下图。
• 在细节方面和java中的hashMap差别还是很大的。列如扩容的过程，key值得hash算法等等。接下来我们根据源码细细的品一品。

• 官方给的解释：字典（dictionary）， 又名映射（map）或关联数组（associative array）， 是一种抽象数据结构， 由一集键值对（key-value pairs）组成， 各个键值对的键各不相同， 程序可以添加新的键值对到字典中， 或者基于键进行查找、更新或删除等操作

其字典的底层结构是使用的是redis 中dict。不仅是hash对象底层使用了dict，而且在redis全局也是使用的是key-vlue结构，也就是字典的形式，还有Zset的数据结构底层也是基于redis 中的dict结构。我们来看一下其源码：

// resdis 全局使用的字典结构
struct RedisDb {
dict* dict; // all keys key=>value
dict* expires; // all expired keys key=>long(timestamp)
...}

// 有序集合的底层数据结构
struct zset {
dict *dict; // all values value=>score
zskiplist *zsl;
}

2. dict结构深度解析

• 源码：

/*
 * 字典
 *
 * 每个字典使用两个哈希表，用于实现渐进式 rehash
 */
typedef struct dict {

    // 特定于类型的处理函数
    dictType *type;

    // 类型处理函数的私有数据
    void *privdata;

    // 哈希表（2 个）
    dictht ht[2];

    // 记录 rehash 进度的标志，值为 -1 表示 rehash 未进行
    int rehashidx;

    // 当前正在运作的安全迭代器数量
    int iterators;

} dict;

• 可以类的成员变量中看到有两个hashtable，通常情况下是一个有值一个没有值。在压缩列表中我们遇到的问题是在扩容方面存在性能问题，这两个hashtable就是来解决扩容问题的。在扩容和缩容时进行渐进式搬迁，当搬迁结束的时候将旧的hashtable进行删除，新的hashtable 取而代之。
• 那我们来细细的研究一下hashtable，（Java中的hashtable是Java中hashMap的线程安全版本）。在这里的hashtable和java中的hashmap是类似的，解决hash冲突的方式通过分桶的方式。一维数组，二维链表。但是在扩容还是有一些区别的。

struct dictEntry {
void* key;
void* val;
dictEntry* next; // 链接下一个 entry
}
struct dictht {
dictEntry** table; // 二维
long size; // 第一维数组的长度
long used; // hash 表中的元素个数
...
}

• 来看一下redis中hash是如何进行的 1.大字典的扩容是非常耗时间的，需要重新申请新的数组，然后将旧的字典所有的链表中的元素重新挂接到新的数组下面，这个过程时间复杂度为O（n），作为单线程的redis怎么会把时间浪费在这里呢，。于是他就采用了渐进式处理的方式（说到渐进式是否能想到他渐进式批量根据key查询呢scan 和 keys）， rehash的过程点击这里。其思想也就是我们上面所说的小步执行。
• 联系一下Set结构也是通过字典实现的，只不是所有的value都是NULL，有没有想到什么？Java中的hashSet是不是也和这个类似呢？。

总结

1. hash对象有两种底层实现方式，hashtable（字典） 和 ziplist（压缩链表）
2. 压缩链表由于是连续空间在刚开始数据量小的时候性能是显著的，但是在数据量大的时候就会出现扩容慢的问题
3. 字典通过双hahstable的方式，再加上渐进式hash的方式解决了压缩列表的扩容的问题
4. redis 高性能数据结构我们可以看到他在很对细节的把握很多，如不同的数字大小选用不同的字段类型，同一个对象根据大小选择不同的存储类型。（节省内存）