搜狐公司研发中心版权所有,仅供技术交流,转载请保留上述文字

搜狗实验室技术交流文档Vol4:2C10K与高性能程序续篇摘要本文介绍了如何利用流水线和一些锁的技巧提高服务器吞吐量,以及新兴的LockFree技术.
PipeLine流水线是已经在大搜索中广泛应用的技术.
流水线解决4个问题:充分利用多CPU,尽量按照FIFO的原则处理用户请求,防止长请求阻塞短请求,提高磁盘I/O效率.
在第一篇技术通讯中讲到用epoll等技术在单线程中调度socketI/O才能达到最高的效率.
单线程的epoll类方法有一个前提是对每个用户请求,都不能占用太多的CPU来处理应用逻辑.
否则很容易出现一个CPU被占满,其它CPU空闲的情况.
总耗时较长且CPU和I/O交替进行的任务,如果是普通的每任务1线程,那么由于OS调度的随机性,对用户请求的响应很难做到先进先出.
用户请求的处理可以分为多个步骤,每个具体请求需要执行的步骤数目可能有差别.
比如对cache的访问,命中和未命中就差别很大,未命中时需要等待后台服务的处理.
每任务1线程的情况下,处理步骤较多的长请求会占据全部的工作线程.
这时候本服务器往往是IDLE的,但是却没有空闲的线程处理那些步骤较少的短请求.
一次用户请求往往需要多次磁盘I/O,普通程序都是串行的执行它们.
这样操作系统失去了内部合并和重排序I/O的机会.
流水线技术把一次任务拆为多个步骤,每一步都有各自专门的线程来处理,每个步骤称为流水线的一级.
拆分的原则是每一级都关心不同的资源:CPU,网络I/O,磁盘I/O,和其他服务的I/O等等.
每一级流水线有自己的线程或者线程池,各级之间通过消息队列通信.
传统模式流水线模式搜狐公司研发中心版权所有,仅供技术交流,转载请保留上述文字流水线继承了epoll类技术线程数不会膨胀的优点,同时通过步骤拆分充分的利用了多个CPU.
线程数少了以后,由于消息队列的存在,FIFO现在很容易保证.
流水线中,长请求只会占用流水线的后级,短请求仍然可以利用流水线的前集快速响应.
这极大地提高了并发.
负责磁盘I/O的任务步骤现在可以很容易的用多个线程来并行发起I/O.
流水线前级把多个磁盘I/O请求打入I/O队列,I/O线程处理完后再打入后级,后级每收集完全一组请求需要的数据后执行对应操作.
一些简单的同步技巧对于一些简单的需求,例如全局统计、引用计数等等,可以归结为对整数的原子计算.
可以使用一些轻量级的原子计算方法,比如Win32下的Interloced系列函数.
Interloced函数粗略的可以分为两族:一族以InterlocedAdd为代表,对应C语言中的A+=B模式;一族以InterlocedCompareAndExchange为代表,提供了CAS操作(Compare–And-Swap)的能力.
基于CAS操作,我们可以在一些更为复杂的需求上实现LockFree.
Linux下有cmpxchg函数实现CAS(kernel-devel).
DoubleCheck已经在Singleton模式中被广泛使用,这里就不多介绍了.
对于大数据集的并发操作,为防止并发线程在同一处阻塞,可以考虑把大数据集拆分成多个小数据集,对每个小数据集单独加锁.
这样既提高了并发度,又不会消耗太多的资源.
pthread_spinlock可以用来在少量线程间同步一些非常短小的操作,例如引用计数.
但是切忌,可能并发访问的线程不能过多,这些线程的优先级不能有差别.
LockFreeOS提供的mutex互斥体这样的线程/进程同步手段,从好的一面来说,只要互斥体是在锁状态,你就可以放心地进行任何操作,不用担心其它线程会闯进来搞坏你的共享数据.
但是也有很多弊病,用mutex的粒度过大容易导致线程闲置,粒度过小又容易导致各种deadlock/lovelock.
尤其是使用spinlock这种轻量级锁的时候,一旦各个线程的优先级不一致,几乎一定会出现优先级倒置带来的死锁.
为此人们提出了Wait-Free等待无关和Lock-Free锁无关的概念.
一个"Wait-Free"的程序可以在有限步之内结束,而不管其它线程的相对速度如何.
一个"Lock-Free"的程序能够确保执行它的所有线程中至少有一个能够继续往下执行.
这便意味着有些线程可能会被任意地延迟,然而在每一步都至少有一个线程能够往下执行.
因此这个系统作为一个整体总是在"前进"的,尽管有些线程的进度可能不如其它线程来得快.
基于锁的程序则无法提供上述的任何保证.
一旦任何线程持有了某个互斥体并处于等待状态,那么其它任何想要获取同一互斥体的线程就只好站着干瞪眼;如果两个线程互相等待另一个线程所占有的mutex,就只好僵死.
优先级倒置、信号中断、异常中止都是多线程程序的噩梦,但是Lock-Free对它们是免疫的.
毫无疑问,落实到最终实现,Lock-Free算法总要对应一些具体的原子操作,现在主要用到的就是CAS(Compare–And-Swap)以及它的一些变种.
搜狐公司研发中心版权所有,仅供技术交流,转载请保留上述文字LLSCCASDCAS与CAS2LL和SC是lockfree理论领域研究的理想原语.
LL[addr],dst从内存单元[addr]读取值到dst.
SCvalue,[addr]若自本线程上次从[addr]LL以来,没有任何SC操作在[addr]上,则把[addr]的值设为valueLL和SC都是原子操作.
实际上没有任何CPU直接实现了SC原语,一般我们用CAS类原语来部分模拟SC.
CAS原语负责比较某个内存地址处的1字长的内容与1个期望值,如果比较成功则将该内存地址处的内容替换为一个新值.
这整个操作是原子的.
现代CPU一般都支持CAS操作.
常用来做指针替换和原子计算.
对应的DCAS原语比较2个内存地址处的1字长的内容与2个期望值,如果成功则将这2个内存地址处的内容替换为2个新值.
这也是原子操作.
经典的用法是同时处理指针和其引用计数.
现在实现DCAS的CPU还很少.
作为一种折衷,CAS2原语比较某个内存地址处的2字长的内容与2个期望值,如果比较成功则将该内存地址处的内容替换为2个新值.
x86/x64的CPU支持CAS2原语.
使用这些原语有一个基本前提,CPU对1字长的内存数据简单存储是原子的.
具体到x86,"movl"这样的操作在地址已对齐的情况下是原子的,不会受到SMP的干扰.
DefinitionImplementationCASboolCAS(intptr_t*addr,intptr_toldv,intptr_tnewv)atomically{if((*addr==oldv){*addr=newv;returntrue;}elsereturnfalse;}x86:cmpxchgWindowsInterlockedCompareAndExchangex64:cmpxchg8bWindowsInterlockedCompareAndExchange64DCASboolDCAS(intptr_t*addr1,intptr_t*addr2,intptr_told1,intptr_told2,intptr_tnew1,intptr_tnew2)atomically{if((*addr1==old1)&&(*addr2==old2)){*addr1=new1;*addr2=new2;returntrue;}elsereturnfalse;}N/ACAS2boolCAS2(intptr_t(*addr)[2],intptr_told1,intptr_told2,intptr_tnew1,intptr_tnew2)atomically{if(((*addr)[0]==old1)&&((*addr)[1]==old2)){(*addr)[0]=new1;(*addr)[1]=new2;x86:cmpxchg8bWindows:InterlockedCompareAndExchange64x64:cmpxchg16b搜狐公司研发中心版权所有,仅供技术交流,转载请保留上述文字returntrue;}elsereturnfalse;}注意:SMP环境下使用comxchg系列指令时,需要lock前缀.
SpinLockSpinLock是一种轻量级的同步方法,它和mutex具有近似的语义.
但是当lock操作被阻塞时,并不是把自己挂到一个等待队列,而是死循环CPU空转等待其他线程放锁.
这样节省了OS切换线程上下文的开销.
如果确信需要同步的操作总是能在数条指令内完成,那么使用SpinLock会比传统的mutexlock要快一个数量级.
基于CAS原语设计很容易实现spinlockstructspinlock{intv;}voidspin_init(spinlock*sl){sl->v=1;}voidspin_lock(volatilespinlock*sl){do{nop;}while(!
CAS(&sl->v,1,0))}voidspin_unlock(volatilespinlock*sl){sl->v=1;}典型的,spinlock可能被用于修改计数器,或者同步一些浮点运算.
pthread提供了spinlock,请参阅pthread_spin_lock.
Lock-FreeLIFOStack借助CAS可以很大程度上避免同步操作,先来看一个用CAS原语实现的简单LIFOStack.
structcell{structcell*next;structvalue_tvalue;}structlifo{volatilestructcell*top;}voidlifo_push(volatilelifo*lf,cell*cl){do{cl->next=lf->top;}while(!
CAS(&lf->top,cl->next,cl))}cell*lifo_pop(volatilelifo*lf){cell*head,*next;do{head=lf->top;if(head==NULL)break;next=head->next;}while(!
CAS(&lf->top,head,next))returnhead;}容易看出LockFree算法基于乐观假设,采用了commit-retry的模式.
当同步冲突出现的机会很少时,这种乐观假设能带来较大的性能提高.
do{备份旧数据搜狐公司研发中心版权所有,仅供技术交流,转载请保留上述文字基于旧数据构造新数据}while(!
CAS(内存地址,备份的旧数据,新数据))ABAProblem如果不涉及到内存回收,上一小节的程序已经相当完善(比如说在有GC的环境中).
一旦涉及到显式的内存管理,就会遇到经典的ABA问题.
1)lifo_push被抢先之前的链表2)抢先结束后的链表3)lifo_push的结果如上图所示.
如果执行lifo_pop的线程,在"head=lf->top;"后被其它线程的pop抢先,经过多次push/pop后返回到原线程时可能出现原有的链表头在释放后又被重新分配的情形.
也就是说lf->top的值从A变成B再变成A这一过程发生在"head=lf->top;"和CAS之间,这时lf->top->next已经不等于原来保存的next,CAS没有办法检测这种变化(这正是CAS比SC弱的地方).
LIIFOwithSequenceNumber为避免ABA问题,我们用一个顺序号lf->pop_count来保护pop操作,如果pop操作被其它的pop抢先,就retry一下.
此时对lf->top和lf->pop_count的修改应该在同一个原子操作中进行——CAS2的用武之地.
structcell{structcell*next;structvalue_tvalue;}structlifo{volatilestructcell*top;volatileintpop_count;}voidlifo_push(volatilelifo*lf,cell*cl){do{cl->next=lf->top;}while(!
CAS(&lf->top,cl->next,cl))}cell*lifo_pop(volatilelifo*lf){cell*head,*next;intoc;do{head=lf->top;oc=lf->pop_count;if(head==NULL)break;next=head->next;}while(!
CAS2(lf,head,oc,next,oc+1))returnhead;}封装好的ifo可以用来做memorypool的freelist,这样很容易就得到了一个lockfree的memorypool.
x8632bit下对CAS和CAS2的实现Windows下直接用InterlockedCompareAndExchange.
Linux下麻烦一点,这里给出linux下的实现.
搜狐公司研发中心版权所有,仅供技术交流,转载请保留上述文字uint32_tCAS(uint32_t*ptr,uint32_told,uint32_tnew){boolret;__asm____volatile__("lockcmpxchgl%1,%2\n\tsete%%al":"=a"(ret):"r"(new),"m"(*ptr),"0"(old):"memory");returnret;}boolCAS2(volatilevoid*ptr,uint32_told1,uint32_told2,uint32_tnew1,uint32_tnew2){boolret;__asm____volatile__("lockcmpxchg8b(%1)\n\tsete%%al":"=a"(ret):"D"(ptr),"a"(old1),"d"(old2),"b"(new1),"c"(new2):"memory");returnret;}进阶阅读zLock-FreeTechniquesforConcurrentAccesstoSharedObjectshttp://www.
grame.
fr/pub/fober-JIM2002.
pdfzHazardpointers:safememoryreclamationforlock-freeobjectshttp://researchweb.
watson.
ibm.
com/people/m/michael/ieeetpds-2004.
pdfz一个Write-Rarely-Read-ManyMaphttp://blog.
csdn.
net/chinajxw/archive/2006/03/08/618850.
aspx这一篇文章的Update函数只能单线程使用,否则可能访问一个悬空指针.
需要在Update中也使用Hazard才可以并行Update.
当然Write-Rarely一般是不会并行Update的.
zSUN的Lock-FreeReferenceCountinghttp://research.
sun.
com/people/moir/Papers/SPAA04.
pdfzLock-FreeLinkedListsUsingCompare-and-Swaphttp://citeseer.
ist.
psu.
edu/cache/papers/cs/1067/ftp:zSzzSzftp.
cs.
rpi.
eduzSzpubzSzvaloisjzSzpodc95.
pdf/valois95lockfree.
pdfztransactionalmemory简介http://www.
newsmth.
net/att.
phpp.
272.
21110.
693.
pdfzGCC-Inline-Assembly-HOWTOhttp://www.
ibiblio.
org/gferg/ldp/GCC-Inline-Assembly-HOWTO.
htmlzIntel64andIA-32ArchitecturesSoftwareDeveloper'sManualshttp://www.
intel.
com/products/processor/manuals/index.
htm