GFS的主要需求
在论文的一开始首先提出了系统的需求：
- 组件失效是正常的事情而不是异常(exception)，因为在GFS中使用了成百上千台普通的机器。所以需要持续的检测错误，并且能够自动恢复。
- 文件巨大，数个GB的文件是非常常见的。
- 大多数文件的修改(mutation)是以追加(append)为主而不是在覆盖(overwrite)。文件一旦写入完成，之后只会有顺序的读操作。
- 支持原子追加操作，多个客户端可以同时对文件进行追加而不需要额外的同步。
- 高带宽比低延迟更加重要。
GFS的设计
结构
GFS集群包括了单个Master和多个Chunkserver，他们会作为用户级程序运行在Linux系统上。
文件在存储时会划分成固定大小的chunks，每一个chunk都是通过由Master分配的一个不可变且全局唯一的64bitchunk handle来标识。chunkserver通过Linux文件读写的方式来处理chunk。每个chunk在多个chunkserver中储存来提高可靠性。
master维护整个文件系统的元数据，包括了namespace(文件名)、access control(权限)、从文件到chunk的映射表以及每个chunk的位置。master还负责了系统级任务比如chunk lease 管理(后文会涉及)、垃圾回收、chunkserver之间的chunk迁移。master通过心跳包(Heartbeat)与chunkserver进行通信来下达指令或收集状态。
client通过向master通信来获得文件的原数据，但是所有的数据都是直接传输到chunkserver。
client和chunkserver都不缓存数据，因此简化了设计难度。因为client需要的是顺序读取而chunkserver中Linux自身的缓存已经足够了。
Master
因为只有一个master，所以我们需要在文件的读写中减少master的参与程度来避免瓶颈。client并不从master中获取数据。
当client需要读取数据时，通过向master发送请求来获得chunkserver的位置，之后client将chunkserver的位置缓存以供以后使用。
当client获得chunk对应的位置后，client直接向对应的chunkserver发送请求来获得数据。
元数据
master存储的元数据有：文件和chunk的命名空间、从文件到chunk的映射以及每个chunk副本的位置。所有的元数据都是储存在内存中，前两个（命名空间以及映射）都是通过log来持久化储存的，而chunk副本的位置则在每次启动master时向每个chunkserver收集。
master中不持久存储chunk的位置避免了两者的同步问题，master通过与chunkserver的心跳包来监控chunk。
log
log包括了关键元数据的历史记录，同时log也作为并发操作的时间线。
在对文件元数据进行操作前首先写入log(类似WAL)，同时定期保存检查点(checkpoint)来减少启动时间：只需要从最后一个没有损坏的检查点开始重做log即可。
在建立检查点的过程中转换到新的log文件并且在另一个线程中穿件检查点。
一致性模型
GFS的一致性模型比较宽松以提高效率。
对文件元数据的操作(如创建文件)是原子的，通过在master中对元数据进行加锁来实现。
在GFS中提出了两个一致性概念：consistent与defined
- consitent指client读取文件的任何一个副本(replica)都是一样的
- defined指client可以看到上一次修改的完成内容
对文件修改后，会出现以下几种情况：
- 一个修改成功的执行并且没有与并行的操作发生干涉，则文件是defined
- 并行的对文件修改是consistent而是undefined：所有的client都能看到相同的数据，但是数据并不能反映任何一次修改
- 失败的写入是unconsistent：不同的client看到的数据不同
对文件的修改包括了overwrite和追加append，注意这里的追加与文件的追加不同：追加数据时GFS保证数据在文件中至少出现一次，而数据的偏移量是由GFS返回。GFS可能在数据之间插入padding或者重复数据。
对应用的要求
因为会出现重复或padding，所以文件的校验需要由上层应用通过添加额外的字段来完成。
GFS的操作
租约Lease与文件修改顺序
mater会把lease给一个chunk的副本，称这个chunk为primary。primary决定文件修改的执行顺序，其他的副本按照primary的顺序进行修改。
租约机制的用来减少master的开销，租约的默认时间为60s，但是primary可以向master申请延长时间，延长请求通过心跳包与所有的chunkserver通信。所以即使是chunkserver失去了与primary的通信依然可以吊销其租约。
写文件流程
- client向master请求哪一台chunkserver持有了要修改的chunk的租约，如果没有租约则master会分配一个
- master返回primary与其他副本的位置，client缓存位置信息供以后修改。当下次无法联系到primary或者租约过期时再向master请求
- client向所有的副本推送数据，chunkserver会把接收到的数据缓存下来(注意这时候还没有对文件进行修改) <–这是数据流
- 在所有的副本都收到了数据后，client发送写请求给primary。写请求中标识了之前推送的数据，primary为写请求安排序列号用来表示执行的顺序。之后按照顺序对本地文件进行修改
- primary将写请求转发到其他的副本中，每一个副本按照相同顺序执行操作
- 副本向primary返回完成操作
- primary向用户返回。如果操作失败(数据在不同副本间不一致，此时为inconsistent)，client会重新尝试执行操作。
如果对数据的操作超过了一个chunk，client会将其分为多个请求。切分后的多个请求可能会与其他的文件操作交织(interleaved)运行，导致在文件中可能交错出现不同的数据，此时文件为undefined。
数据流
在以上过程中很重要的一点就是解藕(decouple)了控制流和数据流，由此可以有效地利用网络带宽。
在推送数据的过程中，按照拓扑顺序推送，由此推送数据可以并行执行。
原子文件追加
文件追加与写文件类似，不同的是primary收到追加的请求后会检查追加文件是否会使chunk超过预设大小，如果会，会将chunk的剩余部分填充空白，并要求client重新执行操作，将数据追加到新的chunk后。
如果追加操作在任意一个副本上失败，client重新执行该操作，这时会出现同一个chunk但是不同副本间不一致的问题。GFS并不保证所有副本间的文件完全一致，只保证数据至少写一次。所以当追加操作执行时可以保证数据必然写入到所有副本的相同偏移量上。下一次的追加操作会在更高的偏移量执行，
快照
快照可以为文件或者目录创建副本。
快照的创建使用了CoW(copy-on-write)技术：当master收到创建快照的请求后，master吊销涉及chunk的租约，确保了下一次的对文件的写操作需要请求master，此时master便有机会创建chunk的拷贝。
创建chunk的拷贝是在本地的，因为硬盘的读取速度相比网络要快。
Master操作
Namespace管理与锁
文件的元数据由master管理，所以master需要锁机制来确保正确的串行化。
所有的master操作在执行钱都需要获取锁，如果需要操作/d1/d2/.../dn/leaf文件，需要对/d1,/d1/d2/, ..., /d1/d2/.../dn加read lock，对/d1/d2/.../dn/leaf加上对应的read或write lock。
由此设计的锁机制可以允许对同一目录的不同文件进行同时操作。
所有的锁只要在需要时才创建，在不需要时被销毁。同时所有的锁都是按照顺序获取以避免死锁。
Replica管理
chunk副本的放置为了实现两个目标：最大文件可靠性与最大化带宽利用率。所以单纯的将副本放置在不同的机器上是不够的，我们需要将chunk放置在不同的机架中，这不仅可以避免整个机架的损坏，也可以利用多个机架的带宽和进行文件读。但是在写文件时流量需要流过许多个机架，在Google看来这是个合理的tradeoff。
当master创建chunk时，对于机器的选择有三个因素：
- 将chunk放置在硬盘使用率较低的机器上
- 限制每个机器中最近创建chunk的数量，如果一个机器中最近创建了很多chunk，那么接下来将会有很多的写操作
- 同时根据上边说的原因，将chunk分布在不同机架中
当副本的数量少于用户设定的值时，进行副本的重建，需要重建的chunk按照如下顺序：
- 距离用户指定数量的差距
- 优先为未删除的文件进行重建
- 优先为阻塞的client操作进行重建
master按照优先级对chunk进行重建，master限制重建任务的数量与带宽使用避免对client操作影响。
最后，master周期性对副本进行浮躁均衡
垃圾回收
在文件进行删除后，GFS不会立刻回收空间。对文件和chunk进行lazy垃圾回收。
当文件删除后，master记录log，然后将文件名重命名为隐藏名字并且带有删除时间戳。在master的周期性扫描中会清理超过一定时间的标记为隐藏的文件。在此之前，仍然可以通过重命名来恢复文件。同时在master的扫描中，master能够发现孤儿chunk。在与master的心跳包中，chunkserver会报告其拥有的chunk，master会回复不再需要的chunk。
这种垃圾回收机制有几点好处：
- 在大型分布式系统中简单可靠。chunk的创建在某些chunkserver可能成功了，但是在其他上可能失败了，导致留下了master不知道是否存在的chunk。删除副本的请求可能会丢失，master要记录并且重发。相比之下垃圾回收提供了一种统一的方式来清理无用的副本
- 将存储空间回收与日常后台任务合并，可以在master空闲时进行
- 删除请求的延迟提供了错误恢复
同时允许用户手动删除文件
容错
设计系统的最大挑战就是组件时常失效。
高可用性
在集群中提供影子master，影子master只提供只读操作。影子master可能会相较master延迟一段时间。
数据完整性
chunkserver使用校验来检测文件损坏。
每一个chunk分为64K的块，每个块计算32bit校验和，保存在log中。
在读操作时，chunkserver会在返回数据前检查校验和。如果校验失败chunkserver会返回失败，client会去读取另一份副本，同时master对副本进行重建。重建完成后master会通知chunkserver删除掉损坏的副本。
校验和的计算方式为文件追加进行优化，校验和可以进行增量更新。追加的最后一块在下一次读取时能够检测到损坏。
但是在覆写一段数据时需要先检测头和尾的校验之后进行写入。
在空闲时，chunkserver可以扫描检测不活跃的chunk的校验和。