Oct. 13, 2021
Here is the article.
下面是本课程要阅读的第二篇论文，同样鼎鼎大名的GFS（其实中间还有一课是对Go语言和RPC的讲解，在此就略过了。）Again，本人水平有限，请谨慎参考。
GFS为上一篇介绍的MapReduce提供了存储，没有GFS也就没有MapReduce了。其实与其说MapReduce多么牛，不如说是GFS牛。MapReduce论文出来的时候被做数据库的喷，不是没有道理的，这个模型早就是数据库领域几十年前玩剩下的了。但他们为什么做不出Google里面那种廉价高效的系统呢，我觉得主要是因为下层的支持系统不好做。
应用场景
GFS是一个分布式的文件系统。它不追求与POSIX接口兼容（我觉得这里不强求兼容是对的）而是使用自己的一套API。它对主要应用场景的假设也与传统单机文件系统不同：
- 系统用大量普通机器堆起来，机器挂掉是非常常见的事。
- 系统里面主要存的是大文件，几百M甚至上G这种大小。
- 读操作是大量的顺序读和少量的随机读。
- 写操作是大量的顺序写(append)，一旦写入几乎不会修改。
- 文件经常被大量client同时append，需要仔细考虑同步机制的开销
- 相比低latency，更看重高吞吐量
可以看出这些需求基本就是针对MapReduce量身订做的。
系统架构
系统里有单个master和众多chunkserver。Master存储metadata，chunkserver存储实际文件数据。文件被分割成固定大小的chunk (e.g.64MB)，每个chunk有一个全局唯一的ID，每个会默认备份3份到不同的机器上，以一个普通的linux文件的形式。
一个读请求的执行流程：客户端发送读请求到master，请求内容包括文件名和offset
--> master返回相应的chunk ID，以及它的若干备份都在哪些机器上
--> 客户端向最近的chunkserver发起读请求，开始传输数据
Master的设计
单master的设计显然带来了single point failure的问题。作者的解释是：1.这样大大减化了设计和实现 2.实际数据直接在客户端和chunkserver间交流，所以单master不会成为bottleneck master内存里的信息主要是每个文件名对应哪些chunk id，以及每台chunkserver上有哪些chunk。只有第一种信息是持久化到本地硬盘以及log中的，第二种信息是持续向chunkserver询问得来，因为chunkserver自己最知道自己的状态，免去了一层没必要的不一致的可能性。
上面提交的master的log非常重要，所以我们要保证先把操作写入log并备份到远程机器后，再对用户可见，和数据库的write-ahead log是一个意思。为了加速挂掉之后的重启速度，会定期作checkpoint，这样重启时只要重跑自上次checkpoint以后的log就行了。
一致性模型(consistency model)
（注：这一块非常重要也比较复杂，以下所述仅为我自己对论文的理解。我大略查了一下网上的资料，细节之处大家的理解并不完全一致。因为没有代码作参考，很难说哪个才是完全对的。）
出于性能考虑，GFS并不是强一致性的，它做出的保证如下：
文件metadata的操作（比如改名）是原子操作，这一点由master里仔细加锁就可以保证。
文件内容的修改有两种，普通写和record append，见下图：（注：“普通写”在论文里简单地用write表示，我在下文称其为“改写”以示和record append的区别）
根据前文所述的假设，record append操作占了绝大多数，改写操作很少。
论文里定义了几种不同的状态，consistent是指多个replica的数据是相同的，但可能内容来自多个并发写入的交叉，不是真正正确的内容，defined是指consistent并且不包含交叉。下文会详述为什么会出现交叉。
为了保证并发写时，各个replica数据的修改顺序是一致的，我们需要指定某个replica为primary，其他的为secondary。在GFS里这个由lease机制来实现。
具体来说，对每个chunk，master负责发放一个lease给其中一个replica，它就变成了primary。lease的有效时间是60秒，但primary可以申请延长，通常情况下都会得到master的批准。当有写请求来时，master会告诉客户端谁是primary，于是客户端总会把写请求发给primary；如果secondary收到了写请求（因为客户端cache了过期信息等原因），它会拒绝执行并通知客户端。master有权提前收回release；如果primary和master无法连通了，lease会在60秒后自动过期。有了lease机制，正常情况下对同一chunk的所有写操作都会发给同一个primary，这样写入的顺序就可以唯一确定下来。
另外，考虑到写入的数据量通常比较大，所以我们把数据流和指令流分开。先把数据发给各个replica，写入本地临时数据区，再传送一个“写入”的指令，这样可以尽可能地避免数据不一致。
我们先来看改写的情况：
- 客户端向master询问欲写入chunk的primary是谁，以及所有的secondary是谁。（如果这时没有人有lease，master就会指定一个。）
- master返回相关信息，客户端会把信息存入cache，以后就不再重复询问master以节省开销，直到该primary说自己已不再持有lease。
- 客户端把数据发给所有replica，replica们会把数据暂存下来，此时并不会真的写入指定位置。
- 当所有replica都报告数据收到后，客户端发写入指令给primary。primary会给这个指令定一个序列号（所以当同时收到多个请求时，在primary这里确定顺序）。primary依序列号修改自己的那份数据。
- primary把写入指令和序列号发给secondary，secondary都依同样序列号修改自己的数据。
- 当primary收到所有人的回复时，返回成功信息给客户端。
- 如果有的secondary成功了，有的失败了，primary会返回失败信息给客户端。此时数据就是不一致的。客户端会发起重试。
这里就出现了一个问题，如果欲改写的区域跨越64MB chunk的边界，那么这个写操作就要写多个chunk，而上文的lease机制不能保证对多个chunk的并发写有一致的修改顺序。假设有两个客户端A/B对同一段跨chunk的区域改写不同的内容，就会出现前一个chunk的写入顺序是先A后B，而后一个是先B后A，于是最终结果就是B的前一半和A的后一半留下来。而在GFS看来这完全是成功的写入。这就是上表中的"consistent but undefined"。
Record append的情况有些相似，不同之处在于客户端不会指定offset，每次写入时会针对待写文件的最后一个chunk。如果发现该chunk剩余空间不足以写入，则把当前chunk用空白补齐（padding)，然后把数据写入新的chunk。数据的写入是at-least-once，如果写失败了（i.e.只在部分secondary上写成功），则会在新的末尾重新写一次，这样就会导致上次已经写成功的replica上数据出现两次，而上次写失败的replica上会有一段空白。返回给客户端的是成功写入的offset位置。这就是上表里所谓的"interspersed with inconsistent"。客户端程序需要能正确处理这些情况：对于不正确的数据，可以在每个记录开头加一个magic number，或者加一个checksum之类；对于重复的数据，需要客户端判重，比如在记录里加一个unique id。
杂项
GFS没有做数据内容的cache，因为按照预想的应用场景，读操作大多是整个文件从头到尾扫一遍，working set太大，cache能提供的帮助有限。
GFS还提供了snapshot操作，利用copy-on-write机制实现文件或目录的快速复制。
用chunk版本号实现过期数据的检查。
用checksum检验硬盘数据是否被偶然修改（坏道？宇宙射线？）
论文里没有明说，但我觉得master挂掉后是会转为readonly模式，需要人工介入来把backup提升成master。（Google里真正用的应该是更nb的了。）
有一些参考资料介绍了GFS的沿革：
http://queue.acm.org/detail.cfm?id=1594206
http://highscalability.com/blo
No comments:
Post a Comment