Software Transactional Memory

History

Maurice Herlihy http://www.cs.brown.edu/~mph/美国布朗大学计算机科学系教授。1993发表了论文《Transactional Memory:Architectural Support for Lock-Free Data Structures》,对于事务性内存的研究基本是随着这篇paper兴起的。最近我在读他和Nir Shavit写的《The Art of Multiprocessor Programming》。

Nir Shavit http://www.math.tau.ac.il/~shanir/ 以色列Tel-Aviv大学任教。主要研究方向是多核机器上的并发数据结构,以及共享内存计算模型的数学基础。 1997年,Nir Shavit, and D. Touitou,在Distributed Computing杂志上发表《Software Transactional Memory》论文。这算是STM的公开研究的起点。 Deuce STM 的作者之一。

Tim Harris http://research.microsoft.com/en-us/um/people/tharris/微软剑桥研究院研究员,2004加入微软剑桥研究院。Keir Fraser and Tim Harris. Concurrent programming without locks. TOCS: ACM Transactions on Computer Systems, 25(2), May 2007 最近他写了一本书,《Transactional Memory》,已经出了第二版,我在艰难的啃着。

Simon Peyton Jones http://research.microsoft.com/en-us/people/simonpj/微软剑桥研究院研究员,1998年加入。研究重点主要在Haskell这样的函数式语言。

David Dice http://blogs.oracle.com/dave/ Sun的工程师,TL/TL2的作者。

Bratin Saha Intel的Programming Systems Lab 的高级研究员,参与了Nelhalem的cache同步及并发控制的设计。McRT-STM的设计者。

Michael L. Scott http://www.cs.rochester.edu/u/scott/ 美国罗彻斯特大学计算机科学系教授,Rochester STM项目是由他带领做的。

João Lourenço http://www-asc.di.fct.unl.pt/~jml/index.html CTL的作者,正在做一个叫Euro-TM的项目。

并发控制概述

并发控制协议需要关注的3个问题:

  1. 冲突何时发生?
  2. 冲突如何被检测到? 
  3. 冲突如何解决?

并发控制协议总的来说,可以分为乐观和悲观两种。

两种版本管理模式:

1、eager version management:直写型。必须要有undo log。

2、lazy version management:延迟更新。所有的修改在提交前都是针对当前事务私有的。

加锁的时机:

ETL:encounter-time locking。事务第一次访问这个地址时加锁。

CTL:commit-time locking。事务提交时加锁。

ETL可以支持eager version management和lazy version management。

CTL只能支持lazy version management。不能支持eager version management是很显然的,因为如果直写,但是事务提交时才加锁,那就乱套了。

互斥锁

先明确三个概念:

Locker: 谁拥有锁。例如Transaction、Thread。

Lock: 锁。一个有状态的对象。

Locked Object: 需要多线程并发访问,所以被用锁保护的对象,如table、data record。

互斥锁(Mutual Exclusion)是线程同步最基本的工具。

读写锁

在大多数场景下,对变量的读操作的次数远远大于写操作。从理论上来说,多个线程同时读取一个变量的时候,是不需要互斥、等待的。于是就有了读写锁。

相容性

Read

Write

Read

O

X

Write

X

X

虽然从概念上来看,读写锁很简单,但是从细节上看,读写锁的实现多种多样。每拿到一个读写锁的实现的时候,我要先考虑如下疑问:

  1. Release preference: 如果一个writer释放它所拥有的写锁,此时既有reader也有writer在等锁,那么谁将获得锁? reader? writer? 还是无论类型,谁先请求谁就先得到?
  2. 读写优先级:如果一个locker已经拥有读锁,一个locker来请求写锁,那么必然会被阻塞。此后,另一个locker来请求读锁,那么它能立即获得读锁吗?
  3. 降级:如果一个locker已经获得写锁,它想换成读锁。那么释放写锁和获取读锁这两个操作是原子的吗?(很少用,所以下面不考虑它)
  4. 升级:如果一个locker已经获得读锁,它想升级成写锁。此时已经有其它的locker也在请求锁,这个locker是否具有优先于其它locker的权利立马获得写锁?

在这几个问题考虑清楚之前,不要轻易使用读写锁。读锁升级操作很容易造成死锁,假设有两个locker A、B都已获得读锁,然后A申请升级,此时还不能得到锁,因为B的锁还没释放。之后B也去申请升级,那么就死锁了。

对于采用encounter-time locking的事务处理系统,读数据的时候,自动获取读锁,写数据的时候自动获取写锁,如果要达到可串行化的隔离度,那么所有的锁都保持到存储过程结束才释放。如果不明白读写锁的升级操作的可怕之处,那么死锁将会四处潜伏。下面以Berkeley DB为例:

void myfunc(DB_TXN* txn){
    DBT key,value;  
    key=…..;
    //读出来。此时拿的是读锁。
    db->get(db, txn,&key,&value,0);
    //修改
    *((int*)value.data)=0;
    //写回去。此时需要申请写锁。
    db->put(db, txn,&key,&value,0);
}

如果有两个线程试图同时执行上面这个函数,则有可能会发生死锁。为此,Berkeley DB为get方法提供了一个flags字段,DB_RMW。

void myfunc(DB_TXN* txn){
    DBT key,value;  
    key=…..;
    //读出来。此时拿的是读锁。
    db->get(db, txn,&key,&value,DB_RMW);
    //修改
    *((int*)value.data)=0;
    //写回去。此时需要申请写锁。
    db->put(db, txn,&key,&value,0);
}

那么此时拿的就是写锁而不是读锁。改成这样之后就避免了死锁。

如果locker拿不到读锁,那么有两种可能性:

  1. 有其它locker已经拿到写锁。
  2. 有其它locker已经拿到读锁,并且已经有其它locker在等待写锁。

如果locker拿不到写锁,那么只有一种可能性,有其它locker拥有这个锁。(无论是读还是写)。

出现等待环是死锁产生的必要条件。而等待只发生在两种情况:

  1. 请求一个现在不拥有的锁
  2. 读锁升级为写锁

对于第二种情况,如果在某个函数中发生了锁升级操作,那么就意味着这个函数本身就一定不支持多个线程并发执行(否则我们就需要deadlock detector)。而对于第一种情况,采用和mutex同样的策略,只要拿锁顺序的顺序是一致的,就不会出现循环等待。

事务嵌套

关于Nesting Transaction的基本假设:

  1. each transaction can have at most one pending child transaction within it
  2. the inner transaction sees modifications to program state made by the outer transaction
  3. there is just one thread running within a given transaction at a given time

Flattened Nesting:子事务回滚导致父事务回滚。子事务的提交需要等到最外层的父事务提交时才真正被执行。

Closed Nesting:子事务回滚不影响父事务。子事务提交后,它所做的更改只对父事务可见。当最外层的父事务提交后,才对全局可见。

Open Nesting:子事务一旦提交成功,所做的更改对全局可见。

McRT-STM关于并发控制有一个基本原则:

拿不到锁就等着。只有被等待的那个锁的拥有者(Transaction)不处于running状态时,才主动打断该事务。

STM的实现策略1:读写锁

每个对象由读写锁保护,按ETL的方式加锁。允许读锁升级成写锁,升级时发生冲突立即发现立即打断。

McRT-STM的读写锁实现:

  1. 每个lock是一个32位整数。
  2. 低三位分别为:Notify、Upgrade、Reader。
  3. 高29位是number of readers。

获取写锁:

往它的transaction local structure中存储一个指针,这个指针指向的内存是8字节对齐的。所以它的低三位都是0。

一旦获得了写锁,因为其它事务无法获得读锁,这个指针的低三位始终是保持不变。

获取读锁:

首先检查是否有writer已经获取了(lock的低三位不是全0)。然后原子化的把这个值+8(也就是number of readers+1),释放锁的时候减回来。一旦获得到锁,低三位的默认值是0x4。

当读锁要升级的时候,首先它用CAS指令原子化的把Upgrade那一位设置成1(expect 0, set 1),然后等现有的reader释放读锁。然后一旦获取到,如同前面所说的获取写锁那样,往它的transaction local structure插入指针。如果Upgrade那一位设置成1的时候失败,也就是说有其它的事务也在等着升级成写锁,那么这就意味着发生了死锁,因为它自己是后来的,所以它就回滚。在Upgrade位已设置和拿到写锁之间,如果有其它事务来请求读锁,一概等待。

Notify位是用于这样一种模式:

一个事务已经读了一些数据,然后现在需要停下来等某个已读过的数据改变。由于此时已经拿了读锁,所以它不可能变。于是就需要原子化的设置Notify位、释放读锁、把自己加入到等待链表中。而写锁在释放的时候(也就是事务提交的时候),检查Notify位,唤醒正在等待的reader,让他们继续执行下去。

我不知道为什么非要有Notify这个功能,是不是说没有Notify的功能就不需要维护readers count了?现在这样设计,每次获取/释放读锁,都需要修改这个计数器,导致CPU的cache被全刷一次。

这种策略属于严格的2段锁协议,所有已获得的锁都保留到commit时。(Notify模式除外)

STM的实现策略2

Lock-Based STM Systems with Local Version Numbers:

  1. 写操作采用悲观的并发控制协议。按ETL的方式加锁。
  2. 读操作采用乐观的并发控制协议,每个Object有一个version number,每次对该对象的修改都会导致version number增长。

McRT-STM:

依然是用一个32位的整数表示锁,低三位依然是为特殊含义而保留,Notify、unused、Reader。

它有两个状态,靠Reader位来分辨。

  1. 被一个writer持有。Reader=0。
  2. 高29位存储着version number。Reader=1。

与2段锁协议相比,这里事务的执行被分为三个阶段:

  1. 读阶段。执行各种读取操作,以及应用本身的事务逻辑。
  2. 验证阶段。对read set做版本验证。
  3. 写阶段。拿写锁,写入数据,增加版本号。拿写锁的时候不仅会把指针存下来,而且会把原始版本号也存下来,因为写完之后要在这个版本号的基础上加1写回去。

后记

这两种并发控制模式,几乎每本讲到事务处理的数据库的课本上都写的有,但是从来没有谁从理论上分析出哪种更好一些。可是按照Intel在他们的paper中给出的测试数据来看,在CPU较多时(如现在8核、16核),对于hash表、链表这样的数据结构,基于本地版本的要比基于读写锁的效率高出几百倍。我觉得是这样,一个事务,它绝对大部分时间都是消耗在自己的逻辑代码上,而不是commit阶段。而在这个阶段,基于版本的乐观控制,不需要拿任何锁,也不需要写任何全局变量,甚至不需要触发任何memory barrier, 这一点非常适合于NUMA架构。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥