mapreduce面试问题
在MapReduce上搜索发现各种分散的博客文章&＃xff0c;一些大学课程页面和一本书&＃xff0c;其中似乎几乎包含其他来源所做的所有事情。
这篇文章包含基于本书的MapReduce问答。 基本上&＃xff0c;如果我是一名学生&＃xff0c;这就是我作为考试准备记录所做的。 如果我要当老师&＃xff0c;这就是我在考试中要问的。
第一章给出应归功的信用&＃xff0c;其余章节包含问题。 上一章包含动手编码练习。
这本书
该书名为MapReduce的数据密集型文本处理 。 如果不确定是否要购买&＃xff0c;可以免费提供预生产手稿。
不要被标题所迷惑。 这本书更多地是关于MapReduce本身&＃xff0c;而不是文本处理。 本书的前半部分描述了对任何任务都有用的通用技巧&＃xff08;设计模式&＃xff09;。 下半部分包含有关文本处理&＃xff0c;图形算法和期望最大化的章节。
这本书包含了我在各种博客&＃xff0c;大学课程页面等等中发现的几乎所有内容。
问题
本书按章节划分问题。 除了一个小例外&＃xff08;计数器&＃xff09;外&＃xff0c;问题主要基于本书的前半部分。 下半部分包含具体算法&＃xff0c;我想专注于通用知识。
这并不意味着学习它们是没有用的。 特别是“图算法”一章包含易于推广的思想。
2 MapReduce基础
2.2映射器和简化器
描述一般的MapReduce算法。 将其分为多个阶段。 对于每个阶段&＃xff0c;包括&＃xff1a;
- 谁负责&＃xff08;框架/程序员/可定制&＃xff09;&＃xff0c;
- 它能做什么&＃xff0c;
- 相位输入
- 相位输出。
MapReduce有四个阶段&＃xff1a;
- 地图&＃xff0c;
- 结合&＃xff0c;
- 穿梭整理
- 减少。
映射阶段由映射器完成。 映射器在未排序的输入键/值对上运行。 保持输入数据运行的相同物理节点也可以使用映射器。 每个映射器为每个输入键/值对发出零&＃xff0c;一个或多个输出键/值对。 输出键/值对称为中间键/值对。 它们的类型通常不同于输入键/值对的类型。 映射器必须由程序员提供。
合并阶段由合并器完成。 组合器应将具有相同键的键/值对组合在一起。 每个组合器可以运行零次&＃xff0c;一次或多次。 框架决定是否以及多少次运行组合器&＃xff0c;程序员对此没有控制权。 组合器的输出键/值对类型必须与其输入键/值对类型相同。
班车和排序阶段由框架完成。 来自所有映射器的数据按键分组&＃xff0c;在化简器中拆分&＃xff0c;然后按键排序。 每个化简器获得与同一键关联的所有值。 程序员可以提供用于分类的自定义比较功能和用于数据拆分的分区器。 到同一化简器的所有键/值对均按键排序&＃xff0c;但没有全局排序。
Reducer获取按键排序的键/ [值列表]对。 值列表包含映射器生成的具有相同键的所有值。 每个缩减器为每个输入键/值对发出零&＃xff0c;一个或多个输出键/值对。 输出键/值对类型通常与输入键/值对类型不同。 减速器必须由程序员提供。
如果算法需要多次MapReduce迭代&＃xff0c;则每个组合器都可以增加全局计数器。 在减少阶段之后&＃xff0c;驱动程序将读取计数器。 然后&＃xff0c;它决定是否需要下一次迭代。
注意&＃xff1a;第2章未提及计数器。 它们将在后面的第5章中进行解释。确定语句是对还是错&＃xff1a;所有MapReduce实现都实现完全相同的算法。
假。 例如&＃xff0c;Google的实现不允许在化简器中更改键&＃xff0c;但可以对值进行排序。 Hadoop不提供值排序&＃xff0c;但是reducer可以更改键。
是非题&＃xff1a;每个映射器必须生成与其输入相同数量的键/值对。
假。 映射器可以生成任意数量的键/值对&＃xff08;包括零&＃xff09;。
是非题&＃xff1a;映射器输入键/值对按键排序。
假。 映射器的输入不进行任何排序。
是非题&＃xff1a;映射器的输出键/值必须与输入的类型相同。
假。 映射器可以产生任何类型的键/值对。
是非题&＃xff1a;Reducer应用于与同一键关联的所有值。
真正。 Reducer应用于与同一键关联的所有值。
是非题&＃xff1a;约简输入的键/值对按键排序。
真正。 约简输入的键/值对按键排序。
实施。
是非题&＃xff1a;每个化简器必须生成与其输入相同数量的键/值对。
假。 Reducer可以生成任意数量的键/值对&＃xff08;包括零&＃xff09;。
是非题&＃xff1a;Reducers输出键/值对必须与输入类型相同。
假。 该语句在Hadoop中为false&＃xff0c;在Google的实现中为true。
2.3执行框架
如果发生硬件/软件故障&＃xff0c;该怎么办&＃xff1f;
MapReduce框架必须能够从硬件&＃xff08;磁盘故障&＃xff0c;RAM错误&＃xff09;和软件&＃xff08;错误&＃xff0c;意外异常&＃xff09;错误中恢复。 两者都是常见的和预期的。
是否可以在某些映射器仍在运行时启动reducer&＃xff1f; 为什么&＃xff1f;
否。Reducer的输入按键分组。 理论上&＃xff0c;最后一个映射器可以生成运行reducer已经消耗的密钥。
定义一个散乱的人。
Straggler是地图绘制或简化任务&＃xff0c;需要花费很长时间才能完成。
什么是推测执行&＃xff08;也称为备份任务&＃xff09;&＃xff1f; 它解决什么问题&＃xff1f;
同一任务的相同副本在多个节点上执行。 输出使用的最快任务。
如果任务由于硬件问题而变慢&＃xff0c;则推测执行将有所帮助。 如果键上的值分布偏斜&＃xff0c;则无济于事。
2.4分区器和合并器
分区程序做什么&＃xff1f;
分区程序在简化程序之间划分由映射任务产生的键/值对。
合并器做什么&＃xff1f;
合并器在穿梭和排序阶段之前或期间对映射器生成的键/值对进行本地聚合。 通常&＃xff0c;它减少了节点之间要传输的数据量。
框架决定运行多少次。 组合器可以在同一输入上运行零次&＃xff0c;一次或多次。
确定该语句是对还是错&＃xff1a;每个组合器仅运行一次。
假。 框架决定组合器运行零次&＃xff0c;一次还是多次。
2.5分布式文件系统
简要描述HDFS架构。
HDFS有一个名称节点和许多数据节点。 Namenode是主节点&＃xff0c;负责协调文件操作&＃xff0c;确保系统完整性并保留名称空间&＃xff08;元数据&＃xff0c;目录结构&＃xff0c;文件到块的映射等&＃xff09;。
数据存储在数据节点上的大块中。 每个块均存储在多个&＃xff08;默认情况下为三个&＃xff09;数据节点上。 名称节点检查数据节点是否正常工作并管理数据复制。
客户联系名称节点&＃xff0c;该节点回答数据块ID和数据节点ID。 然后&＃xff0c;数据节点将数据直接发送到客户端。
确定该语句是对还是错&＃xff1a;HDFS擅长管理大量小文件。
假。 HDFS擅长管理大型文件。
2.6 Hadoop集群架构
解释jobtracker和tasktracker之间的区别&＃xff1f;
客户端在jobtracker上执行作业。 Jobtracker在主服务器上运行。 Jobtracker监视MapReduce作业。 它还协调映射器和缩小器。
Tasktracker在从属节点上同时运行用户代码和datanode守护程序。 客户端永远不会联系它。
解释映射器的生命周期。
在调用任何其他方法之前&＃xff0c;将调用初始化方法。 它没有参数&＃xff0c;也没有输出。
每个键/值对分别调用Map方法。 它处理输入键/值对并发出中间键/值对。
处理完所有输入键/值后&＃xff0c;将运行Close方法。 该方法应关闭所有打开的资源。 它还可能会发出键/值对。
解释减速器的生命周期。
在调用任何其他方法之前&＃xff0c;将调用初始化方法。 它没有参数&＃xff0c;也没有输出。
对每个键/ [值列表]对分别调用reduce方法。 它处理中间键/值对并发出最终键/值对。 它的输入是键和迭代器&＃xff0c;该迭代器遍历与同一键关联的所有中间值。
处理完所有输入键/值后&＃xff0c;将运行Close方法。 该方法应关闭所有打开的资源。 它还可能会发出键/值对。
3 MapReduce算法设计
3.1本地聚集
什么是本地聚合&＃xff0c;为什么要使用它&＃xff1f;
组合器或映射器将键/值对与相同的键组合在一起。 他们可能还会对合并值进行一些其他预处理。 仅合并由同一映射器生成的键/值对。
映射任务创建的键/值对在随机和排序阶段在节点之间传输。 本地聚合减少了要传输的数据量。
如果值在键上的分布不均匀&＃xff0c;则合并器中的数据预处理有助于消除散乱的情况。
什么是映射器内合并&＃xff1f; 说明编写自定义组合器的优缺点。
在映射器内部完成本地聚合&＃xff08;键/值对的组合&＃xff09;。
Map方法不发出键/值对&＃xff0c;它仅更新内部数据结构。 Close方法组合并预处理所有存储的数据&＃xff0c;并发出最终的键/值对。 内部数据结构使用init方法初始化。
优点&＃xff1a;
- 它将只运行一次。 合并器可能运行多次或根本不运行。
- 我们确信它将在地图阶段运行。 合并器可以在映射阶段之后或在缩减阶段之前运行。 后一种情况不能减少传输的数据。
- 映射器内合并通常更有效。 合并器不会减少映射器生成的数据量&＃xff0c;它只会将生成的数据分组在一起。 这会导致不必要的对象创建&＃xff0c;破坏&＃xff0c;序列化和反序列化。
缺点&＃xff1a;
- 可伸缩性瓶颈&＃xff1a;该技术取决于是否有足够的内存来存储所有部分结果。 我们必须定期清除部分结果&＃xff0c;以避免出现这种情况。 组合器的使用不会产生可伸缩性瓶颈。
3.2对和条纹
在同现示例中解释对设计模式。 包括针对Stripes方法的优缺点&＃xff0c;可能的优化及其功效。
映射器生成由同时出现的成对单词组成的键。 该值包含数字1。Framework将具有相同工作对的键/值对组合在一起&＃xff0c;而reducer只是为每个传入的键/值对计算数字值。
每个最终对在共现矩阵中编码一个单元。 可以使用本地聚合&＃xff0c;例如合并器或映射器内合并。
优点&＃xff1a;
- 简单的值&＃xff0c;较少的序列化/反序列化开销。
- 更简单的内存管理。 没有可伸缩性瓶颈&＃xff08;仅在使用映射器内优化的情况下&＃xff09;。
缺点&＃xff1a;
- 大量的中间键/值对。 随机和排序阶段较慢。
- 本地聚合效果不佳–太多不同的键。
在同现示例中解释Stripes设计模式。 包括针对配对方法的优点/缺点&＃xff0c;可能的优化及其功效。
映射器从每个遇到的单词中生成一个不同的键。 关联值包含所有同时出现的单词的地图作为地图键&＃xff0c;并同时出现的次数作为地图值。 框架将相同的单词组合在一起&＃xff0c;而reducer合并值映射。
每个最终对在共现矩阵中编码一行。 可以使用合并器或映射器内合并。
优点&＃xff1a;
- 少量的中间键/值对。 随机排序阶段更快。
- 中间键较小。
- 有效的本地聚合–较少数量的不同键。
缺点&＃xff1a;
- 复杂的值&＃xff0c;更多的序列化/反序列化开销。
- 更复杂的内存管理。 由于价值图可能会变得太大&＃xff0c;因此该方法可能会导致可伸缩性瓶颈。
解释条带化方法引起的可伸缩性瓶颈。
条纹解决方案在内存中保留了共同出现的单词的映射。 因为共现单词的数量是无限的&＃xff0c;所以地图的大小也是无限的。 巨大的映射无法容纳到内存中&＃xff0c;并导致分页或内存不足错误。
3.3计算相对频率
同现问题的相对频率&＃xff1a;
Input: text documents
key: document id
value: text document
输出&＃xff1a;键/值对&＃xff0c;其中
键&＃xff1a;对&＃xff08;word1&＃xff0c;word2&＃xff09;
值&＃xff1a;&＃xff03;co-occurrences&＃xff08;word1&＃xff0c;word2&＃xff09;/&＃xff03;co-occurrences&＃xff08;word1&＃xff0c;任何单词&＃xff09;
针对同现问题的相对频率修复以下解决方案&＃xff1a;
class MAPPERmethod INITIALIZEH &＃61; new hash map method MAP(docid a, doc d)for all term w in doc d dofor all term u patri neighbors(w) doH(w) &＃61; H(w) &＃43; 1emit(pair(u, w), count 1)method CLOSE for all term w in Hemit(pair(w, *), H(w)) class REDUCERvariable total_occurrences &＃61; 0method REDUCE(pair (p, u), counts[c1, c2, ..., cn])s &＃61; 0for all c in counts[c1, c2, ..., cn] do s &＃61; s &＃43; cif u &＃61; * total_occurrences &＃61; selseemit(pair p, s/total_occurrences)class SORTING_COMPARATORmethod compare(key (p1, u1), key (p2, u2))if p1 &＃61; p2 AND u1 &＃61; *return key1 is lowerif p1 &＃61; p2 AND u2 &＃61; *return key2 is lowerreturn compare(p1, p2)
缺少分区程序&＃xff0c;框架可以将总计的键/值对发送给与带有单词对的键/对不同的reducer。
class PARTITIONING_COMPARATORmethod compare(key (p1, u1), key (p2, u2))if p1 &＃61; p2 return keys are equalreturn keys are different
描述顺序反演设计模式 。
如果算法需要两次通过映射器生成的具有相同键的键/值对&＃xff0c;则使用顺序反转。 第一次通过会生成一些总体统计信息&＃xff0c;然后在第二次通过时将其应用于数据。 精简器将需要在内存中缓冲数据&＃xff0c;以便能够两次通过它们。
第一遍结果由映射器计算并存储在某些内部数据结构中。 在所有通常的中间键/值对之后&＃xff0c;映射器以close方法发出结果。
该模式需要自定义分区和排序。 首先通过的结果必须在通常的键/值对之前到达减速器。 当然&＃xff0c;它必须使用相同的减速器。
3.4次要排序
描述值对键的设计模式。
Hadoop实施未在化简器输入中提供对分组值的排序。 值对键用作解决方法。
该值的一部分会添加到密钥中。 然后&＃xff0c;自定义排序按键对主要排序&＃xff0c;对附加值进行次排序。 自定义分区程序必须将具有相同原始键的所有数据移至相同的reducer。
3.5关系联接
描述具有一对一关系的表之间的减少侧连接。
Mapper生成键/值对&＃xff0c;其中键的连接ID为键&＃xff0c;行值作为值。 在混洗和排序阶段&＃xff0c;框架将两个表中的对应行分组在一起。
reducer中的reduce方法获取联接id和两个值&＃xff0c;每个值代表一个表中的行。 Reducer连接数据。
描述具有一对多关系的表之间的减少侧连接。
我们假设联接键是表S中的主键。第二个表称为T。换句话说&＃xff0c;表S in位于关系的“一个”侧&＃xff0c;而表T位于关系的“许多”侧。关系。
我们必须实现映射器&＃xff0c;自定义排序器&＃xff0c;分区器和简化器。
映射器生成由联接ID和表标志组成的键。 分区程序以这样一种方式拆分数据&＃xff0c;即所有具有相同连接ID的键/值对都将分配到相同的reducer。 自定义排序将表S生成的键/值对放在表T中具有相同联接ID的键/值对之前。
减速器输入如下所示&＃xff1a;
((JoinId1, s)-> row)
((JoinId1, t)-> [rows])
减速器将s对中的所有行与后继t对中的所有行连接在一起。
描述具有多对多关系的表之间的减少侧连接。
我们假设数据存储在名为S和T的表中。表S较小。 我们必须实现映射器&＃xff0c;自定义排序器&＃xff0c;分区器和简化器。
映射器生成由联接ID和表标志组成的键。 分区程序以这样一种方式拆分数据&＃xff0c;即所有具有相同连接ID的键/值对都将分配到相同的reducer。 定制排序将从表S生成的键/值对放在所有键/值对与表T的数据之前。
减速器输入如下所示&＃xff1a;
((JoinId1, s)-> [rows])
((JoinId1, t)-> [rows])
精简器将表S中具有相同JoinId的所有行缓冲到内存中&＃xff0c;并将它们与随后的T个表行连接起来。
较小表中的所有数据都必须放入内存中-该算法存在可伸缩性瓶颈问题。
描述两个数据库表之间的地图侧连接。
仅当满足以下假设时&＃xff0c;地图侧联接才有效&＃xff1a;
- 这两个数据集均按连接键排序&＃xff0c;
- 两个数据集以相同的方式进行分区。
映射器映射到较大的数据集&＃xff0c;并读取映射器内部较小数据集的相应部分。 由于较小的集合与较大的集合以相同的方式进行分区&＃xff0c;因此只有一个map任务访问相同的数据。 由于数据是通过join键排序的&＃xff0c;因此我们可以执行merge join O(n) 。
描述内存支持的联接。
较小的数据集将加载到每个映射器的内存中。 映射器遍历较大的数据集&＃xff0c;并将其与内存中的数据结合在一起。 如果较小的集合太大而无法容纳到内存中&＃xff0c;则将数据集加载到memcached或其他某种缓存解决方案中。
哪一个更快&＃xff1f; 地图侧连接还是减少侧连接&＃xff1f;
地图侧联接更快。
转到第2部分
参考&＃xff1a;我们的JCG合作伙伴 Maria Jurcovicova在This is Stuff博客上的MapReduce问答 。
翻译自: https://www.javacodegeeks.com/2012/05/mapreduce-questions-and-answers-part-1.html
mapreduce面试问题
京公网安备 11010802041100号