以橙色为主的网站,网络管理软件app,深圳龙岗职业技术学校招生,做网站赚钱的点在哪里doi#xff1a;DoppelGanger: Towards Fast Dependency Graph Generation for Database Replay#xff0c;点击前往 文章目录 1 简介2 架构概述3 依赖关系图3.1 符号和问题定义3.2 无 IT(k) 图3.3 无 OT 图表3.4 无 OTIT 图表3.5 无 IT[OT] 图表3.6 输出确定性保证 4 重复向后…doiDoppelGanger: Towards Fast Dependency Graph Generation for Database Replay点击前往 文章目录 1 简介2 架构概述3 依赖关系图3.1 符号和问题定义3.2 无 IT(k) 图3.3 无 OT 图表3.4 无 OTIT 图表3.5 无 IT[OT] 图表3.6 输出确定性保证 4 重复向后扫描 (RBSS)5 状态单向扫描 (SSFS)5.1 生成 G~IT~5.2 生成 G~OT~5.3 生成 G~IT[OT]~ 6 并行化 SSFS7 实验7.1 实验设置7.2 TPC-C 的实验结果7.3 真实客户工作负载的实验结果7.4 内存使用情况7.5 PSSFS 的可扩展性 8 相关工作9 结论致谢REFERENCES 数据库重放系统 (DRS) 捕获生产系统上的工作负载然后在测试系统中重放它们以测试各种系统更改从而在生产中实现它们之前避免任何风险。DRS 中的依赖图生成对于保持输出确定性同时最大化并发性至关重要。商业 DBMS 中部署的最先进的依赖图生成算法使用生成和修剪策略。
它首先通过对工作负载中的每个请求执行向后扫描来生成依赖图。然后它使用昂贵的传递性减少算法修剪所有冗余边。但是我们注意到这会生成一个包含许多冗余边的大型依赖图并且其最坏情况时间复杂度是工作负载中请求数量的平方。为了解决这些具有挑战性的问题我们正式提出了四类 DRS 依赖图。然后我们提出了一种有状态的单次前向扫描算法 SSFSstateful single forward scan通过对所有请求执行单次扫描来生成任何类别的依赖图同时简洁地维护状态。这里状态是指为高效生成依赖关系图而存储和维护的信息。我们还提出了并行 SSFS以利用多核 CPU 的计算能力同时平衡负载。
我们在领先的商业 DBMS 中实现了我们的 DRS。使用 TPC-C、SD 基准和真实客户工作负载进行的大量实验表明与最先进的技术相比我们的 DRS 可将依赖关系图生成时间显著缩短两个数量级。
CCS 概念信息系统 → 数据库实用程序和工具数据库性能评估。
其他关键词和短语数据库重放 1 简介
数据库重放系统 (DRS) 在测试系统中测试关系数据库系统。DRS 捕获生产系统上的工作负载然后在测试系统中重放它们以测试各种系统更改例如硬件/软件升级并避免任何风险例如
性能回归错误在生产中实现之前出现新的资源争用点 [20, 28]
在这里工作负载由用户请求组成每个请求都包含带有会话 ID 的 SQL 语句。
输出确定性 [10] 确保捕获的工作负载的重放产生与原始运行相同的输出即使由于硬件或软件更新而导致工作负载的物理计划发生变化。原始运行中两个相关请求之间的相对顺序必须在重放中保留。否则重放不能保证产生与原始运行相同的输出。例如在清单 1 中Q1 在原始运行中先于 Q2 执行。假设两个查询均以自动提交模式执行。然而在数据库重放期间假设Q1 和 Q2 以相反的顺序重放。那么 Q2 的输出与原始运行的输出不同这违反了输出确定性。
Listing 1. Query examples
Q1 : UPDATE emp SET salary salary *1.1;
Q2 : SELECT * FROM emp WHERE salary 60000;最先进的 DRS 通过从捕获的工作负载生成依赖关系图并基于依赖关系图重放请求来确保输出确定性。这里依赖关系图中的每个顶点对应于一个请求并且一条边在两个请求之间施加了优先约束 [3, 28]。虽然可以通过在捕获时间内按相同顺序顺序重放请求来确保输出确定性但这种简单的方法无法运行真实的重放严重限制了并发性 [28]。相反通过并行执行请求同时保留依赖关系图中的顺序DRS 可以实现输出确定性同时支持真实的并发重放。
主要数据库供应商支持 DRS [2, 3, 5, 38]。它们在数据库重放工作流中支持以下四个阶段工作负载捕获、依赖关系图生成、工作负载重放和报告生成。
在第一阶段DRS 记录工作负载中的所有请求每个会话一个捕获文件。此步骤在生产系统中完成而其他步骤通常在测试系统中完成以避免干扰生产系统中正在运行的应用程序在依赖关系生成阶段它会生成一个依赖关系图在请求之间施加优先约束以确保输出确定性在工作负载重放阶段它会使用最小依赖关系图和这些捕获文件重放捕获的工作负载最后一步会生成有关系统更改之间任何差异的各种报告
请注意将现有数据库实例迁移到目标系统的决定不能一次性做出相反需要连续执行捕获和重放以使用各种工作负载测试目标系统。因此减少生成时间至关重要尽管依赖图生成是一个离线过程。
为了在最大化并发性的同时实现输出确定性DRS 必须生成具有最短关键路径的最小依赖图the shortest critical path [39]并在此基础上重放工作负载。Morfonios 等人 [28] 提出了 RBSS这是一种使用生成和修剪策略的高效依赖图生成算法。使用此策略生成步骤通过使用向后扫描在其他会话中查找最新的依赖请求来生成每个顶点的传入边而修剪步骤使用传递归约算法a transitive reduction algorithm修剪冗余边 [9]。如果在移除边后 仍可从 到达则直接边 (, ) 是冗余的。该技术已在商用 DBMS [2] 中采用。 但是RBSS 仍会生成包含许多冗余边的大型依赖图尽管可以在生成步骤中过滤它们。例如图 1 显示在代表性 ERP 工作负载 SD-Benchmark [4] 中此依赖图 (标记为 GRBSS) 中的 99.6% 的边是冗余的。给定依赖图( , )当 || |′| 时计算其传递归约 (, ′) 可能很昂贵因为 中的所有冗余边都将被删除。
其次由于对每个顶点重复进行反向扫描RBSS 的时间复杂度可能为 (||2)。具体来说为了生成会话中每个顶点的入边RBSS 需要向后扫描其他会话直到在最坏情况下到达会话的开头。此外向后扫描会访问许多不必要的会话。依赖图生成算法中的这种低效率显著增加了依赖图生成时间。因此我们必须开发一种有效的算法来生成接近传递约简大小的依赖图。
RBSS 在捕获和重放管道中产生主要瓶颈占总端到端时间的 50% 以上。由于我们的客户不断捕获和重放随时间变化的工作负载以快速检查系统变化之间的任何差异因此需要显著提高依赖关系图的生成速度。
为了正式解决这个问题我们首先在依赖关系图中定义两种类型的主导冗余边对象传递性object transitivity (OT) 和会话间传递性 inter-session transitivity (IT)。
OT 是指由于路径上的所有请求都访问一个公共对象而导致的冗余。考虑图 1 中的依赖关系图。顶点的标签表示对对象的操作更新、选择或提交。例如请求 1 的标签即 1表示对对象 1 的更新语句。例如(6, 9) 由于 OT 而冗余因为存在一条路径 (6, 8, 9)其中所有请求都访问公共对象 2。IT 指的是由于通过两个会话中的请求的路径而导致的冗余即使某些请求访问不同的对象。考虑会话 2 和 3。然后边 (5, 12) 由于 IT 而冗余因为存在通过这些会话的路径 (5, 6, 8, 12)。请注意5 和 12 访问对象 1而另一个请求访问对象 2。虽然我们可以将 IT 的定义推广到三个或更多会话但修剪这种冗余将需要昂贵的连接操作这甚至比传递闭包transitive closure更昂贵。这促使我们在依赖图生成中平衡紧凑性和效率。我们将在第 3.2 节中详细阐述这个问题。
为了通过系统地探索 IT 和 OT 的所有组合的设计空间即分类法来找到最合适的依赖图我们接下来提出了四个新的依赖图IT(k)-free, OT-free, OTIT-free, and IT[OT]-free。我们将在第 3 节中正式定义这些图。我们的形式化可以解释
无 IT(k) 图是 [28] 的广义图OT-free 图是另一种新的依赖图用于捕获通过公共对象的edges的传递属性IT[OT]-free 图兼具两者的优势。我们发现IT[OT]-free 图是平衡效率和大小的最理想图
表 1. 具有 16 个服务器实例的 SD 基准中每个依赖图中冗余边的比例 为了避免重复向后扫描我们提出了一种新颖、高效的依赖图生成算法称为有状态单向前向扫描stateful single forward scan (SSFS)。SSFS 对所有请求执行单次前向扫描同时保持状态。通过分析冗余的定义我们根据依赖图类型简洁地维护状态。我们还提出了 SSFS 的并行版本其中请求按时间范围水平划分。并行 SSFS 分层合并这些本地依赖图以生成全局依赖图实现线性加速。
我们的贡献总结如下
我们在领先的商业 DBMS 中实现了 DoppelGanger这是一个包含所有提议技术的 DRS。因此DoppelGanger 可以支持现实世界的客户工作负载我们通过系统地探索主要冗余边的设计空间正式定义了四种依赖图的分类法。我们还提供了一个维恩图来说明这些依赖图之间的包含关系我们提出了一种新颖的依赖生成算法 SSFS 来扫描一次请求即避免二次复杂度并实现线性复杂度。请注意SSFS 可以生成分类法中的任何类型的依赖图通过分析所有依赖图我们建议使用无 IT[OT] 图的 SSFS这既实现了依赖图的紧凑性又实现了算法的效率我们还提出了 SSFS 的并行版本这进一步缩短了依赖图生成时间使用 TPC-C、SD 基准和真实客户工作负载进行的实验表明SSFS 的性能比 RBSS 高出两个数量级。我们还表明并行 SSFS 实现了几乎线性的加速
本文的其余部分组织如下。第 2 节描述了 DoppelGanger 的整体架构。第 3 节提出了依赖图的分类。在第 4 节中我们回顾了 RBSS 及其与第 3 节中定义的依赖图的关系。第 5 节提出了我们的 SSFS 算法并展示了 SSFS 如何生成所有类型的依赖图。我们还解释了为什么无 IT[OT] 图是平衡效率和大小的理想依赖图。第 6 节提出了 SSFS 的并行版本。为了证实我们的主张第 7 节使用两个基准和真实客户工作负载对 SSFS 与 RBSS 进行了广泛的实验评估。第 8 节将我们的贡献与相关工作进行了比较第 9 节总结了本文。 2 架构概述
DoppelGanger 是一款基于最先进的商业 DBMS 构建的成熟 DRS。该系统为用户提供了一种多用途测试工具允许他们捕获源系统上运行的工作负载并在目标系统上重放捕获的工作负载并提供详细的重放分析报告。用户可以通过可视化工具轻松管理整个过程。图 2 说明了 DoppelGanger 的整体架构包括以下四个步骤 捕获步骤以轻量级方式自动捕获工作负载信息包括执行上下文信息和在生产系统上运行的请求。捕获的信息例如 SQL 数据和事务数据根据其类型进行分类并存储在不同的文件中。在此步骤中DoppelGanger 备份当前快照以便用于重放。 控制系统中的预处理步骤接收捕获的工作负载文件作为输入并生成依赖关系图文件以实现一致的工作负载重放 [28]。输入文件包含捕获时每个数据库会话发出的请求信息。生成的文件可以重播多次。生成的依赖关系图文件是请求的序列化其中每个请求都与其他并发会话中的依赖请求相关联。请注意当我们使用最先进的 [28] 时依赖关系图生成占用了总端到端时间的 50%这是我们的动机。 重放步骤使用依赖关系图文件重放捕获的工作负载同时保留目标系统上的事务顺序该目标系统由备份的快照初始化。具体来说加载器线程loader threads读取依赖关系图文件the dependency graph files并将其加载到特定于会话的请求队列中。每个队列由控制执行时间的请求调度程序a request dispatcher管理。然后请求调度程序将请求从队列发送到执行线程execution threads。可以执行没有传入边incoming edges的请求。当非提交请求启动时它会获取快照并删除其传出边outgoing edges。这可以成功完成长读取事务而不会阻止写入事务。另一方面提交请求获取提交时间戳并删除传出边从而允许成功提交。运行请求后执行线程返回其结果。 分析步骤将重放结果与捕获结果进行比较并生成可视化的分析报告。比较是从性能和一致性的角度进行的。对于性能比较将测量系统级吞吐量、资源消耗和各个请求的执行时间。为进行一致性检查我们会测量整体数据库状态和各个请求的执行结果。
虽然这超出了我们的范围但 DoppelGanger 已经支持分布式环境中的数据库重放。我们的底层 DBMS 维护一个具有全局时间戳的协调器节点。因此分布式数据库节点中执行的事务可以由相同的事务时间戳生成器排序因此不需要更改依赖项生成。位于两个数据库节点中的对象之间的边在重放时实现为进程间通信调用。 3 依赖关系图
我们提出了一种正式分类法使用所有会话间传递性 (IT) 和对象传递性 (OT) 组合的设计空间无 IT(k) 图、无 OT 图、无 OTIT 图和无 IT[OT] 图。由于从工作负载生成的依赖关系图最终通过广泛的传递性减少进行修剪因此我们需要找到一个可以通过顺序扫描有效生成的紧凑依赖关系图。基于我们正式的分类法我们将在引理 1 中表明RBSS 生成的依赖关系图是无 IT(1) 图的一个特例因为它无法修剪某些边 (, ′)其中 和 ′ 之间有多个 IT 连接。
3.1 符号和问题定义
工作负载 W 被建模为有向图 Gini (VR, εses)其中每个顶点对应 W 中的一个请求每个边是会话中的一对连续请求例如图 1 中的 (2, 7)。Gini 称为初始图。此处每个请求 都与一个唯一时间戳 (.)、一个会话 ID (.) 以及由 访问的一组对象 (.) 相关联。如果 是提交请求 . 表示已提交事务修改的所有对象的集合。例如在图 1 中5. 为 {1, 3}因为事务 分别修改了 1 和 3 中的对象 1 和 3。 表示所有会话的集合而 表示工作负载中所有对象的集合。与 [28] 中一样对象可以是表或表分区。请求分为非提交 (NC)即 SELECT 或 UPDATE和 提交 ( C ) 请求从而使其更新永久生效。如果事务未更新任何对象则其提交请求与其他会话中的请求没有任何依赖关系。因此它在依赖关系图生成阶段被忽略但在重放阶段仅在事务结束时重放。会话中的请求被限制为按时间戳的顺序重放如 εses 中规定的那样。由于会话中的请求按时间戳顺序存储 [28]因此我们不需要明确存储 εses。为了便于解释我们假设存在 0 和 ∞它们对应于虚拟的初始请求和最后一个请求。请注意Gini (VR, εses) 不是依赖关系图因为它仅包含每个会话内的排序约束。表 2 显示了整篇论文中使用的符号。 我们首先定义谓词来定义其他依赖二元binary关系 [28]。
考虑两个请求 , ′ ∈ VR。如果 . ′.则谓词 (, ′) 返回 true否则返回 false我们定义优先依赖边precedence-dependent edges集合ε {(, ′) ∈ VR2 | (, ′)}。如果 是提交请求() 返回 true否则返回 false我们定义提交相关边commit-dependent edges集合ε {(, ′) ∈ ε | () ∨ (′)}。如果 和 ′ 访问一个共同的对象即 . ∩ ′. ≠ ∅则 _ _(, ′) 返回 true否则返回 false我们定义一组与对象相关的边object-dependent edgesε {(, ′) ∈ ε | __(, ′)}。最后我们定义碰撞相关边collision-dependent edges集合εcol ε ∩ ε。当 (, ′) ∈ εcol 时我们说 与 ′ 碰撞相关。
我们交替使用术语“依赖关系dependency relation”和“边集edge set”。
给定初始图 Gini (VR, εses)依赖图生成算法根据其特定关系生成新的边集。例如依赖图算法可以通过检查提交依赖关系和对象依赖关系来生成依赖图 Gcol (VR, εcol)。 一个极端依赖图是完全有序的依赖图 Gtotal它通过按时间戳递增顺序连接请求来构建。使用 GtotalVR 中的请求将按顺序执行导致并发性严重受限 [28]因为 Gtotal 的关键路径是所有可能的依赖图中最长的。另一个极端图是最小依赖图 Gmin (VR, εmin)通过它我们可以一致地重放 W 而无需任何不必要的同步开销。在这里可以通过删除 εcol 中的所有冗余边来构建 Gmin即通过对 Gcol 执行传递归约算法。现在我们给出问题的正式定义
问题定义 1给定一个以初始图 Gini (VR, εses) 为模型的工作负载有效生成一个紧凑的依赖图 G (VR, E)使得 G G。
我们现在根据每个依赖图从 Gcol 中修剪的冗余边的类型提供依赖图的概述。图 3 显示了依赖图之间的包含关系。请注意每个依赖图都避免了来自 Gcol 的特定类型的冗余边。无 IT 图 GIT 和无 OT 图 GOT 分别避免了由于 IT 和 OT 而导致的冗余边如第 1 节所述。由 [28] 中的生成步骤即在传递归约之前生成的 GRBSS 是无 IT 图的一个特例。无 OTIT 图 GOTIT 是避免由于 IT 或 OT 而导致的冗余边的图。无 IT[OT] 的图 GIT[OT] 是先修剪由于 OT 而导致的冗余边然后再修剪由于 IT 而导致的冗余边的图。(GIT[OT]) ⊇ (GOTIT)因为 GIT[OT] 在修剪由于 OT 而导致的冗余边后会失去一些 IT 连通性。
例如在图 1 中GIT 避开了所有红色和绿色虚线边而 GOT 避开了所有蓝色和绿色虚线边。GOTIT 避开了除 (5, 10) 之外的所有虚线边。请注意 (5, 13) ∉ (GOTIT)但 (5, 13) ∈ (GIT[OT])。这是因为GIT[OT] 首先删除了 (6, 9)因此路径 (5, 6, 9, 11, 13) 在生成的依赖图中消失。边 (5, 10) 是冗余的这是由于除 IT 和 OT 之外的可达性所致。但是这种类型的冗余相对较少见在表 1 中GOTIT 中只有 5.3% 的边是冗余的。修剪这些边需要计算传递闭包transitive closure。因此我们在生成步骤中允许这样的边。
3.2 无 IT(k) 图
我们首先在两个不同的会话中定义 k 前向路径k-forward的概念。然后我们使用 k 前向路径定义无 IT(k) 图。在 IT(k)-free 图中我们特别讨论了两个特殊图无 IT(1) 图和无 IT(∞) 图。最后我们解释了为什么我们只考虑两个不同的会话。
为了在 εcol 中定义冗余边但在无 IT(k) 图中不定义冗余边我们首先定义 k 前向路径的概念。给定两个顶点会话 中的 和会话 ′ 中的 ′ ≠ ′一条路径 (, 1, · · · , s, ′1, · · ·′, ′) ( ≥ 0, ≥ 0, ≥ 1) 被称为 εcol ∪ εses 中从 到 ′ 的 k-forward-path其中所有 都在会话 中而 ′ 都在会话 ′ 中。这里 是会话 ′ 中由顶点组成的子路径的长度。给定一条边 (, ′)如果存在一条从 到 ′ 的 k 向前路径则 (, ′) 是冗余的。这种冗余被称为会话间传递性 (IT)因为在两个不同会话 ( 和 ′) 中的请求中存在一条 k 向前路径。例如图 1 中的路径 (5, 6, 8, 12) 是从 5 到 12 的 1 向前路径1-forward path。因此(5, 12) 是冗余的。因此它在无 IT(1) 图中被修剪。
然后我们正式定义一个新的无冗余依赖图即使用 k 前向路径的 IT(k) 无图。我们首先定义一个无冗余依赖边集的新概念。为了通用性我们在任意边集 ε 上定义它(ε) {(, ′) ∈ ε | ∄ -forward path from to ′ in ε ∪ εses where 0 ≤ ≤ k}。也就是说(ε) 中的每条边都缺少长度为 或更短的任何前向路径。定义 1 定义了边集为 (εcol) 的图。
定义 1对于 Gini无 IT(k) 图 GIT(k) (VR, εIT(k)) 是一个依赖图其中 εIT(k) (εcol)。
依赖图 GRBSS (VR, εRBSS) 由 [28] 中的依赖图生成算法的生成步骤即在传递归约之前生成位于 GIT(0) 和 GIT(1) 之间 即 εIT(1) ⊆ εRBSS ⊆ εIT(0)。我们将在第 4 节中讨论这一点。
虽然 GRBSS 比 Gtotal 提供更高的重放并发性但它可能有许多冗余边导致重放期间的严重开销。可以在 GRBSS 上执行传递归约算法。但是由于不必要的冗余边生成和删除的开销很高依赖图生成的整体性能会很慢。例如在表 1 中GRBSS 中 99.6% 的边是冗余的。这促使我们定义一个更紧凑的依赖关系图以实现高效的生成和传递归约。
IT(∞)-free 图简称为 IT 无图是 IT(k)-free 图的一般情况其中边没有任何长度的前向路径即 ∞。IT-free图确保在两个会话间修剪所有冗余边。为简便起见我们在以下部分中将 ∞(ε) 表示为 (ε)。
虽然我们可以将 IT 的定义推广到三个或更多会话但修剪这些冗余边将需要对迄今为止正在构建的边集 (ε) 进行昂贵的自连接操作。例如考虑为三个会话构建(ε)。然后我们需要使用量词1、2 和 3 对 (E) 执行三向自连接其中非等值连接条件包括“1._ ≤ 2._ AND 1._ ≥ 2._ AND 2._ 3._”。这甚至比传递闭包transitive closure更加昂贵。
3.3 无 OT 图表
尽管无 IT 图删除了一些冗余边但仍有许多冗余边因为它仅考虑了两个会话导致的会话间冗余。例如在表 1 中无 IT 图中 73.7% 的边仍然是冗余的。我们分析发现无 IT 图中最多的冗余边是由于碰撞相关边collision-dependent edges的传递性其中每条边的源顶点和目标顶点访问同一个对象。我们这种冗余 object transitivity 对象传递性 (OT)。也就是说OT 捕获了多个会话之间重要且占主导地位的冗余这也可以有效地检测到正如我们将在第 5.2 节中看到的那样。在表 1 的 SD 基准测试中无 IT 图中 98% 的冗余边都有 OT。
我们首先正式定义另一种重要的无冗余依赖边集其灵感来自无对象传递性 (OT-free) 边。为了定义无 OT 边集我们定义了一个谓词。考虑两个请求′ ∈ VR。谓词 _(, ) 当且仅当 ∈ . 时返回 。然后我们在定义 2 中定义无 OT 图。例如在图 1 中无 OT 图没有 (6, 9)因为 (6, 8, 9) 因 OT 而存在。 定义 2对于 Gini无 OT 图 GOT (VR, εOT) 是依赖图其中 εOT (εcol)。
3.4 无 OTIT 图表
通过同时应用 (ε) 和 (ε)即删除两种类型的冗余边可以获得更简洁的依赖图。在所有可能的组合中即 ( (ε))、 ( (ε)) 和 (ε) ∩ (ε)最简洁的依赖图是没有任何冗余边的依赖图这些冗余边在无 OT 或无 IT 的图中都不存在。我们将该图称为无 OTIT 图。
无 OTIT 图的边集只是无 OT 和无 IT 图的边集的交集如定义 3 中所定义。请注意OT 和 IT 的顺序与定义无关。
定义 3对于 Gini无 OTIT 图 GOTIT (VR, εOTIT) 是一个依赖图其中 εOTIT (εcol) ∩ (εcol)。
3.5 无 IT[OT] 图表
无 OTIT 图在生成图效率方面存在缺点因为它偏向简洁。我们将在第 5 节中讨论具体的时间复杂度但直观地看确定哪条边同时在 (ε) 和 (ε) 中的成本很高。我们观察到在 (ε) 之后应用 (ε) 可以获得无 IT[OT] 图与无 OTIT 图相比它可以更高效地生成同时只增加少量冗余边在 TPC-C 中多 1.3%。在本节中我们提出了一种无 IT[OT] 图这是一种可以高效生成的紧凑图将在第 7 节中进行实证验证。我们在定义 4 中正式定义了无 IT[OT] 图的概念。
定义 4对于 Gini无 IT[OT] 图 GIT[OT] (VR, εIT[OT]) 是一个依赖图其中 εIT[OT] ( (εcol))。
通过改变 OT 和 IT 的顺序我们可以得到无 OT[IT] 图。然而与无 IT[OT] 图相比无 OT[IT] 图的效率较差因为为每个对象 ∈ 计算 (εIT) 的成本很高。因此我们省略了无 OT[IT] 图的解释。我们将在第 5 节中讨论这个问题然后再解释如何生成每个图。
尽管 GOTIT 是最小的但 DoppelGanger 选择了 GIT[OT] 因为它在大小和效率之间取得了平衡。也就是说在我们广泛的实验中| εIT[OT]| / | εOTIT | 最多为 1.09尽管 GOTIT 的生成成本平均比 GIT[OT] 高 3.2 倍。
3.6 输出确定性保证
我们首先表明我们的捕获和重放算法保证了 (事务级) 快照隔离下的输出确定性。快照隔离级别可防止脏读、不可重复读和幻读。为了确保输出确定性我们必须确保
每个重放请求 返回与捕获期间相同的输出以及 将数据库状态更改为与捕获期间相同的状态
在这里我们假设不存在随机不一致如 [28] 中所述具有相同输入并读取相同数据库状态的语句始终会产生相同的输出。
在快照隔离中每个事务都获取具有其开始时间戳的自己的快照并读取即可能通过多个语句在时间戳之前提交的数据快照。当没有发生写冲突时可以提交事务。为了确保 1)每个重放的事务必须看到与捕获期间相同的快照。为此DRS 将每个事务的快照时间戳记录为其非提交请求的时间戳。
在 Gcol 中每个非提交请求 与修改 . 中某个对象的提交请求之间的顺序得以保留。在重放期间DRS 需要确保每个非提交请求读取在其时间戳之前提交的 . 的快照。使用 Gcol2) 也得到保证因为具有重叠写入集的提交请求是按顺序调度的从而避免了任何写入冲突。
请注意某些 DBMS例如 PostgreSQL声称支持可重复读取隔离但在级别 [6] 中不允许幻像读取而其他 DBMS例如 SQL Server则在每个语句读取的所有数据上持有共享锁直到事务完成。在两种情况下如果我们对捕获和重放使用相同隔离级别下的相同并发控制则满足读取稳定性条件即可重复读。
现在我们来解释一下为什么我们的算法也能保证在较弱的隔离级别语句级快照隔离下的输出确定性。在语句级快照隔离中每个语句都使用其快照时间戳获取自己的快照并读取在时间戳之前提交的数据从而允许不可重复或幻像读取。与事务级快照隔离不同我们还捕获每个非提交请求的时间戳。在重放期间我们确保每个非提交请求都读取在其时间戳之前提交的对象的快照。
我们的正确性保证适用于我们提出的所有依赖关系图。这是因为删除冗余边不会改变请求的执行顺序。例如在图 1 中考虑冗余边 (4, 9)。如果我们删除边由于路径 (4, 8, 9)9 仍将在 4 之后调度。
分区级依赖关系与表级依赖关系一样可确保输出确定性从而避免块级或行级依赖关系中出现的重放不一致问题 [28]。当我们对表进行分区时我们会了解分区信息。因此我们的系统可以使用此信息识别查询的适当分区而块级或行级依赖关系则不足。
商业 DBMS 通常支持基于哈希或基于范围的分区。因此一旦给出查询我们的 DRS 就会使用分区修剪技术例如 [22]识别查询访问的所有相关分区。如果查询包含非分区键上的谓词则 DRS 会识别表 的所有分区即使某些分区可能没有与查询相关的元组。也就是说我们的 DRS 采取保守的方法来保证正确性。
例如考虑一个表 (, ,)其范围在 上分区{[1-10], [11-20], [21-30], …,[9990-10000]}。假设清单 2 中的两个事务在捕获时按顺序执行。这里事务 T1 使用非分区键 上的谓词而事务 T2 使用分区键 上的谓词即 1。然后T1 的 SELECT 请求与 的所有分区相关联而 T2 的两个请求即 UPDATE 和 COMMIT 请求仅与第一个分区相关联请注意T1 的 COMMIT 请求被忽略因为 T1 不会更新任何对象如第 3.1 节所述。因此T1 的 SELECT 请求和 T2 的 COMMIT 请求在依赖图中的顺序正确。
-- Listing 2. Transaction examplesT1 : SELECT * FROM R WHERE B 20; COMMIT ;
T2 : INSERT INTO R VALUES (1 ,5 ,20); COMMIT ;4 重复向后扫描 (RBSS)
本节回顾 RBSS [28] 如何从 Gini 生成依赖图 GRBSS。请注意RBSS 指的是生成算法不包括传递归约。我们还提供了 RBSS 的时间复杂度以及 GRBSS 与 GIT(k) 之间的关系。
RBSS 通过迭代除 ′ ′. 之外的每个会话 ∈ 并以时间间隔 (., .) 执行向后扫描来生成每个请求 ′ ∈ VR 的传入边incoming edges。只要我们发现 与 ′ 发生碰撞它就会停止扫描。假设 是 ′ 在会话 ′ 中的前一个请求。那么 是会话 中 ′ 之后最早的请求而 是会话 中必须等待 的请求。注意边 (, ) 需要在 ′ 的入边生成之前生成。例如我们在图 4 中解释如何计算7 的时间间隔。由于 (2, 4) 是在处理4 时生成的因此 设置为2。 设置为8。 时间复杂度RBSS 的时间复杂度为 (|VR|2)。我们假设请求在会话之间均匀分布。此外我们假设查找 需要 ( (|VR| / ||))而所有其他子过程都需要常数时间。在最坏的情况下RBSS 必须在每个会话中访问 ′. 之外的所有先前请求即 可以为 0。因此总体时间复杂度为 为了使用时间复杂度分析来分析实验结果我们使用平均后向距离average backward distance g 的概念推导出更严格的界限即每个请求需要扫描的平均请求数以从会话中找到传入边。最后我们得到 (| VR | · (| | −1) · ( (| VR | / | |))) 作为 RBSS 的时间复杂度。
我们解释了 IT(k)-free 图与依赖图 GRBSS (VR, εRBSS) 之间的关系。请注意[28] 没有定义此图因此很难理解和分析 GRBSS 的属性。引理 1 建立了这种关系。我们简要解释了引理证明背后的直觉。 RBSS 用 0 前向路径 (, · · · , , ′) ( ≥ 1)即 εRBSS ⊆ εIT(0)修剪每条边 (, ′)。假设在 GRBSS 中(, ′) 有一条 0 前向路径 (, · · · , , ′) ( ≥ 1)。然后在会话 中的向后扫描以生成 ′ 的传入边期间RBSS 必须找到 然后停止。我们现在解释为什么 RBSS 无法修剪某些边 (, ′) ∈ εcol这些边具有 1-前向路径 (, 1, · · · , , , ′) ( ≥ 0)即 εIT(1) ⊆ εRBSS。一旦 (, ) 从 GRBSS 中修剪掉RBSS 就不会继续修剪冗余边 (, ′)因为它具有 1-前向路径。以下引理显示了这些依赖图之间的包含关系。所有形式引理和证明均在技术报告 [7] 中。我们建议感兴趣的读者参阅该报告以了解详细信息。
Lemma 1. εIT(1) ⊆ εRBSS ⊆ εIT(0). 5 状态单向扫描 (SSFS)
本节介绍我们使用状态的高效依赖图生成算法 SSFS。我们首先描述一种使用状态生成依赖图的常用算法。然后我们解释应该维护哪些状态以及如何从每种类型的依赖图的状态生成依赖图。SSFS 可以在第 3 节中生成任何依赖图。
我们将 VR 视为根据时间戳的顶点序列。我们假设时间戳 由单调递增的逻辑计时器 ( ≥ 1) 分配。依赖图生成算法采用 VR处理请求并输出依赖关系 ε ∈ {εOT, εIT, εOTIT, εIT[OT] }。我们省略了如何生成无 OT[IT] 图因为它需要为每个对象 ∈ 计算(εIT)这是昂贵的。给定一个对象计算εIT等同于计算VR(εIT)的传递约简这需要(|(εIT)| | || VR | | ||(εcol)|)[3234]。另一方面我们可以从观察第 5.2 节中有效地计算(εcol)。我们的实验还表明无 IT[OT] 图在简洁性和效率方面都很有效第 7 节。我们省略了如何生成 εOTIT因为它是通过 εOT 和 εIT 的交集获得的。 算法 1 描述了 SSFS。SSFS 首先初始化增量附加的当前边集第 1 行和状态第 2 行。SSFS 按时间戳的递增顺序迭代 VR 中的所有请求 ′第 3 行。对于每个请求 ′SSFS 使用 生成一组 ′ 的传入边 ε′第 4 行然后更新 第 5 行。然后 SSFS 将生成的边集附加到当前边集第 6 行。在迭代结束时SSFS 最终返回生成的依赖图第 7 行。
5.1 生成 GIT 考虑在时间戳 处会话 ′ 的当前请求 ′。由于对于任何 0εIT(0) ⊇ εIT(k)我们首先从每个会话 (≠ ′)情况 0中找到 εIT(0) 中的每个边 (, ′)如果 和 ′ 之间存在 (≥ 1) 前向路径情况 0则对其进行修剪。也就是说未修剪的那些必须在 εIT(k) 中。例如在图 5 中我们假设当前要处理的请求是 7 ( ′)即提交请求。然后从会话 1 开始我们找到 (6, 7) ∈ εIT(0)并且不对其进行修剪因为没有从 6 到 7 的 k 向前路径。另一方面从会话 2 开始我们首先找到 (4, 7) ∈ εIT(0)并对其进行修剪因为存在 1 向前路径 (4, 5, 7)。
对于每个会话 (≠ ′)为确保 (, ′) ∈ εIT(0)情况 0 必须是会话 中对 ′ 的最新碰撞相关请求参见图 6a。否则在会话 中存在最新的与碰撞相关的请求 (≠ ) 到 ′因此存在一条 0-前向路径(, · · · , , ′)这与 εIT(0) 的定义相矛盾。 对于每条边 (, ′) ∈ εIT(0)为确保 (, ′) ∈ εIT情况 ≥ 1没有边 (, ′) ∈εIT(0) 使得 . 、. ≥ .、′. ′ 和 ′. 已被附加到当前正在构建的依赖图中参见图 6b。否则存在一条 k 前向路径 (, · · · , , ′, · · · , ′)这与 εIT(k) 的定义相矛盾。
GIT 的状态为了生成 GIT 的传入边我们维护两个嵌套表作为状态会话碰撞请求the session-wise collision requests (SCR) 和会话间最新附加边the latest appended edges between sessions (LAE)。SCR 存储每对 (, ) 的最新未提交和提交请求。给定一个对象 和一个会话 我们可以使用 SCR 检索和更新会话 中访问 的最新未提交和提交请求。
SCR 以二维数组实现允许在 (1) 中执行查找和更新操作。例如当我们在图 5 中处理7时SCR 分别将2 和4 存储为会话 2 中访问对象 1 的最新未提交和提交请求。同样SCR 分别将1 和4 存储为会话 2 中访问对象 2 的最新未提交和提交请求。LAE 将每对会话的最新附加边存储在 εIT(0) 中同时支持查找和更新。LAE 也是以二维数组的形式实现的因此可以在(1) 中执行操作。例如在同一图中LAE 中的第四个元组表示从会话 2 到会话 3 的最新附加边45。
我们现在描述用于为 GIT 生成 ′ 的传入边的详细算法。给定 ′对于每对 (, )使得 ∈ ′.我们从 SCR 检索与 ′ 冲突相关的最新非提交和提交请求。在 ′ 的所有检索请求中如果 ′ 是提交请求我们将在 (|′.|) 中检索会话 中的最新请求 否则我们将在会话 中检索最新的提交请求 。然后由于 (, ′) ∈ εIT(0)我们使用 (1) 中的 和 ′ 从 LAE 检索最新附加边 (, ′)。如果未找到我们生成 (, ′) 作为新边。否则如果 . .我们生成 (, ′)。生成 (, ′) 后我们使用 (1) 中的 和 ′ 更新 LAE 中的元组方法是将 列的值替换为 (, ′)。对于每个请求更新 SCR 需要 (|′.|)而更新 LAE 需要 (||)即 ′ 的传入边数上限。
现在我们分析 GIT 的边生成和状态维护的时间和空间复杂度。对于每个请求′我们需要扫描 SCR 中对象 ID ∈ ′. 的每个元组。扫描 SCR 中的每个元组需要(1)因此′ 的入边生成的时间复杂度为(|′.| · ||)。维护每个请求的 SCR 和 LAE 的时间复杂度为( (|′.|, | |))。如果||和|′.|被视为常数则保证每个请求的(1)。状态的空间复杂度为 (| | · || ||2)因为 SCR 和 LAE 的大小分别为 (| | · ||) 和 (||2)。
5.2 生成 GOT
考虑当前请求 ′ 在时间戳 访问 ′.。为确保 (, ′) ∈ εOT对于每个对象 ∈ . ∩ ′.不存在从 到 ′ 的对象传递路径。否则对于某个 (, ′) ∉ ((εcol))参见 和 的定义。
因此对于每个 ∈ ′.我们找到 ((εcol)) 的 ′ 入边的候选源顶点。然后我们按顶点 ID 对它们进行分组以修剪组大小与 |′. ∩ .| 不匹配的任何候选顶点 。例如在图 5 中我们假设当前请求为 7 ( ′)。对于对象 1我们发现 4因为 (4, 7) ∈ 1(1(εcol))。
类似地对于对象 2我们发现 5 和 6因为 (5, 7)(6, 7) ∈ 2(2(εcol))。图 5 还显示了 group by 操作的结果。由于 4 (1) ≠ |7. ∩ 4.| (2) 的组大小我们丢弃 4。但是由于 5 (1) 的组大小 |7. ∩ 5.|我们生成 (5, 7)。与 (5, 7) 类似我们生成 (6, 7)。 为了确保对于 ∈ ′.有 (, ′) ∈ ((εcol))如果 ′ 是非提交请求 必须是访问 的最新提交请求。否则存在访问 的最新提交请求 ′′ (≠ )因此存在对象传递路径 (, ′′, ′)这与 ((εcol)) 的定义相矛盾。当′为提交请求时既可以是访问的提交请求也可以是非提交请求。如果为提交请求则必须是访问的最新请求并且在之后不得有访问的非提交请求′′。否则存在对象传递路径′′′参见图7a。如果为非提交请求则在之后不存在访问的提交请求′′。否则存在对象传递路径′′′参见图7b。我们将在访问 的最新提交请求之后访问 的一组未提交请求称为对象 的最新未提交请求集。例如在图 5 中{5, 6} 是对象 2 的最新未提交请求集。
我们将检索到的所有候选源顶点存储在临时表中用于 ′.。然后我们按源顶点 ID 对它们进行分组。如果源顶点 的组大小等于 | (. ∩ ′.)| 即对于每个 ∈ . ∩ ′.(, ′) ∈ ((εcol)))我们生成边 (, ′) 作为 GOT 的新边。否则我们丢弃 。
GOT 的状态为了生成 GIT 的入边我们维护一个嵌套表即OT-free候选表 OTC(, , ) 作为状态。OTC 中的每个元组对应于每对 (, )。如果 是 COMMIT则 存储访问 的最新提交请求。否则 存储为 设置的最新非提交请求。给定一个对象和请求类型我们可以使用 OTC 检索和更新访问的最新提交请求或取决于的的最新非提交请求集。例如在处理图 5 中的7′时对于 2 和 NON-COMMITOTC 将 {5,6} 存储为最新非提交请求集。对于 2 和 COMMITOTC 存储最新提交请求4。
我们现在描述用于为 GOT 生成 ′ 的传入边的详细算法。对于每个请求 ′SSFS 遍历每个对象 ∈ ′.。给定一个对象 当 ′ 是非提交请求时我们使用 (, COMMIT) 在 O(1) 中检索访问 的最新提交请求。如果 ′ 是提交请求我们首先使用 (, NON-COMMIT) 检索最新的非提交请求集。如果不存在这样的非提交请求那么我们使用 (, COMMIT) 在 O(1) 中检索访问 的最新提交请求。所有检索到的请求都存储在临时表中我们按顶点 ID 对候选源顶点进行分组。然后我们生成每个边 (, ′)使得 的组大小与 |. ∩ ′.| 相同。
现在我们分析 GOT 的边生成和状态维护的时间和空间复杂度。对于每个请求 ′我们需要从 OTC 扫描候选源顶点并将它们存储在临时表中。如果 ′ 是非提交请求则需要 (|′.|)。否则需要 (Σ ∈′. # of non-commit request in OTC for )。如果将临时表实现为哈希表则 group by 操作需要 ˜ ( (|′.|,Σ ∈′. # of non-commit request in OTC for ))。维护每个请求的 OTC 的时间复杂度为 (|′.|)。OTC 和临时表的空间复杂度为 (Σ ∈VR(| .|))。
5.3 生成 GIT[OT]
生成 εIT[OT] 的一个简单实现是 1) 在 εOT 中生成 ′ 的传入边2) 修剪一些不在 εIT[OT 中的边。这种方法的效率受到严重限制甚至不如生成 εOT。
我们不会在 εOT 中生成 ′ 的所有传入边而是丢弃一些来自 OTC 的候选请求以避免生成不在 εIT(0) 中的边。具体来说对于每个 (, ) 对我们只维护每个会话的最新请求。因此存储的请求数量明显小于原始 OTC。请注意生成 GIT[OT] 不需要 SCR。
我们还首先迭代会话并计算给定会话的最新候选源顶点 的数量。这样我们可以检查与 对应的组大小是否等于 | (′.∩.)|从而避免基于哈希的分组。与仅为 εOT 生成边相比此优化可显著提高速度。因此生成 εIT[OT] 可同时实现大小和效率。第 7 节中的大量实验证实了我们的说法。在为 εOT ∩ εIT(0) 生成 ′ 的传入边后我们使用 LAE 修剪边参见第 5.1 节中的 0 的情况。 6 并行化 SSFS
在本节中我们提出了 SSFS 的并行版本 (PSSFS)。我们重点介绍 IT[OT] 图因为其他类型的图也可以类似地获得。
它包含三个阶段1分区、2本地依赖图生成和 3分层合并。在分区阶段PSSFS 按时间范围将工作负载分为 p 个分区1、2、· · · 、并生成它们的诱导子图 induced subgraphs Gini[1]、Gini[2]、· · · 、Gini[ ]。其中如果 (G) 中每条边的端点都在 () 中[14]则子图 是 G 的诱导子图。给定一组顶点 ()G [ ()] 表示 。然后PSSFS 使用串行 SSFS 为 Gini[] 生成一个本地IT[OT]-free依赖图 G(0)。这里G() 表示分层合并中第 级的第 本地依赖图。请注意我们将解释为了实现有效的分层合并需要额外维护哪些状态。最后我们通过生成缺失的分区间边并保持状态来分层合并本地依赖图。除了最后一级合并的依赖图也被视为本地依赖图。例如给定局部依赖图 G() 和 G1()对于所有 ⌈log2 ⌉这两个图的合并依赖图也是 (G()) ∪ (G1()) 的另一个局部依赖图。详细算法请参考 [7]。
虽然这似乎是一种典型的并行算法但仍存在三个挑战。1) 与全局依赖图相比局部依赖图中缺少哪些边2) 局部依赖图中是否有边需要删除3) 为了实现高效合并还应保留哪些状态引理 2 回答了前两个问题。引理 2 指出 1) 缺少的边只是分区间的边2) 不存在从局部依赖图中删除任何边的风险。
引理 2。给定全局依赖图 GIT[OT]每个局部依赖图 G 都是使用 G 中所有顶点的全局依赖图的诱导子图。即 现在我们来回答最后一个问题。与 SSFS 一样我们首先解释必须维护哪些状态才能有效地为合并的无 OT 图生成候选分区间边。然后我们解释如何使用 k 前向路径的定义从中修剪冗余边。因此生成的图满足无 IT[OT] 图的所有条件。
考虑两个局部依赖图 G 和 G1 的合并。然后对于两个图之间的任何分区间边 (, ′) ∈ (G) 和 ′ ∈ (G1)。引理 3 指出了我们需要维护的分区间边的候选目标顶点集 {′}。
引理 3. 考虑合并两个局部依赖图 G 和 G1。然后对于某个对象 合并的依赖图中所有分区间边的目标顶点集中的每个顶点 ′ 要么是 G1 中第一个访问 的提交请求要么是第一个访问 的提交请求之前访问 的非提交请求。
基于引理 3我们将新状态维护为哈希表其键是对象 ∈ 其值是 的第一个提交请求和第一个提交请求之前的第一个非提交请求的对。 在这里我们不需要在每个会话的第一次提交请求之前存储所有非提交请求这类似于第 5.3 节中解释的优化。然后对于每个 ∈ 候选目标顶点集是键 的哈希表值中两个集合的并集。
现在我们解释如何使用这个附加状态生成合并的无 OT 图的分区间边。考虑合并两个局部依赖图 G 和 G1。然后我们可以获得 G1 的所有候选目标顶点。由于我们将像在 SSFS 中一样生成 GIT[OT] 的传入边因此我们按时间戳顺序对这些候选目标顶点进行排序。使用 G 中每个 ∈ 的第一个提交请求和提交请求之前的非提交请求PSSFS 像在 SSFS 中一样在 GIT[OT] 中生成边丢弃两个顶点都在 (G1) 中的任何边。
要为合并的 IT[OT]-free 图生成分区间边如果存在从 到 ′ 的 k 向前路径我们需要修剪 εOT 中的任何分区间边 (, ′)。如第 5.1 节所述 必须是 ′ 的最新碰撞相关。因此会话 中 ′ 的传入边的源顶点必须是不同会话中的最新候选源顶点 ∈ (G)。为了修剪 (, ′)使得存在从 到 ′ 的 k 向前路径并且路径中的所有边都在 ((Gcol[ (G) ∪ (G1)])) 中使用状态我们提供了以下引理。通过无 IT 图的定义很容易证明。 根据引理4我们需要找到′来检查分区间边the inter-partition edge′是否需要修剪。如果满足以下任何一种情况则修剪它
′∈(G)∈(G)且′∈(G1)′∈(G1)
当第一种情况成立时存在一条 k 向前路径 (, 1, …, , ′1, …, ′, ′) ( ≥ 0, ≥ 1)使得 且 ′1 ′。也就是说这样的 (, ′) 一定不在 ( (εcol)) 中。根据 k 向前路径的定义其他情况也成立。
第一种情况是使用 G 的 LAE 检查的因为 (, ′) 已为 G 生成。第二种情况也是通过 G 的 LAE 检查的因为候选目标顶点是按时间戳递增顺序处理的。对于第三种情况我们需要维护一个附加状态即会话之间的第一个附加边 the first appended edges (FAE)。这种情况是通过 G1 的 FAE 检查的。
在 G 和 G1 之间生成分区间边后PSSFS 合并所有已解释的状态。我们省略了如何合并的细节因为从定义上看它很简单。
现在我们解释如何并行化传递归约。我们可以使用任何支持局部传递归约和分层合并的并行传递归约算法。为了计算 GIT[OT] 的传递归约 GIT[OT]我们需要计算传递闭包 transitive closure GIT[OT]。这里当且仅当 GIT[OT] 中有一条从 到 ′ 的路径时边 (, ′) ∈ (GIT[OT] )。
对于每个顶点我们需要维护一组可到达的顶点作为状态。在合并阶段需要更新合并依赖关系图的传递闭包因为会额外生成分区间边。我们不需要更新 VR 中所有顶点的状态而是需要更新 1) SCR 中的请求、2) 每个 的第一个提交请求、3) 在第一个访问 的提交请求之前访问 的每个对象 的非提交请求以及 4) 每个会话的第一个和最后一个请求的状态。仅更新这些顶点的状态就足够了因为在合并阶段这些顶点之间会生成额外的边。第 7 节中的实验表明我们高效的合并策略的开销可以忽略不计。 7 实验
我们的实验目标如下。SSFS(G) 表示具有依赖关系图 G 的 SSFS。
• 对于各种工作负载包括实际工作负载SSFS 始终显著优于 RBSS第 7.2 至 7.3 节。 • SSFS(GIT[OT]) 在效率和大小方面均优于具有其他依赖关系图的 SSFS第 7.2 至 7.4 节。 • PSSFS 实现了几乎线性的加速第 7.5 节。
7.1 实验设置
工作负载。我们使用两个 OLTP 基准因为我们的主要客户工作负载是 OLTPTPCC [1] 和 SD 基准 [4]。这些基准是具有代表性的模拟了我们的客户工作负载。TPC-C 基准是一个标准的 OLTP 基准它模拟了一家拥有仓库的批发公司。我们将仓库数量设置为 100。数据库由九个表组成。在第 7.2 节中我们按仓库 ID 对表进行分区以显示每个表分区都是一个对象的情况。SD 基准模拟了包含六个交易的销售和分销场景。每个交易都涉及几个对话步骤 [24]。我们使用 SD 基准的 3 层架构版本。我们改变应用程序服务器实例的数量来改变会话的数量。我们使用 5000 个用户和一秒的思考时间。SD 基准的实验结果显示出与 TPC-C 相似的趋势。由于篇幅限制我们省略了它们并鼓励读者参考我们的技术论文以获取更多信息 [7]。我们还使用了大规模的真实客户工作负载该工作负载是从真实的基于云的业务应用系统中捕获的该系统主要用于处理企业的采购业务。它捕获了 18 分钟有来自 7,393 个会话的 890 万个请求。访问了 2,812 个表33% 的事务包含更新。写入事务平均包含 9.3 个未提交请求其中 INSERT、SELECT、UPDATE、DELETE 和 MERGE_INTO 语句分别占 60%、29%、8.5%、1.5%、1%。写入事务平均访问 4.2 个表并更新 2.7 个表。只读事务平均包含 1.4 个未提交请求读取 2.2 个表。
运行环境。我们在一台 Linux 机器上进行了实验该机器有四个 Intel® Xeon® CPU E7-8880 v4 CPU、1TB RAM 和一个 745GB SSD。除第 7.5 节外我们对所有实验都使用了单线程。
测量。我们测量了经过的时间并将其细分为边生成和传递归约时间。我们使用边的数量来报告依赖图的大小。我们还提供了由传递归约生成的最小依赖图的大小标记为 TR。捕获的事务数可能会随着给定的捕获持续时间而变化。因此我们根据捕获的事务数对测量值进行了标准化。对于 SSFS我们还测量了状态的内存消耗。表 3 总结了实验参数其范围和默认值以粗体标记。在这里我们根据 [28] 使用 30 分钟作为默认捕获持续时间。超时标记为 TO设置为 10 小时。为了分析日志记录粒度的权衡我们报告了不同数量的表分区的端到端时间细分包括捕获时间、依赖图生成时间、重放时间和重放的预处理/后处理时间即导入语句和导出结果。 竞争对手。我们使用增强版的 RBSS、RBSS 和 RBSSL其表现优于 RBSS。RBSS 生成无 IT 图而不是 GRBSS。为了找到 在第 4 节中RBSS 会向后扫描直到找到具有传入边的请求。与 SSFS 不同由于在捕获的工作负载中执行 DB 恢复任务例如表初始化的会话很短RBSS 变得明显更慢对于 RBSS 而言在这样的会话中查找传入边的成本很高。为了进行公平的比较我们允许所有算法忽略这些会话。RBSSL 是 RBSS 的优化版本它通过记忆 RBSS 的 LAE 表尽管这种记忆是我们技术的一部分。RBSSL 使用 LAE 在 (1) 中找到 。
我们并行化 RBSS 和 RBSSLPRBSS 和 PRBSSL。给定一对会话′RBSS 依次生成从 到 ′ 的边。不同会话对的边并行生成。对于传递归约我们使用水平分区如 PSSFS 中一样。
7.2 TPC-C 的实验结果 不同的捕获持续时间 图 8a 和 9a 分别显示了 TPC-C 中不同捕获持续时间的经过时间和边集大小。图 9a 经验性地证实了第 3 节中维恩图中的包含关系。所有算法的经过时间都随着捕获持续时间线性增加。就耗时而言SSFS(GIT[OT]) 的表现比 SSFS(GIT)、SSFS(GOT)、SSFS(GOTIT)、RBSS 和 RBSSL 分别高出 1.6、1.6、1.4、20.9 和 15.9。这是因为 SSFS(GIT[OT]) 的大小仅比最小依赖图大 5%并且同时实现了图的紧凑性和算法的效率。就边生成时间而言SSFS(GOT) 是 SSFS 中最慢的这是因为 1) 将候选源顶点插入临时表和 2) 执行昂贵的分组操作如第 5.3 节中分析的那样的开销。传递减少时间几乎与边集大小成正比。
客户端数量变化 图 8b 和 9b 分别显示了 TPC-C 中客户端数量变化的耗时和边集大小。随着客户端数量的增加会话数量也会增加。RBSS 和 RBSSL 的耗时随着客户端数量的增加而超线性增加。SSFS(GIT[OT]) 和 SSFS(GOT) 的耗时随着客户端数量的增加而缓慢增加因为 | εOT | 无论客户端数量如何都几乎保持不变如图 9b 所示。SSFS(GOTIT) 和 SSFS(GIT) 的耗时几乎线性增加因为这些算法中每个请求的传入边的数量也线性增加。它们的依赖图的大小线性增加如图 9b 所示。
表分区数量变化 图 8c 和 9c 分别显示了表分区数量变化的耗时和边集大小。随着表分区数量的增加RBSS 和 RBSSL 的耗时会增加因为第 4 节中的 会因分区数量的改变而减小。SSFS(GIT[OT]) 的耗时几乎保持不变因为 | εOT | 也几乎保持不变。相反SSFS(GIT) 的耗时会减少因为 | εIT | 也会减少。随着表分区数量的增加| εIT | 会减少因为 εcol 的大小会减小。这解释了为什么随着分区数量的增加SSFS(GIT) 的耗时会略有减少。但是| εOT | 几乎保持不变因为当对象数量增加时对象传递路径修剪边的概率会降低。SSFS(GIT[OT]) 是最快的优于其他依赖图的 SSFS。这是因为它的边集大小几乎接近 TR并且生成 GIT[OT] 的成本最便宜如第 5 节所述。 端到端时间细分 图 10 显示了 TPC-C 中表分区数变化时 SSFS(GIT[OT])、RBSS 和 RBSSL 的端到端时间细分。重放时间受表分区数和客户端数的影响。在图 10a 中没有分区的重放时间比捕获时间长 25%。这是因为表级日志记录中的人为依赖关系会导致重放速度变慢。但是随着表分区数增加到 64 个重放时间比捕获时间快 26%因为访问不同分区的请求可以并行重放。在图 10b 中随着重放并发性随着 256 个客户端的增加而增加重放时间比捕获时间快 58%。这种现象解释如下。在捕获时间内随着客户端数量从 64 个增加到 256 个捕获吞吐量仅增加 5%因为写入冲突也会增加。然而如第 3.6 节所述由于重放期间不会发生写冲突因此当客户端数量从 64 个增加到 256 个时重放吞吐量会增加 67%。RBSS 和 RBSSL 的依赖图生成时间分别占端到端总时间的 89% 和 86%这是瓶颈。
εcol 的大小 表 4 显示了 | VR |、| εcol | 和 | ε |这些结果适用于改变捕获持续时间和表分区数。我们省略了改变客户端数量的结果因为趋势没有变化。在所有情况下εcol 中的冗余边数即 | εcol − ε |都比 | ε | 大至少五个数量级。因此由于图 9 中 εOTIT 的平均边数仅比 ε 多 8%因此超过 99% 的冗余边因 IT 和 OT 而被修剪。这表明两种类型的冗余非常普遍。其他工作负载也显示出类似的趋势。 7.3 真实客户工作负载的实验结果 图 11 显示了大规模真实客户工作负载中的已用时间和边集大小。在图 11a 中边生成时间的趋势与具有 128 个客户端的 TPC-C 的趋势相似。请注意在 TPC-C 中客户端数量是已用时间的主要因素而不是表分区数量。SSFS(GOT) 和 SSFS(GOTIT) 的边生成时间比其他的长 2-3 倍就像在具有 128 个客户端的 TPC-C 中一样。RBSS 和 RBSSL 达到超时。传递减少时间与边集大小成正比。在图 11b 中边集大小的趋势与具有 64 个表分区的 TPC-C 的趋势相似。GOT 最大因此 SSFS(GOT) 的传递减少比其他图表长三倍多。虽然 |εIT|比 |εOT| 小 7.8 倍SSFS(GIT) 的边生成时间比 SSFS(GOT) 慢两倍多。这是因为 SSFS(GIT) 首先从 SCR 扫描 IT(0)-free 图的候选然后使用 LAE 修剪具有 k-forward 路径的边。SSFS(GIT) 中从 SCR 扫描的候选数量比 SSFS(GOT) 中从 OTC 扫描的候选数量大四倍。SSFS(GIT[OT]) 在效率和紧凑性方面仍然最好。
7.4 内存使用情况 表 5 显示了 TPC-C 默认配置、具有 64 个表分区的 TPC-C表示为 TPC-C64以及大规模真实客户工作负载下 SSFS 中状态的内存使用情况具体取决于依赖关系图的类型。在默认配置的 TPC-C 中除 SSFS(GOT) 外状态占用的内存不到 100 kB。但是SSFS(GOT) 的内存消耗明显更高。这是因为当存在未修改的表例如 TPC-C 中的 ITEM 表时SSFS(GOT) 中的 OTC 会无限增长。与 SSFS(GOT) 不同SSFS(GIT[OT]) 和 SSFS(GOTIT) 中的 OTC 为每个会话最多存储一个顶点因此它们的 OTC 的内存使用量限制为 (| | · ||)。在 TPC-C64 中随着 || 的增加状态的内存使用量最多增加 32 倍。状态所需的最大空间仅为 269 MB。在具有 7,393 个会话的大规模实际客户工作负载中状态的内存使用量最多增加 1 GB。请注意SCR 和 LAE 的空间复杂度为 (| | · ||) 和 (||2)。因此SSFS(GIT[OT]) 消耗的内存比 SSFS(GIT) 和 SSFS(GOTIT) 少因为它不维护 SCR。对于这两种工作负载SSFS(GIT[OT]) 都需要现代服务器系统中可管理的状态大小。
7.5 PSSFS 的可扩展性 图 12 显示了通过改变 TPC-C 中的线程数PSSFS(GIT[OT])、PRBSS 和 PRBSSL 与串行 SSFS(GIT[OT]) 相比的加速比。加速比定义为串行 SSFS(GIT[OT]) 的耗时与并行算法的耗时之比。随着线程数量的增加PSSFS 实现了几乎线性的加速合并阶段的开销最小。
虽然 PRBSS 和 PRBSSL 实现了几乎线性的加速但 PSSFS(GIT[OT]) 的平均性能比它们高出 17.2 倍和 12.4 倍。由于趋势相似我们省略了其他工作负载的结果。
8 相关工作
数据库重放的概念最早是在 [20] 中提出的。它提供了一种比必要更严格的同步机制导致并发性较低且性能较差。
Morfonios 等人[28] 通过提出 RBSS 增强了此模式。我们证明 RBSS 生成了 GIT(0) 和 GIT(1) 之间的依赖关系图。Snowtrail [38] 专注于使用不同的云实例无缝执行生产查询而不会干扰云环境中客户的生产工作负载。Snowtrail 的重放机制类似于 Oracle Database Replay [20]。这些技术会生成许多冗余边随后通过昂贵的传递归约进行修剪。
Flex [11] 是一个用于测试和调整生产数据库实例的原型系统。Flex 主要加载特定快照 并在 上执行操作例如用户定义的可执行文件不支持细粒度的工作负载重放。
Doppler [12] 是一个用于将本地数据平台迁移到平台即服务 (PaaS) 产品的推荐引擎。然而Doppler 并不利用工作负载信息而是利用基本信息进行推荐性能计数器、所有可能的云目标库存单位 (Stock Keeping UnitsSKU) 以及每个 SKU 的实时定价。然后它依靠机器学习模型来推荐合适大小的 SKU。相反DRS 专注于细粒度的工作负载信息以便安全地迁移到新的数据库版本或硬件。虽然这些努力与我们的方法正交但我们相信我们的工作是对它们的补充。
Diametrics [13] 是一个用于端到端基准测试和查询引擎性能监控的框架。它专注于对各种查询引擎进行可重复的基准测试而不是诊断任何软件/硬件升级所面临的性能问题。TROD [26] 是一个用于调试 Web 应用程序的框架。它捕获并按顺序重新运行事务以重现错误。
记录一般程序的运行并使用日志重放以调试非确定性故障已被广泛研究 [10, 29, 30]。[10] 利用一致性放松来调试多核环境中的数据竞争。[29] 提出了一种近似重放系统该系统将程序生成的一系列事件划分为事务然后在事务级别记录冲突的操作。然而这种方案不能保证正确的重放而这在我们的目标应用程序中至关重要。[30] 利用硬件辅助虚拟化扩展来实现基于软件的确定性重放系统。但是所有这些方法都是针对一般程序的在记录共享内存上的所有冲突操作时会产生大量开销。但是DRS 是专为数据库工作负载设计的定制重放系统。
有利用依赖关系图来并行化恢复的恢复系统 [27]。自适应日志记录 [40] 需要捕获每个事务的读写集中的所有元组 ID扫描操作的数量可能很大。与我们相比这可能导致edge生成的大量开销。在我们的生产系统中维护所有读/写集也是一项挑战。即使自适应日志记录使用更粗的粒度重放生成的依赖关系图也不能保证快照隔离中的输出确定性这是 DRS 中最重要的要求。在 [40] 中每个节点代表一个事务即存储过程调用。考虑两个事务 1 和 2它们在捕获阶段同时访问包含元组 1 和 2 的公共表。假设1 读取12 读取2。1 分别使用它们读取的值写入22 写入1。此外1 在2 提交之前提交即写入偏差。然后在生成的依赖图中存在从1 到2 的边。因此自适应日志记录在1 之后重播2。但是与捕获期间捕获的数据库状态相比这会导致不同的数据库状态。这将在我们的 DRS 中报告为错误。请注意这不是问题因为事务是在 H-store自适应日志记录的底层 DBMS中串行执行的。Pacman [37] 使用程序分析技术构建依赖图。然而Pacman 假设所有事务都作为存储过程实现并且是提前知道的这严重限制了用户应用程序并使其无法用于一般 DRSs。
还有四种类型的依赖图所有这些依赖图生成算法都不能轻易应用于我们的 DRSG1由锁管理器管理的用于死锁检测的依赖图 [19, 36]G2用于在应用的弱隔离级别下检测给定事务工作负载中可能出现的异常的依赖图 [21, 25]G3用于调度事务以减少运行时冲突的依赖图 [15–17, 35]以及G4用于使副本与主数据库一致的依赖图 [23]。通过将每个事务与图中的所有现有事务进行比较在副本上动态生成依赖图。这里一个节点对应于一个事务而不是一个请求。即使依赖图比我们的要粗得多当顶点很多时系统也会限制顶点的插入。请注意G1 和 G2 专注于查找维护的依赖图中存在的循环。G3 专注于通过重新排序待处理的请求来减少事务间冲突。 G4 仅关注复制的写入事务之间的排序而我们的 DRS 应该考虑写入和读取请求的排序。
图稀疏化是减少边集大小同时近似保留图的属性例如切割大小或顶点之间的距离的问题 [8, 18, 31, 33]。尽管某些图稀疏器例如 [33]可以在近乎线性的时间内减少图但它们不能保证保留所有必要的依赖边。但是正如我们的问题定义所述必须保留 G 中的所有边DRS 才能实现输出确定性。因此这些方法不能轻易应用于我们的问题。
9 结论
在本文中我们提出了一种全面而实用的解决方案用于数据库重放系统 (DRS) 中的快速依赖图生成。在第 3 节中我们正式提出了 DRS 的四种依赖图类型的分类。在第 4 节中我们表明由于对每个请求进行重复的向后扫描最先进技术的最坏时间复杂度为 (| VR |2)。
我们表明它的依赖图是 IT(0)-free 图和 IT(1)-free 图之间的图可能有许多冗余边。为了解决这个具有挑战性的问题在第 5 节中我们提出了一种新颖的依赖关系生成算法 SSFS通过简洁地维护生成边所需的信息来扫描一次请求。我们在领先的商业 DBMS 中实现了我们的解决方案。使用我们的 DRS 进行的实验表明与最先进的技术相比它将依赖关系图生成时间显著缩短了两个数量级。
致谢
作者要感谢 Jaehyun Lim 帮助进行 TPC-C 基准的实验设置。这项工作得到了韩国政府 (MSIT) 资助的韩国国家研究基金会 (NRF) 拨款 (编号 NRF-2021R1A2B5B03001551)。
REFERENCES
[1] 2010. TPC Benchmark C. http://www.tpc.org/tpcc/. Accessed: 2022-06-23. [2] 2020. Oracle Database 19c: Real Application Testing Overview. Technical Report. [3] 2022. Capturing and Replaying Workloads. https://help.sap.com/docs/SAP_HANA_COCKPIT/afa922439b204e9caf22c78b6b69e4f2/4f3c88249d484b0faba0e6b27b82c2dd.html?localeen-US [4] 2022. SAP Standard Application Benchmarks. https://www.sap.com/about/benchmark.html. [5] 2022. Sql server distributed replay. https://learn.microsoft.com/en-us/sql/tools/distributed-replay/sql-server-distributed-replay?viewsql-server-ver16 [6] 2023. The Internals of PostgreSQL. https://www.interdb.jp/. Accessed: 2023-10-20. [7] 2023. Technical Report. https://sites.google.com/view/systemx-replay [8] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2012. Graph sketches: sparsification, spanners, and subgraphs.In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems. ACM, Scottsdale Arizona USA, 5–14. https://doi.org/10.1145/2213556.2213560 [9] Alfred V. Aho, Michael R Garey, and Jeffrey D. Ullman. 1972. The transitive reduction of a directed graph. SIAM J.Comput. 1, 2 (1972), 131–137. [10] Gautam Altekar and Ion Stoica. 2009. ODR: Output-deterministic replay for multicore debugging. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles. 193–206. [11] Nedyalko Borisov and Shivnath Babu. 2013. Rapid experimentation for testing and tuning a production database deployment. Proceedings of the 16th International Conference on Extending Database Technology, 125–136. [12] Joyce Cahoon, Wenjing Wang, Yiwen Zhu, Katherine Lin, Sean Liu, Raymond Truong, Neetu Singh, Chengcheng Wan, Alexandra Ciortea, Sreraman Narasimhan, and Subru Krishnan. 2022. Doppler: automated SKU recommendation in migrating SQL workloads to the cloud. Proceedings of the VLDB Endowment 15, 12 (Aug. 2022), 3509–3521. https://doi.org/10.14778/3554821.3554840 [13] Shaleen Deep, Anja Gruenheid, Kruthi Nagaraj, Hiro Naito, Jeff Naughton, and Stratis Viglas. 2021. Diametrics:benchmarking query engines at scale. ACM SIGMOD Record 50 (2021), 24–31. Issue 1. [14] Reinhard Diestel. 2005. Graph theory 3rd ed. Graduate texts in mathematics 173 (2005), 33. [15] Bailu Ding, Lucja Kot, and Johannes Gehrke. 2018. Improving optimistic concurrency control through transaction batching and operation reordering. Proceedings of the VLDB Endowment 12, 2 (2018), 169–182. [16] Jose M Faleiro and Daniel J Abadi. 2014. Rethinking serializable multiversion concurrency control. arXiv preprint arXiv:1412.2324 (2014). [17] Jose M Faleiro, Daniel J Abadi, and Joseph M Hellerstein. 2017. High performance transactions via early write visibility. Proceedings of the VLDB Endowment 10, 5 (2017). [18] Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi. 2011. A general framework for graph sparsification. In Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, San Jose California USA, 71–80. https://doi.org/10.1145/1993636.1993647 [19] Donald Fussell, Zvi M Kedem, and Abraham Silberschatz. 1981. Deadlock removal using partial rollback in database systems. In Proceedings of the 1981 ACM SIGMOD international conference on Management of data. 65–73. [20] Leonidas Galanis, Supiti Buranawatanachoke, Romain Colle, Benoît Dageville, Karl Dias, Jonathan Klein, Stratos Papadomanolakis, Leng Leng Tan, Venkateshwaran Venkataramani, Yujun Wang, et al. 2008. Oracle database replay. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data. 1159–1170. [21] Yifan Gan, Xueyuan Ren, Drew Ripberger, Spyros Blanas, and Yang Wang. 2020. IsoDiff: debugging anomalies caused by weak isolation. Proceedings of the VLDB Endowment 13, 12 (2020). [22] Herodotos Herodotou, Nedyalko Borisov, and Shivnath Babu. 2011. Query optimization techniques for partitioned tables. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. ACM, Athens Greece,49–60. https://doi.org/10.1145/1989323.1989330 [23] Chuntao Hong, Dong Zhou, Mao Yang, Carbo Kuo, Lintao Zhang, and Lidong Zhou. 2013. KuaFu: Closing the parallelism gap in database replication. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE,1186–1195. [24] Bahman Javadi Isfahani. 2017. Evaluating a modern in-memory columnar data management system with a contemporary OLTP workload. (2017). [25] Kyle Kingsbury and Peter Alvaro. 2020. Elle: inferring isolation anomalies from experimental observations. Proceedings of the VLDB Endowment 14, 3 (Nov. 2020), 268–280. https://doi.org/10.14778/3430915.3430918 [26] Qian Li, Peter Kraft, Michael Cafarella, Çağatay Demiralp, Goetz Graefe, Christos Kozyrakis, Michael Stonebraker, Lalith Suresh, and Matei Zaharia. 2023. Transactions Make Debugging Easy… In CIDR. [27] Arlino Magalhaes, Jose Maria Monteiro, and Angelo Brayner. 2022. Main Memory Database Recovery: A Survey.Comput. Surveys 54, 2 (March 2022), 1–36. https://doi.org/10.1145/3442197 [28] Konstantinos Morfonios, Romain Colle, Leonidas Galanis, Supiti Buranawatanachoke, Benoît Dageville, Karl Dias, and Yujun Wang. 2011. Consistent synchronization schemes for workload replay. Proceedings of the VLDB Endowment 4, 12 (2011), 1225–1236. [29] Ernest Pobee, Xiupei Mei, and Wing Kwong Chan. 2019. Efficient transaction-based deterministic replay for multithreaded programs. In Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering.760–771. [30] Shiru Ren, Le Tan, Chunqi Li, Zhen Xiao, and Weijia Song. 2017. Leveraging hardware-assisted virtualization for deterministic replay on commodity multi-core processors. IEEE Trans. Comput. 67, 1 (2017), 45–58. [31] Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. 2011. Local graph sparsification for scalable clustering. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. ACM, Athens Greece, 721–732. https://doi.org/10.1145/1989323.1989399 [32] Klaus Simon. 1988. An improved algorithm for transitive closure on acyclic digraphs. Theoretical Computer Science 58,1-3 (1988), 325–346. [33] Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing.ACM, Chicago IL USA, 81–90. https://doi.org/10.1145/1007352.1007372 [34] Xian Tang, Junfeng Zhou, Yaxian Qiu, Xiang Liu, Yunyu Shi, and Jingwen Zhao. 2020. One Edge at a Time: A Novel Approach Towards Efficient Transitive Reduction Computation on DAGs. IEEE Access 8 (2020), 38010–38022. [35] Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J Abadi. 2012. Calvin: fast distributed transactions for partitioned database systems. In Proceedings of the 2012 ACM SIGMOD international conference on management of data. 1–12. [36] Gerhard Weikum and Gottfried Vossen. 2001. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Elsevier. [37] Yingjun Wu, Wentian Guo, Chee-Yong Chan, and Kian-Lee Tan. 2017. Fast Failure Recovery for Main-Memory DBMSs on Multicores. In Proceedings of the 2017 ACM International Conference on Management of Data. ACM, Chicago Illinois USA, 267–281. https://doi.org/10.1145/3035918.3064011 [38] Jiaqi Yan, Qiuye Jin, Shrainik Jain, Stratis D Viglas, and Allison Lee. 2018. Snowtrail: Testing with production queries on a cloud database. Proceedings of the Workshop on Testing Database Systems, 1–6. [39] C-Q Yang and Barton P Miller. 1988. Critical path analysis for the execution of parallel and distributed programs. In The 8th International Conference on Distributed. Computing Systems, 366–367. [40] Chang Yao, Divyakant Agrawal, Gang Chen, Beng Chin Ooi, and Sai Wu. 2016. Adaptive Logging: Optimizing Logging and Recovery Costs in Distributed In-memory Databases. In Proceedings of the 2016 International Conference on Management of Data. ACM, San Francisco California USA, 1119–1134. https://doi.org/10.1145/2882903.2915208
