写点什么

Spark on Angel:Spark 机器学习的核心加速器

  • 2017-08-20
  • 本文字数:4423 字

    阅读完需:约 15 分钟

Spark 的核心概念是 RDD,而 RDD 的关键特性之一是其不可变性,来规避分布式环境下复杂的各种并行问题。这个抽象,在数据分析的领域是没有问题的,它能最大化的解决分布式问题,简化各种算子的复杂度,并提供高性能的分布式数据处理运算能力。

然而在机器学习领域,RDD 的弱点很快也暴露了。机器学习的核心是迭代和参数更新。RDD 凭借着逻辑上不落地的内存计算特性,可以很好的解决迭代的问题,然而 RDD 的不可变性,却非常不适合参数反复多次更新的需求。这本质上的不匹配性,导致了 Spark 的 MLlib 库,发展一直非常缓慢,从 2015 年开始就没有实质性的创新,性能也不好。

为此,Angel 在设计生态圈的时候,优先考虑了 Spark。在 V1.0.0 推出的时候,就已经具备了 Spark on Angel 的功能,基于 Angel 为 Spark 加上了 PS 功能,在不变中加入了变化的因素,可谓如虎添翼。

我们将以 L-BFGS 为例,来分析 Spark 在机器学习算法的实现上的问题,以及 Spark on Angel 是如何解决 Spark 在机器学习任务中的遇到的瓶颈,让 Spark 的机器学习更加强大。

1. L-BFGS 算法说明

L-BFGS 模型参数更新过程如下:

计算 pk = Hk-1 gk 伪代码如下所示,这是人们常说的 two-loop recursion 算法,是 Limited-BFGS 算法的核心部分。
返回值 r 是我们说要的 pk。

其中,H0-1 是单位阵,yk=gk-gk-1, sk=wk-w k-1k-1,L-BFGS 算法将最近 m 轮生成的 yk 和 sk 序列,记做 {yk} 和 {sk}。基于计算 {yk} 和 {sk} 计算 pk 。

2.L-BFGS 的 Spark 实现

2.1 实现框架

Spark 中的 driver 负责协调整个 Spark 任务执行的同时,需要保存最近 m 轮的 {yk} 和 {sk} 序列,并在 driver 上执行 two-loop recursion 算法。而 executor 负责分布式地计算梯度向量。

迭代过程:
(1)每轮迭代,将每个 executor 计算的梯度 Aggregate 到 driver
(2)yk 和 sk 保存在 driver 上,在 driver 端执行 two-loop recursion 算法
(3)driver 上更新模型 w,并将 w 广播到每个 Executor

2.2 性能分析

基于 Spark 的 L-BFGS 实现的算法优点比较明显:

  • HDFS I/O
    Spark 可以快速读写 HDFS 上的训练数据;
  • 细粒度的负载均衡
    并行计算梯度时,Spark 具有强大的并行调度机制,保证 task 快速执行;
  • 容错机制
    当计算节点挂掉、任务失败,Spark 会根据 RDD 的 DAG 关系链实现数据的重计算。但是对于迭代式算法,每轮迭代要用 RDD 的 action 操作,打断 RDD 的 DAG,避免因为重计算引起逻辑的错乱;
  • 基于内存的计算
    基于内存的计算过程,可以加速机器学习算法中计算梯度过程的耗时。

该实现的缺点:

  • treeAggregate 引起的网络瓶颈
    Spark 用 treeAggregate 聚合梯度时,如果模型维度达到亿级,每个梯度向量都可能达到几百兆;此时 treeAggregate 的 shuffle 的效率非常低;

  • driver 单点

    • 保存{yk}和{sk}序列需要较大的内存空间;
    • two-loop recursion 算法是由 driver 单点执行,该过程是多个高维度的向量的运算;
    • 每轮迭代,driver 都需要和 executor 完成高维度向量的 aggregate 和 broadcast。

3.L-BFGS 的 Spark on Angel 实现

3.1 实现框架

Spark on Angel 借助 Angel PS-Service 的功能为 Spark 引入 PS 的角色,减轻整个算法流程对 driver 的依赖。two-loop recursion 算法的运算交给 PS,而 driver 只负责任务的调度,大大减轻的对 driver 性能的依赖。

Angel PS 由一组分布式节点组成,每个 vector、matrix 被切分成多个 partition 保存到不同的节点上,同时支持 vector 和 matrix 之间的运算;

{yk} 和 {sk} 序列分布式地保存到 Angel PS 上,two-loop recursion 算法中高维度的向量计算也是在 PS 上完成。Spark executor 每轮迭代过程会从 PS 上Pull w 到本地,并将计算的梯度向量Push到 PS。

迭代过程:

(1)每轮迭代,executor 将 PS 上的模型 w pull 到本地,计算梯度,然后梯度向量 push 给 PS

(2)yk 和 sk 保存在 PS 上,在 PS 端执行 two-loop recursion 算法

(3)PS 上更新模型 w

3.2 性能分析

整个算法过程,driver 只负责任务调度,而复杂的 two-loop recursion 运算在 PS 上运行,梯度的 Aggregate 和模型的同步是 executor 和 PS 之间进行,所有运算都变成分布式。在网络传输中,高维度的 PSVector 会被切成小的数据块再发送到目标节点,这种节点之间多对多的传输大大提高了梯度聚合和模型同步的速度。

这样 Spark on Angel 完全避开了 Spark 中 driver 单点的瓶颈,以及网络传输高维度向量的问题。

4.“轻易强快”的 Spark on Angel

Spark on Angel 是 Angel 为解决 Spark 在机器学习模型训练中的缺陷而设计的“插件”,没有对 Spark 做"侵入式"的修改,是一个独立的框架。可以用 “”、“”、“”、“” 来概括 Spark on Angel 的特点。

4.1 轻——"插件式"的框架

Spark on Angel 是 Angel 为解决 Spark 在机器学习模型训练中的缺陷而设计的“插件”。Spark on Angel 没有对 Spark 中的 RDD 做侵入式的修改,Spark on Angel 是依赖于 Spark 和 Angel 的框架,同时其逻辑又独立于 Spark 和 Angel。

因此,Spark 用户使用 Spark on Angel 非常简单,只需在 Spark 的提交脚本里做三处改动即可,详情可见 Angel 的 Github Spark on Angel Quick Start 文档

可以看到提交的 Spark on Angel 任务,其本质上依然是一个 Spark 任务,整个任务的执行过程与 Spark 一样的。

复制代码
source ${Angel_HOME}/bin/spark-on-angel-env.sh
$SPARK_HOME/bin/spark-submit \
--master yarn-cluster \
--conf spark.ps.jars=$SONA_ANGEL_JARS \
--conf spark.ps.instances=20 \
--conf spark.ps.cores=4 \
--conf spark.ps.memory=10g \
--jars $SONA_SPARK_JARS \
....

Spark on Angel 能够成为如此轻量级的框架,得益于 Angel 对 PS-Service 的封装,使 Spark 的 driver 和 executor 可以通过 PsAgent、PSClient 与 Angel PS 做数据交互。

4.2 强——功能强大,支持 breeze 库

breeze 库是 scala 实现的面向机器学习的数值运算库。Spark MLlib 的大部分数值优化算法都是通过调用 breeze 来完成的。如下所示,Spark 和 Spark on Angel 两种实现都是通过调用breeze.optimize.LBFGS实现的。Spark 的实现是传入的类型是 breeze 库的DenseVector,而 Spark on Angel 的实现是传入BreezePSVector

BreezePSVector是指 Angel PS 上的 Vector,该 Vector 实现了 breeze NumericOps 下的方法,如常用的 dot,scale,axpy,add 等运算,因此在LBFGS[BreezePSVector] two-loop recursion 算法中的高维度向量运算是BreezePSVector之间的运算,而BreezePSVector之间全部在 Angel PS 上分布式完成。

  • Spark 的 L-BFGS 实现
复制代码
import breeze.optimize.LBFGS
  val lbfgs = new LBFGS[DenseVector](maxIter, m, tol)
  val states = lbfgs.iterations(Cost(trainData), initWeight)
<div class="md-section-divider"></div>
  • Spark on Angel 的 L-BFGS 实现
    接口调用里的 Vector 泛型从DenseVector变成 BreezePSVector
复制代码
  import breeze.optimize.LBFGS
  val lbfgs = new LBFGS[BreezePSVector](maxIter, m, tol)
  val states = lbfgs.iterations(PSCost(trainData), initWeightPS)
<div class="md-section-divider"></div>

4.3 易——编程接口简单

Spark 能够在大数据领域这么流行的另外一个原因是:其编程方式简单、容易理解,Spark on Angel 同样继承了这个特性。

Spark on Angel 本质是一个 Spark 任务,整个代码实现逻辑跟 Spark 是一致的;当需要与 PSVector 做运算时,调用相应的接口即可。

如下代码所示,LBFGS 在 Spark 和 Spark on Angel 上的实现,二者代码的整体思路是一样的,主要的区别是梯度向量的 Aggregate 和模型 的 pull/push。
因此,如果将 Spark 的算法改造成 Spark on Angel 的任务,只需要修改少量的代码即可。

L-BFGS 需要用户实现DiffFunctionDiffFunctioncalculte接口输入参数是 ,遍历训练数据并返回 loss 和 gradient。

其完整代码,请前往 Github SparseLogistic

  • Spark 的DiffFunction实现
复制代码
  case class Cost(trainData: RDD[Instance]) extends DiffFunction[DenseVector] {
    def calculate(w: DenseVector): (Double, DenseVector) = {
      // 广播 w
      val bcW = sc.broadcast(w)
      // 通过 treeAggregate 的方式计算 loss 和 gradient
      val (cumGradient, cumLoss) = trainData
        .treeAggregate((new DenseVector(x.length), 0.0)) (seqOp, combOp)
      val resGradient = new DenseVector(cumGradient.toArray.map(_ / sampleNum))
      (cumLoss / sampleNum, resGradient)
    }
<div class="md-section-divider"></div>
  • Spark on Angel 的 DiffFunction 实现

calculate接口输入参数是 w ,遍历训练数据并返回 loss 和 cumGradient。其中 w 和 cumGradient都是BreezePSVector;计算梯度时,需要将 Pull 到本地,本地的 gradient 值,需要通过PSVectorincrementAndFlush方式 Push 到远程 PS 上的cumGradient向量。

复制代码
case class PSCost(trainData: RDD[Instance]) extends DiffFunction[BreezePSVector] {
override def calculate(w: BreezePSVector): (Double, BreezePSVector) = {
// 初始化 gradient 向量:cumGradient
val cumGradient = pool.createZero().mkBreeze()
// 计算梯度和 loss
val cumLoss = trainData.mapPartitions { iter =>
// pull 模型 w 到 executor 本地
val localW = w.toRemote.pull()
val (gradient, loss) = calculateGradAndLoss(iter, localW)
// incement 本地的 grad 到 PS 的 cumGradient
cumGradient.toRemote.incrementAndFlush(gradient)
Iterator.single(loss)
}.sum()
cumGradient *= 1.0 / sampleNum
(cumLoss / sampleNum, cumGradient)
}
}

4.4 快——性能强劲

我们分别实现了 SGD、LBFGS、OWLQN 三种优化方法的 LR,并在 Spark 和 Spark on Angel 上做了实验对比。
该实验代码请前往 Github SparseLRWithX.scala

  • 数据集:腾讯内部某业务的一份数据集,2.3 亿样本,5 千万维度
  • 实验设置:
    说明 1:三组对比实验的资源配置如下,我们尽可能保证所有任务在资源充足的情况下执行,因此配置的资源比实际需要的偏多;
    说明 2:执行 Spark 任务时,需要加大 spark.driver.maxResultSize 参数;而 Spark on Angel 就不用配置此参数。

如上数据所示,Spark on Angel 相较于 Spark 在训练 LR 模型时有 50% 以上的加速;对于越复杂的模型,其加速的比例越大。

5. 结语

Spark on Angel 的出现可以高效、低成本地克服 Spark 在机器学习领域遇到的瓶颈;我们将继续优化 Spark on Angel,并提高其性能。也欢迎大家在 Github 上一起参与我们的改进。

Angel 项目 Github: Angel ,喜欢的话到 Github 上给我们 Star。


感谢蔡芳芳对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作,请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博( @InfoQ @丁晓昀),微信(微信号: InfoQChina )关注我们。

2017-08-20 19:002117

评论

发布
暂无评论
发现更多内容

技术分享| 快对讲,全球对讲

anyRTC开发者

快对讲 抗丢包 网络传输FEC GT-RTN 语音对讲

多云管理平台cmp是什么意思?谁能清楚解释一下

行云管家

云计算 云服务 多云管理 云资源 云管理

作为程序员,对于底层原理真的有那么重要吗?

C++后台开发

后端开发 Linux服务器开发 C++后台开发 底层原理 底层开发

“减负”,让“猪”可以飞得更高

鼎道智联

【云计算】多云管理平台和公有云两者之间是啥关系?

行云管家

云计算 公有云 私有云 多云管理平台 云管理

【网易云信】深度剖析「圈组」消息系统设计 | 「圈组」技术系列文章

网易智企

音视频 IM Discord

web前端培训高频面试题

@零度

前端开发

【云图说】每个成功的业务系统都离不开APIG的保驾护航

华为云开发者联盟

云计算 华为云 业务系统

Meta公司新探索 | 利用Alluxio数据缓存降低Presto延迟

Alluxio

facebook 数据缓存 presto Alluxio meta

洞见科技入选「爱分析· 隐私计算厂商全景报告」,获评金融解决方案代表厂商

洞见科技

隐私保护 隐私计算 数据流通

搜狐员工遭遇工资补助诈骗 黑产与灰产有何区别 又要如何溯源?

郑州埃文科技

网络安全 网络灰黑产 IP溯源

从“化学家”到开发者,从甲骨文到TDengine,我人生的两次重要抉择

TDengine

数据库 tdengine 开源 时序数据库

“易 +”开源计划丨基于 WebRTC 的低延时播放器设计和实践

网易智企

开源 IM 低延时直播

区块链哈希竞猜娱乐游戏俱乐部系统开发

开发微hkkf5566

【大咖秀】博睿数据眼中的AIOps,选择正确的赛道正确的人

博睿数据

AIOPS 智能运维 博睿数据

API如何检测安全配置是否有错误?

百家饭隐私计算平台创业者

安全 API

大数据培训Flink高频面试题分享

@零度

flink 大数据开发

「大模型」之所短,「知识图谱」之所长

博文视点Broadview

焱融看|混合云环境下,如何实现数据湖最优存储解决方案

焱融科技

数仓的基本概念

五分钟学大数据

数据仓库 6月月更

你对PHP数据类型或者其他编程语言的数据类型了解多少呢

迷彩

php 基础 6月月更 InfoQ极客传媒15周年庆

2022年6月中国数据库排行榜:TiDB卷土重来摘桂冠,达梦蛰伏五月夺探花

墨天轮

数据库 TiDB 国产数据库 polarDB KingBase

一次主从表集成流程开发过程

agileai

数据同步 企业服务总线 预置样例 集成流程 主从服务

Mass区块链哈希娱乐游戏开发平台搭建

开发微hkkf5566

20年技术老兵放弃大厂CTO头衔!这家创业公司凭什么吸引他?

XTransfer技术

CTO 跨境支付

架构实战营 第 6 期 模块八课后作业

火钳刘明

#架构实战营 「架构实战营」

2022 年 5 月产品大事记

FinClip

算力网络照进现实,浩鲸科技如何构建?

鲸品堂

算力网络

产品开发的早期阶段,是选择开发app还是小程序?

开源直播系统源码

软件开发 APP开发 小程序开发 直播源码

为你推荐一款高效的IO组件——okio

HarmonyOS开发者

HarmonyOS

【网易云信】深度剖析「圈组」关系系统设计 | 「圈组」技术系列文章

网易智企

音视频 IM Discord

Spark on Angel:Spark机器学习的核心加速器_语言 & 开发_云加社区_InfoQ精选文章