PDF不可变性改变一切
我们需要它，我们负担得起它，现在正是时候
Pat Helland
存储和发送不可变数据已成为一种必然趋势。我们需要不可变性来实现远程协调，并且随着存储成本的降低，我们能够负担得起不可变性。本文是一份开胃小菜，抽样介绍了利用不可变性的重复计算模式。在计算堆栈中上下求索确实会产生似曾相识的感觉。
不久之前，计算昂贵、磁盘存储昂贵、DRAM（动态随机存取存储器）昂贵，但使用锁存器进行协调却很廉价。现在这一切都发生了变化，廉价的计算（多核）、廉价的商品磁盘以及廉价的DRAM和SSD（固态驱动器）使得情况大为不同，而使用锁存器进行协调变得更加困难，因为锁存延迟会损失大量的指令执行机会。保持大量数据的不可变副本现在已经可以负担得起，而一个回报是减少了协调方面的挑战。
更多的存储、分布和模糊性
随着每太字节磁盘成本的持续下降，存储容量正在增加。这意味着可以长期保存大量数据。随着越来越多的数据和工作分布在很远的距离上，分布性也在增加。数据中心内的数据似乎“遥远”。多核芯片内的数据可能看起来也“遥远”。当尝试与远距离系统协调时，模糊性正在增加——自从您听到消息以来，已经发生了更多事情。您能否在知识不完整的情况下采取行动？您能否等待获得足够的知识？
层层叠叠的乌龟17
随着各个技术领域的发展，它们通过以一些非常有趣的方式使用不可变数据来应对存储、分布和模糊性增加的趋势。本文探讨了应用程序如何在正在进行的工作中使用不可变性，如何生成不可变数据集以供后续离线分析，SQL如何公开和处理不可变快照，以及大规模并行大数据工作如何依赖不可变数据集。这将引出对语义上不可变的数据集如何在保持不可变性的同时被更改的方式的探讨。
接下来，本文考虑了如何通过LSF（日志结构文件系统）、COW（写时复制）和LSM（日志结构合并树）等技术，在新创建的不可变文件之上分层实现可更新性。复制和分布式文件系统如何依赖不可变性来消除异常？硬件人员也加入了这一行列，在SSD和HDD（硬盘驱动器）中利用了这些技巧。不可变性是堆栈中许多层的关键架构概念，如图1所示。
会计师不用橡皮擦
许多类型的计算都是仅追加的。本节着眼于通常实现此目的的一些方法。
仅追加计算
在仅追加计算中，观察结果会被永久（或长期）记录下来。派生结果是按需计算（或定期预计算）的。
这类似于DBMS（数据库管理系统），其中事务日志记录对数据库所做的所有更改。高速追加是更改日志的唯一方法。从这个角度来看，数据库的内容保存了日志中最新记录值的缓存。真相是日志。数据库是日志子集的缓存。该缓存子集恰好是日志中每个记录和索引值的最新值。
会计：观察到的事实和派生的事实
会计师不用橡皮擦；否则他们可能会入狱。分类账中的所有条目都保留在分类账中。可以进行更正，但只能通过在分类账中添加新条目来完成。当公司发布季度业绩时，其中包含对上一季度的少量更正。小幅修正是可以接受的。它们也是仅追加的。
有些条目描述了观察到的事实。例如，收到借记卡或贷记卡对支票账户的记录就是一个观察到的事实。有些条目描述了派生的事实，这意味着，基于观察结果，可以计算出一些新的东西。例如，基于费率和成本的摊销资本支出是派生的事实。另一个例子是应用借记和贷记后的当前银行账户余额。
仅追加分布式单主节点
单主节点计算意味着更改以某种方式排序。顺序可以来自集中式主节点或某种Paxos11类分布式协议，该协议提供串行排序。更改在语义上一次应用一个，并层叠在其前任之上。新值取代旧值。这可以是一个关系存储中的一组记录，也可以是文档的新版本。分布式单主节点计算意味着存在一个数据空间（关系记录、文档、导出文件等等），它从一个逻辑位置发出，并随着时间的推移产生新版本。
“过去”的分布式计算
在电话出现之前，人们使用信使——通常是孩子们穿过城镇来传递消息。或者，邮政服务传递消息，但这需要很长时间。有时人们使用花哨的多层表格，每层颜色都不同。页面上有多个部分。每个参与者填写一个部分（用笔用力按压），然后撕下表格的背面并将其存档。每个参与者都获得了所需的数据，并在表格中添加了更多数据。较早的部分无法更新；数据只能追加到末尾。
在计算机出现之前，工作流程经常记录在纸质表格中，表格上有多个部分和多个页面（例如，“填写第3部分并保留背面的金黄色页面”）。这种“分布式计算”是仅追加的。新消息是对表格的新增内容——每个都是一个版本，每个都是不可变的。您永远不允许覆盖已写入的内容。
外部数据与内部数据
令人惊讶的是（对于数据库老手来说），并非所有数据都保存在关系数据库系统中。本节（基于早期的论文7）讨论了解锁数据的一些含义。
内部数据
内部数据指的是经典关系数据库系统及其周围应用程序代码所保存和管理的数据。有时这被称为服务。
内部数据存在于事务世界中，更改以可序列化的方式（或接近可序列化的方式）应用。
外部数据
外部数据被准备为消息、文件、文档和/或网页。这些从服务发送到外部世界。外部数据也可能是由数据库以外的其他机制创建的。
外部数据
* 是不可变的。一旦写入，就永远不会更改。
* 是解锁的。它没有锁定在数据库中。副本被提取并发送到外部。
* 具有身份。当发送到外部时，这些文件、文档和消息具有唯一的身份（可能是URL）。
* 可以是版本化的。更新不是更新，而是具有新唯一标识符的新版本。
内部与外部的对比
内部数据与外部数据在表示、含义和用法上存在深刻差异。越来越多的数据被保存为外部（不可变）数据（见图2）。
引用不可变数据
数据集是具有唯一ID的数据集合。某些数据集具有类似于多个带有模式的表的结构。关系数据库如何引用这些数据集？关系运算符如何在DBMS和数据集之间跨越？
数据集：不可变的数据集合
数据集是固定的、不可变的表集合。每个表的模式都捕获在数据集中。每个表的内容在创建数据集时捕获。由于数据集是不可变的，因此它被创建，可以用于读取，然后被删除。数据集可以是关系型的，也可以具有其他表示形式，例如图形、层次结构（如JSON（JavaScript对象表示法））或任何其他表示形式（图3）。数据集是不可变表的逻辑集合及其模式。
关系数据库引用的数据集
数据集可以被RDBMS（关系DBMS）引用。元数据对DBMS可见。即使数据可能不会被更新，也可以访问数据进行读取。数据集可能在语义上存在于关系系统中，即使它在物理上存储在其他地方。由于数据集是不可变的，因此无需锁定，也无需担心控制更新。
对不可变数据集的关系操作
函数式计算接受一组输入，并可预测地创建一组输出。这可能发生在针对关系数据库中锁定或快照数据的查询中，也可能发生在大数据MapReduce风格的系统中。在这两种情况下，仍然存在一个不变的数据集合。使用快照或某种形式的隔离，数据库数据在计算期间在语义上变得不可变。对于大数据计算，输入通常存储在GFS（Google文件系统）或HDFS（Hadoop分布式文件系统）文件中。
在关系数据库内部存储的数据和外部数据集中存储的数据之间执行JOIN操作没有语义障碍。锁定（或快照隔离）提供了关系数据库的一个版本，可以对其进行JOIN操作。命名和冻结的数据集可以与关系数据进行JOIN操作（见图4）。您可以有意义地对DBMS中保存的数据和不可变数据集中保存的数据应用关系运算。
在某些方面，跨不可变数据集和关系数据库工作的能力令人惊讶。不可变数据集是用身份和可选版本定义的。它的模式（描述数据集在创建时的形状和形式）是描述性的，而RDBMS中保存的模式是规定性的。
这种模式的调整将数据集的模式（描述其写入时的数据）与RDBMS的模式（描述其快照时的数据）连接起来。此外，JOIN和其他关系运算符必须必然地组合数据集的内容，将其解释为一组关系表。这避开了数据集内身份的概念，而只关注解释为行和列中保存的一组值的表。
不可变性在于观察者的角度
消费者可能会将数据集视为不可变的，即使它们在底层发生更改。
数据集在语义上是不可变的
数据集在语义上是不可变的。它有一组表、行和列。它也可能具有半结构化数据（例如JSON）。它可能具有专有格式的应用程序特定数据。
数据集可以定义为对先前存在的数据集进行SELECTION、PROJECTION或JOIN操作的结果。在语义上，所有这些数据现在都是新数据集的一部分。
关于数据集，重要的是它从读取者的角度来看似乎是不变的。
针对读取模式优化数据集
数据集在语义上是不可变的，但在物理上可以更改。您可以添加一两个索引。可以对表进行非规范化以优化读取访问。数据集可以进行分区，并将各个部分放置在靠近其读取者的位置。数据集的面向列的表示形式也可能是有意义的。
您可以创建一个列数少得多的表副本，以优化快速访问（瘦表）。列值可以同时保留在瘦表和胖表中。
通过观察和监控数据集的读取使用情况，您可能会意识到新的优化（例如，新索引）是可能的。
不可变性与大数据
不可变性是大数据的基础。大规模并行计算基于不可变输入和函数式计算。MapReduce3和Dryad9都将不可变文件作为输入。工作被分成多个部分，每个部分都有不可变输入。这种函数式计算（使用不可变输入）是幂等的，使其可以失败和重启。不可变性是大数据的基础。MapReduce对不可变数据执行函数式计算以创建不可变输出。故障和重启对于可靠的大数据至关重要，它们基于函数式计算对不可变输入的幂等性本质。
不可变性作为语义棱镜
数据集显示出不可变的语义棱镜，即使底层表示形式被增强或完全替换也是如此。《詹姆斯国王钦定版圣经》在字符上是不可变的——即使它以不同的字体印刷；即使它被数字化；即使它附有不同的图片。
如果对新的模式表示形式进行无损转换，数据集是否会发生更改？新的地址字段可以有更大的容量吗？枚举值可以映射到新的底层表示形式吗？数据可以从UTF-8映射到UTF-16编码吗？
拥有正确的位是不够的。您必须知道如何解释它们。例如，“布什总统”在1990年和2005年具有不同的含义。“napkin”这个词在美国和英国的解释不同。
不可变时的描述性元数据
当创建不可变数据集时，数据的语义可能不会更改。内容可能只能在创建数据集时进行描述。
大多数程序员都习惯于SQL DDL（数据定义语言）支持对其表的元数据进行动态更改。这发生在事务边界，并且可以为现有数据规定新的模式。SQL DDL可以被认为是规定性元数据，因为它规定了表示形式（可能会更改）。不可变数据集具有描述性元数据，用于解释其中存在的内容。
当然，可以创建引用一个或多个现有数据集的新数据集，以便创建其数据的新表示形式。每个新数据集都有一个唯一的ID。通过引用而不是值来实现数据集没有任何问题。
规范化是给胆小鬼准备的
规范化的目标是消除更新异常。当数据未以规范化方式存储时，更新可能会产生令人不快的结果。经典的例子是一个不完全规范化的表，其中每个员工都有其经理的姓名和电话号码。这使得更新经理的电话号码非常困难，因为它存储在许多地方。规范化在为更新而设计的数据库中非常重要。
但是，在不可变数据集中，规范化不是必需的。规范化不可变数据集的唯一原因可能是为了减少其所需的存储空间。另一方面，非规范化数据集可能更容易且更快地处理，作为计算的输入。
版本也是不可变的！
每个版本都是不可变的。本节首先介绍多版本并发控制；然后介绍诸如LSM之类的技术，这些技术在事务空间内提供更改的语义，同时生成描述这些更改状态的不可变数据；最后，它从COW的角度看待世界，其中高性能更新是通过写入新的不可变数据来实现的。
版本和历史记录
版本应具有不可变的名称。除了事物的第一个版本之外，新版本捕获了对早期版本的替换或增强。线性版本历史记录有时被称为强一致性：一个版本替换另一个版本；有一个父版本和一个子版本；每个版本都是不可变的；每个版本都有一个身份。线性版本历史记录的替代方案是版本历史记录的DAG（有向无环图），其中有多个父版本和/或多个子版本。这有时被称为最终一致性。
多版本并发控制
强一致性或ACID（原子性、一致性、隔离性、持久性）事务看起来好像是以串行顺序运行的。这有时被称为可序列化。2
数据库逐版本更改。事务T1是一个版本，稍后的事务T2是一个版本。事务将记录和索引更改的新版本层叠在早期版本之上。新版本可以捕获为整个数据库的快照（尽管这不会产生高性能）。
或者，新版本可以捕获为对先前版本的更改。通过这种方式，可以构建键值存储，并且可以在键值存储之上构建关系数据库。记录通过添加墓碑来删除。更改数据库是通过向键值存储添加新记录来完成的。
如果为每个新版本添加时间戳，则可以显示数据库在给定时间点的状态。这允许用户将数据库状态导航到任何旧版本。正在进行的工作可以看到数据库版本的稳定快照。
LSM：重组不可变的东西
LSM在不可变文件之上呈现出更改的假象。使用LSM树15，对键值存储的更改是通过写入受影响记录的新版本来完成的。这些新版本被记录到不可变文件中。定期地，键值的新版本按键排序并写入到不可变文件中，该文件称为LSM树内的Level 0文件。Level 0文件被合并到Level 1文件的集合中（通常为10个Level 1文件，每个文件包含键范围的十分之一）。类似地，Level 1文件以10比1的比例与Level 2文件合并。当您向下移动LSM树时，每个级别的文件数量是前一个级别的10倍。读取记录通常涉及搜索每个级别的一个文件。随着LSM文件的合并，可以写入具有新身份的新不可变文件。
大胆去做！来个COW！
LSM树可以通过执行COW，从不可变文件中创建可更改的数据。复制的粒度通常是键值对。对于关系数据库，这可以是每个记录或每个索引条目的键值对。更改被复制到日志中，然后复制到LSM树中（并且为了合并而多次复制）。
高性能COW发生在日志记录和经典DBMS性能技术中。新版本捕获在内存中并记录下来以进行故障恢复。每个日志文件的身份都是唯一的ID，并且日志文件是不可变的。每个新的日志文件都可以记录其先前日志文件的历史记录，甚至记录即将到来的日志文件的身份。拥有最近的日志文件ID之一意味着可以重建整个LSM键值存储。
安全地保存石碑
许多文件系统都保存由不可变块组成的不可变文件。本节从高层次探讨GFS和HDFS的实现，以及使用这些文件可以实现的功能的含义。它讨论了可以重命名的文件的不可预测性，并考虑了在一致性哈希存储中存储不可变数据的价值。
日志结构文件：绕圈运行
通过不可变性来实现更改的早期示例是日志结构文件系统。16在这个奇妙的发明中，文件系统写入始终追加到循环缓冲区的末尾。偶尔，会将足够重建文件系统的元数据添加到循环缓冲区中。必须向前复制旧数据，以免被覆盖。
日志结构文件系统具有一些有趣的性能特征，既有优点也有缺点。今天，它们是一项重要的技术。随着技术趋势继续朝着近年来的方向发展，它们将变得更加重要。
文件、块和复制
GFS5、HDFS1和其他系统提供高可用性文件。每个文件都是一堆块（也称为chunks）。文件由文件名和提供字节流所需的块的描述组成。每个块都在集群中复制，以实现持久性和高可用性。它们通常在数据中心的不同故障区域中复制三次。
每个文件都是不可变的并且（通常）是单写者的。文件被创建，并且一个进程可以追加到它。文件存在一段时间，最终被删除。多写者很困难，GFS在这方面遇到了一些挑战。13
不可变文件和不可变块增强了这种复制。文件系统没有更改完整文件的概念。每个块的不可变性使其可以轻松复制，而不会出现任何更新异常，因为它不会被更新。
广泛共享不可变文件是安全的
不可变文件具有身份和内容，两者都不会更改。您可以随时随地复制不可变文件，并在用户之间共享不可变副本。只要您管理引用计数（以便您知道何时可以删除它），您就可以使用一个文件副本在多个用户之间共享。您可以将不可变文件分布在任何您想要的地方。凭借相同的身份和相同的内容，文件是位置独立的。
名称和不可变性……一个滑坡
GFS和HDFS都提供不可变文件。不可变块（chunks）在数据节点之间复制。不可变文件是块序列，每个块都用GUID（全局唯一标识符）标识。文件的内容是不可变的，并用GUID标记。文件ID GUID始终指向一个且仅指向一个文件及其内容。
GFS和HDFS还提供可以更改的命名空间。不可变文件的逻辑名称可能会更改。文件名可能会重新绑定到不同的内容。用户必须非常小心，以确保在更改文件名时获得可预测的结果。当名称可以更改时，某物真的不可变吗？
不可变数据和一致性哈希
考虑一个强一致性文件系统，其中单个主节点控制命名空间（可能是Posix风格的命名空间）。查找文件会产生一个GUID，用于查找不可变字节流。
现在考虑一个使用一致性哈希实现的存储。10众所周知，一致性哈希在故障和/或额外容量的情况下提供非常强大的重新平衡能力。当环正在调整以适应更改时，它也具有某种混乱的放置行为。有时，一些参与者已经看到了更改，而另一些参与者则没有。当在一致性哈希键值存储中进行读取和更新时，读取有时会产生旧版本的value。为了应对这种情况，应用程序必须设计为使数据最终一致。4这是一个负担，并使应用程序开发更加困难。
当在一致性哈希环中存储不可变数据时，您无法获得数据的陈旧版本。存储的每个块都具有它将永远拥有的唯一版本。这提供了自我管理和无主节点文件存储的优势，同时避免了应用程序看到的最终一致性的异常和挑战（图5）。
使用最终一致性存储来保存不可变数据也意味着，通过允许副本落在集群中不太可预测的位置，日志写入可以具有更可预测的SLA（服务级别协议）。在分布式集群中，您可以知道您正在写入哪里，或者您可以知道写入何时完成，但不能两者兼得。8通过从强一致性目录预先分配文件，使用文件ID的日志写入只需要接触弱一致性服务器，就可以在有限的时间内重试使块持久化。
不可变性和去中心化恢复
将命名空间与块放置控制分离具有许多优势。一致性哈希环即使在环处于变化中也可以进行写入和读取。
虽然目录是访问的中心点，但它没有名称节点在处理集群中的故障时所承受的相同变化负载。集群越大，数据节点故障就越多，每个故障都需要许多控制操作来将副本计数提升回三个。当这种流量发生时，从集群读取和写入的操作将体验到SLA的变化。不可变性允许对数据节点故障进行去中心化恢复，并具有更可预测的SLA。
硬件朝着不变的方向发展
在新设计中利用不可变性的趋势非常普遍，以至于可以在许多硬件领域看到它。本节考察了SSD的实现以及硬盘驱动器的一些新趋势。
SSD和磨损均衡
大多数SSD中的闪存芯片被分成物理块，每个物理块在开始磨损并产生越来越不可靠的结果之前，可以写入的次数是有限的。因此，芯片设计人员具有一种称为磨损均衡12的功能，以减轻闪存的这一方面。磨损均衡是COW的一种形式，并将块的每个版本视为不可变版本。
闪存芯片逻辑地址空间中的每个新块或对块的更新都映射到不同的物理块。每个新的写入（或对新块的更新）都以循环方式写入到不同的物理块，从而均衡写入，使每个物理块的写入频率大致相同。
硬盘驱动器：铺设瓦片
随着硬盘驱动器制造商努力提高磁盘上数据的面密度，一些物理难题介入了。当前的设计具有比读取磁道大得多的写入磁道。写入以类似于在屋顶上铺设瓦片的方式与先前的写入重叠——因此得名叠瓦式磁盘系统。6
在叠瓦式磁盘中，大带数据作为分层写入磁道写入，形成瓦片图案，部分覆盖先前的磁道。如果不破坏该带的其余部分，则无法覆盖该带中间的数据。
为了克服这个问题，硬件磁盘控制器在磁盘控制器内实现了日志结构文件系统。14操作系统不知道叠瓦的使用。写入磁盘的内容（即，用叠瓦写入的数据带）在被丢弃之前保持不变。磁盘的用户（例如，操作系统）感知到就地更新的能力。
不可变性可能有一些阴暗面
当以所有这些方式利用不可变性时，需要管理权衡取舍。非规范化文档有助于提高读取性能，但代价是额外的存储成本。数据通过COW复制多次。当这些机制分层时，情况会变得更糟。
非规范化：灵活但臃肿
当数据项在数据集中复制多次时，非规范化会消耗存储空间。它的优点是消除了将数据组合在一起的JOIN操作，从而提高了数据的使用效率。不可变数据在其表示形式方面有更多选择。它可以规范化以进行空间优化，也可以非规范化以用于读取。
写入放大与读取汗水
数据可能会通过COW复制多次（例如，使用日志结构文件系统、日志结构合并系统、SSD中的磨损均衡和HDD中的叠瓦管理）。这被称为写入放大。18
在许多情况下，写入放大量与读取被管理数据的难度之间存在关系。例如，某些LSM系统在重组和合并数据时会执行或多或少的复制。如果数据被积极地合并和重组，那么读取记录需要检查的位置就更少。这可以降低读取成本，但代价是额外的写入。
结论
设计正在朝着不可变性发展，这是在不断增加的距离上进行协调所必需的。考虑到长期存储数据的空间，不可变性是负担得起的。版本控制提供了不断变化的视图，而底层数据则用绑定到唯一标识符的新内容来表示。
• 写时复制。 许多新兴系统利用COW语义来提供更改的假象，同时将不可变文件写入底层存储。反过来，底层存储提供鲁棒性和可伸缩性，因为它存储的是不可变文件。例如，许多键值系统都是使用LSM树（例如，HBase、BigTable和LevelDB）实现的。
• 干净的复制。 当数据是不可变的并且具有唯一标识符时，复制方面的许多挑战都会得到缓解。永远不用担心找到数据的陈旧版本，因为不存在陈旧版本。因此，复制系统可能更流畅，并且对允许副本落地的位置不太挑剔。复制错误也更少。
• 不可变数据集。 不可变数据集可以通过引用与事务数据库数据组合，并且当数据集投影关系模式和表时，可以提供干净的语义。查看不可变数据集投影的语义，您可以创建它的新版本，该版本针对不同的使用模式进行了优化，但仍然投影相同的语义。投影、冗余副本、非规范化、索引和列存储都是优化不可变数据同时保持其语义的示例。
• 并行性和容错性。 不可变性和函数式计算是实现大数据的关键。
参考文献
1. Apache Hadoop; http://en.wikipedia.org/wiki/Apache_Hadoop。
2. Bernstein, P., Hadzilacos, V., Goodman, N. 1987. 数据库系统中的并发控制和恢复。Addison Wesley。
3. Dean, J., Ghemawat, S. 2004. MapReduce：大型集群上的简化数据处理。《第六届操作系统设计与实现年度研讨会论文集》。
4. DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W. 2007. Dynamo：亚马逊的高可用键值存储。《第21届操作系统原理年度研讨会论文集》。
5. Ghemawat, S.、Gobioff, H.、Leung, S. 2003. Google 文件系统。《第19届操作系统原理年度研讨会论文集》。
6. Gibson, G.、Ganger, G. 2011. 叠瓦式磁盘设备的操作原理。《卡内基梅隆大学并行数据实验室技术报告 CMU-PDL-11-107》。
7. Helland, P. 2005. 外部数据与内部数据。《创新数据库研究会议论文集》。
8. Helland, P. 2014. 海森堡走对了写入的道路。《摘要：创新数据库研究会议论文集》。
9. Isard, M.、Budiu, M.、Yu, Y.、Birrell, A.、Fetterly, D. 2007. Dryad：从顺序构建块构建的分布式数据并行程序。《欧洲计算机系统会议》。
10. Karger, D.、Lehman, E.、Leighton, T.、Panigraphy, R.、Levine, M.、Lewin, D. 1997. 一致性哈希和随机树：用于缓解万维网热点的分布式缓存协议。《第29届计算理论年度研讨会论文集》。
11. Lamport, L. 1998. 兼职议会。《计算机系统汇刊》16(2): 133-169。
12. Lofgren, K.、Normal, R.、Thelin, G.、Gupta, A. 2003. 闪存 EEPROM 系统的磨损均衡技术。美国专利 #6850443 (SanDisk, Western Digital)。
13. McKusick, M.、Quinlan, S. 2009. GFS：快速演进。《 队列》7(7)； https://queue.org.cn/detail.cfm?id=1594206
14. New, R.、Williams, M. 2003. 采用叠瓦式写入技术的磁盘驱动器的日志结构文件系统。美国专利 #7996645 (Hitachi)。
15. O'Neil, P.、Cheng, E.、Gawlick, D.、O'Neil, E. 1996. 日志结构合并树 (LSM 树)。《Acta Informatica》33(4)。
16. Rosenblum, M.、Ousterhout, J. 1992. 日志结构文件系统的设计与实现。《计算机系统汇刊》10(1): 26-52。
17. 维基百科。一直到山脚都是海龟； http://en.wikipedia.org/wiki/Turtles_all_the_way_down。
18. 维基百科。写入放大； http://en.wikipedia.org/wiki/Write_amplification。
Pat Helland 自 1978 年以来一直从事事务系统、数据库、应用程序平台、分布式系统、容错系统和消息传递系统的实施工作。为了消遣，他偶尔撰写技术论文。Pat 目前在 Salesforce 工作。
版权 © 2015 年归所有者/作者所有。出版权已授权给 。首次印刷于 CIDR 2015 年。
最初发表于《Queue》第 13 卷，第 9 期—
在 数字图书馆 中评论本文
更多相关文章
Qian Li、Peter Kraft - 事务与无服务器天生一对
数据库支持的应用程序是无服务器计算令人兴奋的新领域。通过紧密集成应用程序执行和数据管理，事务性无服务器平台能够实现许多在现有无服务器平台或基于服务器的部署中不可能实现的新功能。
Pat Helland - 任何其他名称的身份
新兴的系统和协议既收紧又放宽了我们对身份的概念，这很好！它们使事情更容易完成。REST、IoT、大数据和机器学习都围绕着有意保持灵活且有时含糊不清的身份概念。身份概念是我们分布式系统的基本机制的基础，包括互换性、幂等性和不变性。
Raymond Blum、Betsy Beyer - 实现数字永恒
当今的信息时代正在为世界依赖的数据创造新的用途和新的管理方式。世界正在从熟悉的物理人工制品转向更接近信息本质的新表示方式。我们需要流程来确保知识的完整性和可访问性，以保证历史将被知晓和真实。
Graham Cormode - 数据草图
您是否曾感到被无尽的信息流淹没？ 似乎大量的新电子邮件和短信需要持续关注，还有电话要接听、文章要阅读、敲门声要回应。 将这些碎片拼凑在一起以跟踪重要内容可能是一个真正的挑战。 为了应对这一挑战，流数据处理模型越来越受欢迎。 目的不再是捕获、存储和索引每一分钟的事件，而是快速处理每个观察结果，以便创建当前状态的摘要。
© 版权所有。