22 | 哈希算法（下）：哈希算法在分布式系统中有哪些应用？

精选留言(102)

• 

  ban

  一致性算法讲的有的有点抽象，不够详细。我网上找到一个漫画图解，各位可以参考一下：https://www.sohu.com/a/158141377_479559

  2018-11-09

   7

   217
• 

  null

  一致性哈希算法，举个栗子：
  我们钟表有 60 分钟，从 0 开始到 59，共 60 个点。
  现在我们将机器往这 60 个点分配，规则如下：
  hash(ip) % 60。
  
  假设有 3 台机器 A，B 和 C，分别被分配到了 14，37 和 46 这三个点上。
  
  图片的分配规则类似：
  hash(image_id) % 60。
  现有 3 张图片 x， y， z，分别被分配到 5，30，50 这三个点。
  
  很明示，图片都没被分配到机器的节点上，怎么办呢?在钟表上顺时钟往前寻找，第一台遇到的机器，就是它的归属。
  
  --- 我是分割线 ---
  
  现在很不凑巧，A B C 三台机器分别分配到 5，10，15 这三个点。这样对 A 是很不公平的吖，要负责存储绝大多数的图片，那这怎么办呢?我们社会主义核心价值观基本内容：和谐、平等、公正。为建设和谐社会努力奋斗！！
  
  为了避免不必要的争端，我们引入“虚拟节点”，每台机器都可以拔一根汗毛，变成若干台，把虚拟节点分散到 60 个点上，归属“虚拟节点”的图片，均保存到它的真身。这样就能解决分配不均匀的问题。
  
  ------
  
  应用时，将 60 替换下即可，如替换为 2的 32 次方。

  2018-11-09

  

   113
• 

  Geek_fbe6fe

  跟着作者学习整个数据结构和算法，感觉如醍醐灌顶，好像整个世界被重新打开了，最近也想学习go所以用go实现了到目前为止的所有算法和数据结构，用于自己学习和理解希望对大家有帮助
  https://github.com/xiangdong1987/studyAlgorithm
  对于一致性算法：我理解是先从整体上将hash 分好区间m 在通过自己维护一套在K台机器上m区间的分布来实现不需要rehash 的扩容方式

  2018-11-09

  

   31
• 

  Hesher

  一致性哈希算法没看懂，只能说看完文章知道了有这么个概念可以解决扩容rehash问题

  作者回复: 主要是展开讲内容会很多 网上关于一致性哈希算法的文章很多 你可以看下我给的那个链接。这个算法的核心思想非常简单，网上讲的都很复杂 只是为了实现起来优美。

  2018-11-09

  

   22
• 

  姜威

  总结：哈希算法在分布式系统中的应用
  1.负载均衡
  1.1.需求
  如何实现一个会话粘滞（session sticky）的负载均衡算法？也就是说，在一次会话中的所有请求都路由到同一个服务器上。
  1.2.解决方案
  通过哈希算法对客户端IP或会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，就可以把同一个IP过来的请求都路由到同一个后端服务器上。
  2.数据分片
  2.1.如何统计“搜索关键词”出现的次数？
  ①需求描述
  假如我们有1T的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？
  ②问题分析
  这个问题有两个难点，第一个是搜索的日子很大，没办法放到一台机器的内存中。第二个是只用一台机器来处理这么巨大的数据，处理时间会很长。
  ③解决方案
  先对数据进行分片，然后采用多台（比如n台）机器进行处理。具体做法：从搜索记录的日志文件中依次读取每个关键词，并通过哈希函数计算该关键词的哈希值，然后跟机器的台数n取模，最终得到值就是该关键词应该被分到的机器编号，这样相同的关键词一定会被分配到同一台机器上，数据分配完成后，由多台机器并行进行统计，最后合并起来就是最终结果。
  实际上，这里的处理过程也是 MapReduce 的基本设计思想。
  2.2.如何快速判断图片是否存在图库中？
  ①需求描述
  假设现在我们的图库中有1亿张图片，如何快速判断图片是否在图库中？基本方式是给每个图片去唯一表示（或者信息摘要），然后构建散列表。
  ②问题分析
  很显然，在单台机器上构建散列表示行不通的，因为单台机器的内存有限，而1亿张图片构建散列表远远超过了单台机器的内存上限。
  ②解决方案
  准备n台机器，让每台机器只维护一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一表示和图片路径发往对应的机器构建散列表。
  当我们要判断一个图片是否在图库中时，我们通过同样的哈希算法，计算这个图片的唯一表示，然后与机器个数n求余取模。假设得到的值是k，那就去编号为k的机器构建的散列表中查找。
  如何估算给1亿张图片构建散列表大约需要多少台机器？
  散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设我们通过 MD5 来计算哈希值，那长度就是 128 比特，也就是 16 字节。文件路径长度的上限是 256 字节，我们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突，那还需要存储指针，指针只占用 8 字节。所以，散列表中每个数据单元就占用 152 字节（这里只是估算，并不准确）。
  假设一台机器的内存大小为 2GB，散列表的装载因子为 0.75，那一台机器可以给大约 1000 万（2GB*0.75/152）张图片构建散列表。所以，如果要对 1 亿张图片构建索引，需要大约十几台机器。在工程中，这种估算还是很重要的，能让我们事先对需要投入的资源、资金有个大概的了解，能更好地评估解决方案的可行性。
  实际上，针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制。
  3.分布式存储
  3.1.什么是分布式存储？
  分布式存储就是将数据存储在多台机器上并提供高效的读取、写入支持。那如何决定将哪个数据放到哪个机器上呢？可以利用数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
  3.2.遇到的问题是什么？
  如果数据持续增多，原来的机器数量已经不能满足需求，就需要增加机器，这时就麻烦了，因为所有的数据都需要重新哈希值进行再次分配。这就相当于，缓存中的数据一下子都失效了，所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。
  3.3.解决方案是什么？
  ①这时，需要一种方法，使得新加入一个机器后，并不需要做大量的数据搬移。那就是在分布式系统中应用非常广泛的一致性哈希算法。
  ②一致性哈希算法的基本思想是什么呢？为了说清楚这个问题，我们假设有k个机器，数据的哈希值范围是[0-MAX]，我们将整个范围划分成m个小区间（m远大于k），每个机器复杂m/k个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据量的均衡。

  2018-11-16

  

   16
• 

  鹏飞天下

  一致性hash算法http://www.zsythink.net/archives/1182

  2019-01-03

   2

   14
• 

  CCC

  Redis集群就是应用的一致性哈希算法

  2018-11-09

   1

   13
• 

  会网络的老鼠

  上几节讲过扩容冗余算法，可以避免搬移数据，如果对当前n取模未中再对扩容前的m取模，直到都未中再返回值是不是也可以？

  作者回复: 👍 也是可以的

  2018-11-09

  

   12
• 

  jiaobuchongจุ๊บ

  一致性 hash 算法，这篇文章讲得挺好的：http://www.zsythink.net/archives/1182

  2018-12-15

   1

   11
• 

  若星

  数据分片“搜索关键词”出现的次数，依次读出每个搜索关键词，的时候就可以计数了吧？

  2018-11-26

  

   6
• 

  虎虎❤️

  您在计算1亿张图片的散列表占用内存的部分提到，每个数据单元都包含16字节的md5哈希值。加上文件路径和指针，一共152字节。这里为什么要存哈希值呢？谢谢

  2018-11-13

   2

   5
• 

  www.xnsms.com小鸟接码

  感觉评论里好多技术大佬，如果老师能附上一致性哈希算法代码案例就更好了

  作者回复: 嗯嗯 感谢给出的意见

  2018-11-09

  

   4
• 

  道

  希望对一致性哈希有深入的讲解。

  2018-11-09

  

   4
• 

  Lucus

  git status应该也是利用文件的hash值判断文件是否有修改的

  2019-04-09

  

   3
• 

  蓝艺

  自己用go写的，一致性hash算法，https://github.com/lanyilee/ConsistentHash

  2018-11-30

  

   3
• 

  ZX

  采用一致性hash算法，在增加节点的时候，是不是仍然要遍历数据，进行部分迁移，只是改变存储数据比较少啊

  作者回复: 对于缓存来说 可以不用 直接让要搬移的数据失效就好了

  2018-11-18

  

   3
• 

  晓龙

  一致性hash算法感觉不是利用hash取模分配的，而是规定好哪些内容分配到哪些机器中，如果扩容就讲某些内容移植到新机器中，具体选择哪些内容移植到新机器，也不是用的hash去做的

  2019-02-20

   3

   2
• 

  NeverMore

  我了解的，某些互联网大厂Redis，使用的不是Redis的集群，而是主从的模式，客户端通过Hash映射到相应的机器上，使用的也是自己的hash算法。

  2018-11-12

  

   2
• 

  远方夕阳

  一致性哈希也会存在映射差异的问题， A ,C节点中插入B节点，那么A B之间原先映射到C的请求都会B，这样的情况，是要C分割一些数据给B吗

  作者回复: 是的

  2018-11-11

  

   2
• 

  cyf

  哈希值相同的搜索关键词就被分配到了同一个机器上，这里数据是分片存储到不同的机器上的，而同一个机器只搜索固定的关键词，最后的结果会不会不完整？可能我没get到老师的点。

  2018-11-09

  

   2