晨间论文

  下载本文的 PDF 版本 PDF

晨间论文

SQL 保护伞下的回归

统一服务和分析数据；使用数据库进行分布式机器学习

Adrian Colyer

今年我有幸亲身参加了 VLDB 2019 大会。会议上挤满了有趣的人、海报和演示文稿，我遇到的每个人都让我感到非常受欢迎。如果您是一位从业者，想知道学术会议是否适合您，我强烈推荐它。我从会议中众多优秀的候选论文中选择了两篇用于本期。

Procella 是谷歌长期以来推出的最新数据处理系统。它的独特之处在于它是一个单一的存储，在一个屋檐下处理报告、嵌入式统计、时间序列和即席分析工作负载。它以 SQL 为顶层，云原生为底层，每天处理数十亿次查询，数据量达数十 PB。

然而，Procella 今天尚未处理一个大数据用例，那就是机器学习。但在 Jankov 等人的论文《RDBMS 上的声明式递归计算...或者，为什么你应该使用数据库进行分布式机器学习》中，他们论证了数据库是处理最苛刻的分布式机器学习工作负载的理想场所。

一切是否会再次在 SQL 保护伞下重新统一？

Procella：在 YouTube 统一服务和分析数据

Chattopadhyay 等人，VLDB’19

学术论文通常不会配乐，但如果要配乐，皇后乐队的《I want it all (and I want it now…)》的合唱部分似乎很合适。扎根于支持谷歌 YouTube 业务的主要用例，我们在这里看到的很可能就是谷歌数据处理的未来。好吧，我说的是未来，但“Procella 现已投入生产多年。如今，它已部署在十几个数据中心，每天处理数千亿次查询，数据量达数十 PB……” 所以也许我们看到的是我们其余人的数据处理的未来！

谷歌已经拥有 Dremel、Mesa、Photon、F1、PowerDrill 和 Spanner，那么他们为什么还需要另一个数据处理系统？因为他们有太多的数据处理系统了！;)

大型组织……正在应对爆炸式增长的数据量以及对数据驱动应用程序日益增长的需求。 广义上讲，这些可以分为：报告和仪表板、页面中的嵌入式统计信息、时间序列监控和即席分析。 通常，组织为每个用例构建专门的基础设施。 然而，这会造成数据和处理的孤岛，并导致复杂、昂贵且更难维护的基础设施。

当每个用例都由专用的后端驱动时，对更好性能、改进可扩展性和效率等的投资就会被分散。 鉴于 YouTube 不断增长的规模，其中一些后端系统开始吱吱作响。 此外，在不同系统之间移动数据以支持不同的用例可能会导致棘手的 ETL 管道。

Procella 的远大目标是“实现解决所有四个用例所需的功能超集……在单一产品中实现高规模和高性能”（又名 HTAP：混合事务/分析处理）。 这在很多方面都很困难，包括需要在用例之间进行权衡的吞吐量和延迟。

用例

报告和仪表板用例（例如，了解 YouTube 视频效果）每秒驱动数万个预定义的（预先知道的）查询，这些查询需要在数十毫秒的延迟内提供服务。 每个被查询的数据源每天可以增加数千亿行新数据。 哦，除了低延迟之外，“我们还需要访问新鲜数据。”

仅对于 YouTube Analytics 应用程序，我们看到的指标就像这样，99% 分位数的延迟为 412 毫秒

procella

嵌入式统计信息用例包括页面中包含的各种计数器，例如观看次数、点赞数和订阅数。 这里的查询量达到每天数千亿次，延迟要求为毫秒级（Procella 在这里实现了 99% 分位数延迟为 3.3 毫秒）。

时间序列监控工作负载与仪表板具有相似的属性（相对简单的预定义查询，但需要新鲜数据）。 这里还需要额外的查询功能，例如近似值和专用时间序列函数。

即席分析用例支持内部团队执行复杂的即席分析，以了解使用趋势并确定如何改进产品。 这些查询量相对较低，延迟要求适中，但它们可能很复杂，并且查询模式高度不可预测。

Procella 系统概述

本文涵盖了大量领域。 在这篇评述中，我们将了解一些高层架构原则，然后我将挑选与 Procella 如何实现其性能、延迟和数据新鲜度目标相关的细节。

对于其客户端而言，Procella 是一个 SQL 查询引擎（SQL-all-the-things）。 在底层，它是一个复杂的分布式系统，建立在云原生系统的原则之上

总体架构如下

总而言之，这些原则使 Procella 能够扩展，但要在支持“几乎完整的标准 SQL 实现，包括复杂的多阶段连接、分析函数和集合操作，以及一些有用的扩展，例如近似聚合、处理复杂的嵌套和重复模式、用户定义的函数等等”的同时实现所需的性能水平，则是另一项挑战。 现在让我们看一下有助于使 Procella 快速的一些因素。

使 Procella 快速

缓存所有内容

Procella 通过将存储（在 Colossus 中）与计算（在 Borg 上）分离来实现高可扩展性和效率。 然而，由于每次读取甚至打开文件都涉及多个 RPC，因此这会带来巨大的开销。 Procella 采用多级缓存来缓解这种网络延迟。

不过，关于一旦关闭就不可变的文件的好处是，您不必担心缓存失效。

Procella 积极缓存元数据、列式文件头和列式数据（使用新开发的数据格式 Artus，该格式使数据在磁盘和内存中具有相同的表示形式）。 如果有足够的内存，Procella 基本上可以成为内存数据库。 对于他们的报告实例，只有大约 2% 的数据可以放入内存，但系统仍然实现了 99%+ 的文件句柄缓存命中率和 90% 的数据缓存命中率。

实现如此高命中率的秘诀之一是亲和性调度。 指向数据服务器和元数据服务器的请求被路由，使得对相同数据/元数据的操作以高概率转到同一服务器。 存储层的另一个特性是所有数据都可以从任何地方访问，这意味着亲和性调度是一种优化，即使请求最终因某种原因被路由到其他地方，仍然可以提供服务。

高度优化和预计算数据格式

由于 Procella 旨在覆盖 [即席分析工作负载中典型的大型扫描] 和其他需要快速查找和范围扫描的用例，我们构建了一种新的列式文件格式，称为 Artus，它旨在实现查找和扫描的高性能。

我们真的需要一篇专门介绍 Artus 本身的论文，但这里有一些亮点。

Artus 使用多种方法来编码数据：字典和索引器类型、游程编码、增量编码等，以实现接近强通用字符串压缩（例如 ZSTD）2 倍的压缩率，同时仍然能够直接对数据进行操作。 每种编码都有估计方法，用于估计在提供的数据上它有多小和多快。（我的重点）。

在四种典型的 YouTube Analytics 查询模式下评估，以下是 Artus 与 Google BigQuery 的列式存储格式 Capacitor 的性能和内存消耗数据。


自适应和编译

高性能评估对于低延迟查询至关重要。 如今，许多现代分析系统通过在查询时使用 LLVM 将执行计划编译为本机代码来实现这一点。 然而，Procella 需要服务于分析和高 QPS 服务用例，对于后者，编译时间通常会成为瓶颈。 Procella 评估引擎 Superluminal 采用了不同的方法……

Superluminal 广泛使用 C++ 模板元编程，并以本机方式对底层数据编码进行操作。 没有物化中间表示。

然后，查询优化器结合了静态和动态（自适应）查询优化技术。 基于规则的优化器应用标准逻辑重写。 然后，当查询运行时，Procella 基于查询中使用的实际数据的样本收集统计信息，并使用这些信息来确定下一步该做什么。

自适应技术实现了强大的优化，这些优化很难通过传统的基于成本的优化器来实现，同时大大简化了我们的系统，因为我们不必收集和维护数据统计信息（尤其是在以非常高的速率摄取数据时），而且我们不必构建复杂的估计模型，这些模型可能仅对有限的查询子集有用。

聚合、连接和排序策略都在运行时根据查询执行期间的持续学习进行调整。 对于具有严格低延迟目标的查询，可以预先完全定义执行策略并关闭自适应优化器。

尽可能少地工作，并在最佳位置完成工作

除了尽可能将计算下推到叶节点之外，Procella 还具有多种连接策略，以使分布式连接尽可能高效。 我没有足够的空间在这里描述所有这些策略，但您可以在论文的 §3.5 中找到一个很好的简短摘要。

对于繁重的聚合，Procella 在最终聚合的输入端添加了中间聚合运算符，以防止其成为瓶颈。

还有更多！

在完整论文中还有很多我没有涵盖的额外信息。 如果您对此主题感兴趣，非常值得一读……

RDBMS 上的声明式递归计算……或者，为什么你应该使用数据库进行分布式机器学习

Jankov 等人，VLDB’19

如果您考虑像 Procella 这样的系统，它在云原生架构之上结合了事务性和分析性工作负载，用于流式处理的 SQL 扩展、基于数据流的物化视图（例如，参见 Naiad、Noria、Multiverses，并查看 Materialize 在这里所做的事情）、使用 SQL 接口查询半结构化和非结构化数据的能力等等，那么一个统一的大规模数据平台的蓝图开始浮现，该平台以 SQL 查询引擎为顶层，在一个一站式商店中解决组织的所有数据需求。 只是列表中遗漏了一个明显的方面：处理所有机器学习用例。

在关系数据库中进行机器学习已经实现过，最值得注意的是 MADlib 的形式，它在我在 Pivotal 工作期间被 集成到 Greenplum 中。 Apache MADLib 项目仍在蓬勃发展，最近（2019 年 7 月）发布的 1.16 版本甚至包括对深度学习的一些支持。

为了实现组织所有数据需求一站式商店的愿景，我们需要能够处理最苛刻的大规模机器学习任务——那些需要分布式学习的任务。 今天选择的论文副标题为“为什么你应该使用数据库进行分布式机器学习”，旨在填补这一空白。 这将是对 TensorFlow 等当前命令式高级 DSL 深度学习方法的重大背离，但与此同时，它也提供了一些引人注目的优势。 即使在深度学习中，所有道路最终都会回到 SQL 吗？

我们考虑如何对现代关系数据库管理系统 (RDBMS) 进行非常小的改动，使其适用于分布式学习计算…… 我们还表明，使用 RDBMS 作为机器学习平台具有关键优势。

为什么会有人想这样做？？？

为什么会有人想在 RDBMS 中运行深度学习计算？？

一方面，因为当前深度学习的分布式方法在仅使用基于数据并行的方法（一个模型，拆分数据）时只能走这么远，并且正在转向模型并行以达到下一个级别（跨多个节点拆分模型本身）。

大多数现有大数据 ML 系统（例如 TensorFlow 和 Petuum）青睐的分布式键值存储（称为参数服务器）使得构建模型并行计算变得困难，即使是“手动”构建也是如此。

另一方面，通过切换到关系计算模型，模型并行看起来与数据并行非常相似，我们可以利用经过高度优化的分布式数据库引擎。 SQL 提供了一个声明式编程接口，在该接口之下，系统本身可以根据数据大小和统计信息、布局、计算硬件等找出最有效的执行计划。

小心你所要求的（物化）

如果我们假设 RDBMS “轻微增强”以处理 matrix 和 vector 数据类型，例如 SimSQL，那么我们实际上离今天能够用 SQL 表达机器学习计算不远了。

给定一个权重表 W，用于存储权重矩阵的块，一个激活表 A，用于存储激活值，以及一个 AEW 表，用于存储计算下一次迭代权重所需的值，那么我们可以用 SQL 表示具有八个隐藏层的前馈机器学习模型的迭代 i 的反向传播。

 W (ITER, LAYER, ROW, COL, MAT) A (ITER, LAYER, COL, ACT) AEW (LAYER, ROW, COL, ACT, ERR, MAT)

除了这看起来不太漂亮（参见 MADLib 中的 MLP）之外，对于 SQL 来说也相当命令式（注意 for 循环）。 由此引起的问题是用于物化迭代之间传递的状态的 AEW 表：该状态可能会非常快地增长。 我们希望摆脱命令式的 for 循环，以便我们可以在声明式查询表达式背后实现流水线。

递归 SQL 扩展

经典 SQL 通过称为“公共表表达式”的东西，已经具有递归支持。 在这里，我们想要一些与之略有不同的东西，本质上是表达对任意大表序列的延迟物化能力。

作者介绍了通过数组式索引访问的表的多个版本的概念，使用帕斯卡三角形作为示例。

给定一个基表，例如

 CREATE TABLE pascalsTri[0][0] (val) AS  SELECT val FROM VALUES (1);

然后我们可以递归地定义其他版本，例如，对于帕斯卡三角形的对角线 (j = i)

 CREATE TABLE pascalsTri[i:1...][i] (val) AS  SELECT * FROM pascalsTri[i-1][i-1];

对于 j = 0 的情况

 CREATE TABLE pascalsTri[i:1...][0] (val) AS  SELECT * FROM pascalsTri[i-1][0];

以及其他所有情况

 CREATE TABLE pascalsTri[i:2...][j:1...i-1] (val) AS  SELECT pt1.val + pt2.val AS val  FROM pascalsTri[i-1][j-1] AS pt1,    pascalsTri[i-1][j] AS pt2;

这样，稍后我们可以发出诸如 SELECT * FROM pascalsTri[56][23] 之类的查询，系统将展开递归以将所需的计算表示为单个关系代数语句。

EXECUTE 关键字允许同时查询表的多个版本。 例如

 EXECUTE (  FOR j in 0...50:   SELECT * FROM pascalsTri[50][j]);

我们还可以请求使用 MATERIALIZE 关键字显式物化表（用于动态规划），并且我们可以使用 UNION 合并多个递归定义的表。

SQL 中的递归学习

借助这些新扩展，我们可以像这样定义前向传播计算（计算每层神经元的激活级别）

 -- First layer of activations CREATE TABLE A[i:0...][j:0] (COL, ACT) AS  SELECT DI.COL, DI.VAL  FROM DATA_INPUT AS DI; -- Propagating activations CREATE TABLE WI[i:0...][j:1...9] (COL, VAL) AS  SELECT W.COL, SUM(matmul(A.ACT, W.MAT))  FROM W[i][j] AS w, A[i][j-1] AS A  WHERE W.ROW = A.COL  GROUP BY W.COL; -- Subsequent activations CREATE TABLE A[i:0...][j:1...8] (COL,ACT) AS  SELECT WI.COL, relu(WI.VAL + B.VEC)  FROM WI[i][j] AS WI, B[i][j] AS B  WHERE WI.COL = B.COL; -- Prediction CREATE TABLE A[i:0...][j:9] (COL, ACT) AS  SELECT WI.COL, softmax(WI.VAL + B.VEC)  FROM WI[i][j] AS WI, B[i][j] AS B  WHERE WI.COL = B.COL;

反向传播可以用类似的方式表示

高效的执行计划

本文详细介绍了 RDBMS 如何有效地编译和执行 ML 工作负载的 SQL 规范所暗示的大型复杂计算。 在这里，我只简单介绍一下重点。

从查询中，我们可以展开递归以创建一个未优化的关系代数计划 (DAG)。 下一步是将该计划分解成若干部分，每个子计划称为帧。 显然，选择的分解方式可能会对最终的查询性能产生重大影响。 如果我们过于细粒度，我们可能会失去在帧内找到良好优化的机会（例如，最佳连接顺序）。 因此，帧具有最小尺寸。 下一个主要考虑因素是给定分解所需的帧间通信量。 对此的一个很好的近似值是引入的流水线中断器的数量。

当一个运算符的输出必须物化到磁盘或通过网络传输，而不是直接通过 CPU 缓存或在最坏的情况下通过 RAM 从运算符传输到运算符时，就会发生流水线中断。 诱导流水线中断是指在最佳物理计划中不存在，但由于切割而被强制执行的流水线中断。

即使弄清楚给定的切割是否会引入流水线中断也并非易事，但可以概率性地估计。 此成本会反馈到整体优化中，以找到最佳计划分解，作为众所周知的广义二次分配问题 (GQAP) 的一个实例。 关于 GQAP，众所周知的一件事是它是一个非常难的问题！ 您可能可以猜到接下来会发生什么……贪婪近似。

从一个源运算符开始，我们贪婪地将运算符添加到帧中，选择帧成本增加最小的运算符，直到帧大小超过最小阈值。 结果取决于您碰巧选择的初始源节点，但这可以通过为每个可能的起始操作运行一次贪婪算法来补救。

实验结果

评估比较了多层前馈神经网络 (FFNN)、Word2Vec 算法和 LDA 的分布式折叠吉布斯采样的分布式实现。 这些实现既需要 SQL，也需要一些用 C++ 编写的 UDF。 下表显示了与 TensorFlow 和 Spark 相比，具有代表性的行数。 当然，一旦构建了 UDF 库，它们就可以在各种计算中重复使用。

对于前馈神经网络，使用 GPU 的 TensorFlow 在较小的隐藏层中仍然明显更快，但无法扩展。 除此之外，RDBMS 胜出

对于 Word2Vec 和 LDA 计算，随着维度/主题数量的增加，加速非常显着（例如，对于 50,000 个主题的 LDA，为 8.5 分钟，而几乎为 5 小时）。

我们已经表明，与 TensorFlow 相比，基于 RDBMS 的模型并行 ML 计算可以很好地扩展，并且对于 Word2Vec 和 LDA，基于 RDMBS 的计算可能比 TensorFlow 更快。 然而，对于基于 GPU 的神经网络实现，RDBMS 比 TensorFlow 慢。 虽然这种差异的部分原因是我们在研究原型、高延迟 Java/Hadoop 系统之上实现了我们的想法，但缩小这种差距是未来工作的有吸引力的目标。

Adrian Colyer 是伦敦 Accel 的风险合伙人，他的工作是帮助在欧洲和以色列寻找和建立伟大的科技公司。 （如果您正在从事有趣的技术相关业务，他很乐意与您联系：您可以通过 [email protected] 与他联系。） 在加入 Accel 之前，他在技术岗位工作了 20 多年，包括在 Pivotal、VMware 和 SpringSource 担任 CTO。

版权所有 © 2019，所有者/作者所有。 出版权已授权给 。

经许可转载自 https://blog.acolyer.org

acmqueue

最初发表于 Queue vol. 17, no. 5—
在 数字图书馆 中评论本文




更多相关文章

Qian Li, Peter Kraft - 事务和无服务器天生一对
数据库支持的应用程序是无服务器计算令人兴奋的新领域。 通过紧密集成应用程序执行和数据管理，事务性无服务器平台能够实现许多在现有无服务器平台或基于服务器的部署中无法实现的新功能。


Pat Helland - 任何其他名称的身份
新兴的系统和协议既收紧又放宽了我们对身份的概念，这很好！ 它们使完成工作变得更容易。 REST、IoT、大数据和机器学习都围绕着有意保持灵活有时甚至模糊的身份概念。 身份概念是我们分布式系统的基本机制的基础，包括互换性、幂等性和不变性。


Raymond Blum, Betsy Beyer - 实现数字永恒
当今的信息时代正在为世界所依赖的数据创造新的用途和新的管理方式。 世界正在从熟悉的物理人工制品转向更接近其本质信息的新的表示方式。 我们需要流程来确保知识的完整性和可访问性，以保证历史将被知晓和真实。


Graham Cormode - 数据草图
您是否曾经感到被永无止境的信息流淹没？ 似乎源源不断的新电子邮件和短信需要持续关注，还有电话要接听、文章要阅读以及敲门声要回应。 将这些碎片拼凑在一起以跟踪重要的内容可能是一个真正的挑战。 为了应对这一挑战，流数据处理模型越来越受欢迎。 其目标不再是捕获、存储和索引每一分钟的事件，而是快速处理每次观察，以便创建当前状态的摘要。



© 保留所有权利。

© . All rights reserved.