概述

介绍如下内容:

  • 设计理念/适用场景
  • 系统结构
  • 读写流程
  • 一致性

GFS的设计理念

  • 整个分布式系统是由普通的商用机器构成的,因此故障会比较频繁
  • 系统存储着数百万级的大文件,每个文件的大小基本都大于 100MB;小文件也存在,但是不是优化的目标
  • 文件系统读操作主要有两种:large streaming readsmall random read,且前者占主导; 区别在于large streaming read是顺序访问,读取量大;small random read则刚好相反
  • 文件系统的写操作主要是对文件进行追加append操作, 追加的数据是largesequencial的;且写入后文件就很少会被修改;同样的small random write也支持,但是不是优化的目标
  • 系统需要支持多个client同时写一个文件
  • 相比低延迟,更看重高吞吐量

系统结构

图片加载失败GFS总体系统结构

整个系统包括一个master和若干个chunkserversmaster存储着文件系统的metadatachunkservers 则存储着真正的文件内容,client会先从master获取文件存储在哪一个的chunkserver,然后从这个chunkserver直接读取。该过程有以下几点需要注意:

Metadata

master存储的metadata主要包括文件系统的namespace、文件与chunk的映射、chunk的位置等。

文件系统的namespaceGFS中存储为B+树。树上的每个叶子节点代表普通文件,而中间节点则代表目录文件。根节点是文件系统的根目录。

master启动时会将所有元数据加载至内存中,优点是元数据操作速度很快,但是由于采用的是single mastermaster的内存会限制了文件系统的可扩展性,由于每个 \(64MB\) 的chunk会占据\(64B\)的metadata,则\(64GB\)内存的服务器最多可支持的chunk的数量约为\(64GB/64B = 10亿\)。但由于GFS应用场景是大文件,所以这个问题并不严峻。

Chunk

每个大文都件被划分为若干个固定大小的chunk,每个chunk在创建的时候都会被master赋予一个唯一的ID,称为chunk handle

chunk的大小理论上可为任意值,GFS 中为 \(64MB\)),大的chunk size有以下优点与不足

  • 减少了clientmaster的通信次数,从而减少了master和network的负载;
  • 减少master存储的metadata的大小,因为chunk size越大,chunk的数量就越小
  • 可能会浪费空间,如一个\(65MB\) 的文件会被分成两个chunk,但是第二个chunk只有1MB的数据却占了\(64MB\) 的大小。
  • 可能会导致load imbalance,如一个小文件只有一个chunk,因此存储这些chunkchunkserver会成为hot spot;但是在文章提到的应用中,hot spot并不是一个大问题,因为文章内的应用应用场景是read large multi-chunk files sequentially
  • 此外,在每个chunk都会有另外的两个副本,分别存储在三台机器上,其作用有两个:high availability(HA高可用性)load balancing;在这个机制中,副本位置的选取是一个比较关键的问题,一个好的副本位置定义算法满足下面特性:
    • 保证足够的可靠性,例如,不能将所有副本存放在同一个磁盘或者物理机器上;
    • 保证写入高效性,多副本位置尽量靠近,降低写入延迟,提高读写性能

论文中创建chunk时副本位置的选择方法如下:

  1. 选择存储空间利用率最低的节点和磁盘
  2. 选择最近一段时间内新建 chunk 数量较少的节点和磁盘;
  3. 将多个副本分散在不同的机架上

1和3比较容易理解,2是为了保证一个节点/磁盘不会被频繁新建chunk(新建完接下来就是数据写入了),否则很容易沦为 hot spot,导致磁盘IO和网络带宽被占满,影响效率。

Operation Log

由于metadata存储着GFS的核心信息,因此 GFS 还设置了日志记录metadata的变更信息,这个日志就是Operation Log

Operation Log 中一个关键信息是时间信息,包括chunk的版本、创建时间等,从而能够处理concurrent opration

client请求的operation首先会被master接受,然后master会先写日志,再修改内存中的metadata

为了防止Operation Log过大,GFS会在log达到一定大小时将metadata落盘,称为checkpoint;则 Operation Log只需要存储创建checkpoint的时刻后的所有operation,恢复时根据latest checkpoint恢复最新状态,且重新执行一遍opration log里面的操作即可。

Single Master

Single Master的设计显然存在着单点故障的问题,但是论文表明这么做两个理由

  • 这样大大减化了设计和实现
  • 实际数据直接在clientchunkserver间交流,所以Single Master不会成为bottleneck(瓶颈)
    masterchunkserver通过周期性的HeartBeat通信,用于动态搜集chunkserver的状态:如chunkserver上有哪些chunk,从而master能够及时更新而无需长期存储这些信息

读写流程

读流程

读操作比较简单,上面的系统架构图也显示了这一过程,其步骤如下

  1. client告诉master需要读取的具体文件及其位置(chunk index)
  2. master 返回这部分文件所在的chunservers以及chunkversion
  3. client缓存这些信息避免重复请求。
  4. client请求最近的chunkserver,然后检查chunkserverchunkversion是否与从master获取的相同;如果相同则读取数据,否则重新向 master请求这些信息。

写流程

写操作主要分为两种:writeappend

首先是write的过程,为了让同一个chunk多个副本数据保持一致,master将存储chunk的其中一个chunkserver作为primary,其他是 secondaryprimary用于确定数据写入这个chunk的顺序,secondary则复制primary的写入顺序即可,下图是一个写操作的流程

图片加载失败

  1. client询问master要写入的chunk所对应的primarysecondary位置。
  2. master返回相关信息,client会把信息存入cache,以后就不再重复询问master以节省开销,直到该primary的身份失效。
  3. 客户端把数据发给所有replicas(包括primarysecondary),replicas们会把数据暂存在LRU buffer cache中,但是此时还并没有真的写入磁盘。

    LRU buffer cache:使用LRU思想组织磁盘的缓冲和缓存,以提升效率。

  4. 当所有replica都确认收到数据后,client发写入指令给primaryprimary会给这个指令定一个序列号(当同时收到多个client的请求时,在primary这里确定顺序),primary依序列号修改本地的数据。
  5. primary把写入指令和序列号发给secondarysecondary都依同样序列号修改自己的数据。
  6. primary收到secondary的回复时,返回成功信息给客户端。
  7. 如果有secondary失败了,primary会返回失败信息给客户端。此时数据就是不一致的。客户端会发起重试。

另外一个写操作是record append,其过程与上面相似,但是在这里client不会指定offset,而是只提供数据,GFS会把数据append进去后再返回 offsetclient

record append还在primary添加了以下逻辑:

  • 每次append时会针对待写文件的最后一个chunk; 如果发现该chunk剩余空间不足以写入,则把当前chunk用空白补齐(padding),然后把数据写入新的chunk
  • 数据的写入是at-least-once,如果写失败了(即只在部分secondary上写成功),则会在新的末尾重新写一次,这样就会导致上次已经写成功的replica上数据出现两次,而上次写失败的replica上会有一段空白。返回给客户端的是成功写入的offset位置
  • 客户端程序需要能正确处理这些情况:对于不正确的数据,可以在每个记录开头加一个magic number,或者加一个checksum之类;对于重复的数据,需要客户端判重,比如在记录里加一个unique id

其他策略

Chunk Version

上面提到读写过程中,master均会告诉client对应的chunk目前的version,从而保证clinet读取的是最新的数据。

chunk version会在master为这个chunk选择新的primary时增加,并通知包含这个chunk的所有chunk servers更新这个version
如果client在某个chunk server读到的chunkversion与从master读取的不同,说明这个chunk server 的数据不是最新的。

Snapshot

  • Snapshot是对系统当前状态进行的一次拍照。用户可以在任意时刻回滚到快照的状态。
  • 采用 COW(copy-on-wirte) 机制实现snapshot,拷贝一份chunk进行更新,原来的``chunk`作为快照。
  • 当GFS的Master节点收到Snapshot请求时,其处理逻辑如下
    1. 回收snapshot请求覆盖的文件的chunks上的租约(即撤销primary),这样的话接下来客户端要对文件修改时,就必须向master申请,而此时master就可以对chunk进行复制
    2. master在日志中记录本次snapshot操作,然后在内存中复制一份对应chunk床的metadata
    3. 假如客户端申请更新被snapshot的文件内容,那么找到需要更新的chunk,向其多个副本发送拷贝命令,在其本地创建出chunk的副本 ,之所以本地创建是因为可以避免跨节点之间的数据拷贝,节省网络带宽;
    4. 客户端收到master的响应后,表示该chunk已经COW结束,接下来客户端的更新流程与正常的没有区别。

Checksum

  • checksum解决的是数据完整性问题,即磁盘损坏从而导致数据损坏的问题。
  • 每个chunk会被划分为大小为\(64KB\) 的block,每个block有一个\(32bit\)的checksum
  • client从某个chunk server读取数时,chunkserver首先会验证要读取的数据的checksum,如果checksum不符合已知记录(写入时的记录),会返回错误,从而让client去读取其他chunkserver 上的chunk

一致性

由于GFS中的metadata只在master可写,因此通过加锁保证修改的atomicity;而对于修改metadataconcurrent operationoperation log中定义了这些operation的顺序,metadata的一致性能够得到保证。

因此这里的一致性着重讨论的是文件的一致性,GFS针对文件定义了以下的一致性状态

图片加载失败

  • defined:从客户端角度来看,客户端完全了解已写入集群的数据的offset,例如,客户端串行写入且成功(serial success),此时的状态是defined
  • consistent:客户端角度来看,chunk多副本的数据完全一致,但不一定 defined(defined包含了consistent)
    1. 两个client写写入范围有重合部分。
    2. 一般来说这样并不会出什么问题,因为两者的操作都原子的。
    3. 但是当client的写操作跨度比较大的时候GFS会分解为多个写操作,这样就破坏了操作的原子性。
    4. 数据就很可能undefined了。
  • inconsistent:多副本数据不一致。
  • undefined:数据未定义。

参考文章