最近了解到Google的大数据三驾马车，觉得是一个很好的学习机会，所以应该写一下总结。但是同质化的讲义太多了，不差我这一个，加上也懒，所以权当这是一个辅助记忆的总结。先从GFS开始吧，一个经典的分布式文件系统。至今影响着现在我实习部门的分布式文件系统设计（连名字都是抄的，把Google's G改成了W。不过，架构上还是做了很多改进的）。

原文链接

设计理念

GFS最大的价值或许并非提出了多么精妙的架构，而是其经受过高压实战生产环境的设计理念。这里引用原文的几条假设。

• The system is built from many inexpensive commodity components that often fail. It must constantly monitor itself and detect, tolerate, and recover promptly from component failures on a routine basis. 既然是分布式文件系统，单机的成本不可能太高，不只是硬件的成本还有维护的成本，所以要假定它是一个傻瓜机器，没有优良硬件支持也没有足够人力支持。

• The system stores a modest number of large files. We expect a few million files, each typically 100 MB or larger in size. Multi-GB files are the common case and should be managed efficiently. Small files must be supported, but we need not optimize for them. 这里主要是Google自己的业务考量，当然小文件的成本可不低，毕竟独占一个chunk，也会给分布式的决策带来额外负担。

• The workloads primarily consist of two kinds of reads: large streaming reads and small random reads. In large streaming reads, individual operations typically read hundreds of KBs, more commonly 1 MB or more. Successive operations from the same client often read through a contiguous region of a file. A small random read typically reads a few KBs at some arbitrary offset. Performance-conscious applications often batch and sort their small reads to advance steadily through the file rather than go back and forth. 很常见的决策。

• The workloads also have many large, sequential writes that append data to files. Typical operation sizes are similar to those for reads. Once written, files are seldom modified again. Small writes at arbitrary positions in a file are supported but do not have to be efficient. 这个假设极大的优化了性能，因为从文件中间进行修改的成本是十分高昂的，光处理同步问题的难度就极大。

• The system must efficiently implement well-defined semantics for multiple clients that concurrently append to the same file. Our files are often used as producer-consumer queues or for many-way merging. Hundreds of producers, running one per machine, will concurrently append to a file. Atomicity with minimal synchronization overhead is essential. The file may be read later, or a consumer may be reading through the file simultaneously. 符合上一条假设，重点优化放在了追加写上。

• High sustained bandwidth is more important than low latency. Most of our target applications place a premium on processing data in bulk at a high rate, while few have stringent response time requirements for an individual read or write. 也是结合实际业务的考量。

基础架构

GFS的基础架构设计简单，并没有复杂的系统，只是将其设计理念贯彻在了其中。

组件

• chunk，存放文件数据的最小单位，默认大小为64 MB（魔法数字，业务上的经验，后文简述），即便是1 MB的文件也要占用一整个chunk。为了可靠性，每个chunk都在不同的服务器上有副本，默认是3个副本。

• chunkserver，存放chunk的服务器，只考虑对于chunk的读写，不考虑元数据和一致性等问题。

• master，维护系统元数据的服务器，文件到chunk之间的映射，chunk到chunkserver的映射都在上面保存。他也会做访问和资源的管理。一个GFS只有一个master，这也是为了简化系统设计使其能够完成更加复杂的任务。

• client，就是访问的客户端。每次访问先从master获取元数据，然后再向chunkserver请求文件数据（也就是对应的chunk）。这是不是有点像DMA？

机制

值得一提的是GFS的client和chunkserver都不缓存文件数据（但client会缓存元数据），首先是文件太大了；其次是缓存一致性问题不好解决，剔除这个机制可以简化系统；最后就是chunkserver上的OS本身也有buffer cache。

对于chunk size，默认为64 MB确实挺大的（相对于普通文件来说）。chunk size越大，client和chunkserver的交互就越少，每次读取文件只需要更少个RTT，客户端也可以缓存更多的元数据，master所需要存储的元数据信息也就更少。但弊端也存在，块的数量减少意味着更可能产生热点块。

GFS的所有元数据都会存在内存中，而只有namespace和file-to-chunk映射会做日志形式的持久化。存放在内存中的好处自然就是读取快，追求读取速度的原因是GFS想要周期性地扫描以实现GC、re-replication（chunkserver故障时）和chunk迁移（为保证负载均衡）。

GFS并不选择将chunk的副本信息持久化，而是在启动时进行轮询扫描，并用心跳包进行周期更新chunkserver的信息。这样的方式避免了chunkserver信息的同步问题，毕竟chunkserver很多，这个问题很棘手。

Operation Log

这是GFS中元数据唯一被持久化的形式，还通过files and chunks的logical time定义了并发操作的顺序。如同别的文件系统的日志，元数据需要先于文件数据被持久化。批量写入以降低系统吞吐也是经典技术。master节点会在日志大小超过阈值时定期检查状态，这样下次从磁盘恢复时只需要回放更小的数据。checkpoint是以B树形式存储的，所以创建这个结构需要一定时间且可能阻塞用户操作，master在新的log file里并开启一个新线程来创建checkpoint。恢复过程只需要最新的log file，旧的checkpoint都可以被丢弃，不过GFS仍会保留一小部分以防万一。checkpoint记录过程中发生故障不会影响正确性，因为恢复代码能够检测并跳过不完整的checkpoint。

一致性模型

据原文，“GFS has a relaxed consistency model that supports our highly distributed applications well but remains relatively simple and efficient to implement.”其中，namespace的修改必须是原子的，由master来保证。文件数据在修改后的状态由下表决定：

	Write	Record Append
Serial Success	defined	defined interspersed with inconsistent
Concurrent Successes	consistent but undefined	defined interspersed with inconsistent
Failure	inconsistent	inconsistent

Consistent指的是无论客户端从哪个副本读，看到的都是同一份数据（各副本之间没有分歧；$Defined \subset Consistent$，指在Consistent的基础上，客户端读到的是某个mutation完整写入的内容——不是被撕裂的、不是多个写交错拼出来的残缺数据。

对于Google来说，他们几乎都是通过append来修改文件而不是overwrite，appending的效率高，面对故障的快速恢复能力也比随机写要好。append采用了记录追加采用at-least-once的交付语义，系统保证每个写入者的内容至少会被成功写入文件一次，但极端情况下可能出现重复写入，不会出现写入内容丢失的情况。若业务场景不允许重复数据（比如涉及付款、数据更新这类重复执行会导致错误的非幂等操作），可以利用记录中自带的唯一标识符进行去重。

系统交互

“We designed the system to minimize the master's involvement in all operations.”

租约被用来维护replica之间一致性修改的顺序。master将一个租约给到一个chunk，这时他就作为primary，其余replica被称作secondary。primary负责选取一个所有chunk修改操作的全局串行顺序。如果一个写操作太大或刚好越过了chunk的边界，client会把它拆成多个写操作，它可能会在并发时被影响，所以那个文件区域最终可能会包含不同client的碎片，这就是consistentbut undefined。

为了充分利用网络，GFS将数据流与控制流分离，且数据流的拓扑十分简单，可以直接理解为一个链表，而不是树或图等高级形式。为了避免network bottleneck和high-latency link，每个机器都只将数据送往离自己最近的机器。为了最小化延迟，GFS会pipeline数据传输，拿到数据和发送数据是同步进行的。

GFS的快照跟AFS一样都是基于COW机制的。在快照创建后，如果一个client要写入chunk $C$且master发现chunk $C$不只一个，它就会挑一个新的chunk句柄$C^\prime$，让每一个有chunk $C$的replica都创建新的chunk $C^\prime$，这样数据就只会在本地被复制了。

master操作

GFS不像传统文件系统拥有树状目录结构，而是维护了一个完整pathname到元数据的映射表，通过前缀压缩技术节省很多内存。据原文“if it involves /d1/d2/.../dn/leaf, it will acquire read-locks on the directory names /d1, /d1/d2, ...,/d1/d2/.../dn, and either a read lock or a write lock on the full pathname /d1/d2/.../dn/leaf.”，这样的锁方案允许对同一文件夹的并行操作。锁的获取都在一个一致的顺序下（通常lexicographically），这样可以避免死锁。

GFS集群的分布式部署架构是多级的，这是为了最大化可靠性、可用性和宽带利用率。每个chunk副本都要保证跨rack复制，这样某个rack集中挂了，还可以保证数据的完整性和可用性。这也意味着，单个数据块的流量（尤其是读取流量）可以利用多个机架的总带宽。另一方面，写入流量则需经过多个rack，这是权衡利弊的结果。

创建chunk的副本有三个考虑因素：1. 优先选用磁盘空间宽裕的chunkserver 2. 限制每个chunkserver“最近创建”的数量 3. spread replicas of a chunk across racks。当chunk的可用副本数量低于一个阈值时，master会触发re-replica流程。re-replica的优先级也由三个因素决定：1. 与目标副本数的差距 2. 文件的活跃程度 3. chunk对运行时应用的影响程度。为了防止复制的流量过大，master会限制cluster和每个chunkserver复制操作数量。master也会周期性地对副本做负载均衡，这个过程也可以让新chunkserver慢慢地获得文件而非一下用大流量填满。

当chunkserver在修改chunk时出问题，它的chunk就极有可能成为过期的chunk。master通过对每个chunk都维护一个chunk version number（版本号）来解决这个问题。master为chunk授予新租约时，会首先提升该chunk的版本号，同步通知所有最新状态的副本，master和收到通知的副本都会将新版本号持久化存储；这一流程全部完成后才会通知客client，确保client开始写入数据前，所有有效副本的版本号已完成同步。当一个chunkserver重启并上报它的chunk时，master会检测版本号来判定是否过期。如果master发现chunkserver上报的版本号高于自身记录的版本号，会判定为自身此前授予租约的过程中发生了故障，默认以上报的更高版本号作为最新有效版本。

关于GC

GFS在删除文件后不会立刻将存储空间声明为可用，而是通过GC机制惰性操作。

当文件被删除时，master会立刻在日志中记录，并修改文件名为一个包含删除时间戳的隐藏名称。master会通过周期性的扫描发现被“删除”了一段（可以自己设定的）时间的文件并删除他们，在这之前，这些文件仍然可以以新名字来被阅读并且可以被撤回删除状态。master也会定期扫描命名空间，找到没有与任何文件关联的chunk并让清除其元数据，然后由chunkserver删除其副本。

这样的GC机制对分布式系统极其友好，它简单、可靠，将操作合并起来批量处理以节省空间。另外它也降低了master的负载，让删除操作不会占用过多的运行资源。它甚至允许撤回删除操作。但是这个机制对于空间要求比较高，尤其是频繁创建删除文件的情况。GFS通过在已删除的文件被再次明确删除时加速存储空间回收来解决这些问题。

容错与故障诊断

master与chunkserver均设计为可重新存储其状态，并在无论何种终止方式下均能在数秒内重新启动。GFS并不区分termination的正常与非常，服务器进程很可能常规性地被kill掉。

master也会有复制机制，对master状态的改变只会在log record被存进所有master副本的磁盘才会被提交。另外还有shadow master会在master挂掉的时候为文件系统提供只读访问，

chunkserver会用校验和来检验数据完整性，因为靠对比副本来检验完整性并不现实。一个chunk会被分解成多个64 KB的block，每个block都有一个32位校验和。若某个数据块的校验和与记录值不匹配，chunkserver将向请求方返回错误，并将该不匹配情况上报给masater；作为响应，请求方将从其他副本中读取数据，而master则从另一副本中克隆该chunk。校验和对读取性能影响很小，因为大多数读操作都设计多个block，且client会尽量尝试将读取操作对齐到校验和边界。相比于随机写，追加写的校验和操作优化明显更好。即便之前数据破坏掉了，我们也可以在下一次读操作发现新的校验和与原来数据无法对应。随机写则需要完整计算所有数据并得到校验和。在空闲期间chunkserver也会对非活动块进行扫描，这使得我们可以检测到隐蔽的数据损毁情况。

展望

GFS本身还是有很多的缺陷的，尤其是它的分布式几乎是伪分布式（无状态复制、单点master），后来Paxos和Raft流行之后大家才真正让分布式理论支撑起工程实践。即便GFS还有宽松一致性模型带来应用层负担、小文件、容错与恢复机制的粗糙等问题，但无法否认他极大推动了分布式存储的发展。