使用CAS实现无锁的SkipList

感谢同事【付哲】发布此文。

无锁

并发环境下最常用的同步手段是互斥锁和读写锁,例如pthread_mutex和pthread_readwrite_lock,常用的范式为:

void ConcurrencyOperation() {
	mutex.lock();
	// do something
	mutex.unlock();
}

这种方法的优点是:

  1. 编程模型简单,如果小心控制上锁顺序,一般来说不会有死锁的问题;
  2. 可以通过调节锁的粒度来调节性能。

缺点是:

  1. 所有基于锁的算法都有死锁的可能;
  2. 上锁和解锁时进程要从用户态切换到内核态,并可能伴随有线程的调度、上下文切换等,开销比较重;
  3. 对共享数据的读与写之间会有互斥。

无锁编程(严格来讲是非阻塞编程)可以分为lock free和wait-free两种,下面是对它们的简单描述:

  • lock free:锁无关,一个锁无关的程序能够确保它所有线程中至少有一个能够继续往下执行。这意味着有些线程可能会被任意的延迟,然而在每一个步骤中至少有一个线程能够执行下去。因此这个系统作为一个整体总是在前进的,尽管有些线程的进度可能没有其它线程走的快。
  • wait free:等待无关,一个等待无关的程序可以在有限步之内结束,而不管其它线程的相对执行速度如何。
  • lock based:基于锁,基于锁的程序无法提供上面的任何保证,任一线程持有了某互斥体并处于等待状态,那么其它想要获取同意互斥体的线程只有等待,所有基于锁的算法无法摆脱死锁的阴影。

本文提到的无锁单指lock free。

lock free与CAS

常见的lock free编程一般是基于CAS(Compare And Swap)操作:

CAS(void *ptr, Any oldValue, Any newValue);

即查看内存地址ptr处的值,如果为oldValue则将其改为newValue,并返回true,否则返回false。X86平台上的CAS操作一般是通过CPU的CMPXCHG指令来完成的。CPU在执行此指令时会首先锁住CPU总线,禁止其它核心对内存的访问,然后再查看或修改*ptr的值。简单的说CAS利用了CPU的硬件锁来实现对共享资源的串行使用。它的优点是:

  1. 开销较小:不需要进入内核,不需要切换线程;
  2. 没有死锁:总线锁最长持续为一次read+write的时间;
  3. 只有写操作需要使用CAS,读操作与串行代码完全相同,可实现读写不互斥。

缺点是:

  1. 编程非常复杂,两行代码之间可能发生任何事,很多常识性的假设都不成立。
  2. CAS模型覆盖的情况非常少,无法用CAS实现原子的复数操作。

而在性能层面上,CAS与mutex/readwrite lock各有千秋,简述如下:

  1. 单线程下CAS的开销大约为10次加法操作,mutex的上锁+解锁大约为20次加法操作,而readwrite lock的开销则更大一些。
  2. CAS的性能为固定值,而mutex则可以通过改变临界区的大小来调节性能;
  3. 如果临界区中真正的修改操作只占一小部分,那么用CAS可以获得更大的并发度。
  4. 多核CPU中线程调度成本较高,此时更适合用CAS。

使用CAS实现无锁单向链表

单向链表实现的核心就是insert函数,这里我们用两个版本的insert函数来进行简单的演示,使用的CAS操作为GCC提供的__sync_compare_and_swap函数。

首先是无序的insert操作,即将新结点插入到指定结点的后面。

void insert(Node *prev, Node *node) {
	while (true) {
		node->next = prev->next;
		if (__sync_compare_and_swap(&prev->next, node->next, node)) {
			return;
		}
	}
}

代码分析:

  1. 首先修改node->next,此时node还没有完成插入,只能被本线程看到,因此这个修改可以直接进行。
  2. 在if中尝试修改prev->next,如果失败,则表明prev->next刚刚被其它线程修改了,则重复这一过程。

然后是有序的insert操作,即保证prev<= node <= next。

void insert(Node *prev, Node *node) {
	while (true) {
		Node *next = prev->next;
		while (next != NULL && next->item < node->item) {
			prev = next;
			next = prev->next;
		}
		node->next = next;
		if (__sync_compare_and_swap(&prev->next, next, node)) {
			return;
		}
	}
}

这段代码相比上一版本多了一个next变量。如果去掉next变量,那么代码就是下面的样子。

void insert(Node *prev, Node *node) {
    while (true) {
        while (prev->next != NULL && prev->next->item < node->item) {
            prev = prev->next;
        }
        node->next = prev->next;
        if (__sync_compare_and_swap(&prev->next, node->next, node)) {
            return;
        }
    }
}

上面的代码有着很严重的安全隐患:prev是共享资源,因此每个prev->next的值不一定是相等的!解决办法就是用一个局部变量来保存某个时刻prev的值,从而保证我们在不同地方进行比较的结点是一致的。

Key-Value数据结构

目前常用的key-value数据结构有三种:Hash表、红黑树、SkipList,它们各自有着不同的优缺点(不考虑删除操作):

  1. Hash表:插入、查找最快,为O(1);如使用链表实现则可实现无锁;数据有序化需要显式的排序操作。
  2. 红黑树:插入、查找为O(logn),但常数项较小;无锁实现的复杂性很高,一般需要加锁;数据天然有序。
  3. SkipList:插入、查找为O(logn),但常数项比红黑树要大;底层结构为链表,可无锁实现;数据天然有序。

如果要实现一个key-value结构,需求的功能有插入、查找、迭代、修改,那么首先Hash表就不是很适合了,因为迭代的时间复杂度比较高;而红黑树的插入很可能会涉及多个结点的旋转、变色操作,因此需要在外层加锁,这无形中降低了它可能的并发度。而SkipList底层是用链表实现的,可以实现为lock free,同时它还有着不错的性能(单线程下只比红黑树略慢),非常适合用来实现我们需求的那种key-value结构。LevelDB、Reddis的底层存储结构就是用的SkipList。

SkipList

那么,SkipList是什么呢?它由多层有序链表组成,每层链表的结点数量都是上一层的X倍,而它的插入和查找操作都从顶层开始进行。

470px-Skip_list.svg

(图片取自wiki)

从上图可以很容易看出查找的方式:

  1. 从顶层的头结点出发;
  2. 若下一结点为目标值,则返回结果;
  3. 若下一结点小于目标值,则前进;
  4. 若下一结点大于目标值或为NULL,则:
    1. 若当前处于最底层,则返回NULL;
    2. 下降一层,重复2-4步。

在SkipList中,结点层数非常关键,如果各个结点的层数均匀分布,那么插入与查找的效率就会比较高。为了实现这一目的,SkipList中每个结点的层数是在插入前随机算出来的,其基本原理就是令结点在i层的概率是i+1层的X倍,代码如下:

int RandLevel(int X, int maxLevel) {
	int r = rand();
	int level = 1;
	for (int j = X; r < RAND_MAX / j && level < maxLevel; ++level, j *= X)
		continue;
	return level;
}

插入新结点的过程与查找很类似,这里我们假设链表中的各结点不允许重复:

  1. 计算出新结点的层数lv;
  2. 从lv层的头结点出发,开始查找过程;
  3. 如果找到目标值,返回NULL;
  4. 如果当前处于最底层,则创建新结点,并依次将新结点插入到1-lv层;

可以看出,插入操作的1-3步是单纯的读操作,只有第4步才是对共享资源的写操作。而第4步的插入实质上就是有序链表的插入操作,我们在前面已经简述了如何用CAS实现它。因此,只要保证插入顺序是从底层向上依次插入,那么就可以将SkipList实现为lock free。插入顺序从底向上进行的原因如下。

N个插入操作肯定需要至少N次CAS,而任意一个CAS成功后就意味着新结点已经成为了SkipList的一部分,变成了共享资源,则新结点就需要遵循其它结点的原则:每个结点都同时存在于1-lv层。容易看出,只有从底层向上插入才能满足这一条件。

多个CAS操作本身没有原子性,即在N次插入没有完成前,新结点会表现出一定的不一致性,具体来说就是多个线程先后访问新结点时,看到的它的层数并不相同。这种不一致性会比较轻微的影响SkipList的性能,而不会影响它的正确性。

SkipList的插入代码如下:

void Insert(Node *node) {
	node->level = RandLevel(2, MAX_LEVEL);
	InsertInternal(head, node->level, node);
}
Node *InsertInternal(Node *prev, int lv, Node *node) {
	Node *next = prev->next[lv];
	while (next != NULL && next->item < node->item) {
		prev = next;
		next = prev->next[lv];
	}
	if (next == NULL || next->item > node->item) {
		if (lv != 0) {
			if (InsertInternal(prev, lv - 1, node) != NULL) {
				ListInsert(prev, node, lv);
			}
		}
	} else if (next->item == node->item) {
		return NULL;
	}
	return node;
}

其中ListInsert就是对前面有序链表插入的一个简单改写。整个插入过程递归实现,从而满足了插入顺序要从底向上的要求。

更多思考

在设计无锁SkipList时,不光需要我们将显式的锁用CAS替换掉,还需要尽量避免一些隐式的锁,以及一些非线程安全的函数。

  1. RandLevel中的rand()是非线程安全的函数,需要替换为线程安全的版本(如非标准库的rand_r()),或是由各线程自己来保存rand使用的seed。
  2. 在创建SkipList的时候需要指定一个MAX_LEVEL,即头结点的层数,这个值在此SkipList生命期中固定不变。一般来说12-20层都是可以接受的。
  3. 全局new内部会加锁,如果这里有瓶颈的话需要换用自定义的内存池。
  4. 如果使用了内存池,那么必须确保内存池本身是无锁且支持并发写的。否则就只能将SkipList改写为单写多读版本。
  5. 在计算新结点的层数时,需要传入一个maxLevel,这里有两种常见做法:可以传入SkipList的最大层数MAX_LEVEL,也可以传入当前最大层数topLevel + 1。两种做法的优缺点为:
    1. 传入MAX_LEVEL可能在SkipList中结点数量较少时就达到很高的层数,降低了此时插入与查找的性能;但如果有序插入多个新结点,能保证各结点的层数均匀分布。
    2. 传入topLevel + 1可以保证在结点数较少时不太可能出现很高的层数,但在有序插入多个新结点时,可能导致前面插入结点的层数整体要低于后面插入的结点。
  6. SkipList的修改操作也需要是lock free的,因此需要将Node中的item改为指针,在修改某结点值的时候用CAS来替换掉旧指针,并在完成后删除。
  7. SkipList也可以在最底层加入反向指针prev,这样就能直接O(1)的反向迭代。带来的问题是更大的不一致性——在插入未完成时两个线程分别正向和反向迭代,看到的SkipList是不一致的。但可以保证SkipList在插入完成后的最终状态是一致的。

本文只是对无锁SkipList设计的一个简单回顾,不包括详细的实现代码。因为还不确定自己设计的有没有纰漏,还需要认真学习一下LevelDB和Reddis中的SkipList代码。

参考:

http://en.wikipedia.org/wiki/Skip_list

http://www.myexception.cn/ai/972131.html

http://www.seflerzhou.net/post-6.html

http://coolshell.cn/articles/8239.html

http://blog.csdn.net/sunmenggmail/article/details/12648465

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 使用CAS实现无锁的SkipList

付哲

阿里云开发工程师

Latest posts by 付哲 (see all)

FavoriteLoading添加本文到我的收藏
  • 10,038 人阅读
  • 6 comments
  • Trackback are closed
  • Comments (6)
  1. 您好,首先感谢您的思考。

    针对您对skiplist是设计,我先提几个问题:

    1. 怎样保证prev节点不是一个被删除的节点?
    2. 怎样保证prev节点的next指针没有被修改过(注意,如果prev中下层next指针被修改,但上层指针未修改,那么cas next下层失败,上层成功,会造成断层情况)
    3. 可以用同样的思想实现delete?

    最后,再来看看这句话:
    “多个CAS操作本身没有原子性,即在N次插入没有完成前,新结点会表现出一定的不一致性,具体来说就是多个线程先后访问新结点时,看到的它的层数并不相同。这种不一致性会比较轻微的影响SkipList的性能,而不会影响它的正确性。”

    评论里不能贴图,如果您有空的话,咱们可以邮件或者qq交流。

    谢谢!

      • 付哲
      • 04/10. 2014 7:04pm

      你好,首先解答一下前面的问题:
      1. 这个skiplist的设计不包括删除,因为删除处理起来很麻烦。理论上删除也可以从最上层一层层用CAS修改指针来实现,但在所有层的指针都修改完毕后,这个结点还可能被某些线程访问着,需要等所有的线程都结束对它的访问后才能真正delete。如果有GC的话这一点并不复杂,但本文是基于C++写的,C++中为了实现这点就要对每个节点加上引用计数,首先会影响性能(访问结点的前后都要更新引用计数),其次要将引用计数也用CAS实现。因此在这个设计中我并没有加入删除功能。
      2. 需要在第i层CAS成功后才会去继续修改第i+1层,因此不会导致断层。
      3. 见上。

      下面的那句话可能我说的不是很严谨,N次插入指的是单个insert相当于在N层链表中进行插入。这里的强一致性就是整个insert操作是原子的,即要么其它读线程看不到这个结点,要么看到的时候它已经有N层了。而本文只实现了弱一致性,就是其它读线程可能看到的是有M(M<N)层的新结点。

      另外,本文其实是一次新人分享活动的内容总结,还很不完善,在完善后我会把具体的实现代码发出来的。对于删除操作,我会尝试去实现一下的。
      谢谢你的评论^_^

      • 您好!

        根据您刚才所提到的,只讨论插入的问题。

        第三点:
        “需要在第i层CAS成功后才会去继续修改第i+1层,因此不会导致断层。”

        这个想法是可行的,但是如果是这样的话,这个伪代码的描述就需要修改一下了。

        我的意见是:
        ListInsert(prev, node, lv);
        这个描述需要给出,因为根据第三点而言,事实上在这个函数里进行的是cas操作,那么这个操作的结果直接影响InsertInternal。
        所以需要对其返回值做判断,而不是仅仅在InsertInternal里给一个返回值。

        这样下来,这个insert算法可以说是lock-free了。然而,假如加上lock-free的删除操作,事实上比刚才您所描述的还要复杂一些,和GC无关,而是逻辑上的一些操作影响。
        还是建议参考一下Doug Lea的ConcurrentSkipListMap写法。

          • 付哲
          • 04/10. 2014 8:25pm

          嗯,原来贴上去的代码是我手写的……BUG已fix

    • axx
    • 05/16. 2014 2:04pm

    期待更多人讨论这个问题,尤其是删除操作。很感谢那些分享的人。

    • migsoft
    • 02/28. 2017 5:37pm

    删除用简单的CAS修改指针是有问题的,因为删除操作时在删除节点后可能正好插入了一个节点。
    这篇文章有说明:
    https://www.microsoft.com/en-us/research/publication/a-pragmatic-implementation-of-non-blocking-linked-lists/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F67089%2F2001-disc.pdf

You must be logged in to post a comment.

return top