EagleBear2002 的博客

摘要

流行的隔离级别多版本读已提交 (RC) 牺牲了一些强大的可串行化保证，以换取更高的事务吞吐量。有时，事务工作负载可以在 RC 下安全地执行，从而以较低的 RC 成本获得可串行化。这种工作负载被称为对 RC 具有鲁棒性。先前的研究已经产生了一种可处理的程序，用于确定由事务程序建模为事务模板生成的工作负载对 RC 的鲁棒性。这项工作的一个重要见解是，通过更准确地建模事务程序，我们能够将更大的工作负载集识别为鲁棒的。在这项工作中，我们通过为事务模板扩展功能约束来提高其建模能力，这对于捕获外键等数据依赖关系非常有用。我们表明，加入功能约束可以将更多原本不具有鲁棒性的工作负载识别为鲁棒的。尽管我们确定鲁棒性问题在其最一般的形式下变得不可判定，但我们表明，对功能约束的各种限制会导致可判定甚至可处理的片段，这些片段可用于为现实场景建模和测试对 RC 的鲁棒性。

作者：

• Brecht Vandevoort, UHasselt, Data Science Institute, ACSL, Belgium
• Bas Ketsman, Vrije Universiteit Brussel, Belgium
• Christoph Koch, École Polytechnique Fédérale de Lausanne, Switzerland
• Frank Neven, UHasselt, Data Science Institute, ACSL, Belgium

摘要

流行的隔离级别多版本读已提交（RC）用牺牲强大的可串行化保证来换取事务吞吐量的提高。尽管如此，事务工作负载有时可以在 RC 下执行，同时仍能以较低的成本保证可串行化。这样的工作负载被称为对 RC 具有鲁棒性。本文概述了确定对 RC 的鲁棒性。特别是，我们讨论了如何通过事务模板的形式化来获得合理完整的测试。然后，我们通过使用功能约束来扩展事务模板，从而提高其建模能力，这些功能约束可用于捕获外键等数据依赖关系。我们表明，加入功能约束可以将更多的工作负载识别为鲁棒的，而不是其他情况。即使鲁棒性问题在其最一般的形式下变得不可判定，我们仍确定对功能约束的各种限制会导致可判定甚至可处理的结果，这些结果可用于对实际场景的 RC 鲁棒性进行建模和测试。

作者：

• Brecht Vandevoort, UHasselt, Data Science Institute, ACSL, Belgium
• Bas Ketsman, Vrije Universiteit Brussel, Belgium
• Christoph Koch, École Polytechnique Fédérale de Lausanne, Switzerland
• Frank Neven, UHasselt, Data Science Institute, ACSL, Belgium

INTRODUCTION

摘要

事务处理是大多数数据库应用程序的核心部分。虽然可序列化性仍然是理想事务语义的黄金标准，但许多数据库系统通过选择较低的隔离级别来提高事务吞吐量，但代价是引入潜在的异常。事务通常不是任意的，而是受到在应用程序级别定义的一组事务程序的约束（例如 TPC-C 的情况），这意味着并非所有潜在异常都能有效实现。本文的核心问题是：在特定事务程序的上下文中，何时隔离级别低于可序列化性，才能提供与可序列化性相同的保证？我们将后者称为稳健性问题。本文调查了针对（多版本）读取提交的稳健性测试的最新结果，重点关注完整条件而非充分条件。我们展示了如何将稳健性测试提升到事务模板和程序以增加实际适用性。我们讨论了未解决的问题并强调了未来研究的有希望的方向。

作者：

• Brecht Vandevoort, UHasselt, Data Science Institute, ACSL, Belgium
• Bas Ketsman, Vrije Universiteit Brussel, Belgium
• Christoph Koch, École Polytechnique Fédérale de Lausanne, Switzerland
• Frank Neven, UHasselt, Data Science Institute, ACSL, Belgium

INTRODUCTION

摘要

快照隔离 (SI) 是一种多版本并发控制算法，最早由 Berenson 等人 [1995] 描述。SI 之所以有吸引力，是因为它提供了一种可以避免许多常见并发异常的隔离级别，并且已由 Oracle 和 Microsoft SQL Server 实现（有一些细微的差别）。SI 并不保证在所有情况下都可序列化，但例如，TPC-C 基准测试应用程序 [TPC-C] 在 SI 下执行时不会出现序列化异常。所有主要数据库系统产品都提供默认的非序列化隔离级别，这些级别通常比 SI 更常遇到序列化异常，我们怀疑许多大型站点每天都会因此发生大量隔离错误，导致数据仓库应用程序中有时会出现损坏的数据。较低隔离级别的经典理由是，当应用程序被证明不会导致严重错误时，可以在这些级别下运行以提高效率，但供应商很少或根本没有向应用程序程序员和 DBA 提供有关如何避免此类错误的指导。本文提出了一种理论，用于描述在 SI 下何时会出现应用程序的非序列化执行。在文章的最后，我们将应用该理论来证明 TPC-C 基准测试应用程序在 SI 下没有序列化异常，然后讨论如何将此证明推广到其他应用程序。我们还讨论了如何修改在 SI 下不可序列化的应用程序的程序逻辑，以保证可序列化性。

作者：

• ALAN FEKETE, University of Sydney
• DIMITRIOS LIAROKAPIS, ELIZABETH O’NEIL, and PATRICK O’NEIL, University of Massachusetts
• DENNIS SHASHA, Courant Institute

MOTIVATION AND PRELIMINARIES

\[ \def\T{\mathcal{T}} \def\P{\mathcal{P}} \]

摘要

数据库客户程序鲁棒性问题是数据库一致性领域的一个分支，是验证客户程序在弱一致性模型下的执行结果是否一定会满足某个强隔离级别（一般是 SER）。

本文梳理了数据库客户程序鲁棒性问题领域的现有工作成果并形成综述。本文还整理了 Vandevoort、Gotsman 和 Enea 等人在鲁棒性问题上的贡献。

现有工作综述

\[ \def\po{\mathsf{\textcolor{black}{po}}} \def\so{\mathsf{\textcolor{purple}{so}}} \def\sfwr{\mathsf{\textcolor{green}{wr}}} \def\ww{\mathsf{\textcolor{red}{ww}}} \def\rw{\mathsf{\textcolor{blue}{rw}}} \def\rf{\mathsf{\textcolor{green}{rf}}} \def\mo{\mathsf{\textcolor{orange}{mo}}} \def\rb{\mathsf{\textcolor{red}{rb}}} \def\sc{\mathsf{\textcolor{purple}{sc}}} \]

摘要

Executions

Events 分为四种：Reads, Writes, Updates, Fences

事件间的关系有：

In computing, a memory model describes the interactions of threads through memory and their shared use of the data.

Sequential Consistency (SC) Model [Lamport 1979]

• No muticore processor implements SC
• Compiler optimizations invalidate SC

Weak/Relaxed Memory Models

并发性和正确性

并发对象的正确性往往不容易描述。

如果能将并发执行转化为顺序执行，则只需对该顺序执行进行分析，从而简化了并发对象的分析。

顺序对象

每个对象都有一个状态，通常由一组字段（field）给出。队列示例：项目序列。

Using Locks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Counter {
	private long value;
	private Lock lock;

	public long getAndIncrement() {
		lock.lock(); // acquire lock
		try { // critical section
			int temp = value;
			value = value + 1;
		} finally {
			lock.unlock(); // release lock, no matter what
		}
		return temp;
	}
}

两个 Liveness

避免死锁 Deadlock-Free：如果某个线程调用 lock()，并且从不返回，那么其他线程必须无限次地完成 lock() 和 unlock() 调用。整个系统都会取得进展，即使某个线程饿死。

避免饿死 Starvation-Free：如果某个线程调用 lock()，它最终会返回，各个线程取得进展。

Amdahl's Law

\[ Speedup = \frac{\text{1-thread execution time}}{\text{n-thread execution time}} \\ = \frac{1}{1 - p + \frac{p}{n}} \]

其中 p 是并发执行的代码在所有代码中的比例。

Safety & Linvness 安全性和活跃性

liveness 在中文版教材中被翻译为演进条件。