无堵塞的并发编程

顺序编程非常普及,可以说是大多数程序员编程范式,只不过可能他们没有意识到,如今已经进入并发编程时代,顺序编程和并发编程是两种完全不同的编程思路,堵塞Block是顺序编程的家常便饭,常常隐含在顺序过程式编程中难以发现,最后,成为杀死系统的罪魁祸首;但是在并发编程中,堵塞却成为一个目标非常暴露的敌人,堵塞成为并发不可调和绝对一号公敌。

因为无堵塞所以快,这已经成为并发的一个基本特征。

过去我们都习惯了在一个线程下的顺序编程,比如,我们写一个Jsp(PHP或ASP)实际都是在一个线程
下运行,以google的adsense.Jsp为例子:


<%
//1.获得当前时间
long googleDt = System.currentTimeMillis();
//2.创建一个字符串变量
StringBuilder googleAdUrlStr = new StringBuilder(PAGEAD);
//3.将当前时间加入到字符串中
googleAdUrlStr.append(
"&dt=").append(googleDt);
//4.以字符串形成一个URL
URL googleAdUrl = new URL(googleAdUrlStr.toString());
%>

以上JSP中4步语句实际是在靠一个线程依次顺序执行的,如果这四步中有一步执行得比较慢,也就是我们所称的是堵塞,那么无疑会影响四步的最后执行时间,这就象乌龟和兔子过独木桥,整体效能将被跑得慢的乌龟降低了。
过去由于是一个CPU处理指令,使得顺序编程成为一种被迫的自然方式,以至于我们已经习惯了顺序运行的思维;但是如今是双核或多核时代,我们为什么不能让两个CPU或多个CPU同时做事呢?

如果两个CPU同时运行上面代码会有什么结果?首先,我们要考虑两个CPU是否能够同时运行这段逻辑呢?
首先,上面代码中第二步是不依赖第一步的,因此,第一步和第二步可以交给两个CPU同时去执行,然后在第三步这里堵塞等待,将前面两步运行的结果在此组装。很显然,由于第三步的堵塞等待,使得两个CPU并行计算汇聚到这一步又变成了瓶颈,从而并不能充分完全发挥两个CPU并行计算的性能。

我们把这段JSP的第三步代码堵塞等待看成是因为业务功能必须要求的顺序编程,无论前面你们如何分开跑得快,到这里就必须合拢一个个过独木桥了。

但是,在实际技术架构中,我们经常也会因为非业务原因设置人为设置各种堵塞等待,这样的堵塞就成为并行的敌人了,比如我们经常有(特别是Socket读取)
While(true){
……
}
这样的死循环,无疑这种无限循环是一种堵塞,非常耗费CPU,它也无疑成为并行的敌人。比如JDK中java.concurrent.BlockingQueue LinkedBlockingQueue,都是一种堵塞式的所谓并行包,这些并行功能必须有堵塞存在的前提下才能完成并行运行,很显然是一种伪并行。

由于各种技术上的堵塞存在,包括多线程中锁机制,也是一种堵塞,因为锁机制在某个时刻只允许一个线程进行修改操作,所以,并发框架Disruptor可以自豪地说:无锁,所以很快。

现在非常流行事件编程模型,如Event Sourcing或Domain Events或Actor等等,事件编程实际是一种无堵塞的并行编程,因为事件这个词语本身有业务模型上概念,也有技术平台上的一个规范,谈到事件,领域专家明白如同电话铃事件发生就要接,程序员也能明白只要有事件,CPU就要立即处理(特别是紧急事件),而且事件发生在业务上可能是随机的,因此事件之间难以形成互相依赖,这就不会强迫技术上发生前面Jsp页面的第三步堵塞等待。

因此,在事件模型下,缺省编程思维习惯是并发并行的,如果说过去我们缺省的是进行一个线程内的顺序编程,那么现在我们是多线程无锁无堵塞的并发编程,这种习惯的改变本身也是一种思维方式的改变。

在缺省大多数是并发编程的情况下,我们能将业务上需要的顺序执行作为一种特例认真小心对待,不要让其象癌细胞一样扩散。我们发现这种业务上的顺序通常表现为一种高一致性追求,更严格的一种事务性,每一步依赖上一步,下一步失败,必须将上一步回滚,这种方式是多核CPU克星,也是分布式并行计算的死穴。值得庆幸的是这种高一致性的顺序编程在大部分系统中只占据很小一部分,下图是电子商务EBay将他们的高一致性局限在小部分示意图:

由此可见,过去我们实现的顺序编程,实际上是我们把一种很小众的编程方式进行大规模推广,甚至作为缺省的编程模式,结果导致CPU闲置,吞吐量上不去同时,CPU负载也上不去,CPU出工不出力,如同过去计划经济时代的人员生产效率。

所以,综上所述,以事件编程为范式的无堵塞并发是一种趋势,下面关键问题是哪种事件编程范式更简单,更易于被程序员理解掌握了。

相关话题:
为什么要用Event Sourcing?


2011年10月06日 17:25 "@banq"的内容
,综上所述,以事件编程为范式的无堵塞并发是一种趋势,下面关键问题是哪种事件编程范式更简单,更易于被程序员理解掌握了。 ...

我在JdonFramework 6.5中做了如下探索:
分别使用领域事件Domain Events和DCI的场景对无堵塞并发进行不同级别的抽象封装。

无堵塞并发机制是使用经过实战考验的Disruptor框架,这个不多说,已经有很多帖子解释解释器原理。

在Disruptor上,我使用了领域事件Domain Events封装,因为事件是一个架构层次相对较高,容易理解使用的术语,特别是我们如果有了领域模型对象,通过它发出事件来驱动实现各种功能,也是非常自然易于理解的,这种功能运行是无堵塞并发的。

如果觉得事件层次还不是很高,那么使用DCI概念来实现,我们已经讨论了DCI和四色原型等软件分析方法可以顺利对接,由此可见DCI是一个几乎无技术概念,纯粹业务领域概念的高层次抽象,我用DCI封装了Domain Events,而Domain Events的底层机制是使用Disruptor,经过这样三层封装,无堵塞并发编程应该达到易于使用的目的。

如下图:当没有领域模型对象时,比如在它没有诞生之前,我们创建它时,这时是无法使用它发出领域事件的,因为它还不存在,那么我们以DCI的场景Context为主要操作场所;

当领域模型对象已经存在了,那么就应该以它为核心,它就是司令部,它可以自行运转发出各种领域事件,驱动外界为之服务,包括其自身数值的修改后持久化保存等等。

通过以上这种拟人化的的使用模式,基本上应该能够帮助普通程序员在不自觉的情况下直接使用无堵塞并发编程,从而实现并发编程能够被广泛易于使用的一个目的。

Jdon Framework 6.5beta发布

这里有一篇以机器人为案例,使用DDD/DCI/Domain Events三种不同方式,实现从软件分析设计到代码实现的全过程,包括最终源代码:http://www.jdon.com/jdonframework/dci.html
[该贴被banq于2011-10-07 16:30修改过]


Java 的阻塞(Objectwait和Conditionawait)是基于条件等待,IO阻塞也是等待IO事件。我的理解事件是由一种有状态的命令对象(Source)伴随产生的。之所以要用Lock是因为Java内存模型决定的,既解决Java Heap对象的共享问题。

我粗刚看了一下相关的文章,感觉是通过事件模型来避免程序员自行管理Java并发,而是通过框架来管理线程并发,那么问题来了,多个相同的事件响应,怎么管理共享对象?

2011年10月07日 17:47 "@mercyblitz"的内容
多个相同的事件响应,怎么管理共享对象 ...

这个问题很好,我也希望多考虑一下来完善这种方式,由于事件都是模型对象发出的,这里共享对象可能是共享模型对象。

模型发出事件,可以把自己作为参数传入事件响应器中处理,如果同时有多个事件,那么就需要一种事件的前后顺序次序,这样保证某个时刻只有一个事件操作这个共享的对象,这实际上是事件的顺序化,模拟顺序编程。

不知你说的是不是这个意思,如果是,我可以详细谈一下如何通过事件的顺序化来实现业务逻辑要求的顺序,也就是管理共享对象。


2011年10月07日 19:16 "@banq"的内容
模型发出事件,可以把自己作为参数传入事件响应器中处理,如果同时有多个事件,那么就需要一种事件的前后顺序次序,这样保证某个时刻只有一个事件操作这个共享的对象,这实际上是事件的顺序化,模拟顺序编程。 ...

按照通常的理解的话,一个命令(事件)由一个线程处理,那么,最终处理的是单个线程,一般而言,比如Web交互不要求命令对象传递的顺序性。

我感到困惑的是,对于Java 内存模型(JMM)是JVM实现的一部分,按照原子操作比如AtomicX类和volatile的MB(Memory Fence)操作只能这对某个变量(或者成为内存区域)。但是如何通过匪Native方法来避免锁(其实锁区域是临界区域,对于执行代码而言是顺序相关的)来执行一段上下文操作。

2011年10月07日 21:50 "@mercyblitz"的内容
我感到困惑的是,对于Java 内存模型(JMM)是JVM实现的一部分,按照原子操作比如AtomicX类和volatile的MB(Memory Fence)操作只能这对某个变量(或者成为内存区域)。但是如何通过匪Native方法来避免锁(其实 ...

避免锁或同步锁有多种方式,volatile是一种方式,主要的不变性设计,比如设计成DDD的值对象那种,要变就整个更换,就不存在对值对象内部共享操作;还有克隆原型,比如模型对象克隆自己分别传给并发的多个事件处理;用Visibility 使资料对所有线程可见等等;

最彻底的方式就是使用无锁Queue队列的事件或消息模型,Disruptor采取的是一个类似左轮手枪圆环RingBuffer设计,见http://www.jdon.com/jivejdon/thread/42466,这样既能在两个线程之间共享状态,又实现了无锁,比较巧妙,业界引起震动。

当然Scala的那种Share nothing的Actor模型也是一种无锁并发模型,不过奇怪的是,发明Disruptor的LMAX团队首先使用过Actor模型,但是并发测试发现还是有性能瓶颈的,所以,他们才搞了一个Disruptor。

我在JdonFramework中将Disruptor用Domain Events封装起来,领域模型发出事件,事件由Disruptor的RingBuffer传递给另外一个线程;实现两个线程之间数据传递和共享;当事件消费者线程处理完毕,将结果放入另外一个RingBuffer,供原始线程读取或堵塞读取,是否堵塞取决于是否需要顺序了。

整个一个非堵塞的使用模式如下:

发出调用以后不必立即使用结果,直至以后需要时才使用它。
发出调用后不要堵塞在原地等待处理结果,而是去做其他事情,直至你需要使用这个处理结果时才去获取结果。
被调用者将会返回一个“future”句柄,调用者能够获得这个句柄后做其他事情,其他事情处理完毕再从这个句柄中获得被调用者的处理结果。

据统计,在一个堵塞或有锁的系统中, 等待线程将会闲置,这会消耗很多系统资源。消耗资源的公式如下:
闲置的线程数 =(arrival_rate * processing_time)
如果arrival_rate(访问量达)很高,闲置线程数将会很大。堵塞系统是在一个没有效率的方式下运行,无法通过提高CPU负载获得高吞吐量。

[该贴被banq于2011-10-08 08:11修改过]

关于lmax的事件持久和回放,lmax似乎没把这个说清楚。
他们的事件记录是什么样的是例子1那样的还是例子2那样的。
例子1:
统一一个记录文件【
快照1 12:00 user order item
loginEvent
buyEvent
logoutEvent

例子2:
文件1【
快照1 12:00 user
loginEvent

文件2【
快照1 12:30 user
logoutEvent

文件3【
快照1 12:20 order user
buyEvent

经过思考例1在做回放时,能够简单的保证同一时刻所有模型的一致,而例2要达到这点需要考虑很多复杂因素,例如不同场景共享相同的domain model,回放后如何merge他们这是个问题,又或者是我在这块上理解是否有误区,请大家帮忙指点一二。

2011年10月08日 10:34 "@gamex"的内容
经过思考例1在做回放时,能够简单的保证同一时刻所有模型的一致 ...

我认为也是第一个,因为文件系统只有append操作是最快的,这也是apache日志文件至今一直在使用的原因。

在顺序和并行的关系上,著名的Amdahl定律很有权威,阿姆达尔定律认为,因为顺序计算的存在,所以它将限制并行化的潜在好处。

也就是说顺序执行代码在系统中所占的比例决定了使用并行手段所能改进性能的潜力,如果我们将顺序编程全部局限到业务逻辑上的顺序,那么留给我们实现并行计算的可能性就很大。

再换一句话说:如果我们采取一种主动积极的缺省的并发甚至并行编程习惯,那么无疑我们的精力将集中到缩小顺序编程的范围上,就像我们缺省使用模式,Hold住不变的,这样就有精力对付每个案例中特殊或变化部分。这也是老子反者道之动原理。

阿姆达尔的亮点是在锁争夺上。

如何面对锁的挑战是并发编程最大的难题,JDK提出避免锁的最后一个策略是使用读写锁,但是即使比较快的读写锁,也不可能扩展超过到50-100 CPU。

2008年5月Dr Cliff Click在javaOne上发表了无锁的Array:http://www.azulsystems.com/events/javaone_2008/2008_CodingNonBlock.pdf:

一个大而快速的数组来保存所有的数据,它允许快速并行的数据读取,并允许一个平行的,渐进的,并发拷贝。

针对这些数组元素使用Atomic-update原子级更新(using java.util.concurrent.Atomic.*). 如果处理器是Azul/Sparc/x86, or Load Linked/Store-conditional (LL/SC) on the IBM platform.
原子更新将采取Compare and Swap (CAS)。

原子更新将构建一个有限的状态机(FSM),在每个数组元素间复制,FSM 支持数组大小可变,一般用来控制写。

以此原则,Dr Cliff Click构建了一个无锁的Queue,是用Bit Vector 和 Hash Table实现,这和LMAX的Disruptor的RingBuffer异曲同工,开源代码在:http://sourceforge.net/projects/high-scale-lib/

这个开源并发包专门用来替代JDK5或JDK6的 java.util.* or java.util.concurrent.*包,所以,如果你的系统在性能并发测试时主要CPU集中在JDK并发锁上,那么用Dr Cliff Click来替代JDK并发锁,会有相当大的性能提升。

这个开源并发包的hash table实现支持兼容于ConcurrentHashMap并发插入 移除和大小变化等,在Azul硬件上能够线性扩展伸缩到768 CPUs ,能够获得每秒一亿次的读,每秒千万次的写。

资料来源于:JavaOne: Cliff Click on a Scalable Non-Blocking Coding Style

stackoverflow:What is the most efficient Java Collections library?



[该贴被banq于2011-10-09 14:38修改过]

刚看到马上去测试下 high-scale-lib

pentium(R) dual-core cpu T4400 2.20ghz 1.18ghz
2gb内存
HashMap vs NonBlockingHashMap
测试new 100个线程 同时put HashMap 处理耗时劣微胜出
测试new 1000个线程 同时put 基本不分上下
测试new 2000个线程 同时put HashMap也还好就是稍微阻塞了一会。NonBlockingHashMap处理正常
测试new 3000个线程 同时put HashMap后面基本上处理一段阻塞一段,等了很久没看反应我就把他给停掉了。NonBlockingHashMap处理正常
测试new 5000个线程 同时put NonBlockingHashMap还是处理正常。
总结:线程越少的话用HashMap在处理速度上会比NonBlockingHashMap稍微耗时少点。但是如果处理线程一多的话他就抗不住了阻塞是hashmap的弊端,所以还是大家自己权衡利弊去用吧。

2011年10月09日 17:00 "@gamex"的内容
线程越少的话用HashMap在处理速度上会比NonBlockingHashMap稍微耗时少点。但是如果处理线程一多的话他就抗不住了阻塞是hashmap的弊端,所以还是大家自己权衡利弊去用吧 ...

好样的,最好和ConcurrentHashMap也比较一下,NonBlockingHashMap比ConcurrentHashMap更适合大量频繁写操作;CPU扩展性强,但不知在普通双核CPU下,两者是否有差别。

对上次实验的进一步改进
hashmap vs ConcurrentHashMap vs NonBlockingHashMap
100个线程 每个put 1000次 测试结果
hashmap首先被淘汰严重卡死,ConcurrentHashMap似乎劣胜NonBlockingHashMap

100个线程 每个put 5000次 测试结果
ConcurrentHashMap处理正常不会卡住,NonBlockingHashMap开始出现处理一段卡一段的现象。


5000个线程 每个put 5次 测试结果
ConcurrentHashMap总体耗时时间有时候会比NonBlockingHashMap少一点但基本上差不了多少。

总结:ConcurrentHashMap会比NonBlockingHashMap 性能好点

这就搞不懂了NonBlockingHashMap反而会比ConcurrentHashMap性能差?真是大跌眼镜。

2011年10月10日 09:53 "@gamex"的内容
这就搞不懂了NonBlockingHashMap反而会比ConcurrentHashMap性能差?真是大跌眼镜 ...

有可能,2008年时的ConcurrentHashMap不一定比NonBlockingHashMap性能好,三年过去了,JDK也在升级。

其次,NonBlockingHashMap主要体现在写操作上,也就是put操作,你可以把写和读操作提高到2:1水平,估计这方面性能要强些。

另外也可能在CPU个数少的情况两者差不多,但是CPU个数多了就不一样,这个就难以测试了,NonBlockingHashMap可以最多支持700多个CPU,就只能想象一下了。

你好banq:
我看到了你详讲的“无堵塞的并发编程”。我不明白一个问题,事件编程是随处,随机发生的,我有点不明白事件编程的说法。
<%
//1.获得当前时间
long googleDt = System.currentTimeMillis();
//2.创建一个字符串变量
StringBuilder googleAdUrlStr = new StringBuilder(PAGEAD);
//3.将当前时间加入到字符串中
googleAdUrlStr.append("&dt=").append(googleDt);
//4.以字符串形成一个URL
URL googleAdUrl = new URL(googleAdUrlStr.toString());
%>
比如上面的这个例子,是的,按顺序进行编程,当第三步在运行,就开始堵塞在这里了,这样确实是顺序编程的很大的一个毛病,
事件编程:当你点击软件界面操作的时候,事件发生了,就像上面的例子,是把上面这几行代码看成几个事件来进行事件编程,还是把上面的这一个请求看成一个事件来进行编程了,我看了“事件编程”我的认为是,应该的把上面这个几行代码看成一个事件来进行编码吧,这样事件编程才没有依赖,如果上面的代码是几个事件,那事件编程也会产生依赖了,不知道认为对不?

2012年02月06日 15:35 "@javawebkaifa"的内容
应该的把上面这个几行代码看成一个事件来进行编码吧,这样事件编程才没有依赖,如果上面的代码是几个事件,那事件编程也会产生依赖了 ...

当成一个事件就没有讨论意义了,至少第一步获得时间事件和第二步创建事件是两个可并行的事件,两者也不互相依赖。事件编程原则是能够去除依赖,能够独立跑起来的就单独跑起来。在非堵塞不可的地方再堵塞等待,而且有时会通过异步来实现堵塞。