SOSP '19 | Lineage Stash: Fault Tolerance Off the Critical Path

[PeterSH6]

PDF: https://cs-people.bu.edu/liagos/material/sosp19.pdf Talk: https://www.youtube.com/watch?v=ANSxtucbMzg

[PeterSH6]

使用Causal Logging来保存Lineage

• analyze the nondeterministic events that must be logged in data processing applications.
• A deterministic computation can be safely re-executed many times, but computations with side effects on the outside world often require exactly-once semantics, since the outside world in general cannot be rolled back.
• Guideline: The lineage stash is a form of rollback recovery [18], in which information is recorded during execution to minimize the amount of work that must be redone after a failure. Informally, the lineage stash guarantees that if a process fails, then any messages that it received since its last checkpoint will be replayed in the same order.
• What information they log: 1)In the allreduce case, the message ordering is deterministic, so it need not be recorded at all. 2) Save pointer of the data, record lineage not data
• How should we log information: instead of storing the lineage reliably before the task is executed, we forward the lineage of each of the task’s inputs with the task invocation. Only the nondeterministic events must be reliably recorded for recovery correctness. Thus, in deterministic applications, the lineage need not be forwarded during normal operation because it can be deterministically recreated after a failure. Nondeterministic → forward

这篇文章主要讨论两种Dataflow的情况：一种是Deterministic，一个节点只会收到一个源发来的，因此计算顺序是可以通过Lineage重现的；另一种是NonDeterministic，一个节点会收到多个发来的信息，这个时候A，B，C均向D发送信息，D收到的消息运行的动作顺序是不确定的， 恢复的时候需要恢复这个顺序。

对于Deterministic来说，只需要在local store里面存自己的和下游的Lineage和data pointer就可以了。一个节点的fail完全可以由上游节点恢复。在机器学习训练任务中，应该是deterministic的，但是每个op都需要保存，所以需要保存所有的gradient。最后实际上就是apply上去，虽然很快，但是要存的东西很多。

对于Nondeterministic的情况，由下图可以看到，C是Nondeterministic的节点，他会存自己的lineage和下游节点的Lineage（用于恢复下游节点），同时他需要把这所有的信息forward给下游节点，防止C自己挂了的时候，没法恢复这些顺序。这些顺序没法从上游节点恢复