写分配

在对速度的不懈追求中，现代计算机系统构建于层层抽象之上，每一层都旨在隐藏延迟并最大化效率。这项工作的核心是内存层次结构，其中小而快的缓存弥合了处理器与主存之间的巨大速度鸿沟。尽管人们对数据读取给予了大量关注，但当处理器需要写入数据时，一个关键而复杂的问题便浮出水面。如何处理“写未命中”（即写入一个当前不在缓存中的内存位置）的决策，是一个被称为“写分配策略”的基础性选择。这个看似微小的决策，却对性能、功耗和系统复杂性产生深远的连锁反应。

本文深入探讨写分配的世界。首先，在“原理与机制”一章中，我们将剖析 write-allocate 和 write-no-allocate 这两种主要策略，探索它们的机制、在多核环境中的全系统影响，以及它们与其他硬件组件之间错综复杂的相互作用。然后，在“应用与跨学科联系”一章中，我们将这一概念从一个特定的硬件优化提升为计算机科学中一个强大而统一的原则，揭示同样的“写时分配”理念如何支撑起操作系统、文件系统乃至处理器自身内部逻辑的效率。

现代计算机处理器的核心有一个简单而不懈的目标：尽可能快地为计算引擎提供数据。处理器如同一头贪婪的野兽，每秒能执行数十亿次操作，但它常常处于饥饿状态，等待着数据从广阔但缓慢的主存中传来。为了弥合这一速度鸿沟，处理器使用小而极快的内存池，称为​​缓存​​。当处理器需要数据时，它首先检查缓存。如果数据在那里（即​​缓存命中​​），一切顺利。如果不在（即​​缓存未命中​​），它就必须踏上前往主存的漫长旅程。

这就引出了一个看似简单却极其重要的问题。当处理器想要写入一段数据，而目标位置不在其缓存中时，它该怎么办？这被称为​​写未命中​​。它在此处做出的选择，一个根本性的策略决策，会在整个系统中引发连锁反应，影响性能、功耗，甚至多个处理器核心如何协同工作。

想象一下，你在一个图书馆里，想在一本书的某一页上加一句笔记。然而，这本书不在你的桌上，而是在书库的主书架上。你有两个选择。你可以给图书管理员留个条，让他找到这本书并为你加上那句话。或者，你可以借出整本书，把它带到你的桌上，写下你的笔记，然后把书放在手边，以备不久之后再次需要。这正是处理器所面临的困境。

第一个策略，即把整本书都拿到你的桌上，被称为​​写分配（write-allocate）​​。处理器是一个乐观主义者。它赌的是，如果你现在正在写入这块内存的一小部分，你很可能马上就会读取或写入其邻近的部分。因此，在发生写未命中时，它会发出一个​​请求所有权的读取（Read-For-Ownership, RFO）​​命令。这个命令会从主存中获取包含目标地址的整个内存块——通常是 64 字节，称为一个​​缓存行​​——并将其放入缓存。只有在它对其本地缓存中的该行拥有“所有权”之后，它才执行写操作。

这种做法的吸引力是显而易见的：获取整个缓存行的初始成本可能会被后续发生的、现在变得超快的对同一行的缓存命中摊销。但是，这里有一个不可忽视的前期成本。正如一项分析所揭示的，这种策略会立即为一次写入带来两次潜在的内存传输：一次是获取该缓存行的读事务，另一次是之后当被修改的“脏”行不可避免地被从缓存中逐出以腾出空间给其他数据时的写事务。对于大小为 $L$ 的一个缓存行，这相当于总共 $2L$ 字节的流量。

另一种是实用主义者的选择：​​写不分配（write-no-allocate）​​。在这种情况下，处理器只做被要求做的事，仅此而已。它将小块的写入数据直接发送到主内存，完全绕过缓存。缓存的状态保持不变。如果处理器只是在“流式传输”数据——即写入一长串它再也不会看的值——这种方式的效率就非常高。既然你永远不会再打开那些书，又何必让它们堆满你的桌子呢？

这个精确的场景是 write-no-allocate 大放异彩的经典案例。对于一个向大数组写入数据且后续没有任何读取的程序来说，write-allocate 策略的初始读取是纯粹的开销。它毫无必要地获取数据，只是为了覆盖它。相比之下，write-no-allocate 方法产生的内存流量是绝对最小的：仅仅是被写入的数据。认识到这一点，现代处理器通常支持特殊的​​非暂存​​或“流式”存储指令，这些指令是程序员给出的提示，表明数据没有时间局部性，处理器应该使用 write-no-allocate 路径。

这个局部决策在当今的多核处理器中具有深远的影响，因为在多核处理器中，多个计算引擎共享同一个内存。维护一个一致、统一的内存视图至关重要。

想象一个核心，我们称之为 $C_0$，正在执行一次 write-no-allocate 存储操作。它将写操作直接发送到内存。但如果另一个核心 $C_1$ 的私有缓存中已经有该数据的一个旧副本怎么办？如果 $C_1$ 对 $C_0$ 的写操作一无所知，它稍后将读取到过时的数据，从而导致灾难性的错误。因此，即使是绕过缓存的写操作也不能是秘密行动。它仍然必须在共享的互连总线上宣告其意图，通常是通过广播一个​​作废​​消息。任何其他在互连总线上进行监听且持有该数据副本的核心都必须将其版本标记为无效，以确保它在下次访问时从内存中获取最新的副本。无论采用何种分配策略，一致性都必须得到维护。

当多个核心试图写入相同内存位置时——这种情况被称为高竞争——情况会变得更加复杂。在这里，write-allocate 策略可能将一个简单的任务变成一场狂乱的活动。假设有 $C$ 个核心都想写入同一地址。使用 write-allocate 策略，$C_0$ 发出 RFO 请求并获得独占所有权。接着 $C_1$ 也发出 RFO 请求。这会迫使 $C_0$ 放弃所有权，并刷新其更新的数据，以便 $C_1$ 接管。然后 $C_2$ 对 $C_1$ 做同样的操作，以此类推。这将产生一连串的所有权转移，生成大约 $2C-1$ 次总线事务。与此形成鲜明对比的是，write-no-allocate 策略则异常简单：$C$ 个核心中的每一个都只将其写操作发送到内存，总共只产生 $C$ 次事务。看似“乐观”的 write-allocate 策略可能会造成核间争抢的交通堵塞。

处理器就像一个复杂的交响乐团，而写分配策略只是其中一种乐器。它的表现取决于它如何与其他乐器，如写缓冲器、编译器和预取器协同演奏。

处理器使用​​写缓冲器​​（或存储缓冲器）来避免因缓慢的写操作而停顿。当一条存储指令被执行时，数据被放入这个缓冲器，处理器立即转到下一条指令。然后，缓冲器在后台将其内容排空到缓存或内存中。编译器为了追求性能，甚至可能会重排代码以将存储操作聚集在一起（一种称为​​存储下沉 (store sinking)​​ 的技术），为写缓冲器制造突发的流量高峰。write-allocate 策略因其在未命中时需要执行缓慢的 RFO，导致该缓冲器的排空速率比 no-write-allocate 慢。这可能导致缓冲器更快地被填满，如果空间耗尽，可能会使处理器停顿。因此，一个简单的策略选择直接影响到关键流水线资源所承受的压力。

与​​硬件预取器​​的交互是这种复杂性的另一个绝佳例子。预取器是一个推测引擎，它试图猜测程序很快会需要哪些数据，并提前将它们取入缓存。有时，它会猜错。这被称为​​不准确的预取​​。当一次不准确的预取将一个无用的缓存行带入缓存时，它必须逐出现有的某一行。现在，考虑 write-allocate 策略。它会产生脏缓存行。如果不准确的预取所逐出的行恰好是脏的，那么它必须被写回内存。预取器的错误，加上由写分配策略产生的潜在状态，刚刚触发了一次完全无用的内存写入，消耗了宝贵的带宽。每一个决策都是相互关联的。

那么，哪种策略更好呢？Write-allocate 对于具有高时间局部性（即很快会被重用的数据）的数据非常有效。Write-no-allocate 则非常适合流式、无重用的数据。理想的选择不是静态的；它完全取决于程序在那个确切时刻的行为。

这就引出了许多高性能处理器中发现的优雅解决方案：​​动态或选择性分配​​。为什么不构建一个试图预测未来的预测器呢？在发生写未命中时，这个预测器会估计该缓存行很快被再次读取的概率。

• 如果预测的重用概率高，处理器就使用 write-allocate，支付 RFO 的前期成本，以期获得未来的缓存命中。
• 如果预测的重用概率低，它就使用 no-write-allocate，节省 RFO 带宽并避免缓存污染。

当然，预测器可能会出错。如果它错误地预测一个会被后续读取的缓存行为“无重用”，那么处理器虽然节省了一次 RFO 读取，但稍后会付出一次本可以成为命中的读未命中的代价。但通过仔细调整预测器，就有可能实现内存流量的显著净减少，其性能优于任何一种静态策略。

在某些情况下，决策甚至可以更加确定。考虑使用纠错码 (ECC) 写入内存的细节。要只写入一个缓存行中的几个字节，内存控制器必须首先读取整个旧行以计算新的纠错码。这个读-修改-写周期产生 $2L$ 字节的流量。但是，如果处理器知道它将要覆盖整个缓存行，它就可以只发送 $L$ 字节的新数据进行“整行写入”，这不需要预读，只花费 $L$ 字节的流量。而 write-allocate 策略无论如何都会花费 $2L$ 的流量。因此，如果处理器能检测到整个缓存行正在被覆盖，那么最佳选择是明确的：绕过缓存分配。流量的节省是确定的。

一个简单的选择，却绽放出复杂性与优雅权衡的整个宇宙。在写未命中时是否获取一个数据块的决定，并非一个微不足道的实现细节。它是内存层次结构设计的基石，是乐观主义与实用主义之间的一种平衡艺术，其后果回荡于系统性能的最高层，并深入到硬件组件之间最深层的交互之中。

现在我们已经了解了写分配的机制，你可能会倾向于认为它只是一种小众技巧，是针对处理器缓存的一种特定优化。但这就像只见一块砖，而未见整座大教堂。“写时分配”——将获取资源的成本推迟到修改它的那一刻——是整个计算机科学中最深刻、最反复出现的思想之一。它是一种“智能懒惰”的哲学，一种策略性的拖延，它远非缺陷，而是现代系统速度与效率背后的秘诀。

让我们开启一段旅程，从你每天与之交互的软件，穿过层层抽象，直至硅芯片的核心。在每一站，我们都会发现同样的原则，虽然穿着不同的外衣，但扮演着同样优美的角色。

我们的第一站是操作系统 (OS)，计算机的总指挥。它最伟大的戏法之一就是管理内存。当你运行的程序请求一大块内存时——比如，一个用于视频编辑缓冲区的一千兆字节——感觉是瞬时完成的。操作系统是如何如此之快地变出十亿字节的内存的？秘密在于，它并没有。它作弊了。

当你的程序请求一块“清零”的内存时，操作系统并不会真的去寻找十亿字节宝贵的物理 RAM。相反，它玩了一个巧妙的戏法。它将你的程序想要使用的虚拟地址映射到一个单一的、共享的、已填满零的物理页上，并且至关重要的是，将该页标记为“只读”。

只要你的程序只是从这个内存区域读取，它看到的就全是零，一切正常。操作系统在没有做任何实际工作的情况下满足了请求。魔法发生在第一次写入的瞬间。当你的程序试图改变该内存中的一个值时，处理器硬件会举手投降说：“我不能写入一个只读页！”这会触发一个陷阱（trap），一种将控制权交还给操作系统的特殊中断。操作系统，正是它自己设下了这个陷阱，现在平静地说：“啊，我明白你实际上想使用这块内存了。”只有到那时，它才会为你的程序分配一个真正的、私有的物理内存页，将零复制进去（或者直接将其清零），更新内存映射以指向这个新页，并将其标记为“可写”。现在，写操作就可以成功了。

这种通常被称为“按需零填充 (zero-fill-on-demand)”的策略是写时复制 (Copy-on-Write, COW) 的一种形式。内存直到你写入时才真正属于你。对于那些分配了巨大缓冲区但只使用其中一部分的程序来说，节省的内存是巨大的。我们甚至可以对写入发生的概率进行建模，以量化随时间推移所节省的预期内存——这是计算机科学与随机过程的美妙结合。

这同一个写时复制原则，是 [fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman) 系统调用背后的引擎，而 [fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman) 是类 Unix 操作系统的基石。当一个程序用 [fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman) 创建一个子进程时，操作系统需要创建父进程的一个近乎相同的副本。它会费力地复制父进程内存中的每一个字节吗？不，那样太慢了。相反，它为子进程复制了父进程的内存映射，但让父子进程共享相同的物理内存页，并将它们全部标记为只读。[fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman) 调用几乎是瞬时返回的。只有当父进程或子进程试图写入一个共享页时，操作系统才会介入，为写入者制作一个私有副本，然后让程序继续执行。这是内存资源“按需付费”的终极形式，其根本依赖的正是“写时分配”思想。

让我们从短暂的内存世界转移到硬盘或 SSD 上持久的文件系统领域。在这里，当你写入一个文件时，肯定必须实际分配磁盘空间，对吗？嗯，是的……但要稍后。

像 Linux 上的 ext4 这样的现代文件系统已经学会了同样的策略性拖延。当你的应用程序向一个文件写入数据时，操作系统并不会立即冲向磁盘去寻找一个块来存储它。相反，它只是将你的数据复制到主存中一个名为“页缓存”的临时存放区，并将其标记为“脏”数据。然后它告诉你的应用程序，“好了，我收到了！”，然后让你继续工作。[@problem_gpid:3648665]

物理磁盘块的实际分配被推迟到以后，这个过程被称为​​延迟分配 (delayed allocation)​​。在某个时刻，操作系统中的一个后台进程会决定是时候将这些脏数据写入磁盘了。只有在那个时候，文件系统才会查看一个文件的所有待处理写操作。通过等待，它获得了更多信息。它可能不再看到十几个微小的、独立的写操作，而是看到你已经写入了整整一兆字节。然后，它可以做出一个更明智的决定，为这整个兆字节分配一个大的、连续的磁盘空间块。另一种做法——为每个微小的写操作在它到达时就分配一个单独的块——会将你的文件散布在磁盘各处，这个问题称为碎片化，它会使回读文件变得慢得多。

当然，这种“智能懒惰”是一种权衡。如果你是一个数据库，需要保证一个文件的空间是连续的并且立即预留好，该怎么办？为此，文件系统提供了一个脱离“写时分配”策略的“出口匝道”。像 fallocate 这样的系统调用会告诉文件系统：“别偷懒！现在就为这个文件分配好块。”这是一个设计原则及其必要“逃生舱口”的完美例子，允许程序员为工作选择正确的策略。

这种写时复制的理念在像 ZFS 和 Btrfs 这样的高级文件系统中被推向了逻辑极致。在这些系统中，数据几乎从不被覆盖。对文件的写入会在磁盘的空闲区域创建修改后数据块的新副本，然后更新文件的元数据以指向这些新块。这就是为什么像即时、低成本的“快照”这样的功能成为可能。快照只是文件元数据的一个冻结副本；由于底层数据块永不被覆盖，文件的旧版本保持完好。这也自然地实现了数据去重，即多个共享相同数据块的文件可以全部指向同一个物理副本，而写时复制机制确保对一个文件的写入不会影响其他文件。然而，系统必须在记账时非常小心，始终预留足够的空闲空间来处理最坏情况下的写时复制操作。

到目前为止，我们已经看到了这个原则在软件中的应用。但这个兔子洞还要更深。“写时分配”的思想是如此强大，以至于它被直接融入了处理器本身的硬件之中。

考虑当一个 CPU 核心需要向内存写入一个值时会发生什么。如果数据的位置已经存在于核心的私有缓存中，写入会很快。但如果不在（即“写未命中”），CPU 该怎么办？一种天真的方法是直接将写操作发送到主存。但 CPU 的构建基于局部性假设——如果你写入一个位置，你很可能很快会再次读取或写入它。

因此，大多数 CPU 采用​​写分配​​策略。在发生写未命中时，CPU 首先为其缓存在该内存地址分配一个缓存行。它将整个周围的数据块（通常是 64 字节）从主存取入缓存，然后在缓存的副本上执行写操作。这看起来是额外的工作，但它通过确保数据在后续访问时近在咫尺而获得了丰厚的回报。这再次是在写入的时刻分配资源（一个缓存行）。其反面，即“写不分配”策略，也可用于特殊的“流式”存储，当 CPU 知道数据不太可能被再次使用时，这展示了硬件自身的复杂决策能力。

但也许这个原则最优雅、最微观的例子体现在​​寄存器重命名​​中。一个现代 CPU 有少量“体系结构寄存器”——即程序员看到的寄存器，如 eax 或 r1。然而，在内部，它有一个大得多的“物理寄存器”池。为了避免冲突并实现并行执行，CPU 动态地将体系结构寄存器映射到物理寄存器。现在，精彩的部分来了：如果两个不同的体系结构寄存器（例如 r1 和 r2）碰巧包含相同的值，硬件可以通过让它们都指向同一个物理寄存器来节省资源。

这种共享对程序是不可见的。但是当一条指令要向 r1 写入一个新值时会发生什么呢？你猜对了：写时复制。就在那一刻，处理器的重命名单元从其空闲列表中抓取一个新的物理寄存器，并将 r1 重新映射到它。写操作发生在这个新的物理寄存器上，从而打破了共享。与此同时，r2 不受影响，继续指向带有旧值的原始物理寄存器。这个过程每秒发生数十亿次，是一场无声的、纳秒级的“写时分配”之舞，它对今天几乎所有高端处理器的性能都至关重要。

从操作系统管理千兆字节的虚拟内存，到文件系统组织数太字节的磁盘空间，再到处理器处理单个 64 位寄存器，“写时分配”的原则在层层抽象中回响。它证明了一个单一而强大的思想——直到你真正需要修改一个资源时才为其付费——如何能为构建复杂、高效且优雅的系统提供基础。这是计算机科学中一种宁静而统一的美，它隐藏于显而易见之处，让一切都顺畅运行。