The Google File System 论文阅读笔记
分布式系统的目标:性能,拓展性,容错等等.
1.所面临的基本问题
容错:一台机器的故障发生率也许不高,但是在成千甚至上万台机器的集群中,故障就成了必然事件.系统中的监控,检错,恢复机制设计的重点.
更大,更多的文件:在这里达到几个GB的文件是常见的,如果管理十亿个几KB大小的文件将会给系统带来巨大的负担,所以对于IO操作以及文件分块的大小,也应该重新考虑.
此外,相比于随机写,顺序写(append)的方式成了最常见的方式.
关于GFS的部署规模,大概是1000个以上存储节点,总体来说数百TB(300~500TB).
2.设计总览
首先说明一下,一些基本的前提,这些前提主要围绕着:容错需求,读写场景,存储需求等等.
- 所用的设备不仅数据量大,而且廉价,故障率比较高,需要容错机制.
- 中等数目的大文件(几个GB),假设有几百万100MB设置更大的文件.
- 工作负载分为,大型流式读和小型随机读.
- 有关于写的操作,GFS的应用场景中主要是append.
- 读写会有相关的并发和原子操作的要求.
不过GFS还没有实现完备的
POSIX标准.
在总体结构上,属于主从模式中的单主模式.
不过需要注意的是,在这里的
master,chunkserver并不是狭义地指某一个机器,可以是一个服务器上的一个进程.因而,一个机器其实既可以作为运行一个作为client的进程,也可以运行一个作为chunkserver的进程.
Single Master
简而言之,master是在一个GFS系统中唯一的全局性的管理者,自己不做具体的业务处理.像很多其他的设计一样,仍然通过心跳包和chunkserver通信,记录其状态.单主模式往往是一种比较直观和容易实现的方案,不过当master本身出现宕机时,会带来更大的麻烦,所以master自己会维护一个log文件.这是属于master的容错机制.
master会起到一种路由的作用,当client需要读取数据时,首先要访问master才知道接下来要对那个存储节点进行访问.此外当client访问到某一个chunk时,接下来的访问无需经过master,因为client有一定的缓存机制.
对于clients来说,master根据其所请求的文件名和chunk
id来返回其所访问的chunkserver.
简单地说一下,读操作的实现:
- client根据文件偏移计算出chunk id(毕竟chunk的大小固定).
- client向master发送(文件名和chunk id).
- master返回chunk handle以及replicas的位置.
- client向其中一个repicas发送请求,该请求指定块句柄和该块中的字节范围.
在master内存中有两个表,也就是matadata,其基本内容如下:
前者比较适合使用hashmap实现,对于单个key的查询hashmap性能比较优越.而第二个表比较适合使用B-tree,B-tree更适合范围查询的情况,因为第二个table的key是chunk
handle,相对而言,当访问一个跨越多个chunk的文件时,也就是多个连续的chunk
handle,相当于范围查询了,B-tree效率比较高.在内存中存储metadata的优点,便于密度较大的client请求时,能够做出更快的响应,读取查询起来更快.
不过也并非完全nv的,也会有一些持久化机制,后面会进行更具体地说明.
Chunk Size
64MB,比一般的文件系统块要大不少.也是每个chunk replica的基本单位.
其优点有哪些呢?
1.大粒度的chunk有利于利用局部性的特点,进而一定程度上可以减少
client与master以及client与chunkserver之间交互的数据开销.2.matadata的所占大小(毕竟数量相对较少了)减小,有利于其在内存上存储的特点.
但是对于小文件较多的情况不利.
除此之外,在master将文件Chunk Mappings的时候,会给每一个chunk划分出来一个全局唯一的标识符.
Metadata
存储在master的内存中.有三类:文件及其chunk的namespace,文件到块的映射,每个chunk副本的位置.都会在内存中有存储,并且前两类会有log文件作为持久性存储,主要是为了在故障后快速恢复.后者只在内存中存储,master通过与chunk server交互(一般master开机和chunk
server加入和离开时发生)即可获取并更新the locations of each chunk replicas.在log相关的操作中,主要包含了metadata变化的历史记录,如果log丢失,那么master的可靠性就几乎彻底失去了保证,因此对于log也需要做备份,一般在一个远程的机器上,并且当master与远程复制保持一致时才会相应一个client请求.
关于其中master上维护的chunk location这一信息,master指通过系统启动之初,及其后来和chunk
server不断地心跳包来维护的.也就是说,并不是master决定了chunk
server中存储的chunk,而是master追随每个chunk
server中的chunk的变化.这对于分布式系统中的chunk
server可能发生的各种变更问题,能够进行有效地处理.这个信息并不需要通过log进行持久化.
非常重要,其内容主要是metadata修改的记录,是metadata
的持久性机制.对于metadata一般除了在本机上存储,还会有多个远程的存储备份,一旦Log出现了问题,这个master的容错与恢复也就彻底失败了.对于Log的更新:本机和远程机上的Log的写入(磁盘)都是先于用户的请求处理的.这体现了系统中写日志的一种套路,也就是先写日志,在写数据.再通过日志进行恢复时,master会遍历日志文件记录,逐个重做.如果无论如何都重新做一遍的话,将会是非常麻烦的,所以引入一种checkpoint机制.总的来说,这里的恢复机制和数据库系统中的颇为相似.
Consistency Model
其一致性模型是弱一致性的,但是实现起来高效比较简单.
关于metadata中namespace的变化,master会使用个锁来进行控制原子性和并发.Mater
节点的 operation log 定义了这些操作在系统中的全局顺序.
关于这个表的话,首先解释以下几个关键的名词:
consistent,任何chunk server replicas所读取到的结果都是相同的.defined,当发生文件的写操作后,所有client还是能够读取到consistent的结果,并且还是写数据生效后的结果.consistent but undefined,能保持consistent,但是对于写数据的变化不能保证及时看到.inconsistent.最差的情况,如果不能满足consistent那么defined一定不能满足.
其中defined是最高级别的一致性.关于写的情况,主要有两种,第一种是write,也就是对于某个chunk以某个offset为起始地址开始写数据,另一种是直接在某位进行append.write这种操作并不是原子操作,比如说(64MB为一个chunk的size)要往一个chunk的54MB的起始地址写入20MB,需要先讲这个chunk的剩余10MB写,然后写下一chunk的10MB,如果此时有另一个client并发进行一样的操作,由于其顺序往往无法保证,因此可能导致最终读取到的结果,不是某一个client完整预期的结果,而是多个client“混合写”的结果.关于append,不是在末尾的offset上写,而是通过选择一个offset之后再写.
3.系统交互
接下来说明的是,在这个系统中client,master,chunkservers的交互方式进而实现数据修改,原子记录追加等.
Leases and Mutation Order
mutation就是改变metadata或者chunk内容的操作,比如说write和append.每次修改应该作用于chunk的所有副本上,之所以采用了lease的机制,主要是为了在众副本上,有一个统一的mutation顺序.
这种机制是为了保证各chunkserver写操作具有一致性的.leases机制为后面对副本的写操作做铺垫,因为对于写操作来说,往往考虑先选择某一个节点接收写请求,然后再让该写节点通知其他副本进行同步更新.除此之外,这种设计还减小了master的开销.在lease中的timeout方面,初始值一般为60s,如果这个primary处理了一个mutation请求,就会增加相应的timeout,通常会被允许增加timeout,这些信息往往会被附加在master与chunkservers的心跳包中(比如说心跳包也许还会附带是否是primary以及已经处理的写请求数量等),设置timeout还有个好处就是可以使得该primary在发生宕机等问题时,可以自动退出,因为避免了脑裂的潜在问题.
当一个client要对某个chunk进行写操作时,其过程可以如下:
- client向
master请求该chunk当前的primary机器. - 然后接收到
master的相应.client将会缓存这个数据. - client将这些数据发给所有副本,先存在缓存中.
- 当所有副本收到数据后,client就会向
primary发送一个write请求.这个请求标识了所有之前push副本的数据,primary会给其收到的所有修改指定序号. primary把write请求传递给所有的secondary副本,每个secondary根据指定的序号修改应用,primary等待secondary回复.secondary接收到primary指定的序列号后,处理操作,处理完后通知primary.primary回复client,如果有错误也会反馈.失败时,client通常通过重试,来进行处理.
当write单位的大小跨越多个chunk,通常会拆分成多个请求,转化为多个chunk的操作.
Atomic Record Appends
传统的写入操作一般是指定文件+偏移量进行操作的,但是这在并发的条件下容易出现问题.
在GFS中,client只需要指定要写入的数据,无需考虑所写入文件的偏移量,其偏移量由chunkserver决定,也就是之前提到的primary
node.具体而言,其内部执行的逻辑如下(record append
):
- Client 确定 file name 以及要写入的 byte data.
client向master发送请求,这时不需要加上byte data.master接收到file name通过查询得出对应的chunk servers,并发送给client(更具体地说应该是primary).primary会根据自己文件的情况确定偏移值.- 之后的过程类似于前面所提到的.
4. master的行为
简单地概括一下,master的操作:
- master记录chunks放置的位置.
- 创建新的
chunks和之后的副本. - 协调各种各样的系统范围内的活动,保持chunks完全拷贝.
- 在chunkserver上做负载均衡.
- 回收未使用的内存空间.
namespcace management and locking
对于master中对于namespace的操作使用上锁的方式来实现对多种操作的正确串行顺序.GFS的目录和文件机制没有一般的文件系统那样完备.namespace就像是一个map将文件的相对路径名或者绝对路径名映射到一个metadata.因而便于在内存中存储和查询.对于namespace的树中,每个节点对应一个full pathname,每个节点都有一个读写锁.
有关于写操作所涉及的规律:
- 最底层节点获得写锁.
- 其他父,祖父节点只需要读锁(可以共享读).
Replica Placement
这种机制的目的主要是:
- 最大化可靠性和可用性.
- 最大化网络带宽利用率.
replicas在chunkserver中的分配是有讲究的,在GFS一般是分布存储在不同机架的chunkserver,这样能够减少压力集中在一个机架的情况,也使了当一个机架故障时,仍然有较好的可靠性和可用性.
Garbage Collection
当一个文件应用删除.
首先只在master发生变化,即将先将删除记录写入日志再文件重命名(hidden
name,其中包含删除的时间).
此外master对于namespace会有周期性地扫描,移除3天以上的hidden files相关的metadata,也即是说在3天之内还是有恢复的余地的.
而对chunkserver中的删除应该怎么进行呢?是通过心跳交互间接实现的.
chunkserver和master的心跳包中,会有关于其chunks的信息,master进而响应其中有哪些没有相应的metadata,chunkserver接受到之后进而在检查这些chunks,然后执行删除.
Stale Replica Detection
master中对于每个chunk都会维护版本号,版本号会在每次lease时对相应的版本号进行自增(发生在metadata本地的),然后会将版本号告诉其他replicas.如果某个replica不可用,就收不到版本更新的消息,也就不会自增,当重新上线时,向master发送心跳包时(附带版本号),这个时候可以比对发现此replica的问题.如果master的版本比较低,将会更新为这个比较高的版本.版本号的通知是优先于写操作的执行的.
对于出现版本过旧的replica会在定时地垃圾收集任务中删除有过期问题的replicas,如果client对过期的chunk发出请求,master会响应此chunk不存在.
5.容错和诊断
High Availability
其中主要的策略是fast recovery和replication.
GFS对于chunkserver的退出状态,不区分正常和异常退出,通常也是通过kiil的方式去关闭chunkserver,此外chunkserver也是拥有快速重启的能力,所以client和master借助重发请求就可以做到fast recovery.
此外,我们还会对chunk进行复制,一般情况下复制的级别是3,也就是有3份.
对于master来说除了有log + checkpoint的容错机制除外,还会有一个shadow master,当master宕机,shadow master能够提供可读服务,但是shadow master和master只能保证是弱一致性的.
这与append的特点有关,即使如此,只能说读不到比较新的数据,但不会读到错的旧数据.
对于shadow master的更新来说,依靠的是master日志的replicas.
shadow master不参与和其他chunkserver的通信.
Data Integrity
数据完整性就是检查存储的数据有无错误或者丢失.
数据检查的工作会在chunkserver中有所进行,其使用的方式是chunksum.但如果通过比对不同chunkserver中的chunk来实现,将会是非常困难的.
chunksum和用户数据分开,但是存储在内存上,最终通过日志来持久化.
当client向chunkserver发送请求时,首先chunkserver会对读操作涉及的block进行检验,如果不匹配就会向请求者client发送一个错误响应,并向master报告错误,client收到之后就向另一个replica请求读取,master则会从另一个replica克隆数据块,并指示chunkserver删除其replica.
对于最有特色的apend操作来说,会有额外的优化,就是增加最后部分block对应的chunksum就可以了.