Google File System论文阅读难点笔记
阅读GFS论文时，发现有几个地方特别不容易理解，特记录如下。
一致性问题
GFS中的文件由块组成，同一个块有多个副本，副本分布在不同的节点上，如何保证数据的一致性？
论文中有“宽松的一致性模型”这种说法，一般的理解，“宽松”的意思就是不严格保证，为什么呢？原文中的说法是为了简化系统设计。
为什么会有一致性的问题？一致性问题产生的根源是什么？
写入操作失败，是导致不一致性的一个原因。
更普遍的原因是用户多路并发写操作，因为简化系统设计，又没有提供复杂的同步机制。
一致性涉及到的重要概念：
- consistent：对于文件中的一块区域，比如从某个偏移量开始到某个偏移量结束，如果客户端从任意副本读出的这块数据都相同，则认为文件的这块区域在系统中是consistent，也就是一致的，但一致并不等同于正确。
- defined：如果对于文件中的某一个区域，如果一个变更完成后，区域中的数据在保持一致性的同时，所有的客户端都能完整的看到这次变更，则说明这块区域是defined，也就是定义的，这是理解的状态。
接下来看下表：
| 随机写 | 记录追加写 | |
| 串行成功 | 定义的 | 定义但部分不一致 |
| 并发成功 | 一致但是未定义 | |
| 失败 | 不一致 | |
- 随机写串行成功：因为操作的结果是成功的，写入的文件偏移位置与内容是完全一致的，并且因为是串行写不存在并发冲突，所以结果是最理想的“定义的”。
- 随机写并发成功：因为没有同步机制，如果对文件的同一区域执行写操作，则会存在冲突，虽然写操作成功了，但是有可能被同时并发的写操作干扰、覆盖，其结果是不确定、未定义的。但是，GFS要求所有的变更操作在不同的节点上按相同的顺序执行，所以其结果是一致的，也就是要错大家一起错。
- 追加写成功：首先无论是串行还是并行，在GFS系统看来，都是串行，追加需要排队，必需是前一个追加完全成功后才执行后一个追加。为什么会存在不一致的问题呢？原因是追加操作时，文件尾的偏移量是GFS系统决定的。考虑一下这种情况，如果同时向三个副本追加数据，如果其中一个失败了，整个追加操作需要重新执行，但此时三个副本的文件尾偏移量已经不同，那么GFS可能需要填充、对齐然后再追加数据，结果就是虽然操作是定义的，但是在文件中的某些区域可能是不一致的，这一部分数据是无效的，当然无效的部分不会太大。
- 失败：失败的话不能保证一致性，更谈不上明确定义。
GFS是如何保证一致性的？它采取了两人上措施，一个是事前的，一个是事后的。事前的措施是变更无论是串行还是并发，都要先编号、排除，然后按相同的顺序应该到各个副本上，这样就保证了一致性。事后的措施是给每个副本定义版本号，随着变更的进行版本号依次变化，如果某个副本因为某种原因缺失了某次变更，那么它的版本号就会出现问题，并且GFS在周期性检测中能发现这种问题，此时这份副本就变成失效副本，不会再应用任何变更，GFS将些副本当垃圾回收并自动复制正确的副本实例补全。因为客户端会缓存副本位置信息，不能第一时间感知失效副本，也就是在失效的情况下有可能仍然对它进行读写。写的话没有问题，因为变更应用到了其它正确的副本，并且损失的副本会被GFS自动补全。如果失效副本被回收则写操作失败，并返回失败原因，则此时客户端可重新刷新副本位置缓存。读的话可能会有问题，但问题不太大。因为GFS大部分情况下都采用原子记录追加的方式，顺序的写顺序的读，一旦被写入，大部分情况下都不需要再去随机修改，因此这个时候客户端会读到提前结束的记录或者是块，或者是直接返回错误，此可客户端应该重新刷新副本位置缓存。
GFS的不一致性是客观存在的，客户端如何适应、应对这种情况呢？
首先尽量避免随机写特别是并发随机写，减少冲突发生的可能性。
采用一些合适的设计模式，如先顺序追加文件，直到整个文件完全写入再读取并处理，读写分离，避免在写入的同时读文件而读到不完全的数据。
周期性的作checkpoint，记录那些数据已经被处理，那些已经写入完成但没有被处理，那些不许被处理，协调读写速率。
对于因为写入失败而产生的记录碎片，可以被记录添加checksum，读取以后验证记录的有效性。
对于重复的记录，在设计时可为其添加唯一ID，在处理时根据ID判断记录是否重复等。
变更顺序与租赁机制问题
如果有多路客户端在并发的向一个文件中追加数据，而数据又保存在多个副本中，为了保证数据的一致性，GFS首先会对所有的变更编号、并排队，保证所有的变更在不同的副本上发生的顺序是一致的，这也就保证了不同副本但数据一致。
GFS在逻辑上只有一个master节点，需要尽量减少其工作负荷，因此引入了一个“租赁”的概念，本质上就是将对变更命令的接收、编号、排队、分发到所有副本节点的工作由master节点转移到某个副本节点上去，将这种权力与职责暂时“租赁”出去，这个副本节点称为主副本节点，由master节点从所有可用副本中选出并告诉客户端，当然master节点在某些情况也会剥夺主副本节点身份，或者主副本自己失效、过期等，这个时候客户端需要重新向master询问。
STEP1：客户端告诉master，想对某个文件追加记录。
STEP2：master返回所有副本的位置信息，第一个副本就是master选出的主副本节点，客户端缓存并随后使用。
STEP3：客户端向副本节点推送数据信息。注意只里只是数据，数据会首先被缓存在副本节点的缓存池里边，并没有真正的应用到文件中去。并且需要注意的是数据在推送的过程中，优先选择离自己近的那个，以提高带宽利用率，并没有严格的顺序。
STEP4：当客户端推送完数据后，发送变更请求，要求将STEP3中缓存的数据应用到文件中去。此时发送的数据是控制信息，并且一定要发给主副本节点。可以看出在GFS中数据量与控制流是完全分隔、独立的，发生的时间点不一样，传播的路径也不相同。
STEP5：主副本节点可能会同时收到很多变更请求，由它负责编号、排除、然后分发到其它的节点，无论是主副本还是普通副本，都按这个排好的顺序实施变更。
STEP6：普通节点告诉主副本节点变更完成。
STEP7：主副本节点告诉客户端变更完成。
上图中的粗箭头表示数据流，每个节点都工作在双式模式，就是从上游收数据的同时向下游发数据，因此带宽利用率很高。
在步骤5中，主副本节点汇总所有变更，并给他们排队，然后所有的变更命令在所有节点上都按这个顺序执行。也就是用户虽然并行的在发送变更请求，但是在GFS内部，这些请求还是串行执行的，很显然的是这个降低了写入的速度。
关于记录追加的原子性
记录追加操作是大数据处理中常用的、重要的修改数据的方式，因此在GFS中对它提供了特别的支持。对于客户端而言，如果一次记录追加成功了，那么GFS保证文件中至少有一条正确的记录，也就是说有可能有多条，也有可能有碎片，但些都是GFS在后台自己处理、实现的，对于写数据的用户而言无感知。
参考：http://www.importnew.com/3491.html 比较好的中文翻译