我的“并发编程十五年”，架构师进阶之路②

一个非常强大的系统依据上述内容就可以构建，或者我应该说，多年来经历系统上的冲击，上述基础经受住了时间的考验，并经历了比下一步（语法周边）更少的变化 。 我觉得这时可以离开了。 事实上，依据完美的后见之明，我相信停在这里将是一个合理的故事第一个版本。

然而，还有很多事情需要我们继续向前:

• 子进程没有并行性。 值得注意的是现在还缺乏任务和数据的并行性。 这对于构建.NET的任务和 PLINQ编程模型的人来说是痛苦的。 很多场景有潜在的并行性只是等待被发现，例如图像解码，多媒体管道，FRP渲染堆栈，浏览器，最终语音识别等等。 Midori的一个顶级目标是解决并发难题，尽管很多并行化是为了进程的“自由”，没有任务和数据并行性会使之受到损害。

• 进程之间的所有消息都需要RPC数据调度，因此无法共享对象。 缺少任务并行性的一个解决方案可能是将所有事物抽象为进程。 需要任务？ 那就创建一个进程。 在Midori，他们有充足的条件完成这个工作。 然而，这样做需要调度数据。 这不仅是一个成本高昂的操作，而且并不是所有类型都可管理，这会严重限制可并行操作。

• 事实上，我们为缓冲区开发了一个现有的 “exchange heap”，这是一个松散的基于线性的概念。 为了避免封锁大型缓冲区，我们创建了一个用于在进程之间进行交换的系统，这样就不需要作为RPC协议的一部分进行复制。 这个想法似乎是有用的，足以推广到更高级别的数据结构。

• 由于上述的单个消息循环模型，尽管缺少数据竞争，但是由于多个异步活动交叉，还存在内部竞争条件。 await 模型的一个好处在于交叉至少在源代码中可见可审计; 但是竞争仍然会触发并发错误。 我们看到了语言和框架可以帮助开发人员解决这个问题的机会。

• 最后，我们还有一个模糊的愿望，让系统中有更多的不变性。 这样做对并发安全有帮助，当然，我们也认为语言应该帮助开发人员按照正确的构建来获得现有的常见模式。 如果编译器信任不变性，我们还可以看到性能优化的机会。

我们回到学术界和ThinkWeek paper寻找灵感。 这些方法如果以一种有趣的方式组合，可以给我们提供必要的工具 —— 不仅可以提供安全的任务和数据并行性，还能提供更细粒度的隔离，不可变性以及可能解决进程内竞争的工具。

所以，我们中一部分人开始继续研究C＃编译器。

在这一节，我将重新排列故事，顺序可能有点乱。 （怎么更合适。）经过多年在“教学风格”上的工作经验，首先我将描述我们已经结束的系统，而不是从我们如何结束有点混乱的历史开始。 我希望这能带给你们一个更简洁的欣赏系统的方式。 然后我会提供完整的历史记录，包括以前的数十个系统，这对我们的影响很大。

我们从C＃的类型系统开始，并添加了两个关键概念：权限和所有权。

第一个关键概念是 permission。

任何引用都有一个许可，它控制你可以用引用对象做什么：

• mutable: 目标对象（图形）可以通过一般方式改变。

• readonly: 目标对象（图形）可以读取但不能被改变。

• immutable: 目标对象（图形）可以读取但永远不会改变。

一个 subtyping relationship 意味着你可以隐式地将 mutable 和 immutable 两者之一转化为 readonly. 换句话说， mutable <: readonly ， immutable <: readonly.

例如:

Foo m = new Foo(); // mutable by default.immutable Foo i = new Foo(); // cannot ever be mutated.i.Field++; // error: cannot mutate an immutable object.readonly Foo r1 = m; // ok; cannot be mutated by this reference.r1.Field++; // error: cannot mutate a readonly object.readonly Foo r2 = i; // ok; still cannot be mutated by this reference.r2.Field++; // error: cannot mutate a readonly object.

这些是保证，由编译器强制执行并经过验证。

如果未声明，默认值对于原始类型如 int, string等是不可变的，对于所有其他类型是可变的。 这保留了几乎所有场景中现有的C＃语义。（也就是说，C＃编译没有实质上的改变。）这是有争议的，但实际上这是系统一个很酷的方面。 争议来自于最小授权原则会导致你将 readonly作为默认选择。 而很酷的原因在于可以在他们价值提升时通过C＃代码递增他的权限。 如果我们决定从C＃中彻底地突破——事后看来我们应该这样做—— 打破兼容性选择更安全的默认是正确的; 但是鉴于我们之前所声明的C＃兼容性的目标，我认为我们的调用是正确的。

这些权限也可以显示在方法上，指示如何使用 this 参数：

class List {    void Add(T e);    int IndexOf(T e) readonly;
    T this[int i] { readonly get; set; }
}

调用者需要足够的权限才能调用方法：

readonly List foos = ...;
foos[0] = new Foo(); // error: cannot mutate a readonly object.

类似的事情可以使用委托类型和lambda表示。 例如：

delegate void PureFunc() immutable;

这意味着符合 PureFunc接口的lambda只能在不可变状态上关闭。

注意这突然变得多么强大！  PureFunc正是我们想要的并行任务。 我们很快可以看到，这些简单的概念足以使许多 PFX抽象变得安全。

默认情况下，权限是“深”的，它们以传递的方式应用于整个对象中。 然而，明摆着你可以通过其他方式与泛型交互，例如，深权限和浅权限的组合：

readonly List foos = ...;             // a readonly list of mutable Foos.readonly List foos = ...;    // a readonly list of readonly Foos.immutable List foos = ...;            // an immutable list of mutable Foos.immutable List foos = ...;  // an immutable list of immutable Foos.// and so on...

尽管样做效果显著，但人是很难满足的！

对于高级用户，我们还有一种写入通用类型的方法 —— 把许可参数化。 这对于通用代码来说是绝对需要的，然而被90％的系统用户忽略：

delegate void PermFunc(P T, P U, P V);

// Used elsewhere; expands to `void(immutable Foo, immutable Bar, immutable Baz)`:
PermFunc func = ...;

我还想提醒一下，为了方便起见，你可以将一个类型标记为 immutable，这表示“这种类型的所有实例都是不可变的”。实际上这是最受欢迎的特性之一。 在一天结束时，我估计系统中会有 1/4-1/3 的类型被标记为 immutable：

immutable class Foo {...}immutable struct Bar {...}

有一个有趣的转折。 我们将在下面看到， readonly过去常常被称为 readable，而且是完全不同的。 离开 Midori 之后我们努力工作试图把这些概念包含在C＃中并尝试统一它们。 这就是我想在这里表达的。 唯一的障碍是 readonly有一个稍微不同的意思。 在字段上， readonly现在表示“值不能更改”; 如果是一个指针，今天的 readonly不影响指示对象。 而在这个新模式中，它会有影响。 由于我们预先选择一个标志 --strict-mutability加入，所以这是可以接受的，同时需要 readonly mutable来获得历史行为，这时一个微小的瑕疵。 对我来说这些无关紧要 – 特别是鉴于C＃中的一个非常常见的错误是开发人员假设 readonly是深的（现在是）而明显的相似之处 const。

第二个关键概念是 ownership.

一个引用可以被赋予一个所有权注释，正如它可以被赋予一个许可一样：

• isolated: 目标对象（图）组成了状态的非别名传递性闭环

比如说：

isolated List builder = new List();

与指定了对于给定的引用可以进行哪些操作的许可不同的是，所有权注释告诉我们有关于给定的对象图的别名属性。一个隔离的图有一个“in-reference”指向对象图中的根对象，而没有“our-reference”（除了immutable的对象引用，这种引用是允许的）。

给定一个隔离的对象，我们可以原地改变它：

for (int i = 0; i < 42; i++) {
    builder.Add(i);}

并且/或者销毁原始引用并将所有权迁移到新的引用上面：

isolated List builder2 = consume(builder);

从这里开始，编译器将 builder 标注为未初始化的，尽管它如果被存储在堆中，多个可能的别名会引向它，因此这个分析永远不是无懈可击的。在这种情况下，原始的引用将被标注为 nulled，已防止安全陷阱。（这是众多的做出妥协从而向现存的C#类型系统中更自然地集成的例子之一。）

同时我们可以销毁隔离性，并取回一个普通的 List：

List built = consume(builder);

这使能了一种线性的形式，可以用于安全并发——从而对象可以被安全地移交，归并了缓存交换堆的特殊情况——同时使能了像builder这样的模式，为强不变性打下了基础。

为了看明白为什么这对不变性很重要，请注意我们跳过了一个immutable对象是如何创建的过程。为了安全性，类型系统需要证明在给定的时间没有其他的 mutable 引用指向那个对象（图）存在，而且永远都不会存在。值得庆幸的是这正是 isolated 能为我们做的事情！

immutable List frozen = consume(builder);

或者，更简洁地说，你很容易看到这样的情况：

immutable List frozen = new List(new[] { 0, ..., 9 });

从某种意义上说，我们已经把我们的隔离泡沫（如前所示）完全变绿了

在幕后，这里驱动类型系统的事情是 isolated 和所有权分析。我们稍后会看到更多的形式可以工作，然而对此有一个简单的看法：所有插入 List 构造函数的输入是 isolated ——也就是说，在这种情况下， new[]生成的向量——从而导致结果的 List 同样是隔离的。

事实上，任何只消费 isolated 以及/或者 immutable 输入并且仅针对 readonly 类型进行评估的表达式，都可以隐式地升级为 immutable；以及一个类似的评估 mutable 类型的表达式可以被升级为 isolated。这意味着使用普通表达式创建新的 isolated 与 immutable 的事情是很直观的。

这样做的安全性同样依赖于消除环境权限和可导致泄露的构造。

Midori的一个原则是消除 ambient authority。这使能了 基于能力的安全，然而以一种微妙的方式也对于不变性和下面将提到的安全并发抽象是必要的。

想知道为什么，我们看看前面提到的 PureFunc 例子。这为我们提供了一种方式来局部推导lambda捕获的状态。实际上，一个我们期待的特性是，只接受 immutable 输入的函数将导致 参考透明（referential transparency），从而解锁一系列创新性的编译器优化，并使得我们更容易溯源代码。

然而，如果可变的静态变量仍存在，PureFunc 函数的调用可能不是单纯的。

比如说：

static int x = 42;

PureFunc func = () => x++;

从类型系统的观点来看，这个 PureFunc 函数没有捕获状态，因此它遵循不可变捕获需求。（这样说可能对我们很有吸引力：我们能“看到” x++，因此能够拒绝lambda，然而这个x++可能深深隐藏在一系列虚拟调用中发生，对我们是不可见的。）

所有的副作用需要暴露给类型系统。在过去的几年里，我们探索额外的注释来表明“这个函数对静态变量有可变的访问”；然而，mutable 权限已经是我们这么做的方法了，而且感觉上与Midori采用的对于环境权限整体的立场是一致的。

因此，我们排除了所有环境方面可能带来副作用的操作，转为利用能力对象。这明显覆盖了I/O操作——所有I/O在我们的系统中都是异步的RPC——同时甚至——某种程度是从根本上——意味着即使只是获取当前时间，或者生成一个随机数，都需要一个能力对象。这让我们以类型系统能看到的方式来对副作用进行建模，同时收获能力对象带来的其他好处。

这意味着所有的静态变量必须是不变的。 这将 C# 的 const 关键字带给了所有的静态变量：

const Map lookupTable = new Map(...);

在C#中，const 仅限于原语常量，如 ints，bools，以及 strings。我们的系统扩展了同样的能力至任意类型，如 list，map，…，真正任意的事情。

这正是变得有趣的地方。正如 C# 目前 const 的概念，我们的编译器在编译时评估了所有的对象，并将它们锁定在生成的二进制镜像的只读部分。感谢类型系统保证了不变性得到遵守，这么做会导致没有运行时故障的风险。

锁定进行了两项性能改进。首先，我们可以跨多个进程共享页面、降低总体内存使用和 TLB 压力，例如，保存在映射中的查找表可以在使用该二进制的所有程序之间自动共享。其次，我们能避免对所有类构造函数的访问，并用常量偏移量将其代替，在不改变运行速度的情况下将整个系统的代码量减少 10%。

可变的静态变量代价高昂！

现在我们遇到了第二个需要修补的“漏洞”：可导致泄露的构造函数。

泄露构造函数是在构造完成之前共享 this 的构造函数。由于继承和构造函数链式关系，即使它出现在构造函数较末尾的位置，这样做也不能保证是安全的。

为什么说泄露构造不安全呢？ 主要是因为他们给第三方提供了未完全构建的对象。 这些对象的不变量是不确定的，特别是在构造过程出错的情况下，其不可变性无法保证。

在我们所处的情况中，我们怎么确保在创建一个应是不可变的对象之后，不会有人隐秘地持有一个可变的引用呢？在这种情况下，用 immutable 来标记此对象是一个类型漏洞。

我们可以完全禁用可能导致泄漏的构造函数。关键之处是什么？使用一种特殊权限，init，来表明目标对象正在进行初始化，因此不用遵守常规规则。例如，它意味着字段还不能保证已经被赋值，非空性还未确保，并且对该对象的引用也不能转换为所谓的“顶级”权限， readonly 。任何构造函数默认都有这个权限，并且你不能覆盖它。我们还自动在特定区域使用 init 机制，以保证语言能够更加无缝地工作，比如在对象初始化器中。

这会导致一个不好的后果：默认情况下，你不能从构造函数中调用其他实例方法。（说实话，这在我看来是件好事，因为这意味着你不用顾虑还未完全构造的对象，不会意外地从构造函数中调用其他虚函数，等等）。在大多数情况下，这个问题都能变通解决。但是，对于那些真正需要在构造函数中调用实例方法的情形，我们允许将方法标记为 init 来让它们则拥有该权限。

尽管上文所述在直觉上是合理的，在这些场景背后有一个正式化的类型系统。

作为整个系统的中心，我们与MSR（微软研究院）合作来证明这种方法的可靠性，特别是 isolated，并在 OOPSLA’12 上发表了一篇论文（同样内容参考免费的 MSR技术报告 ）。虽然这篇论文是在最终模型固化前几年出现的，但是当时大多数的关键思想已经形成并正在进行中。

然而，作为一个简单的思维模型，我总是从子类型和替代的角度思考问题。

事实上，一旦通过这种方式建模，对于类型系统的大多数启示很自然地“丢掉了”。readonly 是 “最高权限”， mutable 和 immutable 都可以隐式地转换过去。转换到 immutable 是一个精致的过程，需要 isolated 状态来保证遵守不变性需求。从那里，所有的通常的启示开始出现，包括 substitution（替代），variance（变化），以及它们对于对话、覆盖和子类型的各种影响。

这形成了一个二维的晶格，其中一个维度是经典意义上的“类型”以及其他的“许可”，从而所有类型都可以转换成 readonly 对象。

这个系统明显能够在没有任何这些形式化的情况下被使用。然而，我已经经历过足够的过去几年由于类型系统陷阱，带来的非常可怕但又很细微的安全问题，因此进行形式化不仅帮助我们更好地理解我们的系统，同时帮助我们晚上睡个好觉。

新的类型系统到手后，我们现在回头看看那些PFX抽象，并让他们全部安全起来。

我们必须要建立的必要属性是，当一个 activity（活动）对于一个给定的对象拥有 mutable 权限时，那个对象必须同时对任何其他的 activity 来说都是不可访问的。请注意我是故意使用 activity 这个术语的。现在，想象它等同于“task（任务）”，尽管我们将来会回顾这个微妙的瞬间。同时请注意我说的是“对象”，也是一个总的简化，因为对于某些像向量这样的数据结构，仅仅确保 activity 对于交叉区域没有 mutable 权限就够了。

除了不允许的部分外，它其实允许很多有意思的模式。比如说，任意数量的并发的 activity 可能会共享同一个对象的 readonly 访问。（这有点像读写锁，只是没有任何锁以及运行时性能损失。）记住我们能将 mutable 转换为 readonly，这意味着，给定一个具有 mutable 访问权限的activity，我们能够使用fork/join并行化来捕获一个具有 readonly 许可的变量，假设在这个fork/join操作的过程中，变化被临时停止了。

或者，以代码形式描述：

int[] arr = ...;int[] results = await Parallel.Fork(
    () => await arr.Reduce((x, y) => x+y),
    () => await arr.Reduce((x, y) => x*y)
);

仅仅读一下这段代码，我们就能知道它并行计算一个数组的求和以及乘积。这段代码是没有数据竞争的。

这是为什么呢？在下面这个例子中， Fork 使用了许可来执行所需要的安全性：

public static async T[] Fork(params ForkFunc[] funcs);public async delegate T ForkFunc() readonly;

让我们一点一点看这段代码。 Fork 仅仅以一个 ForkFuncs 数组为输入。由于 Fork 是 static（静态的），我们不必担心它会危险地捕捉状态。但 ForkFunc 是一个委托，并且会因实例方法和 lambda 而得到满足，上述两者都有可能淹没状态。通过将这个位置标记为 readonly，我们限制变量捕获的许可为 readonly；因此，尽管在上述例子中，lambda 能够捕获 arr（数组），它们无法改变它。就是这样。

同样需要注意的是内嵌的 Reduce 函数可以并行运行，这多亏了 ForkFunc！很明显所有我们熟悉的 Parallel.For，Parallel.ForEach，以及友元函数，都能够在同样安全的情况下享受同样待遇。

实际上我们能保证修改器暂停的大多数的 fork/join 模式都是这样工作的。比如说所有的PLINQ 能够通过这种方式表示，完全没有数据竞争。这是我总能想到的用例。

事实上，我们现在可以引入 automatic parallelism（自动并行）！这有几种方法可以实现。第一种方法是不要提供没有被 readonly 注释保护的 LINQ 操作接口。这也是我倾向的方法，因为让查询接口拥有改变数据的权限是荒谬的。但还有其他办法。其中一种是提供过载——一套 mutable 接口，一套 readonly 接口——编译器的过载决议将选择具有类型检查过的最低权限的接口。

如前面提到的，任务可能会比这个更简单：

public static Task Run(PureFunc func);

这采用了我们前面的伙伴，PureFunc，它确保引用透明。由于任务没有像 fork/join 以及前文中的数据平行一样的结构化生命周期，我们甚至不能允许捕获 readonly 状态。要记住，让上述例子工作的一个技巧是修改器被临时暂停了，这是我们在无结构的任务并行中无法保证的。

那么，如果一个任务需要捕获可改变状态呢？

对此，我们使用 isolated！有很多方法可以对此编码，但是，我们使用这样的方法：通过标记委托来指明它们可以捕捉 isolated 状态（这样做的副作用是使得委托自身也是 isolated 的）。

public static Task Run(TaskFunc func);public async delegate T TaskFunc() immutable isolated;

现在我们可以线性地将整个对象图推到一个任务上，永久地或临时地：

isolated int[] data = ...;
Task t = Task.Run([consume data]() => {    // in here, we own `data`.});

请注意我们使用 lambda 捕获列表来使得对象的捕捉变得直观。现在有一个 active proposal（活跃的提议） 将像这样的特性添加到未来的C#版本中，但是如果不添加很多Midori其他的特性的话，这个特性自己是否能工作还有待观察。

由于 isolation 生产周围的一些规则，任务产生的 mutable 对象可能变成 isolated，readonly 对象可能会被冻结变成 immutable。这从组合构图的角度来看是非常强大的。

最后，我们创建了更高等级的框架来辅助数据分区、对类似数组的结构进行不均匀数据并行访问，以及其他方面。上述所有都不再面临数据竞争、死锁和相关的并发危害。

尽管我们在GPU上实现了上述功能的一个可运行的子集，我不得不承认我们还没有完全搞清楚要怎么做。我能说的是当在GPU上编程时，了解其 副作用和内存的所有权是非常重要的概念，我们希望上述的构建块能够帮助创造一个更优雅和统一的编程模型。

最终，上述带来的主要的编程模型增强是细粒度的“actor”，一种在进程内部的微进程。 我在前面提到了 vat 的概念，但同时说明了我们不知道如何使它安全。最终我们找到了遗漏的线索：一个 vat 实际上只是一个状态的 isolated 气泡。既然我们在类型系统里面有这个概念了， 我们可以允许 immutable 和 isolated 对象的“编组”作为信息传输协议的一部分，这个协议不带有任何混编——他们能够通过引用安全地共享。

我想说，这个系统的主要缺点同样也是其主要的优点。纯粹地排列各种概念是很令人疲惫的。这些概念中大多数都很好地形成了，但是创建底层“安全并发”抽象的糟糕的程序员——包括我自己——几乎在做这件事情的时候失去了理智。或许有一些天才般的统一可以将许可和所有权统一起来，但是线性度的“幽默”是很难检查的。

令人惊讶的是，这居然可以工作！我之前提到的所有例子 – 图像解码器，多媒体堆栈，浏览器等等 – 现在都可以使用安全的进程内并发机制通过许多并行的过程构建出来。更有趣的是，我们其中一个生产环境的负载上 – 拿Bing.com的语音识别交通来说吧 – 明显的有延迟减少和吞吐量改善。实际上，Cortana的 基于DNN的语音识别算法，能够相当大程度的提高精度，但如果不是因为这种整体并行模型的引入就永远无法达到它们的延迟目标。

作者：高级架构师

来源：https://my.oschina.net/u/3772106/blog/1798639