GFS论文整理(三)
Snapshot:
??? snapshot(快照)操作瞬间为文件或者目录树（即source）做一个copy，最小化对正在进行的变更操作的打断。我们的用户使用快照功能来快速创建数据集庞大的分支副本（经常是副本的复制，递归地），或者在尝试应用数据修改之前对当前状态设置checkpoint，这样简单地提交或者回滚。
??? 像AFS，我们使用标准的copy-on-write技术来实现snapshot。当master收到snapshot请求后，它首先撤销需要被snapshot的文件中所有chunks上的所有的outstanding leases（？？未交付的lease，大概意思可能是未被收回，尚在起效的leases），这就保证接下来的对这些chunks的所有write操作都需要与master交互一次来获知leases的持有者。这就给master一个创建chunk copy的时机。（声明：snapshot并不是文件的copy，此处论文用词有误）
??? 在这些leases被撤销或者过期后，master将这个操作记录在日志中。然后它通过复制源文件metadata或者目录树的方式，把这个log record应用到它的内存状态（估计大概意思是在leases撤销后，master就把这个record信息写入内存，作为一种状态保存，同时开始复制medatadata of the source file? or directory tree）。这个新建的snapshot文件和源文件指向相同的chunks。
??? 在snapshot操作后，一个client需要向chunk C写入操作，它向master请求当前的lease持有者。Master 发现对chunk C的引用计数器大于1（参见snapshot原理，创建文件的snapshot，会造成源文件的引用计数器+1，物理引用指针）。它（master）推迟对client的响应，而是创建一个新的chunk handle C‘，然后它问询每个chunkserver（持有C的replicas）来创建一个新的称为 C’ 的chunk。 通过在同一个chunkserver上创建新的chunk（每个chunkserver，各自创建自己的新chunk），我们能够确保数据在本地复制，而不是通过网络传输（硬盘的速度是网速的数倍，通过snapshot之后，每个chunkserver都有了对file的copy信息）。基于这一点，请求的处理和其他chunk没什么区别了：master给其中一个replicas C‘授权leases，然后响应给client，然后client就可以像往常一样write操作，而且它无需知道C’是从原有的chunk上新建的。
?
Master operation：
??? master处理所有的namespace操作。此外，它管理整个系统的chunk replicas：它负责chunk的物理位置分配，创建新chunk和replicas，协调多个系统范围内的活动来保持chunk全量的replicated，在所有的chunkserver间负载均衡，回收无用的storage。
?
Namespace管理和锁：
??? master的许多操作是需要花费较长的时间：例如，snapshot操作需要撤销chunkserver中所有chunk（snapshot所覆盖，即需要snapshot的文件对应的chunk）上的leases。在它们运行的时候，我们不想拖延master的其他操作。因此，我们允许多个操作同时进行，我们在相应namspace的region上使用locks，来确保适当的序列化。
??? 不像传统的文件系统，GFS没有per-directory （按照目录区分数据）数据结构列出那个目录下的所有文件。也不支持对一个文件多个别名（像unix下的软/硬链接，hard links）（大概意思是，GFS不像其他文件系统，直接以pathname进行file管理，例如window的文件系统，GFS在这种pathname上做了一些工作，转换成namespace的方式，其实namespace也是给予pathname的，但是做了一些自己的mapping）。GFS逻辑上以一个映射全路径名到metadata的查找表格来描述它的命名空间（GFS logically represents its namespace as a lookup table mapping full pathnames to metadata），使用前缀压缩，这个表格可以被高效的在内存中展示。Namespace tree的每个节点（绝对的文件名称或者绝对的路径名）有一个相关的read-write lock。
??? 每个master操作之前需要获取一系列的locks。如果它（master）调用/d1/d2.../dn/leaf，它将会获取read-locks在路径名为/d1,/d1/d2,......,/d1/d2/..../dn,同时也会获取/d1/d2/.../dn/leaf（全路径）上read-lock或者write-lock。注意leaf节点可能是一个文件或者是一个目录，这个依赖于操作类型。
??? 我们描述一下当/home/user在snapshot成/save/user时，locking机制是如何阻止/home/user/foo文件被创建的。Snapshot操作在/home和/save上获取read-locks，在/home/user和/save/user上获取write-locks。文件创建操作在/home和/home/user上获取read-locks，在/home/user/foo上获取write-locks。这两个操作将会被适当的序列化，因为他们都在尝试在/home/user上获取冲突的locks。创建文件操作不需要在其父目录上（parent directory）获取write-locks。在名称上的read-lock故意防止父目录被删除。
??? 这种锁模式的一个比较好的特性就是允许一个目录下并发的变更。例如，在同一目录下，允许多个文件同时创建：每个操作都在目录名称上获取一个read-lock，和文件名称上的write-lock。目录名称上的read-lock能够阻止目录被删除/重命名/snapshot。在file name上的write-lock序列化的去尝试两次创建新文件（同一名称的文件，尝试两次）。
??? 因为namespace能有无数个nodes，read-write lock对象和它们相关连，并且在它们不用时删除（删除locks）。所以，locks的获取是按照一致的顺序，以避免死锁：它们（locks）以所在namespace tree的level作为第一排序，同一级别按照字典顺序。
?
Replica placement：
??? 一个GFS的集群是一个多级的高度分布式系统。它通常会有数百台chunkserver，分布在数个机架中。这些chunkservers轮流为来自相同的或者不同的racks上的客户端提供访问服务。不同机架（racks）的2台机器通信可能会跨越多个网络交换机。此外，一个机架上的出口和入口贷款可能比此机架上所有机器的整体带宽要小。多极分布式出现一个独特的挑战：分布式数据的扩展性，可靠性，和可用性。
?
Creation，re-replication，rebalancing（replica的创建，重复制，重均衡）:
??? chunk replicas新建的原因有三：chunk创建，重新复制，重新均衡。
??? 当master新建一个chunk，它将选择放置这个初始为空的replicas的位置。它将考虑几个因素：1）我们想把此replica放置在磁盘利用率低于平均值的chunkserver上 2）我们想限制每个chunkserver最近创建chunk的数量，虽然创建本身开支较小，它意味着即将有大量的write操作因为chunks的新建是由于有大量写操作，并且在我们这种append-once-read-many的workload情况下，通常他们在写入成功后，实际上就变成了只读。3）据上所述，我们想跨机架分布这些chunk replicas。
??? 当一个chunk的replicas的数量低于用户制定的目标后，master就会re-replication这个chunk。有很多原因会触发这种情况：一个chunkserver不可用，或者chunkserver报告自己replicas损坏，或者其中一个disk故障，或者用户的replicas目标提高了。不过，每个需要re-replicated 的chunk的优先级基于几个因素。一个是它（chunk）与replication目标的差距（即重复制的饥渴程度），例如失去2个replicas的chunk将比失去一个replicas的具有更高的优先级。此外，我们更倾向于首先re-replicate活跃的（现存的）chunk文件，而不是刚刚删除文件的chunk。最后，为了最小化故障的chunk对正在运行的系统的影响，我们提高那写阻塞客户端处理的chunk的优先级。
??? master选择优先级最高的chunk，通过告知一些chunkserver从现有的有效replicas中直接复制这个chunk数据的方式去“clone”（re-replication）.新的replicas的放置和他们的创建有相同的目标：均衡磁盘利用率，单个chunkserver限制活跃的clone操作数量，跨机架分布这些replicas。为了放置这种clone操作消耗传输量压制client请求的传输量，master在cluster环境中和单个chunkserver都会限制活跃的clone操作数量。此外，每个chunkserver也会通过限制从source chunkserver中读取量（clone时），来控制它clone操作的带宽开支。
??? 最后，会周期性的reblances replicas：它会检测当前replicas的分布情况，为了更好利用磁盘空间和负载均衡，它会迁移replicas。通过这个处理，master逐步的填充一个新的chunkserver，而不是立即分发给它新的chunks，而造成随之而来的大量write操作。placement策略和新建replicas非常相似。此外，master也需要选择哪个现有的replicas被删除。通常，它倾向于删除磁盘剩余空间低于平均值的chunkserver的replicas，这也是为了均衡花磁盘利用率。
Garbage Collection:
??? 当一个文件删除后，GFS不会立即回收其有效的物理存储空间。GFS会回收它在延后的定期垃圾回收期间回收，无论是chunk和文件级别。我们发现这种方式会让系统更加简单和可靠。
?
机制：
??? 当一个file被应用删除，master会其他变更操作一样通过日志立即记录这个删除操作。不过不是立即回收资源，这个文件仅仅被重命名成一个隐藏的名字且包含删除的时间戳。在master定期扫描文件系统namespace期间，它会删除这些隐藏的文件（如果它们已经存在超过3天—这个值可以配置）。直到此时，file仍然可以在一个新的，特殊的命名的下read；也能够在不删除的情况下把它重命名回正常，不过它的in-memory metadata会被清除。
??? 在定期扫描chunk namaspace时，master能够识别孤立的chunks（任何file都无法到达—指向）并且清楚这些chunk的metadata。在master定期的heartBeat信息交换中，每个chunkserver会报告它们所持有的chunks集合，master会把已经不在master metadata中的chunks的标示响应给chunkservers。Chunkserver可以随意的删除这些chunks的replicas。
?
讨论：
??? 虽然分布式的垃圾回收是一个难题，程序设计方面需要解决很多复杂的情况，但是在我们系统中，是相当的简单。我们能够很简单的识别chunks的所有引用：它们在只有master才持有的file-to-chunk映射中。我们也能很简单的识别这些chunks replicas：它们是每个chunkserver中按照设计的目录下的linux文件。每个不能被master认知的replicas就是需要被回收的。
??? 垃圾回收的方式也存储再利用的chunk，比起立即删除，有多个优点。第一，在组件故障很常见的高扩展性的分布式环境中，它是简单和可用的。chunk的新建操作可能在部分chunkserver上成功，但是有些chunkserver上却失败了，留下了一些master不能发现其存在的replics。甚至replicas删除的消息也会丢失，master需要记住重发这些消息，无论是它自己的还是chunkserver的。回收机制提供了一个统一且可靠的方式来清除这些不被认知的chunks，这种方式很有用。第二,它把存储重用（回收）并进master的定期的后台操作，像定期的namespaces扫描和chunkserver的握手一样。因此它是批量处理的，开销也是分摊的。此外，只有当master负载相对较小时才会执行的。master就可以更快的相应client的请求。第三,这种可延迟回收存储的方式，也可以一种安全的网络避免偶尔的不可恢复的删除。
??? 在我们的经验中，一个主要的缺点就是，当存储空间比较tight（紧凑，或者不足时），这种延迟回收会阻碍我们去优化磁盘使用情况。应用重复的创建和删除临时文件或许不能正确的重用存储空间。我们通过加速存储回收的方式也应对这个问题，如果一个被删除的文件再次被删除。我们允许用户针对不同的namaspace部分，使用不同的replication和reclamation的策略。
例如，用户能够指定某个directory tree下的文件的所有chunks存储而无需replication，也可以指定任何删除的文件立即且不可恢复的从文件系统中删除。
?
Stale Replica delection：（过期replicas的删除）
??? 如果chunkserver故障，在此期间，它会丢失chunk的所有变更操作，那么此chunk也变成了stale（过期）。对于每个chunk，master保存了chunkser version number，来区分实时的（最新的）和过期的replicas。
??? 一旦master给chunk授权lease，它（primary）增加chunk version number并且会通知up-to-date replicas。Master和这些replicas都会在她们的持久化状态中记录这个新的version number。这个动作（新增版本号）是在告知客户端之前发生，也就是在它（chunk）开始写入之前发生。如果其他的replicas当前不可用，那么它的chunk version number将不会再增长了。那么在chunkserver重启后，报告它的chunks集合和这些chunks的版本号时，master就会检测到这个chunkserver中有一个过期的replicas。如果master发现一个比自己的记录更高的版本号，它会认为在授权lease的时（该回收的lease没有回收成功）失败了，它就会采取这个较高的版本号做为最新的。
??? master会在其定期的垃圾回收来删除这些过期的replicas。在删除之前，它（master）会检查这些过期的replicas不会包含在它响应给client的chunk信息中。作为应一个安全防护，master会在它告知client哪个chunkserver持有chunk lease时，或者它在复制操作中指派chunkserver从另一个chunkserver中读取chunk数据时，都会包含这个chunk 的version number。client或者chunkserver会在它执行操作是校验这个版本号，所以它总是访问最新的数据。
???
Fault tolerance and Diagnosis(容错和故障诊断):
??? 这个系统设计的最大挑战就是处理频繁的组件故障。组件的数量和质量让这个问题：我们不能完全信任这些机器，也不能完全信任磁盘，组件故障可能会造成系统不可用，甚至数据损坏。我讨论我们是如何解决这些问题的，以及系统内置的一些工具来检测出现的问题。
?
High avialability：（高可用性）
??? 在具有数百台机器的GFS分布式环境中，任何时候都有可能有机器不可用。我们采用2中简单有效的策略保持系统的高可用行：快速恢复/复制
?
? 快速恢复:
??? 无论是master还是chunkserver都是设计成保存他们的状态，并且在数秒内启动无论他们是如何终止的。事实上，我们是不会区分正常和非正常终止。Servers仅仅是通过杀死进程的方式来shut down（挺掉服务）。client和其他servers会经历一次小的振荡，当他们的请求超时，然后重试。（意思：GFS server终止后，请求会超时，然后客户端会尝试重新连接，重试操作。。）接下来讲解。。
?
??? chunk replication：
??? 每个chunk会被replicated在不同的机架上不同的chunkserver中。用户能够对不同的namespace部分，指定不同的replicate级别。默认是3.master会根据需要来保持每个chunk能够全量的replicated，当chunkserver下线或者通过校验和检测出损坏的数据。
??? Master replication：
??? master状态为了可靠性也需要replicated(和master有关的数据replicated，而不是多master 拓扑).它的checkpoints和操作日志是replicated在多个机器上。一个状态的变更认为是提交的，只有当它的日志记录刷新到本地硬盘和所有的master replicas。简单来说，master进程负责所有的变更，包括一些后台活动，例如垃圾回收这样的内部活动。当master故障，可以在短时间内重启。如果它的机器或者硬盘出现故障，GFS外部的监控机制会在operation log分布的replicas机器上启动一个新的master进程。client只使用规范的master的名称（例如gfs-test）,这（gfs-test）是一个DNS别名，当master被定向到其他机器时它也能随着改变。
??? 此外，“shadow”master（slaver？可以认为非主master）提供了对文件系统的只读的操作，即使primary master失效。它们是“shadow”，不是mirrors（影像），它们通常比primary略微落后,通常是几分之一秒.它们提高了文件的read的性能,对那些变更相对不活跃或者应用不在乎获取一个稍微过期的结果(shadow的延迟).这些过期的结果原因(这么极短的时间内),主要是文件的metadata的变更,例如目录内容或者存取控制等.
??? 为了保持自己状态是更新的(时刻被跟进),一个shadow master读取replicas中不断增长的operation log,并且按照和master相同的序列去应用这些数据结构的变更.和primary master一样,每个shadow master也会在启动时去poll chunkserver获取replicas位置信息/交换handshake消息来监控他们的状态.它仅仅依赖于primary master对replicas的位置更新(primary负责对replicas的新建/位置重分配等).
?
GFS论文整理(一):[http://shift-alt-ctrl.iteye.com/blog/1842245]
GFS论文整理(二):[http://shift-alt-ctrl.iteye.com/blog/1842286]
GFS论文整理(四):[http://shift-alt-ctrl.iteye.com/blog/1842510]
