栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

7.算法进阶之分布式篇——MapReduce大规模分布式计算

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

7.算法进阶之分布式篇——MapReduce大规模分布式计算

背景

在大量的数据处理需求下,程序是分布式运行的,但是每个业务如果都需要针对雷同的问题各自做出雷同的处理,效率太低。

例子
假设一个 number 数组中,我们希望统计出数值大于 5 的那些数向上取整的和。这个问题很简单,常规的写法自然是遍历整个数组,写一个 if-else 判断出大于 5 的数,然后用一个变量做累计求和。但是这个写法引入了状态,在循环里你既需要关心 filter 的逻辑,又要关心累计求和的逻辑,不够清晰。
但是如果这样写:

function(arr) {
  arr
  .filter(a => a > 5)
  .map(a => Math.ceil(a))
  .reduce((acc, i) => acc + i);
}

通过三个原语区分开控制逻辑和计算逻辑。

map&reduce

如果我们把输入数据表示成一个键值对KEY/VALUE。输出也是。
那么我们只需要做两种操作就可以完成大部分的变化。

  1. map:对kv进行某种变换,得到和输出集合一样的集合x。这个集合x,既可以作为输出,也可以作为其他需求的中间步骤。
  2. reduce:进行合并计算,合并一些key不同,但是value相同组合,从而得到一个size比原来数据小的集合。

上面的例子有三种操作:

  1. 向上取整:进行map
  2. 过滤5以上的数,进行reduce,得到一个比原来小的集合
  3. 求和:也是reduce,函数就是简单的加法,但是能得到一个原来一半大小的集合。

除了以上例子:还有很多场景:

  1. 分布式 Grep 程序,可以用于对大量数据的模式匹配,比如查询日志中某些模式出现的数量。
  2. 统计 URL 访问频数,把所有的访问记录用 map 函数处理成 (url, 1),再用 reduce 函数对 url 相同的记录,累计计数。
  3. 网络连接逆向,把 (source, target) map 为 (target, source) ,再用 reduce 把 target 相同的记录中的 source,合并成列表,得到 (target, list(source))。
  4. 倒排索引,把文本分词,得到 (word, document) 的集合,并对同样的词进行 reduce 操作,得到(word, list(document)),这样就可以用来给搜索引擎加速查询。
分布式实现

几个原则:

  1. 把数据分区,交给不同的机器执行
  2. 在要汇总的时候也需要有办法进行数据的汇总
  3. 并且要有一定应对故障的能力。

整个 MapReduce 系统是要有一套全局共享的存储系统的,这就是谷歌鼎鼎大名的三驾马车中的另一架 GFS(Google File System)的作用,MapReduce 也是建立在这个存储系统之上的。

执行步骤:
  1. 程序先把输入文件分成m个数据段,每个段大小通常是16MB。
  2. 然后集群快速分发需要计算的任务。我们会让众多进程中的一个成为 master 进程,由它来进行任务的调度,其他进程都是 worker 进程,进行实际的计算任务。master 会把 M 个 map 任务和 R 个 reduce 任务分配给空闲的进程。
  3. map:worker读取数据之后进行map计算,输出结果缓存在内存中,然后worker通过分区函数,把一些中间temp结果定期落盘,分离在r个区域,这些区域信息传递给master,以便后续reduce使用。
  4. reduce:worker收到map存的中间temp结果,通过rpc读取。由于reduce需要按key进行聚合,所以读取完数据要做排序。最后进行reduce函数计算结果,结果被分区追加到对应的文件中。
  5. 两者都执行完,就可得到最后的计算结果。
容错(灾备):
  1. 大规模的部署来提高计算能力和稳定性
  2. 服务也需要长时间在线,不能每次出现故障都由管理员手动恢复。

worker故障:通过master定时ping操作
master 会周期性地给 worker 发送 ping 请求,如果 worker 正常就会回复,所以如果 master 一段时间没有收到回复,会把这个 worker 标记为失效 worker,相关的任务也会被设置为空闲状态,进而分配给其他空闲的 worker。
这里又区分开
map woker任务异常:由于map的结果存在本地节点中,异常节点需要重新执行该节点上所有已经完成的任务
reduce worker任务异常:因为正常完成的直接传输到全局文件中了,没有完成的异常任务是确定的最近的一个,所以只需要重新执行这一个异常的任务即可

master故障:

  1. 周期性的把 master 相关的状态信息保存到磁盘中,形成一个个检查点。如果master节点任务失败了,就从最近的一个检查点恢复。然后redo之后的操作。
  2. 对 master 引入 backup 节点,如果一个节点挂了,我们马上把备份的节点拿来当新的主节点使用

ps:但谷歌工程师偷懒,master挂了直接让这个程序挂掉,让用户重新提交任务。

总结

所有分布式计算框架比如 Hadoop、Spark、Flink 等等都是建立在 Google MapReduce 工作的基础上的。

系统设计,非常重要的一点就是对容灾能力的支持,主要就要分为故障检测和故障恢复两个步骤。

  1. 检测:引入一个控制节点对其他节点进行监控是一个非常有效的手段,通过定时的心跳(即我们刚才的ping操作),控制节点就很容易发现其他节点的异常;
  2. 故障恢复:一个有效手段就是定时设置 checkpoint,定期记录下运行正确时系统的状态,这样异常发生的时候就可以快速恢复,重新执行需要的计算。
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/951193.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号