云计算 反思课 2 并发编程的策略与思考

学习是一个不断改进方法论的过程,第 15 课 分区和复制中,因为自己缺乏对并发编程的基本认识,走了很多弯路。吃一堑长一智,本文着重讲三点:一是为什么我会犯错,二是对并发编程的一些思考,三是结合 Java 语言来探索相关细节。(感谢节瓜 @jiexing 的耐心指导)


应用场景

因为涉及到具体的问题,所以先大概说明一下应用场景,方便之后的叙述。事情大概是这样的:

  • 后端有三台数据库服务器
  • 需要支持两种不同的存储策略(复制机制与分区机制,详情参考这里
  • 由前端来接收和处理请求(不使用任何缓存)
  • 请求有两种:GET(从数据库读取数据)与 PUT(向数据库写入数据)
  • 数据的格式是键值对
  • 保证数据的强一致性
  • 按照请求的顺序返回响应(按照时间戳来排序)

难点在于,每来一个请求,服务器都会新开一个线程来进行处理,多个线程的访问需要保证数据一致性及顺序,如果没有真正理解场景本身,很容易陷入无谓的复杂度,写出冗长却不完备的代码。

我错了

写代码之前,我花了很多时间,试图找到一个合理的满足一致性和顺序的机制。根据文档的提示,用锁来保证一致性,用优先队列来保证顺序,万万没想到这就是一切复杂度的开端,最后我折腾出来的机制大概是这样的:

  • 每个 key 有自己的锁和优先队列
  • 每来一个请求,把它加入到对应 key 的优先队列中
  • 然后开一个线程,取出优先队列的队头进行处理
  • 具体线程之间的同步由锁完成(在停止尝试之前已经变得很复杂,这里不详细展开,总的来说我试图利用三个状态手动控制线程的执行)
  • 因为不同的线程可能需要访问同一个数据结构(这里我用 HashMap 来存储),也要考虑线程同步的问题,于是我决定依赖于『线程安全』的数据结构自动处理好访问冲突

看起来还行,但是实际测试的时候既不能保证强一致性也没办法按顺序,甚至还引入了新的问题,这是为什么呢?我总结的原因如下:

  • 每次接收请求,新开的线程不一定执行这个请求对应的内容,而是执行队列头,让新线程做太复杂的工作
  • 为了保证逻辑一致性被迫设计状态判断的机制,但是没办法穷举出所有的可能
  • 控制线程时利用自动数据结构+手动逻辑控制,并没有得到半自动冲锋枪突突突的效果,而是乱成了一锅粥

后来在瓜瓜的指引下找到了简单且有效的方法,关键点在于:

  • 要自动就全自动,要手动就全手动,不要依赖于自己并不完全理解的容器或者数据结构,因为很可能会和自己预期的表现不一样
  • 每个线程应该就处理好传入的请求,而不是可能执行另外的请求(我之前的机制这种情况是可能出现的)
  • 不要想当然去『控制』线程以达到最优性能,很多串行编程的思维在这里并不适用。

从这样的思路拓展开去,就可以意识到自己之前的思路有多么『想当然』了。

一些思考

Intuition is frequently wrong - be data intensive. [《Real-World Concurrency》 from ACM-Queue]

如果要给云计算这门课一个关键词,当属 tradeoff。所谓权衡的艺术,从不同的角度来看,有不同的表现:

  • 从实现的角度,尽量以最小的代码换取最大的性能
  • 从架构的角度,尽量以简洁的架构满足需求,减少复杂性
  • 从经济的角度,尽力以最小的花费提供最好的服务质量

同样的,对于并发编程,也是如此。

Multi-threading is easy. Correct synchronization is hard

最难的当属思维的转换,很多比较复杂的算法(或者说依赖比较多的算法),在并行环境中往往表现不好,比如说动态规划问题,原本是重复利用子问题的解,但是在多线程的条件下,子问题都不知道飞哪里去了;反而是分治算法,因为子问题独立,反而更适合并行。

而提到并发编程,就不得不提 OpenMP 了,这个学期当助教,我主要负责这一部分的内容,所以也算是有一些理解。OpenMP 的思路是利用尽可能少的代价,把串行代码弄成并行的,核心的机制是共享内存,然后利用线程执行不同的子问题,可能只需要几条 OpenMP 预编译指令,就可以带来明显的性能提升效果。

但是仔细想想,这种改进真的很大吗?在串行代码开发中,程序控制有一个清晰的流程。我们知道数据被访问和更改的方式,并了解其中的依赖关系。究其根本,OpenMP 依赖数据资源的锁定,和串行编程的思路是一样的,只是利用多核进行了简单的并行处理(相当于多叫几个人完成同一个工作,而不是大家做不同的工作)。如果使用不慎,除了带来性能问题之外,还可能造成数据不一致的问题。

而真正的并行程序中,有多个状态会同时发生和改变,依赖关系也会发生变化。必须思考如何同时执行多个指令,以及这些指令会对你的数据结构、变量、算法及其它一切产生什么影响。

总结一下:

  • 单线程逻辑设计的思路
    • 所有数据结构的生存期,以及对这些数据结构的访问都在同一个线程,不存在竞争条件,耗时的操作都给其他线程(IO线程、定时器线程,数据库线程等)做,做完之后向事件队列(多线程安全的队列,其他线程是生产者,逻辑线程是消费者)发送事件
  • 多线程逻辑设计的思路
    • 所有数据结构的生存期,以及对这些数据结构的访问不一定在同一个线程。需要考虑数据结构的竞争条件。网络事件、定时器事件唤醒工作线程(比方说 notifyAll)执行所有工作,一般不需要交换到其他线程

我们可以看出,最关键的就是如何访问数据的问题!线程执行和访问数据的时间没有确定的顺序。操作系统负责对线程进行调度,而它对于数据访问模式一无所知。并行程序中唯一的顺序是我们利用同步方法明确创建的(前面我把这部分工作交给自己并不熟悉的并行库来做,导致出问题)。最重要的是要牢牢记住所有并发线程,这样才能够创建更简单更有约束性的结构来限制并发情况。还有一个需要记得的点是,可能最优化的串行算法并不是好的并行算法。

最后的最后,并发编程真的是一门『纸上得来终觉浅』的艺术,最佳途径就是实践,实践,再实践。

一些对策

这里结合了 CMU 18645 How to Write Fast Code 课程上的一些思路,虽然对于具体场景不算特别适用,不过总体原则放到哪里都能用。

先说说优化并行部分的三个层面:

  • 逻辑层面:减少数据共享
    • 这一部分需要注意 false sharing 的问题,不然反而会造成大量的缓存浪费
    • 解决方法也不算太难:线程本地存储 + 内存对齐,不过需要根据不同的机器不同处理
  • 编码层面:减少锁粒度
    • 同一个模块中,对不总是同时访问的数据,使用不同的锁(固定加锁顺序,防止死锁)
    • 使用锁(临界区)来保护数据,而不是操作
    • 将可能耗时的操作移到临界区外面(特别是 IO)
    • 避免在临界区中调用未知代码
    • 谨慎使用读写锁,实现复杂,效率低下
  • 工具层面:使用轻量同步机制
    • 有些需要深入到内核态进行同步,对于基本的操作来说其实没必要这么兴师动众

换一个视角,可以总结出如下四条原则:

  1. 单一职责:分离并发相关代码和其他代码(并发相关代码有自己的开发、修改和调优生命周期)
  2. 限制数据作用域:两个线程修改共享对象的同一字段时可能会相互干扰,导致不可预期的行为,解决方案之一是构造临界区,但是必须限制临界区的数量
  3. 使用数据副本:数据副本是避免共享数据的好方法,复制出来的对象只是以只读的方式对待
  4. 线程应尽可能独立:让线程存在于自己的世界中,不与其他线程共享数据。Servlet 就是以单实例多线程的方式工作,和每个请求相关的数据都是通过 Servlet 子类的 service 方法(或者是 doGet 或 doPost 方法)的参数传入的。只要 Servlet 中的代码只使用局部变量,Servlet 就不会导致同步问题

在搜索资料的时候发现一个不错的提纲,不过因为刚接触,很多概念理解得不算特别清楚这里列出来,作为一个索引,感兴趣的同学可以按图索骥去深入了解下(参考资料中第二项):

  • 资源并发访问的策略
    • 悲观策略
      • lock based concurrency(theory)
      • java.util.concurrent (framework)
      • 锁还是不锁,这是个问题, 锁多还是锁少,也是个问题(practice)
    • 乐观策略
      • lock free concurrency(theory) : CAS
      • disruptor (framework)
      • 并发度高,还是并发度低的时候使用,这是个问题(practice)
  • 我拆我拆我拆拆拆(逻辑上拆分任务)
    • task-based concurrency (theory)
      • Runnable | Callable(model)
      • Executor | ExecutorService(framework)
    • data-based concurrency(theory)
      • Actor (model)
      • Akka(framework)
  • 从单机到分布式
    • divide and conquer
      • map reduce pattern
      • master-worker pattern
    • swarm framework(move computation instead of data)
  • 从软件到硬件
    • GPU
      • CUDA, jcuda, scuda
      • floating point computation, e.g. image reader and processing
    • PPU
      • 物理计算

看了这么多,唯一的感受就是

路漫漫其修远兮,吾将上下而求索。

参考资料

捧个钱场?