分布式技术原理与算法解析
聂鹏程
智载云帆CTO,前华为分布式Lab资深技术专家
立即订阅
6102 人已学习
课程目录
已完结 39 讲
0/4登录后,你可以任选4讲全文学习。
课前必读 (3讲)
开篇词 | 四纵四横,带你透彻理解分布式技术
免费
01 | 分布式缘何而起:从单兵,到游击队,到集团军
02 | 分布式系统的指标:啥是分布式的三围
第一站:分布式协调与同步 (6讲)
03 | 分布式互斥:有你没我,有我没你
04 | 分布式选举:国不可一日无君
05 | 分布式共识:存异求同
06 | 分布式事务:All or nothing
07 | 分布式锁:关键重地,非请勿入
08 | 分布式技术是如何引爆人工智能的?
第二站:分布式资源管理与负载调度 (6讲)
09 | 分布式体系结构之集中式结构:一人在上,万人在下
10 | 分布式体系结构之非集中式结构:众生平等
11 | 分布式调度架构之单体调度:物质文明、精神文明一手抓
12 | 分布式调度架构之两层调度:物质文明、精神文明两手抓
13 | 分布式调度架构之共享状态调度:物质文明、精神文明多手协商抓
14 | 答疑篇:分布式事务与分布式锁相关问题
第三站:分布式计算技术 (4讲)
15 | 分布式计算模式之MR:一门同流合污的艺术
16 | 分布式计算模式之Stream:一门背锅的艺术
17 | 分布式计算模式之Actor:一门甩锅的艺术
18 | 分布式计算模式之流水线:你方唱罢我登场
第四站:分布式通信技术 (4讲)
19 | 分布式通信之远程调用:我是你的千里眼
20 | 分布式通信之发布订阅:送货上门
21 | 分布式通信之消息队列:货物自取
22 | 答疑篇:分布式体系架构与分布式计算相关问题
第五站:分布式数据存储 (5讲)
23 | CAP理论:这顶帽子我不想要
24 | 分布式数据存储系统之三要素:顾客、导购与货架
25 | 数据分布方式之哈希与一致性哈希:“掐指一算”与“掐指两算”的事
26 | 分布式数据复制技术:分身有术
27 | 分布式数据之缓存技术:“身手钥钱”随身带
特别放送 (3讲)
特别放送 | 分布式下的一致性杂谈
特别放送 | 徐志强:学习这件事儿,不到长城非好汉
特别放送 | 那些你不能错过的分布式系统论文
第六站:分布式高可靠 (5讲)
28 | 分布式高可靠之负载均衡:不患寡,而患不均
29 | 分布式高可靠之流量控制:大禹治水,在疏不在堵
30 | 分布式高可用之故障隔离:当断不断,反受其乱
31 | 分布式高可用之故障恢复:知错能改,善莫大焉
32 | 答疑篇:如何判断并解决网络分区问题?
第七站:分布式核心知识串讲 (2讲)
33 | 知识串联:以购买火车票的流程串联分布式核心技术
34 | 搭建一个分布式实验环境:纸上得来终觉浅,绝知此事要躬行
结束语 (1讲)
结束语 | 为什么说提升职业竞争力要从尊重、诚实开始?
分布式技术原理与算法解析
登录|注册

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

聂鹏程 2019-11-22
你好!我是聂鹏程。今天,我来继续带你打卡分布式核心技术。
在上一篇文章中,我带你了解了分布式存储系统的三个要素:顾客、导购和货架。其中,导购实现了分布式数据存储系统中数据索引的功能,包括存储数据时确定存储位置,以及获取数据时确定数据所在位置。
那么,在分布式系统中,具体是如何实现数据索引或数据分布的呢?目前最常用的方法就是哈希和一致性哈希。
接下来,我们就一起打卡数据分布式方式中的哈希与一致性哈希吧。
首先,我们来看一下数据分布设计的原则。数据分布设计原则是分布式存储系统设计的基本原则,指导了哈希和一致性哈希方法的选择和应用。

数据分布设计原则

其实,这里的数据分布,主要就是数据分片。相信你还记得,我在第 24 篇文章中与你分享分布式存储系统的导购时,已经和你提到数据分片技术,它解决了确定数据位置的问题,并着重与你讲述了按照数据特征进行划分的分片方法。今天,我主要与你讲解按照数据范围,采用哈希、一致性哈希等对数据划分的方法。
假设,现在有上百 G 数据需要进行分布式存储,也就是要存储到不同的节点上。提到这个问题,你可能立刻就会想到很多种方法,比如随机分布、范围分布、映射分布等。那么,我们应该如何选择到底要使用哪种方法呢?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《分布式技术原理与算法解析》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(10)

  • 随心而至
    范围分区:通过确定分区键是否在一定范围内来选择分区。比如按照年龄范围分区。
    列表分区:为分区分配值列表。比如按照所属国家对用户分区。
    循环分区:对于n个分区,将插入顺序中的第i个元组分配给i%n分区
    散列函数:将数据的某些字段通过散列函数计算得到分区号。比如Redis。
    组合分区:允许上述划分方案的某些组合
    参见:
    https://en.wikipedia.org/wiki/Partition_(database)
    https://dev.mysql.com/doc/refman/8.0/en/partitioning-types.html
    2019-11-22
    2
  • LovRNA
    带有限负载的一致性hash,在查询数据时,怎么确定数据存储在哪个节点上呢?

    作者回复: 带有限负载的一致性hash在存储时实际是分两步走,第一步通过一致性哈希计算出一个命中节点,如果命中节点有足够的空间,则存储在命中节点上,否则按顺时针方向,依次遍历下一个节点,直到找到下一个节点为止。

    查询的时候如果按照存储的方式去计算命中节点,然后再去顺时针依次遍历下一个节点,这时你就会发现问题来了。

    因为,如果查询数据不存在的话,需要遍历完整个哈希环上的所有节点。这种遍历的开销就太大了,因为这是网络上的遍历,可不是单机内存内的遍历。

    一种思路是,在哈希命中节点上额外添加一个索引表,用以记录命中到该节点上的数据存储在哈希环上的位置。这样在通过一致性哈希计算出命中的节点后,只需要再查询这个节点上的索引表就可以找到实际的存储节点了。

    其实这个本质上就是一个解决哈希冲突的过程,你可以再回想一下我们在数据结构中的哈希表解决冲突的方法,通过对比学习,可以更进一步加深你的理解。

    2019-12-21
    1
  • Eternal
    本节课是分布式相关的知识点中最熟悉的一节,但是之前都是零碎的信息,没有把这四种数据分布方式进行细致的对比,这次老师的对比
    让我豁然开朗。下面总结一下我的思考:

    提到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+树 来组织分布式的数据???
    2019-11-23
    1
  • Jackey
    之前这些方法也都知道,但就是说不清楚,有些也不知道叫什么名。这回终于能说明白了,感觉以后面试又可以吹一波了。至于今天的思考题…能力有限,坐等课代表科普
    2019-11-22
    1
    1
  • 一毛钱
    根据划定的单位分区,根据指定的规则分区
    2019-12-15
  • Geek_e986e3
    老师 两个问题
    1.带有限状态的分布式一致hash 在读取的时候怎么做的呢,打个比方。如果要存储的节点满了。存到顺时针之后好几个节点。但是读的时候。可能节点已经不满了。怎么做到读取呢?每个都遍历一遍吗?有没有更优雅的方法?
    2.还是有限状态的。如果所有节点都存满了。一般怎么处理呢?
    2019-11-25
  • 终于明白了一致性哈希算法,关键在于一个环,如何确定环上的数据组成是需要考虑的地方,老师举例中是跟数据等值分布,节点再使用ip哈希定位到环中的某个数据,确定这些后,其实数据会被切分成多份,每个节点对应左边的数据就行。
    有限数据一致性哈希是解决稳定性问题的,而带虚拟节点一致性哈希算法是解决节点异构问题的,可以理解成带权重的节点。

    2019-11-22
  • leslie
    哈希这块一直学过可是原理不清楚,为此还去学习算法了解其本源;可是像老师这样清楚的梳理还是没有明白。知其然知其所以然:明白清楚了在数据系统中的使用就更加从容了。
    2019-11-22
  • 随心而至
    有一些疑问:
    1.是不是带有限负载的一致性哈希,所有机器的存储上线都只能是同一个上限值吗?按照老师文中它没有解决不同机器的异构性,以及带虚拟节点的一致性哈希就是用来解决该问题,猜测是这样。
    2.带有限负载的一致性哈希,是不是可能导致读写的时候查多次,因为有个上线的概念?还是说每个节点都有各个节点保存数据的范围,最多只会转发一次读写。
    2019-11-22
  • xingoo
    按照范围进行分片,典型的代表hbase。
    因为它需要根据rowkey范围锁定数据存储的位置,相邻的rowkey数据会按照顺序存储在磁盘,因此在执行rowkey的单位查询时,性能非常快。为了避免单位的热点不均衡,伴随着也有很多差分和合并的机制。
    2019-11-22
收起评论
10
返回
顶部