CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》

这篇具有很好参考价值的文章主要介绍了CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

CHAPTER 5: DESIGN CONSISTENT HASHING

为了实现水平扩展,有效且均匀地分发请求/数据是很重要的在服务器上。一致散列是实现这一目标的常用技术。但首先,让我们深入了解一下这个问题。

重组问题

如果您有n个缓存服务器,那么平衡负载的常用方法是使用以下散列方法:
serverIndex = hash(key) % N,其中N为服务器池的大小。让我们用一个例子来说明它是如何工作的。如表table5-1所示,我们有4台服务器8串键和它们的哈希值。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
为了获取存储键的服务器,我们执行模块化操作f(key) % 4。为实例,hash(key0) % 4 = 1表示客户端必须联系服务器1才能获取缓存的数据。根据table5-1,密钥分配如figure5-1所示。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
当服务器池的大小和数据分布固定时,这种方法在偶数情况下工作得很好。但是,当添加新服务器或移除现有服务器时,就会出现问题。例如,如果服务器1脱机,则服务器池的大小变为3。使用同样的哈希函数,我们得到一个键相同的哈希值。但是应用模块化Operation为我们提供了不同的服务器索引,因为服务器的数量减少了1。我们通过应用hash % 3得到如table5-2所示的结果:
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
根据table5-2,新的密钥分布如figure5-2所示。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
如figure5-2所示,大多数密钥都是重新分发的,而不仅仅是最初存储在脱机服务器(服务器1)。这意味着当服务器1脱机时,大多数缓存客户机也会脱机连接到错误的服务器以获取数据。这将导致大量缓存未命中。一致的散列是缓解此问题的有效技术。

一致性哈希

引用自维基百科:“一致性哈希是一种特殊的哈希,当a重新调整哈希表大小并使用一致哈希,只需要重新映射k/n个键平均,k是键的个数,n是槽的个数。相反,在大多数情况下在传统的哈希表中,数组槽数的变化会导致几乎所有键都被替换贴图[1]”。

哈希空间和哈希环

现在我们了解了一致哈希的定义,让我们来看看它是如何工作的。假设使用SHA-1作为哈希函数f,哈希函数的输出范围为:x0, x1, x2,在密码学中,SHA-1的哈希空间从0到2^160 -1。也就是x0对应于0,xn对应于2^160 - 1,其他哈希值都在中间在0到2^160 - 1之间。哈希空间如figure5-3所示。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
将两端集合,得到一个哈希环,如图figure5-4所示:
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》

散列服务器

使用相同的哈希函数f,我们根据服务器IP或名称将服务器映射到环上。如figure5-5所示,哈希环上映射了4个服务器。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》

散列键

值得一提的是,这里使用的哈希函数与“the”中的哈希函数不同重新散列问题”,并且没有模块化操作。如figure5-6所示,4个缓存键(key0、key1、key2和key3)被散列到散列环上
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》要确定键存储在哪个服务器上,我们从键的位置顺时针进行直到找到服务器为止。流程如figure5-7所示。顺时针方向,key0被存储在服务器0上;Key1存储在服务器1上;Key2存储在服务器2上,key3存储在服务器上3.
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》

添加服务器

使用上面描述的逻辑,添加一个新服务器只需要重新分配一个键的分数。
在figure5-8中,新增服务器4后,只需要重新分配key0。K1 k2,还有K3仍然在相同的服务器上。让我们仔细看看其中的逻辑。在添加服务器4之前,Key0存储在服务器0上。现在,key0将存储在服务器4上,因为服务器4是第一个从key0在环上的位置顺时针移动所遇到的服务器。其他键是不基于一致性哈希算法重新分发。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》

移除服务器

当服务器被删除时,只有一小部分密钥需要重新分配散列。在图5-9中,当服务器1被移除时,只有key1需要重新映射到服务器2。其余的钥匙不受影响。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》

基本方法有两个问题

一致性哈希算法是由Karger等人在MIT[1]提出的。基本步骤是:

  • 使用统一分布的哈希函数将服务器和密钥映射到环上。
  • 要找出一个键映射到哪个服务器,从键位置顺时针走,直到找到环上的第一个服务器。

这种方法存在两个问题。首先,不可能保持相同的规模考虑到可以添加或删除服务器的所有服务器在环上的分区。一个分区是相邻服务器之间的哈希空间。有可能是分配给每个服务器的环上的分区要么非常小,要么相当大。在figure5-10中,如果s1被删除后,s2的分区(用双向箭头突出显示)是so0的两倍大s3的分区。CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》其次,环上可能存在不均匀的密钥分布。例如,如果服务器映射到如figure5-11所示的位置,大部分密钥存储在服务器2上。但是,服务器1和服务器3没有数据。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
使用一种称为虚拟节点或副本的技术来解决这些问题。

虚拟节点

虚拟节点是指实节点,每台服务器由多个虚拟节点表示在环上。在figure5-12中,服务器0和服务器1各有3个虚拟节点。3是任意选择;而在现实世界的系统中,虚拟节点的数量要大得多。我们不用s0,而是用s0_0、s0_1和s0_2表示环上的服务器0。同样的,S1_0、s1_1和s1_2代表环上的服务器1。对于虚拟节点,每个服务器都是负责多个分区。标签为50的分区(边)由服务器0管理。另一方面,标签为s1的分区由服务器1管理。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
要查找密钥存储在哪个服务器上,我们从密钥的位置顺时针查找环路上遇到的第一个虚拟节点。在figure5-13中,查看存储的服务器k0On,我们从k0的位置顺时针走,找到虚拟节点s1_1,它指向服务器1。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》随着虚拟节点数量的增加,密钥的分布变得更加平衡。这是因为虚拟节点越多,标准差越小,导致均衡的数据分布。标准偏差衡量的是数据的分布情况。的在线研究b[2]进行的一项实验结果表明,有一个或两个100个虚拟节点,标准差在5%(200个虚拟节点)~ 10%之间(100个虚拟节点)的平均值。标准差会变小,当我们增加虚拟节点数。但是,需要更多的空间来存储有关虚拟节点的数据。这是一种权衡,我们可以调整虚拟节点的数量以适应我们的系统需求。

查找受影响的键

当添加或删除服务器时,需要重新分发一小部分数据。我们怎么能找到受影响的范围来重新分配键?如figure5-14所示,服务器4加入到环中。受影响的范围从s4 (new添加节点)并沿环逆时针移动,直到找到服务器(s3)。因此,键
位于s3和s4之间的需要重新分配到s4。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》
如figure5-15所示,当一台服务器(s1)被移除时,影响范围从s1开始(移除的节点)并沿环逆时针移动,直到找到服务器(s0)。因此,位于s0和s1之间的键必须重新分配到s2。
CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》

总结

在本章中,我们对一致性哈希进行了深入的讨论,包括为什么要这样做需要和它的工作原理。一致性哈希的好处包括:

  • 当服务器被添加或删除时,最小化的密钥将被重新分配。
  • 容易横向扩展,因为数据分布更均匀。
  • 缓解热点密钥问题。对特定分片的过度访问可能导致服务器故障过载。想象一下,凯蒂·佩里、贾斯汀·比伯和Lady Gaga的数据都出现在同样的碎片。一致散列通过更多地分布数据来帮助缓解这个问题均匀。

一致哈希被广泛应用于现实世界的系统中,包括一些值得注意的系统:

  • Amazon Dynamo数据库[3]的分区组件
  • Apache Cassandra[4]的跨集群数据分区
  • 不和聊天应用[5]
  • Akamai内容分发网络b[6]
  • 磁悬浮网络负载平衡器[7]
    恭喜你走了这么远!现在给自己点鼓励吧。好工作!

参考资料 Reference materials

[1] Consistent hashing: https://en.wikipedia.org/wiki/Consistent_hashing
[2] Consistent Hashing:
https://tom-e-white.com/2007/11/consistent-hashing.html
[3] Dynamo: Amazon’s Highly Available Key-value Store:
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
[4] Cassandra - A Decentralized Structured Storage System:
http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF
[5] How Discord Scaled Elixir to 5,000,000 Concurrent Users:
https://blog.discord.com/scaling-elixir-f9b8e1e7c29b
[6] CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent
Hashing: http://theory.stanford.edu/~tim/s16/l/l1.pdf
[7] Maglev: A Fast and Reliable Software Network Load Balancer:
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf文章来源地址https://www.toymoban.com/news/detail-422818.html

到了这里,关于CHAPTER 5: 《DESIGN CONSISTENT HASHING》 第5章 《设计一致的哈希》的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【漏洞复现】CVE-2004-2761:使用弱哈希算法签名的 SSL 证书(SSL Certificate Signed Using Weak Hashing Algorithm)

    概要:本次复现是针对编号为CVE-2004-2761的漏洞,由于条件有限,本次复现通过创建自签名证书进行操作。 问题描述:证书链中的 SSL 证书使用弱哈希算法进行签名。 本次复现环境在Linux平台下使用Nginx进行环境的搭建,通过 Openssl 组件生成自签名证书,并在 Nginx 配置文件中进

    2024年02月10日
    浏览(41)
  • 一致性哈希(哈希环)解决数据分布问题

    哈希算法是程序开发过程中最广泛接触到的的算法之一,典型的应用有安全加密、数据校验、唯一标识、散列函数、负载均衡、数据分片、分布式存储。前些天遇到用一致性哈希(哈希环)的场景,不过我细想一下,对这个知识点好像了解过,但是又没太深印象,说不出具体

    2024年02月04日
    浏览(53)
  • 【分布式】一致性哈希和哈希槽

    当我们拥有了多台存储服务器之后,现在有多个key,希望可以将这些个key均匀的缓存到这些服务器上,可以使用哪些方案呢? 1.1 直接哈希取模 这是一种最容易想到的方法,使用取模算法hash(key)% N,对key进行hash运算后取模,N是机器的数量。key进行hash后的结果对3取模,得

    2024年02月03日
    浏览(47)
  • 区块链:哈希算法与一致性哈希算法

    本篇主要介绍区块链中常用到的哈希算法。 1 哈希算法 1.1 定义及特性   哈希算法是指通过哈希函数(Hash Function)对任意长度的输入数据(比如文件、消息、数字等)进行转换,生成一个固定长度的哈希值(Hash Value)的过程。   在区块链中,哈希算法常用于区块验证及安全性保

    2024年02月17日
    浏览(62)
  • 谈谈一致性哈希算法

    一致性哈希算法是1997年由麻省理工的几位学者提出的用于解决分布式缓存中的热点问题。大家有没有发现,我们之前介绍的例如快排之类的算法是更早的六七十年代,此时分布式还没有发展起来, 大家往往还在提高单机性能。但是九十年代开始,逐渐需要用分布式集群来解

    2024年02月07日
    浏览(55)
  • 【负载均衡——一致性哈希算法】

    一致性哈希算法就很好地解决了分布式系统在扩容或者缩容时,发生过多的数据迁移的问题。 一致哈希算法也用了取模运算,但与哈希算法不同的是,哈希算法是对节点的数量进行取模运算,而一致 哈希算法 是对 2^32 进行取模运算,是一个固定的值。 一致性哈希要进行两步

    2024年04月10日
    浏览(53)
  • 数字逻辑Fundamentals of Digital Logic with Verilog Design | 3rd Edition Solutins Chapter 4(step by step)

    第四章 重要内容:1、多路选择器  2、采用香农展开的多路选择器综合 3、译码器  4、多路分配器  5、优先级编码器  6、代码转换器  7、算数比较电路  8、Verilog语法 纠错:4-11香农展开式最后结果应该是同或门。 Chapter 4 Chapter 4, Problem 1P Chapter 4, Problem 2P Chapter 4, Problem 3P

    2024年02月05日
    浏览(40)
  • 07. 算法之一致性哈希算法介绍

    哈希算法在程序开发中的很多地方都能看到他的身影,但是哈希有他的局限性,比如如果两个key哈希到同一个位置的时候,此时就不好处理。本节我们介绍一下常规处理方式。 哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。

    2024年02月06日
    浏览(52)
  • Python小知识 - 一致性哈希算法

    一致性哈希算法 一致性哈希算法(Consistent Hashing Algorithm)是用于解决分布式系统中节点增减比较频繁的问题。它的思想是,将数据映射到0~2^64-1的哈希空间中,并通过哈希函数对数据进行映射,计算出数据所在的节点。当节点增加或减少时,只需要重新计算数据所在的节点即

    2024年02月09日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包