精华内容
下载资源
问答
  • 哈希与一致性哈希
    2019-09-06 22:41:53

    1 哈希解决冲突的三种方法

    1. 开放定址法
      也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi
      具体有三种:
      线性探测再散列:冲突发生时,顺序查看表中下一单元,直到找出一个空单元
      二次探测再散列:冲突发生时,在表的左右进行跳跃式探测。
      伪随机探测再散列:伪随机数序列。
    2. 再哈希法
      同时构造多个不同的哈希函数:
      Hi=RH1(key) i=1,2,…,k
      当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。
    3. 链地址法
      这种方法的基本思想是将哈希地址相同的元素构成一个单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
    4. 建立公共溢出区
      这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

    2 一致性哈希

    Consistent hashing 的基本思想就是将元素和服务器都映射到同一个环形hash空间中,并且使用相同的 hash算法。

    更多相关内容
  • 哈希和一致性哈希

    2020-11-17 17:37:05
    Hash,一般翻译做散列、杂凑,或音译为哈希,是指把任意长度的输入(又叫做预映射pre-image)通过哈希算法变换成固定长度的输出的过程,该输出就是哈希值。 哈希算法(哈希函数) 哈希算法指的是能把任意长度的输入...

    什么是哈希

    Hash,一般翻译做散列、杂凑,或音译为哈希,是指把任意长度的输入(又叫做预映射pre-image)通过哈希算法变换成固定长度的输出的过程,该输出就是哈希值。

    哈希算法(哈希函数)

    哈希算法指的是能把任意长度的输入变换成固定长度输出的一系列算法。大家都知道数学中的函数如y=x+1, 通过改变x的值,我们可以得到对应的y。哈希函数其实也一样,通过传入不同的输入得到对应的输出,不同的是哈希函数的输入不仅限于数学中的数字,并且它的输出是固定长度的,具有一定规则的。常见的哈希算法有MD5, SHA-1, SHA-2, UUID1, UUID…

    哈希冲突

    理论上哈希算法输入跟输出的映射关系应该是一对一的,但是会有一定概率出现多个输入对应一个输出,即不同的x值得到了同样的y值,这种情况叫哈希冲突。解决哈希冲突也有许多常见的方法,比如拉链法,线性探查法…可以自行去了解

    哈希取模

    哈希取模是指对hash结果取余。假设我们现在需要对数据库进行分表分库。需要把user表分成10个表,这时我们只需对user_id进行哈希取模,即user_id.hash() % 10, 假设user_id.hash()等于12, 则把该记录存入第2(12 % 10 = 2)个表中。取值的时候重复上面步骤即可知道从哪个表查询我们想要的数据了。但是假设我们的用户有激增了,我们需要从10个表分成20个表,这个时候我们通过user_id.hash()%20去查数据肯定查不到之前的数据了,应为之前是通过user_id.hash() % 10去存储的。要解决这个问题,我们就得把所有数据重新hash,但是这样的代价是比较大的。为了解决这个问题,于是就有了一致性哈希

    一致性哈希

    一致性哈希

    一致性 Hash 算法也是使用取模的思想,只是,刚才描述的取模法是对节点数量进行取模,而一致性Hash算法是对 2^32 取模,什么意思呢?简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希环如下,从 0 ~ 2^32-1 代表的分别是一个个的节点,这个环也叫哈希环
    在这里插入图片描述

    然后我们将我们的节点进行一次哈希,按照一定的规则,比如按照 ip 地址的哈希值,让节点落在哈希环上。比如此时我们可能得到了如下图的环:
    在这里插入图片描述

    然后就是需要通过数据 key 找到对应的服务器然后存储了,我们约定,通过数据 key 的哈希值落在哈希环上的节点,如果命中了机器节点就落在这个机器上,否则落在顺时针直到碰到第一个机器。如下图所示 : A 的哈希值落在了 D2 节点的前面,往下找落在了 D2 机器上,D的哈希值 在 D1 节点的前面,往下找到了 D1 机器,B的哈希值刚好落在了D1 节点上,依次~~~
    在这里插入图片描述

    一致性哈希的分析

    一致性哈希主要就是解决当机器减少或增加的时候,大面积的数据重新哈希的问题,主要从下面 2 个方向去考虑的,当节点宕机时,数据记录会被定位到下一个节点上,当新增节点的时候 ,相关区间内的数据记录就需要重新哈希。

    某节点宕机

    我们假设上图中的 节点 D2 因为一些原因宕机了,可以看到,只有数据 A 的记录需要重新重新定位存储到节点 D1 上,因为 D1 是 D2 的下一个节点,其它的数据都没有被影响到,此时被影响的仅仅是 图中的 D0-D2 这段区间的记录,也就是之前落在 D2 上的数据现在都要落到 D1 上面了。如下图
    在这里插入图片描述

    新增节点

    我们假设我们需要增加一台机器,也就是增加一个节点D4,如下图所示,这个节点落在 D2-D1 之间,按照上述的哈希环上的哈希值落在节点的规则,那么此时之前落在 D2 到 D4 之间的数据都需要重新定位到新的节点上面了,而其它位置的数据是不需要有改变的。
    在这里插入图片描述

    一致性哈希的数据倾斜问题

    一致性Hash算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)问题。比如只有 2 台机器,这 2 台机器离的很近,那么顺时针第一个机器节点上将存在大量的数据,第二个机器节点上数据会很少。如下图所示,D0 机器承载了绝大多数的数据

    数据倾斜

    虚拟节点解决数据倾斜问题

    为了避免出现数据倾斜问题,一致性 Hash 算法引入了虚拟节点的机制,也就是每个机器节点会进行多次哈希,最终每个机器节点在哈希环上会有多个虚拟节点存在,使用这种方式来大大削弱甚至避免数据倾斜问题。同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“D1#1”、“D1#2”、“D1#3”三个虚拟节点的数据均定位到 D1 上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。这也是 Dubbo 负载均衡中有一种一致性哈希负载均衡的实现思想。
    在这里插入图片描述

    一致性哈希的应用案例

    一致性哈希用到的地方很多,特别是中间件里面,比如 Dubbo 的负载均衡也有一种策略是一致性哈希策略,使用的就是虚拟节点实现的。Redis 集群中也用到了相关思想但是没有用它而是根据实际情况改进了一下。而对于存储数据的节点水平切分的时候它的作用就更不可代替了。and so on···

    Redis 集群分槽的实现

    Redis 集群并没有直接使用一致性哈希,而是使用了哈希槽 (slot) 的概念,Redis 没有直接使用哈希算法 hash(),而是使用了crc16校验算法。槽位其实就是一个个的空间的单位。其实哈希槽的本质和一致性哈希算法非常相似,不同点就是对于哈希空间的定义。一致性哈希的空间是一个圆环,节点分布是基于圆环的,无法很好的控制数据分布,可能会产生数据倾斜问题。而 Redis 的槽位空间是自定义分配的,类似于Windows盘分区的概念。这种分区是可以自定义大小,自定义位置的。Redis 集群包含了 16384 个哈希槽,每个 Key 经过计算后会落在一个具体的槽位上,而槽位具体在哪个机器上是用户自己根据自己机器的情况配置的,机器硬盘小的可以分配少一点槽位,硬盘大的可以分配多一点。如果节点硬盘都差不多则可以平均分配。所以哈希槽这种概念很好地解决了一致性哈希的弊端。
    另外在容错性和扩展性上与一致性哈希一样,都是对受影响的数据进行转移而不影响其它的数据。而哈希槽本质上是对槽位的转移,把故障节点负责的槽位转移到其他正常的节点上。扩展节点也是一样,把其他节点上的槽位转移到新的节点上。

    需要注意的是,对于槽位的转移和分派,Redis集群是不会自动进行的,而是需要人工配置的。所以Redis集群的高可用是依赖于节点的主从复制与主从间的自动故障转移。
    在这里插入图片描述

    参考链接:

    链接:https://www.jianshu.com/p/735a3d4789fc

    展开全文
  • 在分布式数据存储系统中,存储方案选型时,通常会考虑数据均匀、数据稳定节点异构这三个维度。 数据均匀 每个节点存储的数据相差不太大即可 数据稳定 当存储节点出现故障需要移除或者扩增时,数据按照分布...

    数据分片方式脑图

    数据分布设计原则

    在分布式数据存储系统中,存储方案选型时,通常会考虑数据均匀、数据稳定和节点异构性这三个维度。

    数据均匀

    每个节点存储的数据相差不太大即可

    数据稳定

    当存储节点出现故障需要移除或者扩增时,数据按照分布规则得到的结果应该尽量保持稳定,不要出现大范围的数据迁移。

    数据稳定,就是尽可能只迁移移除节点上的数据到其他节点上,而不需要对大范围或所有数据进行迁移存储。当然,如果有扩展同类型节点,也是尽可能小范围迁移数据到扩展的节点上。具体的迁移方法,可以采用下文介绍的一致性哈希方法。

    节点异构性

    不同存储节点的硬件配置可能差别很大。比如,有的节点硬件配

    置很高,可以存储大量数据,也可以承受更多的请求;但,有的节点硬件配置就不怎么样,

    存储的数据量不能过多,用户访问也不能过多。

    如果这种差别很大的节点,分到的数据量、用户访问量都差不多,本质就是一种不均衡。所

    以,一个好的数据分布算法应该考虑节点异构性

    隔离故障域

    是为了保证数据的可用和可靠性。比如,我们通常通过备份来实现数据的可靠性。但如果每个数据及它的备份,被分布到了同一块硬盘或节点上,就有点违背备份的初衷了。所以,一个好的数据分布算法,应该为每个数据映射一组存储节点,这些节点应该尽量在不同的故障域,比如不同机房、不同机架等。

    性能稳定性

    是指,数据存储和查询的效率要有保证,不能因为节点的添加或者移除,造成存

    储或访问性能的严重下降。

     

    了解了数据分布的设计原则后,接下来我们再看看主流的数据分布式方法,哈希和一致性哈

    希吧。其中,哈希和一致性哈希是数据分布的基础方法,在不同场景下,数据分布设计的原

    则需要考虑的维度也不一样。随着维度的增加,一致性哈希又可进一步演进为带有限负载的

    一致性哈希和带虚拟节点的一致性哈希方法。

     

    数据分布方法

    哈希是指,将数据按照提前规定好的函数(哈希函数)映射到相应的存储节点,即进行一个

    哈希计算,得到的结果就是数据应该存储的节点。

    一致性哈希同样是采用哈希函数,进行两步哈希:1. 对存储节点进行哈希计算,也就是对存储节点做哈希映射;

    2. 当对数据进行存储或访问时,首先对数据进行映射得到一个结果,然后找到比该结果大

    的第一个存储节点,就是该数据应该存储的地方。我会在下面的内容中,与你详细介绍

    其中的原理。

    总结来讲,哈希是一步计算直接得到相应的存储节点,而一致性哈希需要两步才可以找到相

    应的存储节点。这,是不是就是“掐指一算”与“掐指两算”的事呢?

     

    哈希

    哈希是一种非常常用的数据分布方法,其核心思想是,首先确定一个哈希函数,然后通过计

    算得到对应的存储节点。我们通过一个具体的例子来看一下吧。

    假设,有三个存储节点,分别为 Node1、Node2 和 Node3;现有以下数据,ID 的范围为

    [0,1000]:D0:{ id:100, name:‘a0’}、D1:{ id:200, name:‘a1’} 、D2:{ id:300,

    name:‘a2’}、D3:{ id:400, name:‘a3’}、D4:{ id:500, name:‘a4’}、D5:{ id:600,

    name:‘a5’}和 D6:{ id:700, name:‘a6’}。

    假设,哈希函数为“id% 节点个数”,通过计算可以得到每个数据应该存入的节点。在这

    个例子中,哈希函数是“id%3”,结果为 0 的数据存入 Node1、结果为 1 的数据存入

    Node2、结果为 2 的数据存入 Node3。

    如图所示,Node1 将存储数据 D2(300%3=0)和 D5(600%3=0),Node2 将存储数

    据 D0(100%3=1)、D3(400%3=1)和 D6(700%3=1),Node3 将存储数据

    D1(200%3=2)和 D4(500%3=2)。

    image.png

    可以看出,哈希算法的一个优点是,只要哈希函数设置得当,可以很好地保证数据均匀性,

    但有一个较为严重的缺点,就是稳定性较差。

    比如,随着数据量的增加,三个节点的容量无法再满足存储需求了,需要再添加一个节点。

    这时,哈希函数变成了 id%4,原先存储在那三个节点的数据需要重新计算,然后存入相应

    节点,即需要大规模的数据迁移,显然会降低稳定性。

    所以,哈希方法适用于同类型节点且节点数量比较固定的场景。目前,Redis 就使用了哈希

    方法,你可以再回顾下第 10 篇文章“分布式体系结构之非集中式结构:众生平等”中的相

    关内容。

    接下来,我们再看看一致性哈希吧。

    一致性哈希

    一致性哈希是指将存储节点和数据都映射到一个首尾相连的哈希环上,存储节点可以根据

    IP 地址进行哈希,数据通常通过顺时针方向寻找的方式,来确定自己所属的存储节点,即

    从数据映射在环上的位置开始,顺时针方向找到的第一个存储节点。

    我们看看如何用一致性哈希方法,来实现上述案例的数据存储吧。

    如图所示,假设数据 D0~D7 按照 ID 进行等值映射,即映射值与 ID 值相等,比如数据

    D0 映射到哈希环上的值为 100,数据 D1 映射到哈希环上的值为 200······;同时,假设存

    储节点 Node1、Node2 和 Node3 映射到哈希环上的值分别为 400、600、900。

    按照规则,D0,D1,D2 和 D3 顺时针方向的下一个存储节点为 Node1,因此 Node1 将

    存储数据 D0(id = 100)、D1(id = 200)、D2(id = 300)和 D3(id = 400);同

    理,Node2 将存取数据 D4(id = 500)和 D5(id = 600),Node3 将存取数据 D6(id

    = 700)。

    image.png可以看出,一致性哈希是对哈希方法的改进,在数据存储时采用哈希方式确定存储位置的基

    础上,又增加了一层哈希,也就是在数据存储前,对存储节点预先进行了哈希。

    这种改进可以很好地解决哈希方法存在的稳定性问题。当节点加入或退出时,仅影响该节点

    在哈希环上顺时针相邻的后继节点。比如,当 Node2 发生故障需要移除时,由于 Node3

    是 Node2 顺时针方向的后继节点,本应存储到 Node2 的数据就会存储到 Node3 中,其

    他节点不会受到影响,因此不会发生大规模的数据迁移。

    所以,一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前,

    Cassandra 就使用了一致性哈希方法,你可以再回顾下第 10 篇文章“分布式体系结构之非

    集中式结构:众生平等”中的相关内容。

    一致性哈希方法虽然提升了稳定性,但随之而来的均匀性问题也比较明显,即对后继节点的

    负载会变大。有节点退出后,该节点的后继节点需要承担该节点的所有负载,如果后继节点承受不住,便会出现节点故障,导致后继节点的后继节点也面临同样的问题。

    那么,有没有更好的方法来解决这个问题呢?

    Google 在 2017 年提出了带有限负载的一致性哈希算法,就对这个问题做了一些优化。

    带有限负载的一致性哈希

    带有限负载的一致性哈希方法的核心原理是,给每个存储节点设置了一个存储上限值来控制

    存储节点添加或移除造成的数据不均匀。当数据按照一致性哈希算法找到相应的存储节点

    时,要先判断该存储节点是否达到了存储上限;如果已经达到了上限,则需要继续寻找该存

    储节点顺时针方向之后的节点进行存储。

    我们看看如何用带有限负载的一致性哈希方法,来实现上述案例的数据存储吧。

    如图所示,假设每个存储节点设置的上限值为 3,按照一致性哈希算法,当存储数据

    D3(id = 400)时,会发现应该存储到 Node1 中,但 Node1 已经存储了三个数据

    D0(id = 100)、D1(id = 200)和 D2(id = 300),达到了存储上限,因此会存储到

    该节点顺时针方向的下一个节点 Node2 中。当然,在存储前,也会先检查 Node2 是否达

    到了存储上限,如果达到了,会继续寻找其他节点。

    image.png

    如果你想要了解该算法的详细内容,可以阅读“Consistent Hashing with Bounded

    Loads”这篇论文。

    带有限负载的一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前,在

    Google Cloud Pub/Sub、HAProxy 中已经实现该方法,应用于 Google、Vimeo 等公司

    的负载均衡项目中。

    其实,哈希、一致性哈希、带有限负载的一致性哈希,都没有考虑节点异构性的问题。如果

    存储节点的性能好坏不一,数据分布方案还按照这些方法的话,其实还是没做到数据的均匀

    分布。

    接下来,我们再看一种主要针对存储节点为异构节点场景的方法,即带虚拟节点的一致性哈

    希吧。

    带虚拟节点的一致性哈希

    带虚拟节点的一致性哈希方法,核心思想是根据每个节点的性能,为每个节点划分不同数量

    的虚拟节点,并将这些虚拟节点映射到哈希环中,然后再按照一致性哈希算法进行数据映射

    和存储。

    假设,Node1 性能最差,Node2 性能一般,Node3 性能最好。以 Node1 的性能作为参

    考基准,Node2 是 Node1 的 2 倍,Node3 是 Node1 的 3 倍。

    因此,Node1 对应一个虚拟节点 Node1_1,Node2 对应 2 个虚拟节点 Node2_1 和

    Node2_2,Node3 对应 3 个虚拟节点 Node3_1、Node3_2 和 Node3_3。

    假设,虚拟节点 Node1_1、Node2_1、Node2_2、Node3_1、Node3_2、Node3_3 的

    哈希值,分别为 100、200、300、400、500、600。

    那么,按照带虚拟节点的哈希一致性方法, 数据 D0 和 D6 按顺时针方向的下一个虚拟存

    储节点为 Node 1-1,因此节点 Node1 将会存储数据 D0(id = 100)和 D6(id =

    700);同理,Node2 将会存储数据 D1(id = 200)和 D2(id = 300),Node3 将会

    存储数据 D3(id = 400)、D4(id = 500)和 D5(id = 600)。

    image.png

    可以看出,带虚拟节点的一致性哈希方法比较适合异构节点、节点规模会发生变化的场景

    目前 Memcached 缓存系统实现了该方法,我会在第 27 篇文章中与你详细分析。

    这种方法不仅解决了节点异构性问题,还提高了系统的稳定性。当节点变化时,会有多个节

    点共同分担系统的变化,因此稳定性更高。

    比如,当某个节点被移除时,对应该节点的多个虚拟节点均会移除,而这些虚拟节点按顺时

    针方向的下一个虚拟节点,可能会对应不同的物理节点,即这些不同的物理节点共同分担了

    节点变化导致的压力。

    当然,这种方法引入了虚拟节点,增加了节点规模,从而增加了节点的维护和管理的复杂

    度,比如新增一个节点或一个节点故障时,对应到虚拟节点构建的哈希环上需要新增和删除

    多个节点,数据的迁移等操作相应地也会很复杂。

    四种数据分布方法对比

    为方便理解与记忆,我再通过一个表格和你对比分析下这四种方法吧。请注意,以下方法之

    间的对比都是相对的比较,实际性能优劣与哈希函数的设定以及具体的数据场景密切相关。

    image.png

     

    展开全文
  • 一致性哈希

    2018-10-24 14:26:06
    * 有两种方案,第一种普通hash分布,第二种一致性哈希分布 * * 普通hash分布 * 首先将key处理为一个32位字符串,取前8位,在经过hash计算处理成整数并返回,然后映射到其中一台服务器 * $servers[$this->...
  • 分布式哈希和一致性哈希 分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多,这里做一个入门性质的介绍。     分布式哈希(DHT)   两个key point:每个节点只维护...

    分布式哈希和一致性哈希

    分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多,这里做一个入门性质的介绍。

     

     

    分布式哈希(DHT)

     

    两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。

     

     

    DHT只是一个概念,提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现,并不是DHT的范畴。

     

     

    一致性哈希:

     

    DHT的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡,按querystring签名对后端节点取模是最简单也是最常用的算法,但节点的增删后所造成的问题显而易见,原有的请求几乎都落不到同一台机器上。优化一点的是carp算法(用机器ip和query一起做hash,选取hash值最小的一台),只让1/n的数据受到影响。

     

    一致性哈希,似乎最早提出是在分布式缓存里面的,让节点震荡的时候,影响最小。不过现在已经应用在分布式存储和p2p系统里面。

     

    一致性哈希也只是提出四个概念和原则,并没有提及具体实现:

     

    1、balance:哈希结果尽可能的平均分散到各个节点上,使得每个节点都能得到充分利用。

     

    2、Monotonicity:上面也说了,如果是用签名取模算法,节点变更会使得整个网络的映射关系更改。如果是carp,会使得1/n的映射关系更改。一致性哈希的目标,是节点变更,不会改变网络的映射关系。

     

    3、spread:同一份数据,存储到不同的节点上,换言之就是系统冗余。一致性哈希致力于降低系统冗度。

     

    4、load:负载分散,和balance其实是差不多的意思,不过这里更多是指数据存储的均衡,balance是指访的均衡。

     

     

    Chord算法:

     

    一致性哈希有多种实现算法,最关键的问题在于如何定义数据分割策略和节点快速查询。

     

    chord算是最为经典的实现。cassandra中的DHT,基本是chord的简化版。

     

    网络中每个节点分配一个唯一id,可以通过机器的mac地址做sha1,是网络发现的基础。

     

    假设整个网络有N 个节点,并且网络是呈环状。两个节点间的距离定义为每个节点会存储一张路由表(finger表),表内顺时针按照离本节点2、4、8、16、32.……2i的距离选定log2N个其他节点的ip信息来记录。

     

    存储方面:数据被按一定规则切割,每一份数据也有一个独立id(查询key),并且和节点id的值域是一样的。然后查找节点,如果存在和数据id一样的节点id,则将这份数据存在该节点上;如果不存在,则存储到离该数据id距离最近的节点上。同时,为了保证数 据的可靠性,会顺时针往下找K个冗余节点,存储这份数据。一般认为K=3是必须的。

     

    查询方面:先从自己的路由表中,找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的 id巧合和数据id相等,那么恭喜你。如果不相等,则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点,而这个次数是可以被证明小 于等于log2N的。

     

    在这个查询的过程中就体现了路由表的选取优势了,其实是实现了一个二分查找,从每个节点来观察网络,都是将网络分成了log2N块,最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询,最少排除了一半的节点。保证在 log2N次内找到目标节点。

     

    新增一个节点i,需要预先知道网络中已经存活的一个节点j,然后通过和节点j交互,更新自己和其他节点的路由表。并且,需要将离自己距离最近的节点中的数据copy过来,以提供数据服务。

     

    损失一个节点,路由算法会自动跳过这个节点,并且依靠数据的冗余来持续提供服务。

     

     

    KAD算法(Kademlia)

     

    kad算法其实是在chord上做的优化。主要是两个点:

     

    1、用二进制(32/64/128)表示一个节点的id,两节点的id异或运算得到节点间的距离。

     

    2、 每个节点保持的路由信息更丰富,同样是将整个网络按照划分成log2N份,在chord中,是保持log2N个路由节点,但在kad里面,是保存了 log2N个队列。每个队列长度为配置值K,记录网络中对应节点区域的多个节点,并且根据活跃时间对这些节点进行换入换出。

     

    第一点是方便进行网络划分,节点按照二进制中每一bit的0或1建成一棵二叉树。

     

    第二点是使得节点查询更迅速。从分割情况我们就可以得知,最坏情况不会差于chord,但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出,更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。

    展开全文
  • 一文读懂哈希和一致性哈希算法
  • nginx 负载均衡/一致性哈希

    千次阅读 2021-11-03 16:02:30
    nginx 负载均衡普通算法哈希算法一致性哈希一致性哈希算法的优点hash环的偏斜虚拟节点 普通算法 轮询算法:第一个请求给server1,第二个请求给server2,第3个请求给server3,一直轮询下去。 权重比算法:比如说,给...
  • 其次介绍了系统的实现流程,阐明了系统的关键技术:利用录音服务器对其镜像端口的SIP报文进行解析获得媒体流并解码、采用一致性哈希算法的内存数据库作为解码数据的缓存机制、利用Ckafka技术在两者之间构建实时数据...
  • 随着memcacheredis的出现,更多人认识到了一致性哈希一致性哈希用于解决分布式缓存系统中的数据选择节点存储问题数据选择节点读取问题以及在增删节点后减少数据缓存的消失范畴,防止雪崩的发生。 哈希槽是...
  • 在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。...
  • 一致性哈希和哈希槽

    2021-08-16 17:59:26
    其实哈希槽的本质和一致性哈希算法非常相似,不同点就是对于哈希空间的定义。一致性哈希的空间是一个圆环,节点分布是基于圆环的,无法很好的控制数据分布。而 redis cluster 的槽位空间是自定义分配的,类似于 ...
  • 数据分布方式:哈希与一致性哈希

    万次阅读 2021-12-26 14:22:14
    数据分布方式:哈希与一致性哈希前言数据分布设计原则数据分布方法哈希一致性哈希带有限负载的一致性哈希带虚拟节点的一致性哈希四种数据分布方法对比知识扩展:数据分片数据分区,有何区别?总结 前言 分布式...
  • 一致性哈希算法原理详解

    千次阅读 多人点赞 2021-10-17 18:31:32
    (1)一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环,称为 Hash 环; (2)接着将各个服务器使用 Hash 函数进行哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,从而确定每台机器在...
  • 一致性哈希算法详解

    千次阅读 2021-06-13 10:28:31
    1、使用哈希算法有什么问题? 假设有一个由A、B、C三个节点组成的KV服务,每个节点存放不同的KV数据。通过哈希算法,每个key都可以寻址到对应的服务器,比如,查询key是key-01,计算公式为hash(key-01)%3,经过计算...
  • 基于贪心算法的一致性哈希负载均衡优化
  • 博文链接:https://windshg.iteye.com/blog/1216914
  • 此提交使用一致性敏感散列 (CSH) 提供图像修复。 为了使用它,您需要来自http://www.eng.tau.ac.il/~simonk/CSH/index.html的 CSH 工具箱 包括一个测试脚本几个测试图像。
  • 1 一致性哈希 1.1 简单哈希 1.2 一致性哈希 1.3 一致性哈希的分析 1.4 某节点宕机(缩减节点) 1.5 新增节点 1.6 一致性哈希的数据倾斜问题 1.7 虚拟节点解决数据倾斜问题 1.8 一致性哈希的应用案例 ...
  • 一致性哈希和哈希槽使用场景对比

    千次阅读 2019-08-24 20:32:26
    一致性哈希和哈希槽是分布式缓存集群系统常用的两种算法,本文不会再介绍这两种算法,感兴趣的可以阅读参考博文。本文想在此基础上分析下两种算法使用场景的差异。 在参考博文4中给了一个示例: 上图为一致性...
  • 用于分布式 后总结
  • 运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
  • 一致性哈希和有界负载的一致性哈希的Golang实现。 一致的哈希示例 package main import ( "log" "github.com/lafikl/consistent" ) func main () { c := consistent . New () // adds the hosts to the ring ...
  • #资源达人分享计划#
  • 本文故事绝对真实,如有雷同,绝对不是巧合! 于是呢,烟哥提前十分钟在公司里头找了一个厕所的坑位,然后进去随手一锁门….(以下省略10000字)… 唉… 我竟然又带薪上厕所了,而且上了一小时!...
  • 本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
  • redis哈希槽和一致性哈希实现原理

    千次阅读 2020-10-24 17:41:39
    文章标题一致性哈希 一致性哈希 伴随着系统流量的增大,出现了应用集群。在 Redis 中为了保证 Redis 的高可用也为 Redis 搭建了集群对数据进行分槽存放。在 Mysql数据库要存储的量达到一个很高的地步的时候,我们会对...
  • 一致性哈希算法
  • 在web架构中,分布式是个常见的架构设计。尤其是大家比较熟悉的Memcached,或者其他cache产品常常被设计成分布式集群。...一致性哈希,简单的说在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 ke...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 137,003
精华内容 54,801
关键字:

哈希和一致性哈希