6.824: Distributed Systems 课程讲义3

什么是一致性?

分布式系统中，数据通常会通过复制进行冗余，当应用程序并发访问这些数据的时候，如何保证访问的数据是一致的。如果一个应用程序写入了新的数据，那么之后来访问数据的应用能否看到新增的数据呢? 这就是一致性问题了，通常一致性有几种类型:

弱一致性 读的时候可能会返回老数据，不保证能访问到新写入的数据。

强一致性 读的时候总是返回最新写入的数据。

两者之间的关系 强一致对于应用写入是友好的，对于性能来说是不友好的。弱一致性对性能友好，也易于扩展。但是弱一致性很复杂。这需要根据一些条件在两者之间做一个平衡。这些被称为一致性模型。

理想的一致性模型

看起来就像是单机上写文件一样，总是保持数据是一致的，实际上可能是多台机器在做数据的复制。一个应用程序写入，后续的读请求可以看到最新写入的内容。这就是理想的一致性模型.

如果有多个应用并发写入相同文件呢? 如果是单机的话，这个行为是未定义的，文件可能会出现混合的内容。

如果有多个个应用并发写同一个目录该怎么办? 可以使用锁来将并发写转换为串行写入。

完成理想的一致性模型带来的挑战

并发 – 会导致一致性问题，在加上现实中可能会有多块磁盘会加剧这个问题。机器损坏 – 任何操作都有可能失败。网络分区 – 可能会导致没办法和其他的机器或者磁盘通信。

为什么这些困难很难克服呢?

客户端和服务端需要通信可能会有性能损失通信协议可能会变的复杂难以保证实现的系统是正确的

在6.824课程中很多系统都没有实现理想的一致性模型。GFS就是其中一个例子。

GFS目标

可以扩展为很多机器，机器损坏是常态。必须要容错，不能认为机器一年才会损坏一次。对于一个1000台机器组成的集群平均每天会有三台机器损坏。高性能： 支持并发读和写，Map/Reduce任务会从GFS中进行读取获取输入数据，并最终将结果存在GFS中。高效通信：节省带宽

这些挑战很难和理想的一致性模型结合在一起。

High-level 设计和读流程

master存储目录、文件、名称、提供open/read/write等接口，但是不是POSIX语义的。 chunk服务器就是用来存储实际的数据的，每64MB存储一个chunk，每一个chunk都会被复制三份

Q: 这样做的目的除了为了保证数据可用外，三份副本还给我们带来了什么? 对于热点文件可以进行读的负载均衡，另外还可以实现就近读，也就是亲缘性。

Q: 为什么不利用RAID来存储文件的拷贝? RAID不是一个普通的硬件，而且GFS容错的目标是整个机器，而不仅仅是磁盘

Q: 为什么chunk如此大? 分摊开销，减少master中存储的状态数据的大小

GFS的master是知道整个目录层级的。对于目录来说知道哪些文件在这个目录中，对于文件来说知道文件中的内容在哪些chunk服务器上mastre必须要将这些文件都保存在内存中。对于每一个chunk来说，使用64字节的数据来存在其元数据信息。对于这些元数据，master会通过操作日志将其保存起来放在磁盘上，以便在必要的时候可以用来进行恢复。并且还会定时的对这些元数据进行checkpoint。通过这些元数据master就可以迅速进行恢复了。另外shadow master和主master只差一些元数据信息。必要的时候shadow master可以提升为主master。

客户端读:

发送文件名和chunk index到mastermaster回复一系列的chunk server地址，，还有chunk的版本客户端缓存这些信息，然后找到最新的chunk server检查chunk的版本，如果有问题就重新联系master

写流程

客户端随机写已经存在的文件

客户端询问master chunk的位置和主chunk servermaster回复chunk server的地址和版本，并且告知哪个chunk server是主chunk，并且有60s的租约客户端基于网络拓扑计算复制的chain客户端发送数据给第一个副本，它将会把数据转发给其他的机器，基于网络的pipeline，来分摊单机的网络负载副本响应客户端客户端告知主chunk server进行写入主chunk server根据顺序进行写入，并且告知其他的所有chunk server进行写入，当所有的都写入完成后就告知客户端 如果有另外一个客户端并发写同一个地方怎么办? 客户端2获得的顺序是在客户端1之后，那么会发生数据覆写。尽管所有的数据是一致的，但是却混合了两个客户端的数据。

记录追加的流程

客户端请求master, chunk的位置客户端将数据发送给副本，但是还没有指定offset当数据发送到所有副本后，客户端联系主chunk服务器 主chunk服务器指定顺序主chunk服务器检查append是否合适放入到chunk中如果不合适就进行填充主chunk服务器选择一个offset开始append主chunk服务器在本地进行应用主chunk服务器转发请求给副本机器如果副本3在应用的过程中失败了，主chunk服务器会探测到这种错误，并且告诉客户端进行重试。客户端重新联系master进行重试这个时候master可能会指定副本4或者副本3被重新添加到集群中现在这个副本现的字节序列中有一个间隙，所以不能只是追加需要填充所有副本到下一个可用偏移量。

Housekeeping

如果主chunk服务器不刷新租约的化，master可以重新选择一个主chunk服务器如果chunk的副本数量少于指定值的时候，master会进行chunk复制master可以给副本做rebalance

错误

chunk server很容易替换master down机后会导致GFS不可用，这个时候shadow的master可以提供read-only的操作，但是可能返回的不是最新的数据

为什么不shadow master不能进行写操作呢？ 这个会导致脑裂问题。

GFS是否实现了理想的一致性模型?

两个case: 目录和文件 目录: 是理想的一致性的，但是… 强一致，只有一份拷贝，但是master不总是可用的，扩展性也是一个问题 文件: 不总是满足理想的一致性模型

并发append的时候会导致数据重复、其他副本可能会出现一些填充的记录并发写的时候，会导致数据错乱，相互覆盖，如果你不希望这样，可以通过原子append或者临时文件通过原子的rename来避免这种情况某个较短的间隔，客户端可能会读取到老数据 因为客户端缓存了元数据信息，所以可能会导致读取到不是最新的数据，需要等到租约到期，或者新版本的chunk请求主chunk服务器更新chunk成功后，其他的副本更新失败，会导致数据处于不一致的状态

作者认为弱一致性对于应用来说不是一个问题

大多数文件都是append only的更新应用可以使用UID来检测append的记录是否重复应用可能仅仅只读取少量数据(但不是老数据)应用程序可以通过临时文件并通过原子的rename来进行文件写入来避免并发写导致的数据错乱的问题

性能

大吞吐量的读(3副本、条带化) 125MB/sec，接近网络的最大带宽。网络是个瓶颈，pipeline这种数据传送方式会导致数据在传递给副本的时候存在延迟(一个接一个的传递，而不是广播式的)并发append写入一个文件的时候，性能受限于文件最后一个chunk所在的服务器带宽。因为每次append都是通过这个chunk服务器将，数据传递给其他的副本。

总结

这是一个关于性能、容错、一致性的专门用于MapReduce应用程序的案例研究

哪些工作适合GFS呢? 大量的顺序读和append写入巨大的吞吐量(3副本、条带化，客户端可以通过将读请求分散到三台机器并行读取整个文件，从而提高整体的吞吐量)数据容错性(3副本)

https://en.wikipedia.org/wiki/Data_striping 数据的条带化技术

哪些工作不适合GFS呢? master需要容错的小文件(master是瓶颈)客户端可能会看到老数据追加可能会导致数据重复

References

http://queue.acm.org/detail.cfm?id=1594206 (discussion of gfs evolution)http://highscalability.com/blog/2010/9/11/googles-colossus-makes-search-real-time-by-dumping-mapreduce.html