七周七并发模型

前言

这本书其实是 15 年看的了,有些知识过于陈旧。这边基于以前的读书笔记把最精炼的内容重新按照现在的理解总结下

并行和并发概述

首先了解并行和并发的区别以及如下的几种并行架构:

  • 位级(bit level)并行:同时处理的位数。例如一般来说 32 位的比 8 位计算机快,因为其同时可以处理 32 位。
  • 指令级(instruction-level)并行:这方面 CPU 会采用诸如流水线、乱序执行和猜测执行等技术。
  • 数据级(data)并行:数据级并行也称为“单指令多数据”(SIMD)架构。可以并行地在大量数据上施加同一操作。不过值得注意的是,这病不适合解决所有问题,只在适合的场景应用。例如图像处理场景比较适合数据级并行,比如增加图片亮度就要增加每一个像素的亮度。GPU 就是因为图像处理演化的强大的数据并行处理器。
  • 任务级(task-level)并行:普遍程序员认为的并行形式正是这种。多处理器系统最明显的分类特征是内存模型,可以分为共享内存模型分布式内存模型。据图如下图所示

本书介绍 7 种并发模型,不仅仅是语言层面的,这些并行模型的定义更加广义,从编程语言、软硬件、架构各个角度都有一些并发模型定义,我们在学习的时候也要打开思路

  • 线程与锁:虽然有很多不足,仍然是其他模型的基础,也是很多并发软件开发的首选。
  • 函数式编程:函数式编程消除了可变状态,所以从根本上是线程安全的,而且易于并发执行。
  • Clojure 之道:分离标识与状态:指令式编程和函数式编程混搭,在两种编程方式间取得微妙的平衡来发挥两者的优势。
  • actor:actor 模型是一种适用性很广的并发编程模型,适用于共享内存模型和分布式内存模型,也适合解决地理分布型问题,能提供强大的容错性。
  • 通信顺序进程(Communicating Sequential Processes,CSP):表面上看,CSP 模型与 actor 模型很相似,两者都基于消息传递。不过 CSP 模型侧重于传递信息的通道,而 actor 模型侧重于通道两端的实体,使用 CSP 模型的代码会带有明显不同的风格。
  • 数据级并行
  • Lambda 架构:该架构综合了 MapReduce 和流式处理的特点,是一种可以处理多种大数据问题的架构。

线程与锁

线程与锁模型优点是和硬件工作本质比较接近,在 java 中都是 1 比 1 对应的,缺点是对程序员的要求会比较高,容易产生有问题的代码。即使在 jdk 已经提供如此多的并发工具包的情况下,使用者仍然不得不考虑线程锁模型引出的一些列问题:

  • 内存可见性
  • 竞态条件
  • 互斥资源访问带来的一致性问题
  • 死锁

函数式编程

本质是把函数作为第一类公民,从语言层面不引入共享的可变状态。可变状态导致隐藏和逃逸,写代码是需要非常仔细地考虑类和方法的使用是否线程安全。纯函数式的编程语言,可以不定义变量,对函数进行组合即可完成计算目标。这样整个过程就完全不涉及变量的共享和线程通信。

函数式编程一般具备如下特性:

  • immutable data 不可变数据:像 Clojure 一样,默认上变量是不可变的,如果你要改变变量,你需要把变量 copy 出去修改。这样一来,可以让你的程序少很多 Bug。因为,程序中的状态不好维护,在并发的时候更不好维护。(你可以试想一下如果你的程序有个复杂的状态,当以后别人改你代码的时候,是很容易出 bug 的,在并行中这样的问题就更多了)
  • first class functions:这个技术可以让你的函数就像变量一样来使用。也就是说,你的函数可以像变量一样被创建,修改,并当成变量一样传递,返回或是在函数中嵌套函数。这个有点像 Javascript 的 Prototype(参看 Javascript 的面向对象编程)
  • 尾递归优化:我们知道递归的害处,那就是如果递归很深的话,stack 受不了,并会导致性能大幅度下降。所以,我们使用尾递归优化技术——每次递归时都会重用 stack,这样一来能够提升性能,当然,这需要语言或编译器的支持。Python 就不支持。

tips: 这里不要弄混响应式编程和函数式变成:参考函数式编程和反应式编程(reactive programming)有什么区别? 简单来说 FRP 是基于 FP 理念上的,是个超集。响应式编程使用三个核心概念:数据流,函数式编程和异步观察

分离标识与状态

本质是分离了实体标识和其变化的状态。下图 GOOG 是指的 google 股票实体,其价格是分离出来的,并且状态的变化是原子性操作。所有 ref 这个实体的调用都可以获取到最新的变化。这个并发模型的实现可以参考 clojure。通过将对内存的访问封装在事务(transactions)中,Clojure 消除了内存同步过程中我们易犯的那些错误(见《Programming Clojure》[Hal09]和《The Joy of Clojure》[FH11])。Clojure 会敏锐地观察和协调线程的所有活动。如果没有任何冲突——例如,每个线程都在存取不同账户——则整个过程中就不会涉及到任何锁,于是也就不会有延迟,并最终达到最大的并发度。当有两个线程试图访问相同数据时,事务管理器就会介入解决冲突,而我们的代码也就无需涉及任何显式加锁的操作。如果别的事务和当前事务冲突,则事务回滚重做,如果修改事务中不可变的值,则直接会报错 illegal state。这可以看成借鉴了数据库事务处理冲突的方式,在冲突时语言层面通过 TM 来处理冲突。

了解 colojure 中 SMT 的实现可以参考:软件事务内存导论(二)软件事务内存

思考:冲突特别多的场景,回滚代价如何平衡?答:应该提前探测冲突或者识别高冲突场景,然后直接降级串行化处理。

Actor 模型

基本概念

函数式编程不使用可变状态,也就避免了共享可变状态带来的问题。相比之下,使用 actor 模型保留了可变状态,只是不进行共享。

一个基本的 Actor 概念模型如下。各个 Actor 互相隔离,他们也各自维护自己的状态信息,这样是没有任何数据共享的,单个 actor 内 Event 串行处理,也就没有并发的一系列问题。如果需要 actor 之间通信,则通过队列获取不可变的消息。通过这种消息队列的模式,避免了由于通信带来的数据共享问题。

Smalltalk 的设计者、面向对象编程之父 Alan Kay 曾经这样描述面向对象的本质。

1
2
3
很久以前,我在描述”面向对象编程“时使用了对象这个概念。很抱歉这个概念让许多人误入歧途,他们将学习的中心放在了“对象”这个次要的方面。

真正主要的方面是“消息”。创建一个规模宏大且可生长的系统的关键在于其模块之间应该如何交流,而不在于其内部的属性和行为应该如何表现。

这段话概括了使用 actor 模型进行编程的精髓——我们可以认为 actor 模型是面向对象模型在并发编程领域的扩展。actor 模型精心设计了消息传输和封装的机制,强调了面向对象的精髓,可以说 actor 模型非常“面向对象”。

应用场景

Actor 模型应用产品:

  • erlang OTP
  • Elixir
  • Akka(Flink)

这里思考下 Flink 为什么在其中使用 Akka 通信,可以加深理解:

  • task 实例很多:线程模型比较重度,和系统线程 1:1,伸缩性比较差。基于用户态的轻量级 actor 可以大规模
  • 追求高并发的处理: 在 java 生态中撇开自带的线程模型,可用选择也只有 vert.x(Verticles)和 akka 了

简单总结:在 jvm 上关注高并发、多实例的可伸缩性时可以考虑 akka

缺点思考

  • 没解决死锁问题:该并发模型并没有对死锁提供解决方案,本质是消息的发送需要保序,否则 actor 之间可能由于互相等待导致死锁
  • 发送者、接受者、消息队列耦合度高:actor 之间的通信行为由收发者和消息队列共同构成,这个灵活性相比 CSP 就不太好,由于是面向 actor 的方式,发送者开始就必须确定是给哪个目标 actor 发送信息。下文介绍 CSP 和 Actor 区别的时候可以结合这点来理解。

通信顺序进程(Communicating Sequential Processes,CSP)

基本原理

CSP 模型看上去类似于 actor 模型,但是区别在于:actor 模型的重点在于参与交流的实体,而 CSP 模型的重点在于用于交流的通道 channel。

CSP 和 Actor 都遵循着如下的原则。通过通信来解决共享内存。

1
2
Do not communicate by sharing memory; instead, share memory by communicating.
不要以共享内存的方式来通信,相反,要通过通信来共享内存

Actor 和 CSP 区别

这里参考知乎回答請問 Actor 跟 CSP 之間是相輔相成,還是對立? 的例子来解读下:
一个保险销售团队,有 1 名经理和 5 名业务员。

  • Actor 经理:熟知每一个业务员所擅长的工作种类,直接向每个业务员发布具体的工作安排。
  • CSP 经理:把任务写成很多纸条,粘在黑板上,业务员有空闲就去取一个任务,然后去做。

本质区别在于:是否关心消息的消费者是谁

CSP 是面向 channel 的消息模型,不用关心谁来消费,只需要知道有人订阅这个 channel 的话自然就可以消费。

应用场景

比较典型的就是 go,如下代码块定义了一个 goroutine,多个 goroutine 相当于 actor 模型中的 actor,goroutine 之间的通信通过 channel 去完成,channel 相当于一个队列。go 核心有个调度器,可以负责将不同 goroutine 实例和 channel 关联起来。

1
2
3
go {
//do someting...
}

数据级并行

数据级并行主要实现方式是流水线和多 ALU 处理,如下图所示:

现在看了一些资料,也有说实现方式划分为 SIMD 和 MIMD 的。数据级并行现在的 GPU 都做的比较强,硬件层面也好,软件框架标准支持层面也好。当然 CPU 也可以做数据级并行,比如像 StarRocks 这种数据库通过 AVX2 的 CPU 指令集做 CPU 上的数据级并行,也有非常好的效果。这方面的主要标准可以参考 OpenCL。当然也有 OpenGL、OpenAL 等针对特定领域的标准和框架平台支持。

书本上主要是通过上手写一个 OpenCL 的例子来理解数据集并行的。OpenCL 标准默认是 C,用 Java 也可以的,可以使用Lightweight Java Game Library 这个库,封装了 OpenCL 和 OpenGL

Lambda 架构

这种架构现在来说不一定是最优的了,书中通过 MR 的学习演示来理解这种并行模型。我理解这种模型的关键在于理解 mapreduce 的思想。下图演示了 MR 的流程,本质上是将问题拆解分而治之,然后重新归组合并再输出的过程。只有将问题合理的拆分成独立的小任务才能去更好的并行。这个可以参考 forkjoinpool 的设计理念,本质是相同的。

图参考资料: MapReduce 核心思想与工作过程