redis数据结构之『字典』

介绍

dict 是 Redis 服务器中出现最为频繁的复合型数据结构

项目地址：https://github.com/lishq/redis-base-demo

数据结构

• hash结构使用dict
• redis所有的key-value组成一个全局dict
• 带过期时间的key也是一个dict
• zset存储value和score值映射关系使用dict
• set的结构底层实现也是dict，只不过所有的value都是NULL

  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;
  }

dict 内部结构

dict结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 的值被删除，新hashtable 取而代之。

struct dict {
    ...
    dictht ht[2];
}

类似Java的HashMap，数组+链表的形式。

渐进式rehash

大字典的扩容是遍历链表中所有旧元素，copy到新的数组下，O(n)的操作，所以redis执行渐进式搬迁。

• 当前dict的hset，hdel会触发搬迁操作

• redis定时任务中主动进行搬迁

hash函数

Redis 的字典默认的 hash 函数是 siphash。siphash 算法即使在输入 key 很小的情况下，也可以产生随机性特别好的输出，而且它的性能也非常突出

扩容条件

正常情况下，当 hash 表中元素的个数等于第一维数组的长度时，就会开始扩容，扩容的新数组是原数组大小的 2 倍。不过如果 Redis 正在做 bgsave，为了减少内存页的过多分离 (Copy On Write)，Redis 尽量不去扩容 (dict_can_resize)，但是如果 hash 表已经非常满了，元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio)，说明 hash 表已经过于拥挤了，这个时候就会强制扩容。

缩容条件

当 hash 表因为元素的逐渐删除变得越来越稀疏时，Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的 10%。缩容不会考虑 Redis 是否正在做 bgsave。