MIT 6.5840(6.824) | GFS Note

本篇文章为GFS的学习笔记。

分布式系统的难点

CAP定理，指的是在一个分布式系统中，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性）这3个基本需求，最多只能同时满足其中的2个。

GFS master

Master为Active-Standby模式，所以只有一个Master节点在工作。Master节点保存了文件名和存储位置的对应关系。

Master节点主要存储两个表单：

第一个是文件名到Chunk ID或者Chunk Handle数组的对应。这个表单告诉你，文件对应了哪些Chunk。但是只有Chunk ID是做不了太多事情的，所以有了第二个表单。

第二个表单记录了Chunk ID到Chunk数据的对应关系。这里的数据又包括了：

• 每个Chunk存储在哪些服务器上，所以这部分是Chunk服务器的列表
• 每个Chunk当前的版本号，所以Master节点必须记住每个Chunk对应的版本号。
• 所有对于Chunk的写操作都必须在主Chunk（Primary Chunk）上顺序处理，主Chunk是Chunk的多个副本之一。所以，Master节点必须记住哪个Chunk服务器持有主Chunk。
• 并且，主Chunk只能在特定的租约时间内担任主Chunk，所以，Master节点要记住主Chunk的租约过期时间。

为了保证master节点重启后不丢失，一部分数据需要写入log。Master节点读数据只会从内存读，但是写数据的时候，至少有一部分数据会接入到磁盘中。更具体来说，Master会在磁盘上存储log，每次有数据变更时，Master会在磁盘的log中追加一条记录，并生成CheckPoint（类似于备份点）。

为什么在磁盘中维护log而不是数据库？

数据库本质上来说是某种B树（b-tree）或者hash table，相比之下，追加log会非常的高效，因为你可以将最近的多个log记录一次性的写入磁盘。因为这些数据都是向同一个地址追加，这样只需要等待磁盘的磁碟旋转一次。而对于B树来说，每一份数据都需要在磁盘中随机找个位置写入。所以使用Log可以使得磁盘写入更快一些。

有些数据需要存在磁盘上，而有些不用。它们分别是：

• Chunk Handle的数组（第一个表单）要保存在磁盘上。我给它标记成NV（non-volatile, 非易失），这个标记表示对应的数据会写入到磁盘上。
• Chunk服务器列表不用保存到磁盘上。因为Master节点重启之后可以与所有的Chunk服务器通信，并查询每个Chunk服务器存储了哪些Chunk，所以我认为它不用写入磁盘。所以这里标记成V（volatile），
• 版本号要不要写入磁盘取决于GFS是如何工作的，我认为它需要写入磁盘。我们之后在讨论系统是如何工作的时候再详细讨论这个问题。这里先标记成NV。
• 主Chunk的ID，几乎可以确定不用写入磁盘，因为Master节点重启之后会忘记谁是主Chunk，它只需要等待60秒租约到期，那么它知道对于这个Chunk来说没有主Chunk，这个时候，Master节点可以安全指定一个新的主Chunk。所以这里标记成V。
• 类似的，租约过期时间也不用写入磁盘，所以这里标记成V。

任何时候，如果文件扩展到达了一个新的64MB，需要新增一个Chunk或者由于指定了新的主Chunk而导致版本号更新了，Master节点需要向磁盘中的Log追加一条记录说，我刚刚向这个文件添加了一个新的Chunk或者我刚刚修改了Chunk的版本号。所以每次有这样的更新，都需要写磁盘。GFS论文并没有讨论这么多细节，但是因为写磁盘的速度是有限的，写磁盘会导致Master节点的更新速度也是有限的，所以要尽可能少的写入数据到磁盘。

GFS读文件

1. 客户端向master节点发送想要读取的文件名与想要读取数据在该文件中偏移量
2. Master节点会从自己的file表单中查询文件名，得到Chunk ID的数组。偏移量除以Chunk大小64MB就可以从数组中得到对应的Chunk ID。再从Chunk表单中找到存有Chunk的服务器列表，并将列表返回给客户端。
3. 客户端从Chunk服务器中选一个网络上最近的服务器并向其发送读请求。同时，Chunk与服务器对应关系会被客户端缓存下来，再一次请求时则不用经过master节点。
4. Chunk服务器根据Chunk ID找到对应的Chunk文件，之后从文件中读取对应的数据段，并将数据返回给客户端。

如果读取的数据超过了一个Chunk怎么办？

Robert教授：客户端本身依赖了一个GFS的库，这个库会注意到读请求跨越了Chunk的边界 ，并会将读请求拆分，之后再将它们合并起来。所以这个库会与Master节点交互，Master节点会告诉这个库说Chunk7在这个服务器，Chunk8在那个服务器。之后这个库会说，我需要Chunk7的最后两个字节，Chunk8的头两个字节。GFS库获取到这些数据之后，会将它们放在一个buffer中，再返回给调用库的应用程序。Master节点会告诉库有关Chunk的信息，而GFS库可以根据这个信息找到应用程序想要的数据。应用程序只需要确定文件名和数据在整个文件中的偏移量，GFS库和Master节点共同协商将这些信息转换成Chunk。

从哪个Chunk服务器读取数据重要吗？

Robert教授：是也不是。概念上讲，它们都是副本。实际上，你可能已经注意到，或者我们之前也说过，不同Chunk服务器上的数据并不一定完全相同。应用程序应该要能够容忍这种情况。所以，实际上，如果从不同的Chunk服务器读取数据，可能会略微不同。GFS论文提到，客户端会尝试从同一个机架或者同一个交换机上的服务器读取数据。

GFS写文件

1. 查找主副本

客户端向Master节点发送写请求并查询哪个Chunk服务器保存了文件的最后一个Chunk。

master找出chunk的主副本。如果发现Chunk的主副本不存在，Master会找出所有存有Chunk最新副本的Chunk服务器。（如果一个系统已经运行了很长时间，那么有可能某一个Chunk服务器保存的Chunk副本是旧的，比如说还是昨天或者上周的。导致这个现象的原因可能是服务器因为宕机而没有收到任何的更新。）最新的副本是指，副本中保存的版本号与Master中记录的Chunk的版本号一致。Chunk副本中的版本号是由Master节点下发的，所以Master节点知道，对于一个特定的Chunk，哪个版本号是最新的。

为什么不将所有Chunk服务器上保存的最大版本号作为Chunk的最新版本号？

Robert教授：当Master重启时，无论如何都需要与所有的Chunk服务器进行通信，因为Master需要确定哪个Chunk服务器存了哪个Chunk。你可能会想到，Master可以将所有Chunk服务器上的Chunk版本号汇总，找出里面的最大值作为最新的版本号。如果所有持有Chunk的服务器都响应了，那么这种方法是没有问题的。但是存在一种风险，当Master节点重启时，可能部分Chunk服务器离线或者失联或者自己也在重启，从而不能响应Master节点的请求。所以，Master节点可能只能获取到持有旧副本的Chunk服务器的响应，而持有最新副本的Chunk服务器还没有完成重启，或者还是离线状态（这个时候Master能找到的Chunk最大版本明显不对）。 当Master找不到持有最新Chunk的服务器时该怎么办？Master节点会定期与Chunk服务器交互来查询它们持有什么样版本的Chunk。假设Master保存的Chunk版本是17，但是又没有找到存储了版本号是17的Chunk服务器，那么有两种可能：要么Master会等待，并不响应客户端的请求；要么会返回给客户端说，我现在还不知道Chunk在哪，过会再重试吧。比如说机房电源故障了，所有的服务器都崩溃了，我们正在缓慢的重启。Master节点和一些Chunk服务器可能可以先启动起来，一些Chunk服务器可能要5分钟以后才能重启，这种场景下，我们需要等待，甚至可能是永远等待，因为你不会想使用Chunk的旧数据。 所以，总的来说，在重启时，因为Master从磁盘存储的数据知道Chunk对应的最新版本，Master节点会整合具有最新版本Chunk的服务器。每个Chunk服务器会记住本地存储Chunk对应的版本号，当Chunk服务器向Master汇报时，就可以说，我有这个Chunk的这个版本。而Master节点就可以忽略哪些版本号与已知版本不匹配的Chunk服务器。

2. Primary与Secondary服务器

Master等待所有存储了最新Chunk版本的服务器集合完成，然后挑选一个作为Primary，其他的作为Secondary。Master增加版本号，并将版本号写入磁盘。Master节点会向Primary和Secondary副本对应的服务器发送消息并告诉它们，谁是Primary，谁是Secondary，Chunk的新版本是什么。Primary和Secondary服务器都会将版本号存储在本地的磁盘中。这样，当它们因为电源故障或者其他原因重启时，它们可以向Master报告本地保存的Chunk的实际版本号。

Primary接收来自客户端的写请求，并将写请求应用在多个Chunk服务器中。之所以要管理Chunk的版本号，是因为这样Master可以将实际更新Chunk的能力转移给Primary服务器。并且在将版本号更新到Primary和Secondary服务器之后，如果Master节点故障重启，还是可以在相同的Primary和Secondary服务器上继续更新Chunk。

Master节点通知Primary和Secondary服务器可以修改这个Chunk。它还给Primary一个租约，这个租约告诉Primary说，在接下来的60秒中，你将是Primary，60秒之后你必须停止成为Primary。这种机制可以确保不会同时有两个Primary。

假设现在Master节点告诉客户端谁是Primary，谁是Secondary，GFS提出了一种聪明的方法来实现写请求的执行序列。客户端会将要追加的数据发送给Primary和Secondary服务器，这些服务器会将数据写入到一个临时位置。所以最开始，这些数据不会追加到文件中。当所有的服务器都返回确认消息说，已经有了要追加的数据，客户端会向Primary服务器发送一条消息说，你和所有的Secondary服务器都有了要追加的数据，现在我想将这个数据追加到这个文件中。Primary服务器或许会从大量客户端收到大量的并发请求，Primary服务器会以某种顺序，一次只执行一个请求。对于每个客户端的追加数据请求（也就是写请求），Primary会查看当前文件结尾的Chunk，并确保Chunk中有足够的剩余空间，然后将客户端要追加的数据写入Chunk的末尾。并且，Primary会通知所有的Secondary服务器也将客户端要追加的数据写入在它们自己存储的Chunk末尾。这样，包括Primary在内的所有副本，都会收到通知将数据追加在Chunk的末尾。

但是对于Secondary服务器来说，它们可能可以执行成功，也可能会执行失败，比如说磁盘空间不足，比如说故障了，比如说Primary发出的消息网络丢包了。如果Secondary实际真的将数据写入到了本地磁盘存储的Chunk中，它会回复“yes”给Primary。如果所有的Secondary服务器都成功将数据写入，并将“yes”回复给了Primary，并且Primary也收到了这些回复。Primary会向客户端返回写入成功。如果至少一个Secondary服务器没有回复Primary，或者回复了，但是内容却是：抱歉，一些不好的事情发生了，比如说磁盘空间不够，或者磁盘故障了，Primary会向客户端返回写入失败。如果客户端从Primary得到写入失败，那么客户端应该重新发起整个追加过程。客户端首先会重新与Master交互，找到文件末尾的Chunk；之后，客户端需要重新发起对于Primary和Secondary的数据追加操作。

GFS的一致性

GFS会出现乱序与未写入的情况。

GFS的问题

它最严重的局限可能在于，它只有一个Master节点，会带来以下问题：

• Master节点必须为每个文件，每个Chunk维护表单，随着GFS的应用越来越多，这意味着涉及的文件也越来越多，最终Master会耗尽内存来存储文件表单。你可以增加内存，但是单台计算机的内存也是有上限的。所以，这是人们遇到的最早的问题。
• 除此之外，单个Master节点要承载数千个客户端的请求，而Master节点的CPU每秒只能处理数百个请求，尤其Master还需要将部分数据写入磁盘，很快，客户端数量超过了单个Master的能力。
• 另一个问题是，应用程序发现很难处理GFS奇怪的语义（本节最开始介绍的GFS的副本数据的同步，或者可以说不同步）。
• 最后一个问题是，从我们读到的GFS论文中，Master节点的故障切换不是自动的。GFS需要人工干预来处理已经永久故障的Master节点，并更换新的服务器，这可能需要几十分钟甚至更长的而时间来处理。对于某些应用程序来说，这个时间太长了。