Giraph Unchained: Barrierless Asynchronous Parallel Execution in Pregel-like Graph Processing System

本文由渥太华大学研究人员Minyang Han、Khuzaima Daudjee发表的论文

• 本文提出了无屏障异步并行（BAP）方法，即一种新的减少信息过时和全局同步的计算模型。该方法基于BAP模型，克服了异步限制，但保留了多计算功能的图变异和算法。本文的GiraphUC利用BAP在开源的分布式图处理系统Giraph中建模，GiraphUC还具有大规模评估性能。对于同步系统的整体性能提升了五倍，异步系统的整体性能提升了86倍。在用户级别，BAP模型提供了“程序同步，异步执行”的范式，还提供了性能提升又不损耗可用或兼容性的功能。
• BAP模型通过使用分开本地屏障上的逻辑超步来避免全局屏障。与全局屏障不同，本地屏障不用全局协调，因为对于每个程序，它们都是本地的，而且只用做暂停点执行图突变以及确定是否一定需要全局屏障。逻辑超步与常规BSP超步相当，两个顶点只执行一次并且严格地增加值编号。与BSP超步不同的是逻辑超步不是全局协调，所以不同工作程序会执行不同数量的逻辑超步：第一个全局超步，工作程序1执行四个逻辑超步，而工作程序2和3分别执行两个和三个逻辑超步。
• 宽松的信息隔离和本地屏障结合使程序不用频繁阻塞和等待其他程序即可计算，因为BSP和AP模型在每个超步结束后的全局屏障会使用主机检查终止条件，所以可能造成程序终止。解决方法：使用两步终止检查。第一步在本地屏障处本地执行，而第二步在主节点全局执行。无论顶点是否活跃，任何待处理的信息都会重新激活顶点。所有程序到达全局屏障后，主机执行常规BSP终止检查：如果所有顶点都处于非活跃，则不会有更多未处理信息。
• 前面的方法有可取性，但它在程序决定阻塞全局屏障后却未考虑远程信息的到达，即新收到的远程信息在下一个全局超步之前不应该被处理。如果发生，程序就可能会长时间处于阻塞状态，信息无法顺利传递会导致所有工作程序都停止产生新信息。以单源最短路径算法（SSSP）为例，从一个活跃顶点开始，顶点之间发送的信息数量增加，而峰值会随时间减少。大部分时间会在全局屏障上阻塞，当我们允许程序通顺和处理新带有其他逻辑超步的信息，就可极大减少不必要阻塞并缩短总计算时间。
• 提出的改进方法：在现有的（BSP）全局屏障前插入一个轻量级全局阻碍，使程序一收到新信息后就解除阻塞。这个多余的全局屏障比（BSP）全局屏障更容易阻塞与取消阻塞。此外，如果每个程序在等待阻塞前就传出所有信息，接收程序就会在阻塞前取消阻塞。当其中程序没有任何信息时，所有程序处于轻量级的全局屏障（并继续（BSP）全局屏障）。所以算法在整个全局超步只用一次计算就可完成。由于本地屏障要求算法以最少全局超步完成，还有最少通信和同步开销。因此，两步终止检查比使用由GraphLab异步提供的分布式共识算法更有效和可扩展性。
• 给定一个初值有效信息的信息存储库，保留旧信息，用新信息覆盖旧信息，BAP模型执行顶点需要来自所有邻点的所有信息的单阶段BSP算法，由于顶点有来自所有邻点的所有信息，所以也就知道了顶点v到u的旧信息m，并且被从v到u的新信息m’覆盖。因为每个顶点都需来自其所有边缘的邻点信息，还必须向每个外围邻点发送一条信息，所以就说明顶点包含邻点的最新信息，也可安全覆盖旧信息。首次发送信息时，算法通过在第一个逻辑上的超步后增加全局屏障实现BAP模型。
• 多计算阶段算法是由多任务组成的计算，每个任务都有不同的计算逻辑，所以计算阶段需要全局协调。如在DMST中，顶点在增加和删除边的阶段后找到最小权重边缘。BAP模型必须使用全局屏障分隔不同计算阶段。如果每个信息都在API处用布尔值标记和两个信息存储，则BAP模型可以支持BSP算法多计算阶段。对于此类算法[1]，由于BAP分开了计算阶段与全局屏障分开，它从BSP模型继承了此属性。对于两个信息存储，我们使用一个存储（MSC）保留当前阶段和其他存储的信息（MSN）来保存下一阶段的信息。当一个新计算阶段发生，前一个MSN阶段成为当前阶段MSC，而新阶段MSN为空。我们使用布尔值表示是否当前阶段发送的信息将在下一个计算阶段处理。由于所有信息均已标记使用布尔值，我们可确定哪个储存库（MSC或MSN）将存储收到的信息。因此，涵盖了所有三种情况[2]，此外，为了知道何时使MSN变成新MSC，则需要知道何时有新阶段开始。在BAP中，一个阶段的开始是一个全局超步的开始，而通过检查是否还有本地或远程信息可用于当前阶段来确定结束阶段，忽略下一阶段信息。BAP模型还有效地支持多阶段算法同时保留了BSP开发接口。
• 为了支持多线程，每个工作程序都分配了多图分区。在每个超步中，工作程序会把可用的计算线程与未计算分区进行配对。超步之间，程序使用单线程以解决突变的串行任务并阻塞全局屏障。每个工作程序维护自己的信息存储区以容纳所有传入信息。每个计算线程具有信息缓冲区高速缓存，用于批处理所有传出信息。在缓存已满或已计算分区后，信息将刷新到本地信息存储或发送到网络。为了实施BSP，工作程序维护两个信息分别存储用于保留先前和当前超步中的信息，存储器会被循环，以便存储器持有当前超步的信息只在下一个超步读取。最后，由主机使用ApacheZooKeeper协调全局屏障。
• 实现Giraph异步是实现GiraphUC的第一步。Giraph异步通过使用单个信息存储提供宽松的信息隔离，其中包含来自先前和当前的超步。对于GiraphUC，我们允许外发本地信息跳过该信息缓冲区高速缓存以最小化陈旧性，但继续批处理外发远程信息以提高网络性能。计算顶点时，到达的信息从信息存储中删除该顶点，而在下一步（逻辑）超步中看到到达的信息。异步Giraph增加了本地屏障用于实施GiraphUC，在终止检查的第一步，程序检查他们的信息存储库是否为空，如果信息被覆盖而不是被删除，则信息会被重写。在第二步中，基于每个程序记录的统计信息ZooKeeper，主机检查是否所有顶点处于非活跃状态以及未处理信息数为零。每个工作程序都有一个字节计数器，该字节计数器随着远程信息增加，并在每个全局（而非逻辑）超步开始时重置。每个程序在阻塞全局屏障之前使用ZooKeeper记录计数器值。通过总结程序计数器，主机可正确地判断是否存在未处理的信息。最后，主机通过ZooKeeper协调了轻量级全局屏障。
• GiraphUC完全支持图突变，突变请求以异步信息的形式发送给拥有被修改的顶点或边的程序，突变请求通过程序得到了缓冲区。在GiraphUC中，顶点被单独一个分区拥有，而一条边仅属于其源顶点。因此，顶点和边突变都交给一个程序的本地操作，当没有计算线程在执行，也可在本地屏障得到解决。最后，因为信息在接收者的程序信息存储区缓冲，所以会保留新顶点的信息。
• 为避免网络开销，在Giraph中发送的信息与目标分区ID一起，接收者会确定每条信息的目的图分区。所以可将布尔值编码到整数分区ID：当前阶段信息有积极分区ID，而下一阶段分区ID消极。标志ID表示信息存储是MSC还是MSN，以及信息应放入何处。
  Giraph异步使用相同的布尔标记技术支持多阶段算法。但是，由于Giraph无法推断计算阶段的变化，一个无参数通知必须在master.compute（）中增加，通常是管理阶段传递逻辑或在顶点计算功能。在这种情况下，主机在下一个超步开始之前通知所有程序。这可使程序可辨别阶段，并知道何时交换其信息存储。
  Giraph基于BSP模型，因此聚合器默认情况下会阻塞。在全局屏障后才获得聚合器值。为避免全局屏障，GiraphUC支持不需要全局协调的聚合器。在GiraphUC的工作无需更改，因为每个程序都可使用本地聚合器来追踪活跃顶点的数量，将值汇总到本地每个逻辑超步，并在出现全局屏障时将本地聚合器值阻塞为零。
  GiraphUC容错是使用Giraph现有的检查点和故障恢复机制。与Giraph中一样，在检查点期间对所有顶点、边缘和信息存储区进行序列化，在恢复期间对它们进行反序列化。对于具有多计算的算法阶段，可在分隔计算阶段的全局屏障处执行检查点。对于更精细的检查点，或在带有单个计算阶段算法的情况下，以固定的时间间隔执行检查点。在每个时间间隔后，程序为启用同步检查点的全局屏障会独立地指定下一个本地屏障。

SSSP，WCC和PageR的相关内容以及实验结论不再赘述

提示：
[1]此类算法，信息有三种：
（1）信息在k-1阶段发送，而在k阶段处理;
（2）信息在k阶段发送，也在k阶段处理；
（3）信息在k阶段发送，在k+1阶段处理；
在其他情况下，由于BSP的属性而不可能在阶段m发送信息而在阶段n处理（（n-m）>1），任何在一个超步中发送的信息仅在下一个超步可见，因此信息不会在下一个超步中处理了。如果（n-m）>1，则阶段n和m大于相距一个超步，因此n无法看到m发送的信息。
[2]三种情况：（1）信息为在阶段k-1中被放置在MSN中，在阶段k中变为MSC，因此在正确的状态下该信息可见；（2）信息放置在阶段k的MSC中，其中在阶段k中立即可见；（3）信息放置在阶段k的MSN中，在k+1阶段将成为MSC。