一致性哈希指南

作者: Juan Pablo Carzolio

译者: java达人

来源: https://www.toptal.com/big-data/consistent-hashing

近年来,随着云计算、大数据等概念的出现,分布式系统得到了普及和应用。

其中一种类型的系统是分布式缓存,它支持许多高流量动态网站和web应用程序,通常由一种特定的分布式哈希实现,一种一致性哈希算法。

什么是一致性哈希?它背后的动机是什么?你为什么要关注它?

在本文中,我将首先回顾哈希的一般概念及其用途,然后描述分布式哈希及其所涉及的问题,引出了我们的主题。

什么是哈希

哈希是什么意思?韦氏词典将“hash”一词定义为“肉丁和土豆混在一起烧成棕色”,而动词则是“将东西(如肉和土豆)切成碎片”。所以,撇开烹饪细节不谈,hash大致的意思是“切碎和混合”—这正是这个技术术语的来源。

哈希函数是将一段数据(常是描述某种类型的对象,通常是任意大小的)映射到另一段数据(通常是一个整数,称为哈希码,或者简称哈希)。

例如,一些哈希函数设计用于哈希字符串,输出范围为0 .. 100的数、可以将字符串 Hello 映射到数字57, Hasta la vista, baby映射到数字 33,将其他任何可能的字符串映射到该范围内的某个数字。由于可能的输入比输出多得多,任何给定的数字都会有许多不同的字符串映射到它,这就是所谓的碰撞现象。好的哈希函数应该以某种方式“切碎并混合”输入的数据,以便不同输入值的输出尽可能均匀地分布在输出值范围内。

哈希函数有许多用途,对于每种用途,可能需要不同的属性。有一种叫加密哈希函数,它必须严格满足一组属性,用于安全目的,如密码保护、消息的完整性检查和指纹识别,数据损坏检测等,这些超出了本文讨论范围。

非加密哈希函数也有几种用途,最常见的是它们在哈希表中的使用,这是我们关心的问题,我们将更详细地进行探讨。

介绍Hash Table(Hash Map)

假设我们需要保存某个俱乐部所有成员的列表,同时能够搜索任意特定的成员。我们可以通过将列表保存在数组(或链表)中来处理它,并执行搜索,迭代元素直到找到所需元素(例如,我们可能根据它们的名称进行搜索)。在最坏的情况下,这意味着检查所有成员(如果我们正在搜索的是最后一个成员,或者这个成员根本不存在),或者检索一半(这是平均情况)。在复杂度理论中,搜索的复杂度为O(n),对于一个小列表,它的速度相当快,但是它会随着成员数量的增加而变得越来越慢。

如何改进呢?假设所有这些俱乐部成员都有一个成员ID,它恰好是一个反映其加入俱乐部顺序序列号。

假设可以接受按 ID进行搜索,我们可以将所有成员放入一个数组中,其索引与ID匹配(例如,ID=10的成员位于数组索引10处)。这将允许我们直接访问每个成员,根本不需要搜索。这将是非常高效的,事实上,越是高效,对应于越小的复杂度,O(1)也被称为常数时间。

但是,必须承认,俱乐部成员ID场景是有些人为的。如果id很大、非顺序的或是随机数,或者如果不能接受按ID进行搜索,而需要按名称(或其他字段)进行搜索,怎么办?需要保持我们的快速直接访问(或其他类似的访问),同时能够处理任意数据集和较少限制的搜索条件。

这就是哈希函数发挥作用的地方。一个合适的哈希函数可以将任意的数据映射到一个整数,这个整数将扮演类似于我们的俱乐部成员ID的角色,尽管有一些重要的区别。

首先,一个好的哈希函数通常有一个宽泛的输出范围(通常是32位或64位integer范围),所以为所有可能的索引构建一个数组要么不切实际,要么根本不可能,而且会浪费大量内存。为了克服这个问题,我们可以有一个合理大小的数组(比方说,只需要两倍于我们预期存储的元素的数量),并执行Hash取模操作来获得数组索引。索引为index = hash(object) mod N,其中N是数组的大小。

其次,对象哈希不是唯一的(除非我们使用固定的数据集和自定义的完美哈希函数,但我们不会在这里讨论这个)。它们会有冲突(取模操作进一步增加冲突),因此简单用索引直接访问将无法工作。有几种方法可以解决这个问题,一种典型的方法是将一个列表(通常称为bucket)附加到每个数组索引,以保存共享同一个索引的所有对象。

因此,我们有一个大小为N的数组,每个条目都指向一个对象桶。要添加一个新对象,我们需要计算它的hash modulo N,并检查结果索引处的bucket,如果还没有对象,则添加该对象。要搜索一个对象,我们也要做同样的事情,即查看桶中是否有对象。这样的结构称为哈希表,尽管桶内的搜索是线性的,但是哈希表大小适当的话每个桶应该有相当少的对象,从而产生几乎是常数时间的访问(平均复杂度为O(N/k,其中k是桶的数量)。

对于复杂对象,哈希函数通常不计算整个对象,而是对键进行计算。在我们的club成员示例中,每个对象可能包含几个字段(比如姓名、年龄、地址、email、电话),但是我们可以选择email作为键,这样哈希函数只应用于email。事实上,键不需要是对象的一部分;通常存储键/值对时,键是相对较短的字符串,而值可以是任意数据块。在这种情况下,哈希表或hash map作为字典使用,这也是一些高级语言创建对象或关联数组的方式。

扩展:分布式哈希

既然我们已经讨论了哈希,现在我们准备研究分布式哈希。

在某些情况下,可能必须或者希望将哈希表拆分为由不同服务器承载的多个部分。这样做的主要动机之一是绕过只使用单台计算机的内存限制,允许构造任意大的哈希表(给定足够的服务器)

在这种情况下,对象(及其key)分布在多个服务器中,因此称为分布式哈希

这方面的一个典型用例是内存缓存(如Memcached)的实现。

这种配置由一个缓存服务器池组成,这些缓存服务器托管许多键/值对,用于提供对原来在其他地方存储(或计算)的数据的快速访问。例如,为了减少对数据库服务器的负载,同时提高性能,应用程序可以设计先从缓存服务器中获取数据,只有当数据不存在时—这种情况称为缓存未命中—才请求数据库,运行相关查询并使用适当的键缓存结果,以便下次需要时可以找到它。

那么,分布式是如何实现的呢?使用什么标准来确定要在哪些服务器上驻留哪些key?

最简单的方法根据服务器数量哈希取模。即 server = hash(key) mod N,其中 N是池的大小。要存储或检索密钥,客户机首先计算哈希,使用modulo N操作,并使用生成的索引与合适的服务器关联(可能通过使用IP地址查找表)。注意,用于key分发的哈希函数在所有客户端上必须都是相同的,但是缓存服务器内部使用的哈希函数不一定相同。

让我们看一个例子。假设我们有三个服务器,A、B和C,我们有一些拥有哈希值的字符串键:

KEY

HASH

HASH mod 3

"john"

1633428562

2

"bill"

7594634739

0

"jane"

5000799124

1

"steve"

9787173343

0

"kate"

3421657995

2

客户端想要检索key为 john的值。它 hash modulo 3是2,所以它必须与服务器C关联。key不存在,所以客户端从数据源获取数据并添加。服务器池结果如下:

A

B

C

"john"

接下来,另一个客户端(或同一客户端)希望检索key 为bill的值。它hash modulo 3结果是0,所以它必须与服务器A关联。key未找到,所以客户端从数据源获取数据并添加。服务器池结果如下:

A

B

C

"bill"

"john"

在添加了其余的key之后,服务器池结果如下:

A

B

C

"bill"

"jane"

"john"

"steve"

"kate"

Rehash问题

这种分配方案简单、直观、工作良好,但是如果服务器的数量发生变化就不行了。如果其中一个服务器崩溃或变得不可用,会发生什么?当然需要重新分发key来弥补损失的服务器。如果将一台或多台新服务器添加到池中,情况也是如此;需要重新分发key以包含新服务器。任何分发方案都会有这种问题,但是我们这种简单的取模分发方案的问题是,当服务器的数量发生变化时,大多数hashes modulo N 结果将发生变化,因此大多数key将需要移动到不同的服务器。因此,即使删除或添加了单个服务器,也可能需要将所有key rehash到不同的服务器中。

从我们之前的例子中,如果我们删除了服务器C,我们将不得不根据 hash modulo 2而不是hash modulo 3对所有key进行rehash,key的新位置如下:

KEY

HASH

HASH mod 2

"john"

1633428562

0

"bill"

7594634739

1

"jane"

5000799124

0

"steve"

9787173343

1

"kate"

3421657995

1

A

B

"john"

"bill"

"jane"

"steve"

"kate"

注意,所有key位置都发生了变化,不仅仅是在服务器 C的key的位置。

在我们前面提到的典型用例(缓存)中,这意味着,key突然都找不到了,因为它们还没有被存放在新的位置。

因此,大多数查询将不会命中,并且可能需要重新从数据源检索原始数据来rehash,进而给源服务器(通常是数据库)带来沉重的负载。这可能会严重降低性能,导致源服务器崩溃。

解决方案:一致性哈希

那么,如何解决这个问题呢?我们需要一个不直接依赖于服务器数量的分发方案,这样,在添加或删除服务器时,需要重新定位的key的数量就可以最小化。有一个这样的方案—一个聪明的,却非常简单的方案—被称为一致性哈希,它首次由麻省理工学院的Karger等人在1997年的一篇学术论文中提出(根据维基百科)。

一致性哈希是一种分布式哈希方案,它在一个抽象的圆或哈希环上为服务器或对象分配一个位置,它的操作不依赖于分布式哈希表中服务器或对象的数量。这允许服务器和对象在不影响整个系统的情况下进行伸缩。

假设我们将哈希输出范围映射到圆环的边缘。这意味着最小散列值零将对应于零角,其最大可能值(我们称为INT_MAX的大整数)对应于2?(或360度)的角,所有其他的哈希值线性地介于两者之间。我们可以取出一个key值,计算它的哈希值,然后找出它在圆环的位置。假设 INT_MAX 为1010(举例子),我们前面的例子中的key应该是这样的:

KEY

HASH

ANGLE (DEG)

"john"

1633428562

58.8

"bill"

7594634739

273.4

"jane"

5000799124

180

"steve"

9787173343

352.3

"kate"

3421657995

123.2

现在假设我们将服务器也放置在圆环,通过伪随机方式分配它们所在的角度。这应该以一种可重复的方式完成(或者至少让所有客户端都在服务器的角度问题上达成一致)。一种方便的方法是根据服务器名称取哈希(或IP地址,或某些ID)—就像我们对任意其他key所做的操作那样—来找出它的角度。

在我们的例子中,也许是这样的:

KEY

HASH

ANGLE (DEG)

"john"

1633428562

58.8

"bill"

7594634739

273.4

"jane"

5000799124

180

"steve"

9787173343

352.3

"kate"

3421657995

123.2

"A"

5572014558

200.6

"B"

8077113362

290.8

"C"

2269549488

81.7

因为我们的对象和服务器都有key放在在同一个环,我们可以定义一个简单的规则将前者与后者关联:每个对象key将归属于在逆时针方向上(或顺时针,取决于约定)key最接近的服务器。换句话说,要找到向哪台服务器获取key,我们需要在环上定位key,并沿着角度升序方向移动,直到找到那台服务器为止。

示例如下:

KEY

HASH

ANGLE (DEG)

"john"

1633428562

58.7

"C"

2269549488

81.7

"kate"

3421657995

123.1

"jane"

5000799124

180

"A"

5572014557

200.5

"bill"

7594634739

273.4

"B"

8077113361

290.7

"steve"

787173343

352.3

KEY

HASH

ANGLE (DEG)

LABEL

SERVER

"john"

1632929716

58.7

"C"

C

"kate"

3421831276

123.1

"A"

A

"jane"

5000648311

180

"A"

A

"bill"

7594873884

273.4

"B"

B

"steve"

9786437450

352.3

"C"

C

从编程的角度来看,我们要做的是保持服务器值的排序列表(可以是任何真正间隔的角度或数字),遍历这个列表(或使用二分搜索),找到大于或等于key的第一个服务器值。如果没有找到这样的值,我们需要从列表中提取第一个值。

为了确保对象key在服务器之间均匀分布,我们需要应用一个简单的技巧:为每个服务器分配多个标签(角度),而不是一个。所以我们不用标签 A, B,C,我们可以用A0 .. A9, B0 .. B9和C0 .. C9, 所有的都沿着圆环散布。增加的标签(服务器key)数量,称为权重,它根据具体情况(甚至可能对每个服务器来说是不同的)来调整每台服务器上key结束的概率。例如,如果服务器B的性能是其他服务器的两倍,那么它可以被分配两倍的标签,这样它将持有两倍的对象(平均而言)。

在我们的例子中,我们假设所有3个服务器的权值都是10(这对于3个服务器很有效,10到50个服务器时,权值在100到500之间会更好,更大的池可能需要更高的权值):

KEY

HASH

ANGLE (DEG)

"C6"

408965526

14.7

"A1"

473914830

17

"A2"

548798874

19.7

"A3"

1466730567

52.8

"C4"

1493080938

53.7

"john"

1633428562

58.7

"B2"

1808009038

65

"C0"

1982701318

71.3

"B3"

2058758486

74.1

"A7"

2162578920

77.8

"B4"

2660265921

95.7

"C9"

3359725419

120.9

"kate"

3421657995

123.1

"A5"

3434972143

123.6

"C1"

3672205973

132.1

"C8"

3750588567

135

"B0"

4049028775

145.7

"B8"

4755525684

171.1

"A9"

4769549830

171.7

"jane"

5000799124

180

"C7"

5014097839

180.5

"B1"

5444659173

196

"A6"

6210502707

223.5

"A0"

6511384141

234.4

"B9"

7292819872

262.5

"C3"

7330467663

263.8

"C5"

7502566333

270

"bill"

7594634739

273.4

"A4"

8047401090

289.7

"C2"

8605012288

309.7

"A8"

8997397092

323.9

"B7"

9038880553

325.3

"B5"

9368225254

337.2

"B6"

9379713761

337.6

"steve"

9787173343

352.3

KEY

HASH

ANGLE (DEG)

LABEL

SERVER

"john"

1632929716

58.7

"B2"

B

"kate"

3421831276

123.1

"A5"

A

"jane"

5000648311

180

"C7"

C

"bill"

7594873884

273.4

"A4"

A

"steve"

9786437450

352.3

"C6"

C

那么,这种使用环的方法有什么好处呢?假设服务器C被删除。为了说明这一点,我们必须删除环上标签C0 .. C9。这将导致先前与被删除标签相邻的对象key,现在被随机标记为Ax 和 Bx,并被重新分配到服务器 A和 B。

但是那些原本属于 A和B的key怎么办呢?没有什么变化!这就是它的美妙之处:没有Cx标签,并不影响这些key。因此,删除一个服务器会导致它的对象key被随机地重新分配给其他服务器,而其他key则保持不变

KEY

HASH

ANGLE (DEG)

"A1"

473914830

17

"A2"

548798874

19.7

"A3"

1466730567

52.8

"john"

1633428562

58.7

"B2"

1808009038

65

"B3"

2058758486

74.1

"A7"

2162578920

77.8

"B4"

2660265921

95.7

"kate"

3421657995

123.1

"A5"

3434972143

123.6

"B0"

4049028775

145.7

"B8"

4755525684

171.1

"A9"

4769549830

171.7

"jane"

5000799124

180

"B1"

5444659173

196

"A6"

6210502707

223.5

"A0"

6511384141

234.4

"B9"

7292819872

262.5

"bill"

7594634739

273.4

"A4"

8047401090

289.7

"A8"

8997397092

323.9

"B7"

9038880553

325.3

"B5"

9368225254

337.2

"B6"

9379713761

337.6

"steve"

9787173343

352.3

KEY

HASH

ANGLE (DEG)

LABEL

SERVER

"john"

1632929716

58.7

"B2"

B

"kate"

3421831276

123.1

"A5"

A

"jane"

5000648311

180

"B1"

B

"bill"

7594873884

273.4

"A4"

A

"steve"

9786437450

352.3

"A1"

A

如果不删除服务器,而是添加一个服务器,也会发生类似的情况。如果我们想将服务器D添加到我们的示例中(例如,作为对C的替换),我们需要添加标签D0 .. D9。其结果是,大约三分之一的现有key(都属于A或B)将被重新分配给D,其余的key将保持不变:

KEY

HASH

ANGLE (DEG)

"D2"

439890723

15.8

"A1"

473914830

17

"A2"

548798874

19.7

"D8"

796709216

28.6

"D1"

1008580939

36.3

"A3"

1466730567

52.8

"D5"

1587548309

257.1

"john"

1633428562

58.7

"B2"

1808009038

65

"B3"

2058758486

74.1

"A7"

2162578920

77.8

"B4"

2660265921

95.7

"D4"

2909395217

104.7

"kate"

3421657995

123.1

"A5"

3434972143

123.6

"D7"

3567129743

128.4

"B0"

4049028775

145.7

"B8"

4755525684

171.1

"A9"

4769549830

171.7

"jane"

5000799124

180

"B1"

5444659173

196

"D6"

5703092354

205.3

"A6"

6210502707

223.5

"A0"

6511384141

234.4

"B9"

7292819872

262.5

"bill"

7594634739

273.4

"A4"

8047401090

289.7

"D0"

8272587142

297.8

"A8"

8997397092

323.9

"B7"

9038880553

325.3

"D3"

9048608874

325.7

"D9"

9314459653

335.3

"B5"

9368225254

337.2

"B6"

9379713761

337.6

"steve"

9787173343

352.3

KEY

HASH

ANGLE (DEG)

LABEL

SERVER

"john"

1632929716

58.7

"B2"

B

"kate"

3421831276

123.1

"A5"

A

"jane"

5000648311

180

"B1"

B

"bill"

7594873884

273.4

"A4"

A

"steve"

9786437450

352.3

"D2"

D

这就是一致性哈希解决rehash问题的方法。

通常,当k是key的数量,N是服务器的数量(更具体地说,是初始和最终服务器数量的最大值)时,只需要重新映射k/N个key。

后续

我们注意到,当使用分布式缓存优化性能时,缓存服务器的数量可能会发生变化(原因可能是服务器崩溃,或者需要添加或删除服务器来增加或减少总体容量)。通过使用一致性哈希来在服务器之间分发key,我们可以对此放心,如果发生这种情况,rehash的key数量(同时对数据源服务器的影响)将被最小化,从而防止可能的停机或性能问题

几个像Memcached和Redis系统的客户端,包含对一致性哈希开箱即用的支持。

或者,您可以使用您选择的语言自己实现算法,一旦概念被理解,这应该是比较容易的。

如果你对数据科学感兴趣,Toptal博客上有一些关于这方面主题的最好的文章(https://www.toptal.com/developers/blog/data-science-and-databases)

java达人

ID:drjava

(长按或扫码识别)

本文分享自微信公众号 - java达人(drjava)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券