GFS, Big Table, Map Reduce称为Google的三驾马车，是许多基础服务的基石

GFS于2003年提出，是一个分布式的文件系统，与此前的很多分布式系统的前提假设存在很大的不同，适用于以下场景

      1）认为组件失效是一种常态，提供了容错机制，自动负载均衡，使得分布式文件系统可以在廉价机器上运行

      2）面向大文件存储，系统主要的工作负载是大规模的流式读取，写操作主要是追加方式写，很少有随机写

      3）一次写入，多次读取，例如互联网上的网页存储

    一个GFS集群由一台master服务器（有备份），多台chunk服务器组成，客户端，架构上比较简单。

  Chunkserver：数据存储节点，文件被分割为固定大小的Chunk，每个Chunk被唯一标识，默认情况下，Chunk存储为3个副本

  Chunk：每个文件至少存储为一个chunk，每个chunk以普通linux文件存储，chuck尺寸大小选择是一个关键的设计参数，默认64MB，每个chunk有全局64位唯一标识符

Chunk尺寸较大优缺点？

较大：减小master上元数据大小，放在内存，减少client与master交互

缺点：小文件会存储为一个Chunk，多个Client同时对单个小文件多次操作时，存放这个Chunk的ChunkServer会成为热点

  GFS master：管理所有元数据信息；租约管理；集群Chunk迁移；无用Chunk回收；

                        元信息(metadata)主要有三类：命名空间、文件和Chunk的映射关系(一个文件包含哪些Chunk)、每个Chunk副本的位置信息。元信息存储在内存中，加快处理速度。

前两类元信息会以操作日志文件存储在本地磁盘上，并复制到远程Master备机上，容灾需要。Chunk副本的位置信息为Master通过心跳向各个ChunkServer轮询获得，无需持久化，避免了ChunkServer变更时的Master和ChunkServer的数据同步问题。                                            

  GFS client：与 Master节点的通信只获取元数据，所有的数据操作都直接和 Chunk 服务器进行交互，GFS提供了一套类似传统文件系统的 API 接口

读流程：客户端向master请求<file_name, chunk index>，master返回chunk的位置信息，客户端再向对应的chunkserver请求

写流程：写通常又被细分成write和append，write是对已有数据的更新(指定偏移量offset)，而append则是在文件的末尾增加新的数据。

 GFS 供了一种原子的append操作，即Client只需指定要写入数据（而不用指定偏移值），GFS就保证至少有一次原子的写入操作执行成功，并返回追加成功的数据的起始位置的偏移值给Client。记录追加的引入是为了在分布式应用中，减少很多Client并行对同份数据写入的同步机制开销，例如使用一个分布式的锁管理器。

写操作会在所有副本上执行。

     Master 节点选择某个副本为主 Chunk，并给其建立租约，租约默认60s，然后主Chunk协调客户端的写入，保证多副本之间维持一个全局统一的更新顺序。

     使用租约机制来保障数据多个副本变更顺序的一致性，租约序列由主Chunk产生，chunk 租约机制的设计主要是为了减轻 Master 的负担，由主副本所在的 chunkserver 来承担流水线顺序的安排。

     租约本质上是一种有时间限制的锁：租约的持有者（chunk的某个副本）需要定期向Master申请续约。如果超过租约的期限，那么该租约会被强制收回并重新分配给其他副本。

数据写入流程：

1. 客户端向Master查询待写入的chunk的副本信息；
2. Master返回副本列表，第一项为主副本，即当前持有租约的副本；
3. 客户端向多副本推送待写入数据，这里的推送是指将数据发送至chunkserver，chunkserver会缓存这些数据，此时数据并不落盘；
4. 客户端向主副本发起sync请求；
5. 主副本将数据写入本地的同时通知其他副本将数据写入各自节点，此时数据方才落盘；
6. 主副本等待所有从副本的sync响应；
7. 主副本给客户端返回写入成功响应

这里需要说明的是客户端的数据写入被拆成了数据推送和sync两个子命令，这是因为：

• 数据推送过程，客户端可以根据网络拓扑情况进行推送路径优化，Google的网络拓扑较简单，通过IP地址就可计算出节点“距离”。客户端可以选择距离自己最近的副本推送数据，然后再由该副本选择下一个距离自己最近的副本进行数据推送，直到数据被扩散至所有副本，由于该过程仅仅是将数据推送给chunkserver并保存在内存缓冲区中，因此，无需保证数据推送顺序；
• sync是将上面推送的数据落盘，需要保证多副本上数据写入顺序的一致性，该指令必须由主副本确定数据更新顺序然后将该顺序通知给其他从副本。
  
  主副本等待sync过程中写某个从副本失败，如何处理？
  客户端收到请求失败消息后，然后对步骤3到7全部重试
  
  

    GFS定义了下列几种一致性：总体而言，是弱一致性

    defined：状态已定义，从客户端角度来看，客户端完全了解已写入集群的数据。即当一个客户端写文件，之后读能否读出之前写的文件，也就是说和自己的写的是否一致。

    consistent：客户端来看chunk多副本的数据完全一致，但不一定defined

    unconsistent：多副本数据不一致

    undefined：数据未定义

undefined

串行write

10

60

90

客户端A写数据，偏移量[10,60)

客户端B写数据，偏移量[60,90)

并行write

10

50

60

客户端A写数据，偏移量[10,60)

客户端B写数据，偏移量[50,90)

90

defined

consistent

undefined

consistent

     无论是串行write还是并行write，一旦失败，多个chunk副本上的数据可能都不一致了，其次，客户端从不同的副本上读出的数据也不一样（可能某些副本成功而某些副本失败），因此，必然也是undefined，也是inconsistent

draw.io evaluation version

append

10

60

90

客户端A追加数据，返回offset=10

客户端B追加数据，返回offset=60

客户端A追加数据，返回offset=90

defined

150

append fail

10

60

客户端A追加数据，第一次副本1写成功，副本2写失败，立刻重试，第二次副本1，2均写成功，最终返回offset=60

interspersed with inconsistent

10

60

110

110

副本1

副本2

    对于append操作，客户端无需指定offset，由chunk主副本根据当前文件大小决定写入offset，在写入成功后将该offset返回给客户端，因此，客户端能够根据offset确切知道写入结果，无论是串行写入还是并发写入，其行为是defined。对于如果append第一次失败，导致多副本在10-60的数据可能不一致，但接下来重试成功，从60至110之间的数据一致，因此，其状态是interspersed with inconsistent（部分不一致）。

   注：追加操作和写文件不一样，追加操作不是幂等的，当一次追加操作没有成功，客户端重试时，不同副本可能被追加了不同次数，也可能填充数据。

1）命名空间管理

      命名空间的修改通过锁保证为原子性的。

      在逻辑上，GFS 的名称空间就是一个全路径和元数据映射关系的查找表。利用前缀压缩，这个表可以高效的存储在内存中。在存储名称空间的树型结构上，每个节点(绝对路径的文件名或绝对路径的目录名)都有一个关联的读写锁。采用这种锁方案的优点是支持对同一目录的并行操作，比如，每一个文件操作需要获取父目录读锁和目标文件写锁。目录名的读取锁防止目录被删除、 改名以及被快照。

如何避免死锁？

锁的获取依据全局一致的顺序，先按名字空间层次排序，同一层次按字典序排序

2）副本位置分布   

    GFS中chunk以多副本存储，以提高数据可靠性。一个好的副本位置定义算法满足下面特性：

1. 最大化数据可靠性，例如，不能将所有副本存放在同一个磁盘或者物理机器上；
2. 最大化网络带宽利用率，有效利用多个机架的整合带宽

3）Chunk的创建、负载均衡     

      当 Master 节点创建一个 Chunk 时，它会选择在哪里放置初始的空的副本，需要考虑以下几个因素：

1. 选择存储空间利用率最低的节点和磁盘；
2. 选择最近一段时间内新建chunk数量较少的节点和磁盘；
3. 将多个副本分散在不同的机架上。 

4）垃圾回收 

     所有 Master 节点不能识别的副本都是“垃圾”。我们很容易能得到 Chunk 的所有引用: 它们都只存储在 Master 服务器上的文件到chunk的映射表中。 我们也可以得到所有 Chunk 的副本:它们都以 Linux 文件的形式存储在 Chunk 服务器的指定目录下。 

     GFS 在文件删除后不会立刻回收可用的物理空间，空间回收采用惰性的策略，周期性的常规垃圾扫描才回收物理空间，并在 Master 节点相对空闲的时候完成。

      具体流程：Client提交文件删除操作，Master将删除操作记录到日志，并将对应文件名改为包含删除时间戳的隐藏文件名（改名字，并没有回收物理空间。Master周期性对名字空间做常规垃圾扫描，会在名字空间中删除3天前（时间可配置）的隐藏文件及元数据。ChunkServer在与Master的心跳信息中，得知哪些Chunk的元数据不存在了，便可实际回收其物理空间。直到文件被真正删除，它们仍旧可以用新的特殊的名字读取，也可以通过把隐藏文件改名为正常显示的文件名的方式“反删除”。当隐藏文件被从名称空间中删除，Master 服务器内存中保存的这个文件的相关元数据才会被删除，这也有效的切断了文件和它包含的所有 Chunk 的连接。    

     优点：设计简单，批量执行，防误删

     缺点：存储的开销，阻碍用户调优存储空间使用，特别是当存储空间比较紧缺的时候。我们允许用户为命名空间的不同部分设定不同的复制和回收策略。例如，用户可以指定某些目录树下面的文件不做复制，删除的文件被即时的移除。

• 快照对系统当前状态进行的一次拍照，用户可以在任意时刻回滚到快照的状态，GFS使用Copy-On-Write技术实现Snapshot。
• Master节点收到客户端的快照请求时，Master并没有立即对指定Chunk拷贝，而只拷贝其元数据并对指定Chunk的引用计数增1，等到Client需要修改指定Chunk时，再在本地复制，并却保新Chunk拥有租约。

      具体流程是： 

• 收回Snapshot请求覆盖的文件chunk上的租约；
• 操作元数据完成元数据拷贝；
• 客户端要写入该文件的Chunk时，Master通知该Chunk所在ChunkServer进行本地拷贝，之所以本地创建是因为可以避免跨节点之间的数据拷贝，节省网络带宽；
• 发放租约给拷贝Chunk；
• 返回拷贝Chunk的位置信息，接下来客户端的更新流程与正常的没有区别。

   1）高可用性

•  遵循的2个简单策略：1 快速恢复  2 复制
• 快速恢复：Master或ChunkServer关闭（正常/异常），都被设计在数秒内可恢复状态并重启。Client和其他服务器发现请求超时，会重连重启的Server
• Chunk的复制：当ChunkServer关闭或Chksum校验出损坏的Chunk副本，Master都会通过复制已有Chunk副本来保障副本个数 
• Master的复制：CheckPoint文件+操作日志完成Master的恢复。此外，GFS还有些“影子”Master，在Master宕机时提供GFS的只读访问

   2）数据完整性        

• 每个ChunkServer独立维护Checksum来校验自己副本的完整性，每个Chunk块都对应一个32位的Checksum。和其它元数据一样， Checksum 与其它的用户数据是分开的，并且保存在内存和硬盘上，同时也记录操作日志。
  独立维护原因：

• 跨Chunk服务器比较副本开销大；
• 追加操作可能造成数据的字节级别不一致，无法通过比较副本判断完整性。

• 对读操作，在把数据返回给客户端或者其它的 Chunk 服务器之前，Chunk 服务器会校验读取操作涉及的范围内的块的checksum, 当checksum校验到数据不正确，ChunkServer会做两件事：1、返回给Client错误信息，让Client读取其他Chunk副本   2、通知Master，请求Chunk副本复制
• 当ChunkServer空闲时，其会周期性扫描不活动的Chunk块，检验数据完整性 
• 读操作的Checksum：只取Chunk小部分额外相关数据进行校验，客户端每次把读取操作对齐在Chunk块的边界上
• 记录追加操作的Checksum（高度优化）：只增量更新最后一个不完整Chunk块的Checksum
• 写操作的Checksum：先读取和校验被写操作覆盖的第一个和最后一个Chunk块，写操作完成后再重新计算和写入Chunksum

Colossus

Google内部至少运行着200多个GFS集群，最大的集群有几千台服务器，数据量是PB级别的，并且服务于多个Google服务，包括Google搜索和Google Earth等。GFS对于大文件很友好，吞吐量很大，但是延迟较高，所以并不很适合新的一些Google产品，比YouTube、Gmail和非常强调实时性的Caffeine搜索引擎等，Google在2009年已经在开发下一代GFS，代号为“Colossus”。

 几个改进如下：

• 支持分布式 Master节点来提升高可用性并能支撑更多文件，将所有管理数据进行数据分片后分配到不同的Master服务器上
• chunk节点能支持1MB大小，对小文件友好，以支撑低延迟应用的需要
• 数据冗余技术：Chunk数据的多个备份虽然增加了系统可用性，但是付出了更多的存储成本，一种常见的折中方案是采用纠删码算法。纠删码通过技术含量较高的算法，提供和副本近似的可靠性，同时减小了额外所需冗余设备的数量，从而提高了存储设备的利用率，但纠删码所带来的额外负担主要是计算量和数倍的网络负载，优缺点都相当明显

HDFS

Hadoop的分布式文件存储系统，完整实现了GFS论文中的概念模型，在某些方面做了简化处理：

• HDFS 在考虑写入模型时做了一个简化，就是同一时刻只允许一个写入者或追加者，在这个模型下同一个文件同一个时刻只允许一个客户端写入或追加，而 GFS 则允许同一时刻多个客户端并发写入或追加同一文件。
• GFS 和 HDFS 的写入流程都采用了流水线方式，但 HDFS 没有分离数据流和控制流，HDFS 的数据流水线写入在网络上的传输顺序与最终写入文件的顺序一致，而 GFS 数据在网络上的传输顺序与最终写入文件的顺序可能不一致。