分布式系统 - 分布式计算详解

传统的并行计算要的是:投入更多机器,数据大小不变,计算速度更快。 分布式计算要求:投入更多的机器,能处理更大的数据。

作者:张建国 链接:https://www.zhihu.com/question/23645117/answer/234783116 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

数据分布方式

哈希方式 哈希方式是最常见的数据分布方式。可以简单想象有一个大的hash表,其中每个桶对应的一台存储服务器,每条数据通过某种方式计算出其hash值分配到对应的桶中。 int serverId =data.hashcode % serverTotalNum上面只是一个简单的计算公式示例,通过这种方式就可以将数据分配到不同的服务器上。·

数据范围分布 将数据的某个特征值按照值域分为不同区间。比如按时间、区间分割,不同时间范围划分到不同server上。

数据量分布 按数据量分布,可以考虑一个简单例子:当使用log文件记录一些系统运行的日志信息时,当日志文件达到一定大小,就会生成新的文件开始记录后续的日志信息。这样的存储方式和数据的特征类型没有关系,可以理解成将一个大的文件分成固定大小的多个block。

一致性哈希 前文刚提到的哈希方式,当添加删除节点时候,所有节点都会参与到数据的迁移,整个集群都会受到影响。那么一致性哈希可以很好的解决这个问题。一致性哈希和哈希的数据分布方式大概一致,唯一不同的是一致性哈希hash的值域是个环。

作者:马超 链接:https://www.zhihu.com/question/23645117/answer/124708083 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

如同分布式存储系统一样,我对分布式计算系统也做了一个分类,如下:

  1. 传统基于msg的系统
  2. MapReduce-like 系统
  3. 图计算系统4. 基于状态(state)的系统
  4. Streaming 系统

当然不同的人可能会有不同的分类方法,不过大同小异。我们接下来聊聊这些系统都在干些什么。传统基于msg的系统 . 这类系统里比较有代表性的就是 MPI (message passing interface). 目前比较流行的两个 MPI 实现是 mpich2 和 openmpi . MPI 这个框架非常灵活,对程序的结构几乎没有太多约束,以至于大家有时把 MPI 称为一组接口 API, 而不是系统框架。在这些 API 里最常用的两个就是 send 和 recv 接口(还有一系列非阻塞扩展接口,例如:Isend, Irecv 等)。MPI 除了提供消息传递接口之外,其框架还实现了资源管理和分配,以及调度的功能。除此之外,MPI 在高性能计算里也被广泛使用,通常可以和 Infiniband 这样的高速网络无缝结合。除了 send 和 recv 接口之外,MPI 中另一个接口也值得注意,那就是 AllReduce. 这个接口在很多机器学习系统开发里都很用。因为很多并行机器学习系统都是各个进程分别训练模型,然后再合适的时候(例如一轮迭代结束)大家同步一下答案,达成共识,然后继续迭代。这个 “达成共识” 的操作往往可以很方便的通过 AllReduce 来完成。 AllReduce 接口具有两个优点:1. 高效。 2. 实用简单。 先说说为什么使用简单。使用 AllReduce 通常只需要在单机核心源码里加入 AllReduce 一行代码,就能完成并行化的功能。说 AllReduce 高效的原因是因为其底层消息传递使用了 tree aggregation,尽可能的将计算分摊到每一个节点。可是,既然 AllReduce 这么好,为什么在实际大大规模计算中很少看到呢?原因很简单,就是因为 MPI 不支持容错,所以很难扩展到大规模集群之上。不过最近陈天奇写了一个支持容错的 allreduce 接口,叫rabit,有兴趣的同学可以关注一下。 大名鼎鼎的 xgboost 底层的分布式接口就是 rabit.MapReduce-like 系统. 这一类系统又叫作 dataflow 系统,其中以 MapReduce (Hadoop) 和 Spark 为代表。其实在学术界很有很多类似的系统例如 Dryad, FlumeJava, Twister 等等。这一类系统的特点是将计算抽象成为 high-level operator, 例如像 map,reduce,filter 这样的函数式算子,然后将算子组合成 DAG ,然后由后端的调度引擎进行并行化调度。其中,MapReduce 系统属于比较简单的 DAG,只有 map 和 reduce 两层节点。MapReduce 这样的系统之所以可以扩展到超大规模的集群上运行,就是因为其完备的容错机制。在 Hadoop 社区还有很多基于 mapreduce 框架的衍生产品,比如 Hive (并行数据库OLAP), Pig(交互式数据操作)等等。MapReduce-like 的编程风格和 MPI 截然相反。MapReduce对程序的结构有严格的约束——计算过程必须能在两个函数中描述:map 和 reduce;输入和输出数据都必须是一个一个的 records;任务之间不能通信,整个计算过程中唯一的通信机会是 map phase 和 reduce phase 之间的 shuffuling phase,这是在框架控制下的,而不是应用代码控制的。因为有了严格的控制,系统框架在任何时候出错都可以从上一个状态恢复。Spark 的 RDD 则是利用 Lineage,可以让数据在内存中完成转换。由于良好的扩展性,许多人都机器学习算法的并行化任务放在了这些平台之上。比较有名的库包括 Mahout (基于Hadoop), 以及 MLI (基于 Spark) . 然而这些系统最大缺点有两点:1. 这些系统所能支持的机器学习模型通常都不是很大。导致这个问题的主要原因是这系统在 push back 机器学习模型时都是粗粒度的把整个模型进行回传,导致了网络通信的瓶颈。有些机器学习的模型可以大到无法想象,比如我们用 Field-aware factorization machine (FFM)做 criteo 的 ctr prediction 时模型大小可以达到100 GB.2. 严格的 BSP 同步计算使得集群的效率变的很低。也就是说系统很容易受到straggle的影响。图计算系统. 图计算系统是分布式计算里另一个分支,这些系统都是把计算过程抽象成图,然后在不同节点分布式执行,例如 PageRank 这样的任务,很适合用图计算系统来表示。最早成名的图计算系统当属 Google 的 pregel,该系统采用 BSP 模型,计算以 vectex 为中心。随后又有一系列图计算框架推出,例如:GPS (对 Pregel 做了优化,除了vectex-centric computation,还有 global computation,动态调整分区等等。)Giraph / Hama 都是基于 Hadoop 的 Apache 的开源 BSP 图计算项目。除了同步(BSP)图计算系统之外,异步图计算系统里的佼佼者当属 GraphLab,该系统提出了 GAS 的编程模型。目前这个项目已经该名为 dato.,专门推广基于图的大规模机器学习系统。基于状态(state)的系统. 这一类系统主要包括 2010 年 OSDI 上推出的 Piccolo, 以及后来 2012 年 nips 上 Google 推出的 distbelief,再到后来被机器系学习领域广泛应用的 Parameter Server 架构。这里我们重点介绍一下 Parameter Server 这个架构。我们之前说,MPI 由于不支持容错所以很难扩展至大规模集群之中;MapReduce 系统无法支持大模型机器学习应用,并且节点同步效率较低。用图抽象来做机器学习任务,很多问题都不能很好的求解,比如深度学习中的多层结构。而 Parameter Server 这种 state-centric 模型则把机器学习的模型存储参数上升为主要组件,并且采用异步机制提升处理能力。参数服务器的概念最早来自于 Alex Smola 于 2010 年提出的并行 LDA 架构。它通过采用分布式的 memcached 作为存放参数的存储,这样就提供了有效的机制作用于不同worker节点同步模型参数。 Google 的 jeff dean 在 2012 年进一步提出了第一代 Google Brain 大规模神经网络的解决方案 Distbelief. 在后来的 CMU 的 Eric xing 以及百度少帅 李沐 都提出了更通用的 Parameter server 架构。如果要深入 Parameter server 系统的设计,需要一些机器学习的背景,比如什么是 ssp 协议, 在此我们就不详细讨论了。Streaming 系统. Streaming 系统听名字就能看出来是为流式数据提供服务的。其中比较有名的系统包括 Storm, Spark Streaming, Flink 等等。由于本人对这个领域并不是很熟,就不详细介绍了。

联系我

添加@pdai微信

PS:添加时请备注Java全栈,谢谢!