System|Concurrency|单机事务

摘要

本文介绍了在没有网络延迟的情况下，为了保证事务的原子性和隔离性的机制与实现。

在计算机中有几个重要的概念，atomicity、isolation。原子性意为：要么全做，要么不做，隔离性意为：并发的事务运行结果看起来像是串行执行。

为了实现上述特性，实现一个可靠的Lock是必要的。

All or nothing

shadow copy

对于原数据的修改写入副本，然后直接原子性切换到新的副本

原子性通过硬件原子性保证（sector write）

+ Works well for a single file

- Hard to generalize to multiple files or directories

- Might have to place all files in a single directory, or rename subdirs

- Requires copying the entire file for any (small) change

- Only one operation can happen at a time

- Only works for operations that happen on a single computer, single disk

log

Log only

每次都遍历整个log，来获取变量最新的值（类似于blockchain的做法）

•1. begin: allocate a new transaction ID •2. write variable: append an entry to the log •3. read variable: scan the log looking for last committed value •As an aside: how to see your own updates? •Read uncommitted values from your own TID •4. Commit: write a commit record •Expectedly, writing a commit record is the "commit point" for action, because of the way read works (looks for commit record) •However, writing log records better be all-or-nothing •One approach, from last time: make each record fit within one sector •5. Abort: Do nothing or write a record? •Could write an abort record, but not strictly needed Recover from a crash: do nothing •Write performance is probably good •Sequential writes, instead of random •Need to write to disk twice instead of once •Read performance is terrible! •Scan the log for every read! •Recovery is instantaneous •Nothing to do

Log & Data

我们在数据存储区域（cell stotrage）之外额外开辟一段区域，在事务提交之后增加一条commit记录。如果UNDO，根据之前的log即可回退到上一个commit时的状态。

事务的任意操作都会伴随着先log（对log的修改）再install（对数据的修改），两者均持久化。

The rule for logging is the "Write-ahead-log protocol" (WAL).If we crash, log is authoritative and intact, can repair cell storage

read(var):
    return cell_read(var)

write(var, value):
    log.append(cur_tid, update,
               var, read(var), value)
    cell_write(var, value)

•Writes might still be OK •but we do write twice: log & install •Reads are fast •just look up in cell storage •Recovery requires scanning the entire log •Remaining performance problems: •We have to write to disk twice •Scanning the log will take longer and longer, as the log grows

Optimization 1: Improve Writes

对Cell Storage进行Cache（注意，这里即使log完成了持久化，install仍有可能没有持久化，因此我们需要在Recover时对log进行redo，以确保install持久化，然后再进行undo）

Optimization 2: Truncate the Log

在事务持久化完成后，我们并不需要保存先前的log。（类比Journal那一章）

1. Stop accepting new transactions 2. Wait until all current transactions commit or abort and have written the COMMIT or ABORT to the log 3. Flush the log to disk 4. Write a log record <CKPT> and flush the log again 5. Resume accepting transactions

Optimization 3：Non-quiescent Checkpointing

checkpoint需要整个系统停止，因此很慢。这里我们用一个比较有趣的方式，就是类似于之前OPT journal里面的。即使没有checkpoint，新事务仍然可以执行。

1. Write a record <START CKPT(T1…Tk)> and flush log (T1,…Tk are the active transactions) 2. Wait until all of T1, … Tk commit or abort, but allow new transactions to start 3. When all of T1,…Tk have written COMMIT or ABORT, then write <END CKPT> to the log If crash, then look backwards for the first <START CKPT(T1…Tk)> or <END CKPT> If see an <END CKPT>, only have to consider after this If see a <START CKPT(T1…Tk)> but no <END CKPT>, then only need to consider after the transactions T1, .. Tk began

Optimization 4：External Sync

我们并不需要使用速度慢的flush，而是使用External Sync，直到其外部可见（如print时）再进行flush

Before or After

Race Condition

某个资源不能被线程同时使用，因为使用的先后顺序产生不同的结果。这种错误极难复现，又被称为Heisenbug（测不准）

Serialization

多个并行的事务，我们让他们看起来像是在顺序执行

• Final-state serializability

只关注终态结果

• Conflict serializability

如果两个属于不同事务的操作对同一个对象，其中一个是写，则conflict

如果这些conflict的顺序像是在顺序执行的调度下，那么称为Conflict serializability

我们可以根据其建立冲突图，如果两个事务间存在冲突，则先进行操作的事务指向后发生操作的事务。如果最后冲突图无环，那么则满足这样的serializability。示例如下，下面的两个操作均满足Final-state serializability，但是T1 read的x却不是相同的。

• View serializability

上面我们发现了，Final-state serializability并不是很好，因为中间插入的read读到的结果可能并不正确。但是上图不满足confict serializability，中间插入的read也是正确的。因此confict serializability过于严格了。

因此我们认为终态和中间的读如果和顺序调度结果一致，那么则满足view serializability。然而，这种做法却很难验证（NP-hard），也没有好的调度算法实现，并且大多数情况下conflict和view的结果是一样的。而confict serializability则通过2PL能够保证，并且验证很快，此外，blind write（不被读取的写，并不常见）也会导致view serializable的调度算法受影响，虽然更严格，但是实用性更强。

实现Conflict serializability需要利用Concurrency Control (CC)，暂时不写。而CC需要利用lock实现。

Lock

Peterson's Algorithms

int flag[2]; // assume two threads on two CPUs
int turn;
void init() {
    flag[0] = flag[1] = 0; // 1->thread wants to grab lock
    turn = 0; // whose turn? (thread 0 or 1?)
}
void lock() {
    flag[self] = 1; // self: thread ID of caller
    turn = 1 - self; // make it other thread's turn
    while ((flag[1-self] == 1) && (turn == 1 - self))
        ; // spin-wait
}
void unlock() {
    flag[self] = 0; // simply undo your intent
}

可以看出，他主要解决的是双线程互斥的问题，看起来就挺憨憨。不过实际上算法的正确性很高，因为turn == 1 - self这个条件不可能同时在两个线程成立，因此不会出现抢夺情况。

这个算法事实上假设了load/store具有硬件原子性，然而现代的硬件中，因为relaxed memory consistency model的存在，这个算法已经不适用。

Memory Consistency

内存一致性模型描述多核同时读写同一块内存时的行为。理想情况下，读操作将会读到最后一次对该内存进行写的值。

Strict Consistency

读操作将会读到最后一次对该内存进行写的值。符合严格定义，但是实现起来就要等待其他CPU的结果，才能执行当前的指令。因此性能不佳。

Sequantial Consistency

"… the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program."

所有的处理器以相同的顺序看到所有的操作。单个处理器内部以程序定义的顺序执行。

这里右边P2的第一个R(x)读到了0，而不是最后写入的1，因此不满足Strict Consistency。

但是，在P1和P2看来，对内存的几次读操作仍然是先读0，再读修改后的1，因此满足Sequantial Consistency。

Intel处理器提供的TSO（Total Store Order）保证了这个层次的一致性，但是ARM则没有保证。

Processor Consistency

不同的处理器以不同的顺序看到所有的操作。单个处理器内部以程序定义的顺序执行。

这和多核的延迟有关，例如P4先通知了P3 W(y)，P1先通知了P2 W(x),两个处理器看到W(x)和W(y)的顺序不同。

Summary

不同的机器有各自的内存一致性模型。consistency和performance呈现trade-off。

JVM让用户自行决定critical section，在其中保证Processor Consistency。只提供最小的支持，以防在堆上分配/释放内存时读到未初始化的内存。（JVM是虚拟机，因此可以自己定义内存一致性模型）

Lock Implementation with Atomic Instructions

由于内存一致性不严格的存在，我们需要硬件提供额外的原子性操作，以满足我们锁的需求。下面事实上没有避免starvation，如果想要FIFO，那么可见

Atomic Exchange

我们一般使用atomic exchange来保证获取锁会是原子性操作，要么同时完成flag的检测和设置，要么什么都不做。这里C代码形式如下(TestAndSet）:

int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // fetch old value at old_ptr
*old_ptr = new; // store ’new’ into old_ptr
return old;
}

typedef struct __lock_t {
int flag;
} lock_t;

 void init(lock_t *lock) {
 // 0: lock is available, 1: lock is held
 lock->flag = 0;
 }

 void lock(lock_t *lock) {
 while (TestAndSet(&lock->flag, 1) == 1)
; // spin-wait (do nothing)
}

 void unlock(lock_t *lock) {
 lock->flag = 0;
}

而另一种形式为（CompareAndSwap），作用类似，但比TestAndSet更为泛用

int CompareAndSwap(int *ptr, int expected, int new) {
 int original = *ptr;
 if (original == expected)
 *ptr = new;
 return original;
 }
void lock(lock_t *lock) {
 while (CompareAndSwap(&lock->flag, 0, 1) == 1)
 ; // spin
}

Fetch-and-add

领票排队，轮到自己就拿锁。因为unlock不是幂等的，所以如果写的代码不对容易产生bug。比如可以unlock任意次。

int FetchAndAdd(int *ptr) {
 int old = *ptr;
 *ptr = old + 1;
 return old;
}

typedef struct __lock_t {
 int ticket;
 int turn;
 } lock_t;

void lock_init(lock_t *lock) {
 lock->ticket = 0;
 lock->turn = 0;
 }

 void lock(lock_t *lock) {
 int myturn = FetchAndAdd(&lock->ticket);
 while (lock->turn != myturn)
; // spin
 }

 void unlock(lock_t *lock) {
 lock->turn = lock->turn + 1;
 }

Load-linked and Store-conditional

 int LoadLinked(int *ptr) {
 return *ptr;
 }

 int StoreConditional(int *ptr, int value) {
 if (no one has updated *ptr since the LoadLinked to this address) { 
 *ptr = value;
  return 1; // success!
 } else {
return 0; // failed to update
}
}

下面的代码相当于一旦test到flag为0且中间没有被修改为1，那么set为1。 和TestAndSet原理差不多。

void lock(lock_t *lock) {
while (1) {
while (LoadLinked(&lock->flag) == 1)
； // spin until it's zero
if (StoreConditional(&lock->flag, 1) == 1)
return; // if set-it-to-1 was a success: all done
// otherwise: try it all over again
}}

Performance

锁越多，实现的并发量更大。下面是一段move代码

1:
acquire(fs_lock)
 unlink(dir1, filename)
 link(dir2, filename)
release(fs_lock)
2:
acquire(dir1.lock)
  unlink(dir1, filename)
release(dir1.lock)
acquire(dir2.lock)
  link(dir2, filename)
release(dir2.lock)
3:
acquire(dir1.lock)
  acquire(dir2.lock)
unlink(dir1, filename)
link(dir2, filename)
  release(dir1.lock)
release(dir2.lock)

1导致dir1,dir2操作之间完全无法并发

2导致dir1的操作可以和dir2并发，但是release dir1之后，原本的file就不知道在哪个目录下了。

3解决了上述问题，但是可能导致死锁。

Dead Lock

四个条件见https://www.cnblogs.com/sunnyCx/p/8108687.html

• 互斥：某种资源一次只允许一个进程访问，即该资源一旦分配给某个进程，其他进程就不能再访问，直到该进程访问结束。
• 占有且等待：一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源。
• 不可抢占：别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过来。
• 循环等待：存在一个进程链，使得每个进程都占有下一个进程所需的至少一种资源。

Solution

•Lock ordering (pessimistic)：避免循环等待，给锁唯一的序号，进程增序获取。

•Backing out (optimistic)：避免不可抢占，给锁唯一的序号，进程任意获取，如果低序号的锁冲突，UNDO释放高序号的锁，等待低序号锁释放后再REDO。

•Timer expiration (optimistic)：超时直接abort

•Cycle detection (optimistic)：避免循环等待，死锁可以抽象为一个图，其中存在有向环，两节点互为前置。因此选定环中某个节点作为胜利者。