Massive Data Process Homework 1

分布式文件系统(The Google File System)仔细阅读Google File System这篇论文,回答下面的问题。

  • 简述在分布式文件系统中维护数据块一致的步骤。
  • 简述在分布式文件系统中的删除文件的过程。
  • 在分布式文件系统中,Append操作为什么被认为是defined interspersed with inconsistent,并发写为什么会出现undefined的情况。

简述在分布式文件系统中维护数据块一致的步骤。

分布式文件系统中通过以下措施维护数据块一致性:

  • 在所有副本上按相同的顺序执行一个块上的修改操作
  • 使用版本号来检测并复制过期文件,这种过期可能是由于块服务器宕机而造成了部分修改丢失引起的。过期的副本不会再涉及修改操作,主节点也不会将该副本返回给客户端。它们会尽快的进行垃圾回收操作。

而这种措施的实现是由于分布式文件系统完成修改操作时遵循了lease mechanism,通过该机制来确保多个副本间变更顺序的一致性。Master节点为Chunk的一个副本建立一个租约,我们把这个副本叫做Primary Chunk。Primary Chunk对Chunk的所有更改操作进行序列化。所有的副本都遵从这个序列进行修改操作。因此,修改操作全局的顺序首先由Master节点选择的租约的顺序决定,然后由租约中主Chunk分配的序列号决定。通过这样的方式,在完成修改操作时所有的Chunk节点及其副本是经过了同一个修改序列进行的,因此当修改操作完成时数据块是一致的。

  1. 初始数据一致
  2. 修改操作都是一致的
  3. 操作顺序是一致的

简述在分布式文件系统中的删除文件的过程

分布式文件系统中通过垃圾回收机制实现”慢删除文件操作”, 当一个文件被应用程序删除时,Master 将该删除操作以log方式记录下来,并且把文件名修改为包含删除时间戳的、隐藏的文件名,Master节点进行定期的常规文件系统命名空间扫描时,会删除已经被隐藏的超过3天的文件(时间间隔可自定义), 在隐藏文件被删除前仍然可以通过特殊的名字进行读取,也可以通过重命名为普通文件名而实现撤销删除操作的功能。当隐藏文件从命名空间中删除之后,它在内存中的元数据也会被清除。

在对Chunk Server的命名空间做类似的扫描时,Master标识出孤儿Chunk块(比如:任何文件都无法访问到的块),并将那些块的元数据清除。在Chunk服务器与Master节点进行定期的心跳信息交换时,报告其拥有的Chunk子集的信息,Master回复Chunk服务器哪些块在Master节点保存的元数据中已经不存在了,Chunk服务器将释放并删除这些块的副本。

也就是说在分布式文件系统中,删除文件时,先在Master节点中删除对应的元数据信息,然后Chunk 服务器再通过Master和Chunk服务器之间的心跳信息收发待删除数据块信息,实现垃圾回收,最终删除文件。

在分布式文件系统中,Append操作为什么被认为是defined interspersed with inconsistent,并发写为什么会出现undefined的情况。

分布式文件系统的写操作流程解析

图1是写操作的控制流和数据流:

写操作控制流和数据流

分布式系统中的数据修改详细步骤如下:

  1. 客户端询问Master哪个块服务器持有这个块的当前租约,以及这个块的其它副本位置。如果没有一个租约,则Master选择一个副本并授予一个租约。
  2. Master回复客户端primary的标识,以及其它(secondary)副本的位置。客户端缓存这些数据用于以后的修改操作。只有当primary不可达或者接收到primary不再持有租约时才需要再一次请求主节点。
  3. 客户端将数据推送到所有的副本。一个客户端能够以任意顺序进行推送。每个块服务器将数据保存在内部的LRU缓存中,直到数据被使用或者过期被替换掉。通过对数据流和控制流的分流,我们能够通过基于网络拓扑来调度数据流,不管哪个块服务器为primary,以此提高性能。
  4. 一旦所有的副本都确认接收到了数据,客户端将向primary发送一个写请求。这个请求确定了之前的数据被推送到了所有副本。Primary为接收到的所有修改操作分配连续的序列号,这些操作可能来自多个客户端,序列号提供了严格的序列化,应用按序列号顺序执行修改操作,进而改变自己的状态。
  5. Primary将写请求发送到所有的secondary副本上。每个secondary副本按照primary分配的相同的序列号顺序执行这些修改操作。
  6. Secondary副本回复primary,表示它们已经完成了所有的操作。
  7. Primary回复客户端。任意副本上的任意错误都将报告给客户端。在一些错误情况下,写操作可能在primary和一些secondary副本上执行成功。(如果失败发生在primary,它将不会分片一个序列号,并且不会被传递。)客户端的请求被视为已经失败,这个修改的区域停留在不一致的状态上。我们的客户端代码通过重试失败的修改操作来处理这种错误。在从头开始重复执行之前,它将在3-7步骤上做几次尝试。

分布式文件系统的并发写

当一个应用的写操作数据很大以至于跨越了多个数据块时,分布式文件系统会将该写操作分割为多个写操作,这些操作都遵循1.3.1节所描述的控制流,但是可能会被其它客户端上的请求打断或覆盖,即并发写时多个客户端先后发出的写操作的文件共享部分可能最终会包含多个客户端的交叉碎片,即undefined,但是由于lease机制的保障所有副本都是执行的同一个写操作序列,孤儿所有的副本都是完全相同的,即consistent but undefined

分布式文文件系统的Append操作

分布式文件系统中还存在另一种写操作append record,append只在文件的尾部以record为单位(为了避免内部碎片,record一般不会很大)写入数据。append是原子性 的,GFS保证将数据顺序地写到文件尾部至少一次。append record的流程和图2类似,只是在primary有点区别,GFS必须保证一个record存储在一个chunk内,所以当primary判断当前 chunk无足够空间时,就通知所有副本将chunk填充,然后汇报失败,client会申请创建新chunk并重新执行一次append record操作。如果该chunk大小合适,primary会将数据写到数据块的尾部,然后通知其它副本将数据写到一样的偏移。任何副本append失 败,各个副本会处于不一致状态(完成或未完成),这时primary必然是成功写入的(不然就没有4以后的操作了)。客户端重试append record操作时,因为primary的chunk长度已经变化了,primary就必须在新的偏移写入数据,而其它副本也是照做。这就导致上一个失败 的偏移位置,各个副本处于不一致状态,应用必须自己区分record正确与否,我称这为无效数据区。

记录追加操作是修改操作中的一种,在一个记录追加操作中,客户端只需要指定数据,GFS将数据至少一次的原子性的追加到文件。该操作遵循1.3.1节中所示控制流程,只在primary上有一些额外的逻辑。客户端把数据推送到文件最后一个块的所有的副本上,然后将向primary发送它的请求。Primary会检查这次追加操作是否使块的大小超过了最大尺寸(64MB)。如果超过,它将把这个块填充满,通知所有的secondary副本进行相同的操作,并回复客户端表明这个操作将在下一个块上重新执行。(记录追加操作的数据大小严格控制在最大尺寸的1/4以内,以确保最坏情况下碎片的数量在一个可接受范围。)通常情况下,如果记录不超过最大尺寸,primary将数据追加到它的副本上,然后通知secondary把数据写到与primary相同的位置上,最后回复客户端操作成功。

如果在任意一个副本上的记录追加失败,客户端将重试这个操作。因此,在同一个块的副本上可能包含不同的数据,包括同一个记录的全部或部分的重复数据。GFS不保证写入的数据在字节上完全相同,它只保证作为一个原子单元至少被写入一次。这个特性能够通过简单的观察得到:如果操作执行成功,数据肯定被写入到了某些块副本的相同位置。此外,在这之后,所有副本至少都达到了记录尾部的长度,因此,即使一个不同的副本成为了primary,以后的任何记录也都将被放置在更大的偏移位置或者是一个不同的块上。在我们的一致性保障方面,记录追加操作成功的写入数据的区域是被定义的(因此是一致的),反之,介于中间状态的区域是不一致的(因此是undefined的)。

由上述分析可知,在Append操作中,分布式文件系统确保至少有一个记录追加操作被至少一次地原子性追加到文件,从而确保其defined,但是,如果在Primary Chunk中追加成功,而副本追加失败时,客户端会重试追加操作,而之前的部分追加操作会被应用程序通过某种机制使之失效(即不影响其明确性),不同的副本可能失败情况不一致,因此最终各个副本中数据可能局部不一致,故而Append操作是defined interspersed with inconsistent的

  1. write(offset, **)
  2. Append(data): 不关心数据位置
打赏