分布式系统 - 分布式计算详解
传统的并行计算要的是：投入更多机器，数据大小不变，计算速度更快。 分布式计算要求：投入更多的机器，能处理更大的数据。
作者：张建国 链接：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 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
如同分布式存储系统一样，我对分布式计算系统也做了一个分类，如下：
- 传统基于msg的系统
- MapReduce-like 系统
- 图计算系统4. 基于状态（state）的系统
- 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 等等。由于本人对这个领域并不是很熟，就不详细介绍了。