Lec3: GFS

GFS 是 Google File System 的简称，是 Google 开发的分布式文件系统。

GFS旨在保持高性能，且有复制、容错机制，但很难保持一致性。google确实曾使用GFS，虽然后继被新的文件系统Colossus取代。

GFS是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通硬件上，并提供容错功能。它可以给大量的用户提供总体性能较高的服务。

主要特点

GFS的服务器是普通商用服务器，容易出现节点故障，因此需要错误检测和恢复机制。
存储负载较大，需要存储大数量的大文件，有概率出现 PB、TB 级的数据。
大量流式读、顺序读，需要进行优化。
连续写和追加写，但是修改与读相比总体较少。
高并发，需要快速处理大量数据。

体系结构

GFS包括一个master结点（元数据服务器），多个chunkserver（数据服务器）和多个client（运行各种应用的客户端）。

GFS master就是GFS的元数据服务器，负责维护文件系统的元数据，包括命名空间、访问控制、文件-块映射、块地址等，以及控制系统级活动，如垃圾回收、负载均衡等。
chunkserver提供数据的存储。
client作为代理与master和chunkserver交互。master会定期与chunkserver交流（心跳），以获取chunkserver的状态并发送指令。

读取

读取流程

应用指定读取某文件的某段数据。
client 计算出这段数据所占的数据块，并将文件名和需要的数据块索引发给 master。
master 根据文件名查找命名空间和“文件-块映射”表，找到数据块的位置，将数据块id和副本地址列表返回给 client。
client 选择其中一个副本，向其中一个 chunkserver 发送读取请求。
chunkserver 读取数据块，并将数据返回给 client。

一致性

这里的一致性指的是 master 中的元数据和 chunkserver 存储的数据是否一致，多个数据副本是否一致。

元数据的一致性

GFS用的是读写锁。

并发写的一致性，

client 发出更新请求，向 master 询问谁是数据块的主节点（primary），拥有该数据块的租约。
master 将持有租约的 primary 告诉 client，client 会将其缓存。
client 向所有副本传输数据。
chunkserver 将数据写入LRU缓存，并发送确认数据。
当所有副本都确认数据，client 向 primary 发送写请求。
primary 为接受到的请求分配序列号，并按顺序执行数据更新。
副本收到 primary 的写请求，每个副本都按照顺序执行更新。
副本向 primary 汇报操作情况。
primary 收到所有副本的确认后，向 client 返回成功。

lec4: Replication

这一讲主要是聊主备复制和网络分区。

网络分区

在主从系统中，一致性是一个非常重要的属性。很难想象，如果我们两次访问一个数据，第一次访问从一个服务器获取一个值，第二次访问却从另一个服务器获取另一个值。因此我们要避免这种情况的发生。

网络分区是指两个节点之间的通信出现了问题，导致它们之间的数据无法及时同步。在本来的一主多从的环境中，部分从节点与主节点失联，而仍有部分从节点可以跟主节点通信。这样无法通讯的从节点就会认为主节点挂了，从而选举出一个新的主节点，自成一派；而保持连接的从节点们和主节点连接的好好的，还是岁月静好，照常运行。至此，就出现了两片网络分区。而且棘手的是，我们从单集群的视角来看，我们无法确定到底是另一个集群的机器都故障了，还是它们自立门户了。

而上面这种情况也叫脑裂（split-brain），显然大家可以发现，如果任由这种情况发生，整个系统的数据将会严格划分成多块，这对一致性来说是灾难性的。并且从单节点或者单集群的视角来看，我们无法判断到底是另一个集群的机器都故障了，还是它们自立门户了。

分析

从需求和难点入手，我们来分析一下现在的情况。

从客户端的视角看，主从节点都是一样的，对同一数据的只读访问应该返回同样的结果。从服务器的视角看，我们的目标是primary失败时，backup能接手primary的工作，并且从primary停止的地方继续工作。

我们一要保证执行的顺序性，二要保证数据在主从中是一致的。

主备复制

state transfer：状态转移，物理复制。主节点在更新完毕后，将自身当前的状态快照发送给backup，后者同步完成后主节点才会向客户端返回成功。
replicated state machine：复制状态机，逻辑复制。主节点这次转移的是操作本身，而非数据本身，等backup执行完操作后，再将操作结果发送给客户端。

总结来说，二者都是为了保证主备间数据的一致性。并且都会等到 backup 完成操作后才会返回客户端成功。但用的更多的还是后者，因为状态转移中一个操作可能会出现多个状态，导致复杂性和性能问题。