Noria:高性能web应用程序的动态、部分状态数据流

论文地址：Noria:高性能web应用程序的动态、部分状态数据流Gjengset，Schwarzkopf等人，OSDI’18

我们已经看到了流数据流引擎，它维护状态并提供SQL接口，甚至事务（例如Apache Flink和dataartian的Flinkstreaming ledger）。这里的主要模型是数据流，SQL作为状态的接口被固定。本文的标题让我开始沿着这些思路思考，但是从最终用户的角度来看，Noria看起来和感觉更像一个数据库。SQL接口是主接口，而不是辅助接口，它在基表中维护关系数据（使用RocksDB作为存储引擎）。为了维护一组（半）物化视图，Noria智能地使用SQL接口下的数据流（即，数据流不作为最终用户编程模型公开）。Noria自己找出最有效的数据流来维护这些视图，以及如何在模式/查询集更改时更新数据流图。

Noria的主要用例是为具有高性能（低延迟）需求的高读取量web应用程序而设计的。现在的这些应用程序通常包括某种缓存层（例如memcached、Redis），以提高读取性能并减轻数据库负载。应用程序开发人员的大量工作可以用于维护这些缓存，也可以用于数据库中的非规范化和计算状态。

一般来说，开发人员必须在方便但缓慢的“自然”关系查询（例如，使用内联聚合）和以应用程序和部署复杂性为代价的性能提高（例如，由于缓存）之间做出选择。
Noria通过将数据保存在基表（大致上，核心持久数据）和维护派生视图（大致上，应用程序可能选择缓存的数据）来简化应用程序开发。从基表派生的任何计算信息都不在这些表中。程序员不需要担心显式的缓存管理/失效、计算和存储派生值以及保持这些值的一致性。诺里亚为他们做了这些。
在其核心，Noria运行一个连续但动态变化的数据流计算，它结合了持久存储、缓存和应用程序逻辑元素。对Noria的每次写入都通过当前查询的联合数据流图进行流式处理，并以增量方式更新缓存的、最终一致的内部状态和查询结果。
（这也让人想起CQRS，但这里的模式还是在数据存储中使用的）。

对Noria来说，仅仅维护最近的状态窗口是不够的，它需要存储所有的持久状态。所以状态爆炸是一个潜在的问题。这就是论文标题中的“部分有状态数据流”部分，因为Noria有一种机制，可以在内存中只保留记录的一个子集，并根据需要重新计算上游运算符（最终是基表）的任何缺失值。

目前的原型有一些局限性，但它也显示出了很大的希望：

在单个Amazon EC2 VM上为Lobsters web应用程序提供服务时，我们的原型的性能比默认的基于MySQL的后端强5倍，同时简化了应用程序。对于一个代表性的查询，我们的原型的性能比广泛使用的MySQL/memcached栈和商业数据库的物化视图高出2-10倍，它还将查询扩展到ec2vm集群上每秒数百万次的写操作和数千万次的读操作，优于最先进的数据流系统differential data flow。

最终用户视角
Noria程序看起来像SQL DDL，它包括基表的定义、在其他表达式中用作速记的内部视图以及应用程序以后可以查询的外部视图。通过参数化的SQL查询检索数据。可以使用SQL插入、更新和删除更新基表中的数据。Noria将这些更改应用于相应的基表并更新相关视图。

Noria还实现了MySQL二进制协议，因此使用针对MySQL数据库的准备语句的现有应用程序可以直接在Noria之上工作，而无需进行任何更改。

• 一致性模型的最终保证是，如果写操作停止，所有外部视图最终都会保存与直接针对基表数据执行查询相同的结果。“许多web应用程序都符合这个模型：它们接受缓存所带来的最终一致性，缓存使普通大小写的读取速度更快。”

• Noria的一个非常好的特性是它接受应用程序查询和模式随着时间而发展的事实。Noria计划对数据流图所需的更改，以支持更改并在不停机的情况下转换应用程序。

将基于MySQL的应用程序移植到Noria通常需要三个步骤：

• 将现有数据从数据库转储导入Noria，并将应用程序指向Noria MySQL适配器。您应该看到读查询的性能改进，特别是那些经常使用的查询。
• 创建MySQL应用程序当前手动实现的计算视图。
• 增量重写应用程序以依赖这些自然视图，更新写入路径，使应用程序本身不再手动更新视图和缓存。

在第三阶段，应用程序性能应该稳步提高，同时代码也会简化。

Noria的数据流
Noria创建了一个关系运算符的有向非循环数据流图，根上有基表，叶上有外部视图。
当应用程序写入到达时，Noria将其应用于持久基表，并将其作为更新注入数据流。操作员处理更新并向其子级发出派生更新；最终更新会到达并修改外部视图。更新是可以添加到下游状态、修改下游状态和从下游状态删除的增量。
连接是使用upquery实现的：来自有状态祖先的匹配记录请求。

一致性
为了提供最终一致性保证，Noria要求：

• 算子是对自身状态和祖先输入的确定函数；
• 更新和upquery之间没有竞争；
• 同一数据流路径上的更新不会重新排序；以及
• 解决了通过不同数据流路径独立到达多祖先操作符的相关更新之间的竞争。诺里亚通过要求这些运算符是可交换的来解决这个问题。“Noria支持的标准关系运算符具有此属性。”

在排序方面，每个操作符对其接收到的条目的所有更新和upquery请求进行完全排序，下游数据流确保所有来自该条目的更新和upquery响应都由按顺序排列的消费者。

upquery需要特别小心，因为upquery响应不会相互交换或与以前的更新进行交换。Noria通过确保在发生join-upquery时上游有状态运算符和join之间没有更新来处理这个问题：每个join-upquery的作用域都是由单个线程处理的运算符链。（其他链上的更新可以并行处理）。

状态
部分状态数据流模型允许操作员只维护其状态的一个子集。这种局部物化的概念以其在数据库中的物化视图而闻名，但对于数据流系统来说却是新颖的。部分状态减少了内存使用，允许收回很少使用的状态，并免除了运算符维护从不读取的状态的责任…Noria只要能够使用有效的索引查找服务于upquery，就会使状态部分化。如果Noria必须扫描上游运算符的完整状态以满足upquery，则Noria将禁用该运算符的部分状态。
部分状态操作符从空开始，逐渐地被upquery填充。
像缓存一样，在内存压力下可以收回条目。逐出通知沿更新数据流路径流动，指示某些状态项将不再被更新。如果以后需要从被逐出的状态读取，Noria将通过递归upquery重新计算它（如果需要，一直到基表）。



为了正确处理连接，一旦通过递归upquery填充了上游状态，一个特殊的join upquery将在单个操作符链中执行，并排除并发更新。

数据流转换
随着时间的推移对Noria程序的更改（例如，一组SQL查询表达式）是通过动态调整数据流来处理的。
Noria首先计划转换，尽可能重用现有表达式的运算符和状态。然后，它以增量方式将这些更改应用于数据流，并注意保持其正确性不变量。两个步骤完成后，应用程序可以使用新表和查询。
详情见论文第5节。

评估
Noria是45kloc的Rust，支持单服务器和集群使用。原型使用从production Lobsters web应用程序生成的后端工作负载进行评估。它与vanilla MySQL（MariaDB）、MySQL/memcached堆栈、商业数据库的物化视图和理想化的仅缓存部署（后者不提供任何持久性，但提供从内存提供所有读取时的性能估计）进行了比较。
下面是Noria在Lobsters方面与MariaDB的比较，在Lobsters方面“Noria既实现了良好的性能，又实现了自然、健壮的查询。”

Noria的空间开销大约是lobsters基础表大小的3倍。

其余的比较是通过单服务器设置和Lobsters子集完成的。对于读取繁重的工作负载，除了纯memcached之外，Noria以每秒100-200K个请求的速度优于其他所有系统。对于混合读写工作负载，除了（不切实际的）纯memcached解决方案外，Noria再次击败了所有其他解决方案。

关于Noria和DBToaster的有趣比较，请参见第8.2节。

与基于Naiad和95%读取Lobsters子集工作负载的差分数据流实现相比，Noria具有竞争力地扩展，并从4台机器部署开始显示优势。

为了实现真正的大规模，Noria可以在机器之间切分具有大状态的大型基表和运算符。“对数据流进行有效的重新硬装和分区以最小化网络传输是Noria未来的重要工作…”
那么让我们回到我们开始的问题，Noria是什么样的程序呢？
用作者自己的话说：
Noria是一个web应用程序后端，它提供了高性能，同时允许简化应用程序逻辑。部分有状态的数据流对于实现这一目标至关重要：它允许快速读取，将Noria的内存占用限制为实际使用的状态，并允许对数据流进行实时更改。
Noria可在https://pdos.csail.mit.edu/Noria上获得