25 | 数据分布方式之哈希与一致性哈希：“掐指一算”与“掐指两算”的事

带有限负载的一致性hash，在查询数据时，怎么确定数据存储在哪个节点上呢？

本节课是分布式相关的知识点中最熟悉的一节，但是之前都是零碎的信息，没有把这四种数据分布方式进行细致的对比，这次老师的对比 让我豁然开朗。下面总结一下我的思考： 提到hash的时候，学后端的小伙伴一定会回想到数据结构课程中的hash，会想到Java的经典面试题：HashMap的原理，其实我想说的是 分布式的数据分布其实就是从基本的hash演化来的。 数据的最基本的存储组织方式：数组，所有的数据按照地址顺序放在一个列表 数组通过游标查询快，修改数据快，删除数据和插入数据需要移动数据就慢了，分配内存需要连续的内存空间，内存使用的效率低 于是链表诞生--->>> 链表修改数据快，删除数据，插入数据快，分配的内存空间不需要连续，内存使用的效率高，但是链表的查询需要遍历很慢 于是hash表诞生--->>> hash散列表存储键值对数据，key通过hash函数计算出一个hash值，这个hash值再和数据的地址做一个映射就找到数据了，hash解决 了链表的查询慢的问题；但是hash又引入了新的问题：hash函数性能损耗，hash散列不均衡，hash冲突等 这里再想想Java中的HashMap怎么优化这个问题--->>> hash函数性能损耗：通过取模（CPU的原生指令）提高效率 hash散列冲突：数组+链表 、数组+红黑树的方式解决冲突 从上面对比我想到，需求的本质就像想做数据映射，通过key和value做映射，value可能是内存地址，可能是hash值， 可能一次映射不够就做两次。 然后想想数据库的索引也就是为了做数据映射，更快更高效的对数据进行增删该查。 在分布式的场景下，我们可以迁移这些思想， 一个数如何据映射到具体节点上，这和一个值映射到具体哪个内存地址有共享。 最后--->>> 老师讲到的hash，一致性hash，有限负载的一致性hash，虚列节点的一致性hash以及它们各种特性比较。 老师总结的非常好，自己对对于这个块知识不是很清楚的地方这次也明白了： 均衡性：也就hash的分散性，老师讲的从两个维度理解。第一：每个节点的数据量要均衡分配，第二：用户访问的请求要均衡的落在每个节点 ，第二个维度可以理解为系统的热点数据访问怎么处理，不能让热点数据成为系统访问的压力，要分散它。 节点异构：我们组的系统刚好做过通过虚拟节点的一致性hash方式实现数据分布，当时一直理解的是虚拟节点再多了一次映射就是为了数据分散 更均衡，老师讲的是因为节点以后的原因，然后通过虚拟节点来实现数据分散，这个本质的今天才get到。 我有2个疑问： 1.如果相同的数据被映射到了不同的节点，空间不是就浪费了？ 2.做数据分布映射的时候我们是不是需要考虑有key是单调递增的场景呢？ 最后说说老师的课后问题：寻找其它数据分布的方式 散列：老师讲的hash三个都是属于这一类 范围：按照id划分，按照地区，国家，民族等自定义的维度 循环：按照一个步长循环 组合：以上三种方式按照特定场景的组合 个人认为：数据分布，数据分片，索引，hash，负载均衡实现的方式中有共性 疑问：如果我们能把数据按照页的级别分布在不同的节点上，我们是不是可以通过一个可棵 B+树 来组织分布式的数据？？？

范围分区：通过确定分区键是否在一定范围内来选择分区。比如按照年龄范围分区。 列表分区：为分区分配值列表。比如按照所属国家对用户分区。 循环分区：对于n个分区，将插入顺序中的第i个元组分配给i%n分区 散列函数：将数据的某些字段通过散列函数计算得到分区号。比如Redis。 组合分区：允许上述划分方案的某些组合 参见： https://en.wikipedia.org/wiki/Partition_(database) https://dev.mysql.com/doc/refman/8.0/en/partitioning-types.html

老师，redis用的不是带有虚拟节点的一致性hash算法么？

推荐一个实现 https://github.com/golang/groupcache/blob/master/consistenthash/consistenthash.go

Consistent Hash 在 Dynamo: Amazon’s Highly Available Key-value Store 一文里介绍的比较详细：最初的版本是一个节点（机器）分配一个 token；为了解决可能出现的负载不均衡, 出现了几个变种： 1. T random tokens per node and partition by token value 每个节点分配多个 token (引入 virtual node 虚拟节点概念)； Cassandra 参考的 Dynamo，用的是策略一 2. T random tokens per node and equal sized partitions 在每个节点分配多个 token 的同时，将 hashing ring 分割成同等大小的分区 3. Q/S tokens per node, equal-sized partitions: 其中 Q 是分区数，S 是节点数 Redis Cluster 中将 key space 分成 16384 个 slot，之后每个节点分配一部分 slot；和上面的策略 2, 3 比较接近，都是二阶段映射（key 到分区，分区到节点）

很棒，哈希算法、一致性哈希算法、带虚拟节点的哈希算法之前学习过，带负载的哈希算法第一次接触，老师的对比图做的很好。 哈希算法的核心是哈希函数的选择，而且使用哈希算法必然会出现哈希碰撞的问题，解决哈希碰撞问题也有一下非常经典的方式。老师讲的带负载的哈希算法如果负载值是1就是一种解决哈希冲突的方式。 还有什么分区的方式呢？其他同学的评论也提到了一些，散列+范围（数值大小、地理区域、民族、国家）+自定义类别+组合，其他我也不知道，不过哈希算法确实非常经典。 想一想全球有几十亿人，每个人代表一条数据的话，我们被存储在地球上，通过性别、年龄、肤色、国籍、工种、文化程度、社会角色、生死、健康或疾病等等各种各样的维度划分。不过最快的获取一个人的信息的方式就是她的身份证、护照、驾照等方式，唯一标识感觉就是一个主键。如果要找具体的人，就需要时间+空间这两个维度来去定位了，这是否也是一种分区的方式呢？

哈希这块一直学过可是原理不清楚，为此还去学习算法了解其本源；可是像老师这样清楚的梳理还是没有明白。知其然知其所以然：明白清楚了在数据系统中的使用就更加从容了。

之前这些方法也都知道，但就是说不清楚，有些也不知道叫什么名。这回终于能说明白了，感觉以后面试又可以吹一波了。至于今天的思考题…能力有限，坐等课代表科普

按照范围进行分片，典型的代表hbase。 因为它需要根据rowkey范围锁定数据存储的位置，相邻的rowkey数据会按照顺序存储在磁盘，因此在执行rowkey的单位查询时，性能非常快。为了避免单位的热点不均衡，伴随着也有很多差分和合并的机制。