分布式基础——GFSGoogle file system

设计大型分布式系统或大型存储系统的出发点：想获得巨大的性能加成，从而利用数百台计算机的资源同时完成大量的工作。

分片：将数据分隔放在大量的服务器上，从而并行的从多台服务器读取数据。

但是，如果大量的服务器进行分片，故障将常态化。如果有数千台服务器，总会有一台服务器宕机，每天甚至每小时都会发生错误。我们需要一个自动的容错系统。实现容错的最有用的一种方法是复制，只需维护2—3个数据的副本，当其中一个故障了，可以使用另一个。但是，如果复制得到两个副本，在工作的过程中，副本变得不一致了，他们便不再互为副本，获取到的数据也取决于向哪个副本请求数据。这是不一致（inconsistency）问题。

在现实世界中，会构建多副本的分布式系统，提高容错能力。

目标：构建一个大型的、快速的文件系统，这个文件系统是全局有效的，这样各种不同的应用程序都可以从中读取数据。

一种构建大型存储系统的方法是针对某种特定的应用程序构建特定的裁剪的存储系统，但如果另一个应用程序也想要一个大型存储系统，那么又需要重新构建一个存储系统。如果有一个全局通用的存储系统，那么如果一个人存储了大量的数据，其他人也可以申请权限来查看这些数据，因为使用了同一个存储系统。

为获得大容量和高速的特性，每个包含了数据的文件都会被GFS自动分割并存放在多个服务器上；这样读写操作会变得很快，因为可以从多个服务器上同时读取同一个文件，进而获得更高的聚合吞吐量；将文件分割存储还可以在存储系统中保存比单个磁盘还要大的文件。由于在数百台服务器上构建存储系统，我们希望系统有自动的故障修复。

GFS被设计成只在一个数据中心中运行，并没有将副本保存在世界各地，单个GFS仅存在于单个数据中心的单个机房里。理论上讲，数据的多个副本应该彼此之间间隔的远一些，以防止部分不可控因素导致所有副本都失效，但是这种方式实现起来较难，故GFS仅局限在了一个数据中心内。

GFS在各个方面对大型的顺序文件读写做了定制。在存储系统中有一个完全不同的领域，该领域仅对小份数据进行优化：如一个银行账户系统就需要一个能读写100字节的数据库，因为100字节就可以表示人们的银行账户。而GFS是为TB级别的文件服务的，且GFS只会顺序处理，不支持随机访问，从某种程度上，他类似于批处理。GFS并没有花费太多的精力来降低延迟，它的关注点在于巨大的吞吐量上，所以单次的操作都涉及到MB级别的数据。

GFS的论文提出了一个异类的观点：存储系统具有弱一致性也是可以的。GFS的目标是提供更好的性能，并不保证返回正确的数据。GFS作为Google——一个搜索引擎的系统，少量的错误并不重要，在上万个搜索结果中丢失几条或搜索结果排序错误重要性并不是那么大。

针对GFS可能会返回错误的数据，我们可以在应用程序中做一些补偿。应用程序可以对数据做校验，并明确标记数据的边界，这样应用程序在GFS返回不正确数据时可以恢复。

GFS中的master是active-standby模式，故只有一个master节点在工作。master节点保存了文件名和存储位置的对应关系。GFS还有大量的chunk服务器，可能会有数百个，每一个chunk服务器上都有1~2块磁盘。

master节点用来管理文件和chunk的信息，chunk服务器用于存储实际的数据。master节点知道每一个文件对应的所有chunk的ID，每个chunk为64MB大小，它们共同构成一个文件。master节点知道文件的第一个chunk存储在哪，第二个chunk存储在哪，当需要读取文件中的任意部分时，我们需要向master节点查询对应的chunk在哪个服务器上，然后直接从chunk服务器上读取对应的chunk数据。

master节点内保存的数据内容，重点是两个表单：第一个是文件名到chunk id 或chunk handle数组的对应。这个表单告诉你，文件对应了哪些chunk。第二个表单记录了chunk ID到chunk数据的对应关系，chunk数据包括：chunk服务器的列表（每个chunk存储在哪些服务器上）；每个chunk目前的版本号；哪个chunk服务器持有主chunk（所有对chunk的写操作必须在主chunk（primary chunk）上顺序进行，主chunk是chunk的多个副本之一）；主chunk的租约过期时间（主chunk只能在特定的租约时间内担任主chunk）。

上述数据都存储在内存中，当master故障时，这些数据就丢失了。为能让master重启而不丢失数据，master节点会同时将数据存储在磁盘上。故master节点读数据时只会从内存中读，写数据时至少有一部分数据会接入到磁盘中。更具体的来说，master节点会在磁盘上存储log，每次有数据变更时，master节点会在磁盘的log中追加一条记录，并生成checkpoint（相当于备份点）。

有些数据需要存在磁盘上，而有些不用：chunk handle的数组（第一个表单）必须保存在磁盘上（非易失，non-volatile）。chunk服务器列表不用保存在磁盘上，因为master节点重启后可以与所有的chunk服务器通信，并查询每个chunk服务器存储了哪些chunk（volatile）。版本号要不要取决于GFS是如何工作的，这里先认为他需要写入磁盘（non-volatile）（因为如果版本号在故障重启中丢失，且部分chunk服务器持有旧版本的chunk，master节点就无法区分哪些chunk服务器的数据是最新的，哪些是旧的）。主chunk的ID，不用写入磁盘，因为master节点重启后会忘记谁是主chunk，它只需要等待60秒租约到期，这时便没有主chunk，master节点可以安全的指定一个新的主chunk（volatile）。租约过期时间也不用写入主chunk（volatile）。

只要文件扩展到了一个新的64MB需要新增一个chunk或者指定了新的主chunk，导致版本号更新了，master节点就需要向磁盘中的log追加一条记录，记录向这个文件新增的chunk或刚刚修改了chunk的版本号。故每次有这样的更新，都需要写磁盘。但写磁盘的速度是有限的，写磁盘会导致master的更新速度也是有限的，故应该尽量少的写入数据到磁盘。

这里选择在磁盘中追加log而不是数据库的原因:数据库本质上是一种B-tree或hash table，相比之下，追加log会非常的高效，因为可以一次性将最近的多个log记录写入磁盘。而对于B-tree来说，每一份数据都必须在磁盘中随机找个位置写入。故使用log可以使磁盘写入的更快一些。

master节点故障重启，并重建它的状态时，从log的最开始重建系统会非常的耗时。故master节点会在磁盘中创建一些checkpoint点，这可能会花费几秒或一分钟，但master节点重启时，会从log中最近的一个checkpoint开始恢复，再逐条运行从checkpoint开始的log，最后恢复自己的状态。

GFS read file：应用程序或GFS客户端有一个文件名和从文件的某个位置读取的偏移量，客户端将这些信息发送给master节点，master节点会从file表单中查询文件名，得到chunk ID的数组。每个chunk为64MB，故偏移量除以64MB就可以从数组中得到对应的chunkID。master在从chunk表单中找到存有chunk的服务器列表，并将列表返回给客户端。 总结：1.客户端将文件名和偏移量发送给master（读取特定文件的特定偏移位置上的某段特定长度的数据）（文件名、长度、起始位置）。 2.master节点将chunk handle和服务器列表发送给客户端。

客户端从这些chunk服务器中挑选一个来读取数据。在GFS的论文中，客户端会选取一个网络和是哪个最近的服务器，将读请求发送到那个服务器上。客户端可能会连续多次读取同一个chunk的不同位置，故客户端会缓存chunk和服务器的对应关系，这样当再次读取同一个chunk的不同位置时，就不用一次次向master请求相同的信息。

最后客户端会与选出的chunk服务器通信，将chunk handle和偏移量发送给chunk服务器。chunk服务器会在本地的硬盘上将每个chunk存储成独立的Linux文件，并通过普通的Linux文件系统管理。chunk文件会按照handle命名。chunk服务器需要做的就是根据文件名找到对应的chunk文件，之后在文件中读取对应的数据段，并将数据返回给客户端。

客户端本身依赖于GFS的一个库，当数据读取跨越chunk边界时，这个库会注意到读请求跨越了chunk的边界，然后将读请求拆分，之后再将其合并起来。

GFS write file：从应用程序的角度，写文件和读文件的接口十分相似，都是调用GFS的库。写文件时，应用程序会告诉库函数，我想对这个文件名的文件在这个数据段写入当前存在buffer中的数据。简化一下，后面只讨论将buffer中的数据追加到这个文件名对应的文件中的情况（记录追加（record append））。在简化的情况下，客户端在写文件时，会先master发送请求：向这个文件名对应的文件追加数据，请返回文件中最后一个chunk的位置。

多个客户端同时写一个文件时，一个客户端无法知道其他客户端写了多少，就不知道文件到底有多长，就不知道该往什么样的偏移量或向哪个chunk追加数据。所以写文件必须通过chunk的主副本（primary chunk）写入，而不像读文件时可以从任何最新的chunk副本读取数据。如果chunk的主副本不存在，master节点会找出所有存有chunk最新副本的chunk服务器。如果一个服务器运行了很长时间，那么可能会有chunk服务器保存的chunk副本是旧的，其原因可能是服务器因宕机没有收到任何更新。最新副本是副本中保存的版本号与master记录的chunk版本号一致的副本。这是为什么chunk版本号需要保存在磁盘这种非易失的存储中的原因。如果版本号在故障重启中丢失，且部分chunk服务器持有旧的chunk副本，master就无法区分哪些服务器的数据是最新的。

不能将所有chunk服务器上保存的最大版本号作为chunk的最新版本号：master重启时，无论如何都要和所有的chunk服务器通信，从而确定哪个chunk服务器上存了哪个chunk。如果所有持有chunk的服务器都响应了，那么把最大版本号当最新版本号就没有问题。但是当master节点重启时，部分chunk服务器可能离线或失联或自己也在重启，而不能响应master节点的请求。这时master节点可能只能获取到持有旧版本的chunk服务器的响应，这时吧最大版本号当作最新版本号显然是不对的。

当master节点找不到持有最新chunk的服务器时，master节点会定期和chunk服务器交互，查询他们持有的chunk版本。要么master节点会等待，不响应客户端的请求；要么会返回给客户端：目前还不知道chunk在哪，过会儿重试吧。

每个chunk服务器会记住本地存储chunk对应的版本号，master节点会整合具有最新版本chunk的服务器，忽略版本号与最新版本号不匹配的chunk服务器。

所以，当客户端想对文件进行追加但不知道文件尾的chunk对应的primary在哪时，master节点会等所有存储了最新chunk版本的服务器集合完成，挑选一个作为primary，其他的作为secondary。然后，master会增加版本号（版本号只在master节点认为chunk没有primary时才会增加），并将版本号写入磁盘 。再然后，master会向primary和secondary副本对应的服务器发送消息，告诉它们谁是primary、谁是secondary，chunk的新版本是什么。primary和secondary服务器会将版本号存储在本地的磁盘中，这样，当它们因电源故障等原因重启时，可以向master报告本地保存的chunk的实际版本号。现在有了一个primary可以接收来自客户端的写请求，并将写请求应用在多个chunk服务器上。master可以将实际更新chunk的能力转移到primary服务器。在将版本号更新到primary和secondary服务器以后，如果master节点故障重启，还是可以在相同的primary和secondary服务器上继续更新chunk。

master节点会给primary一个租约，在租约内primary将是primary，租约结束后必须停止成为primary。这种机制可以保证不会同时有两个primary。

在GFS中，客户端会将要追加的数据发送给primary和secondary服务器，但数据不会立刻追加到文件当中，而是会写入到一个临时位置。当所有服务器都返回确认消息说已经有了要追加的数据，客户端才会向primary服务器发送消息，将数据追加到文件中。

primary或许会从大量的客户端收到大量的并发请求，primary服务器会以某种顺序，一次仅执行一个请求。对于每个客户端的写请求，primary会查看文件末尾的chunk，确保chunk中有足够的剩余空间，然后将客户端要追加的数据写入在他们自己存储的chunk末尾。primary也会通知所有secondary服务器也将客户端要追加的数据写入chunk末尾。

如果所有secondary服务器都将数据成功写入，并回复了“yes”，primary会向客户端返回写入成功。如果存在secondary没有回复或回复“No”，primary会返回写入失败，，然后客户端应当重新发起整个追加过程。客户端会先重新和master交互，找到文件末尾的chunk；然后客户端重新发起对primary和secondary的数据追加操作。最终master会ping所有的chunk服务器，如果secondary挂了，master可以发现并更新primary和secondary的集合，之后在增加版本号。同样的，master也会一直通过定期的ping来检查primary是否存活。

master发送了一些ping给primary，primary没有响应，master不能立即指定一个新的primary。因为可能是因为网络原因而导致ping没有成功，primary还可以与客户端进行交互，这是如果为chunk指定了一个新的primary，就会有两个primary同时处理不同的写请求，最终导致两个不同的数据拷贝，这称为脑裂（split-brain）。脑裂通常由网络分区引起，如：master无法与primary通信，但primary可以与客户端通信，这就是一种网络分区问题。

为了避免脑裂，master要为primary分配一个租约，primary仅仅只在租约内有效，租约到期时，primary会忽略或拒绝客户端的请求。master和primary都知道租约有多长，如果二者不能通信，master会等租约到期再指定新的primary。

客户端会通过缓存提高效率，通过短时间内缓存primary的身份信息而不每次都向master查询primary的信息。

客户端只将数据发送给离它最近的副本，之后那个副本会将数据转发到另一个副本，以此类推形成一条链，直到所有的副本都有了数据，这样一条数据传输链可以在数据中心内减少跨交换机传输，否则，所有数据吞吐都在客户端所在的交换机上。

对新的文件（没有副本）进行追加：master发现该文件没有关联的chunk，master或许会通过随机数生成器创造一个新的chunk ID。然后创建一条新的chunk记录（版本号为1），再为这个空chunk随机选择一个primary和secondary。

GFS设计的很简单，为应用程序提供了一个相对简单的写入接口，但应用程序需要容忍读取数据的乱序。如果应用程序不能容忍乱序，可以通过在文件中写入序列号，这样在读取的时候可以自己识别顺序。如果应用程序对顺序十分敏感（如电影），那么就不要将文件并发写入，可以只用一个客户端连续顺序写入。

如果要把GFS设计成强一致性系统，可以考虑一下内容：1、让primary探测重复的请求，确保同一数据不会在文件中重复出现。2、如果primary要求secondary执行一个操作，secondary必须要执行而不是只返回一个错误给primary。对于一个严格一致的系统来说，不允许secondary忽略primary的请求而没有任何补偿措施。如果一个secondary有一些永久性故障，必须有一种机制将secondary从系统中移除，primary与剩下的secondary继续工作。3、当primary要求secondary追加数据时，直到primary确信所有的secondary都能执行数据追加之前，secondary必须小心不要将数据暴露给读请求。故对于写请求，我们需要两阶段提交（two-phase commit）：第一阶段，primary向secondary发请求，要求其执行某个操作，并等待secondary回复是否能完成该操作，secondary并不实际执行操作。第二阶段，如果所有secondary都回复可以执行该操作，primary在要求所有secondary执行该操作。4、新primary上任时，需要显式的与secondary进行同步，以确保操作历史的结尾是相同的。因为primary奔溃时，可能有一组操作已经发送给了secondary，但是primary在确认所有secondary收到了请求之前就奔溃了，这时一个secondary会接任成为primary，但由于部分副本没有收到前一个primary奔溃前发出的请求，新primary和剩下的secondary会在最后几个操作产生分歧。5、在执行写操作的过程中，不同secondary之间可能会有一点差异，客户端可能从master那里获取的是稍微过时的secondary，解决方法：将所有读请求发送给primary，因为只有primary知道哪些操作实际发生了；或者对secondary也设置一个租约系统，这样就知道secondary在哪些时间可以合法的响应客户端了。

实现强一致增加了系统的复杂度，增加了系统内组件的交互。

GFS最大的局限性可能在于它只有一个master节点，因为：master节点必须为每个文件、每个chunk维护表单，随着文件越来越多，最终master会耗尽内存来存储文件表单。虽然可以增加内存，但是单台计算机的内存也是有上限的；当master节点要承担数千个客户端的请求，而master节点的CPU每秒只能处理数百个请求，master节点还需要将部分数据写入磁盘，客户端数量很容易就能超过单个master的能力；应用程序很难处理GFS奇怪的语义（GFS副本数据的不同步）；master节点的故障切换不是自动的，GFS需要人工干预来处理已经永久故障的master节点，并更换服务器，这可能需要几十分钟甚至更长的时间，对于某些应用程序来说，这时间太长了。

这篇好文章是转载于：学新通技术网