本章我们将主要讨论分布式缓存的概念，描述缓存集群相对单节点缓存的优势以及如何实现一个缓存集群。

为什么我们需要集群服务

用集群来提供服务有许多优点是单节点的服务无法相比的。

首先单节点的扩展性不好。我们知道网络吞吐量和缓存容量会受到硬件的限制，对于单节点来说，这个上限就是本机硬件接口的数量;而对于集群来说它可以提供的硬件数量不受单块主板插槽数量的限制，只需要增加新的节点就可以了。

其次单节点性价比很低，一台高端设备能提供的服务往往弱于同样价钱多台低端设备组建的集群能提供的服务。

最后，集群的容错率高于单节点。一台服务器死机对于一个有 10台服务器的集群来说损失了 10%的处理能力，但是对于单节点服务来说就是损失 100%的能力。

集群根据功能可以分为高可用性集群(high availability，HA)、负载均衡集群(load balancing)、高性能计算集群(high performance clusters，HPC)以及网格计算(grid computing)。

缓存服务不涉及计算，所以缓存服务集群要求的通常是高可用性以及负载均衡。

高可用性指的是当集群中某个节点失效的情况下，对该节点的访问请求可以被转移到其他正常的节点上。而且对某个节点进行离线维护和再上线，整个集群的运行不受影响。

负载均衡指的是通过某种算法，将整体的工作负载均分到每个节点上。

集群根据结构可分为两种： 同构集群和异构集群。同构集群的所有节点功能都相同，异构集群的节点具有不同的功能。

在《分布式对象存储——原理、架构及Go 语言实现》中实现的分布式对象存储就是一个异构集群，它具有接口服务节点和数据服务节点两种不同类型的节点，以分别实现 REST 接口和数据存储的功能。

本书实现的分布式缓存集群是一种同构集群，所有的节点功能完全相同，节点之间通过 gossip 协议互相更新状态，节点失效事件会在有限时间内扩散到整个集群，失效节点的负载会由其他有效节点承担，以达到高可用的目的。同样，当新增节点时，其他节点也会将自己的负载分出一部分给新节点。

gossip 协议简介

gossip 协议是一种计算机与计算机之间互相通信的协议，它的原理借鉴了社交网络和传染病的传播方式。现代分布式系统在遇到以下两种问题时通常会选择采用gossip 协议来作为节点间通信的协议：

• 通信需要跨越异质网络，节点之间不能两两互通；
• 分布式系统过于庞大以至于没有别的协议比 gossip 更高效。

gossip 协议满足以下几个条件:

• 协议核心包含定期的一对一的节点间通信;
• 通信的消息长度有限;
• 节点互动会导致某个节点的状态被更新到至少一个其他节点上;
• 不需要底层网络稳定;
• 通信频率较低，协议本身的开销可以忽略;
• 通信对象的选择具有随机性，可从全体节点中选出，也可以选自一个较小的相邻节点的集合;
• 消息会在节点间被复制，意味着传递的信息存在冗余。

我们实现的缓存服务使用了 HashiCorp 公司开源的第三方Go包memberlist作为gossip 协议库。

为了能成功编译本章源码，读者需要运行下列go get 命令下载这个Go包:
go get github.com/hashicorp/memberlist

负载均和一致性散列

对于一般的集群来说,负载均衡功能的实现通常是在网络入口处配置一台或多台负载均衡节点，专门用来将客户端的请求重定向到实际的操作节点上。这样的做法不需要客户端和服务端了解负载均衡的实现方式，可以有效降低客户端和服务端实现的复杂度。代价则是额外的负载均衡节点和重定向的开销。

缓存服务集群却不能使用这种方法。 缓存服务追求的是速度，响应一次请求可能也就几毫秒，重定向的开销对我们来说过大。所以缓存服务集群一般不会有这样一个额外的负载均衡节点，相对的，服务端和客户端就必须自己来实现负载均衡。

负载该由哪个节点承担需要对键进行一致性散列计算获得。如果某个服务节点接收到的请求不应由该节点处理，则该节点会拒绝该请求，并通知客户端正确的节点。

客户端需要在启动时随机访问一台缓存节点，获取集群所有节点列表并对自己操作的每一个键计算一致性散列来决定访问哪个节点。

通常情况下,集群是稳定的,客户端的请求总是被发送给正确的节点。特殊情况发生时，比如有节点死机维护或新节点上线、客户端的某个请求会发生超时或连接关闭或被服务端拒绝，此时客户端需要重新获取集群所有节点列表并重新计算一致性散列。

一致性散列是一种特殊的散列表，每次当它需要重新分配大小时，需要重新映射的键的平均数仅有 K/n 个，其中K是键的总数，n 是对应的节点数。而传统的散列表重新分配大小时，绝大多数键需要重新分配，因为传统散列表的键对应的节点由其散列值对节点总数取模决定，见图 7-1

现在假设又多了 个节点，ID 为4，此时原先的个散列值需要对 取模，结果见图 7-2：

可以看到由于模数发生了变化，大多数键的取模余数也会变化。这意味着每次当集群新增或删除节点时，大部分的键都会被映射到别的节点上，反映到缓存服务上就是大多数缓存立即失效。

一致性散列可以极大地减少需要重新映射的键的数量，它的实现方式见图7-3。
一致性散列的实现方式可以被看成一个环，所以一致性散列通常也被成为散列环。在一致性散列中，节点ID 和 key 一样需要进行散列计算，以决定自己在环上的位置，如图 7-3 所示。

计算散列值的散列函数是由算法决定的，不受节点总数变化的影响，这彻底避免了节点总数变化导致余数变化的问题。两个相邻节点的散列值决定一个半开半闭区间的范围，落在这个范围内的键由闭节点负责处理。

比如，假设 3个节点的散列值分别为50、150和250，那么它们将整个散列环分成3 个区间，分别是[50,150]、[150,250)、[250,50)，那么，散列值为 101 的键落在第一个区间，由节点1处理: 202 落在第二个，由节点2处理:303、404 和10 落在第三个，由节点3 处理。

散列函数的结果取值范围是全体 32 位正整数，在计算机中可以表示成[0, 2^32-1]。向上跨越正整数边界将会回到 0开始继续递增，所以被称为环。我们第3 个区间就是这样形成的。

现在我们假设新的节点4加入集群，它的散列值为350，见图7-4。

此时，原来的3个区间变成了 4个，但是只有散列值为 10和404 的两个 key需要重新映射到节点 4 上，其他键的映射节点都保持不变。

同理，如果我们将节点2移出集群，只有散列值为 202 的键需要被重新映射到节点1上，其他键的映射节点保持不变。

散列表就是键和节点之间的映射关系。传统散列表将节点总数作为计算映射关系的算法的参数，节点总数发生变化意味着算法的参数发生了变化，从而导致大多数键的映射结果发生变化。一致性散列令节点也计算散列值，从算法参数中移除了节点总数，所以新增或删除节点的影响范围就仅限于该节点跟相邻节点形成的区间。

致性散列的虚拟节点

虚拟节点，可以让我们的负载分散得更加均匀。
散列函数让我们的节点随机分散在整个环上。当节点数很多的时候，相邻节点之间的区间长度就会比较平均，意味着每个节点的负载比较均衡。然而当节点数比较少时，节点的负载就可能不均衡，见图 7-5。

当我们的集群只有节点1时，所有的负载都由它承担没问题。现在我们要新加一个节点 2，由于散列函数的随机性，节点 2出现在环上各个位置的概率都是一样的，所以很可能就出现图 7-5 这样的状况，两个节点之间离的很近。此时，节点1只需要负责 25% 的负载，而节点2需要负责 75%。

解决方案是使用虚拟节点，见图 7-6

如果我们让每个节点拥有 3 个虚拟节点，那么新增节点 2会让虚拟节点数增加到6个。每个虚拟节点都随机分配，虚拟节点数越多，最终的负载分布就越平衡。

我们实现的缓存服务使用了第3方Go包consistent作为我们的一致性散列库。
go get stathat.com/c/consistent

小结

本章实现了缓存的集群服务。跟单节点服务相比，集群服务可以提供更高的容量和网络带宽。同时，集群还具备高可用和负载均衡的功能：高可用意味着当集群中有节点下线时，该节点的负载会自动由其他节点接手；负载均衡意味着集群的总负载会平均地分摊到每个节点上。

我们利用 gossip 协议来进行节点间通信，同时使用一致性散列来计算负载均衡。当节点总数发生变化时，一致性散列需要重新映射的键比传统散列表少得多，平均为K/n。

分布式系统的CAP理论证明了一致性 Consistency、可用性Availability和分区容错性Partition tolerance不可能被一个分布式系统同时满足：

• 一致性意味着每一次读取要么得到最新的结果，要么得到一个错误；
• 可用性意味着每一次成功的读取都可以得到一个结果，但不保证是最新的；
• 分区容错性意味着在集群节点无法互通的情况下依然能对外提供服务。

我们的缓存服务集群可以保证分区容错性,因为我们不需要去其他节点获取数据，缓存服务使用的都是当前节点的本地数据，无法互通的集群节点可以独立对外提供服务。

我们也可以保证可用性。当集群状态发生改变的时候(如节点死机或新节点上线)，键的映射关系也会发生变化，但总有一个节点可以提供服务。

我们无法保证的是一致性。前一秒 Set 的键值对，后一秒再去访问可能就因为键的映射关系变了而被拒绝服务，我们去新节点访问的时候得到的可能就不是最新的值。

为了解决这个问题，我们会在下一章介绍一种技术，该技术能够将这些键从老节点转移至新节点上。这样，当客户端需要 Get 这些键时，新节点能够提供服务，而老节点的缓存资源也将释放。