[[325799]]

一、集中存储结构

说到分布式存储，我们先来看一下传统的存储是怎么个样子。

传统的存储也称为集中式存储， 从概念上可以看出来是具有集中性的，也就是整个存储是集中在一个系统中的，但集中式存储并不是一个单独的设备，是集中在一套系统当中的多个设备，比如下图中的 EMC 存储就需要几个机柜来存放。

[[325800]]

在这个存储系统中包含很多组件，除了核心的机头(控制器)、磁盘阵列( JBOD )和交换机等设备外，还有管理设备等辅助设备。

结构中包含一个机头，这个是存储系统中最为核心的部件。通常在机头中有包含两个控制器，互为备用， 避免硬件故障导致整个存储系统的不可用。机头中通常包含前端端口和后端端口，前端端口用户为服务器提供存储服务，而后端端口用于扩充存储系统的容量。通过后端端口机头可以连接更多的存储设备，从而形成一个非常大的存储资源池。

在整个结构中，机头中是整个存储系统的核心部件，整个存储系统的高级功能都在其中实现。控制器中的软件实现对磁盘的管理，将磁盘抽象化为存储资源池，然后划分为 LUN 提供给服务器使用。这里的 LUN 其实就是在服务器上看到的磁盘 。当然，一些集中式存储本身也是文件服务器，可以提供共享文件服务。无论如何，从上面我们可以看出集中式存储 最大的特点是有一个统一的入口，所有数据都要经过这个入口 ，这个入口就是存储系统的机头。这也就是集中式存储区别于分布式存储最显著的特点。如下图所示：

二、分布式存储

分布式存储最早是由谷歌提出的，其目的是通过廉价的服务器来提供使用与大规模，高并发场景下的 Web 访问问题。它 采用可扩展的系统结构，利用多台存储服务器分担存储负荷，利用位置服务器定位存储信息，它不但提高了系统的可靠性、可用性和存取效率，还易于扩展。

1 、分布式存储的兴起

分布式存储的兴起与互联网的发展密不可分，互联网公司由于其数据量大而资本积累少，而通常都使用大规模分布式存储系统。

与传统的高端服务器、高端存储器和高端处理器不同的是，互联网公司的分布式存储系统由数量众多的、低成本和高性价比的普通 PC 服务器通过网络连接而成。其主要原因有以下三点

(1) 互联网的业务发展很快，而且注意成本消耗，这就使得存储系统不能依靠传统的纵向扩展的方式，即先买小型机，不够时再买中型机，甚至大型机。互联网后端的分布式系统要求支持横向扩展，即通过增加普通 PC 服务器来提高系统的整体处理能力。

(2) 普通 PC 服务器性价比高，故障率也高，需要在软件层面实现自动容错，保证数据的一致性。

(3) 另外，随着服务器的不断加入，需要能够在软件层面实现自动负载均衡，使得系统的处理能力得到线性扩展。

2 、分布式存储的重要性

从单机单用户到单机多用户，再到现在的网络时代，应用系统发生了很多的变化。而分布式系统依然是目前很热门的讨论话题，那么，分布式系统给我们带来了什么，或者说是为什么要有分布式系统呢?

(1)升级单机处理能力的性价比越来越低;

企业发现通过更换硬件做垂直扩展的方式来提升性能会越来越不划算;

(2)单机处理能力存在瓶颈;

某个固定时间点，单颗处理器有自己的性能瓶颈，也就说即使愿意花更多的钱去买计算能力也买不到了;

(3)出于稳定性和可用性的考虑

如果采用单击系统，那么在这台机器正常的时候一切 OK ，一旦出问题，那么系统就完全不能用了。当然，可以考虑做容灾备份等方案，而这些方案就会让系统演变为分布式系统了;

(4)云存储和大数据发展的必然要求

云存储和大数据是构建在分布式存储之上的应用。移动终端的计算能力和存储空间有限，而且有在多个设备之间共享资源的强烈的需求，这就使得网盘、相册等云存储应用很快流行起来。然而，万变不离其宗，云存储的核心还是后端的大规模分布式存储系统。大数据则更近一步，不仅需要存储海量数据，还需要通过合适的计算框架或者工具对这些数据进行分析，抽取其中有价值的部分。如果没有分布式存储，便谈不上对大数据进行分析。仔细分析还会发现，分布式存储技术是互联网后端架构的神器，掌握了这项技能，以后理解其他技术的本质会变得非常容易。

3 、分布式存储的种类和比较

分布式存储包含的种类繁多，除了传统意义上的分布式文件系统、分布式块存储和分布式对象存储外，还包括分布式数据库和分布式缓存等，但其中架构无外乎于三种

A、 中间控制节点架构

以 HDFS ( Hadoop Distribution File System )为代表的架构是典型的代表。在这种架构中，一部分节点 NameNode 是存放管理数据(元数据)，另一部分节点 DataNode 存放业务数据，这种类型的服务器负责管理具体数据。这种架构就像公司的层次组织架构， namenode 就如同老板，只管理下属的经理( datanode )，而下属的经理，而经理们来管理节点下本地盘上的数据。

在上图中， 如果客户端需要从某个文件读取数据，首先从 NameNode 获取该文件的位置(具体在哪个 DataNode )，然后从该 NameNode 获取具体的数据。在该架构中 NameNode 通常是主备部署( Secondary NameNode )，而 DataNode 则是由大量节点构成一个集群。由于元数据的访问频度和访问量相对数据都要小很多，因此 NameNode 通常不会成为性能瓶颈，而 DataNode 集群中的数据可以有副本，既可以保证高可用性，可以分散客户端的请求。因此，通过这种分布式存储架构可以通过横向扩展 datanode 的数量来增加承载能力，也即实现了动态横向扩展的能力。

B、 完全无中心架构 – 计算模式

以 Ceph 为代表的架构是其典型的代表。在该架构中与 HDFS 不同的地方在于该架构中没有中心节点。客户端是通过一个设备映射关系 计算出来 其写入数据的位置，这样客户端可以直接与存储节点通信，从而避免中心节点的性能瓶颈。

如上图所示， 在 Ceph 存储系统架构中核心组件有 MON 服务、 OSD 服务和 MDS 服务等。

(1) MON 服务用于维护存储系统的硬件逻辑关系，主要是服务器和硬盘等在线信息。MON 服务通过集群的方式保证其服务的可用性。

(2) OSD 服务用于实现对磁盘的管理，实现真正的数据读写，通常一个磁盘对应一个 OSD 服务。

(3) MDS 只为 CephFS 文件存储系统跟踪文件的层次机构和存储元数据。Ceph 块设备和 RADOS 并不需要元数据，因此也不需要 Ceph MDS 守护进程

(4) RADOS ：RADOS 就是包含上述三种服务的 ceph 存储集群。在 Ceph 中所有的数据都以对象形式存在的，并且无论哪种数据类型 RADOS 对象存储都将负责保存这些对象。RADOS 层可以确保数据始终保持一致性。要做到这一点必须执行数据复制、故障检测和恢复，以及数据迁移和所在集群节点实现在平衡

(5) RBD (块设备)：原名 RADOS 块设备，提供可靠的分布式和高性能块存储磁盘给客户端。

(6) CephFS ：Ceph 文件系统提供了一个使用 Ceph 存储集群存储用户数据的与 POSIX 兼容的文件系统

(7) Librados ：libRADOS 库为 PHP 、 RUBY 、 Java 、 Python 、 C++ 等语言提供 了方便的访问 RADOS 接口的方式

(8) RADOS GW ：RGW 提供对象存储服务，它允许应用程序和 Ceph 对象存储建立连接， RGW 提供了与 Amazon S3 和 openstack Swift 兼容的 RUSTFUL API

客户端访问存储的大致流程是，客户端在启动后会首先通过 RADOS GW 进入，从 MON 服务拉取存储资源布局信息，然后根据该布局信息和写入数据的名称等信息计算出期望数据的位置(包含具体的物理服务器信息和磁盘信息)，然后和该位置信息对应的 CephFS 对应的位置直接通信，读取或者写入数据

C、 完全无中心架构 – 一致性哈希

以 swift 为代表的架构是其典型的代表。与 Ceph 的通过计算方式获得数据位置的方式不同，另外一种方式是通过一致性哈希的方式获得数据位置。一致性哈希的方式就是将设备做成一个哈希环，然后根据数据名称计算出的哈希值映射到哈希环的某个位置，从而实现数据的定位。

Swift 中存在两种映射关系，对于一个文件，通过哈希算法( MD5 )找到对应的虚节点(一对一的映射关系)，虚节点再通过映射关系( ring 文件中二维数组)找到对应的设备(多对多的映射关系)，这样就完成了一个文件存储在设备上的映射。

D 、分布式存储的比较

那么现在问题来了，如果我们要选择分布式存储，选择哪种好呢?其实它们各有各的优势和使用场景，具体要看需求。

(1)HDFS

主要用于大数据的存储场景，是 Hadoop 大数据架构中的存储组件。HDFS 在开始设计的时候，就已经明确的它的应用场景，就是大数据服务。主要的应用场景有：

a 、对大文件存储的性能比较高，例如几百兆，几个 G 的大文件。因为 HDFS 采用的是以元数据的方式进行文件管理，而元数据的相关目录和块等信息保存在 NameNode 的内存中， 文件数量的增加会占用大量的 NameNode 内存。如果存在大量的小文件，会占用大量内存空间，引起整个分布式存储性能下降，所以尽量使用 HDFS 存储大文件比较合适。

b 、适合低写入，多次读取的业务。就大数据分析业务而言，其处理模式就是一次写入、多次读取，然后进行数据分析工作， HDFS 的数据传输吞吐量比较高，但是数据读取延时比较差，不适合频繁的数据写入。

c 、 HDFS 采用多副本数据保护机制，使用普通的 X86 服务器就可以保障数据的可靠性，不推荐在虚拟化环境中使用。

( 2 ) Ceph

目前应用最广泛的开源分布式存储系统，已得到众多厂商的支持，许多超融合系统的分布式存储都是基于 Ceph 深度定制。而且 Ceph 已经成为 LINUX 系统和 OpenStack 的 “ 标配 ” ，用于支持各自的存储系统。Ceph 可以提供对象存储、块设备存储和文件系统存储服务。同时支持三种不同类型的存储服务的特性，在分布式存储系统中，是很少见的。

a、 Ceph 没有采用 HDFS 的元数据寻址的方案，而且采用 CRUSH 算法，数据分布均衡，并行度高。而且在支持块存储特性上，数据可以具有强一致性，可以获得传统集中式存储的使用体验。

b、 对象存储服务， Ceph 支持 Swift 和 S3 的 API 接口。在块存储方面，支持精简配置、快照、克隆。在文件系统存储服务方面，支持 Posix 接口，支持快照。但是目前 Ceph 支持文件的性能相当其他分布式存储系统，部署稍显复杂，性能也稍弱，一般都将 Ceph 应用于块和对象存储。

c、 Ceph 是去中心化的分布式解决方案，需要提前做好规划设计，对技术团队的要求能力比较高。特别是在 Ceph 扩容时，由于其数据分布均衡的特性，会导致整个存储系统性能的下降

( 3 )Swift

主要面向的是对象存储。和 Ceph 提供的对象存储服务类似。主要用于解决非结构化数据存储问题。它和 Ceph 的对象存储服务的主要区别是。

a 、客户端在访问对象存储系统服务时， Swift 要求客户端必须访问 Swift 网关才能获得数据。而 Ceph 使用一个运行在每个存储节点上的 OSD (对象存储设备)获取数据信息，没有一个单独的入口点，比 Swift 更灵活一些。

b 、数据一致性方面， Swift 的数据是最终一致，在海量数据的处理效率上要高一些，但是主要面向对数据一致性要求不高，但是对数据处理效率要求比较高的对象存储业务。而 Ceph 是始终跨集群强一致性。主要的应用场景，在 OpenStack 中，对象存储服务使用的就是 Swift ，而不是 Ceph 。

三、分布式理论浅析

1 、一致性和可用性

由于异常的存在，分布式存储系统设计时往往会将数据冗余存储多份，每一份称为一个副本)。这样，当某一个节点出现故障时，可以从其他副本上读到数据。可以这么认为，副本是分布式存储系统容错技术的唯一手段。由于多个副本的存在，如何保证副本之间的一致性是整个分布式系统的理论核心。

数据一致性这个单词在平常开发中，或者各种文章中都能经常看见，我们常常听见什么东西数据不一致了，造成了一定的损失，赶快修复一下。那有几种一致性呢?

a、 时间一致性：要求所有数据组件的数据在任意时刻都是完全一致的;

b、 事物一致性：事务一致性只能存在在事务开始前的和事务完成之后，在事务过程中数据有可能不一致，比如 A 转 100 元给 B ， A 扣减 100 ， B 加上 100 ，在事务开始前和事务完成之后都能保证他们的帐是对上的，那么这就是事务一致性。但是在事务过程中有可能会出现 A 扣减了 100 元， B 没有加上 100 元的情况，这就是不一致

c、 在应用程序中涉及多个不同的单机事务，只有在所有的单机事务完成之前和完成之后，数据是完全一致的。

仅仅靠这三种一致性在实际的一些复杂场合是很难描述清楚的，所以，我们引出了一致性模型，这里我们由强到弱简单的介绍几种常见的一致性模型。

A 、线性一致性

又称强一致性， 可以看做只有一个单核处理器，或者可以看做只有一个数据副本，并且所有操作都是原子的。

如上图所示，对于事件 e1 和 e2 来说，如果事件 e1 的 response 是在事件 e2 的 invoke 之前，我们就说 e1 happen before e2 。

对于同一个线程来说，前面的事件一定 happen before 后面的事件。但是对于不同线程上的两个事件来说，它们之间只有在在时间线上没有交叉的情况下，才会存在 happen before 关系。对于有交叉的那些事件，比如下图中的 event2 和 event3 ，它们两个就不存在 happen before 关系，对于我们要寻找的合法顺序执行过程来说，它们两个的顺序可以是任意的。

B 、顺序一致性

顺序一致性弱于严格一致性。对变量的写操作不一定要在瞬间看到，但是，不同处理器对变量的写操作必须在所有处理器上以相同的顺序看到，这里处理器再分布式系统中可以换成不同的节点。

假设有两个线程 A 和 B 并发执行。其中 A 线程由 3 个操作构成，它们在程序中的顺序是：A1->A2->A3. B 线程也有 3 个操作，它们在程序中的顺序是：B1->B2->B3. 假设如果在顺序一致的模型中的效果就是如上两个图所示。

C 、因果一致性

因果一致性是弱于顺序一致性的一致性模型，顺序一致性要求所有的操作的顺序都必须按照某个单个处理器 ( 节点 ) 的顺序，而因果一致性只需要满足有因果关系的操作是顺序一致性即可。

简单来说如果有人问你一个问题，那么你给出答案，这两个就是因果关系，但如果你给出答案再问题之前，那么这个就违反了因果关系。举个简单的例子如果节点 1 更新了数据 A ，节点 2 读取数据 A ，并更新数据 B ，这里的数据 B 有可能是根据数据 A 计算出来的，所有具备因果关系，但是如果节点 3 看到的是先更新的 B ，再更新的 A 那么就破坏了因果一致性。

D 、最终一致性

其实除了强一致以外，其他的一致性都可以看作为最终一致性，只是根据一致性不同模型的不同要求又衍生出了很多具体一致性模型。当然最简单的最终一致性，是不需要关注中间变化的顺序，只需要保证在某个时间点一致即可。只是这个某个时间点需要根据不同的系统，不同业务再去衡量。再最终一致性完成之前，有可能返回任何的值，不会对这些值做任何顺序保证。

E 、可用性

可用性指“ Reads and writes always succeed” ，即服务一直可用，而且是正常响应时间。对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。所以，一般我们在衡量一个系统的可用性的时候，都是通过停机时间来计算的。

可用性分类

可用水平（%）

年可容忍停机时间

容错可用性

99.9999

/ < Machine id > / < Logical volume,Photo > ，后续根据各个部分的信息依次访问 CDN ， Cache 和后端的 Haystack Store 存储节点。Haystack Directory 构造 URL 时可以省略 部分从而使得用户直接请求 Haystack Cache 而不必经过 CDN 。Haystack cache 收到的请求包含两个部分：用户 Browser 的请求及 CDN 的请求， Haystack cache 只缓存用户 Browser 发送的请求且要求请求的 Haystack Store 存储节点是可写的。一般来说， Haystack Store 的存储节点写一段时间以后达到容量上限变为只读，因此，可写节点的图片为最近增加的图片，是热点数据。

Haystack 的写请求 ( 图片上传 ) 处理流程为：Web Server 首先请求 Haystack Directory 获取图片的 id 和可写的逻辑卷轴，接着将数据写入对应的每一个物理卷轴 ( 备份数一般为 3) 。

Facebook Haystack 及 Taobao TFS 这样的文件系统一般称为 Blob 文件系统。它们都是解决大量的小图片文件的问题，因此架构很类似，不同点包括

(1) 逻辑卷轴大小的选择，比如 Haystack 选择 100GB 的逻辑卷轴大小， TFS 中 block 大小一般为 64MB ;

(2) Haystack 使用 RAID 6 ，且底层文件系统使用性能更好的 XFS ，淘宝后期摈除了 RAID 机制，文件系统使用 Ext3 ;

(3) Haystack 使用了 Akamai & Limelight 的 CDN 服务，而 Taobao 已经使用自建的 CDN ，当然， Facebook 也在考虑自建 CDN 。

4、 CDN 内容分发网络

CDN 的全称是 Content Delivery Network ，即内容分发网络。其目的是通过在现有的 Internet 中增加一层新的网络架构，将网站的内容发布到最接近用户的网络 " 边缘 " 。实现如下三个目的

( 1 )解决因分布、带宽、服务器性能带来的访问延迟问题，适用于站点加速、点播、直播等场景。使用户可就近取得所需内容，解决 Internet 网络拥挤的状况，提高用户访问网站的响应速度和成功率。

( 2 )控制时延无疑是现代信息科技的重要指标， CDN 的意图就是尽可能的减少资源在转发、传输、链路抖动等情况下顺利保障信息的连贯性。

( 3 ) CDN 就是扮演者护航者和加速者的角色，更快准狠的触发信息和触达每一个用户，带来更为极致的使用体验。

如下图所示 DNS 在对域名解析时不再向用户返回源服务器的 IP ，而是返回了由智 CDN 负载均衡系统选定的某个边缘节点的 IP 。用户利用这个 IP 访问边缘节点，然后该节点通过其内部 DNS 解析得到源服务器 IP 并发出请求来获取用户所需的页面，如果请求成功，边缘节点会将页面缓存下来，下次用户访问时可以直接读取，而不需要每次都访问源服务器。

Taobao 的 CDN 架构是自研的，用于支持用户购物，尤其是“双 11” 光棍节时的海量图片请求，图片存储在后台的 TFS 集群中， CDN 系统将这些图片缓存到离用户最近的边缘节点。CDN 采用两级 Cache ：L1-Cache 以及 L2-Cache 。用户访问淘宝网的图片时，通过全局调度系统( Global Load Balancing )调度到某个 L1-Cache 节点。如果 L1-Cache 命中，那么直接将图片数据返回用户;否则，请求 L2-Cache 节点，并将返回的图片数据缓存到 L1-Cache 节点。如果 L2-Cache 命中，直接将图片数据返回给 L1-Cache 节点;否则，请求源服务器的图片服务器集群。每台图片服务器是一个运行着 Nginx 的 Web 服务器，它还会在本地缓存图片，只有当本地缓存也不命中时才会请求后端的 TFS 集群，图片服务器集群和 TFS 集群部署在同一个数据中心内。

对于每个 CDN 节点，其架构如图 4-11 所示。从图中可以看出，每个 CDN 节点内部通过 LVS+Haproxy 的方式进行负载均衡。其中， LVS 是四层负载均衡软件，性能好;Haproxy 是七层负载均衡软件，能够支持更加灵活的负载均衡策略。通过有机结合两者，可以将不同的图片请求调度到不同的 Squid 服务器。

上图是 CDN 的单节点架构，它有以下三个特点

(1) Squid 服务器构成淘宝单节点中的 CDN 中的分布式缓存，这个实现比分布式缓存简单很多，因为不需要考虑数据持久化。

(2) 分级缓存，由于缓存数据有较高的局部性，在 Squid 服务器上使用 SSD+SAS+SATA 混合存储，图片随着热点变化而迁移，最热门的存储到 SSD ，中等热度的存储到 SAS ，轻热度的存储到 SATA 。通过这样的方式，能够很好地结合 SSD 的性能和 SAS 、 SATA 磁盘的成本优势;

(3) 低功耗服务器定制， CDN 缓存服务是 IO 密集型而不是 CPU 密集型的服务，因此，选用 Intel Atom CPU 定制低功耗服务器，在保证服务性能的前提下大大降低了整体功耗。

五、分布式键值系统

分布式键值系统是用于存储关系简单的半结构化数据，半结构化数据均封装成由 键值对组成的对象，其中 key 为唯一标示符;value 为属性值，可以为任何类型，如文字、图片，也可以为空;timestamp 为时间戳，提供对象的多版本支持。分布式键值系统以键值对存储，它的结构不固定，每一元组可以有不一样的字段，可根据需要增加键值对，从而不局限于固定的结构，适用面更大，可扩展性更好。

分布式键值系统支持针对单个 键值对的增、删、查、改操作，可以运行在 PC 服务器集群上，并实现集群按需扩展，从而处理大规模数据，并通过数据备份保障容错性，避免了分割数据带来的复杂性和成本。

总体来说，分布式键值系统从存储数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是，分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统可以配置数据的备份数目，可以将一份数据的所有副本存储到不同的节点上，当有节点发生异常无法正常提供服务时，其余的节点会继续提供服务。

1、 Amazon Dynamo

Dynamo 以很简单的键值方式存储数据，不支持复杂的查询。Dynamo 中存储的是数据值的原始形式，不解析数据的具体内容。Dynamo 主要用于 Amazon 的购物车及 S3 云存储服务。在实现过程中解决了如下问题：

问题

采用的技术

数据分布

改进的哈希算法

复制协议

复制写协议（NRW参数可调）

数据冲突的解决

向量时钟

临时故障处理

数据回传机制

永久故障处理

Merkle哈希树

成员资格及错误检测

基于Gossip的成员资格和错误检测协议

Dynamo 采用一致性哈希将数据分布到多个存储节点中，概括来说：给系统中的每个节点分配一个随机 token ，这些 token 构成一个哈希环。执行数据存放操作时，先计算主键的哈希值，然后存放到顺时针方向的第一个大于或者等于该哈希值的 token 所在的节点。一致性哈希的有点在于节点加入 / 删除只会影响到在哈希环相邻的节点，而对其他节点没影响。

A 、 Dynamo 架构

考虑到节点的异构性，不同节点的处理能力差别很大， Dynamo 使用了改进的一致性哈希算法：每个物理节点根据其性能的差异分配多个 token ，每个 token 对应一个虚拟节点，每个虚拟节点的处理能力基本相当，并随机分布在哈希空间中。存储时，数据按照哈希值落到某个虚拟节点负责的区域，然后被存储到该虚拟节点所对应的物理节点。

如下图，某 Dynamo 集群中原有 3 个节点，每个节点分配 3 个 token 。存放数据时，首先计算主键的哈希值，并根据哈希值将数据存放到对应 token 所在的节点。假设增加节点 4 ，节点 token 分配情况发生变化，这就实现了自动负载均衡。

为了找到数据所属的节点，要求每个节点维护一定的集群信息用于定位。Dynamo 系统中每个节点维护整个集群的信息，客户端也缓存整个集群的信息，因此，绝大部分请求能够一次定位到目标节点。

B 、 Gossip 协议

由于机器或者人为的因素，系统中的节点成员加入或者删除经常发生，为了保证每个节点缓存的都是 Dynamo 集群中最新的成员信息，所有节点每隔固定时间(比如 1s )通过 Gossip 协议的方式从其他节点中任意选择一个与之通信的节点。如果连接成功，双方交换各自保存的集群信息。

Gossip 协议用于 P2P 系统中自治的节点协调对整个集群的认识，比如集群的节点状态、负载情况。我们先看看两个节点 A 和 B 是如何交换对世界的认识的。

( 1 ) A 告诉 B 其管理的所有节点的版本(包括 Down 状态和 Up 状态的节点);

( 2 ) B 告诉 A 哪些版本它比较旧了，哪些版本它有最新的，然后把最新的那些节点发给 A (处于 Down 状态的节点由于版本没有发生更新所以不会被关注);

( 3 ) A 将 B 中比较旧的节点发送给 B ，同时将 B 发送来的最新节点信息做本地更新;

( 4 ) B 收到 A 发来的最新节点信息后，对本地缓存的比较旧的节点做更新。

由于种子节点的存在，新节点加入可以做得比较简单。新节点加入时首先与种子节点交换集群信息，从而对集群有了认识。DHT ( Distributed Hash Table ，也称为一致性哈希表)环中原有的其他节点也会定期和种子节点交换集群信息，从而发现新节点的加入。

集群不断变化，可能随时有机器下线，因此，每个节点还需要定期通过 Gossip 协议同其他节点交换集群信息。如果发现某个节点很长时间状态都没有更新，比如距离上次更新的时间间隔超过一定的阈值，则认为该节点已经下线了。

2、 Taobao Tiar

Tair 是一个分布式的 key/value 系统。

Tair 有四种引擎：mdb, rdb, kdb 和 ldb 。分别基于四种开源的 key/value 数据库：memcached, Redis, Kyoto Cabinet 和 leveldb 。Tair 可以让你更方便地使用这些 KV 数据库。比如 Redis 没有提供 sharding 操作，如果有多个 Redis Server ，你需要自己写代码实现 sharding ， Tair 帮你封装了这些。

Tair 有以下优点：

( 1 )统一的 API 。无论底层使用何种引擎，上层的 API 是一样的。

( 2 ) Tair 将集群操作封装起来，解放了开发者。淘宝内部在使用 Tair 时，一般都是双机房双集群容错，利用 invalid server 保证两个集群间的一致性，这些对于开发者都是透明的。

A 、 Tair 使用场景

( 1 )非持久化 (mdb,rdb)

( 2 )持久化 (kdb,ldb)

B 、 Tair 的架构

Tair 作为一个分布式系统，是由一个中心控制节点和若干个服务节点组成，

a 、 config server 功能：

( 1 )通过维护和 data server 心跳来获知集群中存活节点的信息;

( 2 )根据存活节点的信息来构建数据在集群中的分布表;

( 3 )根据数据分布表的查询服务;

( 4 )调度 data server 之间的数据迁移、复制;

b 、 data server 功能

( 1 )提供存储引擎;

( 2 )接受 client 的 put/get/remove 等操作;

( 3 )执行数据迁移，复制等;

( 4 )插件：在接受请求的时候处理一些自定义功能;

( 5 )访问统计;

c 、 client 功能

( 1 )在应用端提供访问 tair 集群的接口;

( 2 )更新并缓存数据分布表和 invalid server 地址等;

( 3 ) local cache ，避免过热数据访问影响 tair 集群服务;

( 4 )流控;

在下图中，。客户端首先请求 Config Server 获取数据所在的 Data Server ，接着往 Data Server 发送读写请求。Tair 允许将数据存放到多台 Data Server ，以实现异常容错。

C 、数据分布均衡性

Tair 的分布采用的是一致性哈希算法，对于所有的 key ，分到 Q 个桶中，桶是负载均衡和数据迁移的基本单位， config server 根据一定的策略把每个桶指派到不同的 data server 上，因为数据按照 key 做 hash 算法，保证了桶分布的均衡性，从而保证了数据分布的均衡性。

D 、容错

当某台 Data Server 故障不可用时， Config Server 能够检测到。每个哈希桶在 Tair 中存储多个副本，如果是备副本，那么 Config Server 会重新为其指定一台 Data Server ，如果是持久化存储，还将复制数据到新的 Data Server 上。如果是主副本，那么 ConfigServer 首先将某个正常的备副本提升为主副本，对外提供服务。接着，再选择另外一台 Data Server 增加一个备副本，确保数据的备份数。

E 、数据迁移

增加或减少 data server 的时候， config server 会发现这个情况， config server 负责重新计算一张新的桶在 data server 上的分布表，将原来由减少的机器服务的桶的访问重新指派到其他的 data server 中，这个时候就会发生数据的迁移。比如原来由 data server A 负责的桶，在新表中需要由 B 负责，而 B 上并没有该桶的数据，那么就将数据迁移到 B 上来，同时 config server 会发现哪些桶的备份数目减少了，然后根据负载均衡情况在负载较低的 data server 上增加这些桶的备份。当系统增加 data server 的时候， config server 根据负载，协调 data server 将他们控制的部分桶迁移到新的 data server 上，迁移完成后调整路由;

数据迁移时 data server 对外提供服务的策略，假设 data server A 要把桶 1,2,3 迁移到 data server B ，因为迁移完成前，客户端的路由表没有变化，客户端对 1,2,3 的访问请求都会路由到 A ，现在假设 1 还没迁移， 2 正在迁移， 3 已经迁移完成，那么如果访问 1 ，则还是访问 data server A ，如果访问 3 ，则 A 会把请求转发给 B ，并且将 B 的返回结果返回给客户，如果访问 2 ，则在 A 上处理，同时如果是对 2 的修改操作，会记录修改 log ，当桶 2 完成迁移的时候，还有把 log 发送给 B ，在 B 上应用这些 log ，最终 AB 数据一致才是真正完成迁移。如果 A 是由于宕机而引发的迁移，客户端会收到一张中间临时状态的分配表，把宕机的 data server 负责的桶临时指派给有其备份的 data server 来处理，此时服务是可用的，负载可能不均衡，当迁移完成后，又能达到一个新的负载均衡状态。

3、 ETCD

ETCD etcd 是一个高可用的键值存储系统，主要用于共享配置和服务发现。

(1) 由 CoreOS 开发并维护的，灵感来自于 ZooKeeper 和 Doozer ;

(2) 它使用 Go 语言编写，并通过 Raft 一致性算法处理日志复制以保证强一致。

(3) Google 的容器集群管理系统 Kubernetes 、开源 PaaS 平台 Cloud Foundry 和 CoreOS 的 Fleet 都广泛使用了 etcd ;

(4) 当集群网络出现动荡，或者当前 master 节点出现异常时， etcd 可以进行 master 节点的选举工作，同时恢复集群中损失的数据

A 、 ETCD 的特点

( 1 )简单：基于 HTTP+JSON 的 API 让你用 curl 就可以轻松使用。

( 2 )安全：可选 SSL 客户认证机制。

( 3 )快速：每个实例每秒支持一千次写操作。

( 4 )可信：使用 Raft 算法充分实现了分布式。

B 、提供的能力

Etcd 主要提供以下能力

(1) 提供存储以及获取数据的接口，它通过协议保证 Etcd 集群中的多个节点数据的强一致性。用于存储元信息以及共享配置。

(2) 提供监听机制，客户端可以监听某个 key 或者某些 key 的变更。用于监听和推送变更。

(3) 提供 key 的过期以及续约机制，客户端通过定时刷新来实现续约( v2 和 v3 的实现机制也不一样)。用于集群监控以及服务注册发现。

(4) 提供原子的 CAS ( Compare-and-Swap )和 CAD ( Compare-and-Delete )支持( v2 通过接口参数实现， v3 通过批量事务实现)。用于分布式锁以及 leader 选举。

C 、 ETCD 架构

( 1 ) Etcd v2 存储， Watch 以及过期机制

Etcd v2 是个纯内存的实现，并未实时将数据写入到磁盘，持久化机制很简单，就是将 store 整合序列化成 json 写入文件。数据在内存中是一个简单的树结构。

store 中有一个全局的 currentIndex ，每次变更， index 会加 1. 然后每个 event 都会关联到 currentIndex.

当客户端调用 watch 接口(参数中增加 wait 参数)时，如果请求参数中有 waitIndex ，并且 waitIndex 小于 currentIndex ，则从 EventHistroy 表中查询 index 小于等于 waitIndex ，并且和 watch key 匹配的 event ，如果有数据，则直接返回。如果历史表中没有或者请求没有带 waitIndex ，则放入 WatchHub 中，每个 key 会关联一个 watcher 列表。当有变更操作时，变更生成的 event 会放入 EventHistroy 表中，同时通知和该 key 相关的 watcher 。

( 2 ) Etcd v3 存储， Watch 以及过期机制

Etcd v3 将 watch 和 store 拆开实现，我们先分析下 store 的实现。Etcd v3 store 分为两部分，一部分是内存中的索引， kvindex ，是基于 google 开源的一个 golang 的 btree 实现的，另外一部分是后端存储。

按照它的设计， backend 可以对接多种存储，当前使用的 boltdb 。boltdb 是一个单机的支持事务的 kv 存储， Etcd 的事务是基于 boltdb 的事务实现的。Etcd 在 boltdb 中存储的 key 是 reversion ， value 是 Etcd 自己的 key-value 组合，也就是说 Etcd 会在 boltdb 中把每个版本都保存下，从而实现了多版本机制。

4 、产品选型比较( Etcd ， Zookeeper ， Consul 比较)

这三个产品是经常被人拿来做选型比较的。

(1) Etcd 和 Zookeeper 提供的能力非常相似，都是通用的一致性元信息存储，都提供 watch 机制用于变更通知和分发，也都被分布式系统用来作为共享信息存储，在软件生态中所处的位置也几乎是一样的，可以互相替代的。二者除了实现细节，语言，一致性协议上的区别，最大的区别在周边生态圈。Zookeeper 是 apache 下的，用 java 写的，提供 rpc 接口，最早从 hadoop 项目中孵化出来，在分布式系统中得到广泛使用( hadoop, solr, kafka, mesos 等)。Etcd 是 coreos 公司旗下的开源产品，比较新，以其简单好用的 rest 接口以及活跃的社区俘获了一批用户，在新的一些集群中得到使用(比如 kubernetes )。虽然 v3 为了性能也改成二进制 rpc 接口了，但其易用性上比 Zookeeper 还是好一些。

(2) Consul 的目标则更为具体一些， Etcd 和 Zookeeper 提供的是分布式一致性存储能力，具体的业务场景需要用户自己实现，比如服务发现，比如配置变更。而 Consul 则以服务发现和配置变更为主要目标，同时附带了 kv 存储。在软件生态中，越抽象的组件适用范围越广，但同时对具体业务场景需求的满足上肯定有不足之处。