第2章 Google云盘算原理与应用
《云盘算 第三版 刘鹏 》第2章 Google云盘算原理与应用的具体总结，课后习题解答。可用于期末测验。
2.1 Google文件系统GFS
当前主流分布式文件系统有RedHat的GFS（Global File System）、IBM的GPFS、Sun的Lustre等。这些系统通常用于高性能盘算或大型数据中心，对硬件设施条件要求较高。
Google文件系统（Google File System，GFS）是一个大型的分布式文件系统。
GFS采用廉价的商用呆板构建分布式文件系统。
GFS将容错的使命交给文件系统来完成，使用软件的方法解决系统的可靠性问题。
2.1.1 系统架构
一个GFS集群由一个主服务器(master)、多个数据块服务器(Chunkservers)组成。一个数据块服务器可以被多个客户端(clients)访问，一个客户端也可以同时访问多个数据块服务器。Master是GFS的管理节点，保存了所有文件系统的元数据，包括命名空间、访问控制信息、从文件(files)到数据块(chunks)的映射以及当前数据块(chunks)的位置。它还控制系统范围内的运动，如数据块租赁管理、孤立数据块的垃圾回收以及数据块服务器之间的数据块迁移。主服务器定期在HeartBeat中与每个块服务器通信，给它指令并网络其状态，判定数据块服务器是否存活。
文件被分为多个固定巨细的数据块(Chunk,默认巨细为64MB,块句柄)，每个数据块都有对应的索引，存储在数据块服务器(Chunkservers)中。为了进步可靠性，每个数据块(Chunk)都会进行多次复制并存放在不同的数据块服务器(Chunkservers)上，一般存储三份。
①中心服务器模式(single master)
客户端从不通过主服务器读取和写文件数据。相反，客户端会询问主服务器应该联系哪个数据块服务器。它会在有限的时间内缓存这些信息，即数据块句柄(chunk handle)和副本的位置(locations of the replicas)，并为很多后续操作直接与数据块服务器交互。
如图，客户端将由应用程序指定的文件名(file name)和字节偏移量(byte offset)转换为文件的块索引(chunk index)，然后向主服务器发送一个包含文件名和块索引(file name, chunk index)的请求，主服务器则回复客户端数据块句柄(chunk handle)和副本的位置(locations of the replicas)。客户端使用文件名和块索引作为键(key)缓存此信息。之后，客户端向chunkserver发出请求，这个请求指定了数据块句柄和块内字节范围，chunkserver返回给客户端相应的数据。在缓存信息过期或者重新打开文件之前，对于同一个数据块(same chunk)的访问不再须要客户端和服务器的交互(client-master interaction)。通常，客户机一次性请求多个数据块。
GFS的这种设计方法实现了控制流和数据流的分离。Client与Master之间只有控制流，而无数据流，极大地降低了Master的负载。Client与Chunk Server之间直接传输数据流（也有控制流）。
当然，中心服务器模式也带来一些固有的缺点，好比极易成为整个系统的瓶颈等。GFS采用多种机制来制止Master成为系统性能和可靠性上的瓶颈，如只管控制元数据的规模、对Master进行远程备份、控制信息和数据分流等。
②不缓存数据
从须要性上讲，客户端大部分是流式次序读写，并不存在大量的重复读写，缓存这部分数据对进步系统团体性能的作用不大；对于Chunk Server，由于GFS的数据在Chunk Server上以文件的形式存储，如果对某块数据读取频繁，当地的文件系统天然会将其缓存。
从可行性上讲，怎样维护缓存与现实数据之间的一致性是一个极其复杂的问题，在GFS中各个Chunk Server的稳固性都无法确保，加之网络等多种不确定因素，一致性问题尤为复杂。此外由于读取的数据量巨大，以当前的内存容量无法完全缓存。
对于存储在Master中的元数据，GFS采取了缓存计谋。由于一方面Master须要频繁操作元数据，把元数据直接保存在内存中，进步了操作的服从。另一方面采用相应的压缩机制降低元数据占用空间的巨细，进步内存的使用率。
③在用户态下实现
文件系统是操作系统的紧张组成部分，通常位于操作系统的底层（内核态）。在内核态实现文件系统，可以更好地和操作系统本身结合，向上提供兼容的POSIX接口（可移植操作系统接口）。然而，GFS却选择在用户态下实现，主要基于以下考虑。
（1）在用户态下实现，直接使用操作系统提供的POSIX编程接口就可以存取数据，无须了解操作系统的内部实现机制和接口，降低了实现的难度，进步了通用性。
（2）POSIX接口提供的功能更为丰富，在实现过程中可以使用更多的特性，而不像内核编程那样受限。
（3）用户态下有多种调试工具，而在内核态中调试相对比力困难。
（4）用户态下，Master和Chunk Server都以进程的方式运行，单个进程不会影响到整个操作系统，从而可以对其进行充分优化。在内核态下，如果不能很好地把握其特性，服从不光不会高，以致还会影响到整个系统运行的稳固性。
（5）用户态下，GFS和操作系统运行在不同的空间，两者耦合性降低，方便GFS自身和内核的单独升级。
④只提供专用接口
GFS在设计之初，是完全面向Google的应用的，采用了专用的文件系统访问接口。接口以库文件的形式提供，应用程序与库文件一起编译，Google应用程序在代码中通过调用这些库文件的API，完成对GFS文件系统的访问。
采用专用接口有以下利益。
（1）降低了实现的难度。通常与POSIX兼容的接口须要在操作系统内核一级实现，而GFS是在应用层实现的。
（2）采用专用接口可以根据应用的特点对应用提供一些特殊支持，如支持多个文件并发追加的接口等。
（3）专用接口直接和Client、Master、Chunk Server交互，淘汰了操作系统之间上下文的切换，降低了复杂度，进步了服从。
2.1.2 容错机制
①Master容错
Master上保存了GFS文件系统的三种元数据。
(1)文件和数据块的命名空间
(2)从文件到数据块的映射
(3)每个数据块副本的位置，一个Chunk默认有三个副本
所有的元数据都保存在主服务器的内存中。前两种元数据 (namespaces and file-to-chunk mapping)还恒久保存于多副本的日志中，GFS通过操作日志来提供容错功能。第三种元数据信息则直接保存在各个Chunk Server上，当Master启动或Chunk Server向Master注册时自动天生。这些元数据以及日志都保存在磁盘中，因此当Master发生故障时，在磁盘数据保存齐备的情况下，可以迅速规复以上元数据。为了防止Master彻底死机的情况，GFS还提供了Master远程的及时备份，这样在当前的GFS Master出现故障无法工作的时候，另外一台GFS Master可以迅速接替其工作。
②Chunk Server容错
每一个Chunk有多个存储副本（默以为三个），分别存储在不同的Chunk Server上，以淘汰ChunkServer挂掉带来的损失。对于每一个Chunk，必须将所有的副本全部写入成功，才视为成功写入。
GFS中的每一个文件被分别成多个Chunk，Chunk的默认巨细是64MB，这比范例的文件系统块巨细要大得多，这是由于Google应用中处理的文件都比力大，以64MB为单元进行分别，是一个较为合理的选择。
每一个Chunk分别为多个Block，Block巨细为64KB，每一个Block对应一个32bit的校验和(checksum,用block里的数据hash一下得到的值)。当读取一个Chunk副本时，Chunk Server会将读取的数据与checksum进行比力(雷同于带有hash加密的账号登录，判定暗码是否正确)，如果不匹配，代表数据损坏，就会返回错误，使Client选择其他Chunk Server上的副本(如某个ChunkServer发现自己的Chunk03坏了，会求助Master探求其他副本)。对于一个1T的文件，1T/64KB*32bit=64MB，即1T的文件的checksum只须要占用64MB，因此checksum可以放在内存中。
原论文中对于Chunk Size的优缺点形貌为：
A large chunk size offers several important advantages. First, it reduces clients’ need to interact with the master because reads and writes on the same chunk require only one initial request to the master for chunk location information. The reduction is especially significant for our work loads because applications mostly read and write large files sequentially. Even for small random reads, the client can comfortably cache all the chunk location information for a multi-TB working set. Second, since on a large chunk, a client is more likely to perform many operations on a given chunk, it can reduce network overhead by keeping a persistent TCP connection to the chunkserver over an extended period of time. Third, it reduces the size of the metadata stored on the master. This allows us to keep the metadata in memory, which in turn brings other advantages that we will discuss in Section 2.6.1.
On the other hand, a large chunk size, even with lazy space allocation, has its disadvantages. A small file consists of a small number of chunks, perhaps just one. The chunkservers storing those chunks may become hot spots if many clients are accessing the same file. In practice, hot spots have not been a major issue because our applications mostly read large multi-chunk files sequentially.
翻译如下：
较大的块巨细具有几个紧张上风。起首，它淘汰了客户端与主服务器交互的需求，由于对同一数据块的读写仅需向主服务器发送一次初始请求以获取数据块位置信息。对于我们的工作负载而言，这种淘汰尤为明显，由于应用程序主要按次序读写大型文件。即使对于小型随机读取，客户端也可以轻松地缓存多 TB 工作集的所有数据块位置信息。其次，由于在较大的数据块上，客户端更有可能在给定的数据块上执行很多操作，因此它可以通过在较长时间内保持与数据块服务器的恒久 TCP 毗连来淘汰网络开销。第三，它减小了存储在主服务器上的元数据的巨细。这使我们能够将元数据保存在内存中，这反过来又带来了其他上风，我们将在 2.6.1 节中进行讨论。
另一方面，即使采用延迟空间分配，较大的块巨细也有其缺点。一个小文件由少量块组成，可能只有一个。如果很多客户端正在访问同一个文件，存储这些块的块服务器可能会成为热门。在实践中，热门并不是一个主要问题，由于我们的应用程序主要是次序读取大型多块文件。
2.1.3 系统管理技术
GFS是一个分布式文件系统，包含从硬件到软件的整套解决方案。除了上面提到的GFS的一些关键技术外，另有相应的系统管理技术来支持整个GFS的应用，这些技术可能不一定为GFS独有。
①大规模集群安装技术
②故障检测技术
③节点动态加入技术
④节能技术
2.2 分布式数据处理MapReduce
MapReduce是Google提出的一个软件架构，是一种处理海量数据的并行编程模式，用于大规模数据集（通常大于1TB）的并行运算。Map（映射）、Reduce（归约）的概念和主要思想，都是从函数式编程语言和矢量编程语言鉴戒来的。
MapReduce封装了并行处理、容错处理、当地化盘算、负载平衡等细节，还提供了一个简朴而强大的接口。通过这个接口，可以把大尺度的盘算自动地并发和分布执行，使编程变得非常容易。另外，MapReduce也具有较好的通用性，大量不同的问题都可以简朴地通过MapReduce来解决。
MapReduce把对数据集的大规模操作，分发给一个主节点管理下的各分节点共同完成，通过这种方式实现使命的可靠执行与容错机制。在每个时间周期，主节点都会对分节点的工作状态进行标记。一旦分节点状态标记为殒命状态，则这个节点的所有使命都将分配给其他分节点重新执行。
2.2.1 程序模子
MapReduce的输入为一组键值对，通过map函数得到表现另一种含义的新的键值对，将得到的新的键值对交给Reduce函数处理，得到末了的结果。
什么是Map？
Map的含义是”分解“。如果输入为一辆汽车，map的作用就是把汽车拆成各种零件。每个零件都会带有标记信息，根据需求的不同可以是零件数目，零件在汽车中的位置，零件的作用等。
什么是Reduce？
Reduce的含义是”组装“。对于经Map拆分的得到的零件，reduce的作用就是把零件重新组合成变形金刚，此时map中零件的标记信息就可以是”零件的作用“，reduce根据零件作用的不同进行重组并组装到变形金刚的不同部位。
什么是MapReduce？
①假设有很多的蔬菜、水果和面包(Input)；
②另外有多个不同的厨子，他们各自取了(主动拿)不同的食材(Split)；
③厨子拿到食材之后把它们切碎(Map)；
④之后把切碎的食物放入不同的烤箱、冰箱(容器主动拿食材)等容器(Shuffle)；
⑤之后根据顾客需求从容器中拿不同食材制作成不同食物(Reduce)；
⑥末了顾客付费(Finalize)。
共六大过程。
2.2.2 例子1：统计单词数
①输入(Input)为带有编号的句子：<id, content>；
②根据编号的不同分配给不同的工作机(Worker)来处理(Split)；
③对每个句子进行Map处理，统计句子中单词出现的个数<word, 1>，如0号句子被处理为<Deer, 1>, <Bear, 1>, <River, 1>；
④然后将所有句子的Map结果根据单词(key)放在不同的盒子里(Shuffle)，根据首字母排序，排序是为了让雷同的key在一起；
⑤之后Reduce操作，统计每个盒子单词的次数；
⑥末了将结果放在一起(Finalize)。
末了的结果是乱序的，即高度并行的。
- Map(String key, String value){
-
- //key: the id of the line.
- //value: the content of the line.
- for word in value{
-
- OutputTemp(word, 1);
- }
- }
- Reduce(String key, List valueList)
|
