EagleBear2002 的博客

摘要

事务处理是大多数数据库应用程序的核心部分。虽然可序列化性仍然是理想事务语义的黄金标准，但许多数据库系统通过选择较低的隔离级别来提高事务吞吐量，但代价是引入潜在的异常。事务通常不是任意的，而是受到在应用程序级别定义的一组事务程序的约束（例如 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}} \def\WR{\mathsf{WR}} \def\WW{\mathsf{WW}} \def\RW{\mathsf{RW}} $$

摘要

数据库客户程序鲁棒性问题是数据库一致性领域的一个分支，是验证客户程序在弱隔离级别下的行为在多大程度上满足某个强隔离级别（一般是 SER）。鲁棒性常被分为动态鲁棒性和静态鲁棒性两个层次来讨论。

• 动态鲁棒性研究数据库的某一个弱隔离级别 $I_1$ 下的执行历史 $H$ 是否满足较强的隔离级别 $I_2$（一般是 SER）。如果满足，我们说 $H$ 在 $I_1$ 下是鲁棒的。动态鲁棒性的研究与执行历史验证较为相似。
• 静态鲁棒性研究客户程序 $P$ 在弱隔离级别 $I_1$ 下的所有执行历史是否都满足较强的隔离级别 $I_2$（一般是 SER）。如果满足，我们说 $P$ 在 $I_1$ 下是鲁棒的。例如，如果 $P$ 在 SI 下鲁棒，则我们可以在 SI 下运行 $P$，这可以在保证执行历史满足 SER 的情况下提高系统性能和吞吐率。

现有工作综述

$$ \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 在中文版教材中被翻译为演进条件。

为贯彻落实党的二十大作出的战略部署，二十届中央委员会第三次全体会议研究了进一步全面深化改革、推进中国式现代化问题，作出如下决定。

进一步全面深化改革、推进中国式现代化的重大意义和总体要求

（1）进一步全面深化改革的重要性和必要性。改革开放是党和人民事业大踏步赶上时代的重要法宝。党的十一届三中全会是划时代的，开启了改革开放和社会主义现代化建设新时期。党的十八届三中全会也是划时代的，开启了新时代全面深化改革、系统整体设计推进改革新征程，开创了我国改革开放全新局面。

以习近平同志为核心的党中央团结带领全党全军全国各族人民，以伟大的历史主动、巨大的政治勇气、强烈的责任担当，冲破思想观念束缚，突破利益固化藩篱，敢于突进深水区，敢于啃硬骨头，敢于涉险滩，坚决破除各方面体制机制弊端，实现改革由局部探索、破冰突围到系统集成、全面深化的转变，各领域基础性制度框架基本建立，许多领域实现历史性变革、系统性重塑、整体性重构，总体完成党的十八届三中全会确定的改革任务，实现到党成立一百周年时各方面制度更加成熟更加定型取得明显成效的目标，为全面建成小康社会、实现党的第一个百年奋斗目标提供有力制度保障，推动我国迈上全面建设社会主义现代化国家新征程。

（2024 年 7 月 18 日中国共产党第二十届中央委员会第三次全体会议通过）

中国共产党第二十届中央委员会第三次全体会议，于 2024 年 7 月 15 日至 18 日在北京举行。

出席这次全会的有，中央委员 199 人，候补中央委员 165 人。中央纪律检查委员会常务委员会委员和有关方面负责同志列席会议。党的二十大代表中部分基层同志和专家学者也列席了会议。

全会由中央政治局主持。中央委员会总书记习近平作了重要讲话。

全会听取和讨论了习近平受中央政治局委托所作的工作报告，审议通过了《中共中央关于进一步全面深化改革、推进中国式现代化的决定》。习近平就《决定（讨论稿）》向全会作了说明。