IT评测·应用市场-qidao123.com技术社区

标题: 我用Awesome-Graphs看论文：解读Naiad [打印本页]

---

作者: 水军大提督    时间: 2024-7-31 11:59
标题: 我用Awesome-Graphs看论文：解读Naiad

Naiad论文：《Naiad: A Timely Dataflow System》

前面通过文章《论文图谱当如是：Awesome-Graphs用200篇图体系论文打个样》向大家介绍了论文图谱项目Awesome-Graphs，并分享了Google的Pregel、OSDI'12的PowerGraph、SOSP'13的X-Stream。这次向大家分享Microsoft发表在SOSP'13的另一篇关于流处置惩罚体系论文Naiad，TimelyDataflow是它的开源实现。该论文促进了后续的流图体系的设计与创新，从其调度框架设计中也可以看到TuGraph Analytics调度器的影子。
对图计算技术感兴趣的同学可以多做了解，也非常欢迎大家关注和参与论文图谱的开源项目：

• Awesome-Graphs：https://github.com/TuGraph-family/Awesome-Graphs
  
• OSGraph：https://github.com/TuGraph-family/OSGraph
  

提前感谢给项目点Star的小伙伴，接下来我们直接进入正文！
摘要

Naiad是一个可执行有环数据流的分布式数据并行体系，提供了高吞吐的批处置惩罚、低延迟的流处置惩罚，以及迭代和增量计算的能力。
1. 介绍

支持特性：

• 循环布局化，支持反向边（feedback）。
  
• 有状态的数据流节点，支持无需全局调和的生产消费能力。
  
• 节点收齐特定轮次/迭代的输入后的通知机制。
  

2. 及时数据流

数据流图可以包含嵌套的循环布局，时间戳用于区分数据是由哪个轮次/迭代产生的。
2.1 图布局

及时数据流图包含输入/输出节点，输入节点从外部的生产者接受消息序列，输出节点将消息序列发送到外部消费者。
外部的生产者为每个消息打标了一个轮次（epoch），当没有消息需要输入时，会主动通知输入节点。
生产者也可以关闭输入节点，表现输入节点将不会再收到任何消息。
输出节点的消息也会打标这个轮次，同样当没有消息需要输出时，也会通知外部消费者。
及时数据流图里可以包含嵌套的循环上下文（loop contexts）：

• 入口点（ingress vertex）：数据流图的边进入循环上下文必须颠末入口点，如I。
  
• 出口点（egress vertex）：数据流图的边脱离循环上下文必须颠末出口点，如E。
  
• 反馈点（feedback vertex）：循环上下文内必须包含反馈点，如F。
  

针对上图所表达的计算语义解释：

关键概念：逻辑时间戳（logical timestamp）：

• e：消息的轮次。
  
• k：循环嵌套的深度。
  
• c：向量，每层循环的迭代次数。
  

逻辑时间戳变革规则：

• 颠末入口点：c增长一个维度，初始化为0，表现循环开始。
  
• 颠末反馈点：c的最后一个维度+1，表现循环次数累计。
  
• 颠末出口点：c的最后一个维度提出，规复成与入口点一致。
  

逻辑时间戳大小比力，t1=(e1, )，t2=(e2, )：

• 条件1：整数比力，e1 < e2。
  
• 条件2：字符串比力，c1 + ... + cm < c1 + ... + cn。
  

2.2 节点计算

数据流的节点可以吸收、发送带逻辑时间戳的消息（message），以及通知（notification）。
每个节点v实现两个回调函数：

• v.OnRecieve(Edge e, Message m, Timestamp t)：吸收消息。
  
• v.OnNotify(Timestamp t)：吸收通知。
  

并可以调用体系提供的两个函数：

• this.SendBy(Edge e, Message m, Timestamp t)：发送消息。
  
• this.NotifyAt(Timestamp t)：发送通知。
  

对于数据流边e=(u, v)，u.SendBy将触发v.OnRecieve，u.NotifyAt将触发v.onNotify。
数据流体系包管v.OnNotify(t)肯定发生在v.OnRecieve(e, m, t')之后，其中t' < t，即包管处置惩罚完所有t之前的消息后再处置惩罚通知，以让节点具备机会清理t之前的工作状态。
这种机制包管了消息处置惩罚不会发生韶光回溯（backwards in time）。
如下示例代码描述了一个双出的数据流节点实现distinct、count算子的逻辑。

1. class DistinctCount<S,T> : Vertex<T>
2. {
3.     Dictionary<T, Dictionary<S,int>> counts;
4.     void OnRecv(Edge e, S msg, T time)
5.     {
6.         if (!counts.ContainsKey(time)) {
7.             counts[time] = new Dictionary<S,int>();
8.             this.NotifyAt(time);
9.         }
10.         if (!counts[time].ContainsKey(msg)) {
11.             counts[time][msg] = 0;
12.             this.SendBy(output1, msg, time);
13.         }
14.         counts[time][msg]++;
15.     }
16.     void OnNotify(T time)
17.     {
18.         foreach (var pair in counts[time])
19.         this.SendBy(output2, pair, time);
20.         counts.Remove(time);
21.     }
22. }

复制代码

2.3 实现及时数据流

数据流处置惩罚受限于未处置惩罚的事件（events：消息、通知）和数据流图的布局。
关键概念：pointstamp：

• u.SendBy(e, m, t)：天生pointstamp (t, e)。
  
• u.NotifyAt(t)：天生pointstamp (t, v)。
  

单线程调度器实现：

• 维护一个激活pointstamp（active pointstamp） 聚集，聚集大小至少为1。对于每个pointstamp，有两个计数器：
  
  
  
  • OC（occurrence count）：未完成的pointstamp数。
    
  • PC（precursor count）：上游激活的pointstamp数。
    
  
  
• 体系初始化时，为输入节点天生第一个pointstamp，其中t=e，OC=1，PC=0。当e完成后，继续天生t=e+1的pointstamp。
  
• 当激活pointstamp p时，初始化PC为上游所有激活的pointstamp数，并递增下游节点所有pointstamp的PC值。
  
• 当OC[p]=0时，从active聚集删除p，并递减下游节点所有pointstamp的PC值。
  
• 当PC[p]=0时，表现上游没有激活的pointstamp影响到p，则称p是frontier，调度器会把所有通知发送给frontier。
  

OC的计算规则为：

3. 分布式实现

• Naiad集群包含多个历程，每个历程包含多个worker，worker管理数据流节点的一个分区。
  
• worker之间通过本地的共享内存大概远程TCP连接互换消息。
  
• 历程遵循分布式进度追踪协议（Progress Tracking Protocol），用于调和通知的分发。
  

3.1 数据并行

• 逻辑数据流图：stages+connectors。
  
• connectors包含一个分区函数。
  
• 运行时逻辑数据流图被展开为物理数据流图，stage被更换为一组节点，connectors被更换为一组边。
  

3.2 Workers

• 分发消息优先于分发通知。
  
• 分发策略多样，如基于最早的pointstamp分发降低端到端延迟。
  
• worker使用共享队列举行通信。
  
• 如果分发的目标节点在同一个worker，那么SendBy会直接调用目标节点的OnRecieve。
  
• 如果存在环则需要逼迫进入队列，大概控制递归深度避免体系过载。
  

3.3 分布式进度追踪

• 每个worker维护各自的状态，通过广播OC举行状态共享。
  
• 优化手段：
  
  
  
  • 使用映射的pointstamp实现进度跟踪，以降低并发辩论和更新规模。
    
  • 更新广播前先辈行本地聚合。
    
  
  

3.4 错误容忍和可用性

• Checkpoint和Restore接口。
  

3.5 预防抖动

• 网络。
  
• 数据布局竞争。
  
• 垃圾接纳。
  

4. 使用Naiad写步伐

5. 性能评估

6. 现实应用

• 批量迭代图计算
  
• 批量迭代机器学习
  
• 流式无环计算
  
• 流式迭代图分析
  

7. 总结

Naiad通过答应步伐按需调和，支持了混淆的同步+异步计算。
                        本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面显着位置给出原文链接，否则作者保留追究法律责任的权利。               
                                    若本文对你有所资助，您的                                    关注                                和                                    保举                                是我分享知识的动力!                    
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4