[译]软硬件协同之单写原则

前言

以前我常常喜欢用并发的手段去解决问题，直到最近看见一篇文章介绍单线程写的一些思想，觉得很有启发，很值得借鉴，遂把它翻译了一下，并做个分享，有兴趣的同学可以看原文。
原文地址：Hardware and software working together in harmony
以下为正文。
当试图构建一个高扩展性的系统时，影响其扩展性的最大限制往往是多线程对数据或资源的竞争，当然，也可能是因为很烂的算法。但假设我们选用的算法复杂度(O(x))还不错，此时来分析系统设计的扩展性限制因素。
我观察过很多人使用多线程写程序已是习以为常，计算机科学中有许多研究来管理并发，但归结起来就两种基本方案：其一是对访问资源作互斥控制，其二是采取乐观策略（如果数据未变更的话，则用新数据做替换）。

互斥

互斥意味着在同一时刻只有一个线程能访问受保护的资源，一般用锁策略来实现。 锁策略需要一个仲裁者，当线程在竞争资源时，通常是操作系统内核介入，并决定由哪个线程访问资源。这可能代价比较大，因为需要很多个CPU时钟周期，往往花费的时间比处理实际的业务逻辑还长。而竞争失败的线程需要进入队列等待，而入队则会造成延迟，同时执行变得不可预期，导致最后限制了系统的吞吐量。

乐观并发控制

乐观策略涉及到修改副本操作，在同一时刻，如果数据修改失败，则需要不断重复处理，直到修改成功。重复的过程引入了竞争，这与互斥里的入队有类似的副作用。这种算法在源代码管理系统(svn,cvs)中屡见不鲜。乐观策略很适合处理数据，但是对硬件类资源却不适用，因为你不能获取硬件的副本。很多处理器提供了CAS指令来自动的执行这种操作。
实际上，大多数锁策略都用乐观策略来更新锁状态，或互斥操作原语(mutual exclusion primitive).

管理竞争 vs 做实事

大家都知道，CPU在每个周期可以执行多条指令。现代Intel CPU的每片核有6个执行单元，可以并行处理算法联合，分支逻辑，字处理，内存读取与写入。如果CPU在执行时，出现缓存缺失，则需回主存加载数据，此过程又会花费几百个周期。为了尽力提高效率，CPU会以预读的方式加载更多内存数据，并缓存起来。如果CPU每秒都出现缓存穿透，那么CPU不再预读而是直接读内存数据。因为CPU在单位周期内缓存失效两次的话，则不能保持预读的状态。 因此管理缓存失效是当代CPU最大的限制因素。
那么，我们该怎么管理线程间的竞争呢。如果有两个或多个线程是采用锁来做互斥，设计上线程最好能命中CPU的三级缓存，或都基于底层互联的Socket, 并通过CAS操作来更新锁状态。CAS指令在未发生竞争的场景中会执行10个周期左右，同时由于乱序执行的原因，CPU需要暂停下来去回写内存。最坏的情况下，多个线程发生冲突时，内核会参与并让多余线程进入休眠状态，直到锁释放时才唤醒他们。这种对阻塞线程的重调度导致缓存污染，最糟糕的是线程被调度到另一个cpu片上去执行，结果会造成大量的缓存缺失。
在频繁竞争的场景中，很多系统会花费很多的时间来管理竞争，而真正用于执行业务逻辑的时间反而变少了。 下表给出了程序状态在较稳定时，不回主存而是基于L2/L3缓存加载数据的场景中，管理竞争的时间消耗。

上表记录了在2.4GHz Westmere的处理器上用不同的技术方案对64位的计数器做5亿次自增计算的统计数据。 可能有人说：“这只是个实验，真实世界的程序没有这么多竞争”。
相信我，真实世界的程序会有更多的竞态条件，而即使所有的状态都在CPU缓存中，但当CPU上下文切换时，你觉得会发生什么？？ 通过记录竞争的时间消耗，我们可以推断系统的扩展性限制因素。

单写设计

那凭借已有的数据和资源，怎么设计一个只有单线程写的系统？实际上在我看来还是蛮容易的。多线程读数据是没问题的，CPU遵循缓存一致性原则，会在不同的CPU执行片间做同步，这虽然有消耗，但影响略小。
如果你的系统遵从单写原则，那么每个执行上下文会完整的执行业务逻辑，而不会被资源竞争而打断。因此在硬件资源消耗饱和前，你都可以无限制的扩展你的系统。在x86/x64的CPU架构上有个优势，在硬件层有个内存模型，基于它的内存读取和写入操作可以维持顺序，因此如果你采用单写原则，则不再需要内存屏障。x86/x64的架构通过内存屏障来保证多线程在跨cpu片写相同的数据。而单写原则避免了这个问题，因为不用再在CPU片的高速缓存中同步数据。
那么该怎么设计单写？首先，我觉得这是一件自然的事情。人类或其他自然界自主的生物都有应对这个世界的模式，我们大脑里有着世界的处理模型，通过我们的感官和触觉（输入）来反馈给大脑的模型，然后大脑采取对应的行为作为输出。没有人能直接跑到别人的大脑里搅乱别人的神经系统。起初，面向对象(OO)的设计都是关于消息传递的，但是慢慢却演变成了在方法调用中可以直接修改对象的属性，这是谁想出来的，谁允许对象的公有方法可以修改特有属性的？ 这下你该自食其果了吧。（译者注:指的是上文提到的并发控制对系统带来的限制）
在大学里我研究了晶片机和一门有趣的编程语言: Occam，我认为它引入了一种很优雅的设计 — 让所有的参与者通过消息传递来协作，而不是去改变共享状态。我很确定这应该是Disruptor的灵感来源。我的Disruptor使用经验说明了用这种设计构建的系统比基于锁或竞态条件的系统，其吞吐量要高好几个数量级，同时还大大的降低了延迟。
有趣的是，现在出现了许多引入单写原则的技术方案，如Node.js, Erlang, Actor Patterns, SEDA等等，遗憾的是大多数的底层实现都用的是队列，而队列又破坏了单写原则。
然而，Disruptor分离了关注点，因此在内部很多场景中都应用了单写原则。
现在，我不会说锁和乐观策略就是不好的，就不应该采用。他们对于很多问题仍然是极好的方案，如引导并发系统启动，或在配置或引用数据中生成核心状态。然而如果核心事物行为是处理竞态数据，此时若采用了锁或乐观策略来控制，那么其扩展性在根本上会受到限制。

原则应用（The Principle at Scale）

单写原则适用很多不同场景， Mandelbrot同志 也很认同这一点。CPU仅仅是执行节点，而缓存系统则提供了消息通信机制。同样有在类似的模式，如服务器是处理节点，而通信系统则是局域网络。如果一个SOA的服务只能写入数据，那么可应用此原则来提高处理性能，假设底层数据是直接存入数据库，其他服务可以直接读取，但是不用发送消息来告知原系统，则可由数据库来管理数据的并发访问。这种方式可以防止服务因读取缓存数据出给客户端，导致数据不一致，同时也限制了数据的共享方式。

总结

如果一个系统被分解成多个组件，每个组件都保留有相应的状态模型，系统没有中心共享模型，而且所有的通信是通过消息传递来完成，那么这个系统自然就不用管理竞争，如果系统的消息传递方案不是基于队列的话，那么这类系统则遵从了单写原则。如果你不能直接应用这种模式，那么找出因竞争而对系统产生限制的地方，然后开始问自己一个问题：我该怎样修改代码才能运用单写原则，这样就可以资源竞争。
最后，CPU在每个执行周期需要的数据来源，最好都通过单写原则来写入。
（原文完）