随着计算机技术的发展,研发人员意识到通过不断增加主频来提升CPU性能的时代已经结束,近年来,CPU架构更加注重低功耗和多核心.芯片设计工程师将两个或多个内核封装到单一处理器中,片上多核处理器已经成为处理器发展的趋势.多核带来的性能提升及其在商业上的成功使得多核心架构从最初的2核、4核,跨越到8核、16核,不久的将来,普通PC机或许将迎来超过100核的处理器.那么,这波多核运动要发展到什么程度呢?没有人能给出一个明确的答案.可以肯定的是,我们已经迈入了一个多核时代,这已成为计算机设计和应用中不可回避的问题^[].

多核时代给人们带来了机遇,同时也带来了巨大的挑战.在一个单独封装的处理器内拥有多个内核,它们共享同一块内存,并发执行多个线程时通过共享内存中的数据结构来进行通信和同步^[].随着内核数量的增多,程序对共享资源访问的冲突也在加剧,这成为一个亟待解决的问题^{[, ]}.虽然在过去的几十年中,研究者们已经在多核处理器的机器上运行软件程序,然而这些软件程序通常是数值计算、大规模矩阵运算等科学研究性质的并行程序,或者是未针对多核处理器优化的顺序型程序.伴随着商用多核(multicore)系统成本的降低,未来个人电脑、平板电脑、手机等设备势必将具备更多核心,我们越来越需要对原有的顺序型程序进行改造和优化,使其能够更充分地利用多核资源^{[, ]}.目前面临的瓶颈是多核软件的发展没有跟上硬件的发展.

数据结构是软件设计的核心,对整个软件的性能有着重要影响.往往在数据结构上的一些细微改动就能够很大程度地提升整个软件的运行效率.然而,目前大部分程序员、科研工作者对多核时代数据结构并发编程的理解还不够深刻,只有少部分人具备设计并发程序的能力^[].对于大多数人而言,设计多核并发数据结构的难点在于:在一个进程内大量并发运行的线程会交错地执行指令,从而产生不可预期的结果.这就要求我们对多核时代的数据结构有新的认识,用新的方法和工具集来开展研究和设计^[].

总体而言,多核架构下基于共享内存的并发数据结构仍然有很多问题亟待解决.本文针对多核时代数据结构的相关研究进行综述.剖析了国内外各类并发数据结构的研究现状,总结了并发数据结构设计和实现的关键技术.最后,基于这些讨论,对多核架构下并发数据结构未来的研究趋势和应用前景进行了展望.

本文在第1节分析数据结构并发的重要性及其与并行的区别.第2节归纳提出基于演进条件(progress condition)的并发数据结构分类.第3节对近年来学术界对各类并发数据结构(如:堆栈、链表、哈希、树型结构等)的研究现状进行综述.在此基础上,在第4节~第6节总结并发数据结构的关键技术、开发流程和理论正确性验证方法.最后在第7节对多核架构下并发数据结构未来的研究趋势和应用前景进行展望.

1 数据结构并发的重要性及其与并行的区别 1.1 并发与并行的区别

多核系统在一段时间片段内,运行的线程会交错地执行指令.因此,并发(concurrency)和并行(parallelism)是多核编程中经常会碰到的概念,也容易混淆,首先需要区分并发与并行.

并发:用来描述存在至少两个线程正在工作(并不一定在同时执行)的状态,是一种更加通用的、可以在单核处理器上通过时间切片实现的状态.

并行:用来描述至少两个线程同时执行的状态.在同一时间点上,多个线程可同时并行执行.

1(a)所示,并发从逻辑上看是多个线程同时发生,但在物理上则是由操作系统调度完成.CPU某一时刻依然只执行某个线程的任务.所有的并发处理都有排队等候、唤醒、执行至少3个这样的步骤.当多个线程同时工作时,从宏观上看它们是并发的,从微观上看它们却又是顺序被处理的,只不过资源不会被阻塞(一般是通过时间片轮转).而并行则是物理上多个线程同时发生.如图 1(b)所示,同一个时刻,有3个线程同时运行,无论从宏观还是微观来看,3个线程都是同时工作的,也即是并行执行的.

通常而言,并发编程会涉及到较多系统资源竞争,比如同时读写共享内容、操作系统层面的线程调度等.而并行编程则较少出现严重的资源竞争现象.如GPU平台的编程,同一时刻可以存在大量同时执行的线程,因而带来高吞吐量.但是,由于GPU架构中计算能力较强,逻辑控制单元较弱,GPU不适合开发逻辑较为复杂的并发程序.

在多核出现前的单核处理器时代,经过几十年的发展,人们已经在编译器优化、处理器优化、多线程编程等方面有深入的研究,开发了对编程人员而言非常抽象的各种基础库,编程人员无需知道底层硬件设备、编译器、OS调度等实现细节.进入多核时代后,由于计算机CPU架构的变化,相应的OS调度、编程模型等的调整才刚刚开始,一个高度抽象的基础库还没有形成,因此,多核时代的并发编程更加困难.

1.2 数据结构并发的重要性

为了更深刻地理解数据结构并发的重要性,首先让我们来看看著名的阿姆达尔定律(Amdahl’s law)^[].设n为可并发执行线程数,p为可并发执行部分所占整个程序的比例,那么最后可以得到这个程序最优情况下能够达到的加速比S.

通过上述公式可以推出S并不是和n线性相关的.举一个直观的例子:假设目前可并发执行的线程数为10,那么理想情况下可以达到的加速比是10.然而,根据上面的阿姆达尔定律,当并发执行的程序比重占到90%时,最后只能得到5.2倍的性能提升,仅为理想值的一半左右.因此,阿姆达尔定律揭示我们,对一个程序进行并发改造的空间是有限的,主要的影响因素是CPU核心数目和程序必须顺序执行的部分占整个程序的比例.在上述例子中,剩下不可并发执行的10%部分对于整个程序并行效率的提升相当重要,而这部分在程序中通常体现为需要内部调整、具有特殊性质的数据结构.因此,只有提升了这些关键数据结构的并发能力,才有可能给整个应用带来很大的性能提升.

演进条件是指并发数据结构活性能够被保障的条件.它是用来评价并发数据结构的重要指标,意味着并发数据结构算法最终在怎样的情况下完成^[].演进条件在一定程度上反映了并发数据结构的性能.根据演进条件的差异性可以将其主要分为4个大类别:阻塞(blocking)、无干扰(obstruction-free)、无锁(lock-free,简称LF)和无等待(wait-free,简称WF),这4个类别又可以被细分为如图 2所示的7个不同小类.分析已有的演进条件,归纳它们之间的定义及关系如下.

● 阻塞:即这种方法在其执行过程中不能正常运行,直到其他(占有锁的)线程释放.阻塞是大家所熟知的,基本上,所有加锁的算法都可以说是阻塞的.使用阻塞算法时,某个线程所引起的意外延迟会阻止其他线程继续运行.在极端情况下,会造成死锁;

● 无饥饿(starvation-free):那些希望进入互斥区域的线程最终都能够进入互斥区域(即使之前在互斥区中的线程意外停止了).无饥饿有的时候也被称为无闭锁.

● 无干扰:如果一种方法满足无干扰性质,那么这种方法从任意一点开始它的执行都是隔离的.当一个线程调用该无干扰方法时,其他任何线程调用的各种方法都不会对这种无干扰方法的运行结果造成实质性影响,但是该方法的运行时间可能由于其他线程占用资源而受到影响,但是绝对不会出现死锁.

● 无锁:如果一种方法是无锁的,那么它保证有一些调用能够在有限步内完成.

● 无等待:假如一种方法是无等待的,那么无论其他操作如何,这种方法的每一次调用都可以在有限的步骤内结束.无等待是一种非阻塞的演进条件,意味着一个线程的任意意外延迟(比如说一个线程持有锁)都不会阻塞其他线程的继续执行.

● 有界无等待(wait-free bounded,简称WFB):如果一种方法是有界无等待的,那么这种方法保证每次调用都能够在有限并且有界的步骤内完成.这个界限可能依赖于线程的数量.

● 集居数无关无等待(wait-free population oblivious,简称WFPO):一种无等待的方法,如果其性能和活动线程数目无关,那么被称为集居数无关无等待的.

多核时代的数据结构基本上都可以按照上述7类演进条件来进行划分,从演进条件的活性保障程度来说,存在如下关系:集居数无关无等待>有界无等待>无等待>无锁>无干扰>无饥饿>阻塞.演进程度越高,意味着线程的活性能够得到更多的保障,多线程在执行时受到的干扰和约束越少,因此执行的效率更高.演进程度高的涵盖演进程度低的.对于阻塞和非阻塞两大类来说,若一个数据结构满足演进程度高的条件,那么它也一定满足演进程度低的演进保证.举个例子:我们可以说“无等待意味着无锁”(但是不能反过来说).这意味着一种方法如果满足无等待,那么这种方法就有着与一种无锁方法同样的演进保证.非阻塞类的演进条件涵盖关系可以用维恩图的形式来表达.

在设计并实现并发数据结构时,其能够达到的演进条件取决于应用的需求和底层软硬件平台的支持.一般来讲,演进程度高会具有比演进程度低更好的效率.

3 各类数据结构并发研究现状

近30年来,科研人员对各种数据结构并发操作的研究步伐一直没有停歇过,研究的重点也逐步从最初简单的数据结构(如:Stack,Queue,Hash-Table,Skiplist等)转向复杂树形结构.在这一节中,我们将对这些主要数据结构的研究情况进行分析.

堆栈(stack)是较为简单的数据结构.在前人深入研究的基础上,Michael和Scott在文献[]中总结了多个基于锁的并发堆栈实现,其基本原理是利用全局锁对堆栈访问进行控制,然而,这种设计使得堆栈的栈顶成为并发的瓶颈.Treiber在文献[]中首次提出了演进条件达到无锁级别的并发堆栈,它采用单链表来表示堆栈,使用CAS(compare-and-swap)原子操作来修改堆栈的栈顶.实验结果表明,相对于基于锁的实现,这种无锁实现在性能上具有很大优势.

4所示,当多个线程(线程A和线程B)进行栈顶访问发生资源冲突时,使用CAS原子操作来修改堆栈的栈顶.同一个时刻只有一个线程成功(线程A),另外一个线程B失败后则进入下一轮CAS竞争.这样在对资源的竞争中避免使用锁,取得了比较高的并发性.除此之外,文献[, ]中提出一种称为“消除(elimination)”的技术来提高堆栈的并发性,其核心思想是允许成对的彼此相反的操作在不经过中央调度的情况下立即完成.因此,当一个pop操作遇到一个并发执行的push操作时,允许pop操作立即获得push操作的值,并且这两个操作都立即返回.

最早的无锁并发队列出现在文献[]中,其核心思想是通过一个有限长度的数组来实现无锁功能,两个独立的线程分别在队列的入口和出口负责读操作和写操作.在此基础上,文献[]提出了一个基于链表的无锁队列.文献[]提出一个数组容量无限、基于无锁数组的队列.文献[]对无阻塞队列的实现作了详细总结,并提出一种基于CAS原子操作且演进条件为无锁的队列,通过CAS来对队列的头尾进行多线程的资源互斥和并发控制.上述工作^{[, , , ]}都基于单端队列,双端队列的并发设计则比普通队列难很多,因此目前实现的大多是基于锁的阻塞双端队列.文献[]指出,即便使用CAS,也很难设计出无锁的双端队列.目前已知的实现是Herlihy在文献[]中提出一种基于CAS、满足演进条件为无干扰的双端队列.

最早的并发链表是一种基于全局锁的实现,每一个获得全局锁的线程进入链表进行操作,其他线程则在外等候,因而全局锁的粒度较粗.一种称为“手连手锁(hand-over-hand locking)”的细粒度锁在文献[, ]中被提出,在这种方法中,链表中的每个节点都有一个锁的标志位,线程在遍历链表时,只有当获得下一个节点的锁之后才会释放当前节点的锁.相对于全局锁,手连手锁的特点是缩小了锁影响的节点范围,一个链表中可以同时存在多个线程进行操作,提高了链表的并发性.但是,在相互临近节点的插入和删除操作还是会相互干扰,影响了结构的并发性.Valois^[]首次提出了基于CAS的无锁链表,但是Valois的设计过于复杂而难以实现.在此基础上,Harris^[]提出了一种更易于实现、演进条件为无锁的链表,通过为节点设置一个删除标志位,只允许用原子操作来修改这个标志位.在这种实现中,节点被设置成删除后并不是马上就物理删除,而是先存在于链表中,等待内存垃圾回收时再统一删除.

通过为哈希表的每个存储单位分配一个读/写锁,固定长度哈希表的并发操作相对容易实现^[].然而,随着插入元素的增多,只有可扩展的哈希表才能保障良好的性能,但设计并发的可扩展哈希表难度较大.文献[, , ]提出了一种适用于分布式数据库的、基于两层锁的可扩展哈希表.在此基础上,Lea在文献[]中提出了可扩展哈希表的算法,在测试中表现出了良好的性能.该算法不对每一个存储单元加锁,而是建立少量更高层的锁.在哈希表进行调整时允许进行并发查找,但是不允许并发的插入和删除操作.上述工作^{[, , , ]}都是基于锁的可扩展并发哈希表来实现,这种方法不可避免地存在阻塞同步的缺陷,并且当哈希表的容量进行扩充时需要重新调整元素的分布,这使得阻塞情况更加严峻.Shalev和Shavit^[]首次提出一种演进条件为无锁的可扩展哈希表,其核心思想是将哈希表中的每个元素放到一个无锁的单向链表中.由于单向链表本身是无锁实现的,因此对其中每个元素(也就是哈希表中的每个元素)的操作(插入、删除)也就是无锁的.单向无锁链表的引入使得对元素的查询具有O(n)的时间复杂度,这有悖于哈希表中O(1)的属性.为了解决这个问题,Shalev和Shavit在算法中维护了一个可变长的指示数组,数组中存储了指向相应单向链表节点的指针.通过这种方式,使得查询操作不再是顺序查找的过程,而是能够通过数组中的指针快速定位到相应的链表节点的过程.

并发技术也被引入一些新近提出的Hash算法中以提高效率.Cuckoo hashing是Pagh等人^[]于2001年提出的一种解决hash冲突的方法,其基本思想是使用两个hash函数来处理碰撞,通过多步探测,以增加查找与插入时间为代价减小hash碰撞,提高了hash

传统的并发数据结构(如Linked-list,Stack,Queue,Hash-Table,Skiplist等),由于结构相对简单且研究时间较长,都已经做到无锁实现.对于更高程度的无等待并发,由于研究难度较大,目前进展缓慢.因此,近年来科研工作者将研究重心转向并发树型结构的研究^{[, , , memory)实现的并发红黑树结构,虽然这种实现非常方便,不需要程序员进行额外的同步处理.然而,STM实现普遍导致了巨大的时间开销,一个简单的细粒度锁二叉树结构,或者是非阻塞二叉树结构可以在性能上轻易地超过它.文献[]提出了一种基于细粒度锁的并发平衡二叉树数据结构.该二叉树结构利用了乐观并发的思想,利用版本号控制技术来判断操作是否冲突:如果冲突,那么算法从根节点开始重新遍历;否则,操作完成.Ellen等人[]首次提出了利用CAS原子操作的并发二叉树结构,该结构属于“外部树”结构,即所有键值存储在叶子节点,并且删除时将父节点和叶子节点一起删除,而不对其他内部节点作任何处理.文献[]中将待删除节点的后继节点覆盖到待删除节点,如果后继节点只有一个孩子,那么将后继节点删除,否则,保留后继节点(采取逻辑删除的思想).上面提到的并发树[]本质上都是基于外部树,其结构如图}

如图 5所示,所有外部树的信息都存储于叶节点,中间节点起到路由作用.因此,相对于普通内部树,外部树会导致一定的额外存储空间开销,但是这样做的好处是在插入、删除时避免了树型结构的大范围调整,有利于多核多线程的并发操作.如图 5(a)所示,在内部树中删除节点15时,需要将底层节点20调整到顶部,影响范围比较大,而外部树则避免了这种情况,减小了因为节点调整影响的范围.

Natarajan等人在文献[]中利用CAS和SETB操作设计了一种高效的并发二叉树数据结构,大幅度提升了二叉树的性能.Drachsler等人^[]针对二叉树中的查找操作进行优化(这里提到的查找操作指的是查询、插入和删除都需要涉及的定位节点操作),主要利用了逻辑有序(logical ordering)的思想,即存储每个节点逻辑上的前后节点,将插入和删除操作的查找行为和查询操作的查找行为分离,从而提升查找操作的效率.他们也提到了关于在提升查找操作的性能、额外的存储空间以及调整Logical order的额外时间之间存在一个权衡的问题.文献[]结合了前人的技术要点,构造了一个高效的二叉树结构.该二叉树结构具有以下几个特点:(1) 采用内部树以及线索树结构,并且通过一些技巧加以优化,使得操作的复杂度从O(cH(n))降低到了O(H(n)+c).(2) 仅使用CAS原语,因此跨平台可用.在二叉树研究的基础上,Brown等人将研究的范围扩展到多叉树(k-ary tree),并且着重讨论了多核情况下多叉树中的范围查询问题,实验结果显示,基于CAS的实现在小范围查询时取得了显著效果^{[, ]}.

对于需要平衡的树形结构来说,插入、删除操作都会带来树形结构的调整,因此,前人还针对并发二叉树的平衡性策略进行了相关研究.文献[]在每一次互斥操作之后进行上锁调整平衡,而文献[]则采用一个额外的线程专门进行调整操作.有的时候,可以通过弱化平衡操作的实效性来减小数据结构设计的难度,如文献[]通过将树的平衡操作分离实现了一个平衡二叉树,其核心思想是在进行插入、删除操作时并不立即进行平衡调整,而是等到一定时间后再进行平衡调整.

目前所有已知实现的树型结构,能够达到的最高演进条件是无锁级别.

4 并发数据结构关键技术

在上一节中,我们对现有数据结构的并发研究现状进行了分析.可以看出,每一种并发数据结构的设计都具有一定的难度,需要选用特定的技术来精心设计,我们将其中一些关键技术进行分析总结如下.

通用构建是对不同数据结构提供一套在多核环境下的统一构建方法.有两种不同的实现:(1) 将数据结构的所有并发操作都放入队列中来生成对应的顺序化操作^[].(2) 对数据结构建立多个副本,并发操作在不同的副本上得到执行,更新受到影响的共享结构部分,完成不同副本之间的一致性保证^{[, ]}.由于其普适性的设计思想,通用构建方法相对于采用特殊设计技术(如:基于锁的实现)的执行效率较低,除此之外,在一些复杂结构(如树型结构)中很难采用通用构建方法.

基于锁的实现是目前多核并发编程中采用最为广泛的技术.根据锁的粒度的不同,可分为粗粒度锁和细粒度锁.

粗粒度锁主要解决线程之间同步和互斥问题,在Java编程中体现为管程(moniter)的概念.管程是一种程序结构,结构内的多个子程序(对象或模块)形成的多个工作线程互斥访问共享资源.通过使用管程,可以针对管程对象的每一种方法自动获取锁资源,释放锁资源.与那些通过修改数据结构实现互斥访问的并发程序设计相比,管程很大程度上简化了程序设计.管程实现了在一个时间点,最多只有一个线程在执行管程的某个子程序.采用粗粒度的锁可以简化加锁行为,减少编程难度,但是粗粒度锁对并发性影响更大.在第3.3节中提到的全局锁就是一种粗粒度锁.

相对于粗粒度锁在线程层面实现并发,细粒度锁可以在数据结构层面实现并发.几乎所有数据结构(如:堆栈^[]、队列^[]、链表^{[, ]}、哈希表^{[, , ]}、树形结构^[])等都可以采用细粒度锁来实现多核数据结构并发.这种技术在简单数据结构(例如:堆栈队列、哈希表、跳表)中实现的效果很好,然而在树形结构,特别是需要调整平衡的树形结构中效率却不高.其根本原因在于,基于细粒度锁的实现需要对树形结构中附近区域内的多个节点进行加锁操作,同时只允许一个线程进入共享区进行操作来保障共享数据的安全.对于需要平衡的树形结构来说,插入、删除操作都带来树形结构的调整,这就意味着加锁的范围会很大,降低了数据结构的并发性.Leo^[]通过将树的平衡操作分离实现了一个平衡二叉树,其核心思想是在进行插入、删除操作时并不立即进行平衡调整,而是等到一定时间后再进行平衡调整.基于这样的思想,Nurmi放松了平衡的条件,实现了chromatic树^[],这是一种采用面向叶子(leaf-oriented)技术的红黑树.在此基础上,Boyar通过修改chromatic树的平衡条件提高了其性能^[],并首次给出了完整的正确性证明.

手连手锁是一种特殊的细粒度锁,在这种方法中,每个节点都维护一个锁.线程在遍历时,只有当获得下一个节点的锁之后才会释放当前节点的锁.相对于全局锁,手连手锁的特点是缩小了锁影响的节点范围.文献[]提出了一种基于手连手锁的并发平衡二叉树数据结构.在文献[]中提出了一种基于手连手锁的红黑树结构.

综合近几年来二叉树研究的情况,在多核时代的树形数据结构设计中,基于细粒度锁的实现会对树中一定范围的节点进行锁定,这在一定程度上会对并发的更新操作产生影响.

此外,由于基于锁的技术能够有效保护共享数据,一些特殊设计的锁(如:自旋锁(spinlock)、读写锁(rwlock))在Linux操作系统中得到了广泛的使用.传统上,当发生访问资源冲突时,可以有两种选择:一种是死等,另一种是挂起当前进程,调度其他进程执行.spin lock就是一种死等的机制,当前的执行线程会不断地重新尝试直到获取锁进入临界区.因此,自旋锁在同一时刻只能被最多一个内核任务持有,所以,一个时刻只有一个线程允许存在于临界区中.在多核时代,自旋锁总是只允许一个CPU核访问共享资源,其余CPU核均是忙等待,无法发挥多核的优势.考虑到这样的情况,Linux中还提供了读写锁,该方法允许多个CPU核读者同时访问,绝对限制只有一个核可以作为写者.当读者访问资源时,写者必须忙等待,反之亦然.然而,随着计算机硬件的快速发展,获得各种锁的开销相对于CPU的速度在成倍地增加.在大部分非x86架构上获取锁使用了内存栅(memory barrier),这会导致使用锁的时候处理器流水线停滞或刷新,因此使用锁的开销相对于CPU速度而言就越来越大,因此,一种能够提供高并发性的同步机制——Read-Copy-Update(RCU)^[]即被提出,它允许reader和writer并发地访问共享数据,支持一个writer和多个reader之间的并发.通过维护多个版本的数据,RCU保证了reader读取到的数据的一致性,还保证在reader完成读取前,被访问的数据不会被释放.

综合近几年来二叉树研究的情况,在多核时代的树形数据结构设计中,基于细粒度锁的实现会对树中一定范围的节点进行锁定,这在一定程度上会对并发的更新操作产生影响.

如图 6所示,对于读者,在访问被RCU保护的共享数据时可以直接访问,不用关心这个数据是否被锁住;而对于写者,在进行更新操作时,首选需要获得该数据的一个拷贝(如图 6中步骤2所示),然后对该拷贝进行更新,在没有任何读者来读取该数据时,将这个原始数据指针修改为指向该更新拷贝(如图 6中步骤3所示),于是就完成了修改操作.RCU的好处是读操作是无锁的,所以不存在同步问题,也不需要内存栅栏,对于由于锁机制导致的死锁和内存延迟等问题都有较好的改善.写操作的同步开销相对较大,因为需要等待合适的更新数据的时机,以及增加了原始数据释放、修改指针等操作,如果当前存在多个写者,依旧需要使用锁机制来同步其他写操作.RCU在Linux内核2.5.43版本开始使用,截至2014年,已经使用了超过9

在2015年召开的SOSP会议上,Alexander等人^[]提出了RCU的改进版RLU(read-log-update)技术.相对于RCU只允许多个读、一个写机制来说,RLU的最大优势是允许多个读、多个写同时进行,提高了并发性.

control,简称OCC)是一种并发控制的方法,首先出现在数据库系统^[]的相关工作中.其核心思想是让每个线程分离执行,使得每个线程执行时并不受到其他线程的干扰,当线程需要对数据结构作修改时,再对比前后是否保持一致性状态,如果确认状态一致,那么说明在这段时间内没有任何其他线程对数据结构做过修改,该线程提交修改,并且更新版本号;否则,线程需要回滚重试.

memory,简称STM),被用来设计并发树^[]和并发平衡树^[].后来,OCC被用来对并发二叉树中查询操作进行优化^[].值得注意的是,演进条件“无干扰”本身就具有乐观并发性,即旧值和新值比较时,只有不存在冲突时才能避免重试.无干扰的演进条件屏蔽了线程操作的中间状态,而通过数据结构的前后版本对比来确定前后是否保持一致.显然,这种演进条件比无锁和无等待要弱得多,因为它并不能保证在某一时刻至少一个线程是处在演进状态的(可以把演进看作是数据结构的一种不断改变的状态).然而,这种演进条件也有一定的好处,其实现思想简单,极大地简化了设计并发数据结构的过程,程序员不用花时间去思考如何验证数据结构的正确性.乐观并发控制的思想并不一定用在非阻塞技术中,如文献[]中提出了一种基于细粒度锁的乐观平衡二叉树,文献[]中提出了一种易于证明的乐观并发跳表.

事务性内存可分为两类:软件事务内存(STM)和硬件事务内存(HTM),硬件事务内存的概念很早于1986由 Herlihy^[]提出,然而直到最近的Haswell处理器上,才开始提供硬件事务内存接口^[].借鉴硬件事务内存的思想,1995年,麻省理工大学的Shavit教授在其论文中首次提出软件事务内存的概念^[],并因为在该领域的一系列杰出贡献获得了2012年分布式领域著名的Dijkstra奖.软件事务内存的核心思想是假设多用户并发的事务在处理时不会彼此互相影响,各事务能够在不产生锁的情况下处理各自影响的那部分数据.在提交数据更新之前,每个事务会先检查在该事务读取数据后有没有其他事务又修改了该数据.如果其他事务有更新的话,正在提交的事务会进行回滚.在数据冲突较少的环境中,偶尔事务回滚的成本会低于读取数据时锁定数据的成本,因此可以获得比其他并发控制方法更高的吞吐量.

软件事物内存是并发实现技术中锁的一种替代机制,它的出现引起了研究人员和开发人员的高度关注,分别从编程语言、编译器、指令执行等各个软件层面进行了深入研究^{[, , , , , , , , , ]}.目前主流语言都在不同程度上支持软件事务内存^[],其中,Clojure将软件事务内存集成在其核心语言中.相对于其他并发实现技术,软件事物内存对于程序开发人员的好处在于,简化了并发设计中对于资源共享、冲突部分的软件设计.相对于传统意义上广泛采用的加锁技术,STM的概念要简单得多,因为每一个事务可以理解为隔离的,就像只有单个线程进行操作一般,而死锁等特殊情况都由系统来控制完全加以避免,程序员无需担心这些问题.软件事物内存简化了无阻塞编程的难度,然而,相对于成熟的基于锁的技术,软件事物内存需要记录每次操作日志,因而带来不小的开销,在高并发情况下,不断的事物回滚减弱了多核数据结构执行的效率,扩大了事物执行的顺序开销.因此,目前软事物内存尚未成熟,远未达到实际系统中大规模采用的程度^[,

^{资源竞争是并发编程中存在的最核心问题,通常可采用互斥的方式来解决.操作系统分别从软件和硬件层面提供了支持,软件层面可以采用信号量和锁的机制,硬件层面则提供了原子操作的手段.从CPU指令执行的角度来看,软件层面的信号量和锁通常涉及多个CPU执行周期,而硬件层面的原子操作则能够由一条指令完成,因此原子操作执行速度最快,这使它成为高速并发数据结构设计的首选.原子操作具有不可分割性,在执行完毕之前不会被任何其他任务或事件中断,也不会被线程调度机制打断.在并发编程中,经常采用的原子操作包括:}

^{需要指出的是,MCAS可以同时对多个内存单元的数据进行compare-and-swap原子操作,因此在并发数据结构设计中更具灵活性,但是MCAS的最大缺点是可移植性差,很多硬件并不提供支持.原子操作使得并发线程对资源竞争的相应速度达到最大化,同时也保证了对并发线程的隔离.}

^{标志位是近年来多核数据结构非阻塞算法中最为核心的辅助技术,主要用于让线程对竞争区域的操作可见,即明确其他线程对自身线程操作区域的动作.因此,标志位的好处在于使得其他线程不必等待占有临界区的线程操作,而是能够感知临界区的当前操作,从而做出相关动作.对标志位的修改只能用原子操作来实现,这样才能做到线程之间的绝对隔离.}

^{文献[]中最早提出了一种用标志位和CAS操作实现的无锁链表,Michael[]在前人的基础上,改善了内存管理机制,并且大量优化了并发效率.Lea在此基础上实现了ConcurrentSkipListMap,并集成到java.util. concurrent中.该并发跳表被认为是最快的并发跳表,经常被用来和并发平衡二叉树、乐观并发跳表等实现作效率对比.2010年,Ellen等人[]将标志位和原子操作引入平衡二叉树的设计中,极大地降低了由于插入、删除操作造成的平衡开销,首次实现了无阻塞的平衡二叉树,取得很大的突破.从第3.5节的分析中我们也可以看出,标志位和原子操作是近几年并发树型结构采用的主要技术.值得注意的是,对于原子操作的选取需要慎重考虑底层硬件的支持,否则整个结构的可移植性和实用性都不高[].}

应用标志位和原子操作的示意图如图 7所示,每个节点都维护一个标志位,初始状态为CLEAN,当需要进行插入或删除操作时,多线程采用CAS原子操作进行竞争,只有一个线程能够进入插入循环圈(如图 7所示,在CLEAN右边)或删除循环圈(如图 7所示,在CLEAN左边)进行活动,这样使得进行并发操作的多个线程得到隔离,保证了并发操作的安全性.以插入循环圈为例,只有一个线程进入,其他线程在外面等候,通过iflagCAS操作将该节点标志位从CLEAN设置为IFLAG,然后,通过iflagCAS操作将孩子节点的标志位从CLEAN设置为IFLAG,等到插入完成后,再利用iunflagCAS操作将该节点和孩子节点的标志位一同恢复到CLEAN.

Kogan在2011年^[]提出了首个满足无等待演进条件且高效的队列结构,该结构的基本思想是将所有线程的操作记录到线程数组中,使得后来的线程能够帮助之前的线程完成操作,因而每一步操作都可以在固定步骤内完成.这种技术参考了文献[]中提出的快速和慢速通路方法(fast-path-slow-path

目前,已有多核数据结构都是特定构建的,支持的功能以及采用的关键技术都存在很大差别,并没有形成一套系统化的规范准则.上述6种核心技术各有特色,在多核数据结构设计中需要慎重选取.在对它们进行分析后得到如下对照表(见表 1).

如表 1所示,不同核心技术在已实现结构中达到的最大演进条件各不相同,线程监控数组技术和通用构建实现的演进条件最高,达到Wait free级别.但是,基于线程监控数组的方案很难实现,实际应用很低.通用构建在几种情况下得分都比较落后,因此不适合作为实际选取的开发技术.基于锁的方案虽然是一种阻塞实现,且运行效率为中等,但是由于从单核时代就已经大量运用,程序员较为熟悉,因此实际应用最广泛.标志位、原子操作和乐观并发控制具有运行效率高等特点,但是对程序员友好程度低,开发难度较大,实际研究和应用刚刚开始,这也意味着它们是目前最具研究潜力的两项技术.

5 并发数据结构开发 5.1 并发数据结构开发流程

设计并实现并发数据结构是一个复杂的过程,需要涉及很多概念和步骤,整个过程可以总结如图 8所示.

如图 8所示,并发数据结构的设计和实现工作可以总结为3个主要步骤:(1) 分析;(2) 设计;(3) 实现和验证.

首先通过实际需求调研,选择合适的数据结构.然后查看国内外文献,以及搜索开源代码来确定这些数据结构是否已有成熟的实现.对于已有开源实现的,分析其工作原理、性能和已经达到的演进条件,可作为下一步设计的参考对比.对于还没有实现的,则需要明确演进条件,作为下一步设计的基础.就目前的软硬件条件来说,对多核数据结构的演进条件(意味着能达到的性能)的要求主要集中在无锁层面,对于更高的演进条件(集居数无关无等待、有界无等待和无等待),由于实际完成难度太大,因此建议慎重考虑.

根据演进条件、对程序员的友好程度、结构执行的效率、应用场景中对于数据结构中执行不同操作的需求(如:侧重读访问或是读写均衡)等因素来选择实现技术手段.例如:如果想要实现一个阻塞的、执行效率高的数据结构,则基于锁的实现是一个很好的选择.如果想要实现一个obstruction-free的、程序员开发容易的数据结构则可以考虑软件事物内存这种方式来实现.如果应用需求中读操作很多,而插入、删除比重很小,则可以考虑利用OCC技术来实现.最后,再综合考虑数据结构具体的组织形式和相应的插入、删除、查询、调整等算法.合理的技术路线选择能够在很大程度上指导和简化之后的算法设计和实现.

选用合适的语言来实现,一般建议选择自己最熟悉的语言,这样可以减少开发难度.此外,选择的开发语言必须能够支撑步骤(2)中选择的实现技术手段.例如:在步骤(2)中确定要选择软件事务内存,那么所选用的开发语言需要支持.如果在步骤(2)中是选择基于锁的实现,因为不同开发语言对锁的实现其实差异很大,所以也需要认真评估.选定开发语言后,接下来就是按照之前的设计,具体实现这个数据结构.然后分别从理论和实验角度验证数据结构的正确性,并通过实验来验证相应结构的性能.

5.2 Java中现有并发数据结构实现情况

由于并发数据结构存在设计和实现上的难度,因此真正已发布的、稳定的并发库其实并不太多.Java中的java.util.concurrent是极少数得到广泛应用的软件包,现已在并发编程中成为很常用的工具类.在Java 5之前,Java中如果需要处理并发,那么通常需要使用wait()、notify()和synchronized手工实现并发处理的代码,加上需要考虑性能、死锁和资源管理等因素,开发的负担会很重.从Java

OnWriteArraySet.由此可见,目前Java 8版本中只提供一些最基本的并发数据结构,对于一些复杂的结构,则需要编程人员自己实现.

6 多核CPU数据结构正确性理论分析方法

设计出多核CPU数据结构后,就需要评估设计的正确性,通常有两种手段可选:实验的方法和理论分析的方法.实验的方法通常比较直观,理论分析的方法则逻辑性要求更强,表达起来也更困难.

通过对前人在多核CPU数据结构正确性分析方法进行对比研究,总结如下.

结构不变性主要用来说明并发操作并不会改变原始数据结构的属性.每种数据结构都有其自身特点的数据组织形式(如:链表和树的结构就不同),这些性质在数据结构被创建时就已成立,并且任何操作都不能改变这些性质.因此,当多线程并发地对多核CPU数据结构进行操作时,无论经过多少次插入、删除、查找,最终得到的还是同种性质的数据结构(如:初期是二叉树,经过N次并发操作后还应该是二叉树.不允许出现初期是二叉树,经过N次并发操作后变成m叉树).在具体分析说明时涉及到两个关键步骤:(1) 列举出这种结构的不变性质;(2) 对每一种操作都分析其不会改变原来数据结构的性质.举个例子:如果现在来分析并发跳表的结构不变性,则需要首先列举出跳表的结构的不变性质:(1) 哨兵节点不能改变.(2) 每一层的节点都按照关键字排序,并且不会出现重复的关键字.(3) 下层节点的节点数一定不少于上层节点.然后,再分别对查找、插入、删除、置标志位等操作进行分析,说明这些操作并不会改变其跳表的属性.

安全性意味着对并发数据结构的操作不会出错^[].对安全性的一个重要评价是可线性化,其基本思想是每一个并发的经历(history)都等价于一个顺序的经历.通常来说,用来说明并发数据结构的可线性化性质的方法就是指出该算法的可线性化点(linearizability point),然后指明在该线性化点的并发操作是如何映射为不同线程的等价顺序操作的.

当考虑并发数据结构的活性时,我们期待对这个数据结构的操作最终都能够完成^[].活性意味着并发数据结构算法最终在怎样的情况下完成.通常可以用演进条件来表示,如无死锁、无饥渴、无锁、无等待等.如果保证算法调用不会因为互相等待而无法获取资源,那么称其为无死锁.如果保证算法调用最终都能取得请求的资源,那么称其为无饥渴.如果保证算法某次调用能在有限的步骤内完成,那么这种方法是无锁的.如果算法每次调用总是在有限步骤内完成,那么这种方法是无等待的.

随着商用多核(multicore)和众核(many-core)系统越来越普及,软件中数据结构对多核支持的需求也就越来越迫切.因此,如何在多核时代提升数据结构的性能成为研究的热点.结合已有相关研究成果及其发展趋势,我们认为,以下有关研究将是研究者近年来所关注的热点问题.

基于硬件事务内存的并发数据结构研究

支持无等待的高效可实用的数据结构研究

按照多核数据结构演进条件的定义,演进条件越高,意味着活性越高,也在一定程度上表明其性能越好.在目前已经实现的数据结构中,只有采用线程监控数组技术实现了高效、实用的无等待的队列,虽然采用通用构建也可以得到无等待的数据结构,但是这些实现效率都不高^{[, ]}.因此,对于很多并不具有无等待性质的数据结构来说,总是有部分比例的线程在多核执行时存在等待的时间.在这个问题上,任何高效、实用的数据结构(如:哈希、链表、树等)研究的突破都将产生较大的实际影响.

基于标志位和原子操作的无锁带调整复杂树型结构研究

标志位和原子操作是近几年来并发树型结构研究的重点,已在平衡二叉树上得到实现.然而,对于一些更加复杂的树形结构,如红黑树、空间树、前缀树、后缀树等,由于其结构组织本身具有特殊性或者存在特殊的调整策略,目前还少有文献涉及,因此这方面具有比较大的研究空间.

分布式系统的多核数据结构研究

现在大型系统都是分布式架构的,文献[]对分布式系统中不同机器的内存建立了一个统一的映射,并在上面建立B+树.这样,对于用户来说,看到的是一棵统一的B+树,然而,B+树上不同节点是映射到不同机器的内存中的.文献[]中B+树的多核实现是基于锁的传统实现.那么,如何发挥多核优势,研究并设计出适应分布式环境的无锁数据结构也将是研究者关注的热点.

总之,多核的出现给我们带来机遇的同时也带来了巨大的挑战.基于共享内存的多核数据结构已成为研究者关注的热点问题.为了有效发挥硬件多核的优势,多核数据结构及其相关研究还存在许多挑战性问题,需要不断地去探讨和研究.