Swift

讨论编写 Copy-on-Write 的正确姿势

基本形式

Swift 语言严格区分 value semantics (值语义) 和 reference semantics (引用语义). Copy on write 是一种代码范式, 它结合了操作对象时由值语义带来的安全性, 和引用语义带来的便捷性和高性能.

考虑一个对象被拷贝到另一个变量.

1
2
3
4
5
struct Object {
  // all kinds of data stored
}
var o1 = Object()
var o2 = o1 // <- Copy operation

通常而言, 对于简单而小巧的对象, 上面的拷贝操作是非常快速的. 然而当 Object 中包含了大量成员变量, 或者其包含了动态尺寸的对象 (如一块内存大小不明确的 buffer, 或者不定长度的数列), 此时的拷贝操作就可能非常耗时. 然而, 如果简单定义成 class Object 又给程序带来了 shared mutable state 即 “共享对象的意外修改” 这一陷阱.

COW 通过将核心数据定义成 reference type, 并使用 value type 进行包装解决这一问题. 部分 Swift 语言特性底层是用 COW 实现的 (例如 indirect enum 对 self 修改时), 另外也有大量标准库类型使用 COW 实现.

我们自定义的类型也可以手工实现 COW.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class CoreData {
  var value: Int
  init(_ value: Int) {
    self.value = value
  }

  func mutate() {
    value += 1
  }
}

public struct DataBox {
  private var data: CoreData
  init(_ value: Int) {
    data = CoreData(value)
  }

  mutating func mutate() {
    if !isKnownUniquelyReferenced(&data) {  // <- (A)
      print("deep copy happened")
      data = CoreData(data.value)           // <- (B)
    }
    data.mutate()                           // <- (C)
  }
}

DataBox 是暴露给外部使用的唯一接口. 使用者创建 DataBox 类型的对象后, 当没有任何修改操作时, 程序仅仅是对底层数据增加引用计数; 当发生修改时, 如果底层数据非独占, 则先进行 copy, 后再对独占的数据进行修改.
这里把 DataBox.mutate() 标记成 mutating, 体现了 Swift 如此设计带来的语法和语义的统一: 一方面在语义上提示即使是 reference type 的底层数据在通过 DataBox 这一接口修改时, 形式上必须符合 value type 的特征; 另一方面在语法上确实允许了对成员变量 var data 进行重新赋值.

并发语境下的正确性

上述实现在单线程下的正确性是显而易见的, 那么在并发语境下, 这样的写法是 ok 的吗? 在网上经常可以看到一些写法, 给 DataBox 增加了一些锁, 并使用这个锁包裹了整个 mutate 操作.

这是有必要的吗? 首先需要说明的是, 对于单一的 value type 变量, 例如 d1, 它的所有 mutating 方法本身就不应该在不同的线程中被随意调用, 正如我们知道不能在不同的线程中不加思索地修改一个 Int 或一个 Array, 这很显然破坏了多线程安全. 所以单看这一点不构成加锁的原因. 那么如果假定一个变量只是单一操作, 在涉及多变量的时候, 还会有别的问题吗? 下文解释这一问题.

以 2 个变量为例, 常见的并发操作为如下情形

1
2
3
4
5
6
7
8
var d1: DataBox(0)
var d2 = d1

// thread 1
d1.mutate()

// thread 2 
d2.mutate()

我们考察 d1 和 d2 中各自 mutate 中的 3 个子逻辑的先后关系, 进行分类讨论. 注意到

  • isKnownUniquelyReferenced 的实现是线程安全的. 即使是同一底层地址, 只要是来自不同的变量, 其返回值就是真实的, 因此可以视作原子操作. d1, d2 各自的 (A) 语句执行时间上一定有先后, 而不可能交叠. 不失一般性, 我们假设 d1.A 始终早于 d2.A.
  • 各自的 (B) 语句, 如果存在, 则是对当前底层对象的 read 操作.
  • 各自的 © 语句, 如果存在, 则是对当前底层对象的 write 操作.

Case 1: 最优情况

假设 d2.A 在 d1.B 执行完成后开始. 即整体时间序列为

1
2
|d1.A| -> |d1.B| -> |d1.C|
               |d2.A| -> |d2.C|

此时, 由于 d1.B 完成了深拷贝, d2.A 的 isKnownUniquelyReferenced 将返回 true 从而 d2 不需要进行任何拷贝. d1, d2 两者没有对同一底层对象引用的任何和操作.

Case 2: 冗余拷贝情况

假设 d2.A 在 d1.B 开始执行前返回. 即整体时间序列为

1
2
|d1.A| ->  ...  |d1.B| -> |d1.C|
          |d2.A| -> |d2.B| -> |d2.C|

此时, 由于 d1.B 中并没有完成对旧底层对象的引用 release, 因此 d1 和 d2 的 isKnownUniquelyReferenced 都返回 false, 之后两者分别对初始的底层对象进行 read 操作并执行深拷贝 (B), 再之后两者各自操作时都已经在不同的引用上了.

可以看到, 在这种情形时, 虽然我们例子中从头到尾只有 2 个变量 d1 和 d2, 但是实际运行时, 确实从头到尾生成了 3 个 CoreData 对象: 1 个是最初被 d1 和 d2 共同引用的, 2 个是各自深拷贝出的. 这也是一个例子解释为什么 isKnownUniquelyReferenced 在多线程下并不能真正用作"语义上对象是否独占"的精确判断. 当然, 在这里, 我们只是产生了一次冗余拷贝, 对程序的正确性没有任何影响.

Case 3: 剩余情况

剩余的即是 d2.A 和 d1.B 在运行时间上有交叠的情况了. 仔细研究可以确定关键之处是在于 d1.B 中在对旧的底层 CoreData 引用进行 read 操作并生成新底层对象后, 何时 release 旧对象的引用.

然而通过上面 2 种 case 的分析, 可以看到, 无论细微的时序如何, 无论 d2 的 isKnownUniquelyReferenced 返回 true 还是 false, 都无关紧要.
* 如果返回 true, 正如 case 1 一样, 它确保了 d1 中对底层对象的最后一丝引用已经消失, 从而 d2 后续无论对底层引用如果 read/write 都是独占操作.
* 如果返回 false, 那么和 case 2 相同, d1 和 d2 两者对共享的旧引用只有拷贝前的 read 操作, 即使并行也是安全的.

可能的错误, 来自他处

到这里, 我们可以看到, 不增加额外任何的同步机制, 只要如上面的代码使用 isKnownUniquelyReferenced, 我们就可以保证多线程下的拷贝安全, 从而放心地这样实现 COW.

然而, 是否仍有某种时序, 能使上文中 d1 和 d2 对底层对象的操作出现读写竞争呢? 例如是否可以构造出某种时序, 其中 d2.B 对底层对象的 read 操作 和 d1.C 对底层对象的 write 操作作用在同一个对象上, 且是并行的?

如果要构造这样的时序, 我们必须使 d1 的 isKnownUniquelyReferenced 返回 true, 而使 d2 的 isKnownUniquelyReferenced 返回 false. 这等价于要让 d2 对 d1.data 的 retain 延迟到 d1.A 执行后. 我们似乎可以写出这样的代码:

1
2
3
4
5
6
7
var data1 = DataBox(3)

DispatchQueue(label: "back thread").async {
  var data2 = data1
  data2.mutate()
}
data1.mutate()

确实如此. 上面的代码确实有概率产生 read/write 竞争. 可能导致 data2 copy 过来的数据是损坏的.

然而, 发生错误的原因, 并非是来自上文的 COW 实现, 而是来自更上层使用者. 变量 data1 在上面的代码里的使用其实已经违反了线程安全: 它在 main thread 类被 write, 而在 back thread 里被 read, 而代码也并没有使用任何机制来确保 data1 的读写安全性. 事实上, 上文也提到, 一个 value type 变量, 在不同的线程被不加限制地读写, 是相当愚蠢的做法, 只不过在这个例子里可能比较隐晦.

在历史代码中这样的编程错误并不容易被发现. 在某些情况下 Xcode 的 thread sanitizer 或者 Swift compiler 中对 “Law of Exclusivity” 机制的 Dynamic enforcement 可能可以在 debug 时帮我们发现问题. 也许是因为 value type 的强大, 部分使用场景中开发者可能对其过分自信, 使其没有意识到即使强如 value type, 在使用时也是需要考虑线程安全的. 如今 Swift 编译器也在不断进步, 使一些相关问题在编译期被暴露出来.

对 value type 在线程安全方面的使用姿势, 有一个好的准则: 只要涉及到 mutation, 就应该确保 copy 操作发生在任何可能的异步之前. 如果将 data2 的初始化放到 async 之前, 那就没有问题了.

1
2
3
4
5
6
7
var data1 = DataBox(3)
var data2 = data1

DispatchQueue(label: "back thread").async {
  data2.mutate()
}
data1.mutate()

一种更加安全[1]且 local friendly 的方式是使用 capture list 创建中间变量 (capture list 中的变量创建是在 closure 创建时).

1
2
3
4
5
6
7
var data1 = DataBox(3)

DispatchQueue(label: "back thread").async { [data1] in
  var data2 = data1
  data2.mutate()
}
data1.mutate()

此时从调用方的语义上看, 对 data1 和 data2 的操作是在独立的变量上操作的, 没有任何竞争. 即使我们怀疑 DataBox 内部是使用 COW 实现的, 可能有一些底层数据的共享, 我们也不用担心, 因为那里的正确性理应由恰当使用的 isKnownUniquelyReferenced 确保了. 这正印证了语言是否设计良好的标准之一: 每个 level 保证局部的正确性, 就可以获得整体的正确性.

  1. 上面的写法的风险在于, 无法保证 data2 在 main thread 后面会不会被读写. 事实上, 上面的写法在完整开启 SWIFT_STRICT_CONCURRENCY 后, 会报 warning/error. ↩︎