分布式基础学习【一】 —— 分布式文件系统

转载自 ---- http://www.cnblogs.com/duguguiyu/archive/2009/02/22/1396034.html

所谓分布式，在这里，很狭义的指代以Google的三驾马车，GFS、Map/Reduce、BigTable为框架核心的分布式存储和计算系统。通常如我一样初学的人，会以Google这几份经典的论文作为开端的。它们勾勒出了分布式存储和计算的一个基本蓝图，已可窥见其几分风韵，但终究还是由于缺少一些实现的代码和示例，色彩有些斑驳，缺少了点感性。幸好我们还有Open Source，还有Hadoop。Hadoop是一个基于Java实现的，开源的，分布式存储和计算的项目。作为这个领域最富盛名的开源项目之一，它的使用者也是大牌如云，包括了Yahoo，Amazon，Facebook等等（好吧，还可能有校内，不过这真的没啥分量...）。Hadoop本身，实现的是分布式的文件系统HDFS，和分布式的计算（Map/Reduce）框架，此外，它还不是一个人在战斗，Hadoop包含一系列扩展项目，包括了分布式文件数据库HBase（对应Google的BigTable），分布式协同服务ZooKeeper（对应Google的Chubby），等等。。。
如此，一个看上去不错的黄金搭档浮出水面，Google的论文 + Hadoop的实现，顺着论文的框架看具体的实现，用实现来进一步理解论文的逻辑，看上去至少很美。网上有很多前辈们，做过Hadoop相关的源码剖析工作，我关注最多的是这里，目前博主已经完成了HDFS的剖析工作，Map/Reduce的剖析正火热进行中，更新频率之高，剖析之详尽，都是难得一见的，所以，走过路过一定不要错过了。此外，还有很多Hadoop的关注者和使用者贴过相关的文章，比如：这里，这里。也可以去Hadoop的中文站点（不知是民间还是官方...），搜罗一些学习资料。。。
我个人从上述资料中受益匪浅，而我自己要做的整理，与原始的源码剖析有些不同，不是依照实现的模块，而是基于论文的脉络和实现这样系统的基本脉络来进行的，也算，从另一个角度给出一些东西吧。鉴于个人对于分布式系统的理解非常的浅薄，缺少足够的实践经验，深入的问题就不班门弄斧了，仅做梳理和解析，大牛至此，可绕路而行了。。。
一. 分布式文件系统
分布式文件系统，在整个分布式系统体系中处于最低层最基础的地位，存储嘛，没了数据，再好的计算平台，再完善的数据库系统，都成了无水之舟了。那么，什么是分布式文件系统，顾名思义，就是分布式+文件系统。它包含这两个方面的内涵，从文件系统的客户使用的角度来看，它就是一个标准的文件系统，提供了一系列API，由此进行文件或目录的创建、移动、删除，以及对文件的读写等操作。从内部实现来看，分布式的系统则不再和普通文件系统一样负责管理本地磁盘，它的文件内容和目录结构都不是存储在本地磁盘上，而是通过网络传输到远端系统上。并且，同一个文件存储不只是在一台机器上，而是在一簇机器上分布式存储，协同提供服务，正所谓分布式。。。
因此，考量一个分布式文件系统的实现，其实不妨可以从这两方面来分别剖析，而后合二为一。首先，看它如何去实现文件系统所需的基本增删改查的功能。然后，看它如何考虑分布式系统的特点，提供更好的容错性，负载平衡，等等之类的。这二者合二为一，就明白了一个分布式文件系统，整体的实现模式。。。
I. 术语对照
说任何东西，都需要统一一下语言先，不然明明说的一个意思，却容易被理解到另一个地方去。Hadoop的分布式文件系统HDFS，基本是按照Google论文中的GFS的架构来实现的。但是，HDFS为了彰显其不走寻常路的本性，其中的大量术语，都与GFS截然不同。明明都是一个枝上长的土豆，它偏偏就要叫山药蛋，弄得水火不容的，苦了我们看客。秉承老好人，谁也不得罪的方针，文中，既不采用GFS的叫法，也不采用Hadoop的称谓，而是另辟蹊径，自立门户，搞一套自己的中文翻译，为了避免不必要的痛楚，特此先来一帖术语对照表，要不懂查一查，包治百病。。。

文中所用翻译 HDFS中的术语 GFS中的术语 术语解释
主控服务器 NameNode Master 整个文件系统的大脑，它提供整个文件系统的目录信息，并且管理各个数据服务器。
数据服务器 DataNode Chunk Server 分布式文件系统中的每一个文件，都被切分成若干个数据块，每一个数据块都被存储在不同的服务器上，此服务器称之为数据服务器。
数据块 Block Chunk 每个文件都会被切分成若干个块，每一块都有连续的一段文件内容，是存储的基恩单位，在这里统一称做数据块。
数据包 Packet 无 客户端写文件的时候，不是一个字节一个字节写入文件系统的，而是累计到一定数量后，往文件系统中写入一次，每发送一次的数据，都称为一个数据包。
传输块 Chunk 无 在每一个数据包中，都会将数据切成更小的块，每一个块配上一个奇偶校验码，这样的块，就是传输块。
备份主控服务器 SecondaryNameNode 无 备用的主控服务器，在身后默默的拉取着主控服务器 的日志，等待主控服务器牺牲后被扶正。

*注：本文采用的Hadoop是0.19.0版本。
II. 基本架构
1. 服务器介绍
与单机的文件系统不同，分布式文件系统不是将这些数据放在一块磁盘上，由上层操作系统来管理。而是存放在一个服务器集群上，由集群中的服务器，各尽其责，通力合作，提供整个文件系统的服务。其中重要的服务器包括：主控服务器（Master/NameNode），数据服务器（ChunkServer/DataNode），和客户服务器。HDFS和GFS都是按照这个架构模式搭建的。个人觉得，其中设计的最核心内容是：文件的目录结构独立存储在一个主控服务器上，而具体文件数据，拆分成若干块，冗余的存放在不同的数据服务器上。
存储目录结构的主控服务器，在GFS中称为Master，在HDFS中称为NameNode。这两个名字，叫得都有各自的理由，是瞎子摸象各表一面。Master是之于数据服务器来叫的，它做为数据服务器的领导同志存在，管理各个数据服务器，收集它们的信息，了解所有数据服务器的生存现状，然后给它们分配任务，指挥它们齐心协力为系统服务；而NameNode是针对客户端来叫的，对于客户端而言，主控服务器上放着所有的文件目录信息，要找一个文件，必须问问它，由此而的此名。。。
主控服务器在整个集群中，同时提供服务的只存在一个，如果它不幸牺牲的话，会有后备军立刻前赴后继的跟上，但，同一时刻，需要保持一山不容二虎的态势。这种设计策略，避免了多台服务器间即时同步数据的代价，而同时，它也使得主控服务器很可能成为整个架构的瓶颈所在。因此，尽量为主控服务器减负，不然它做太多的事情，就自然而然的晋升成了一个分布式文件系统的设计要求。。。
每一个文件的具体数据，被切分成若干个数据块，冗余的存放在数据服务器。通常的配置，每一个数据块的大小为64M，在三个数据服务器上冗余存放（这个64M，不是随便得来的，而是经过反复实践得到的。因为如果太大，容易造成热点的堆叠，大量的操作集中在一台数据服务器上，而如果太小的话，附加的控制信息传输成本，又太高了。因此没有比较特定的业务需求，可以考虑维持此配置...）。数据服务器是典型的四肢发达头脑简单的苦力，其主要的工作模式就是定期向主控服务器汇报其状况，然后等待并处理命令，更快更安全的存放好数据。。。
此外，整个分布式文件系统还有一个重要角色是客户端。它不和主控服务和数据服务一样，在一个独立的进程中提供服务，它只是以一个类库（包）的模式存在，为用户提供了文件读写、目录操作等APIs。当用户需要使用分布式文件系统进行文件读写的时候，把客户端相关包给配置上，就可以通过它来享受分布式文件系统提供的服务了。。。
2. 数据分布
一个文件系统中，最重要的数据，其实就是整个文件系统的目录结构和具体每个文件的数据。具体的文件数据被切分成数据块，存放在数据服务器上。每一个文件数据块，在数据服务器上都表征为出双入队的一对文件（这是普通的Linux文件），一个是数据文件，一个是附加信息的元文件，在这里，不妨把这对文件简称为数据块文件。数据块文件存放在数据目录下，它有一个名为current的根目录，然后里面有若干个数据块文件和从dir0-dir63的最多64个的子目录，子目录内部结构等同于current目录，依次类推（更详细的描述，参见这里）。个人觉得，这样的架构，有利于控制同一目录下文件的数量，加快检索速度。。。
这是磁盘上的物理结构，与之对应的，是内存中的数据结构，用以表征这样的磁盘结构，方便读写操作的进行。Block类用于表示数据块，而FSDataset类是数据服务器管理文件块的数据结构，其中，FSDataset.FSDir对应着数据块文件和目录，FSDataset.FSVolume对应着一个数据目录，FSDataset.FSVolumeSet是FSVolume的集合，每一个FSDataset有一个FSVolumeSet。多个数据目录，可以放在不同的磁盘上，这样有利于加快磁盘操作的速度。相关的类图，可以参看这里 。。。
此外，与FSVolume对应的，还有一个数据结构，就是DataStorage，它是Storage的子类，提供了升级、回滚等支持。但与FSVolume不一样，它不需要了解数据块文件的具体内容，它只知道有这么一堆文件放这里，会有不同版本的升级需求，它会处理怎么把它们升级回滚之类的业务（关于Storage，可以参见这里）。而FSVolume提供的接口，都基本上是和Block相关的。。。
相比数据服务器，主控服务器的数据量不大，但逻辑更为复杂。主控服务器主要有三类数据：文件系统的目录结构数据，各个文件的分块信息，数据块的位置信息（就数据块放置在哪些数据服务器上...）。在GFS和HDFS的架构中，只有文件的目录结构和分块信息才会被持久化到本地磁盘上，而数据块的位置信息则是通过动态汇总过来的，仅仅存活在内存数据结构中，机器挂了，就灰飞烟灭了。每一个数据服务器启动后，都会向主控服务器发送注册消息，将其上数据块的状况都告知于主控服务器。俗话说，简单就是美，根据DRY原则，保存的冗余信息越少，出现不一致的可能性越低，付出一点点时间的代价，换取了一大把逻辑上的简单性，绝对应该是一个包赚不赔的买卖。。。
在HDFS中，FSNamespacesystem类就负责保管文件系统的目录结构以及每个文件的分块状况的，其中，前者是由FSDirectory类来负责，后者是各个INodeFile本身维护。在INodeFile里面，有一个BlockInfo的数组，保存着与该文件相关的所有数据块信息，BlockInfo中包含了从数据块到数据服务器的映射，INodeFile只需要知道一个偏移量，就可以提供相关的数据块，和数据块存放的数据服务器信息。。。
3、服务器间协议
在Hadoop的实现中，部署了一套RPC机制，以此来实现各服务间的通信协议。在Hadoop中，每一对服务器间的通信协议，都定义成为一个接口。服务端的类实现该接口，并且建立RPC服务，监听相关的接口，在独立的线程处理RPC请求。客户端则可以实例化一个该接口的代理对象，调用该接口的相应方法，执行一次同步的通信，传入相应参数，接收相应的返回值。基于此RPC的通信模式，是一个消息拉取的流程，RPC服务器等待RPC客户端的调用，而不会先发制人主动把相关信息推送到RPC客户端去。。。
其实RPC的模式和原理，实在是没啥好说的，之所以说，是因为可以通过把握好这个，彻底理顺Hadoop各服务器间的通信模式。Hadoop会定义一些列的RPC接口，只需要看谁实现，谁调用，就可以知道谁和谁通信，都做些啥事情，图中服务器的基本架构、各服务所使用的协议、调用方向、以及协议中的基本内容。。。
III. 基本的文件操作
基本的文件操作，可以分成两类，一个是对文件目录结构的操作，比如文件和目录的创建、删除、移动、更名等等；另一个是对文件数据流的操作，包括读取和写入文件数据。当然，文件读和写，是有本质区别的，尤其是在数据冗余的情况下，因此，当成两类操作也不足为过。此外，要具体到读写的类别，也是可以再继续分类下去的。在GFS的论文中，对于分布式文件系统的读写场景有一个重要的假定（其实是从实际业务角度得来的...）：就是文件的读取是由大数据量的连续读取和小数据量的随机读取组成，文件的写入则基本上都是批量的追加写，和偶尔的插入写（GFS中还有大量的假设，它们构成了分布式文件系统架构设计的基石。每一个系统架构都是搭建在一定假设上的，这些假设有些来自于实际业务的状况，有些是因为天生的条件约束，不基于假设理解设计，肯定会有失偏颇...）。在GFS中，对文件的写入分成追加写和插入写都有所支持，但是，在HDFS中仅仅支持追加写，这大大降低了复杂性。关于HDFS与GFS的一些不同，可以参看这里。。。
1. 文件和目录的操作
文件目录的信息，全部囤积在主控服务器上，因此，所有对文件目录的操作，只会直接涉及到客户端和主控服务器。整个目录相关的操作流程基本都是这样的：客户端DFSClient调用ClientProtocol定义的相关函数，该操作通过RPC传送到其实现者主控服务器NameNode那里，NameNode做相关的处理后（很少...），调用FSNamesystem的相关函数。在FSNamesystem中，往往是做一些验证和租约操作，具体的目录结构操作交由FSDirectory的相应函数来操作。最后，依次返回，经由RPC传送回客户端。具体各操作涉及到的函数和具体步骤，参见下表：

相关操作 ClientProtocol / NameNode FSNamesystem FSDirectory 关键步骤
创建文件 create startFile addFile 1. 检查是否有写权限；
2. 检查是否已经存在此文件，如果是覆写，则先进行删除操作；
3. 在指定路径下添加INodeFileUnderConstruction的文件实例；
4. 写日志；
5. 签订租约。
创建目录 mkdirs mkdirs mkdirs 1. 检查指定目录是否是目录；
2. 检查是否有相关权限；
3. 在指定路径的INode下，添加子节点；
4. 写日志。
改名操作 rename renameTo renameTo 1. 检查相关路径的权限；
2. 从老路径下移除，在新路径下添加；
3. 修改相关父路径的修改时间；
4. 写日志；
5. 将租约从老路径移动到新路径下。
删除操作 delete delete delete 1. 如果不是递归删除，确认指定路径是否是空目录；
2. 检查相关权限；
3. 在目录结构上移除相关INode；
4. 修改父路径的修改时间；
5. 将相关的数据块，放入到废弃队列中去，等待处理；
6. 写日志；
7. 废弃相关路径的租约。
设置权限 setPermission setPermission setPermission 1. 检查owner判断是否有操作权限；
2. 修改指定路径下INode的权限；
3. 写日志。
设置用户 setOwner setOwner setOwner 1. 检查是否有操作权限；
2. 修改指定路径下INode的权限；
3. 写日志。
设置时间 setTimes setTimes setTimes 1. 检查是否有写权限；
2. 修改指定路径INode的时间信息；
3. 写日志。

从上表可以看到，其实有的操作本质上还是涉及到了数据服务器，比如文件创建和删除操作。但是，之前提到，主控服务器只于数据服务器是一个等待拉取的地位，它们不会主动联系数据服务器，将指令传输给它们，而是放到相应的数据结构中，等待数据服务器来取。这样的设计，可以减少通信的次数，加快操作的执行速度。。。
另，上述步骤中，有些日志和租约相关的操作，从概念上来说，和目录操作其实没有任何联系，但是，为了满足分布式系统的需求，这些操作是非常有必要的，在此，按下不表。。。
2、文件的读取
不论是文件读取，还是文件的写入，主控服务器扮演的都是中介的角色。客户端把自己的需求提交给主控服务器，主控服务器挑选合适的数据服务器，介绍给客户端，让客户端和数据服务器单聊，要读要写随你们便。这种策略类似于DMA，降低了主控服务器的负载，提高了效率。。。
因此，在文件读写操作中，最主要的通信，发生在客户端与数据服务器之间。它们之间跑的协议是ClientDatanodeProtocol。从这个协议中间，你无法看到和读写相关的接口，因为，在Hadoop中，读写操作是不走RPC机制的，而是另立门户，独立搭了一套通信框架。在数据服务器一端，DataNode类中有一个DataXceiverServer类的实例，它在一个单独的线程等待请求，一旦接到，就启动一个DataXceiver的线程，处理此次请求。一个请求一个线程，对于数据服务器来说，逻辑上很简单。当下，DataXceiver支持的请求类型有六种，具体的请求包和回复包格式，请参见这里，这里，这里。在Hadoop的实现中，并没有用类来封装这些请求，而是按流的次序写下来，这给代码阅读带来挺多的麻烦，也对代码的维护带来一定的困难，不知道是出于何种考虑。。。
相比于写，文件的读取实在是一个简单的过程。在客户端DFSClient中，有一个DFSClient.DFSInputStream类。当需要读取一个文件的时候，会生成一个DFSInputStream的实例。它会先调用ClientProtocol定义getBlockLocations接口，提供给NameNode文件路径、读取位置、读取长度信息，从中取得一个LocatedBlocks类的对象，这个对象包含一组LocatedBlock，那里面有所规定位置中包含的所有数据块信息，以及数据块对应的所有数据服务器的位置信息。当读取开始后，DFSInputStream会先尝试从某个数据块对应的一组数据服务器中选出一个，进行连接。这个选取算法，在当下的实现中，非常简单，就是选出第一个未挂的数据服务器，并没有加入客户端与数据服务器相对位置的考量。读取的请求，发送到数据服务器后，自然会有DataXceiver来处理，数据被一个包一个包发送回客户端，等到整个数据块的数据都被读取完了，就会断开此链接，尝试连接下一个数据块对应的数据服务器，整个流程，依次如此反复，直到所有想读的都读取完了为止。。。
3、文件的写入
文件读取是一个一对一的过程，一个客户端，只需要与一个数据服务器联系，就可以获得所需的内容。但是，写入操作，则是一个一对多的流程。一次写入，需要在所有存放相关数据块的数据服务器都保持同步的更新，有任何的差池，整个流程就告失败。。。
在分布式系统中，一旦涉及到写入操作，并发处理难免都会沦落成为一个变了相的串行操作。因为，如果不同的客户端如果是任意时序并发写入的话，整个写入的次序无法保证，可能你写半条记录我写半条记录，最后出来的结果乱七八糟不可估量。在HDFS中，并发写入的次序控制，是由主控服务器来把握的。当创建、续写一个文件的时候，该文件的节点类，由INodeFile升级成为INodeFileUnderConstruction，INodeFileUnderConstruction是INodeFile的子类，它起到一个锁的作用。如果当一个客户端想创建或续写的文件是INodeFileUnderConstruction，会引发异常，因为这说明这个此处有爷，请另寻高就，从而保持了并发写入的次序性。同时，INodeFileUnderConstruction有包含了此时正在操作它的客户端的信息以及最后一个数据块的数据服务器信息，当追加写的时候可以更快速的响应。。。
与读取类似，DFSClient也有一个DFSClient.DFSOutputStream类，写入开始，会创建此类的实例。DFSOutputStream会从NameNode上拿一个LocatedBlock，这里面有最后一个数据块的所有数据服务器的信息。这些数据服务器每一个都需要能够正常工作（对于读取，只要还有一个能工作的就可以实现...），它们会依照客户端的位置被排列成一个有着最近物理距离和最小的序列（物理距离，是根据机器的位置定下来的...），这个排序问题类似于著名旅行商问题，属于NP复杂度，但是由于服务器数量不多，所以用最粗暴的算法，也并不会看上去不美。。。
文件写入，就是在这一组数据服务器上构造成数据流的双向流水线。DFSOutputStream，会与序列的第一个数据服务器建立Socket连接，发送请求头，然后等待回应。DataNode同样是建立DataXceiver来处理写消息，DataXceiver会依照包中传过来的其他服务器的信息，建立与下一个服务器的连接，并生成类似的头，发送给它，并等待回包。此流程依次延续，直到最后一级，它发送回包，反向着逐级传递，再次回到客户端。如果一切顺利，那么此时，流水线建立成功，开始正式发送数据。数据是分成一个个数据包发送的，所有写入的内容，被缓存在客户端，当写满64K，会被封装成DFSOutputStream.Packet类实例，放入DFSOutputStream的dataQueue队列。DFSOutputStream.DataStreamer会时刻监听这个队列，一旦不为空，则开始发送，将位于dataQueue队首的包移动到ackQueue队列的队尾，表示已发送但尚未接受回复的包队列。同时启动ResponseProcessor线程监听回包，直到收到相应回包，才将发送包从ackQueue中移除，表示成功。每一个数据服务器的DataXceiver收到了数据包，一边写入到本地文件中去，一边转发给下一级的数据服务器，等待回包，同前面建立流水线的流程。。。
当一个数据块写满了之后，客户端需要向主控服务器申请追加新的数据块。这个会引起一次数据块的分配，成功后，会将新的数据服务器组返还给客户端。然后重新回到上述流程，继续前行。。。
关于写入的流程，还可以参见这里。此外，写入涉及到租约问题，后续会仔细的来说。。。
IV. 分布式支持
如果单机的文件系统是田里勤恳的放牛娃，那么分布式文件系统就是刀尖上讨饭吃的马贼了。在分布式环境中，有太多的意外，数据随时传输错误，服务器时刻准备牺牲，很多平常称为异常的现象，在这里都需要按照平常事来对待。因此，对于分布式文件系统而言，仅仅是满足了正常状况下文件系统各项服务还不够，还需要保证分布式各种意外场景下健康持续的服务，否则，将一无是处。。。
1、服务器的错误恢复
在分布式环境中，哪台服务器牺牲都是常见的事情，牺牲不可怕，可怕的是你都没有时刻准备好它们会牺牲。作为一个合格的分布式系统，HDFS当然时刻准备好了前赴后继奋勇向前。HDFS有三类服务器，每一类服务器出错了，都有相应的应急策略。。。
a. 客户端
生命最轻如鸿毛的童鞋，应该就是客户端了。毕竟，做为一个文件系统的使用者，在整个文件系统中的地位，难免有些归于三流。而作为客户端，大部分时候，牺牲了就牺牲了，没人哀悼，无人同情，只有在在辛勤写入的时候，不幸辞世（机器挂了，或者网络断了，诸如此类...），才会引起些恐慌。因为，此时此刻，在主控服务器上对应的文件，正作为INodeFileUnderConstruction活着，仅仅为占有它的那个客户端服务者，做为一个专一的文件，它不允许别的客户端染指。这样的话，一旦占有它的客户端服务者牺牲了，此客户端会依然占着茅坑不拉屎，让如花似玉INodeFileUnderConstruction孤孤单单守寡终身。这种事情当然无法容忍，因此，必须有办法解决这个问题，办法就是：租约。。。
租约，顾名思义，就是当客户端需要占用某文件的时候，与主控服务器签订的一个短期合同。这个合同有一个期限，在这个期限内，客户端可以延长合同期限，一旦超过期限，主控服务器会强行终止此租约，将这个文件的享用权，分配给他人。。。
在打开或创建一个文件，准备追加写之前，会调用LeaseManager的addLease方法，在指定的路径下与此客户端签订一份租约。客户端会启动DFSClient.LeaseChecker线程，定时轮询调用ClientProtocol的renewLease方法，续签租约。在主控服务器一端，有一个LeaseManager.Monitor线程，始终在轮询检查所有租约，查看是否有到期未续的租约。如果一切正常，该客户端完成写操作，会关闭文件，停止租约，一旦有所意外，比如文件被删除了，客户端牺牲了，主控服务器都会剥夺此租约，如此，来避免由于客户端停机带来的资源被长期霸占的问题。。。
b. 数据服务器
当然，会挂的不只是客户端，海量的数据服务器是一个更不稳定的因素。一旦某数据服务器牺牲了，并且主控服务器被蒙在鼓中，主控服务器就会变相的欺骗客户端，给它们无法连接的读写服务器列表，导致它们处处碰壁无法工作。因此，为了整个系统的稳定，数据服务器必须时刻向主控服务器汇报，保持主控服务器对其的完全了解，这个机制，就是心跳消息。在HDFS中，主控服务器NameNode实现了DatanodeProtocol接口，数据服务器DataNode会在主循环中，不停的调用该协议中的sendHeartbeat方法，向NameNode汇报状况。在此调用中，DataNode会将其整体运行状况告知NameNode，比如：有多少可用空间、用了多大的空间，等等之类。NameNode会记住此DataNode的运行状况，作为新的数据块分配或是负载均衡的依据。当NameNode处理完成此消息后，会将相关的指令封装成一个DatanodeCommand对象，交还给DataNode，告诉数据服务器什么数据块要删除什么数据块要新增等等之类，数据服务器以此为自己的行动依据。。。
但是，sendHeartbeat并没有提供本地的数据块信息给NameNode，那么主控服务器就无法知道此数据服务器应该分配什么数据块应该删除什么数据块，那么它是如何决定的呢？答案就是DatanodeProtocol定义的另一个方法，blockReport。DataNode也是在主循环中定时调用此方法，只是，其周期通常比调用sendHeartbeat的更长。它会提交本地的所有数据块状况给NameNode，NameNode会和本地保存的数据块信息比较，决定什么该删除什么该新增，并将相关结果缓存在本地对应的数据结构中，等待此服务器再发送sendHeartbeat消息过来的时候，依照这些数据结构中的内容，做出相应的DatanodeCommand指令。blockReport方法同样也会返回一个DatanodeCommand给DataNode，但通常，只是为空（只有出错的时候不为空），我想，增加缓存，也许是为了确保每个指令都可以重复发送并确定被执行。。。
c. 主控服务器
当然，作为整个系统的核心和单点，含辛茹苦的主控服务器含泪西去，整个分布式文件服务集群将彻底瘫痪。如何在主控服务器牺牲后，提拔新的主控服务器并迅速使其进入工作角色，就成了系统必须考虑的问题。解决策略就是：日志。。。
其实这并不是啥新鲜东西，一看就知道是从数据库那儿偷师而来的。在主控服务器上，所有对文件目录操作的关键步骤（具体文件内容所处的数据服务器，是不会被写入日志的，因为这些内容是动态建立的...），都会被写入日志。另外，主控服务器会在某些时刻，将当下的文件目录完整的序列化到本地，这称为镜像。一旦存有镜像，镜像前期所写的日志和其他镜像，都纯属冗余，其历史使命已经完成，可以报废删除了。在主控服务器不幸牺牲，或者是战略性的停机修整结束，并重新启动后，主控服务器会根据最近的镜像 + 镜像之后的所有日志，重建整个文件目录，迅速将服务能力恢复到牺牲前的水准。。。
对于数据服务器而言，它们会通过一些手段，迅速得知顶头上司的更迭消息。它们会立刻转投新东家的名下，在新东家旗下注册，并开始向其发送心跳消息，这个机制，可能用分布式协同服务来实现，这里不说也罢。。。
在HDFS的实现中，FSEditLog类是整个日志体系的核心，提供了一大堆方便的日志写入API，以及日志的恢复存储等功能。目前，它支持若干种日志类型，都冠以OP_XXX，并提供相关API，具体可以参见这里。为了保证日志的安全性，FSEditLog提供了EditLogFileOutputStream类作为写入的承载类，它会同时开若干个本地文件，然后依次写入，防止日志的损坏导致不可估量的后果。在FSEditLog上面，有一个FSImage类，存储文件镜像并调用FSEditLog对外提供相关的日志功能。FSImage是Storage类的子类，如果对数据块的讲述有所印象的话，你可以回忆起来，凡事从此类派生出来的东西，都具有版本性质，可以进行升级和回滚等等，以此，来实现产生镜像是对原有日志和镜像处理的复杂逻辑。。。
目前，在HDFS的日志系统中，有些地方与GFS的描述有所不同。在HDFS中，所有日志文件和镜像文件都是本地文件，这就相当于，把日志放在自家的保险箱中，一旦主控服务器挂了，别的后继而上的服务器也无法拿到这些日志和镜像，用于重振雄风。因此，在HDFS中，运行着一个SecondaryNameNode服务器，它做为主控服务器的替补，隐忍厚积薄发为篡位做好准备，其中，核心内容就是：定期下载并处理日志和镜像。SecondaryNameNode看上去像客户端一样，与NameNode之间，走着NamenodeProtocol协议。它会不停的查看主控服务器上面累计日志的大小，当达到阈值后，调用doCheckpoint函数，此函数的主要步骤包括：

    首先是调用startCheckpoint做一些本地的初始化工作；
    然后调用rollEditLog，将NameNode上此时操作的日志文件从edit切到edit.new上来，这个操作瞬间完成，上层写日志的函数完全感觉不到差别；
    接着，调用downloadCheckpointFiles，将主控服务器上的镜像文件和日志文件都下载到此候补主控服务器上来；
    并调用doMerge，打开镜像和日志，将日志生成新的镜像，保存覆盖；
    下一步，调用putFSImage把新的镜像上传回NameNode；
    再调用rollFsImage，将镜像换成新的，在日志从edit.new改名为edit；
    最后，调用endCheckpoint做收尾工作。

整个算法涉及到NameNode和SecondaryNameNode两个服务器，最终结果是NameNode和SecondaryNameNode都依照算法进行前的日志生成了镜像。而两个服务器上日志文件的内容，前者是整个算法进行期间所写的日志，后者始终不会有任何日志。当主控服务器牺牲的时候，运行SecondaryNameNode的服务器立刻被扶正，在其上启动主控服务，利用其日志和镜像，恢复文件目录，并逐步接受各数据服务器的注册，最终向外提供稳定的文件服务。。。
同样的事情，GFS采用的可能是另外一个策略，就是在写日志的时候，并不局限在本地，而是同时书写网络日志，即在若干个远程服务器上生成同样的日志。然后，在某些时机，主控服务器自己，生成镜像，降低日志规模。当主控服务器牺牲，可以在拥有网络日志的服务器上启动主控服务，升级成为主控服务器。。。
GFS与HDFS的策略相比较，前者是化整为零，后者则是批量处理，通常我们认为，批量处理的平均效率更高一些，且相对而言，可能实现起来容易一些，但是，由于有间歇期，会导致日志的丢失，从而无法100%的将备份主控服务器的状态与主控服务器完全同步。。。
2、数据的正确性保证
在复杂纷繁的分布式环境中，我们坚定的相信，万事皆有可能。哪怕各个服务器都舒舒服服的活着，也可能有各种各样的情况导致网络传输中的数据丢失或者错误。并且在分布式文件系统中，同一份文件的数据，是存在大量冗余备份的，系统必须要维护所有的数据块内容完全同步，否则，一人一言，不同客户端读同一个文件读出不同数据，用户非得疯了不可。。。
在HDFS中，为了保证数据的正确性和同一份数据的一致性，做了大量的工作。首先，每一个数据块，都有一个版本标识，在Block类中，用一个长整型的数generationStamp来表示版本信息（Block类是所有表示数据块的数据结构的基类），一旦数据块上的数据有所变化，此版本号将向前增加。在主控服务器上，保存有此时每个数据块的版本，一旦出现数据服务器上相关数据块版本与其不一致，将会触发相关的恢复流程。这样的机制保证了各个数据服务器器上的数据块，在基本大方向上都是一致的。但是，由于网络的复杂性，简单的版本信息无法保证具体内容的一致性（因为此版本信息与内容无关，可能会出现版本相同，但内容不同的状况）。因此，为了保证数据内容上的一致，必须要依照内容，作出签名。。。
当客户端向数据服务器追加写入数据包时，每一个数据包的数据，都会切分成512字节大小的段，作为签名验证的基本单位，在HDFS中，把这个数据段称为Chunk，即传输块（注意，在GFS中，Chunk表达的是数据块...）。在每一个数据包中，都包含若干个传输块以及每一个传输块的签名，当下，这个签名是根据Java SDK提供的CRC算法算得的，其实就是一个奇偶校验。当数据包传输到流水线的最后一级，数据服务器会对其进行验证（想一想，为什么只在最后一级做验证，而不是每级都做...），一旦发现当前的传输块签名与在客户端中的签名不一致，整个数据包的写入被视为无效，Lease Recover（租约恢复）算法被触发。。。
从基本原理上看，这个算法很简单，就是取所有数据服务器上此数据块的最小长度当作正确内容的长度，将其他数据服务器上此数据块超出此长度的部分切除。从正确性上看，此算法无疑是正确的，因为至少有一个数据服务器会发现此错误，并拒绝写入，那么，如果写入了的，都是正确的；从效率上看，此算法也是高效的，因为它避免了重复的传输和复杂的验证，仅仅是各自删除尾部的一些内容即可。但从具体实现上来看，此算法稍微有些绕，因为，为了降低本已不堪重负的主控服务器的负担，此算法不是由主控服务器这个大脑发起的，而是通过选举一个数据服务器作为Primary，由Primary发起，通过调用与其他各数据服务器间的InterDatanodeProtocol协议，最终完成的。具体的算法流程，参见LeaseManager类上面的注释。需要说明的是此算法的触发时机和发起者。此算法可以由客户端或者是主控服务器发起，当客户端在写入一个数据包失败后，会发起租约恢复。因为，一次写入失败，不论是何种原因，很有可能就会导致流水线上有的服务器写了，有的没写，从而造成不统一。而主控服务器发起的时机，则是在占有租约的客户端超出一定时限没有续签，这说明客户端可能挂了，在临死前可能干过不利于数据块统一的事情，作为监督者，主控服务器需要发起一场恢复运动，确保一切正确。。。
3、负载均衡
负载的均衡，是分布式系统中一个永恒的话题，要让大家各尽其力齐心干活，发挥各自独特的优势，不能忙得忙死闲得闲死，影响战斗力。而且，负载均衡也是一个复杂的问题，什么是均衡，是一个很模糊的概念。比如，在分布式文件系统中，总共三百个数据块，平均分配到十个数据服务器上，就算均衡了么？其实不一定，因为每一个数据块需要若干个备份，各个备份的分布应该充分考虑到机架的位置，同一个机架的服务器间通信速度更快，而分布在不同机架则更具有安全性，不会在一棵树上吊死。。。
在这里说的负载均衡，是宽泛意义上的均衡过程，主要涵盖两个阶段的事务，一个是在任务初始分配的时候尽可能合理分配，另一个是在事后时刻监督及时调整。。。
在HDFS中，ReplicationTargetChooser类，是负责实现为新分配的数据块寻找婆家的。基本上来说，数据块的分配工作和备份的数量、申请的客户端地址（也就是写入者）、已注册的数据服务器位置，密切相关。其算法基本思路是只考量静态位置信息，优先照顾写入者的速度，让多份备份分配到不同的机架去。具体算法，自行参见源码。此外，HDFS的Balancer类，是为了实现动态的负载调整而存在的。Balancer类派生于Tool类，这说明，它是以一个独立的进程存在的，可以独立的运行和配置。它运行有NamenodeProtocol和ClientProtocol两个协议，与主控服务器进行通信，获取各个数据服务器的负载状况，从而进行调整。主要的调整其实就是一个操作，将一个数据块从一个服务器搬迁到另一个服务器上。Balancer会向相关的目标数据服务器发出一个DataTransferProtocol.OP_REPLACE_BLOCK消息，接收到这个消息的数据服务器，会将数据块写入本地，成功后，通知主控服务器，删除早先的那个数据服务器上的同一块数据块。具体的算法请自行参考源码。。。
4、垃圾回收
对于垃圾，大家应该耳熟能详了，在分布式文件系统而言，没有利用价值的数据块备份，就是垃圾。在现实生活中，我们提倡垃圾分类，为了更好的理解分布式文件系统的垃圾收集，搞个分类也是很有必要的。基本上，所有的垃圾都可以视为两类，一类是由系统正常逻辑产生的，比如某个文件被删除了，所有相关的数据块都沦为垃圾了，某个数据块被负载均衡器移动了，原始数据块也不幸成了垃圾了。此类垃圾最大的特点，就是主控服务器是生成垃圾的罪魁祸首，也就是说主控服务器完全了解有哪些垃圾需要处理。另外还有一类垃圾，是由于系统的一些异常症状产生的，比如某个数据服务器停机了一段，重启之后发现其上的某个数据块已经在其他服务器上重新增加了此数据块的备份，它上面的那个备份过期了失去价值了，需要被当作垃圾来处理了。此类垃圾的特点恰恰相反，主控服务器无法直接了解到垃圾状况，需要曲线救国。。。
在HDFS中，第一类垃圾的判定自然很容易，在一些正常的逻辑中产生的垃圾，全部被塞进了FSNamesystem的recentInvalidateSets这个Map中。而第二类垃圾的判定，则放在数据服务器发送其数据块信息来的过程中，经过与本地信息的比较，可以断定，此数据服务器上有哪些数据块已经不幸沦为垃圾。同样，这些垃圾也被塞到recentInvalidateSets中去。在与数据服务器进行心跳交流的过程中，主控服务器会将它上面有哪些数据块需要删除，数据服务器对这些数据块的态度是，直接物理删除。在GFS的论文中，对如何删除一个数据块有着不同的理解，它觉着应该先缓存起来，过几天没人想恢复它了再删除。在HDFS的文档中，则明确表示，在现行的应用场景中，没有需要这个需求的地方，因此，直接删除就完了。这说明，理念是一切分歧的根本：）。。。
V. 总结
整个分布式文件系统，计算系统，数据库系统的设计理念，基本是一脉相承的。三类服务器、作为单点存在的核心控制服务器、基于日志的恢复机制、基于租约的保持联系机制、等等，在后续分布式计算系统和分布式数据库中都可以看到类似的影子，在分布式文件系统这里，我详述了这些内容，可能在后续就会默认知道而说的比较简略了。而刨去这一些，分布式文件系统中最大特点，就是文件块的冗余存储，它直接导致了较为复杂的写入流程。当然，虽说分布式文件系统在分布式计算和数据库中都有用到，但如果对其机理没有兴趣，只要把它当成是一个可以在任何机器上使用的文件系统，就不会对其他上层建筑的理解产生障碍。。。