分布式块存储相关综述

-.z---..--总结资料目录目录11HDFS综述41.1引言41.2HDFS体系构造455文件系统的名字空间(namespace)51.2.4SecondaryNamenode61.3HDFS数据组织6数据流-读文件6数据流-写文件71.4HDFS数据复制8副本存放8副本选择9多副本写策略91.5HDFS元数据组织10元数据及其修改的存放位置10元数据的持久化101.6HDFS强健性11磁盘数据错误、心跳检测和重新复制11数据完整性11元数据磁盘错误11存储空间回收12负载均衡121.7总结131.8参考文献132GoogleFS概述142.1背景介绍142.2GFS体系构造152.3数据组织16读写流程162.4元数据组织192.5副本放置策略202.6多副本的写策略212.7一致性策略222.8节点状态管理23消息通信23副本状态管理：24垃圾回收机制：252.9总结263Dynamo系统综述263.1简介26需求背景26主要特点27系统架构273.2主要技术介绍29分布式哈希〔DistributedHashTable〕30虚节点〔VirtualNode〕31节点管理〔Membership〕33数据分区的复制〔Replication〕35矢量时钟〔Vectorclock〕35读写策略〔Read/Write〕37反熵〔Anti-entropy〕37树39暗示移交(Hintedhandoff)40协议413.3实现443.4总结453.5参考464Ceph分布式文件系统简介474.1简介474.2Ceph特点474.3Ceph目标484.4Ceph客户端504.5Ceph元数据效劳器514.6Ceph监视器514.7Ceph对象存储524.8其他功能524.9Ceph的地位和未来524.10其他分布式文件系统534.11展望未来534.12参考文献53HDFS综述摘要：HDFS是一个分布式的文件系统，有着高的容错性等特点，并设计用来部署在低廉的硬件上，它提供高传输率用来应用程序的数据，适合有着超大数据集的应用程序，为了更好的了解HDFS文件系统及其特点，本文对HDFS的体系构造，数据组织，副本策略，元数据组织，数据维护，负载均衡等方面进展了分析研究。关键字：分布式文件系统HadoopHDFS引言当数据集超过一个单独的物理计算机的存储能力时，便有必要讲它分布到多台计算机上，管理者跨计算机网络存储的文件系统成为分布式文件系统。Hadoop是一个基于JAVA的支持数据密集型分布式应用的分布式文件系统，可以在成千个低本钱商用硬件存储节点上处理PB级的数据。Hadoop是Apache开源工程，用户可以在不了解分布式底层细节的情况下，开发分布式程序，充分利用集群的威力高速运算和存储。支持这个工程并在自己的web搜索和商业广告业务上使用它，开发类似于Google的MapReduce和GoogleFS的技术。Hadoop包含两个局部，Hadoop文件系统(HadoopDistributedFileSystem,HDFS)和MapReduce编程模型，图1为Hadoop的组成局部。其中HDFS运行在商用硬件上，它和现有分布式文件系统很相似，但也具备了明显的差异性，比方HDFS是高度容错的，可运行在廉价硬件上；HDFS能为应用程序提供高吞吐率的数据，适用于大数据集的应用中；HDFS在POSI*规*进展了修改，使之能对文件系统数据进展流式，从而适用于批量数据的处理。HDFS为文件采用一种"一次写屡次读"的模型，从而简化了数据一致性问题，使高吞吐率数据成为可能，一些Map/Reduce应用和网页抓取程序在这种模型下表现完美。HDFS在云计算中特别是其分布式系统布局得到了人们广泛的关注，并得到了很好的应用。图1Hadoop组成HDFS体系构造HDFS的体系构造如图2所示，HDFS采用master/slave架构，一个HDFS集群主要由一个Namenode和一定数目的Datanode组成，并且还有Secondraynamenode和客户端共同构成整个完整的HDFS体系，HDFS内部的所有通信都基于标准的TCP/IP协议。图2HDFS体系构造图NamenodeNamenode是HDFS的中心效劳器，负责管理文件系统的namespace〔命名空间〕和客户端对文件的。Namenode执行文件系统的namespace操作例如翻开，关闭，重命名文件和目录，同时决定了block到具体的Datanode的映射关系，Datanode在Namenode的指挥之下进展block的创立、删除和复制。除此之外，集群配置管理，处理事务日志：记录文件的创立、删除等。因为Namenode的全部元数据在内存中存储，所以内存大小决定了整个集群的存储量。集群中单一Namenode的构造大大简化了系统的架构，Namenode是所有HDFS元数据的仲裁者和管理者，这样，用户数据不会和Namenode进展交互而是直接和Datanode进展传输。DatanodeDatanode在集群中一般是一个节点一个，它可以作为块效劳器，存储本地文件系统的数据和块的元数据，并且提供效劳数据和元数据给客户端，负责管理节点上他们附带的存储。在内部，一个文件其实分为多个block，这些block存储在Datanode集合里。Datanode在Namenode的指挥下进展block的创立、删除和复制。除此之外，Datanode进展块报道即周期性发送所有正存在的块的报告给Namenode进展系统检测，在Datanode内部也进展数据发送给其他的Datanode流水线。Namenode和Datanode都是设计成可以跑在不同的廉价的运行linu*及其上。一个典型的部署场景是一台机器跑一个单独的Namenode节点，集群中其他机器各跑一个Datanode实例。文件系统的名字空间(namespace)HDFS支持传统的层次性文件组织构造，用户或者应用程序可以创立目录，然后将文件保存在这些目录里。文件系统名字空间的层次构造和大多数现有的文件系统类似，用户可以创立、删除、移动或者重命名文件。当前HDFS不支持用户磁盘配额和权限控制，也不支持硬和软连接。Namenode负责维护文件系统的名字空间，任何对文件系统名字空间或者属性的更改都将被Namenode记录下来。应用程序可以设置HDFS保存文件的副本数目。文件副本的数目成为文件的副本系数，这个信息也是由Namenode保存。SecondaryNamenodeSecondarynamenode其实作为一个保存Namenode修改的过程，Fsimage和Editlog是HDFS的核心构造，Fsimage记录了名字空间namespace，Editlog记录了元数据的改变。每次从Namenode中复制fsimage和log到一个临时目录，然后在临时目录中集合Fsimage和Editlog到新的fsimage，然后更新新的Fsimage给Namenode。HDFS数据组织在第二章的HDFS体系构造可以看到Namenode作为控制枢纽，控制整个系统，但真正的数据交换却不经过Namenode而是直接在客户端和Datanode之间进展。在HDFS中，默认的数据块的大小为64M，文件所对应的块按照一定的部署策略存于Datanode中，Namenode管理了文件到Datanode的映射。这个数据组织构造减少了客户端和Namenode交互需求，对同一块的读写只需要向Namenode发送一个请求即可。另外块大小可以让客户端在一个给定块上进展屡次操作，降低了网络交互困难，同时也减少了Namenode的元数据大小。图3显示了数据组织构造，Namenode中元数据存放了文件路径，副本个数，存放位置等信息，通过这种组织方式能很好的找到文件块位置加快了查找速度。图3HDFS的数据组织构造HDFS被设计成支持大文件，使用HDFS的是那些需要处理大规模的数据集的应用，这些应用都是只写入数据一次，但却读一次或屡次，并且读取数据能满足流式读取需要。HDFS支持文件的“一次写入屡次读取〞语音，一个典型的数据块大小是64M，HDFS中的文件总是按照64M被切分成不同的块，每个块存储在不同的Datanode中。HDFS数据流-读文件在图4中描述了在文件读过程中，client,Namenode与Datanode三者之间是如何互动的。图4HDFS读文件流程文件读取过程如下：(1)客户端通过调用open()方法翻开要读取文件系统对象〔对于Hadoop来说，是DistributedFileSystem实例〕中的*一的文件。(2)FileSystem对象与控制节点RPC通讯以确定待读取文件的文件头几个分块所在位置。FileSystem对象返回一个FSDataInputStream对象〔支持文件查找的输入流〕给客户端供其读取数据。FSDataInputStream派生出

DFSInputStream管理控制节点和存储节点的通讯。(3)客户端调用DFSInputStream的read()方法读取最近〔远近的解释，详见后续slide〕的存储节点上的文件分块。(4)客户端不断调用read()方法将数据从存储节点下载到本地节点。(5)数据读取到一个块的末尾时，DFSInputStream将关闭到该块所在存储节点的连接，然后寻找最近的下一个数据块。这一过程对客户端是透明的。(6)客户端读取数据完毕后，调用FSDataInputStream对象的close()方法。HDFS数据流-写文件在图5中描述了在文件读过程中，client,Namenode与Datanode三者之间是如何互动的。图5HDFS写文件流程写文件流程如下：(1)客户端通过调用文件系统对象〔对于Hadoop来说，是Distributed-FileSystem实例〕的create()方法创立文件。(2)FileSystem对象与控制节点RPC通讯以在文件系统命名空间内创立新的文件，此时文件没有关联数据块。控制节点例行检查，比方文件有没有存在，客户端有没有权限创立文件等。检查通过，FileSystem对象返回一个FSDataOutputStream对象给客户端供其写入数据。与客户端读取文件时一样，FSDataOutputStream派生出

DFSOutputStream管理控制节点和存储节点的通讯。(3)客户端写入数据。DFSOutputStream将数据分组写入被称为数据队列的一个内部队列。数据队列供DataStreamer使用。(4)DataStreamer将数据组写入存储节点管线中的第一个存储节点。该节点存储相应数据并将其转交给下一个存储节点。同理，第二个节点客户端转交给最后一个〔第三个〕存储节点，〔默认备份数为3〕。(5)DFSOutputStream维护着一个被称为应答队列的内部数据组队列，该队列内容为等待被写入存储节点的数据组。只有管线中的所有存储节点都确认正确存储*一数据组，该数据组才被从应答队列中删除。(6)客户端写完数据后，调用DFSOutputStream的close()方法。该操作将所有未保存的数据组压入存储节点管线，然后等待所有数据组都被正确存储。(7)客户端联系控制节点，说明文件已经写操作执行完毕。控制节点实际上知道当前文件的存储现状，在数据块副本数到达最低副本数要求时，返回文件存储成功的消息。客户端创立文件的请**际并没有立即发送给Namenode，在刚开场客户端会讲这个文件数据缓存在本地的一个临时文件。应用程序的写操作被透明的重定向到这个临时文件，当这个临时文件累积的数量超过一个数据块的大小，客户端才会联系Namenode，后来客户端根据收到的Datanode标识符和目标数据块，将这数据块从本地临时文件上传到指定的Datanode上。HDFS数据复制HDFS被设计成能够在一个大集群中跨机器可靠地存储超大文件，它将每个文件存储成一系列的数据块，除了最后一个，所有的数据块都是同样大小的。为了容错，文件的所有数据块都会有副本。每个文件数据块大小和副本系统都是可配置的，应用程序可以指定*个文件的副本数目。副本系数可以在文件创立的时候指定，也可以在之后改变。HDFS的文件都是一次性写入的，并且严格要求在任何时候只有一个写入者。Namenode管理数据块的复制，周期性的从集群中的每个Datanode承受心跳检测和块状态报告。接收到心跳信号意味着该Datanode节点工作正常。块状态报告包含了一个该Datanode上所有数据块的列表，如图3中显示。副本存放副本存放是HDFS可靠性和性能的关键，优化的副本存放策略是HDFS区分于其他大局部分布式文件系统的重要特性。这种特性需要做大量的调优，并需要经历的累积。HDFS采用一种机架感知(rack-aware)的策略来改良数据的可靠性、可用性和网络带宽的利用率。通过机架感知的过程,Namenode可以确定每个Datanode所属的机架id。一个简单但没有优化的策略就是将副本存放在不同机架之上，这样可以有效防止当整个机架失效时数据的丧失，并且允许读数据的时候充分利用多个机架的带宽。这种策略设置可以将副本均匀分布在集群中，有利当组件失效情况下的负载均衡。但是，增加了写代价。大多数情况下，副本系数为3,。图6为HDFS的副本分配图，HDFS的存放策略是一个副本存放在本地机架的节点上，一个副本存放在同一机架的另一节点上，最后一个副本存放在不同机架的节点上，一个数据节点内最多放一个此块副本。这种策略减少了机架间的数据传输提高了写操作的效率。机架的错误远远比节点的错误少，所以这个策略不会影响到数据的可靠性和可用性。与此同时，数据块只存放在两个不同机架上，减少了读取数据所需的时间。图6HDFS副本存放副本选择为了降低整体的带宽消耗和读取延时，HDFS会尽量让读取程序读取离它的节点上副本。如果读取程序同一机架上有一副本，则读取该副本。如果HDFS集群跨越多个数据中心，则客户端讲首先读取本地数据中心的副本。多副本写策略当客户端当HDFS文件写入数据时，一开场是写到本地临时文件中，假设副本系数设置为3，当本地临时文件累积到一个数据块大小时，客户端会从Namenode获取一个Datanode列表用于存放副本，然后客户端开场向第一个Datanode传输数据，第一个Datanode一小局部一小局部的接收数据，将每一局部写入本地仓库，并同时传输该局部到列表中第二个Datanode。第二个Datanode一样，一小局部一小局部的接收数据，写入本地仓库，并同时传送给第三个Datanode。最后，第三个Datanode接收数据并存储在本地。因此，Datanode能流水线式的从前一个节点接收数据，并在同时转发给下一个节点，数据以流水线的方式从前一个Datanode复制到下一个，如图7所示。图7HDFS流水线写副本HDFS元数据组织HDFS元数据及其修改的存放位置HDFS系统的元数据存放于内存之中，由Namenode管理。如图3所示，元数据记录了文件名，副本个数以及存放位置等信息，以这种存储方式将整个系统数据联系起来。元数据的修改存放在Editlog之中，存于本地Namenode之上。在Namenode的元数据全部存放贮存之中，且没有文件系统元数据的页请求。在元数据类型方面，有文件系列的映射，有每个文件的块系列，有每个文件的属性等类型，事务日志记录了文件的创立、文件删除等信息。Namenode上保存着HDFS的命名空间，对于文件系统元数据产生修改的操作将会以Editlog的事务日志记录下来。例如，在HDFS中创立一个文件，Namenode就会在Editlog中插入一条记录来表示；同样地，修改文件副本系数也将往Editlog插入一条记录。Namenode在本地操作系统的文件系统中存储这个Editlog。整个系统的namespace，包括数据块到文件的映射、文件的属性等。都放在FsImage的文件中，这个文件也是放在Namenode所在的本地文件系统上。HDFS元数据的持久化Namenode在内存中保存着整个文件系统的namespace和文件数据块映射的映像。这个关键的元数据设计很紧凑，因而有一个4G内存的Namenode支撑足够大量的文件和目录。当Namenode启动时，它从硬盘中读取Editlog和FsImage,将所有Editlog中事务作用在内存中的FsImage上，并将这个新版本的FsImage从内存中保存到本地磁盘上，然后删除旧的Editlog，因为这个旧的Editlog的事务已经作用于FsImage上了。这个过程称为一个检查点，在当前现实中，检查点只发生在Namenode启动时,如图8所示。图8检查点流程图Datanode将HDFS数据以文件的形式存储在本地文件系统中，并不知道有关HDFS文件的信息，它把每个HDFS数据块存储在本地文件系统的一个单独文件中。Datanode并不在同一目录创立所有文件。当一个Datanode启动时，它会扫描本地文件系统，产生一个这些本地文件对应的所有HDFS数据块的列表，然后作为报揭发送给Namenode。HDFS强健性HDFS的主要目标就是即使在出错的情况下也要保证数据存储的可靠性。下面将分别对HDFS的措施进展分析。磁盘数据错误、心跳检测和重新复制每个Datanode节点周期性向Namenode发送心跳信号，Namenode通过心跳包的缺失检测Datanode故障，并将这些Datanode标记为dead，不会将新的请求发给它们。存放在deadDatanode上的任何数据将不再有效。这种心跳检测每三分钟进展一次。Datanode死亡有可能引起一些block副本数据低于指定值，Namenode不断跟踪需要复制的block，在任何需要的情况下启动复制。以下情况需要重新复制，当*个Datanode节点失效，*个副本遭到损坏，Datanode的硬盘错误或者文件的副本系数增大。数据复制，选择最近的复制块进展相应，另外平安模式下不发生文件块的复制，但承受心跳报告。数据完整性从*个Datanode获取的数据块有可能是损坏的，损坏可能是由Datanode的存储设备错误、网络错误或者软件bug造成的。HDFS客户端软件实现了对HDFS文件内容的校验检查。当客户端创立一个新的HDFS文件时，会计算这个文件每个数据块的校验和，并将此校验和作为一个单独的隐藏文件保存在同一个HDFS的namspace下。当客户端获取文件内容后，它会检验从Datanode获取的数据跟相应的校验和是否匹配，如果不匹配，客户端则可从其他Datanode中获取该数据块的副本。元数据磁盘错误FsImage和Editlog是HDFS的核心数据构造，如果这些文件损坏了，整个HDFS实例都会失效。因此，Namenode可以配置成支持维护多个FsImage和Eidtlog的副本。任何对FsImage或Eidtlog的修改都将同步到副本上。这在元数据组织中讲到了就不细述了。存储空间回收当用户或应用程序删除*个文件时，这个文件并没有立刻从HDFS中删除。实际上，HDFS会将这个文件重命名转移到/trash目录中。只要文件还在/trash中，该文件就可以被迅速的恢复。文件在/trash中保存的时间是可配置的，当超过这个时间Namenode就会将该文件从namespace中删除，删除文件会使得该文件相关的数据块被释放。如果用户想恢复删除的文件，可以通过浏览/trash目录找回文件，/trash目录仅仅保存了被被删除的最后副本。负载均衡Hadoop的HDFS集群中容易出现机器与机器之间磁盘利用率不平衡的情况，例如集群中增加新的数据节点，集群中负载不均衡会产生很多问题，例如机器之间无法到达更好网络带宽，磁盘无法利用等等，因此就需要进展负载均衡策略。实际上，在Hadoop中包含一个balance程序，通过运行这个程序到达负载均衡的状态，例如命令sh$HADOOP_HOME/bin/start-balancer.sh-t10%，这个命令中-t参数后面跟的是HDFS到达平衡状态的磁盘使用率偏差值。如果机器与机器之间磁盘使用率偏差小于10%，则我们就认为HDFS集群已经到达了平衡的状态。开发人员在开发Balancer程序的时候，遵循了以下几点原则：1.在执行数据重分布的过程中，必须保证数据不能出现丧失，不能改变数据的备份数，不能改变每一个rack中所具备的block数量。2.系统管理员可以通过一条命令启动数据重分布程序或者停顿数据重分布程序。3.Block在移动的过程中，不能暂用过多的资源，如网络带宽。4.数据重分布程序在执行的过程中，不能影响namenode的正常工作。基于这些根本点，目前Hadoop数据重分布程序实现的逻辑流程如以下图9所示：图9Hadoop数据重分布逻辑流程图Rebalance程序作为一个独立的进程与namenode进展分开执行。1RebalanceServer从NameNode中获取所有的DataNode情况：每一个DataNode磁盘使用情况。2RebalanceServer计算哪些机器需要将数据移动，哪些机器可以承受移动的数据。并且从NameNode中获取需要移动的数据分布情况。3RebalanceServer计算出来可以将哪一台机器的block移动到另一台机器中去。4,5,6需要移动block的机器将数据移动的目的机器上去，同时删除自己机器上的block数据。7RebalanceServer获取到本次数据移动的执行结果，并继续执行这个过程，一直没有数据可以移动或者HDFS集群以及到达了平衡的标准为止。总结数据量的增长以及网络的开展，分布式文件系统越来越受到关注，分布式文件系统的设计需求一般是，并发控制，可伸缩性，容错以及平安需求。本文对HDFS的体系构造，数据组织和元数据组织，数据复制，系统强健性等多方面对HDFS进展了分析研究。HDFS作为一个分布式文件系统，提供高吞吐量的应用程序数据，对外部客户机而言，HDFS就像一个传统的分级文件系统，数据组织方面主/从构造元数据和数据分开存放，设计缓存区进展读写，并且使得客户端直接和Namenode进展数据交互来到达数据传输的高性能。在可扩展性和容错方面，HDFS设置了多副本来保证数据块的准确，设置了心跳检测和元数据持久化来保证整个系统的容错能力。HDFS以其分布式文件系统和开源特性得到了很多人的关注和研究，Hadoop最常见的用法之一就是web搜索，作为并行数据处理，它的表现非常突出。由于其扩容能力，本钱低，高效率和高可靠性等方面的特性，很多公司使用Hadoop作为其文件系统，得到了互联网公司的广泛的应用，从初创到现在，在Hadoop客户中，可以看到Facebook，Linkedin，Amazon,可以看到EMC，eBay，Twitter，IBM,Micrsoft，Apple，HP等等大小型企业。可能Hadoop在Namenode的内存限制，网络带宽，平安问题方面还没有做到很完善，但并不大影响其开展，Hadoop在分布式领域得到越来越多的人去研究，去不断改良不断完善。参考文献[1]HadoopDistributedFileSystemfortheGrid,GarhanAttebury,AndrewBaranovski[2]基于HDFS的云存储效劳系统研究，黄晓云，硕士论文，2010[3]HadoopHighAvailabilitythroughMetadataReplication,FengWang,JieQiu[4]HDFSAchitectureGuide[5]TheHadoopDistributedFilesystemBalancingPortabilityandPerformance,JeffreyShafer,ScottRi*ner,andAlanL.Co*GoogleFS概述摘要：GoogleFS是一个分布式的文件系统，设计是用来满足Google迅速增长的数据处理需求。GFS与过去的分布式文件系统拥有许多一样的目标，例如性能，扩展性，可靠性以及可用性等等。本文就GFS的体系构造，数据组织，容错策略等方面进展了分析研究。关键字:分布式文件系统GFS背景介绍GFS〔GoogleFileSystem〕是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进展的应用。它运行于廉价的普通硬件上，但可以提供容错功能。它可以给大量的用户提供总体性能较高的效劳。GFS作为新型的分布式文件系统，在高性能计算，数据传输容错等方面拥有自己特点，与此同时它的设计还受到应用负载和技术环境的影响。因此，GFS与其他分布式文件系统有着一定的区别。GFS在特点和预期和预期上，组建失效不做异常对待，做正常事件相应；文件数量适中，大小较大，一般为100MB以上；GB级文件为主，系统需要对GB级文件处理优化需要支持小文件处理，无需优化。在Google大局部文件的修改，不是覆盖原有数据，而是在文件末尾追加新数据。对文件的随机写几乎是不存在的。一般写入后，文件就只会被读，而且通常是按顺序读取。另外，数百个数据源可能同时写一个文件。运行中的应用程序连续产生的数据，档案数据，由一台机器产生而被另一台机器同时或者稍后使用的中间结果等都拥有这样的特征文件末尾追加的写方式是性能优化和原子性保证的核心。系统必须高效地实现良好定义的多客户端并行追加到一个文件的语义。GFS提供了一个类似传统文件系统的接口，虽然它并没有实现类似POSI*的标准API。文件在目录中按照层次组织，用路径名来标识。支持常用的操作，如创立，删除，翻开，关闭，读和写文件等。 GFS有快照〔snapshot〕和记录追加〔recordappend〕操作。快照操作可以用很低的本钱创立文件或者目录树的拷贝。记录追加操作可以在保证原子性的前提下，允许多个客户端同时在一个文件上追加数据。这对于实现多路结果合并以及“产生者—消费者〞模型非常有好处，多个客户端可以同时在一个文件上追加数据，而不需要任何额外的锁定。GFS体系构造GFS的体系构造如以下图1所示，下面是GFS的组成局部的介绍。图1GFS体系构造图一个GFS集群由一个master和大量的chunkserver构成，并被许多客户。Master：单一的主效劳器大大简化了设计，这样主效劳器可以通过全局的信息准确确定块的位置以及块的分配和复制决定。但是必须尽量减少其参与数据读写过程，防止使主效劳器成为系统的瓶颈Chunkserver:管理块，数据处理Client:请求读写。客户端通常在一次请求中查询多个块，而主效劳器的回应也可以包含紧跟着这些请求块后面的块的信息。这些额外的信息实际上在没有代价的前提下，防止了客户端与效劳器未来的几次通讯。文件被分成固定大小的块。每个块由一个不变的、全局唯一的64位的chunk－handle标识，chunk－handle在块创立时由master分配。出于可靠性考虑，每一个块被复制到多个chunkserver上。Master维护文件系统所以的元数据，包括名称空间，控制信息，文件到块的映射信息，以及块当前所在的位置。同时也控制系统*围的活动，如块租约〔lease〕管理，废弃块的垃圾收集，chunkserver间的块迁移。定期通过HeartBeat消息，Master与每一个chunkserver通信，给chunkserver传递指令并收集它的状态。主效劳器可以在后台，简单而高效的周期扫描自己的整个状态。这种周期性的扫描用来在块效劳器间实现块的垃圾收集的功能，用来实现块效劳器失效的时复制新副本的功能，用来实现负载均衡的块移动的功能，以及用来实现统计硬盘使用情况的功能等。数据组织块规模是设计中的一个关键参数。GFS选择的是64MB，这比一般的文件系统的块规模要大的多。每个块的副本作为一个普通的Linu*文件存储，在需要的时候可以扩展。实际应用中，Google应用几乎只需要顺序地读取大规模的多块文件。平均文件大小约为100MB，因此存储数据块的大小被设计为64MB并且拥有以下优点：减少client和master之间的交互。因为读写同一个块只是要在开场时向master请求块位置信息。即使对于少量数据的随机读操作也可以很方便的为一个规模达几个TB的工作集缓缓存块位置信息。Client在一个给定的块上很可能执行多个操作，这样就可以和一个chunkserver保持较长时间的TCP连接，减少网络负载。它减少了master上保存的元数据〔metadata〕的规模，从而使得可以将metadata放在内存中。读写流程读算法：应用程序产生读请求;GFSClient讲请求转换成索引(filename,byterange->filename,chunkinde*)并发送给Master;Master回复块句柄与副本位置图2读流程1Client确定一个块并向该位置发送读请求Chunkserver向client发送读取出的数据Client将数据传递给应用图3读流程2读*例：图4读*例1产生包含索引的读请求〔crawl_99,2048字节〕；GFS转换索引并发送请求〔crawl_99,2048字节->crawl_99,inde*:3〕;Master相应并回复位置〔chunksever4,7,9包含含有文件信息的块〕；图5读*例2客户端选取读取位置(chunkserver7被选中)；并且发送读请求；Chunkserver发送读取出的数据(2048字节)给客户端；客户端传递数据给应用。图6读*例3写算法：1，2同读；3.Master回复块句柄和副本位置〔包含主块和二级副本块的信息〕；图7写流程14.Client将要写的数据推送到各个位置，数据被暂时存放在CHUNKSERVER的内部缓存中；图8写流程25.CLIENT发送写命令给主块；6.主块决定存放在CHUNKSEVER数据缓存中的操作执行序列，并且决定的按顺序写入块中；7.主块将操作序列发给其他二级副本，副本执行按该序列写命令；图9写流程38.二级副本回复完成给主块；9.主块回复完成给客户端。图10写流程4如果写失败，主块通知客户端重新发送写请求。元数据组织 Master效劳器保存三种主要类型的元数据：文件和块的命名空间；文件到块的映射；每个块的副本的位置。所有的元数据都保存在主效劳器的内存里，所以主效劳器操作的速度很快。纯内存的机制一种可能的问题是，块的数量和整个系统的容量都受限于主效劳器拥有的内存尺寸。不过实际上这不是一个严重的限制。对于每个64MB的块，效劳器只需管理不到64字节的元数据。同时，大多数的块是满的，因为每个文件只有最后一块是局部填充的。前两种类型〔命名空间和文件到块的映射〕的元数据，还会用日志的方式保存在主效劳器的硬盘上的操作日志内。操作日志是包含元数据关键性变化的历史记录，它作为逻辑时间线定义了并发操作的执行顺序，并用于恢复文件系统状态。文件、块以及它们的版本号都由它们被创立时的逻辑时间而唯一地、永久地被标识。使用日志，让我们可以简单可靠的更新主效劳器的状态，而且不用担忧效劳器崩溃带来的数据不一致的风险。Master可以用操作日志来恢复它的文件系统的状态。为了将启动时间减至最小，日志就必须要比拟小。每当日志的长度增长到超过一定的规模后，master就要检查它的状态，它可以从本地磁盘装入最近的检查点来恢复状态。操作日志被复制到数个远程的机器上，并且只有在将相应的日志记录写到本地和远程的磁盘上之后才答复用户的请求。主效劳器并不会持久化保存块的位置信息。主效劳器在自己启动以及块效劳器参加集群的时候，会询问块效劳器它所包含的块的信息。副本放置策略 块副本创立有三种原因：块创立，重新复制和负载均衡。块副本放置策略效劳于两个目标：最大化数据可靠性和可用性，最大化网络带宽利用率。GFS副本放置策略是主要是根据以下几点要求和特点而设计的：希望把新的副本放置在低于平均硬盘使用率的块效劳器，这样平衡块效劳器之间的硬盘使用率。希望限制每一个块效劳器上“近期〞创立操作的数量。虽然创立操作本身是廉价的，但是它总是会紧跟着沉重的写操作，因为写入者需要写的时候才会进展创立，而在我们的“追加一次读屡次"的工作负载下块一旦被成功写入就会变为只读。希望把块分布在机架之间，这样能充分利用带宽。而当一个块效劳器(chunckserver)变得不可用，或者块效劳器报告存储在其中的副本损坏，或者副本数的目标被提高，如之前一个存在3个副本而现在需要增加1个副本的时候，副本需要被重新复制。 重新复制的块的基于几个因素排序：块离它的副本数量目标有多远，例如，我们给已经丧失两个副本的块比只丧失一个副本的块更高的优先级我们优先重新复制活着的文件而不是属于那些近期删除的文件的块为了减小对正在运行的应用程序的影响，我们提高阻塞客户机流程的块的优先级主效劳器选择优先级最高的块，然后通过通知一些块效劳器上直接从已有的可用的副本复制数据的方式来"克隆"它。新副本位置的策略根创立操作类似：平均硬盘使用率，限制同一块效劳器上的活动的克隆操作数量，在机架间分布副本。为了防止克隆所需的网络流量超过客户端流量，主效劳器限制块和块效劳器的活泼克隆操作数量。另外，每个块效劳器，通过调节它对源块效劳器的读请求来限制它花在每个克隆操作上面的带宽。最后，主效劳器周期性地对副本进展负载均衡：它检查当前的副本分布情况，然后移动副本以得到更好的硬盘剩余空间以及负载的均衡。同时在这个过程中，主效劳器逐渐的填满一个新的块效劳器，而不是用新块以及随之同时涌入的沉重的写通讯淹没它。新副本的布置标准根上面讨论的一样。另外，主效劳器必须选择哪些现有的副本要被移走。一般来说，它移动那些剩余空间低于平均值的块效劳器上面的副本，这样就可以平衡硬盘使用率。多副本的写策略 多个副本需要保持变更顺序的一致性。所谓变更，就是指一个会改变块内容或者元数据的操作，例如写入或者记录追加。GFS使用租约来保证多副本的一致写操作。 主效劳器为其中一个副本签署一个块租约，我们把这个副本叫做主块〔Primary〕。主块决定对块所有的一系列操作的顺序。进展操作的时候所有的副本遵从主块确定的这个顺序。图11多副本写策略(1)Client向主效劳器询问哪一个块效劳器保存了当前的租约，以及其他副本的位置，如果当前没有租约，Master指定一个块作为主块；(2)主效劳器回复主块的标识符以及其他副本的位置，Client保存此主块信息，在之后的通讯中可以减少与Master的通讯；(3)客户机把数据推进到所有的副本上；数据流和控制流分开；(4)所有的副本都被确认已经得到数据后，客户机发送写请求到主块；(5)主块把写请求传递到所有的二级副本；(6)所有的二级副本回复主块说明他们已经完成操作；(7)主块回复client完成写操作。租约机制的设计是为了最小化主效劳器的管理负载。租约的初始超时是60秒。然而一旦块被修改正，主块可以请求更长的租期，通常可以通过主效劳器确实认收到额外的时间。这些额外时间的请求和批准都通过效劳器和块效劳器之间的心跳信息来传递。即使主效劳器和主块失去联系，它仍旧可以平安地在老租约到期后产生一个加诸于其他的副本的租约。一致性策略 由于客户端缓存块位置，所以在信息刷新前，他们有可能从一个失效的副本读取数据。时间窗口由缓存的超时以及文件的下一次翻开时间决定。文件翻开后会清楚缓存中与文件有关的所有块信息。而且由于GFS的文件的修改大多数都只是进展末尾追加，所以一个失效的副本通常返回一个提前完毕的块而不是过期的数据。读取者重新尝试并联系主效劳器后，就会立即得到当前的快位置。 成功操作很久后，组件的失效当然也可以损坏或者毁掉数据。GFS用主效劳器和块效劳器之间的握手来找到失效的块效劳器。用校验和来检测数据的损坏。一旦发现问题，数据会尽快从有效的副本中恢复出来。只有一个块的所有副本在GFS做出反响之前，全部丧失，这个块才会不可逆转的丧失，而通常GFS的反响是在几分钟内的，即使在这种情况下，块不可用，而不是损坏；应用程序会收到清晰的错误信息而不是损坏的数据。 保证数据一致性的关键是具有原子性的操作—记录追加操作。向同一个区间的并发的传统的写操作是不连续的，因此区间有可能包含来自多个client的数据碎片。GFS提供了一个叫做记录追加的原子性的附加操作，相比传统的写操作中client指定被写数据的偏移位置，在recordappend中，client只是指定数据，而偏移的位置有GFS指定。具体而言是指写文件的块的末尾。GFS在其选定的偏移处将数据保证原子性地添加到文件中，并将偏移返回给client。 记录追加操作在GFS的分布应用中使用的非常频繁，许多客户机并行地追加数据到同一个文件。它是遵循租约的控制流程的一个操作，区别是仅在主块有点额外的控制逻辑：Client把数据推送给文件最后一个块的所有副本，然后发送请求给主块。主块检查对当前块的记录追加操作是否会造成块超过最大值〔64MB〕。如果是这样，它首先把块填充到最大值，告诉所有二级块做同样的操作，然后回复Client说明需要对下一个块也进展操作节点状态管理消息通信Master定期通过HeartBeat消息与每一个chunkserver通信，给chunkserver传递指令并收集它的状态。不管主效劳器和块效劳器是如何关闭的，它们被设计为可以在数秒钟内恢复它们的状态并启动。事实上，我们并不区分正常或者非正常的关闭；通常关闭效劳器的方法就是杀死它的进程。对客户机和其他的效劳器来说，他们发出的请求超时只是个小问题，重新连接到重启后的效劳器。每个块被复制到不同的块效劳器上，当有块效劳器离线或者通过校验和验证发现了坏块，主效劳器克隆已存在的副本用来保证每个块被完全复制。为了可靠性主效劳器状态要被复制。它的操作日志和检查点都要复制到多台机器上。对状态的操作被设计为，只有当它的日志记录被写入到本地硬盘以及所有的主效劳器副本以后才会被提交。为了简化设计，一个主效劳器进程管理所有改变系统状态的操作包括如垃圾回收这样的后台活动。当它失效，它几乎可以马上重新启动。当它的机器或者硬盘损坏，GFS架构之外的监视机构会总启动一个包含这操作日志副本的新主效劳器进程。客户机只使用主效劳器的规*名〔例如，gfs-test〕与之联络，这是一个DNS别名，如果主效劳器被重新指定它可以相应的改变。此外，还有些"影子"主效劳器，它们即使在真正的主效劳器当机的时候也只提供文件系统的只读。它们是影子，而不是镜像，所以它们的数据总是比主效劳器更新要慢点，通常是1秒以下。它们可以提高那些不经常改变的文件的读取效率，或者是帮助那些不在乎数据更新略有延迟的程序。事实上，自从文件从块效劳器被读走，应用程序就不再关心它们内容的变化了。在短暂窗口可以延迟的是文件的元数据，比方目录的内容或者控制信息。为了保持自己被通知，影子主效劳器增长中的操作日志的副本，并按照与主效劳器完全一样的顺序对自己的数据构造执行修改。类同主效劳器，它也在启动的时候轮询块效劳器〔之后定期〕以获得块副本的位置，交换心跳信息以监控它们的状态。它仅在主效劳器决定创立和删除副本的时候，才需要依靠主效劳器得到副本位置的更新结果。副本状态管理：过期副本检测： 如果块效劳器失效，或者块效劳器当机的时候错过了一些操作，块副本会过期。对于每个块，主效劳器保存一个块版本号，用来分辨当前副本和过期副本。无论何时主效劳器获得一个块的新租约，它增加块的版本号，然后通知当前副本。主效劳器和这些副本都把新的版本号记录在它们的持久化存储的状态中。这发生在任何客户机得到通知以前，发生在它写入块之前。如果另外一个块效劳器正好不可用，则它的块版本号就不会被更新。当这个块效劳器重新启动，向主效劳器报告它拥有的块的集合以及相应的版本号的时候，主效劳器就会检测出来块效劳器包含过期的块。当主效劳器看到一个比它们的记录更高的版本号，主效劳器假定那些块效劳器在获取租约的时候失效了，所以选择更高的版本作为当前的版本。主效劳器在周期的垃圾回收中移除所有的过期副本。在这之前，当回复客户机的块信息请求的时候，主效劳器只是高效的当作那些过期的块不存在而已。作为另外的保护措施，主效劳器通知客户机哪个块效劳器持有租约的时候，当主效劳器指示块效劳器从哪个块效劳器读取数据进展克隆操作的时候，主效劳器的信息都包含了块的版本号。客户机或者块效劳器执行操作时会验证版本号，这样它们就可以总是当前版本的数据了。垃圾回收机制：文件删除后，GFS不会立刻收回可用的物理空间。对文件和块的常规垃圾收集非常惰性。我们发现这样可以使系统更简单更可靠。当应用程序删除了一个文件，主效劳器立刻把删除记录到日志里就像其他的改变一样。然而，它不是马上回收资源，而是把文件改成一个包含删除时间戳的隐藏的名字。当主效劳器对文件系统命名空间进展常规扫描的时候，它会删除所有有如此隐藏文件名的文件，如果它们已经存在超过3天了〔这个时间间隔是可以被设置的〕。直到此时，文件仍旧可以用新的特殊的名字读取，可以被反删除，通过改名把它变为正常文件。如果隐藏文件从名称空间中移走，保存在内存中它的元数据就被删除了。这有效的效劳于对所有块的连接。在相似的对块命名空间的常规扫描中，假设主效劳器找到孤儿块〔无法从任何文件到达的块〕会擦除它们的元数据。在与主效劳器交换数据的心跳信息中，每个块效劳器报告它拥有的块的信息的一个子集，然后主效劳器回复指出哪些块在主效劳器的元数据中已经不存在了。块效劳器上面就是任意删除这些块的副本了。我们可以很容易的识别所有块的引用：他们都在效劳器独立掌握的文件到块的映射表中。我们也可以轻易的找到所有块的副本：在每个块效劳器上他们都是指定目录下的Linu*文件。所有主效劳器不知道的副本都是"垃圾"。垃圾回收在恢复存储空间的同时，提供直接删除无法得到的几个好处。首先，这样对于组件经常失效的大规模分布系统简单而且可靠。块创立可能在*些块效劳器成功，*些效劳器上失败，留着那些失败的副本反正主效劳器也不知道。副本删除信息可能丧失，主效劳器必须记得重新发送失败传递的目标，它自己的和块效劳器的。垃圾回收提供了统一无依赖的途径，来去除那些不知道用处的副本。其次，它把存储回收操作合并到主效劳器规律性的后台活动，如例行扫描以及跟块效劳器握手。这样，操作会被批量的执行，开销会被分散。而且，操作会在主效劳器相对空闲的时候完成。这样主效劳器可以给那些需要快速反响的客户机请求提供更快捷的响应。三，有延迟的存储回收比随机、不可逆转的删除，更加平安。总结GFS(googleFileSystem)，是google公司为了存储海量搜索数据而设计的文件系统，在分布式文件系统领域占有举足轻重的作用，之后很多的文件系统都借用了GFS的设计理念，特别是随着云计算的火爆，GFS越来越得到人们的关注。本文是对GFS文件系统构造，数据组织，节点管理等方面进展了分析。Dynamo系统综述简介Dynamo是由亚马逊〔Amazon〕公司开发的一个分布式数据存储系统，它是一个完全分布式的、无中心节点的存储系统。相比传统的集中式存储系统，Dynamo在设计之初就定位在一个高可靠、高可用且具有良好容错性的系统。实践说明，Dynamo作为亚马逊的key-value模式的存储平台，可用性和扩展性都很好，性能也不错：读写中99.9%的响应时间都在300ms内。需求背景Amazon是全球第一大网络书店，拥有5900万活泼用户、25万多可在线全文阅读的图书、数据存储总量到达42TB。2010年有个统计，Amazon每年通过每部kindle卖出的图书数量为24本，按2010年销售kindle300万台来算，Amazon光kindle上每天卖出的图书就有19.7万。amazon还提供了效劳水平协议〔SLA〕，简单的例子来说，Amazon效劳器要求对99.9%的用户请求在300ms内提供响应。对应这样的存储率、吞吐量和性能要求，传统数据库很难全部兼顾。根据CAP原理〔一致性，可用性，分区容忍性〕，传统数据库没有分区容忍性，数据集中存储。存储率可能不是问题，但是对吞吐量和性能来说就有点吃力。再加上为了防止单点故障，数据必然有备份与复制，在强一致性的要求下，又必将以损失性能为代价。而且随着业务量的增大，数据越来越多，传统数据库的可扩展性也是个问题，这不是一部强大的机器不停的挂硬盘就能解决的问题。所以，时势造英雄，Dynamo应运而生。它的最大特点是去中心化的分布式系统，整个Dynamo存储平台由多个物理异构的机器组成〔可以是廉价的普通机器〕，每台机器角色一样，可以随意添加或去除，且不需要太多人为干预。每台机器存放一局部数据，这些数据的备份同步完全由系统自己完成，单台机器故障甚至一个数据中心的断电故障都不会影响系统对外的可用性，是具有高可用性和高扩展性的分布式数据存储系统。主要特点完全分布式、无中心节点；Key-value模式；高容错性；使用了多种技术解决一致性问题；高可用性和扩展性。系统架构设计原则：增量的可扩展性：Dynamo应能够一次水平扩展一台存储主机，而对系统操作者和系统本身的影响很小对称性：每个dynamo节点应该与它的对等节点有一样的责任；不应该存在有区别的节点或采取特殊较色，有额外责任的节点；去中心化：是对对称性的延伸，设计应采用有利于去中心化而不是集中控制的技术；异质性：系统能够利用异质性的根底设施运行。设计目标：Dynamo主要是针对应用程序需要一个“永远可写〞数据存储，不会由于故障或并发写入而导致更新操作被拒绝；Dynamo是建立在一个所有节点被认为是值得信赖的单个管理域的根底设施之上；使用Dynamo的应用程序不需要支持分层命名空间(许多文件系统采用的规*)或复杂的(由传统的数据库支持)关系模式的支持；Dynamo是为延时敏感应用程序设计的，需要至少99.9％的读取和写入操作必须在几百毫秒内完成。面向效劳的Amazon平台架构如以下图所示：从上到下依次是页面呈现组件，聚合器效劳，效劳，数据存储。网页的内容是由页面呈现组件生成，该组件进而查询许多其它效劳。一个效劳可以使用不同的数据存储来管理其状态，这些数据存储仅在其效劳*围内才能。有些效劳作为聚合器使用其他一些效劳，可产生合成相应。存储系统在建立一个效劳的SLA中扮演着重要角色，状态管理成为一个效劳的SLA的主要组成局部。对Dynamo的主要涉及考虑就是将控制权赋给各个效劳，通过系统属性来控制其耐用性和一致性，并让效劳自己在功能和本钱效益之间进展权衡。主要技术介绍Dynamo采用了一些技术，用于解决其对等架构下的一致性问题，如下表所示：数据均衡分布改良的一致性哈希算法数据冲突处理矢量时钟临时故障处理暗示移交永久故障恢复Merkle哈希树成员资格和错误检测基于gossip协议的错误排查分布式哈希〔DistributedHashTable〕为了到达去中心化的设计目的，DHT通过基于key-based路由策略来找到对应的存储节点：-整个分布式系统组成一个环，环根据节点的数目被化分为对应的区域-每个区域用一个*围值token表示(n-1,n]-每个节点负责一个区域通常采用MD5作为hash算法来分配key值给环上的区域：-设节点数为N-MD5算法将输出一个128bit的整数，为方便表示，去掉负数，因此0≤token≤2^127-因此对于任一的节点，为其分配*围(tokenn-1,tokenn]，即(前一节点的最大值,本节点的值]，它将负责MD5(k)值落在其中的所有Key-必定存在一个首尾相接的区域(wrappingrange),该区域一定是包含最小token值的区域，且一般为left>right,其分配的值分成两局部：

a)MD5(k)=(0,token0]即最小节点值到*围的最小值〔由于去掉负数，所以为0)

b)MD5(k)=(tokenn-1,

2^127]，如下例:下面以一个4节点，token*围为[0,100]为例说明：-A(80,5]此为wrappingrang〔因为其包含了最小值0，且左值大于右值〕。因为最小*围值规定为0,最*围值只能到100,其实际可以拆分为(80,100],(0,5]B(5,30]C(30,55]D(55,80]非wrappingrang比拟好理解，对于wrapping其有以下特点：-左值>右值-包含最小值的token值-其包含所有比当前所有分配的节点最大值的*围〔本例中为80)但是，隐含条件必须小于最大的取值*围〔本例中为100),所以得到(80,100]-其包含所有比当前所有分配的节点最小值的*围〔本例中为5)但是，隐含条件必须大于最小的取值*围〔本例中为0)，所以得到(0,5]-0与100重叠，这即是wrappingrang的来历。保持平衡为了保持平均动态分配〔即不引起热点〕，对于MD5算法的DHT,在分配节点token值时，需要按照以下公式计算对应的值：tokenN=i*(2^127/N)fori=0..N-1(N为节点个数)虚节点〔VirtualNode〕对于hash，第一种是普通的hash。假设有N个结点，hash(key)模N就可以把key值平均分配在结点上。但这样有个问题，当有新结点参加的时候，因为N变了，所有的数据必须重算并重新迁移分配。一般的应用可能无所谓，考虑Amazon则大的数据量和SLA要求，把所有的数据重算一遍就要了命了。然后是分布式hash。每个结点被分配一个区间，比方说A分配的区间是[A,B)，则只有满足A<=hash(key)<B的key值会存放在A结点上。这样，当有新结点参加时，受影响的只有相邻结点而不是所有结点。比方，在AB之间参加一个结点H，只要把A上的数据拆成[A,H)和[H,B)，并把[Q,B)迁到Q上就行了。这样迁移时还是需要对A的所有数据进展扫描拆分，会影响结点A的响应速度。最后是dynamo中的改良的分布式hash。Dynamo引入虚结点的概念。假设有N个结点，把所有key值分成Q个区间〔Q>>N〕，一个区间就是一个虚结点，这Q个虚结点轮番依次放在N个真实结点上，每个结点上存放Q/N个虚结点。比方说，has(key)的结果是64位，则K的*围在[0,2^64)。把这个*围平均分成2^8份，也就是说Q=256个虚结点，第一个虚结点*围就将是[0,2^16)。再假设一共有N=3个物理结点，则每个结点将平均存放85个虚结点。1号结点上存放的key值*围是[0,2^16)，[2^144,2^160)，[2^304,2^320)……一共85个，二号结点放的是[2^16,2^32)，[2^160,2^176)，[2^320,2^336)等85个。则当再添加一个新结点时，平均每个结点上存放31个，它需要从其他3个上挨次拿44个出来。这样的好处是，结点的添加和删除只需要重新分配虚结点，省去了数据扫描和拆分的工作，而且迁移时负载平均。节点管理〔Membership〕对用户来讲，集群中的所有节点都同等的。实际上，从上面的DHT原理看出，每个节点只负责整个数据集的不同局部。但是，每个节点又必须具备效劳任何特定的key的请求。为了到达这种对用户透明度，每个节点必须维护一些原数据：

-所有其他节点的列表

-所有节点当前状态

-对于一个给的key,其主要负责节点和n-1副本节点〔n为replicationfactor〕。一个节点参加到Token环的处理流程:1.启动gossip效劳(需要和其他节点通信以获得对等信息)2.启动消息效劳3.发起各节点播送各自负载信息4.如果是一个新节点

4.1.如果配置为该新节点指定了token，则使用它，否则

4.2.基于存在的节点的负载信息得到，得到当前负载最大的节点，并从它那里得到token，该token将大约分担它的一半负载

4.3.本地更新并保存这个token

4.4.Gossip状态信息到所有其他节点，接下来将做进展引导了〔bootstraping)

4.5.(开场引导过程)

1)基于keyspace的配置信息，得到可能的负责这局部数据的节点列表

2)向他们发起pipelineIn请求，传递这局部数据5.如果是一个曾经启动过的节点〔即down，可能是人工和错误原因导致),从配置表读取保存的Token6.对本地系统元信息应用这个更新：newToken7.Gossip状态信息，通知其他节点这个节点的新的token〔2〕一个节点离开Token环的处理流程：1.Gossip节点即将leaving的状态2.重新调整Range信息

1.得到所有受影响的range

2.得到新的负责这些range的节点3.计算要传送给其他节点的数据

1〕得到即将离去的节点负责所有区域(＊进一步描述，见成员关系图谱〕

2〕得到当前负责这些区域的所有副本的地址

3〕合计出当该节点离开后，Token的新分配

4〕对各个在第1〕步的Range,重新计算其副本的地址

5〕计算Range之差：最终剩下的Range即是需要的range4.向所有将代替当前节点的节点pipelineout数据5.将当前节点从token元数据中移除6.Gossip消息到其他节点，当前节点已经离开了7.停顿该节点的Gossip效劳8.停顿该节点的消息效劳〔3〕响应成员变化存在的节点在收到节点状态改动时的动作，在不同的状态变迁下虽然有些不同，但大体上执行以下操作：1.状态检验，以确保不会造成冲突2.记录对应节点的该状态，以用于校验3.更新〔增加／修改／删除〕系统元数据4.更新Range信息

1〕得到所有受影响的range

2〕得到新的负责这些range的节点数据分区的复制〔Replication〕为了到达数据高可用性和数据持久型，所有的结点都要求备份。在ConsistentHashingRing上面，用后续结点为前面的结点做备份。在上面的图上，B、C、D为A做备份，一共备份3份。也就是说key值K同时存在4个结点上。虽然K值存在4个结点上，但这4个结点会记在一个persistlist上面，以这个例子来说list=(A,B,C,D)，只有排在第一的结点负责K值的操作以及将它复制到其他结点。当A结点挂掉时，才按persistlist的排序由后续结点接手。这里有两点需要考虑，一个是虚结点的问题，另一个是备份数量的问题。