数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

应用五:负载均衡

我们知道,负载均衡算法有很多,比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞(session sticky)的负载均衡算法呢?也就是说,我们需要在同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上。
最直接的方法就是,维护一张映射关系表,这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求,都要先在映射表中查找应该路由到的服务器编号,然后再请求编号对应的服务器。这种方法简单直观,但也有几个弊端:
如果客户端很多,映射表可能会很大,比较浪费内存空间;
客户端下线、上线,服务器扩容、缩容都会导致映射失效,这样维护映射表的成本就会很大;
如果借助哈希算法,这些问题都可以非常完美地解决。我们可以通过哈希算法,对客户端 IP 地址或者会话 ID 计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。 这样,我们就可以把同一个 IP 过来的所有请求,都路由到同一个后端服务器上。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(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
收起评论
99+
返回
顶部