CMU技术分享

Noria Fast Materialized Views for Fast Websites

这个在monringpaper有提到过，最近又在cmu有techtalk

避免不了解，先看一下文档预习一下概念

morning paper链接

看不懂有中文翻译

代码这里 https://github.com/mit-pdos/noria-mysql

https://github.com/mit-pdos/noria/

转自极客时间-左耳听风-《高效学习》系列整理

如何学习和阅读代码

读书还是读代码？

关于书/文档和代码的关系：

• 代码：What、How & Details；
• 书/文档：What、How & Why；

代码是具体的实现，但是并不能告诉你为什么？书和文档是人对人说的话，代码是人对机器说的话：

1. 如果想知道为什么要这么搞，应该去看书、看文档：特别当我们想了解一种思想、一种方法、一种原理、一种经验时，书和文档是最佳的方式、更有效率一些；
2. 如果想知道是怎么实现的，实现的细节，应该去看代码：对于具体的实现，比如：某协程的实现、某模块的性能、某个算法的实现，这时候最好的方式就是去读代码；

至于从代码中收获大还是从书中收获大，不同的场景、不同的目的下，会有不同的答案，我个人对这部分的想法是：

1. 工作的前几年，更多的时候应该关注代码、关注细节的实现、多写代码（当然不是说完全不看书，书是必须要看的，特别是当有了相关实战经验之后再去看书看，效果会更好），这个阶段，Google、Stack Overflow、Github 将会是最好的学习渠道，如果在过程中，还能获得一些技术影响力，那将再好不过了；
2. 有一定经验之后，这时候需要更多的【理性认识】，在这个阶段，我们的想法不再是实现某个功能，可能是想做出更牛逼的东西来，这时候应该多读那些大牛的书、与大牛交流、关注国际顶级会议的论文，应该让自己往技术 leader 这个方向发展。

如何阅读源代码

关于如何阅读源代码，耗子叔分享了一些干货，我这里简单总结一下

首先是阅读代码之前，最好先有以下了解：

1. 基础知识：相关的语言和基础技术的知识；
2. 软件功能：需要知道这个软件是做什么的、有哪些特性、哪些配置项，最好能够读一遍用户手册，然后让软件跑起来，自己先用一下感受一下；
3. 相关文档：读一下相关的内部文档；
4. 代码的组织结构：先简单看下源码的组织结构。

接下来，就是详细地看代码的实现，这里耗子叔分享了一个源代码阅读的经验：

1. 接口抽象定义：任何代码都会有很多接口或抽象定义，其描述了代码需要处理的数据结构或者业务实体，以及它们之间的关系，理清楚这些关系是非常重要的；

2. 模块粘合层：我们的代码有很多都是用来粘合代码的，比如中间件（middleware）、Promises 模式、回调（Callback）、代理委托、依赖注入等。这些代码模块间的粘合技术是非常重要的，因为它们会把本来平铺直述的代码给分裂开来，让你不容易看明白它们的关系；

3. 业务流程：这是代码运行的过程。一开始，我们不要进入细节，但需要在高层搞清楚整个业务的流程是什么样的，在这个流程中，数据是怎么被传递和处理的。一般来说，我们需要画程序流程图或者时序处理图；

4. 具体实现

   ：了解上述的三个方面的内容，相信你对整个代码的框架和逻辑已经有了总体认识。这个时候，你就可以深入细节，开始阅读具体实现的代码了。对于代码的具体实现，一般来说，你需要知道下面一些事实，这样有助于你在阅读代码时找到重点。

   • 代码逻辑：代码有两种逻辑，一种是业务逻辑，这种逻辑是真正的业务处理逻辑；另一种是控制逻辑，这种逻辑只是用控制程序流转的，不是业务逻辑。比如：flag 之类的控制变量，多线程处理的代码，异步控制的代码，远程通讯的代码，对象序列化反序列化的代码等。这两种逻辑你要分开，很多代码之所以混乱就是把这两种逻辑混在一起了；
   • 出错处理：根据 2：8 原则，20% 的代码是正常的逻辑，80% 的代码是在处理各种错误，所以，你在读代码的时候，完全可以把处理错误的代码全部删除掉，这样就会留下比较干净和简单的正常逻辑的代码。排除干扰因素，可以更高效地读代码；
   • 数据处理：只要你认真观察，就会发现，我们好多代码就是在那里倒腾数据。比如 DAO、DTO，比如 JSON、XML，这些代码冗长无聊，不是主要逻辑，可以不理；
   • 重要的算法：一般来说，我们的代码里会有很多重要的算法，我说的并不一定是什么排序或是搜索算法，可能会是一些其它的核心算法，比如一些索引表的算法，全局唯一 ID 的算法，信息推荐的算法、统计算法、通读算法（如 Gossip）等。这些比较核心的算法可能会非常难读，但它们往往是最有技术含量的部分；
   • 底层交互：有一些代码是和底层系统的交互，一般来说是和操作系统或是 JVM 的交互。因此，读这些代码通常需要一定的底层技术知识，不然，很难读懂；

5. 运行时调试：很多时候，代码只有运行起来了，才能知道具体发生了什么事，所以，我们让代码运行进来，然后用日志也好，debug 设置断点跟踪也好。实际看一下代码的运行过程，是了解代码的一种很好的方式。

总结一下，阅读代码的方法如下。

• 一般采用自顶向下，从总体到细节的【剥洋葱皮】的读法；
• 画图是必要的，程序流程图，调用时序图，模块组织图；
• 代码逻辑归一下类，排除杂音，主要逻辑才会更清楚；
• debug 跟踪一下代码是了解代码在执行中发生了什么的最好方式。

另外这里也有个见解 https://www.codedump.info/post/20200605-how-to-read-code-v2020/ 兼听则明

---

看到这里或许你有建议或者疑问或者指出我的错误，请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要！

觉得写的不错可以点开扫码赞助几毛

准备把blog阅读和paper阅读都归一，而不是看一篇翻译一篇，效率太低了

后面写博客按照 paper review，blog review，cppcon review之类的集合形式来写，不一篇一片写了。太水了

准备把blog阅读和paper阅读都归一，而不是看一篇翻译一篇，效率太低了

后面写博客按照 paper review，blog review，cppcon review之类的集合形式来写，不一篇一片写了。太水了

1. 支持反馈的有结构循环
2. 有状态的数据流节点，能够在没有全局协调(global coordination)的情况下消费和生产记录（record）
3. 当达到某个循环次数或者遍历完所有数据之后通知所有节点

Timely Dataflow

Timely dataflow基于有向图：

• 顶点是有状态的，可沿着边发送/接收有逻辑时间的消息
• 图可包含环，且可嵌套，时间戳反映不同的输入时期（epoch）和循环迭代

生成的模型：

• 支持并发执行不同时期和循环迭代的数据
• 当所有的消息都被传输后（根据某个时间戳），顶点支持显式的通知

2.1. 图结构

2.1.1. 图结构的顶点

• 输入顶点：接收外部生产者的消息

  • 输入的消息会标记epoch，外部生产者可通知顶点该epoch不会有消息进来，且当所有epoch消息都不会进来时可以“关闭”顶点

• 输出顶点：将消息输出给外部的消费者

  • 输出的消息也会标记epoch，顶点可通知外部消费者该epoch的消息不会出来，且当所有epoch消息都不会出来时可以“关闭”顶点

2.1.2. 嵌套循环上下文

包含3个系统相关的顶点

• 入口顶点：进入该上下文必须经过该顶点
• 出口顶点：离开该上下文必须经过该顶点
• 反馈顶点：每个循环至少有1个，它不会嵌套在任何内部循环上下文中

2.1.3. 时间戳

消息时间戳t

可定义为下面2个元素的元组：

• e* ∈ℕ：Epoch号

c*⃗ =⟨*c*1,*c*2,…,*c*k*⟩∈ℕ*k* ：Loop counter向量，每个维度对应对应循环上下文的循环次数，可用于区分循环上下文，且可跟踪循环进度

上述3个节点处理时间戳的结果如下（对于第k个循环上下文）：

顶点	输入时间戳	输出时间戳
入口顶点	(e,⟨c1,c2,…,c**k⟩)	(e,⟨c1,c2,…,c**k,0⟩)
出口顶点	(e,⟨c1,c2,…,ck*,*ck+1⟩)	(e,⟨c1,c2,…,c**k⟩)
反馈顶点	(e,⟨c1,c2,…,c**k⟩)	(e,⟨c1,c2,…,c**k+1⟩)

时间戳的比较：当且仅当e1≤e2

且c1→≤c2→（根据字典序比较）时，t1≤t2

2.2. 顶点计算

每个顶点v实现下面2个回调：

• v.OnRecv(edge, msg, timestamp)：收到来自edge的消息
• v.OnNotify(timestamp)：没有更多<= timestamp的消息到来

回调可被自定义（重写）

回调上下文中，可能会调用下面2个系统提供的方法：

• this.SendBy(edge, msg, timestamp)：向一条边发送消息
• this.NotifyAt(timestamp)：在timestamp时候，进行调用通知

调用关系是：

• u.SendBy(e, m, t) -> v.OnRecv(e, m, t) ，e为u->v的边
• v.NotifyAt(t) -> v.OnNotify(t)
• 每个顶点的回调都会被排队，但必须保证：
  • 当t' <= t时，v.OnNotify(t)发生在v.OnRecv(e, m, t')后，因为前者是作为t之前所有消息都已收到，不会再来的信号。重写的回调也得满足这个要求。

2.3. 达成Timely Dataflow

本节主要讲系统如何推断具有给定时间戳的未来消息的不可能性（即推断“通知”的安全性），并提供单线程的实现。

2.3.1. Pointstamp

任何时刻，未来消息的时间戳受到当前未处理事件（消息和通知请求）以及图结构的限制：

• 消息只会沿边传输，且时间戳仅会被2.1.3.小节的三种顶点修改。
• 由于事件的发送不能产生时间回溯，因此可以计算事件产生的消息时间戳的下界。将这种算法应用到未处理事件上，则可判断顶点通知是否正确

这里定义Pointstamp，对应每个事件：(t∈Timestamp,l∈Edge*∪*Vertex)

• 对于v.SendBy(e, m, t)，对应的是(t, e)
• 对于v.NotifyAt(t)，对应的是(t, v)

一些结论和定义：

• 当且仅当满足下面条件时，(t1,l1)

could-result-in(t2,l2)：

• 存在一条路径ψ=⟨l1,…,l2⟩

，根据这条路径，时间戳ψ(t1)≤t2，左边表示t1

• 仅被路径上的3类节点修改的时间戳

Path Summary：l1

到l2的时间戳变化的函数

• 可以保证若两位置存在多条路径，它们的summary必然不一样，其中一条总会比另一台更早产生调整后的时间戳

• 可以找到最小的path summary，将路径记为ψ[l1,l2]

• • 因此，检测could-result-in，只需检测$\psil_1, l_2 \le t_2$即可

2.3.2. 单线程实现

调度器维护一组活跃的pointstamp，每个元素包含2个计数器：

• Occurrence count（OC）：未完成的事件发生个数
• Precursor count（PC）：could-result-in顺序下，前面的pointstamp个数

当顶点产生和撤销事件时，OC根据下面更新：

• v.SendBy(e,m,t)前，v.NotifyAt(t)前：OC[(t,e/v)] += 1
• v.OnRecv(e,m,t)后，v.OnNotify(t)后：OC[(t,e/v)] -= 1

当pointstamp活跃时，PC根据下面初始化：

• 置为已有could-result-in的活跃pointstamp个数
• 同时，增加当前pointstamp之后的pointstamp PC值

当pointstamp不活跃时：

• OC值为0，移除活跃pointstamp集合

• 递减之后的pointstamp PC值

  当PC值为0，则该pointstamp为frontier，调度器可将任何通知发给它

系统初始化时，在下面位置初始化一个pointstamp：

• 位置为每个输入顶点
• 时间戳为：第一个epoch，以及全为0的loop count
• OC为1，PC为0

当输入节点的输入完毕时：

• 若epoch e完毕，则创建e+1的pointstamp，删除原有的pointstamp
• 通知下游epoch e的消息已经输入完毕
• 若输入节点关闭时，删除当前位置的所有pointstamp，允许输入到下游的事件最终可从计算中消失

有个rust实现 https://github.com/TimelyDataflow/timely-dataflow

这里有个faster的rust封装，目的是让timely-dataflow做存储后端，延迟提升很好 论文 代码

RDD 擅长什么

• 擅长

• • 对数据集中所有元素做同样操作的批处理应用
  • 高效地记住每个转换（lineage图中的每一步）
  • 不需要备份大量的数据就可以恢复丢失的分区

• 不擅长

• • 需要对共享的状态做异步细粒度更新(fine-grained)的应用

Timely Dataflow

• 一个有向图，有状态节点通过有向边发送和接受带有逻辑时间戳（logically timestamped）的消息
• 由于每个loop都会有自己的timestamp，利用这个可以区分数据在哪个epoch和loop iterations，也支持嵌套循环
• 支持在不同epochs和iterations间的并发执行
• 当一个特定的timestamp的所有messages交付之后，向节点发出通知

如何实现低延迟

1. 采用消息机制作为编程模型

v.SENDBY(edge, message, time)

v.ONRECV(edge, message, time)

v.NOTIFYAT(time)

v.ONNOTIFY(time)

\2. 异步细粒度执行

\3. 分布式进度追踪协议

---

参考

• https://keys961.github.io/2019/04/19/%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB-Naiad/

---

看到这里或许你有建议或者疑问或者指出我的错误，请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要！

觉得写的不错可以点开扫码赞助几毛