推荐算法笔记07_工程实现与评估【上】

推荐系统的数据流

典型数据流框架

批处理大数据架构

• “分布式存储+Map Reduce”的架构只能批量处理已经落盘的静态数据，无法在数据采集、传输的工属具流动的过程中处理数据。

image-20220106101127328.png

流计算大数据架构

• 分布式流计算大数据架构在数据流产生及传递过程中流式的消费并处理数据。

• 流计算架构中使用滑动窗口，在每个窗口内部，数据被短暂缓存并消费，在完成一个窗口的数据处理后，流计算平台滑动到下一个时间窗口进行新一轮的数据处理。

• 理论上，流计算平台的延迟仅与滑动窗口的大小有关，滑动窗口的大小基本以分钟级别居多，数据延迟小。

工具

• Strom、Spark-streaming、Flink（主流）

• Flink将所有数据均看做流，把批处理当做流计算的特殊情况

• Spark-streaming的流计算时小时间片内的小批量处理

Lambda架构

• 数据通道在数据采集阶段就分为两条：实时流和离线处理

• 实时流保持了流计算框架，以增量计算为主来保障数据实时性(kafka+redis)。

• 离线部分进行批处理，对数据进行全量计算，保障其最终的一致性及最终推荐特征的丰富性(hdfs)。

• 最终数据入库时，实时流数据和离线数据进行合并，利用离线层数据对实时流数据进行校验和纠错。

Kappa架构

• 解决Lambda架构的代码冗余问题，批处理与实时流都以流计算形式进行如何在离线环境下利用同样的流处理框架进行数据批处理？

• 需要在原有流处理框架上加上两个新的通路“原始数据存储”和“数据重播”

• 原始数据存储将未经流处理的数据或者日志原封不动地保存到分布式文件系统中

• 将这些原始数据按时间顺序进行重播，采用相同的流处理框架处理，完成离线状态下的数据批处理。

推荐系统分布式离线训练

在推荐、广告、搜索等互联网场景下，动则TB甚至PB级数据量。

导致几乎不可能在传统单机环境下完成机器学习模型的训练。

分布式机器学习训练成为唯一选择。

Spark MLlib

• 如随机森林，并行计算梯度过程（数据并行）。

image-20220106110135943.png

• 把当前模型参数广播到各个数据 Partition(worker)

• 把各计算节点进行数据抽样得到mini batch的数据，分别计算梯度，再通过treeAggregate操作汇总梯度，得到最终梯度gradientSum。

• 利用gradientSum更新模型参数。

image-20220106110255571.png

• 局限性：

  • 采用全局广播的方式，在每轮迭代前广播全部模型参数，非常消耗带宽资源

  • 采用阻断式梯度下降方式，每轮梯度下降由最慢的节点决定（同步问题）

    • Spark MLlib的mini batch过程是在所有节点计算完各自的梯度之后逐层聚合，最终汇总生成全局的梯度。也就是说如果出现数据倾斜导致某个节点计算梯度时间过长，那么这一过程将阻断其他所有节点。

  • Spark MLlib并不支持复杂深度学习网络结果结构和大量可调超参

    • Spark MLlib在其标准库里只支持标准的MLP的训练，并不支持RNN、LSTM等复杂网络结构，而且无法选择不同的激活函数等大量超参。

Parameter Server

• 用异步非阻断式的分布式梯度下降策略替代同步阻断式的梯度下降策略。

• 实现多server节点的架构，避免单master节点带来的带宽瓶颈和内存瓶颈

• 实现使用一致性哈希，参数范围pull，参数范围push等工程手段实现信息的最小传递，避免广播操作带来全局性网络网络阻塞和带宽浪费。

• 服务器节点组

  • 每个服务器节点负责保存一部分模型参数，接受工作节点的局部

    梯度来汇总计算全局梯度，并更新模型参数。

  • 节点间可通信

  • manager node负责metadata的一致性，如节点状态，参数分配

• 工作节点组

  • 每个工作节点保存部分训练数据，拉取对应服务器节点模型参数并计算当前梯度，然后上传对应该服务器节点。

  • 工作节点组间，以及工作节点组内部的任务节点之间并不通信，任务节点只与server通信

  • task scheduler负责为工作节点分配任务，监控工作节点运行情况，当有新的工作节点加入或者退出时，负责重新分配任务。

• 资源管理中心组

  • 负责维护和分配各节点资源

image-20220106111255045.png

同步SGD（先计算每个worker再进入server）

image-20220106111629228.png

异步SGD（机器之间计算速度不同）

image-20220106111731116.png

在t=1 读取worker3会导致结果不一致，此时正常应该是push worker2

pull1

pull2

push1

pull3 【此处正常为push2】

push2

push3

训练加速与结果不一致的解决方案：

image-20220106111833585.png

Sequential:

• 任务之间是有顺序的，只有上一个任务完成，才能开始下一个任务（同步）

Eventual:

• 所有任务之间没有顺序，各自独立完成自己的任务（异步）

Bounded Delay:

• Sequentia跟 Eventual 之间的trade-off，设置一个 𝜏 作为最大的延时时间，

• 只有 𝜏 之前的任务都被完成了，才能开始一个新的任务

• 𝜏 = 0, 情况就是 Sequential

• 𝜏 = ∞, 情况就是 Eventual

• 必须等待慢的worker执行完才可以继续下一个

image-20220106111926908.png

Parameter Server Implementation

针对Bounded Delay的优化

• Vector Clock

  • parameter server中，参数都是可以被表示成(key,value)的集合，key就是feature ID，而value就是它的权重，对于稀疏参数，不存在的key，就可以认为是0

  • 为参数伺服器中的每个参数添加⼀个时间戳，来跟踪参数的更新和防⽌重复发送数据，基于此，通信中的梯度更新数据中也有时间戳， 防⽌重复更新

  • 如果每个参数都有一个时间戳，那么参数众多，时间戳也众多，由于parameter server在push和pull的时候都是range-based（只在局部范围内），那么在range里面的参数共享同一个时间戳，就可以大大降低空间复杂度。

• Messages

  • Messages是节点间交互的主要格式，一条message包括 [ 𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 , （𝑘1, 𝑣1） , （𝑘2, 𝑣2） , … ]

  • key和value的压缩

• 节点增加或减少的一致性哈希（负载均衡）

  • PS汇总：http://www.learn4master.com/algorithms/parameter-server-resources

http://www.cs.cmu.edu/~muli/file/ps.pdf

https://www.cs.cmu.edu/~muli/file/parameter_server_osdi14.pdf

Tensorflow

• 计算图+session

• 计算存在依赖关系的任务节点或者子图之间需要串行执行，不存在依赖关系的任务节点或子图可以并行执行

• TensorFlow的分布式训练模式采用parameter server策略，则各worker节点会以数据并行方式训练

• 单机采用CPU+GPU多核并行

https://www.tensorflow.org/guide/distributed_training?hl=zh-cn