数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?

一致性哈希算法
一致性哈希算法
数据分片
散列表构建
多机处理
分片处理
MapReduce思想
并行处理
分片处理
借助哈希算法
维护映射关系表
解决扩容、缩容问题
突破资源限制
提高处理速度
解决分布式问题
分布式存储
数据分片
负载均衡
其他分布式存储系统
分布式缓存
快速判断图片是否在图库中
统计搜索关键词出现次数
会话粘滞
哈希算法的优势
哈希算法在分布式系统中的应用
分布式存储
数据分片
负载均衡
总结
哈希算法在分布式系统中的应用

该思维导图由 AI 生成,仅供参考

上一节,我讲了哈希算法的四个应用,它们分别是:安全加密、数据校验、唯一标识、散列函数。今天,我们再来看剩余三种应用:负载均衡、数据分片、分布式存储
你可能已经发现,这三个应用都跟分布式系统有关。没错,今天我就带你看下,哈希算法是如何解决这些分布式问题的

应用五:负载均衡

我们知道,负载均衡算法有很多,比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞(session sticky)的负载均衡算法呢?也就是说,我们需要在同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上。
最直接的方法就是,维护一张映射关系表,这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求,都要先在映射表中查找应该路由到的服务器编号,然后再请求编号对应的服务器。这种方法简单直观,但也有几个弊端:
如果客户端很多,映射表可能会很大,比较浪费内存空间;
客户端下线、上线,服务器扩容、缩容都会导致映射失效,这样维护映射表的成本就会很大;
如果借助哈希算法,这些问题都可以非常完美地解决。我们可以通过哈希算法,对客户端 IP 地址或者会话 ID 计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。 这样,我们就可以把同一个 IP 过来的所有请求,都路由到同一个后端服务器上。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

哈希算法在分布式系统中有着广泛的应用。本文总结了哈希算法在负载均衡、数据分片和分布式存储等方面的应用。在负载均衡中,哈希算法可以实现会话粘滞的负载均衡策略,避免了映射表的弊端。在数据分片应用中,哈希算法可以实现海量数据的分片处理,通过多机分布式处理来提高处理速度。在分布式存储中,一致性哈希算法解决了扩容、缩容导致数据大量搬移的难题。此外,一致性哈希算法在分布式存储系统中有着广泛的应用。文章还提到了哈希算法的其他应用,如网络协议中的CRC校验、Git commit id等。通过本文的总结,读者可以快速了解哈希算法在分布式系统中的重要作用,以及其在负载均衡、数据分片和分布式存储中的具体应用。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(171)

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

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

    2018-11-09
    5
    37
  • 会网络的老鼠
    上几节讲过扩容冗余算法,可以避免搬移数据,如果对当前n取模未中再对扩容前的m取模,直到都未中再返回值是不是也可以?

    作者回复: 👍 也是可以的

    2018-11-09
    5
    29
  • Geek_41d472
    感觉评论里好多技术大佬,如果老师能附上一致性哈希算法代码案例就更好了

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

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

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

    2018-11-18
    2
    7
  • 书木子谢明
    老师,MD5计算的哈希值是128位,是不是意味着,用MD5计算小于2∧128个不同数据,不会出现哈希冲突?

    作者回复: 当然不是了 大于2^128个数据是必然有冲突 但有可能随便找2个数据就冲突了

    2018-11-10
    4
  • Jamin
    如果减机器呢

    作者回复: 减机器的套路也是一样的 机器上的数据分配给其他机器

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

    作者回复: 是的

    2018-11-11
    2
  • 勤劳的小胖子-libo
    在负载均衡那一块,客户端上线下线和服务器扩容缩容怎么影响映射表呢啊? 这部分没看明白。"如果借助哈希算法,这些问题都可以非常完美地解决。"这个方法也会对服务器列表进行取模运算,那为什么扩容,缩容没影响?难道是应用到了一致性哈希?

    作者回复: 客户端下线了 映射关系要删除吧 不然会浪费内存 客户端上线 映射关系要加上吧

    2018-11-11
    4
    1
  • 厚积薄发
    老师举例的负载均衡,利用哈希算法解决同一个IP的请求,都被路由到同一个服务器编号,而服务器机器增加、减少等,原来的服务器会变成新的服务器,这个时候如果涉及到数据文件等的迁移,那么可以应用到下面讲到的哈希一致性能解决了数据的全量搬迁问题,我的理解是这样,不知道对不对

    作者回复: 对的

    2019-10-18
    2
  • 小喵喵
    找了好多资料终于看懂了一致性hash算法,但是还是有一个疑问,就是为什么节点是2的32次方,而不是其他,比如10w。请老师帮我解答一下,谢谢。

    作者回复: 没说非得是2的32次方吧,其他的也可以的。

    2019-10-17
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部