6.824分布式笔记1-简介、MapReduce、GFS


笔记性质,只记录关键词。

Introduction

能单机处理就单机,分布式比较复杂。

关键点:并行、容错。

可能遇到的问题:

并发、网络不稳定、机器可能崩溃(partial failure)。。。

基础架构的类型:

  • storage
  • comms
  • comp

理想情况就是封装好接口,用的时候完全感觉不到和非分布式系统不同,但是实际上是一个高性能、高可用的分布式系统。

用到的工具:

  • RPC
  • 线程
  • 并发控制

可扩展性(Scalability)

如果用一台计算机解决了一些问题,那么我用两台计算机,应该能用一半时间解决这些问题。

这个是个比较牛逼的特性。对一个系统,只要增加机器成本,就可以获取性能提升或者吞吐量提升。

可用性(Availablity)

分布式系统中问题会被放大,因为机器很多,故障几率增加(机器原因或者网络原因等)。

比如在lab1 mapreduce中,worker线程可能会崩溃,这不应对最后的结果产生影响。

  • 非易失存储(如硬盘)。可以保存系统状态以便恢复,但是写硬盘代价高。
  • 复制。多副本系统,问题:可能偏离同步,解决比较复杂。

一致性(Consistency)

举例:分布式存储系统,只支持kv put和kv get操作。

单机上,一个服务器,一个表单,通常不会出现put/get 操作的歧义问题。但是对于分布式系统,从性能和容错角度讲,通常会有多个副本。

假设器上两个副本的初始值相同,都是键值对{"1":20}

一个客户端发送了put请求,将key 1的值改为了21。发送给了第一台服务器,然后发送给了第二台服务器。但是发送完一个之后,还没发另一个,电脑崩了。一个电脑上是20,一个是21,另一个客户端访问的话可能得到二十,也可能得到21。

一致性几种类别:

  • 强一致性:访问到的就是最新的。

  • 弱一致性:数据更新后,如果能容忍后续的访问只能访问到部分或者全部访问不到,则是弱一致性。

    这个老哥举的例子不错:一致性例子

    用户更新网站头像,在某个时间点,用户向主库发送更新请求,不久之后主库就收到了请求。在某个时刻,主库又会将数据变更转发给自己的从库。最后,主库通知用户更新成功。

    如果在返回“更新成功”并使新头像对其他用户可见之前,主库需要等待从库的确认,确保从库已经收到写入操作,那么复制是同步的,即强一致性。如果主库写入成功后,不等待从库的响应,直接返回“更新成功”,则复制是异步的,即弱一致性。

    强一致性可以保证从库有与主库一致的数据。如果主库突然宕机,我们仍可以保证数据完整。但如果从库宕机或网络阻塞,主库就无法完成写入操作。

    在实践中,我们通常使一个从库是同步的,而其他的则是异步的。如果这个同步的从库出现问题,则使另一个异步从库同步。这可以确保永远有两个节点拥有完整数据:主库和同步从库。 这种配置称为半同步。

  • 最终一致性:一段时间后,节点数据会达到一致状态。

MapReduce

输入被分割成不同的文件或者数据块。MapReduce启动后,会查找map函数,并用它对输入文件运行map函数,这个过程可以多个worker并行。Map的函数输出是kv键值对列表。然后MapReduce框架收集Map函数输出中属于同一个key的键值对,交给reduce。

不说了,这个lab已经做过了。它是一个MapReduce框架,在使用的时候只要更改Map函数和Reduce函数,就可以实现不同的功能。笔记:

6.824分布式lab1准备工作

6.824分布式lab1通过

GFS

The Google File System.

分布式存储系统的难点

对于大型存储系统,要提升性能,利用大量计算机同时完成大量工作。自然的想法就是分片。

但是在大量计算机上进行分片,故障是很常见的,总有机器可能出现故障。所以需要自动容错系统。

falut tolerance。

实现容错最有用的方式就是复制,维护几个数据的副本,这样又会有数据不一致的问题。

理想的一致性系统:从客户端看,就像是在和一台服务器在通信。可能会有大量的客户端并发请求发送到服务器上,服务器从请求里挑出一个先执行,执行完成之后再执行下一个。

举个存储的例子:

一些客户端。客户端C1发起写请求将X设为1,同一时刻,客户端C2发起写请求将X设置为2。

执行完毕后,C3发送读取X的请求,过了一会,C4也发送读取X的请求,它们能得到什么值?

考虑一致性,二者访问的结果应相同,可能是1也可能是2。

一个不好的多副本设计方案

只是为了显示问题所在。

两个服务器,每个服务器都有数据的一份完整拷贝,如磁盘上都有一个kv表单。一台服务器故障了,可以切换到另一台服务器去做读写。

两个表单完全一致就意味着,写请求要在两台服务器上执行,读请求在一台服务器上执行。

如果两个客户端同时执行写请求,C1设置x为1,C2设置x为2,需要更新两个服务器上的数据。

没有措施保证两台服务器会以相同的顺序处理这个请求,可能C1设置了服务器S1的x为1,然后C2设置了S2的x为2,然后C2设置了S1的x为2,然后C1设置了S2的x为1。

最后数据就会不一致,如果两个请求访问不同的机器,就会访问到不同的值。

GFS的设计目标

GFS在2003年提出,当时在学术领域,大家已经知道了怎么构建高度并行并且有容错的分布式系统,但是在工业界却很少应用。大概从GFS提出开始,Google开始构建严格意义上的分布式系统。

GFS:Big,Fast,Global,sharding(分片)

为了获得大容量和高速的特性,每个包含了数据的文件会被GFS自动分割并存储在过个服务器之上,这样读写操作就会变得很快。而且这样还可以存储比单个磁盘更大的大文件。

这样的一个存储系统服务器故障是很正常的,因为机器数量大,所以系统最好能自动修复。

GFS设计成只是一个数据中心保存。(理论来说,多个机房当然最好,但是实现起来更难)

GFS是为了TB级别的文件而生,只会顺序处理,不支持随机访问。它的关注点在巨大的吞吐量上。

GFS:

  • Single data center
  • Internal use(谷歌自用)
  • Big sequential access

GFS论文的思想如:分布式,分片,容错并不是很新颖,当时已经有一些论文描述这些东西了,但是GFS的特点是提供了一个真家伙,工业应用的系统,规模远超学术界的系统,反映了现实世界的经验。而且,GFS提出了一个当时比较异类的观点:存储系统具有弱一致性也是可以的

GFS宣称使用单个Master节点,并能很好的工作。

GFS返回可能错误的数据会影响程序吗?

搜索引擎之类的结果,谁关心是否是排序正确或者缺失了几条呢?个人感觉:这种搜索结果之类的东西弱一致性也无所谓,对于一些需要精确的东西,应该保证最终一致性。

但是例如银行的系统,一致性是如何保证的呢?

猜想下:不同的账户并不是存在一个数据库,而是存在于几个不同的数据库中,根据卡号能判断银行卡开户地点之类的,从而知道存储这个卡账户信息的数据库,接下来就对它进行操作。这样想银行也不一定是强一致性,只要扣款之后如果转账失败再加回来就是了。

如:A账户给B账户转账100。

查询A账户钱够不够,B账户信息对不对,对的话就开始转账流程。

A扣钱,然后通知B加钱,加成功了,返回信号给A,结束流程;失败了,告诉A失败了,再把钱加回来,流程结束。流程结束之后返回给客户转账结果信息。过程中随时记录日志并且多拷贝几份,这样数据库崩溃的时候也可以进行修复。也就不存在一致性问题。

GFS架构

一个Master节点和多个Chunk server(类似于云计算中的工作机,具有数据多副本,中等规模数据粒度,自动负载均衡,宕机恢复等特点)。每个chunk server上都有几块磁盘。

Chunk :[tʃʌŋk] 大块、区块、数据块。

Master节点管理文件和chunk的信息,chunk服务器用来存储实际的数据。

Master节点知道每一个文件对应的所有chunk的ID,每个chunk是64MB大小。假设有一个1GB的文件,Master节点知道这个文件的第一个chunk存储在哪,第二个chunk存储在哪等等。

Master关注的主要是两个表单:

  • 文件名到chunk ID数组的对应。
  • chunk ID到chunk数据的对应关系:
    • 每个chunk存储在哪个服务器上。
    • chunk当前的版本号
    • 对于chunk的写操作必须在primary chunk上顺序处理,primary chunk是chunk的多个副本之一。
    • primary chunk的过期时间。

这些信息同时存储在硬盘上,避免数据丢失。Master读数据只会从内存读,但是写数据至少以一部分数据会接入到磁盘。

master数据有些需要写在磁盘上,有的不用:

  • chunk ID数组,要保存在磁盘上,NV(non-volatile)
  • chunk服务器列表不用保存在磁盘上,master重启之后可以与chunk服务器通信查询。V
  • 版本号要看GFS工作方式。
  • primary chunk id。V
  • primary chunk expiration time。V

如果文件扩展达到了一个新的64MB,需要新增一个chunk或者制定了新的primary chunk导致版本号更新了,master节点需要向磁盘的log添加一条记录。

写log而不是数据库的原因是,log顺序写,比较高效。

一般来说,重启需要从一个最近的checkpoint恢复,然后执行之后的log。

GFS读文件

读请求:GFS客户端有一个文件名和文件的读取偏移量。发送给Master节点。Master节点从file表单中查询文件名,得到chunk id的数组。每个chunk 64MB,可以查询到对应偏移量的chunk ID。Master再查找chunk 的服务器列表,返回给客户端。

之后客户端就可以从chunk服务器之中选一个来读取数据。

因为客户端每次可能只读取1MB或者64KB数据,所以,客户端可能会连续多次读取同一个Chunk的不同位置。所以,客户端会缓存Chunk和服务器的对应关系,这样,当再次读取相同Chunk数据时,就不用一次次的去向Master请求相同的信息。

GFS写文件

针对大文件、添加。

向文件append内容的话,客户端向Master节点发送请求,得到文件中最后一个chunk的位置。

写文件需要通过primary chunk写入,要考虑chunk主副本不存在的情况。

最新的副本:版本号与Master节点中记录的chunk版本号一致。

如果客户端对文件进行追加,如果不知道文件尾的Chunk对应的Primary在哪时,Master会等所有存储了最新Chunk版本的服务器集合完成,然后挑选一个作为Primary,其他的作为Secondary。之后增加版本号,将版本号写入磁盘。

文件的添加可能会出现这种情况

image-20220606211028460

首先添加A,都成功了,然后添加B,第三个没成功,然后添加C,都成功了,然后客户端重试添加B,都成功了。这样就会造成padding和数据的重复。

所以这种方式不适合需要严格标准格式的文件,如图片、视频。但是记录不同的数据记录,缺失或者重复不会有什么影响的时候,可以用。

总结

有很多东西没记笔记,具体的有个lab,到时候会谈到一些细节,到时候再补充。