无锁数据结构（1）：简介
（点击上方公众号，可快速关注）
来源： 伯乐在线 - 乔永琪
英文出处：khizmax
如果转载，请发送「转载」二字查看说明
希望本文能成为无锁（lock free）数据结构系列文章一个好的开端。我很乐意与社区分享我的经历，这个系列就什么是无锁数据结构、如何实现以及 STL 容器概念是否适用于无锁容器，何种情形下适合应用无锁数据结构做一些分享。
谈论无锁数据结构，必然要谈论诸如原子操作、编程语言中的内存模型、安全内存回收以及在此基础上的编译和优化、现代CPU设计等内容。所有话题或多或少都会在这一系列文章中得到讨论。
我大胆地讨论这些话题，不是因为觉得自己是这些领域及其权威的专家。倘若我没有这些概念，我无法创建并维护这个libcds库——这是一个包含无锁容器和安全内存回收算法的开源C++库。Cds代表并发数据结构，前缀”lib”代表“library（库）”。
我开始构建此库，是在2006年。
当时我在一家超级大公司为某个电信运行商做软件开发。我们极其困难地在各种硬件平台（the zoo of hardware platforms）上开发服务器应用，很快就出现了性能问题（必然会出现该问题）。该问题用平行数据处理的方式得到了解决。通常，并行涉及共享数据，访问该数据必然要求同步。某天，在一次讨论中同事问我：“你从来就没有听说过无锁队列？”，那会我对此一无所知。我谷歌搜索之后，发现关于无锁队列伪代码的文章寥寥无几。来来回回读了好几遍，一无所获。 就在“一无所获”这种情形下，我鼓舞自己说：“你们这些蠢货，我才是全世界最聪明的”。接着尝试简化算法，并尝试在常识和这些算法之间寻求一种平衡。和段错误（segmentation fault）奋战了一个月之后，我以前的常识都没有用。那时真是一无所获，即使IT领域获得某种程度的成功，但是我完全不知道它的机理。但它确实在某种程度上是可以实现的，不然那些聪明家伙绝不会写这些文章，其他聪明的家伙也绝不会去引用这些文章。追溯这些论文，我读了大量的文章，从CPU设计、软件开发者指南开始，到关于无锁算法实现基本方法的综述结束。
一次偶然的机会，我用C++在这个项目做了一些开发，实现了一些原语。不过在2006-2007年那段时间，原语啥都不是；C++标准库仍然沿用所谓的C++ox优化方式，STL中并没有原子性原语，接口也只是一个轮廓，编译器时不时地对我的原子原语恶作剧。特别是在临界区竟然出现不能执行的代码。直到2008年，libcds库开始有了一个模糊的轮廓。第一次平台测试给了我很大的鼓励，甚至是极大的鼓舞（快了50倍），从此我沉浸在无锁的世界。2010年，我在SourceForge上发布了此库的0.5.0版本。截至今天（2014年3月）版本库是1.4.0，目前正在开发的版本是1.5.0。
现在，我打算对无锁数据结构做一个总体的概括。程序员设计开发软件项目最大的难点在于，如何最有效地利用平台的所有资源，特别是服务器。现代计算机，即使很小的智能机亦或者平板电脑，都是一个多核处理设备。性能调优最主要的方法便是并行编程，线程并行处理一些共享数据。因此我们的主要任务便是如何通过并行的形式，高效地访问共享数据。
（译者注：同步劣势：一、并行的对立面，即杀死并行操作；二 、弱分布式，加剧恶化多个连接响应）
上个世纪80年代，一种叫做结构编程的方式很流行，通过此方式认为可以编写出好的程序。结构编程的忠实拥护者Niklaus Wirth，Pascal语言的作者，写过一本畅销书《算法+数据结构=程序》。有趣的是，这个古老的等式正是现代API类型线程——Win32 API 的弱点，该API由操作系统创建而成。该API提供了一种并行编程方式（就是线程），但它并没有提供一种可实现共享存取的并行数据结构构建方式。恰恰相反，Win32 API通过同步原语的方式保障数据安全，同步是程序并行的一大瓶颈。顾名思义，同步就是并行的对立面：当并行算法与连续数据结构结合在一起时，它需要提供同步原语才能运作——比如临界区、互斥锁、条件变量。结果，所有线程在队列中等待以获取数据结构，杀死了并行操作。有些同步原语是操作系统内核对象，调用此对象代价是很昂贵的：上下文切换或许是必须的，切换到内核执行级别，支持访问被同步原语数据保护的等待队列。所有你需要做的是，仅仅改变指示符（designator）的含义，比如去执行一两个汇编函数。负载可能很高，事实上也确实如此。毕竟，操作系统内核对象是一个数量有限的资源。
同步的另一个缺点是弱分布式。一旦访问数据的线程增加到一定数量，就会成为程序的一个瓶颈。如果并行的级别不断增高，超出了可容纳的合适比例，就会加剧恶化多连接的响应。
Wirth的等式“算法+数据结构=程序”，我只用在libcds数据结构中。然而在我的库中，不会有并行排序算法或者并行for-each算法。本库只仅包含几种竞争性数据结构——queue、list、map、set等。对无锁数据做必要的算法支持，这些算法都是内存安全回收（safe memory reclamation）类型的；通常这些数据结构实现很少。最初决定阶段：一般来说，实现某个有意思的队列或者map算法很少，我也不知道那种更好一些。因为，“好”与“坏”是一个相对的概念，取决于有限的计算机硬件所对应的有限任务。其次，直到你实现了某种算法，并于其它算法做过比较，你才知道它不是不更好的。既然算法都实现了并且都调试了，为何不放在库中，让用户多一种选择呢？
在教育领域，对共享数据提供并发访问的竞争数据结构研究有下面几个方面：
无锁数据结构；
细颗粒度的算法；
事务内存
目前还没有嵌入式的事务性内存。不过事务性内存是一个巨大的研究课题，终极目标是未来能够实现它。基于事务性内存的算法表明，简单地说，内存支持原子性事务的原子性提交或者回滚。显然，这样的内存应该在硬件中实现。研究者承认，目前的软件实现还没有充分具备这样的能力。不过英特的Haswel处理器设计已经在其代码指令中支持事务，可以说基于事务性内存规则算法的全盛时期就要到来了。
细颗粒度的算法是一种偏离同步方法的算法，通常被认为并不是基于操作系统提供的同步原语应用，而是基于“轻量级的”原子性原语，比如自旋锁。在此类原语之上构建的数据结构，可以并行读取，甚至并发写入。在此基础上，同步应用于节点、页、桶（bucket）级别的数据结构中，同时被构建在操作系统相关的算法中。在相对轻量级连接中，细粒度容器可以和无锁容器相媲美。因此，libcds库并没有轻视此类型的数据结构。
（译者注：自旋锁适用于任何锁持有时间少于将一个线程阻塞和唤醒所需要的时间的场合，即减少上下文切换、数据结构更新）
我所提到的数据结构不需要外部同步访问，它是无锁数据结构。它是一种非官方的、纯技术性定义，反映的是容器的内部构件以及在此之上的各种操作。重点强调“外部”的目：应该明确一点，没有处理器的支持，几乎是无法构建无锁数据结构的。无锁容器中的这种支持，不是由访问容器序列化方法的同步机制提供的，而是原子性修改机制提供的。此机制已注入了容器的方法中，亦或者是容器组成（节点、桶、页）级别的内部同步机制提供的。
（译者注：缺少处理器的支持，几乎是无法构建无锁数据结构的）
无锁对象（lock-free object）的正式定义如下 [Her91]：判断一个共享对象是否为无锁类型（非阻塞对象），就看它是否能确保一些线程在有限的系统步骤中完成某个操作，并且与其他线程的操作结果无关（即便其它线程操作没有成功）。一个更加严格的非等待对象（wait-free object）是这样定义的：判断某个对象是否为非等待，就看每个线程是否是在有限的步骤中完成了在该对象上的操作。无锁的条件是至少保证一个线程完成任务，而更苛刻的非等待条件则是要保证所有的线程都能成功完成任务。线性化（linearizability）在竞争数据结构上也有理论性的定义[Her90]，作为一种标准，在验证无锁算法正确性方面，发挥着重要作用。简而言之，算法是否为线性化的，就看算法完成之后的操作结果是否显而易见，不言自明。举个例子来说，只要插入函数完成，列表插入操作的结果就显而易见的。听起来很白痴，但没有人能想出某个算法做了一个列表插入，却不是线性化。再譬如，各种类型的缓存可能违反这种特性：我们先将一个新元素放入缓存中而非直接插入，接着命令其它线程“将该缓存中的此元素插入列表中”，直到此元素插入进去。或者只有当缓存中有相当数量的元素时，我们才做一次插入。那么插入函数执行完毕，我们依旧不能保证此元素在列表中。可以确定的是，此元素迟早会被插入到列表中。
这些定义广泛地用于科学研究领域。本篇非科技类文章，因此我用无锁这个狭义的术语定义竞争性容器类。此类构建无需传统同步模板应用，甚至同步。那么无锁算法的特点是什么？我认为第一明显的特征是其复杂性。请问如何在单项链表基础之上实现常规队列？下面是一个非常简单的代码实现：
struct Node {
Node * m_pNext ;
};
class queue {
Node * m_pHead ;
Node * m_pTail ;
public:
queue(): m_pHead( NULL ), m_pTail( NULL ) {}
void enqueue( Node * p )
{
p->m_pNext = m_pTail ;
m_pTail = p ;
if ( !m_pHead )
m_pHead = p ;
}
Node * dequeue()
{
if ( !m_pHead ) return NULL ;
Node * p = m_pHead ;
m_pHead = p->m_pNext ;
if ( !m_pHead )
m_pTail = NULL ;
return p ;
}
};
甚至可以写得更简短一点，这就是无锁 Michael&Scott 队列经典算法实现。它看起来就像入队、出对方法（和压栈、弹出的意思相同）。（代码是libcds库类cds::intrusive::MSQueue简化版）
bool enqueue( value_type& val )
{
node_type * pNew = node_traits::to_node_ptr( val );
typename gc::Guard guard;
back_off bkoff;
node_type * t;
while ( true ) {
t = guard.protect( m_pTail, node_to_value() );
node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
if ( pNext != null_ptr<node_type *>() ) {
// Tail is misplaced, advance it
m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed );
continue;
}
node_type * tmp = null_ptr<node_type *>() ;
if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed ))
{
break;
}
bkoff();
}
++m_ItemCounter;
m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel,
CDS_ATOMIC::memory_order_relaxed );
return true;
}
value_type * dequeue()
{
node_type * pNext;
back_off bkoff;
typename gc::template GuardArray<2> guards;
node_type * h;
while ( true ) {
h = guards.protect( 0, m_pHead, node_to_value() );
pNext = guards.protect( 1, h->m_pNext, node_to_value() );
if ( m_pHead.load(memory_model::memory_order_relaxed) != h )
continue;
if ( pNext == null_ptr<node_type *>() )
return NULL; // empty queue
node_type * t = m_pTail.load(memory_model::memory_order_acquire);
if ( h == t ) {
// It is needed to help enqueue
m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed );
continue;
}
if ( m_pHead.compare_exchange_strong( h, pNext,
memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
{
break;
}
bkoff();
}
--m_ItemCounter;
dispose_node( h );
return pNext;
}
这是一个很复杂的算法，相同的单向链表。不过即使大体比较一下，也能看出无锁队列的一些特征。在无锁队列中，我们可以找到如下描述：
无限循环：稍后我们会尝试执行这个操作，这是一个实现了原子性操作compare_exchange的典型模式；
局部变量的安全性（guards），需借助于无锁算法中安全内存收回方法。本例中，为风险指针（Hazard Pointers）方法；
采用C++11标准的原子性原语：load、compare_exchange以及内存栅栏（memory fences）memory_order_xxx;
helping ：一种广泛存在于无锁算法中的方法，特别是在一个线程帮助其它线程去执行任务场景中；
补偿策略（functor bkoff）： 这不是必须的，但可以在连接很多的情况下缓解处理器的压力，尤其是多个线程逐个地调用队列时。
我不打算在本文中，进一步就这些事情展开广泛的讨论，开启新的话题。让我们保留这份好奇心，我会在接下来的文章中逐一阐述。
接下来的一篇文章将集中关注无锁数据结构的基础概念：原子性和原子性原语。
最后，给大家推荐一些有用的资料，其中不泛竞争性编程基本议题的广泛讨论。
截至目前我所知道的两本不错的著作：
Nir Shavit, Maurice Herlihy The Art of Multiprocessor programming。此书中，世界级著名无锁作者描述了大量并行算法及其实现方法。所有的例子都是用Java实现的，免去了C++内存回收带来的麻烦，采用Java实现，只需考虑内存模型以及其它的。倘若你的技术栈是C++，那就必须独自用C++实现了。尽管如此，此书还是很有帮助。
Anthony Williams C++ Concurrency in Action。此书中，世界级著名C++作者解答了C++多线程编程的诸多问题，描述了基于并行算法实现的新C++标准以及其它工具。强烈推荐大家读一读。
链接：
[Her90] M. Herlihy, J. M. Wing Linearizability: A Correctness Condition for Concurrent Objects, ACM Transactions on Programming Languages and Systems, 1990
[Her91] M. Herlihy A Methodology for Implementing Highly Concurrent Data Object, 1991
[Mic96] M.Michael, M.Scott Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
觉得本文有帮助？请分享给更多人
关注「算法爱好者」，修炼编程内功