命令查看

  1. 127.0.0.1:6379> hset hash1 name zhangsan age 18 city xian
  2. (integer) 3
  3. 127.0.0.1:6379> hget hash1 name
  4. "zhangsan"
  5. 127.0.0.1:6379> hget hash1 age
  6. "18"
  7. 127.0.0.1:6379> hget hash1 city
  8. "xian"
  9. 127.0.0.1:6379> object encoding hash1
  10. "ziplist"
  11. 127.0.0.1:6379> hset hash3 longkey loooooooooooooooooooooooooooooooooooooooooooooooooooooooooooogkey
  12. (integer) 1
  13. 127.0.0.1:6379> object encoding hash3
  14. "hashtable"

我们可以看到hash底层有两种数据结构实现， ziplist 和 hashta``ble 。当hash对象可以同时满足一下两个条件时，哈希对象使用ziplist编码。

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  • 哈希对象保存的键值对数量小于512个

ziplist 和上一篇List数据结构分析里的ziplist一样，这篇就主要说哈希结构。

hashtable存储的结构

哈希表的制作方法一般有两种，一种是：开放寻址法，一种是拉链法。redis的哈希表的制作使用的是拉链法。

整体结构如下图：
Hash数据结构分析 - 图1
上图是一个没有处于rehash状态下的字典dict，整个dict中有两个哈希表dictht，其中一个哈希表存储数据，另一个哈希表为空。

dict 字典

字典作为一种常用的数据结构，也被内置在很多编程语言中，比如 Java 的 HashMap 和 Python 的 dict. 然而 C 语言又没有（知道为什么大家更喜欢写 Java,Python 等高级语言了吧）.
所以 Redis 自己实现了一个字典，其定义如下：

https://github.com/redis/redis/blob/unstable/src/dict.h

  1. typedf struct dict{
  2.     dictType *type;//类型特定函数，包括一些自定义函数，这些函数使得key和
  3.                    //value能够存储
  4.     void *private;//私有数据
  5.     dictht ht[2];//两张hash表 
  6.     int rehashidx;//rehash索引，字典没有进行rehash时，此值为-1
  7.     unsigned long iterators; //正在迭代的迭代器数量
  8. }dict;
  • type和private这两个属性是为了实现字典多态而设置的，当字典中存放着不同类型的值，对应的一些复制，比较函数也不一样，这两个属性配合起来可以实现多态的方法调用；
  • ht[2]，两个hash表
  • rehashidx，这是一个辅助变量，用于记录rehash过程的进度，以及是否正在进行rehash等信息，当此值为-1时，表示该dict此时没有rehash过程

  • iterators，记录此时dict有几个迭代器正在进行遍历过程

    dictht 哈希表结构

    由上面可以看出，dict本质上是对哈希表dictht的一个简单封装，dictht的定义如下所示：

    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. */
    3. typedef struct dictht {
    4.   dictEntry **table;
    5.   unsigned long size;
    6.   unsigned long sizemask;
    7.   unsigned long used;
    8. } dictht;

    **table是一个dictEntry类型的数组，用于真正存储数据；size表示**table这个数组的大小；sizemask用于计算索引位置，且总是等于size-1；used表示dictht中已有的节点数量。

    dictEntry

    由上面可以看到，真正存储数据的结构是dictEntry数组，其结构定义如下：

    1. typedf struct dictEntry{
    2.   void *key;//键
    3.   union{
    4.       void val;
    5.       unit64_t u64;
    6.       int64_t s64;
    7.       double d;
    8.   }v;//值
    9.   struct dictEntry *next；//指向下一个节点的指针
    10. }dictEntry;

    扩容与缩容

    当哈希表中元素数量逐渐增加时，此时产生hash冲突的概率逐渐增大，且由于dict也是采用拉链法解决hash冲突的，随着hash冲突概率上升，链表会越来越长，这就会导致查找效率下降。相反，当元素不断减少时，元素占用dict的空间就越少，出于对内存的极致利用，此时就需要进行缩容操作。
    既然说到扩容和缩容，熟悉Java集合的小伙伴是不是想到了什么。不错，那就是负载因子。负载因子一般用于描述集合当前被填充的程度。在Redis的字典dict中，负责因子=哈希表中已保存节点数量/哈希表的大小，即：

    1. load factor = ht[0].used / ht[0].size

    Redis中，三条关于扩容和缩容的规则：

  • 没有执行BGSAVE和BGREWRITEAOF指令的情况下，哈希表的负载因子大于等于1时进行扩容；

  • 正在执行BGSAVE和BGREWRITEAOF指令的情况下，哈希表的负载因大于等于5时进行扩容；
  • 负载因子小于0.1时，Redis自动开始对哈希表进行收缩操作；

其中，扩容和缩容的数量大小也有一定的规则：

  • 扩容：扩容后的dictEntry数组数量为第一个大于等于ht[0].used * 2的2^n；

  • 缩容：缩容后的dictEntry数组数量为第一个大于等于ht[0].used的2^n；

    扩容动图

    Hash数据结构分析 - 图2

    缩容动图

    Hash数据结构分析 - 图3

    渐进式rehash

    与Java中的HashMap类似，当Redis中的dict进行扩容或者缩容，会发生reHash过程。Java中HashMap的rehash过程如下：新建一个哈希表，一次性将当前所有节点进行rehash然后复制到新哈希表相应的位置上，之后释放掉原有的hash表，而持有新的表，这个过程是一个时间复杂度为O(n)的操作。而对于单线程的Redis而言很难承受这么高时间复杂度的操作，因而其rehash的过程有所不同，使用的是一种称之为渐进式rehash的方式，一点一点地进行搬迁。其过程如下：

  • 假设当前数据在dictht[0]中，那么首先为dictht[1]分配足够的空间，如果是扩容，则dictht[1]大小就按照扩容规则设置；如果是缩减，则dictht[1]大小就按照缩减规则进行设置；

  • 在字典dict中维护一个变量，rehashidx=0，表示rehash正式开始；
  • rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将dictht[0]哈希表在rehashidx索引上的所有键值对rehash到dictht[1]，当一次rehash工作完成之后，程序将rehashidx属性的值+1。同时在serverCron中调用rehash相关函数，在1ms的时间内，进行rehash处理，每次仅处理少量的转移任务(100个元素)；
  • 随着字典操作的不断执行，最终在某个时间点上，dictht[0]的所有键值对都会被rehash至dictht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成；

上述就是Redis中dict的渐进式rehash过程，但在这个过程会存在两个明显问题。第一，第三步说了，每次对字典执行增删改查时才会触发rehash过程，万一某一时间段并没有任何请求命令呢？此时应该怎么办？第二，在维护两个dictht的时候，此时哈希表如何正常对外提供服务？

Redis的设计人员在设计时就已经考虑到了这两个问题。对于第一个问题，Redis在有一个定时器，会定时去判断rehash是否完成，如果没有完成，则继续进行rehash。定时函数如下所示：

  1. // 服务器定时任务
  2. void databaseCron() {
  3.          ...
  4.          if (server.activerehashing) {
  5.             for (j = 0; j < dbs_per_call; j++) {
  6.                  int work_done = incrementallyRehash(rehash_db);//rehash方法
  7.                  if (work_done) {
  8.                        /* If the function did some work, stop here, we'll do
  9.                         * more at the next cron loop. */
  10.                        break;
  11.                   } else {
  12.                  /* If this db didn't need rehash, we'll try the next one. */
  13.                       rehash_db++;
  14.                       rehash_db %= server.dbnum;
  15.                   }
  16.              }
  17.         }
  18. }

对于第二个问题，对于添加操作，会将新的数据直接添加到dictht[1]上面，这样就可以保证dictht[0]上的数量只减少不增加。而对于删除、更改、查询操作，会直接在dictht[0]上进行，尤其是这三个操作，都会涉及到查询，当在dictht[0]上查询不到时，会接着去dictht[1]上查找，如果再找不到，则表明不存在该K-V值。

渐进式rehash

  • 优点：采用了分而治之的思想，将 rehash 操作分散到每一个对该哈希表的操作上以及定时函数上，避免了集中式rehash 带来的性能压力；

  • 缺点：在 rehash 的时间内，需要保存两个 hash 表，对内存的占用稍大，而且如果在 redis 服务器本来内存满了的时候，突然进行 rehash 会造成大量的 key 被抛弃；

    为什么扩容的时候要考虑BIGSAVE的影响，而缩容时不需要？

  • BIGSAVE时，dict要是进行扩容，则此时就需要为dictht[1]分配内存，若是dictht[0]的数据量很大时，就会占用更多系统内存，造成内存页过多分离，所以为了避免系统耗费更多的开销去回收内存，此时最好不要进行扩容；

  • 缩容时，结合缩容的条件，此时负载因子<0.1，说明此时`dict`中数据很少，就算为`dictht[1]`分配内存，也消耗不了多少资源；

    总结

    Hash数据结构分析 - 图4