存储架构空间 - 写入路径 （P4）
这是长篇“分布式存储架构和设计空间”的第五篇。原文很长，受微信公众号长度限制，需要分P发出。全文将依次总结各存储组件的技术和设计空间，本章关注写入路径。
写入路径（Write Path）
分布式存储系统中的下一个重要组件是写入路径，通过它可以描述系统的主要工作方式。Append-only 或 Update In-place 从根本上划分了系统的风格和下一层所需的技术。写入路径几乎触及系统中的所有组件，例如元数据、索引、数据组织、日志记录、复制，以及许多系统属性（system properties），例如一致性，持久性（Durability），读写放大（Amplification）。而读路径可以看作是写路径的缩影，外加为优化性能而引入的缓存。
追加 vs 就地更新（Append-only vs Update In-place）
系统的第一个关键维度是 Append-only（追加） 与 Update In-place（就地更新）。传统的单节点文件系统通常就地更新磁盘数据（BtrFS 除外）。后来 LSM-tree 的快速采用，导致了 Append-only 系统（也称为日志结构系统，Log-structured systems）的主导地位。不仅 HDD 受益于顺序写入，SSD 由于内部的 FTL 和 GC，也受益于 Append-only（例如 RocksDB）。更多地，PMEM 文件系统，例如 NOVA 采用 Append-only 和 Per-inode Logging；内存系统（In-memory systems），例如 Bw-tree ，采用 Append-only 增量页面（Delta pages）。
Update In-place。例如 EXT4、Ceph。如果要更新一条数据，则将其覆写（Overwrite）在磁盘的同一地址，而不是写入新地址。与 Append-only 相比，地址跟踪更简单，不需要额外的内存元数据来记录新地址，并且不需要额外的昂贵的 GC 来回收旧数据。缺点是：1）底层硬盘（HDD）不喜欢随机写入；2) 对于固定块大小的系统，存储压缩结果（大小可变）很棘手；3）双写问题（Double write），覆写需要事务以实现崩溃保护（Crash Consistency），因而新数据需要在日志中额外写入一次。 基于内容的寻址（Content-based addressing）。例子是 XtremIO。每条数据都有一个固定的磁盘存储位置（在磁盘块级别，按数据哈希放置）。当数据块位置由数据的内容哈希确定时，可以自动去重。由于数据块位置的自由度为零，这样的系统需要很少的元数据来跟踪数据位置，并且不能直接通过 Append-only 实现。 组关联缓存（Set-associative cache）。示例是 Kangaroo 和 Flashcache[319] 。整个 SSD 用来映射一个大的 HDD 空间，就像 CPU 缓存映射内存一样。HDD 数据块可以存储在 SSD 上，从一个小集合的块中选择。该集合由哈希确定，通过线性探测（Linear probing）寻找其中的块。同样，通过限制数据位置的自由度，需要极少的内存元数据。
数据库分页（Database paging）。一种更简洁的 Update In-place 方法是将地址空间划分为页面，并使用页面作为传输的原子单位。这里的“页”就像是存储“块”。但是，系统还需要事务日志来保证崩溃一致性（Crash Consistency）。更多地，即使只更新几个字节，也得切换（switch）整个页面，即写放大（Write amplification）。页面可能有内部碎片（Internal Fragmentation），无法利用边缘的（marginal）字节，导致空间放大（Space amplification）。如果页面（Page）不需要大小相等，该技术可变成“块”（Chunk）或“微分区”（Micro-partition）。
Append-only。例子有 LSM-tree 或 RocksDB，日志即数据库，以及 Azure 存储。系统不支持修改磁盘上已写入的数据，因此更新需要追加（append）到新的地方，类似日志。此类系统的主要缺点是：1) 需要不断的 GC（或 Compaction）来回收旧数据，这会占用甚至 50% 的系统带宽。2) 数据位置的自由度高，系统要么需要庞大的内存元数据以进行跟踪，要么在扫描时过时数据时会导致读放大。好处是：1）一切都简化了，因为写入的数据是不可变的（Immutable）；2）写入是顺序的，受 HDD 喜爱；3）事务和崩溃一致性是自然支持的，因为数据即日志。多年来，Append-only 被证明是成功的。
顺序结构与否（Sequential structure or not）。例子是 BtrFS。并非所有的 Append-only 系统都使用顺序的日志记录（Sequential logging）。在 BtrFS 中，新数据写入时 Copy-on-write 到新页面（COW），然后原子地链接到 B+ 树。此外，像并行多段日志（Parallel Multi-segment Logging）这样的优化，也打破了默认的顺序日志记录。
在线或离线清理（Cleanup inline or offline）。Append-only 系统需要清理过时数据；应该在写入路径上进行还是离线完成？GC/Compaction 选择离线。Apache Hudi 的 Copy-on-write 选择在线于写入路径上。此外，清理甚至可以延迟到第一次用户读取，即 Apache Hudi 的 Merge-on-read。
增量数据（Delta data）。Append-only 的想法可以扩展到 PMEM（例如 NOVA）或内存（例如 Bw-tree）上的索引。追加增量数据的方式，有利于高并发，简化锁的处理，并避免像 COW 那样的读写放大。从另一个角度来看，不可变数据可以通过 COW 或追加增量实现，但 COW 在写入路径上强制 Compaction。
日志即数据库（Log is database）。我们之前已经提到过它。数据库分页的设计倾向随机写入，与之相比，在组件间传输日志倾向顺序写入。如果只修改部分页面，同步整个页面（syncing pages）导致写放大，但可以吸收对同一地址的重复修改；而由日志携带的增量，比完整页面小，但重复修改可以增长为长链，因此需要 Compaction 。虽然日志可以很容易地用作数据库状态的一致性的事实（a consistent truth for database state），但重播（replay）最新数据会产生计算成本，并且需要仔细的版本控制以利用缓存的页面。
混合方案（Hybrid approach）。例子是 Ceph BlueStore，其中大写入用 Append-only，不与现存数据重叠的小写入用 Update In-place，小的覆写（Overwrite）合并到 RocksDB WAL （Write-ahead logging，预写日志）。这种方法是为了克服 Ceph 的双写问题而发明的，它实质上将过去的 Update In-place 转变为 Append-only。
从更高的层面思考， Append-only 与 Update In-place 背后的驱动因素是是否延迟 维护磁盘上的数据组织（Maintaining on-disk data organization），以在线还是离线方式进行，或者说使用写入优化的数据格式（Write-optimized Data Format）vs 读取优化的数据格式（Read-optimized Data Format）。
写入路径 是高效的，如果不需要维护磁盘上的 数据组织（Data Organization）（参见 数据组织章节）。写入会因批处理（batching）、顺序性（sequential）而受益；这是 Append-only 带来的好处，除了用于 GC/Compaction 的额外带宽。此外，写入受益于更少的需要协同更新（co-update）的组件（in sync，同步地），例如更少的索引、缓存、更少的碎片化的写入位置。
读取路径（Read path） 是高效的，如果数据有索引，或者存储位置可以从键（Key）中计算得出，或者排序良好以有利于全扫描（Full Scan）。数据应该更少碎片化（less fragmented），保留局部性（locality），并且具有更少的过时条目（stale entries）。尽管 Append-only 生成碎片化的增量，但 GC/Compaction 可以将它们重写为读取优化的数据格式。尽管 Update In-place 节省了 GC/Compaction 的带宽，但实现读取优化的数据格式可能仍需要额外的重写。
数据索引（Data index） 通常被高效的读取路径所需要。 Update In-place 通过限制数据位置的自由度来减小索引大小，但不适用于二级索引（Secondary Index）。它也避免了减小跟踪粒度，即不像 Append-only 将小更新重定向到新页面。这也意味着连锁发生的索引更新更少。
磁盘上的数据组织（On-disk data organization）。最好的读取优化的数据格式几乎总是需要完全重写才能生成，这解释了为什么 Append-only 是有利的，特别是考虑到列压缩（columnar compression，即 OLAP）。新近的数据，可以通过冷热分层（Tiering，或类似于 LSM-tree 中的 “Level” ）分离。它仍可能受益于 Update In-place，以减少 GC/Compaction 或索引的扰动（尽管实际上大多数系统仍使用 Append-only）。
协同更新邻接组件（Co-updating neighbor Components）
除了磁盘数据外，写入路径还涉及更多需要一同更新的组件，例如元数据、索引、检查点（Checkpoint）、日志记录、缓存。
元数据、索引（Metadata, index）。这里主要关注的是从磁盘数据更改到最终用户的可见性的传播。这在之前的 一致性章节 中提到过。
检查点、日志记录（Checkpoint, logging）。新的更改首先由 WAL 原子地实现持久化，一种典型的技术是分离键/值 (WiscKey)。然后可以将已持久化的更改传播到索引和元数据，以便对用户可见。日志记录是一种写入优化的数据格式，但读取需要结构化的数据。“结构化的数据”要么定期从内存刷新到磁盘，即检查点，要么通过传输数据库页面实现。碎片化、有重叠部分的检查点，需要 GC/Compaction 来重写为更读取优化的数据格式（例如 LSM-tree），并回收已删除的存储空间。
缓存（Cache） 更新是异步的，通常从写路径，离线进行；除非写入想要无效化（Invalidate）过时数据，或立即加载新数据。
除了在本地写入外，数据复制 也在混合在写入路径中。它实现了持久性（Durability）和许多其它目的
持久性（Durability），例如 Raft 复制，3-way Replication，Quorum Write，参见 一致性章节 。为持久性而使用的数据复制通常是同步的，具有强一致性。
灾难恢复（Disaster-recovery），例如备份（Backup）, 地理复制（geo-replication），参见 一致性章节 。它们可以异步进行，并设定 RPO 。
局部性（Locality），例如将数据移动到用户本地区域的地理复制，例如 Akkio u-shards。由 CDN 充当静态内容的缓存，作为跨 WAN 提供商间的桥梁。
数据布局（Data layout）。例如 TiFlash 和 F1 Lightning 。数据库将主要数据副本维护为行格式（row format）以服务于 OLTP，它复制一个额外的列布局（Columnar format）副本供 OLAP 使用。可以使用 Raft 协议或细粒度版本跟踪来保持副本之间的一致性。
冷热分层（Tiering）。热点数据可以复制到缓存。冷数据可以卸载（Offload）到慢速的 HDD 或归档存储（Archival Storage）中。层之间的数据格式也可以不同，以优化访问延迟、存储效率或压缩。
数据平衡（Data balance）。通常，数据可以重新平衡以填充更空的新节点，从关联故障域（Correlated failures）的位置分散开，或平衡节点上的冷热访问。
日志即数据库（Log is database）。不同于复制数据或页面，而是将带有增量的日志作为数据的真实来源（source of truth），进行复制和传播。参见 一致性章节 。
分离写入路径和读取路径（Separating write path and read path）。例子是 AnalyticDB、MySQL 主/从复制。该设计源自数据库社区，使用一台服务器作为写入主服务器，并复制到多个副本以横向扩展（Scaleout）读取能力。它利用该模式：社交网络以相对恒定的速率生成内容（写入），但用户浏览量（读取）可能会激增（burst）。
涉及数据的离线后台作业（offline background jobs）也可以按目的划分。它们通常会重写数据副本，这是 写放大 的主要来源，但有必要通过生成更优化的数据布局来减少 读放大。
持久性（Durability）。通常涉及数据修复（data repair）的过程，当节点或磁盘出现故障时被考虑。这些后台作业需要较短的检测发现时间（detection time）和高优先级的带宽。可以通过 引入更多节点 提供源数据，来提高数据修复的效率，例如 Ceph 修复让整个集群参与，Copyset 修复集群的分区参与，以及主/从复制让少数从节点参与。
存储效率（Storage efficiency）。数据压缩可以在写入路径之外运行，以避免增加用户可见的延迟。擦除编码（Erasure Coding）可以进一步减少所需的存储空间。GC 定期运行以回收已删除的存储空间。
数据布局（Data layout）。例如 RocksDB 运行离线 Compaction，来删除过时数据，整理重叠的 SST 文件，以提高读取效率。例如 AnalyticDB 将新的写入缓冲在增量文件中，然后将它们合并到基线数据并构建全量索引。类似的增量合并模式也可以在 Datalakes 中找到，例如 Apache Hudi 。对于数据复制，目标副本可以放在另一个区域甚至另一个云服务中，同时计算也可以 卸载到云。
数据完整性（Data integrity）。存储系统通常采用离线数据擦洗（Data Scrubbing）来检测静默数据损坏（Silent Data Corruption）。端到端 CRC（End-to-end CRC）可以与数据一起存储。此外，可以检查不同层次的不变约束（Invariants），例如索引与数据，映射关联（mapping constraints）。
写入不同的存储介质（Write to different storage media）
写入数据流经或最终持久化在一种存储介质中：内存、PMEM、SSD、HDD、或归档磁带（archival taps）。数据结构和所使用的技术（techniques）因存储介质的特性（characteristics）和工作负载（workload）访问模式（access pattern）而异。我们将在 数据索引章节 和 数据组织章节 中看到更多信息。
内存层（Memory tier） 在随机访问方面做得很好，与其它存储层相比延迟最低。主要关注的是提高并发性、缓存效率、以及在内存排列（pack）更多数据。典型的数据结构可以是普通指针链接（例如 FaRM），跳表（Skip List，例如 RocksDB），或有利于并发的 Bw-tree。相比红黑树，B+-tree[320] 更大的节点有利于装进缓存行（Cache Line）。还有哈希表用于快速查找（例如 Memcached）。可以启用内存压缩（Memory compression）和磁盘交换（disk swap，例如 TMO[321]）。
持久内存层（PMEM tier） 比 DRAM 慢 2~3 倍（PMEM empirical guide[322]），并且不喜欢小的随机写入。主要关注点是提高并发性，补偿较慢的 CPU ，并保障崩溃一致性，同时避免昂贵的缓存 flush 指令。RDMA 和 Kernel Bypassing 是常见的技术。基于树的 Append-only 数据结构，例如 NOVA 中的 per inode 日志记录，仍然是有利的。另一种方法使用哈希表数据结构，例如 Level Hashing 。
SSD 层。除了少数系统 Update In-place 外，大多数系统都转向 Append-only，例如 RocksDB 和使用 RocksDB 作为引擎的 TiDB / Cockroach / MySQL，使用 LSM-tree（类似）引擎的 HBase / ClickHouse，或构建在共享日志记录之上的 FoundationDB / Azure 存储。换句话说，SST 文件和共享日志是 SSD 上常见的数据结构。OLAP 数据库也青睐于批量追加和重写为压缩的列式布局。一些数据库选择为每一列建立索引，而另一些则完全依赖于全扫描（Full Scan）。
HDD 层。由于两者都青睐于 Append-only，因此 HDD 或 SSD 上的数据结构相似，大多数系统可以在两者上互换运行。不同之处在于 SSD 需要更多的 CPU ，和为每个设备（SSD die、plane）分配的并行度。
存档磁带层（Archival tapes tier）。Append-only 也是受欢迎的写入方式，例如 Data Domain，因此与 HDD 或 SSD 没有太大区别。数据通常以顺序结构进行去重（Dedup）和追加，并依靠索引进行查找。去重指纹（fingerprint）可以与保留局部性（Locality）的数据一起存储。更高的压缩级别和更长的纠删码常被使用。
计算层（Computation tier）。上述层按数据大小排序。而计算层的特殊之处在于，在某些情况下没有数据需要存储，它们可以通过计算重新得出。换句话说，在计算中“存储”数据。
在不同的存储介质之间分层（Tiering between different storage media）
通常，存储介质层是根据数据的价格、规模和性能目标来选择的。每一层都有自己的优化技术。跨层的数据移动还需要高效的冷热检测/预测（detection/prediction）算法，这些算法通常是 LRU 变体，但更关注于减小因大数据规模而带来的跟踪元数据体积：
指数平滑（Exponential Smoothing）。这是标准的学术方法，它用一个权重来平均现在和历史的热度，更早的历史被指数级地遗忘。该方法没有提到如何有效地实现它。热度可以通过时间窗口中的数据访问次数和字节数来衡量。
LRU（Least-recent Used，最近最少使用）。与指数平滑一样，LRU 是大多数冷热分层算法的典型，但没有指定如何实现。
每个对象的比特（Bits per object）。例子是 Kangaroo RRIParoo 算法。冷热度由每个对象的比特跟踪。当访问对象时，或需要全局逐出时（例如时钟到期、缓存已满），可以翻转一个比特位。如果所有比特位都匹配，则可以逐出该对象。
列表中的对象（Objects in list）。例子是链表实现的 LRU，或 Linux 内核的 内存页面交换[323] 。冷热由列表中的对象位置跟踪。对象在访问时被提升到头部，在变冷时被降级到尾部，并最终被逐出列表。
上次访问和过期（Last accessed and expire）。通常在 App 操作旁路缓存时看到。简单地说，数据库中最新访问的项目被放入缓存中。如果缓存已满，则最旧的项目将被逐出。缓存项也会因超时而过期。
离线分类（Offline classification）。例如 Hekaton Siberia，Google G-SWAP[324]。当冷热跟踪元数据过大时，系统可以将流量记录（可能被采样，sampled）转储到磁盘，并采用离线的定期分类作业或 机器学习 对冷热数据进行分类。
用户标记（User tagging）。为最终用户开放接口，以明确标记一条数据是热是冷。方法简单，而用户总是更了解自己的数据。
写入和读取路径合并（Write & read paths coalescing）
虽然写/写和读/读合并是常见的技术，但写/读和读/写有有趣的方式来组合，并重用彼此的中间结果。
写入合并（Writes coalescing）。小写入可以组合成一个大写入到磁盘。系统可以使用定时蓄水池（timeout plug）来积累足够多的小写入来合并，或者是扫描并重排序写入队列。可以组合相邻地址中的小写入以形成大的顺序写入。可以合并（cancel out）对同一地址的重复写入，仅需将最后一次写存入磁盘。可使用更快的 Stageing 内存、闪存（flash）、或 PMEM ，来吸收小写入。
读取合并（Read coalescing）。与写入一样，可以组合小读取以利于顺序磁盘访问，或者通过缓存来避免重复磁盘读取。读取查询通常需要扫描比用户请求更多的物理数据，这意味着可以批处理（batch）多个查询，并共享一次磁盘扫描。
读作为写的路径 （Read as a path for write）。当读取查询扫描数据以查找某些内容时，概念上它正在构建索引。读取可以利用该扫描，将索引的“零件”推送到写入路径，而写入路径负责真正地构建索引。例如 REMIX LSM-tree[325] 利用范围查询为 SST 文件构建索引。写入路径还负责将新接收的数据重写为读取优化的数据格式，它可以重用读取查询刚刚扫描并加载到内存中的内容。当加载操作昂贵、且涉及远程网络时，这个技术更有用。
写作为读的路径（Write as a path for read）。新写入的数据通常更有可能被读取。写入可以将它们留在内存或 Staging 区中，直接填充（populate）缓存，并将它们组织在读取优化的数据结构中，让接下来的读取受益。例如典型的 LSM 树中的内存表（Memtable）。
卸载（Offloading）
在线或离线于写入路径，FPGA 和 ASIC 通常用于从 CPU 卸载计算，例如压缩/加密和多租户（multi-tenant）的云虚拟网络（virtual network）处理。卸载能够减轻不断增长的 IO 硬件吞吐量对 CPU 的压力，而下推（Pushdown）则缩短了数据传输的路径。
FPGA 的特色是支持重新配置（Reconfiguration），有利于灵活性和快速实验。 ASIC 是专用电路，很难更改，但制造完毕后，它们的效率要比 FPGA 高得多。FPGA 有成功的用例，例如 Project Catapult[326] ，SmartNICs[327] 也很受欢迎。
压缩/加密 是典型的卸载用例，因为逻辑是固定的，很少有异常处理，并且计算是面向数据管道（data pipeline）的。网络处理类似。此外，如今的高速 RDMA 对 CPU 的要求更高，云虚拟网络涉及更多层次的的重定向。
最近的 IPU[328]（Infrastructure Processing Unit，基础设施处理单元）在 DPU[329] 之后被提出，将常见的数据中心基础设施功能卸载到 CPU 以外的处理芯片。
Smart SSD[330] 将计算芯片添加到 SSD。查询过滤或 GC/Compaction 可以下推到 SSD 内部，而不需要跨 PCIe 的更长的数据传输路径。
引用
前文中引用的很多技术名词和产品可以在 存储架构空间 - 参考架构 （P1） 中找到，P1 专门汇总各类技术。
文章引用在 存储架构空间 - 引用部分 （P0） 中。
(封面图片 by SBA73, CC BY-SA 2.0: https://99percentinvisible.org/episode/la-sagrada-familia/. 注：本文为个人观点总结，作者工作于微软)