大数据相关算法题解
- Spark的执行机制
Spark是一种类Hadoop MapReduce的通用并行计算框架，spark基于map reduce算法来实现分布式计算。
Spark的中间数据放到内存中，对于迭代运算效率更高，并且相比Hadoop提供了更多的数据集操作类型，如map, filter, flatMap, sample等（称为Transformation）。同时spark还提供了count，collect，reduce等action操作。
图1.1 是Spark在分布式集群上的一般执行框架，包括了sparkcontext（上下文），cluster manager（资源管理器），executor（单个节点的执行进程）cluster manager负责整个集群的统一资源管理，executor是应用执行的主要进程，内部包含多个task线程以及内存空间。
图1.2具体描述了spark的执行机制流程，
（1）应用程序在使用spark-submit提交后，根据提交时的参数设置在相应位置初始化sparkcontext，即spark的运行环境，并创建DAG Scheduler和Task Scheduler，Driver根据应用程序执行代码，将整个程序根据action算子划分成多个job，每个job内部构件DAG图，DAG Scheduler将DAG图划分为多个stage，同时每个stage内部划分为多个task，DAG Scheduler将taskset传给Task Scheduler，Task Scheduler负责集群上task的调度。
（2）Driver根据sparkcontext中的资源需求向resource manager申请资源，包括executor数及内存资源。
（3）资源管理器收到请求后在满足条件的work node节点上创建executor进程。
（4）executor创建完成后会向driver反向注册，以便driver可以分配task给其执行。
（5）当程序执行完毕，driver会向resource manager注销所申请的资源。
- spark的transformation和action的区别
Spark是以RDD（弹性分布式数据集）为中心运行的，RDD是一个容错的、可以被并行操作的元素集合。Transformation和action是其中的两类操作算子
Transformation操作会针对已有的RDD创建一个新的RDD，常用方法包括了：
（1）map(func)：将func函数作用到数据集的每个元素，生成一个新的分布式的数据集并返回。
（2）filter(func)：选出所有func返回值为true的元素，作为一个新的数据集返回。
（3）flagMap(func)：与map类似，但是每个输入的item能够被map到0个或者更多的items输出。
（4）sample(withReplacement, fraction, seed)：从数据中抽样，withReplacement表示是否有放回，withReplacement = true表示有放回抽样，fraction为抽样的概率，seed为随机种子。
（5）union：并集操作，将源数据集与union中的输入数据集取并集，默认保留重复元素。
action则主要是对RDD进行最后的操作，比如遍历、reduce、保存到文件等，并可以返回结果给Driver程序，常用方法包括了：
（1）reduce(func)：使用函数func对数据集中的元素做聚集操作。
（2）collect()：在driver程序中以数组形式返回数据集中所有的元素。
（3）count()：返回数据集中元素的个数。
（4）first()：返回数据集中的第一个元素。
- 如何实现分布式 SGD？
SGD(随机梯度下降)是一种用于训练神经网络的优化算法，用于调整权重、更新参数，能在每次反向传播步骤之后使结果更接近最小值。SGD 不同于单纯的梯度下降，因为其处理的是 mini-batch，而非单个训练样本。其形式如下：
其中是为当前批计算出的权重，n 是 mini-batch 中的训练样本的数量，∇l(x, w_t) 是为前一个训练样本计算出的梯度。
对于分布式的情况，SGD 可分为两类：异步 SGD 和同步 SGD。
同步 SGD 是当前用于分布式训练的最常用优化方法之一。网络中的节点首先在它们的本地数据批上计算出梯度，然后每个节点都将它们的梯度发送给主服务器。主服务器通过求这些梯度的平均来累积这些梯度，从而为权重更新步骤构建出新的全局梯度集。这些全局梯度会通过使用与单机器 SGD 同样的配方来更新每个节点的本地权重。这整个过程都类似于在单台机器上通过单个数据 mini-batch 计算前向通过和反向传播步骤，因此同步 SGD 能保证收敛。但是同步 SGD 也存在一些局限性：慢，大部分计算都依赖于主服务器，其他卡都在等他的结果。
异步 SGD ，允许在不同节点上使用不同的数据子集来并行地训练多个模型副本。每个模型副本都会向参数服务器请求全局权重，处理一个 mini-batch 来计算梯度并将它们发回参数服务器，然后参数服务器会据此更新全局权重。因为每个节点都独立计算梯度且无需彼此之间的交互，所以它们可以按自己的步调工作，也对机器故障更为稳健，即如果一个节点故障，其它节点还能继续处理。
在日常训练模型的时候，我们无需关注底层细节，pytorch 等模型库都提供了很好的封装，直接使用即可。pytorch中的有两种分布式训练方式，一种是常用的DataParallel(DP)，另外一种是DistributedDataParallel(DDP)，两者都可以用来实现数据并行方式的分布式训练，DP采用的是PS模式，DDP采用的是ring-all-reduce模式，两种分布式训练模式主要区别如下：
DP是单进程多线程的实现方式，DDP是采用多进程的方式
DP只能在单机上使用，DDP单机和多机都可以使用
DDP相比于DP训练速度要快
import torch.distributed as dist # 建议使用 ddp 训练，前期学习成本稍微高一点，但很能提升效率 from torch.nn.parallel import DistributedDataParallel as DDP
