Readings - The Google File System论文

介绍

GFS是由Google设计和实现的，以满足Google对数据处理快速正常的需求。GFS和先前的分布式文件系统有很多相似的目标，例如：性能、可扩展性、可靠性和可用性。然而，GFS的设计是由Google对应用负载和技术环境的关键（当前和预期的）观察驱动的，这反映了与早期文件系统设计假设的显著不同。Google重新审视传统的选择，并探索在设计领域探索了彻底不同的观点。

• 组件故障是常态而非例外。 因此持续的监控、错误监测、容错和自动恢复是系统不可缺少的。
• 传统标准的文件是巨大的，常常很多GB。处理包含数十亿个对象、很多TB、且快速增长的数据集时，即便文件系统可以支持，也很难管理数十亿个约KB大小的文件。 因此设计假设和参数，例如IO操作和block大小必须被重新审视。
• 大多数文件修改都是通过追加新数据的方式，而非覆盖已有的数据。对文件的随机写几乎已经不存在了。一旦写入，文件就是只读的，且常常只是顺序读。 鉴于这样对大文件的访问模式，追加成为了性能优化和原子保证的的关注点，而在client上对数据块的缓存失去了吸引力。
• 应用程序和文件系统api的协同设计，通过提升灵活性，有益于整个系统。

设计概览

接口

虽然GFS没有实现例如POSIX的标准API，但也提供了一组熟悉的文件系统接口。文件以层次结构的方式用目录组织起来，并用路径名来标识。GFS支持create，delete，open，close，read和write文件。GFS还支持snapshot和record append。

架构

一个GFS集群由一个master和多个chunkserver构成，可以被多个client访问。

文件被切分为固定大小的chunks。每个chunk都由一个不可变，且全局唯一的64位chunk handle标识，这个chunk handle在创建chunk时master分配的。chunkservers把chunk作为linux文件存储在本地磁盘上，并通过指定的chunk handle和byte range来读写文件。为了reliability（可靠性），每个chunk会在多个chunkservers上有复制。

master维护这整个文件系统的metadata，包括namespace，访问控制信息，文件到chunk的映射，以及chucks的当前位置。master还可控制着系统级别的活动，例如chuck租约管理，孤儿chunk的垃圾回收，以及chunkservers之间的chunk迁移。master定期与每个chunkserver以HeartBeat消息的形式进行通信，完成指令的发送和状态的收集。

client与master通信来进行metadata相关的操作，数据相关的通信是直接与chunkserver进行的。

client和chunkserver都不需要缓存数据。client缓存数据的收益很小，因为大多数程序都是流式读取大文件或者数据量太大而无法缓存。client不用缓存数据消除了缓存一致性的问题，简化了系统设计。但client会缓存metadata。chunkserver不必缓存文件数据，因为chunk都是以本地文件的形式保存的，linux buffer cache会把常访问的数据放入内存。

单一master

单一master极大的简化了设计，并使master能够使用全局信息来进行复杂的chunk布局和复制决策。然而当读写时，必须最小化master的参与，这样master才不会成为瓶颈。client进行读写时，先询问master应该连接哪个chunkserver，并缓存这个信息一段时间，然后直接与这个chunkserver交互来完成后续的操作。

chunk size

chunk size是关键设计参数之一。GFS使用一个远大于典型文件系统的block size，64MB。每个chunk副本都以普通linux文件的形式存储在chunkserver，并在需要的时候扩展。惰性空间分配避免了由于内部碎片导致的空间浪费。

大型chunk size有这些优势，

• 减少了client与master交互的需求。 读写同一个chunk只需要向master请求一次chunk的位置信息。
• 由于chunk较大，client也较为可能在一个给定的chunk上进行很多的操作。 通过在较长时间内保持与chunkserver的TCP连接，可以减少网络开销。
• 减少了存储在master上metadata的大小。 由此可以将metadata放入内存。

然而大型chunk size，即便有惰性空间分配，也存在弊端，

• chunkserver的热点访问。 一个小文件仅有为数不多的chunks组成，可能就一个。如果大量的client都访问同一个文件，那么存储这些chunk的chunkserver可能会成为热点。

Metadata

mater主要存储3类metadata：

• 文件和chunk namespace
• 文件到chunks的映射关系
• 每个chunk副本的位置

其他metadata还包括所有权和权限、每个chunk的版本、引用计数（用于实现copy-on-write）。

所有的metadata都是存储在内存中的。

• 前两种还会进行持久化存储（使用write-ahead log），这是通过把记录修改到操作日志、在master落盘、以及在远程机器上存放副本来实现的。
• 对于最后一种metadata，master并不会做持久化存储。在master启动和有chunkserver加入集群的时候，master会询问每一个chunkserver存放的chunks。

In-Memory Data Structures 由于metadata是存放在内存中的，因此mater的操作很快，除此之外还能完成定期在后台较快的完整扫描。这个定期扫描用于实现chunk的gc，chunkserver故障时副本重新复制，以及chunk的迁移。

一个潜在的问题是存储的chunk数目受限于内存的大小。但由于每个chunk的metadata少于64byte，且文件的namespace数据也少于64byte，并且启用了前缀压缩，因此这不是一个严重的问题。如果确实有必要支持更大的文件系统，加内存即可。

Chunk Locations master并不对chunk locations做持久化。master启动时，会向所有chunkserver请求。之后，由于master控制着所有chunks的放置，并通过心跳消息来监控chunkserver，master能够确保自身的信息是最新的。

为什么不做持久化？

1. 消除了master和chunkserver的同步问题。 chunkserver可能加入、离开、重启、重命名、故障等。
2. chunkserver对自己有和没有哪些chunk有最终的话语权。 在master维护此信息的一致视图是没有意义的，chunkser可能出现1中的各种问题。

Operation Log 操作日志对GFS很重要，

• 包含了metadata关键修改的历史记录，并持久化。
• 作为逻辑时间戳，定义了并发操作的顺序。 文件和chunks，以及它们的版本，全都在创建的时候被逻辑时间唯一且永久的标识。

可靠性保证，

• 仅当metadata的修改完成持久化以后，这些修改才对client可见。
• 在多个远程机器上有复制。
  • 仅当把相应的log记录写入本地和远程机器的磁盘后，才响应client。
  • master会批量flush日志，来减少flush和复制对整个集群吞吐量的影响。
• master通过重放操作日志来恢复文件系统的状态。
  • 为了减少启动的时间，需要保证log较小。
  • 当log增长超过特定大小时，master会checkpoint自身的状态，以便可以在恢复时载入最后一个checkpoint并重放在那之后的log。

checkpoint和恢复，

• checkpoint类似于压缩后的B树，可以直接map到内存，并用用户namespace的查找，且不需要额外的解析。
• master创建checkpoint时，会切换到新log文件，并在另外的线程中创建checkpoint（包含了checkpoint前的所有修改），避免延误当前的修改。
• 恢复只需要最近的一个完整（需要检测是否完整）checkpoint和后续的log文件。更老的checkpoint和log是可以释放的。

一致性模型

GFS有一个宽松的一致性模型，这在支持高度分布式应用的同时，也相对简单和高效。

Guarantees by GFS 文件namespace修改（例如：创建文件）是原子的，由master专门执行。namespace锁保证了原子性和正确性；master的操作日志定义了这些操作的全局顺序。

一个文件区域有两种状态，

1. consistent：无论client从哪个副本读取，都能看到相同的数据。
2. defined：在文件数据修改后，如果文件区域是consistent的，并且client能看到所有写入到文件的修改。

数据修改包含，

1. 写入
   • 写入操作会把数据写到应用程序指定的文件offset。
2. 追加
   • 即使在并发修改存在的情况下，追加会把数据在GFS选择的offset处至少一次原子追加一次。
   • 这个offset会返回给client，标记了一个defined文件区域的起始位置，这个区域包含了已追加记录。
   • GFS可能会插入填充或重复记录项。他们占据的区域被认为是inconsistent，且占用户数据总量的很小一部分。

如何区分defined和undefined的文件区域？

在一些列的成功修改后，被修改的文件区域保证是defined（？），且包含了最后一次修改所写入的数据。GFS通过以下方式来实现这个保证，

1. 在所有的副本上以相同的顺序对chunk进行修改。
2. 用chunk版本号来检测过期的副本（由于chunkserver下线导致缺失修改）。 过期的副本不会参与到修改或返回给client，会尽早的被gc掉。

不过这里我存疑，例如：concurrent write，并不能保证defined。

某些client会cache chunk的位置。由于cache的timeout，读取到过期数据的时间窗是有限的。另外，对于大多数文件都是追加操作，一个过期的副本通常会返回过早结束（a premature end of chunk）的文件块，而非过期的数据。

在修改完成很长时间后，机器故障也会破坏或摧毁数据。GFS通过master和chunkserver定期的握手来检测失效的chunkserver，并通过校验和来检查数据损坏。当问题出现时，数据会尽快的从有效的副本进行恢复。如果在GFS来不及反应（没有足够的处理时间）的时候，所有的副本都丢失了，那应用能收到错误，而不是看到损坏的数据。

Implications for Applications GFS应用可以通过一些已经用于其他目的的简单技术来适应宽松一致性模型，

• 依赖追加而非覆盖，以及checkpointing
  • 例如：writer从头生成一个文件，待所有数据写入完毕以后，原子的把文件进行重命名。也可以定期创建checkpoints记录成功写入了多少。checkpoints也可以包含应用级别的校验和。readers只检查和处理至最后一个checkpoint之间的文件区域，这些文件区域是defined。
  • 追加远比随机写要高效和有弹性的多。
  • checkpoint允许writer以增量的方式重新写入，并避免reader处理那些从应用的角度看仍是不完整的数据，尽管这些数据已被成功写入。
• 写入时自我校验和自我识别的记录
  • 记录是以至少追加一次的语义来记录每个writer的输出的，因而reader需要处理偶然的填充和重复的情况。
  • writer写入的每个记录都包含额外的信息，例如校验和，用于验证。reader用校验和来识别并丢弃填充数据，以及记录片段。
  • 如果无法容忍偶然出现的重复（例如，这些数据会触发非幂等的操作），那可以通过记录中的唯一标识来进行过滤。

Checkpointing allows writers to restart incrementally and keeps readers from processing successfully written file data that is still incomplete from the application’s perspective. 我没有完全理解所谓的从应用的角度看仍是不完整的数据，是指的最后一个checkpoint之后的那些数据？

系统交互

GFS的设计可以最大限度的减少master参与到所有的操作。

租约和修改顺序

文件的修改发生在chunk的所有副本上，GFS使用租约来维护副本之间一致的修改顺序。master会将一个chunk的租借给其中一个副本，这个部分叫做主副本。主副本选择对chunk所有修改的序列顺序，所有的副本在应用这些修改的时候都会遵循这个顺序。最后，全局的修改顺序，首先由master选择的租借授权顺序定义（先选择某个副本为primary，然后可能又选择了另一个为primary），并在租期内由主副本分配的序列号定义。

租约机制的好处是最小化master的管理开销。

• 租约起始的timeout是60s，但只要chunk还在被修改，主副本可以无限次的请求，然后（一般情况下）得到timeout的扩展。
• timeout扩展的请求的授权是存放在master和所有chunkservers定期交互的心跳包里面的。
• master可能会在租约过期前撤销（例如master要禁止一个正在rename的文件的修改）。
• 即使master丢失了与primary的通信，master也可以在老的租约过期后，将新的租约授权给另一个副本。

下面以写入为例说明整个过程，

1. client向master请求持有租约的chunkserver以及其他副本的位置。如果租约未被持有，master会授权一个副本。
2. master返回给client primary的标识和其他副本的位置。client cache这些数据，且仅在无法连接到primary或primary不在持有租约的时候才会联系master。
3. client将数据推送到所有副本，任何顺序均可。每个chunkserver会将这些数据存储在内部的LRU缓存中，直至数据被使用或过期。
4. 一旦所有副本确认收到数据以后，client向primary发送写请求。写请求标识了先前推送到所有副本的数据。
   • primary为所有收到的修改（可能来自多个client）分配连续的序列号，序列号提供了必要的序列化（necessary serialization）。
   • primary将修改以序列号顺序应用到本地状态。
5. primary向所有从副本转发写请求。每个从副本都以primary分配的相同序列号顺序应用修改。
6. 所有从副本回复primary，表明已完成操作。
7. primary回复client。

如果上述过程出错，

• 任何副本发生错误，都会汇报给client。
• 如果在primary发生错误，序列号将不会被分配和转发。
• client的请求被认为已失败，被修改的文件区域将处于不一致状态。
• client会做重试，先会重试步骤3~7，如果不行，会完全从头重试写入。

如果存在另一个并发写入到相同位置的client，

• 前一个client写入的内容被后一个写入的覆盖
• 所有副本都有相同的数据，但是混合了来自两个client的数据，consistent but undefined。

如果一个写入的数据很大或跨越了chunk的边界，GFS client会把数据打散成多个写操作。这些写操作遵循了上述流程，但是可能会与其他client的并发写操作交替和被覆盖。因此文件区域将会出现consistent but undefined的情况。

数据流

从控制流解耦数据流是为了高效的使用网络，

1. 最大化利用每个机器的网络带宽
   • 数据以流水线的方式，沿着精心挑选的chunkservers链进行线性的推送，而非以其他拓扑形式来推送（例如：树）。
   • 这样每个机器的所有出口带宽都会用书尽可能快的传输数据，而非将带宽拆分到多个接收者。
2. 避免网络瓶颈和高延迟的链路
   • 交换机链路通常有这两个问题。
   • 每个机器会把数据转发到网络拓扑中最近（通过ip地址来估算）的且未收到数据的机器。
3. 最小化推送所有数据的延迟
   • 通过在TCP连接上以pipelining的方式进行数据传输来实现
   • 一旦某个chunkserver收到一份数据，就立即开始转发。立即转发并不会降低接收数据的速度。
   • pipelining在使用全双工链路交换网络的情况下很有用。
   • 在没有网络拥塞的情况下，传输一份R个副本B byte的数据，理想的时间开销是B/T + RL，T是网络吞吐量，L是机器间的传输延迟。

Atomic Record Appends

GFS提供了原子追加记录的操作，叫做record append。

• 传统的写操作中，client指定data需要写入的offset。并发写入到同一个区域是不可序列化的。
• record append中，client指定data，GFS在自己选择的offset处以原子的方式至少一次追加数据到文件末尾，并将offset返回给client。

record append是一种修改操作，遵循前面描述的控制流。

1. client向文件最后一个chunk的所有副本推送数据，然后向primary发送请求。
2. primary检查追加到当前chunk是否会导致chunk超出大小限制。
   • 如果是，那么填充当前chunk，并告知从副本也填充。返回client需要在下一个chunk上重试。
   • 追加记录被限制在0.25 * maximum chunk size，以限制碎片在可接受的范围内。
   • 如果没有超过，那么primary进行追加，并告知从副本也在相同的offset追加，最后返回client操作成功。
3. 如果在任何副本上追加失败，client会重试。

重试追加时，

• 重试的结果是，同一个chunk的副本可能会包含不同的数据，可能包括部分或全部相同的记录。
• GFS并不保证所有副本每个字节都是相同的，只能保证数据会以一个原子单位的形式至少一次写入。
• 对于一个成功的写入操作，数据一定写在某个chunk的所有副本的相同offset位置。在这之后，所有副本都至少与记录的结尾一样长。因此任何后续的记录，即使另一个副本成为primary的情况下，都会被分配到更高的offset，或者另一个chunk。

Snapshot

GFS使用copy-on-write的方式来实现文件或目录的快照，创建snapshot的速度很快。

• master收到快照请求时，首先撤销将要做snapshot的所有授权chunk的租约。
• 租约撤销或过期后，master在磁盘记录操作日志。接着通过复制文件或目录树的metadata，把日志应用到内存状态。新创建的文件快照与原文件指向相同的chunks。
• client写入某个chunk C时，先通过master找到primary。master发现引用计数不唯1，选择一个新的chunk handle C’，并通知相关chunkserver本地复制创建C’。
• 最后client遵循前面的过程进行写入。

对目录进行snapshot的时候，复制的metadata是什么？

master操作

master执行，

• 所有namespace的操作。
• 管理chunk副本的放置、创建、复制、以及与各种系统级活动协调来保证：chunk是完全备份的、平衡chunkserver的负载、回收未使用的空间。

namespace管理和锁

GFS使用完整路径名到metadata的map来从逻辑上表示namespace。存储的时候使用前缀压缩。

锁以及加锁方式，

• namespace树的每个节点（绝对文件名或绝对目录名）都有关联的读写锁，读写锁是惰性分配的。
• master进行每个操作前，都会对路径名/d1/d2/.../dn的每一级父目录加上读锁，并对/d1/d2/.../dn/leaf加上读锁或写锁，leaf可能是文件或目录。 这里不需要对父级目录加写锁，因为并没有真正意义上的父级目录，也没有需要避免并发修改的数据。只要能防止被删除、重命名或被snapshot即可。
• 锁是以一个一致的全序来获取的，以避免死锁。首先按namespace树的层级排序，然后按同一级的字典序排序。

副本放置

副本放在分布在多个机器内是不够的，还需要分布在不同的机架，放置策略有两个目的：

• 最大化数据可靠性和可用性。
• 最大化带宽利用。

Creation，Re-replication，Rebalancing

chunks在三种情况下会进行创建：

1. master创建新chunk。 创建时会考虑这些因素，
   • chunkserver磁盘使用率低于平均值。
   • 限制每个chunkserver最近创建数。结合上一点，如果不限制，那么对于一个空chunkserver，迁移时繁重的写操作，会导致磁盘I/O过高。
   • 跨多个机架。
2. 副本数低于目标值（由于机器不可达、副本损坏、目标值增加），master重新创建副本。
   • 每个需要被re-replicated的chunk的优先级由多个指标衡量：低于目标值多少？优先为存在的文件（live files）创建而不是最近被删除的。优先创建任何阻塞了client操作的的chunk。
   • 创建时，chunkserver会从有效的副本直接复制，会考虑1中的各种因素。
   • 为了避免对client流量的影响，master会限制集群和每个chunkserver的clone数目。chunkserver会限制从源chunkserver的读请求来实现限速。
3. 平衡磁盘空间和负载。
   • master定期进行rebalance，一般来说选择移除磁盘空闲空间低于平均值的。
   • 新chunkserver会被逐渐的填满，而非立即将新chunk和写流量都直接打上去。

垃圾回收

当文件删除的时候，GFS不会立即回收物理存储。GFS会在定期的gc期间，在文件和chunk级别进行回收。

机制

当文件被删除的时候，

• master立即记录删除日志，并将文件重命名到一个包含删除时间的隐藏名字。
• master定期扫描文件系统的namespace时，删除存在3天以上（可配置）的隐藏文件，这有效的切断了与chunks的连接。
• master定期扫描chunk namespace，识别出孤儿chunk，并清除它们的metadata。
• chunkserver与master的心跳包汇报了有哪些chunks，master告知哪些是已经不在metadata中的，可以自由删除。

这个删除机制相比立即删除，有很多好处，

• 在机器故障很常见的大规模分布式系统中，这个机制简单可靠。 chunk的创建可能只在部分chunkserver上成功；副本删除消息可能丢失，master必须重发。
• 将存储回收合并到了mater常规的后台活动里。 可以批量完成，开销被均摊了。
• 仅在master相对空闲的时候完成。
• 延迟回收提供了应对意外、不可逆删除的保障。

最大的缺点是，延迟机制妨碍了用户在存储紧张的时候，对空间使用的调优。

• GFS通过加快对再次明确删除已删除的文件的回收来解决这一问题。
• GFS还允许对namespace的不同部分设置不同的复制和回收机制。

过期副本检测（Stale Replica Detection）

副本在chunkserver失败且错过修改的时候会过期。

• master维护了一个chunk version number来区分最新和过期的副本。在授权租约前，master会增加chunk version number，并通知所有最新的副本。master和所有副本都会将版本号进行持久化存储。
• 失败的chunkserver在重启后，master通过心跳包可得知副本过期。
• 反过来，如果chunkserver的版本号高于master记录的，master会假设在授权的时候自己失败了，并把更高的版本号作为最新的。
• 过期的副本使用gc进移除。
• mater把primary返回给client的时候，以及通知chunkserver进行clone副本的时候，会带上版本号，二者会检查版本号以保证访问到最新的数据。

容错和诊断

高可用

GFS通过两个简单却有效的策略来实现系统高可用：快速恢复、副本。

• 快速恢复
  • master和chunkserver可快速启动。
  • 不区分正常和非正常终止。
• chunk副本
  • 除副本外，parity和erasure coding对于只读的场景，也是有用的。
• master副本
  • 为了master状态的可靠性，操作日志和checkpoint会被复制到多个机器上。只有flush到本地和所有远程机器上的修改，才认为是已经提交了的。
  • 提交与写入数据的顺序是什么，在写入数据完成前还是后？
  • 如果在log复制到多个机器前，master挂了？如果未复制log无法恢复？
  • shadow master
    • 提供了文件系统的只读访问，因为log可能落后于master；不可写，会导致脑裂。
    • 与primary相同的顺序apply操作日志。
    • 启动时定位chunk副本的位置（启动后就不会很频繁），并定期与chunkserver通信监控它们的状态。
    • 仅当primary更新副本位置时，需要依赖master。
    • 可被晋升为master。
  • 主从切换是如何进行的？

数据完整性

• chunkserver使用checksum来检查数据损坏。
  • 直接对比两个chunkserver上的副本是不不现实的。
  • 两个不同的副本可能是合法的（详见Atomic Record Appends）。
  • 每个chunkserver必须独立维护checksum来维护副本完整性。

chunk结构：

• 细分为64KB block。
• 每个block都有32bit checksum。
• 保留在内存中，且与log一起持久化存储，和用户数据分离。

对于读操作：

• 在返回给client或chunkserver前，会检查与读取范围重叠的部分。因此损坏的数据不会传播开。
• 如果checksum不匹配，返回错误给请求方，并通知master。请求方会读取其他副本，master会从其他副本clnoe数据。新副本到位后，通知chunkserver删除错误的副本。

checksum对（读和追加）性能的影响较小：

1. 读

   • 绝大多数读只跨越少数几个block，因此只需要对少量数据进行校验checksum。
   • GFS client在读取是对尝试对齐checksum block的边界。
   • checksum的查找和比较不需要做I/O，checksum的计算可以和I/O同时进行。

2. 追加

   • 只需要增量的更新最后一个block的last partial checksum，并计算后续新block的checksum。
   • 计算last partial checksum block已经损坏，现在无法检测到它，新的checksum也将与存储的数据不匹配，并且在下次读取时将像往常一样检测到损坏。

   现在无法检测到它（we fail to detect it now），这具体指的是？

但对于覆盖现有chunk某个range的写操作，必须先读取和检查被覆盖range的首个和最后一个block（为了避免新的checksums可能隐藏存在于未被覆盖区域内的数据损坏），然后写入，最后计算和存储新的checksum。

诊断工具

大规模和细致的诊断日志可以极大帮助问题隔离、debug和性能分析，且只有很小的开销。

思考问题

以下问题部分是我自己提出，部分来自Distributed-Systems/Lec03_GFS/Question.md

• 为什么存储三个副本？而不是两个或者四个？
• 为什么不适用RAID？ 重点是整机的容错，而非存储设备的容错。
• chunk的大小为何选择64MB？这个选择主要基于哪些考虑？
  • 减少了client与master交互的需求。
  • 由于chunk较大，client也较为可能在一个给定的chunk上进行很多的操作。
  • 减少了存储在master上metadata的大小。
• master的checkpoint与application checkpointing的区别是什么？
• 论文提到append机制可以用于multiple-producer/single-consumer queues，这个具体是如何实现的？
• GFS主要支持追加（append）、改写（overwrite）操作比较少。为什么这样设计？如何基于一个仅支持追加操作的文件系统构建分布式表格系统Bigtable？
• 为什么要将数据流和控制流分开？如果不分开，如何实现追加流程？
  • 最大化利用每个机器的网络带宽
  • 避免网络瓶颈和高延迟的链路
  • 最小化推送所有数据的延迟
• GFS有时会出现重复记录或者补零记录（padding），为什么？
• 租约（lease）是什么？在GFS起什么作用？它与心跳（heartbeat）有何区别？
• GFS追加操作过程中如果备副本（secondary）出现故障，如何处理？如果主副本（primary）出现故障，如何处理？
• GFS master需要存储哪些信息？master数据结构如何设计？
• 假设服务一千万个文件，每个文件1GB，master中存储的元数据大概占用多少内存？
• master如何实现高可用性？
• 负载的影响因素有哪些？如何计算一台机器的负载值？
• master新建chunk时如何选择chunkserver？如果新机器上线，负载值特别低，如何避免其他chunkserver同时往这台机器迁移chunk？
• 如果某台chunkserver报废，GFS如何处理？
• 如果chunkserver下线后过一会重新上线，GFS如何处理？
• 如何实现分布式文件系统的快照操作？
• chunkserver数据结构如何设计？
• 磁盘可能出现“位翻转”错误，chunkserver如何应对？
• chunkserver重启后可能有一些过期的chunk，master如何能够发现？

Lectures

什么是一致性？

• 正确性条件
• 重要但是当存在数据副本的时候难以实现，尤其是应用并发访问时
• 弱一致性 read()可能返回过期的数据。
• 强一致性 read()使用返回最近write()的数据。

“理想”的一致性模型

• 一个存在副本的FS行为和不存在副本的FS一样。
• 读可以观察到最近的写。

实现“理想”的一致性模型的挑战

• 并发
• 机器失败：任何操作都可能失败
• 网络分区：每个机器/磁盘不是总能访问到的
• 为什么这些挑战难以克服？
  • 需要c/s间的通信：可能影响性能
  • 复杂的协议：难以正确的实现
  • 不少系统没有提供理想的一致性模型

GFS是否实现了“理想”的一致性模型

• 对于目录：实现了
  • 强一致性，只有一个副本
  • 不是高可用，可扩展性受限
• 对于文件：不总是

总结

• GFS优秀的地方：
  • 顺序读写性能高
  • 追加
  • 吞吐量大
  • 数据容错
• GFS不好的地方：
  • master容错
  • 小文件（master是瓶颈）
  • client可能看到过期的数据
  • 追加可能重复

Lab

• Lecture 3没有关于GFS的实验，不过我找到了ppca-gfs，看介绍是上交ACM班一个课程的作业，就用这个来补上GFS的实验吧。
• lab的代码在github.com/chaomai/mit-6.824

References

1. Case Study GFS: Evolution on Fast-forward
2. Google’s Colossus Makes Search Real-Time By Dumping MapReduce
3. 大规模分布式存储系统：原理解析与架构实战