本节课主要讨论的是 Google 的文件系统 GFS 的论文。

Big Strorage

存储抽象问题，或许对于分布式系统来说，你能想到很多，但是提供一个简单的存储接口storage interface会更方便，更通常。

我们会主要讨论如何更好的设计 big storage 的接口以及如何设计存储系统的内部来提供更好的性能。

文章中还有很多关键词汇，如parallel performance，fault tolerance replication，consistency。文章展开很自然、直接，容易理解。

教授在讲解 GFS 前先理了一下分布式存储系统的思路。

Why hard

Performance -> Sharding（碎片化）

我们需要将数据分片储存到很多个储存节点上，也需要从很多个节点（clients）中读取数据进行处理。如果你分片到成百上千个 server 上，总会有个别宕掉。错误是 constant 的。

Faults -> Tolerance

所以我们需要automatic fault-tolerant systems能够自动化容错的系统。提供容错能力最直接有效的方法是使用备份（replication）转移到多台机器上，So，一台坏掉，我们就需要启动备份容灾的能力。

Tolerance -> Replication

那多个备份，就要小心out of sync不同步的情况，这样才能保证使用任意备份都可以用来 tolerate the fault（备份间应是 interchangeably）。

Replication -> Inconsistency

通过更合理的设计，能避免 inconsistency 带来的影响。反之，则需要更多机器间的确认。这样挤占吞吐量会降低性能。

Consistency -> Low Performance

这样就产生了一个奇怪的 loop，从提高性能出发却得到了更差的性能，感觉做了无用功？

Strong Consistency

好的一致性就让 client 和 server 之间的操作像对待单一机器一样，这个在课程后面会再详细说明。

一个例子，并发的两个 client，C1 和 C2 在同时修改了相同 key 的 value，C1 修改 keyx 值为 1，C2 修改相同 key 值为 2.如果之后读该 key，值该是多少呢？如果读出来的值总是一致且确定的，具备强一致性。

Bad Replication Design

两个 k-v store 的 server，S1 和 S2，我们希望他们彼此独立，因为如果一台宕掉，另一台要能继续支持我们的工作。还是 C1 和 C2，每个 client 分别给 server 发出写命令。

那么很有可能出现这样的情况，S1 接收顺序为 C1C2，而 S2 接收顺序为 C2C1，那么 S1 最终 key x 的 value 为 2，S2 最终 key x 的 value 为 1。

人们设计了很多层级的一致性，以及哪些不一致情况可被 reveal。

GFS_1

GFS

想法诞生自 2003 年，科学界这十几年来发展出各种各样的高并行的适合分布式存储系统的设计。但是！工业界上少有真正将这些理论academic ideas应用。但在这篇 paper 发布的时候，Google 就已经开始构建严谨的分布式系统。

Google 有太大太大的数据，单一硬盘根本无力应对。包括爬取拷贝（crawl copy）、流视频、超大日志文件等。需要高效存储（GFS 的工作）以及高效分析（MapReduce 的工作）。

Concerning Goals

Big Fast Global

面向巨大数据，高效处理，还要对 Google 内部基本所有人都可用。

Sharding Automatic recovery

数据分片划分，以及自动容错恢复

Non Goals

Placing replicas（因为是 Single data center）

考虑在单一数据中心的服务，跨区域的不考虑

Big sequential access

不考虑

发布时情况

带来了业界对超大规模数据的探索，反映了真实世界经验。学界从来没有考虑过这么大规模的数据（在当时）。

有意思的是，GFS 好像并不会保证强一致性？设计的目的就是高效（High performance），允许其中的一点小错误。

而且只使用单一 Master（因为设计者觉得够了）。

Structure

结构

一个 master server 和众多 chunk server。

Master Server Data

关注两个 table

table1： 储存映射（map）： Filename -> an array of chunk ID's(chunk handles)

告诉我们去哪里找 data。chunk 大小设定 64MB。

table2： 储存映射（map）： chunk ID's(chunk handle) -> a list of chunk servers, version, primary, lease expiration（租约到期时间）

两个 table 都在 master 的 RAM 和硬盘中，一些数据需要可持久化，否则 master 挂掉就完了。所以加入日志与检查点

log, checkpoint —— on disk

使用 log 而非 database（b-tree 或 hash table）来记录操作的原因是 append log 容易，只需要加入一些 log records 即可，而数据结构则需要再开辟一个空间写改变。log 写得会快些。

我们不希望 master 挂掉要从 install chunk 这种远古时期开始重新构建系统，所以我们还需要固定的检查点。

Read 过程

应用想读取已知文件名（filename），一定偏移量（offset）的数据。

• Step1. client(name, off) -> master
• Step2. master(handles,list of servers) -> client

找寻最近的可使用 server，（或许从 list 中找相同机架的是最近的）。 会 Cache 来提高重访问的效率。

• Step3. client() -> one chunk server
• Step4. chunk server(data) -> client

Q&A 被问及最多的是，系统如何返回合理的 a list of chunk server handlers（如果我没理解错的话），教授说这是 GFS library 做的事情，Client 会链接这个 library，比如访问的 filename 和 offset 涉及 Chunk7 的最后几 bytes 和 Chunk8 的前几字节，然后 put them together in a buffer 并返回给应用程序。

Write 过程

写讨论起来更复杂一些。在文件名对应的文件后面 append 些内容。应用所在的 client 需要知道 the last chunk。不幸的是，reading 可以在多个 client 并发获取最新的内容，但是并发写是需要 have a primary 的那个机器写。

• no primary—— on master

  在这种情形下，master 需要找到那些获取了最新 copy 的 chunk servers。尤其考虑到掉线很久重连的 server。这种情形下，client 询问，工作都在 master 上。

  find up-to-date

  chunk 的 version number 与 master 记录相等（这可以解释为什么 version number 需要在 master 中可持久化记录在硬盘上）

  Q：如果 master 这里记录的 version number 是 17，找不到 chunk server 的 version 与他相等。 A：那或许可以等待，或许就告诉 client（好吧我不知道该怎么办了）。

  master 记录一个列表的 chunk server 的版本号，chunk server 记录自己的版本号，这样在应用请求的时候，master 就可以查询并且选择性找到那些版本号匹配的 chunk server。

• primary

  选择 primary chunk server 和 secondary chunk server，优先增加 primary 的版本号，再通知到其他 secondary 的版本号。

  Q：是否会出现 chunk server 版本号高于 master server 的情况？ A：教授说这也是他对论文的一个问题，master 会接受这个版本号（来自 primary 的），他认为这种满足了一定 master failure 的容错能力。教授认为版本号会被 master 可持久化在硬盘上，通知后掉电应该仍能保持最新，同学提出是否是 ACK（确认消息）为抵达，或许有道理。

  挑选出的 primary chunk server 会有一个租约期 lease time（60s），这是确保不会有两个 primary 的策略（一会儿详细解释）。

  primary picks offset

  all replicas told to write at the offset

  先行写在临时位置，直到所有 secondary 都 finish，再发送给 primary 信息。primary 收到大量同时的请求（并发的），选择一个顺序，逐个执行客户请求，并通知 secondary。

  if secondary if all "yes" primary("success") -> client else primary("no/failure") -> client

  如果失败的话，客户就要 reissue（不过听意思，好像是 library 的逻辑，并不需要用户继续提交），所以 eventually，客户会得到一个 ok？

  Q：确切的存储位置，可能会对某项操作速度有明显的影响（普通策略，可能会先传递到远的再到近的。）

  A：文章中有提及设计者的一个改良“开始是传递到每个 replica”，然后文章转向成“先出地道最近的 replicas 之后再链式传递到所有 replica”，这个传递链是经过排序优化的，所以会极大化减小不同启动位置（exact path）产生的 bottleneck。

  Q：如果只有一个 secondary server 返回失败，为何 master 不起动新的版本号并把这个 secondary 抛弃呢？

  A：paper 只是简单重启整个任务，如果 ping 不通再进行版本号的更替，更多情况下，可能是网络传输的问题，这个 server 不见得真的出现什么问题。我个人觉得是网络问题多见的话，那 master 立即再尝试一遍任务或许是最好的选择。

  lease， double primary， split brain，

  Q：（没有太听清楚问题）为什么？secondary 需要向 master 确认？

  A：教授举了一个（好恶心的例子），server 2 作为 secondary 向 master 询问谁是 primary，master 告诉它的消息“server 1 是 primary”还在传递中，结果 master 发现 sever 1 挂掉了。又发送新的消息（这里疑惑，master 可以直接选择新的 primary 吗，什么时候可以选择）。那么 server 请求的 primary 是谁的消息，刚一收到，就是 outdate 的。

sync

教授给了张 replica num=3，但是由于故障，replica 存在 blank 的情况，引出 sync 的问题。

需要保持 replica 保持 sync，这个就是 Lab2 & Lab3 需要同学们完成的事情。You can't have there partial operations that are applied to only some and not others and that means that there has to be some mechanism.您不能只将部分操作应用于某些操作，而不能应用于其他操作，这意味着必须有某种机制。

什么样的机制 where the system even if the client dies where the system says we don't wait a minute there was this operation I haven't finished it yet. So you build systems in which the primary actually make sure the backups get every message.即使客户在系统说我们不等一分钟的情况下死亡，也喜欢系统在哪里，我还没有完成此操作。 因此，您构建的系统中，主数据库实际上会确保备份获得每条消息。

issue

duplicate detection

防止 B 出现两次

two-phase commit

primary 先向所有 secondary 询问是否可以保证操作（promise），待所有回复保证后再真正执行操作。

left operations

当 primary 挂掉（过期会续租），还存续一些已经分配给 secondary 做的任务、operation，新选出的代表可能会有和这些 operations 不同的地方，需要 resynchronization。