00:00
好,同学们,我们继续接下来给大家介绍一下分布式存储思想的第二种算法,一致性哈希算法来进行我们的分区。那么通过上一讲我们都晓得底层的这个分母不是固定的,写死的,它有可能扩,有可能缩,有可能蛋机,有可能故障,那只要这个底子一变化,就会导致我们哈西渠全部数据要重新洗牌,这个呢是有一些安全隐患的。那么接下来我们进一步来看一下一致性哈希算法,那么首先它是什么?来。他那是不行了啊,九七年就有麻省理工学院提出来的,它的设计目标就是为了解决分布式缓存数据的变动和映射问题,某个机器宕机了。对吧。分母数量改变了,自然取于就不OK了,那么这样的话呢,我们之前的映射规则就会发生一些改变,那么为了解决这个问题,我们往前走一步,一致性哈希算法,来来看看它能解决些什么呢?提出一致性哈希的解决方案,目的是当服务器的个数发生变动的时候,尽量减少影响到客户端和服务器端之间的映射关系。
01:07
那么一般啊,一致性哈希算法这种呢,有三大步骤,第一个。用算法构建一个一致性哈希环啊,待会我们说啊,第二个服务器IP,那么你构建这个环了以后,相当于说。你后面按照IP的节点可以映射落到这个环上面。然后这个key再落到服务器的产生一个落键的规则,好,那么现在。不担心,一步一步给大家说。来,弟兄们,什么叫一致性哈希环啊?一致性哈希算法必然有个哈希函数,并按照算法产生一个哈希值啊,对吧?那么这个算法的所有可能哈希时,就会构成一个全量的集合,比如说你某个算法它能产生的数据从零到多少多少多少,它肯定会有一个上限,那么这些全部给它收集起来,我们这个集合就可以形成一个哈希空间,那么根据我们的算法,它的大小是零到二的32次方减一。
02:07
那么这是一个线性的空间,但是在算法当中,我们通过适当的逻辑控制将它首尾相连,这样就让它的逻辑上形成了一个环形空间,那什么意思呢?就说现在。以前你的区间范围。比如说这就是零到我们的二的32次方,对吧,那么。完了以后。现在。这个呢,就是个全量集合。没问题吧,那么现在呢,我们把这圈呢,给它估起来,让它呢,从一个数组一样的从零到这个最大值,让它形成一个环。OK,那么这个是第一步,那么为什么要这么做?待会我们聊就是减轻底层机器台数变动以后我们的映射和分配规则,那么来,同学们走吧。我们按照我们也是按照使用取值这个方法啊,我们上一个算法的话介绍的节点的取值是对节点服务器的数量进行取值,对吧?比如说三台就是三,六台就是六而一致性,二而一致性,哈希的算法是对二的32次方。
03:13
学,那么简单来说就是一致性哈算法将整个哈西式的空间组织成了一个虚拟的圆环。从躺平到。圆圈,OK,再次强调这句话啊。以前我们是对机器的数量,这个机器数量是会变化的,可能三台,可能六台,可能八台,可能十台,但是一致性还有算法底子二的32次方,那么这样的算法来了以后会变成一个全量级。那么现在。我们某个哈希值,它的空间呢,就是从零到这个,那么整个哈希环就会像这样。就像杨哥画的。从这。估成个圈,那么这个时候你所有的集合是不是都在这个圈圈里面一匡天下?一览无鱼,一网打尽,那么圆滑的正上方的点就代表示零,右边第一个就是一,就跟一个钟一样的零,1234567,一直到二的32次方减去,也就是说从零点左侧的第一点代表是吗?二的32次方减一这个最大值。
04:13
这个是最小零转一圈,最大的就是它,那么在零和二的三次方减一的这个零点中方向重合,我们就把这个由二的32次方个点组成的圆环就称为哈西环,那么现在就是我不管你底子怎么变,反正我取余的固定了二的32次方。好,这是第一步,我们构建了一个环,换句话说什么你把它当做一口锅。你不管怎么映射,你下面怎么变,再大的饼大不过烙它的锅,对吧,都在这个全量级的范围以内了,那么好,这第一步,第二步服务器IP节点的映射,那么你有这个环得落到哪吧,对吧,那么所以说。我们在这儿呢,走起来。将集群中的各个IP节点映射到环上的某一个位置,那么就是节点映射来吧。当各个服务器使用我们的一种哈希算法,会得到一个哈希值,那么具体可以选择服务器的IP或者主机啊,作为你是按照IP还是主机名作为关键字进行哈希,那么这样每台机器都能确定在哈希环上的落点位置,假设啊,四个节点abcd。
05:17
那么现在。Abcd经过,我们按照IP地址进行哈希计算,那么使用IP地址哈希的空间是这样的落点。假设节点A通过这个算法得到一个值,那么OK,它呢,就在这儿,又得到一个值,在这儿,在这儿,在这儿,那么是不是像一块手表,一个钟一样的,反正每一个节点一定所有,一天24小时,无非就是转一圈,是转两圈,都在这个圆盘上,OK,那么他们的什么节点映射就在这个环上面?好,那么下面key落到服务器的落建规则是这样的。当我们需要存储一个KB键值段,我们首先计算出K的哈希池,我们刚才已经看到了啊,那些机器的节点已经在这了,明白了吧?那么现在哈希拿来KABCD,四台机器都落在这个二的32次方减一的这个环上面了,那么机器落了以后就是节点1234ABCD,那么现在来个K,比方说K1,将这个K使用一个哈希来算一下,那么由于它跟我们落点机器那个哈希函数就是这个是一样的,那么算出的哈希值必然也会落到这个环上面,那么最后我们得到的结论是从此环。
06:26
顺时针往前走。第一台遇到的机器就是他应该落点的位置,首次出狱就是他的真爱。那么这个时候请大家看。假设节点A是某个机器通过这个哈希我落到这儿,那么现在这个K。来了,它的数据叫object a,假设这个K就叫A,那么现在通过一样的这个哈希算法,请看。这个KA通过这个哈希函数,我落到皇上的这儿干嘛?沿此位置顺时针走遇到的第一个那么好说明什么?我这个K落到还的这往前顺时针走,碰到的第一个就是我的真爱结no的A就是落在一号服务器上面存进去,那么这样的话呢,ABCD4个K。
07:15
四个数据对象经过相同的哈希计算方法以后,在环空间上面的位置一下。根据一致性哈希算法,A会被定位到。Note ABB会定位到note bc往前走,顺时针会定位到CB,落到这儿,往前顺针走放到D,那么这样是不是就让他们有序的落到了四台服务器上面,那么我们的T就有着落了,好所以说这个就是我们的什么三个步骤,那么。一致性哈,喜欢。映射。最后是落箭规则,OK,那么来同学们来看一下。一致性哈希算法它的优点和缺点。比起上面这个好在哪?又会产生什么问题,我们要进一步的优化,首先优点啊。
08:03
一致性哈希算法,它解决了哈希起余的容错性和扩张性的问题。大家请看。现在啊,根据我们的落点啊,就是落下来以后往前顺时针往前走,遇到的第一台就是我的真爱,我就存进去,那么现在假设我们出现这么一个问题,假设。C not c这个节点。蛋鸡了,最下面这个啊。那么此时可以看到。我们当然希望你淡季以后就是所谓的什么。谁的锅谁背,你C宕机了,别影响abd这三台那么好,现在呢,只有。我们那就不会受到影响对吧,Abd这三台,那么这他死了。假设我这个K,这个C落到这儿,如果你以前活着,我应该落到C这,可是你现在已经挂了,我应该怎么办?那么同学们,我继续往前走。已经没有C了,我再继续往前顺时针走,遇到的我的什么?
09:03
第一个遇到的服务器是D,那么所以说C对象被重新定位到D,那么一般的我们在一致性算法中,如果一台服务器不可用了,则受到影响的数据仅仅是此服务器到其环空间中的前一台,就是说C宕机了。假设这走不通这一台受影响和沿着什么逆时针方向行走,遇到的第一台服务器就是只会假设我这台死了。只会影响这一段,我往前走C死了,顺时针是不是这儿,那么我的逆时针方向后面是不是B,那么也就是说BC这段就存不进去了,为什么?因为这个区间C没有了,那么是不是从BC变成了BD这个区间了,能理解,所以说同学们请看,只会影响这一段区间上的数据,其他是不会受到影响的,所以说简单来说就是。C挂了,受影响的只是BC之间的数据,说C,假设我落到这C挂了,往前走是不是C,往后逆时针方向是不是B,所以说只会影响BC这一段,其他不会影响,那么由于已经没有C了,按照我们的一致性哈希算法的规矩,遇到C是吧,干嘛?此处不留爷自有留爷处,我往前走还是顺时针,那么我遇到的第一个就是不是就变成D了,那么所以说这些数据会转移,移动到D上面存储,那么这个就是它第一个优点,有容错性,第二个干嘛,扩张性。
10:30
那么我们说过了。现在ABCD4塔,那假设你扩容要变成。六台呢,八台呢,十台呢?那么这个数据又怎么扩呢?那么来吧,弟兄们请看,假设数据量增加了啊,按照我们这个图需要增加一台节点,比如说第五台机器。XX的位置刚好根据我们的哈希算法算了以后就在AB之间,我这个机器就会落到这儿。那么。那么受到影响的也就是A到XOK,那么这个时候我们需要把A到X录取,重新录到X之上就OK了,不会导致哈希取决全部重新洗牌,听懂了吗?那比如说啊,兄弟们啊,我这又加一台机器了,以前是什么我落到这一段?
11:15
怎么着,我可能往前存是存到B,那么现在又多了一台X,那不就是什么我呢,直接遇到的我第一台干嘛落到X上面就完活明白了吗?那么X加到这,那么以前遇到的第一个就从B变成了我们的什么X好,那么这个呢,就是一致性,哈希算法的扩张性,貌似到这儿都挺爽,那么它的缺点是什么呢?有一个他难以解决。一致性还算法的数据倾斜问题,那么来为什么说小厂用这个就够了,小厂不用上这个什么意思啊,你的数据量没那么大,没到那么大的话,你不用上那么十多台,对吧,又不是像京东这种体量,美团这种体量,那么对于一致性哈希算法。如果你机器比较少,不要用这种算法,理由你很难解决。
12:03
数据倾斜的问题。那么弟兄们请看。是这样的。如果节点太少,非常因为非常容易会导致节点分布不均匀,造成数据倾斜,那比如说兄弟们AB2个节点好落到这儿,那么假设某种算法它落到这B往前走,顺时针遇到的第一个我存到B,但是假设啊,这一段以外的都是往前走遇到的是不是都只会存到A呀?那么被缓存的对象大部分货集中在。一台机器上面,那么这样就会导致A特别重,B特别轻,你看我如果落到这顺时针往前走,遇到的第一台我就存进去,那么这儿就是A,落到这儿也是A,只有落到AB之间的会存到B,那么这样会导致这两个头重脚轻,非常的不稳定,所以说这个就是一致,一致性哈希算法。它的优点和缺点相比于哈西取鱼增强了容错性和扩张性好。那么总结一下。
13:03
那么为了在节点数目发生改变时尽可能少的迁移数据。我们将所有节点。按首尾相接放在一个哈希环上面,那么每个T在计算哈希后会顺时针找到临近的存储节点,就第一次啊。放进去,那么当有节点加入和退出时,仅仅影响该节点在哈希环上顺时针节点相邻的这种后续两个节点,OK,前面我们都说过,那么优点加入和删除节点只影响哈希环中顺时针方向的相邻节点,对其他节点无感,缺点分布和节点的位置有关系啊,如果。不是太均匀的话,会达到那种头重脚轻的感觉,那么所以说兄弟们在这儿如果只有两台机器什么的,就不要玩什么一致性哈希算法,OK,好,那么这个理论知识主要就是这三步哈希环。节点映射和落建规则。
我来说两句