交易内存原理概览：故障 tolerant 协议与分布式系统设计

需积分: 10 111 浏览量更新于2024-07-31 收藏 1.46MB PDF 举报

《事务内存原理》是一本由Rachid Guerraoui和Michał Kapałka共同编写的简短著作，它深入探讨了事务内存的核心概念和技术。事务内存是一种编程模型，它允许并发线程在共享数据上执行一系列操作，仿佛它们是独立的原子操作，即使在存在竞争条件的情况下也能保证数据一致性。该书旨在为程序员和系统设计者提供理解并利用事务内存进行并发控制的关键原则。在分布式计算领域，事务内存是实现并发控制的一种重要工具，尤其是在大规模并行系统和分布式环境中。《分布式计算合成讲座》系列，由麻省理工学院的Nancy Lynch编辑，涵盖了分布式计算理论的广泛议题，包括但不限于分布式算法设计、容错协议、形式建模和验证、以及并发数据结构的设计。这些讲座旨在紧跟顶级计算机科学会议，如ACM PODC、DISC、SPAA、OPODIS、CONCUR、DialM-POMC、ICDCS、SODA、Sirocco和SSS等会议的研究前沿。《事务内存原理》这本书可能会讲解以下核心知识点： 1. **事务定义与特性**：事务通常包括原子性（atomicity）、一致性（consistency）、隔离性（isolation）和持久性（durability），这些属性确保了并发操作的正确性和可靠性。 2. **硬件支持与软件实现**：介绍如何在现代多核处理器和分布式系统中实现事务，包括内存屏障（memory fences）、锁机制（lock-free algorithms）和软件交易（software transactional memory, STM）。 3. **死锁避免与恢复**：讨论如何通过预判、循环检测或乐观并发控制策略来防止死锁，以及在出现故障后如何恢复事务状态。 4. **可扩展性和性能优化**：研究如何通过分段事务、超时管理和优化调度来提高系统的吞吐量和响应时间。 5. **并发数据结构**：事务内存如何影响和优化传统数据结构（如队列、栈和哈希表）在并发环境中的性能。 6. **跨层协调**：涉及分布式环境中的事务管理，如两阶段提交协议（2PC）和乐观并发控制协议（OCC）的比较。 7. **故障模型与容错性**：讨论不同类型的故障模型（例如拜占庭故障模型），以及如何在事务内存下处理故障和网络不一致。 8. **应用实例**：书中可能会提供实际应用案例，比如数据库系统、并行计算框架和云计算环境中的事务内存使用。通过阅读这本书，读者可以深入了解事务内存技术在解决分布式系统中的并发控制问题中的关键作用，并为实际项目开发和系统设计提供理论基础和实践经验。

CHAPTER 1

Introduction

Those are my principles.

If you don’t like them I have others.

Groucho Marx

The clock rate of processors used to grow exponentially. Going from below 1 MHz to around

3 GHz took the computer industry less than 40 years. However, increasing the clock rate further

has become infeasible. In fact, the ubiquity of portable computers, for which power consumption is

a top concern, has forced the industry to keep the clock rate of many processors much below the

achievable maximum.

The demand for computational power,however,has not ceased to increase.The result is a com-

pletely new trend, which is commonly referred to as a “multi-core revolution”. Instead of increasing

the clock speed of processors, more computing cores are put on a single chip. Multiprocessing,which

used to be a feature of only high-end machines, has become commonplace in personal computers

and laptops. It is possible that, in the near future, mobile phones, media players, and other small

devices will become equipped with many processors.

This new trend has created a big challenge. Before, with each new processor, all existing

applications would automatically get faster. Now, applications will need to get increasingly parallel

in order to exploit the power of new processors. Therefore, parallel programming, which used to be

the domain of a few high-performance computing experts, will now have to be mastered by common

programmers.

1.1 PROBLEMS WITH EXPLICIT LOCKING

Creating threads is easy in any modern programming language. What is hard, however, is synchro-

nizing their actions, especially if one wants to make those threads run truly in parallel. Consider,

for example, an application in which threads operate on a big data structure. A simple way to en-

sure thread-safety is to protect the entire structure with a single lock (coarse-grained locking).Then,

however, all accesses to the data structure are serialized, which can severely limit the scalability of the

application. Moreover, lock contention may become a problem, especially if the number of threads

becomes high.

Optimally, one would use many locks, each protecting a small part of the data structure (ﬁne-

grained locking). But this is an engineering challenge because one has to ensure that all components

of the application follow the same locking policy. If even one method acquires locks in a wrong

2 1. INTRODUCTION

order, then a deadlock can occur. One missing lock acquisition can lead to race conditions, which are

very difﬁcult to debug. Indeed, concurrency-related programming errors often manifest themselves

only in some, possibly rare, executions, and sometimes only when the application is run with all its

debugging functions turned off. Those errors can result in effects ranging from program crashes,

which are directly visible, up to very subtle data corruption, which may pass undetected for a long

time.

The problem with following a complex locking policy in a big application is that this policy

exists only in the documentation (e.g.,comments in the code) or in the programmers’minds.Looking

just at the code of a program, written in one of the mainstream programming languages such as

Java or C++, one typically cannot tell which lock protects which objects, or in which order those

locks should be acquired. Associating a monitor with each object, as in Java, does not really help in

ﬁne-grained locking when a single monitor or lock can protect a group of objects and, conversely,

a single object can be protected by more than one lock. It thus takes a very disciplined team of

programmers to do ﬁne-grained locking right.

But even following a locking policy to the letter does not guarantee success in terms of perfor-

mance on multi-core systems. Fine-grained locking involves many trade-offs. For instance, locks are

not given for free, and acquiring them takes time. Hence, it might be hard to ﬁnd the right balance

between using too many locks, which can result in high locking overhead, and too few locks, which

can lead to scalability problems.To give a concrete example, devising an efﬁcient, scalable algorithm

that implements a thread-safe queue, a data structure almost trivial in a single-thread program, is so

hard that it deserved at least two papers in top computer science conferences [Herlihy et al., 2003b;

Michael and Scott, 1996]. We cannot expect that ordinary programmers will spend so much effort

in getting the last bit of parallelism from every part of their application, given how hard it is to do

it right.

O bviously, modern programming languages offer libraries containing highly-optimized and

thread-safe implementations of commonly used data structures. In many cases, it sufﬁces to use

those components to get a program that can make use of a few CPU cores. But here we face a

problem with composability: a data structure composed of thread-safe objects is not necessarily itself

thread-safe. For example, consider two thread-safe sets, and a problem of removing an element from

one set and then adding it to the other. Often, one wants such a composite operation involving both

sets to be atomic. That is, the intermediate step of this operation, in which an element is removed

from one of the sets but still not added to the other, should not be observed by concurrent threads.

But implementing such an operation requires either adding additional locks, which protect both sets,

or extending the locking mechanisms used by the implementations of those sets. In the former case,

one effectively devises a ne w locking policy for the two sets, which can introduce race conditions

or scalability issues. In the latter case, one has to “open” the set implementations, understand their

locking policies,and extend them,which not only is challenging,but also breaksobject encapsulation.

Using locks explicitly to handle concurrency becomes even harder when threads operate on

different pr iority lev els, e.g., in a real-time system. If a high-priority thread wants to acquire a lock

1.2. TRANSACTIONAL MEMORY 3

that is held by a low-priority thread, it has to wait until the lock is released.That is, the high-priority

thread has to wait for the low-priority thread—a problem known as priority inversion.Synchronizing

those threads using nonblocking mechanisms, i.e., without using any form of mutual exclusion, would

solve the problem. However, designing those mechanisms is sometimes even harder than using ﬁne-

grained locking.

1.2 TRANSACTIONAL MEMORY

Given the above challenges posed by the explicit use of locks to manage concurrency, it is not surpris-

ing to see a large body of research aimed at making concurrent programming easier. One of the most

appealing solutions is transactional memory (TM) [Herlihy and Moss, 1993; Shavit and Touitou,

1995]. The basic idea behind TM is to enable threads of an application to communicate by exe-

cuting lightweight, in-memory transactions. A transaction is a sequence of operations that should

be executed atomically. The purpose of a transaction is thus similar to that of a critical section.

However, unlike critical sections, transactions can abort, in which case all their operations are rolled

back and are never visible to other transactions. Also, transactions only appear as if they executed

sequentially—a TM is free to run them concurrently, as long as the illusion of atomicity is preserved.

Using a TM is, in principle, very easy: the programmer simply converts those blocks of code

that should be executed atomically into transactions. In some TMs, this can be as straightforward as

annotating functions and methods with a special language keyword (usually: atomic), as illustrated

in Figure 1.1.TheTM implementation is then responsible for executing those transactions safely and

efﬁciently.The TM might internally use ﬁne-grained locking, or some nonblocking mechanism, but

this is hidden from the programmer and the application. Thus, if the T M is implemented correctly,

which can be done once by a group of experts, the programmer is less likely to introduce concurrency

bugs in the code than if he or she had to handle locks explicitly.Indeed,a transaction is a very intuitive

abstraction that has been used with success in databases for a long time.

A TM can be implemented in hardware, in software, or as a hardware-software hybrid. The

TM API usually allows for (1) starting a transaction,(2) performing operations on shared data within

a transaction, and (3) committing or aborting a transaction. Such an interface can be provided, e.g.,

by a sof tware library. There are also experimental TM-aware compilers for languages such as Java

and C++. Those compilers automatically convert blocks of code annotated with a special keyword

(e.g., atomic) into transactions.

Even though a TM can internally use ﬁne-grained locking, the paradigm is free of problems

that explicit locking (i.e., locking used directly by the programmers) creates, and which we listed

above. First, transactions are composable. For instance, consider the problem of moving an element

between two sets. If both sets are implemented using transactions, then it sufﬁces to create another

transaction that will simply remove an element from one set and add it to the other set. Indeed,

most TM implementations allow transactions to be nested. There exists also a technique, called

transactional boosting [Herlihy and Koskinen, 2008], which allows transactions to use any thread-

safe data structure, even one not implemented using transactions.

4 1. INTRODUCTION

atomic1

v ← x.getVal;2

x.setVal(v + 1);3

Figure 1.1: An illustration of a high-level interface of a TM. The programmer annotates the block of

code that should be executed atomically with a special keyword (here:atomic).This block is then executed

as a transaction. If the transaction aborts (e.g., due to a conﬂict with another transaction), an exception

might be thrown or the block may be automatically restarted.

Second, even though transactions are not much more difﬁcult to use than coarse-grained

locking, they can execute in parallel, and so there is a hope that using a T M one can achieve perfor-

mance close to that of explicit ﬁne-grained locking. A TM also gives additional ﬂexibility because

the synchronization policy of a TM can be ﬁne-tuned to a speciﬁc system, or even changed com-

pletely. For instance, the granularity of locks used internally by a TM can be adapted to the number

of CPU cores, or the locking polic y can be replaced with a nonblocking synchronization mechanism

if priority inversion becomes an issue. All those changes are local to the TM implementation and

the code of the application does not have to be updated. This also means that programs that use a

TM for thread synchronization should be easier to maintain than ones that use explicit locking.

1.3 SCOPE OF THIS BOOK

The TM paradigm promises a lot, but it is not free of its own challenges. Some of those are: reducing

the overhead of transactions (e.g., of logs that are used during transaction rollback), dealing with

I/O and other irrevocable operations inside transactions, integrating transactions into programming

languages, providing interoperability with legacy components whose source code is no longer avail-

able, and dealing with situations in which the same data can be accessed from within transactions

and from non-transactional code. It is thus not surprising to see a large amount of research dedicated

to addressing those problems and providing practical TM implementations (see Chapter 6 for an

overview).

In order to be able to compare the various proposed TM algorithms and optimizations, we

ﬁrst need to know what a TM really is. That is, we need precise criteria according to which we can

evaluate whether a given TM is correct and whether the TM gives guarantees on a par with other

TMs from the same class. We thus need a theoretical framework that will allow for modeling a TM,

deﬁning its correctness condition, and expressing its properties.

Having a theory of TMs helps not only in fair comparison of various TM strategies but also

in understanding the inherent power and limitations of the TM paradigm. For instance, we can

seek to prove formally which properties of a TM are associated with which complexity of the TM

implementation. That is, we can get a precise view of the different fundamental trade-offs involved

in designing a TM.

1.4. CONTENTS 5

Also, having a model of a TM and a formal deﬁnition of the correctness of a TM is the

ﬁrst, and necessary, step towards proving the correctness of TM algorithms, as well as verifying

concrete TM implementations. Since a TM is meant to be a reusable component, relied upon by

many applications, it is indeed crucial to be able to show that this critical component is implemented

correctly.

1.4 CONTENTS

This book describes a theory of transactional memory. The questions that we try to answer here are,

for example: How to model a TM? When is a TM correct? How to prove the correctness of a TM

implementation? What properties can a TM ensure? What is the computational power of a TM?

What are the inherent trade-offs in implementing a TM?

The theoretical framework we build here is deeply rooted in the theories describing database

transactions and distributed systems. However, as we explain in this manuscript, TMs cannot be

described precisely and comprehensively using onl y existing concepts, models, and properties from

databases and shared memory systems. Indeed, even though a transaction is a very old abstraction,

the set of requirements imposed on memory transactions is unique.

It is worth noting that the model we consider in this book is necessaril y simpliﬁed. It provides

an abstraction that allows us to focus on those aspects of a TM that are interesting from a theoretical

perspective, without being too distracted by certain implementation issues. For instance, we do not

model the interactions between transactions and non-transactional code, and we assume no nested

transactions. We discuss, however, the recent work that has addressed some of those limitations.

This manuscript is split into three parts. In Part I, we give a model of a shared memory system

(Chapter2) and of aTM (Chapter 3).We also explain,in Chapter 4,the intuition behindacorrectness

condition for TMs, which we call opacity.Then, in Chapter 5, we show two example TM algorithms

whose purpose is to illustrate the ideas and trade-offs behind a typical T M implementation.

In Part II, we ﬁrst deﬁne opacity—our correctness condition for T M s (Chapter 7). Then, in

Chapter 8, we show how one can prove that a given TM is correct, using as examples the two TM

algorithms introduced in Chapter 5. Finally, in Chapter 9, we show that opacity is fundamentally

different from classical serializability of database transactions: we prove a complexity lower bound

that is inherent to opacity but can be overcome when a TM ensures only serializability.

In Part III, we focus on the progress semantics ofTM implementations.We ﬁrst give a general

overview of the contents of this part (Chapter 11). Then, in Chapters 12 and 13, we discuss the

progress properties of two main classes of TM implementations: lock-based TMs and obstruction-

free TMs. We also determine the computational power of those TMs, and we prove various related

results. In Chapter 14, we determine the boundary between the liveness properties that can be

ensured by a TM, and those that cannot.

Each part ends with a chapter that highlights major references to the related work concerning

that part. We try to list not only publications that ﬁrst introduced some of the concepts and methods

剩余193页未读，继续阅读

gleex_pp

粉丝: 0
资源: 3

交易内存原理概览：故障 tolerant 协议与分布式系统设计

Transactional Memory

Principles of Instrumental Analysis, 7th Edition

The Art of Multiprocessor Programming.pdf（英文，高清，带书签）

一种改进的自适应短时傅里叶变方法-基于梯度下降 算法运行环境为Jupyter Notebook，执行一种改进的自适应短时傅里叶变方法-基于梯度下降，附带参考 算法可迁移至金融时间序列，地震 微震信号

一个Java GUI 图书借阅系统源码

螺旋藻过滤机sw21可编辑全套技术资料100%好用.zip

【java】基于java+SSM-考试系统.zip

【python设计模式】大话设计模式python实现.zip

太原理工大学javaee实践教学：从校内项目到学科竞赛及校企合作的全面覆盖

【课程设计】TensorRT部署DETR项目工程python源码.zip

最新资源

一种改进的自适应短时傅里叶变方法-基于梯度下降算法运行环境为Jupyter Notebook，执行一种改进的自适应短时傅里叶变方法-基于梯度下降，附带参考算法可迁移至金融时间序列，地震微震信号