<commit_before>---
layout: post
title:  "大规模文件系统及MapReduce"
date:   2017-08-15 10:00:00
categories: 大数据
tags: 大数据 MapReduce hadoop
excerpt: 本笔记来自于阅读《大数据-互联网大规模数据挖掘与分布式处理》第2章
mathjax: true
---

Hadoop不适合处理“快数据”。似乎有点过时了。而Spark在内存中处理数据具有较好的性能表现，同时也提供了简单易用的API，目前很火热。
事实上，它们有不同的使用场景，有不同的应用领域。它们不是替代的关系。MapReduce也在演化和扩展。

书中列举了两个例子：
- Web网页重要性排序：涉及一个迭代的矩阵-向量乘法计算，其中矩阵和向量维度达到百亿维。
- 社交网站的朋友关系网络，包含上亿个节点和几十亿条边，在这样的网络中搜索想要的信息。

解决思路（分层）
- 分布式文件系统：存储单位要比传统OS的磁盘块要大很多; 提供数据冗余机制来防止数据分布在上千块磁盘上时频发媒介故障。

- 在文件系统之上，得有一个编程模型，MapReduce编程系统，把计算分布在集群中实现。

# 分布式文件系统 #
## 计算节点的物理结构 ##
集群计算(cluster computing)：计算节点存放在机架上，单节点之间网络互连，机架之间另一级网络或交换机互连。

主要故障模式：单节点故障和单机架故障

解决方案：多副本存储；计算过程分成多个任务完成，一个任务的执行不影响其他任务。

## 大规模文件系统的结构 ##
集群计算需要分布式文件系统（Distributed File System，DFS）的支持，现有DFS如GFS、HDFS、DFS Cloudstore等。DFS的应用场景：
- 大文件，TB以上级别。小文件使用DFS无任何意义。
- 文件极少更新。对于频繁变化的数据，不适合采用DFS。例如机票订购系统就不适合采用DFS，虽然数据量很大，但数据变化频繁。

在DFS中，文件被分为文件块（chunk)，大小通常为64MB，文件块会被复制多个副本放在不同的节点/机架上，副本个数一般可设置。

分散存储后如何读取文件？ 通过主节点(master node)或名字节点（name node），它们负责维护着整个文件系统的文件目录树，文件/目录的元信息和文件的数据块索引。

问题：只读共享（Hadoop）？ 还是受控写操作，或者并发写操作（基本不实用）？

# MapReduce #
MapReduce通过“分而治之”管理大规模并行计算过程，同时保障对硬件的容错性(机器故障是常态)。如何拆分任务，如何合并结果？

MapReduce把复杂的任务分解为若干个“简单的任务”执行，“简单的任务”有几个含义：
- 数据或计算规模相对于原任务要大大缩小；
- 就近计算，即会被分配到存放了所需数据的节点进行计算；
- 这些小任务可以并行计算，彼此间几乎没有依赖关系。

## 基于MapReduce的计算过程 ##
- Map任务。

	每个任务的输入是DFS中的一个或多个文件块，可看成多个元素组成，元素可以是任意类型，同一个元素不能跨文件块。Map任务将文件块转换成一个键-值对（key-value）。所有Map任务的输入和Reduce任务的输出都是键-值对的形式，键值对的具体生成方式由用户编写Map函数决定。注意：此时的“键”不要求它们的唯一性，一个Map任务可以生产多个具有相同键的键-值对。
	MapReduce系统能够管理这些并行任务的执行及任务之间的协调，能处理某个任务执行失败的情况。我们只需编写Map和Reduce函数即可，其他都交给MapReduce来完成。

- 主控制器(master controller)

  从每个Map任务收集一系列键-值对，并按照键大小排序，然后分配给多个Reduce任务，相同键值对会归到同一Reduce任务。

	Master的任务分配过程很复杂，考虑任务时间？任务是否出错？网络通讯负担等等许多问题。

- Reduce任务

	每次作用于一个键，将与此键关联的所有值（结果）以某种方式（取决于用户编写的Reduce函数）结合起来。

## 示例：计算词语在文档中出现的次数。##
Map任务读入一篇文档，获取词语序列$w_1, w_2,..., w_n$，然后输出键-值对序列$(w_1,1), (w_2,1) ,..., (w_n,1)$

如果单词$w$在文档中出现过$m$次，则输出结果中会有$m$个$m$个键值对$(w,1)$；Reduce任务对值部分应用满足结合率和交换率的加法运算，将$m$个对合成$(w,m)$。

书中提到： 通常情况下Reduce函数都满足交换率和结合率，可以将Reduce任务中的部分工作放到Map任务中完成。对于词语例子，可以将单个Map任务产生的包含键$w$的键值对组合成一个$(w, m)$，也就是该Map任务处理的文档中出现词语$w$的次数。

##	执行细节 ##

用户程序创建一个主控进程以及运行在不同节点上的工作进程
- 对于输入文件中的每个文件块创建一个Map任务，每个Map任务都要给每个Reduce任务建立一个中间文件,存放于Map工作进程所在的本地磁盘。
- Reduce任务则尽量少。否则，中间文件的数目爆炸性增长。当Reduce任务被主控进程分配给某个工作进程时，该任务获得所有的输入文件，最终结果输出到一个文件中（该文件是整个分布式文件系统的一部分）。

## 节点失效的处理 ##

- 主控节点崩溃：整个MapReduce作业必须重启。
- 工作节点崩溃
	- Map任务节点：主控进程定期检查，一旦发现工作节点的崩溃情况，将该节点所有Map任务的状态置为“空闲”，等待某个工作进程可用时安排它们重新运行。主控进程同时通知每个Reduce任务它们的输入位置发生改变。
	- Reduce任务节点：将任务置为空闲，并安排给其他工作节点重新运行。

# 使用MapReduce算法

## 矩阵-向量乘法

## 向量v无法放入内存时的处理

## 关系代数运算

## 选择运算 ##

## 投影运算 ##

## 并、交和差运算<commit_msg>MapReduce<commit_after>---
layout: post
title:  "大规模文件系统及MapReduce"
date:   2017-08-15 10:00:00
categories: 大数据
tags: 大数据 MapReduce hadoop
excerpt: 本笔记来自于阅读《大数据-互联网大规模数据挖掘与分布式处理》第2章
mathjax: true
---

Hadoop不适合处理“快数据”。似乎有点过时了。而Spark在内存中处理数据具有较好的性能表现，同时也提供了简单易用的API，目前很火热。
事实上，它们有不同的使用场景，有不同的应用领域。它们不是替代的关系。MapReduce也在演化和扩展。

书中列举了两个例子：
- Web网页重要性排序：涉及一个迭代的矩阵-向量乘法计算，其中矩阵和向量维度达到百亿维。
- 社交网站的朋友关系网络，包含上亿个节点和几十亿条边，在这样的网络中搜索想要的信息。

解决思路（分层）
- 分布式文件系统：存储单位要比传统OS的磁盘块要大很多; 提供数据冗余机制来防止数据分布在上千块磁盘上时频发媒介故障。

- 在文件系统之上，得有一个编程模型，MapReduce编程系统，把计算分布在集群中实现。

# 1. 分布式文件系统 #
## 计算节点的物理结构 ##
集群计算(cluster computing)：计算节点存放在机架上，单节点之间网络互连，机架之间另一级网络或交换机互连。

主要故障模式：单节点故障和单机架故障

解决方案：多副本存储；计算过程分成多个任务完成，一个任务的执行不影响其他任务。

## 大规模文件系统的结构 ##
集群计算需要分布式文件系统（Distributed File System，DFS）的支持，现有DFS如GFS、HDFS、DFS Cloudstore等。DFS的应用场景：
- 大文件，TB以上级别。小文件使用DFS无任何意义。
- 文件极少更新。对于频繁变化的数据，不适合采用DFS。例如机票订购系统就不适合采用DFS，虽然数据量很大，但数据变化频繁。

在DFS中，文件被分为文件块（chunk)，大小通常为64MB，文件块会被复制多个副本放在不同的节点/机架上，副本个数一般可设置。

分散存储后如何读取文件？ 通过主节点(master node)或名字节点（name node），它们负责维护着整个文件系统的文件目录树，文件/目录的元信息和文件的数据块索引。

问题：只读共享（Hadoop）？ 还是受控写操作，或者并发写操作（基本不实用）？

# 2. MapReduce #

MapReduce通过“分而治之”管理大规模并行计算过程，同时保障对硬件的容错性(机器故障是常态)。如何拆分任务，如何合并结果？

MapReduce把复杂的任务分解为若干个“简单的任务”执行，“简单的任务”有几个含义：
- 数据或计算规模相对于原任务要大大缩小；
- 就近计算，即会被分配到存放了所需数据的节点进行计算；
- 这些小任务可以并行计算，彼此间几乎没有依赖关系。

## 基于MapReduce的计算过程 ##
- Map任务。

	每个任务的输入是DFS中的一个或多个文件块，可看成多个元素组成，元素可以是任意类型，同一个元素不能跨文件块。Map任务将文件块转换成一个键-值对（key-value）。所有Map任务的输入和Reduce任务的输出都是键-值对的形式，键值对的具体生成方式由用户编写Map函数决定。注意：此时的“键”不要求它们的唯一性，一个Map任务可以生产多个具有相同键的键-值对。
	MapReduce系统能够管理这些并行任务的执行及任务之间的协调，能处理某个任务执行失败的情况。我们只需编写Map和Reduce函数即可，其他都交给MapReduce来完成。

- 主控制器(master controller)

  从每个Map任务收集一系列键-值对，并按照键大小排序，然后分配给多个Reduce任务，相同键值对会归到同一Reduce任务。

	Master的任务分配过程很复杂，考虑任务时间？任务是否出错？网络通讯负担等等许多问题。

- Reduce任务

	每次作用于一个键，将与此键关联的所有值（结果）以某种方式（取决于用户编写的Reduce函数）结合起来。

## 示例：计算词语在文档中出现的次数。##
Map任务读入一篇文档，获取词语序列$w_1, w_2,..., w_n$，然后输出键-值对序列$(w_1,1), (w_2,1) ,..., (w_n,1)$

如果单词$w$在文档中出现过$m$次，则输出结果中会有$m$个$m$个键值对$(w,1)$；Reduce任务对值部分应用满足结合率和交换率的加法运算，将$m$个对合成$(w,m)$。

书中提到： 通常情况下Reduce函数都满足交换率和结合率，可以将Reduce任务中的部分工作放到Map任务中完成。对于词语例子，可以将单个Map任务产生的包含键$w$的键值对组合成一个$(w, m)$，也就是该Map任务处理的文档中出现词语$w$的次数。

##	执行细节 ##

用户程序创建一个主控进程以及运行在不同节点上的工作进程
- 对于输入文件中的每个文件块创建一个Map任务，每个Map任务都要给每个Reduce任务建立一个中间文件,存放于Map工作进程所在的本地磁盘。
- Reduce任务则尽量少。否则，中间文件的数目爆炸性增长。当Reduce任务被主控进程分配给某个工作进程时，该任务获得所有的输入文件，最终结果输出到一个文件中（该文件是整个分布式文件系统的一部分）。

## 节点失效的处理 ##

- 主控节点崩溃：整个MapReduce作业必须重启。
- 工作节点崩溃
	- Map任务节点：主控进程定期检查，一旦发现工作节点的崩溃情况，将该节点所有Map任务的状态置为“空闲”，等待某个工作进程可用时安排它们重新运行。主控进程同时通知每个Reduce任务它们的输入位置发生改变。
	- Reduce任务节点：将任务置为空闲，并安排给其他工作节点重新运行。

# 3. 使用MapReduce算法

## 矩阵-向量乘法

## 向量v无法放入内存时的处理

## 关系代数运算

## 选择运算 ##

## 投影运算 ##

## 并、交和差运算
{'fraction_non_alphanumeric': 0.12292296072507553, 'fraction_numerical': 0.010007552870090634, 'mean_word_length': 10.823660714285714, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4802325', 'n_tokens_mistral': 4539, 'n_tokens_neox': 5261, 'n_words': 180}