Redis中哈希分布不均匀该怎么办

双子孤狼 2021-01-20 21:46:17
redis 哈希 分布 不均 不均匀


前言

Redis 是一个键值对数据库,其键是通过哈希进行存储的。整个 Redis 可以认为是一个外层哈希,之所以称为外层哈希,是因为 Redis 内部也提供了一种哈希类型,这个可以称之为内部哈希。当我们采用哈希对象进行数据存储时,对整个 Redis 而言,就经过了两层哈希存储。

哈希对象

哈希对象本身也是一个 key-value 存储结构,底层的存储结构也可以分为两种:ziplist(压缩列表) 和 hashtable(哈希表)。这两种存储结构也是通过编码来进行区分:

编码属性 描述 object encoding命令返回值
OBJ_ENCODING_ZIPLIST 使用压缩列表实现哈希对象 ziplist
OBJ_ENCODING_HT 使用字典实现哈希对象 hashtable

hashtable

Redis 中的 key-value 是通过 dictEntry 对象进行包装的,而哈希表就是将 dictEntry 对象又进行了再一次的包装得到的,这就是哈希表对象 dictht

typedef struct dictht {
dictEntry **table;//哈希表数组
unsigned long size;//哈希表大小
unsigned long sizemask;//掩码大小,用于计算索引值,总是等于size-1
unsigned long used;//哈希表中的已有节点数
} dictht;

注意:上面结构定义中的 table 是一个数组,其每个元素都是一个 dictEntry 对象。

字典

字典,又称为符号表(symbol table),关联数组(associative array)或者映射(map),字典的内部嵌套了哈希表 dictht 对象,下面就是一个字典 ht 的定义:

typedef struct dict {
dictType *type;//字典类型的一些特定函数
void *privdata;//私有数据,type中的特定函数可能需要用到
dictht ht[2];//哈希表(注意这里有2个哈希表)
long rehashidx; //rehash索引,不在rehash时,值为-1
unsigned long iterators; //正在使用的迭代器数量
} dict;

其中 dictType 内部定义了一些常用函数,其数据结构定义如下:

typedef struct dictType {
uint64_t (*hashFunction)(const void *key);//计算哈希值函数
void *(*keyDup)(void *privdata, const void *key);//复制键函数
void *(*valDup)(void *privdata, const void *obj);//复制值函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);//对比键函数
void (*keyDestructor)(void *privdata, void *key);//销毁键函数
void (*valDestructor)(void *privdata, void *obj);//销毁值函数
} dictType;

当我们创建一个哈希对象时,可以得到如下简图(部分属性被省略):

rehash 操作

dict 中定义了一个数组 ht[2]ht[2] 中定义了两个哈希表:ht[0]ht[1]。而 Redis 在默认情况下只会使用 ht[0],并不会使用 ht[1],也不会为 ht[1] 初始化分配空间。

当设置一个哈希对象时,具体会落到哈希数组(上图中的 dictEntry[3])中的哪个下标,是通过计算哈希值来确定的。如果发生哈希碰撞(计算得到的哈希值一致),那么同一个下标就会有多个 dictEntry,从而形成一个链表(上图中最右边指向 NULL 的位置),不过需要注意的是最后插入元素的总是落在链表的最前面(即发生哈希冲突时,总是将节点往链表的头部放)。

当读取数据的时候遇到一个节点有多个元素,就需要遍历链表,故链表越长,性能越差。为了保证哈希表的性能,需要在满足以下两个条件中的一个时,对哈希表进行 rehash(重新散列)操作:

  • 负载因子大于等于 1dict_can_resize1 时。
  • 负载因子大于等于安全阈值(dict_force_resize_ratio=5)时。

PS:负载因子 = 哈希表已使用节点数 / 哈希表大小(即:h[0].used/h[0].size)。

rehash 步骤

扩展哈希和收缩哈希都是通过执行 rehash 来完成,这其中就涉及到了空间的分配和释放,主要经过以下五步:

  1. 为字典 dictht[1] 哈希表分配空间,其大小取决于当前哈希表已保存节点数(即:ht[0].used):

    • 如果是扩展操作则 ht[1] 的大小为 2 的 n次方中第一个大于等于ht[0].used * 2属性的值(比如used=3,此时ht[0].used * 2=6,故 23次方为8就是第一个大于used * 2 的值(2 的 2 次方 < 6 且 2 的 3 次方 > 6))。
    • 如果是收缩操作则 ht[1] 大小为 2 的 n 次方中第一个大于等于 ht[0].used 的值。
  2. 将字典中的属性 rehashix 的值设置为 0,表示正在执行 rehash 操作。

  3. ht[0] 中所有的键值对依次重新计算哈希值,并放到 ht[1] 数组对应位置,每完成一个键值对的 rehash之后 rehashix 的值需要自增 1

  4. ht[0] 中所有的键值对都迁移到 ht[1] 之后,释放 ht[0] ,并将 ht[1] 修改为 ht[0],然后再创建一个新的 ht[1] 数组,为下一次 rehash 做准备。

  5. 将字典中的属性 rehashix 设置为 -1,表示此次 rehash 操作结束,等待下一次 rehash

渐进式 rehash

Redis 中的这种重新哈希的操作因为不是一次性全部 rehash,而是分多次来慢慢的将 ht[0] 中的键值对 rehashht[1],故而这种操作也称之为渐进式 rehash。渐进式 rehash 可以避免集中式 rehash 带来的庞大计算量,是一种分而治之的思想。

在渐进式 rehash 过程中,因为还可能会有新的键值对存进来,此时** Redis 的做法是新添加的键值对统一放入 ht[1] 中,这样就确保了 ht[0] 键值对的数量只会减少**。

当正在执行 rehash操作时,如果服务器收到来自客户端的命令请求操作,则会先查询 ht[0],查找不到结果再到ht[1] 中查询

ziplist

关于 ziplist 的一些特性,之前的文章中有单独进行过分析,想要详细了解的,可以点击这里。但是需要注意的是哈希对象中的 ziplist 和列表对象中 ziplist 的有一点不同就是哈希对象是一个 key-value 形式,所以其 ziplist 中也表现为 key-valuekeyvalue 紧挨在一起:

ziplist 和 hashtable 的编码转换

当一个哈希对象可以满足以下两个条件中的任意一个,哈希对象会选择使用 ziplist 编码来进行存储:

  • 哈希对象中的所有键值对总长度(包括键和值)小于等于 64字节(这个阈值可以通过参数 hash-max-ziplist-value 来进行控制)。
  • 哈希对象中的键值对数量小于等于 512 个(这个阈值可以通过参数 hash-max-ziplist-entries 来进行控制)。

一旦不满足这两个条件中的任意一个,哈希对象就会选择使用 hashtable 编码进行存储。

哈希对象常用命令

  • hset key field value:设置单个 field(哈希对象的 key 值)。
  • hmset key field1 value1 field2 value2 :设置多个 field(哈希对象的 key 值)。
  • hsetnx key field value:将哈希表 key 中域 field 的值设置为 value,如果 field 已存在,则不执行任何操作。
  • hget key field:获取哈希表 key 中的域 field 对应的 value
  • hmget key field1 field2:获取哈希表 key 中的多个域 field 对应的 value
  • hdel key field1 field2:删除哈希表 key 中的一个或者多个 field
  • hlen key:返回哈希表key中域的数量。
  • hincrby key field increment:为哈希表 key 中的域 field 的值加上增量 incrementincrement 可以为负数,如果 field 不是数字则会报错。
  • hincrbyfloat key field increment:为哈希表 key 中的域 field 的值加上增量 incrementincrement 可以为负数,如果 field 不是 float 类型则会报错。
  • hkeys key:获取哈希表 key 中的所有域。
  • hvals key:获取哈希表中所有域的值。

了解了操作哈希对象的常用命令,我们就可以来验证下前面提到的哈希对象的类型和编码了,在测试之前为了防止其他 key 值的干扰,我们先执行 flushall 命令清空 Redis 数据库。

然后依次执行如下命令:

hset address country china
type address
object encoding address

得到如下效果:

可以看到当我们的哈希对象中只有一个键值对的时候,底层编码是 ziplist

现在我们将 hash-max-ziplist-entries 参数改成 2,然后重启 Redis,最后再输入如下命令进行测试:

hmset key field1 value1 field2 value2 field3 value3
object encoding key

输出之后得到如下结果:

可以看到,编码已经变成了 hashtable

总结

本文主要介绍了 Redis5 种常用数据类型中的哈希类型底层的存储结构 hashtable 的使用,以及当 hash 分布不均匀时候 Redis 是如何进行重新哈希的问题,最后了解了哈希对象的一些常用命令,并通过一些例子验证了本文的结论。

版权声明
本文为[双子孤狼]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/lonely-wolf/p/14305238.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云