ACM

ACM通信

首页 / 杂志存档 / 2016年1月(第59卷第1期) / 不变性改变了一切 /全文

实践

不变性改变了一切

Pat Helland
ACM通信，2016年1月，第59卷第1期，第64-70页
10.1145 / 2844112
评论

认为: 打印手机应用程序 ACM数字图书馆全文(PDF) 数码版分享: 通过电子邮件发送在reddit分享在StumbleUpon分享在黑客新闻上分享在推特上分享在Facebook上分享

存储和发送不可变数据是一种不可阻挡的趋势。我们需要的不变性在远处协调，而我们能负担得起的不变性随着存储成本的降低。本文提供了一个利用不可变性的重复计算模式的小点心。在计算堆栈上爬上爬下确实会让人产生一种déjè似曾相识的感觉。

不久以前，计算成本很高，磁盘存储成本很高，动态随机存取存储器(DRAM)成本很高，但与闩锁的协调成本很低。现在所有这些都通过使用廉价的计算(多核)、廉价的商品磁盘、廉价的DRAM和ssd(固态驱动器)而改变了，而与闩锁的协调变得更加困难，因为闩锁延迟失去了许多指令机会。保持大量数据的不可变副本现在是负担得起的，一个好处是减少了协调挑战。

存储在增加，而每tb磁盘的成本在不断下降。这意味着大量数据可以保存很长一段时间。随着越来越多的数据和工作分散到很远的地方，分布也在增加。数据中心中的数据似乎“很遥远”。多核芯片中的数据可能看起来“很遥远”。当试图与遥远的系统协调时，模糊性会增加——自从您听到消息以来，已经发生了更多的事情。你能在不完全了解的情况下采取行动吗?你能等待足够的知识吗?

乌龟一直往下走。¹⁷随着各种技术领域的发展，它们通过以一些非常有趣的方式使用不可变数据来应对存储、分发和模糊性增加的趋势。本文将探讨应用程序如何在其正在进行的工作中使用不可变性，它们如何生成一个不可变数据集用于以后的离线分析，SQL如何公开和处理不可变快照，以及大规模并行大数据工作如何依赖于不可变数据集。这导致我们要研究如何在保持不可变的情况下改变语义不可变的数据集。

接下来，本文将考虑如何通过LSF(日志结构文件系统)、COW(写时复制)和LSM(日志结构合并树)等技术将可更新性置于新的不可变文件的创建之上。复制和分布式文件系统如何依赖不变性来消除异常?硬件开发人员通过在ssd和hdd(硬盘驱动器)中利用这些技巧加入了这个聚会。在堆栈的许多层上，不可变性是一个关键的体系结构概念，如所示图1．

最后，本文讨论了使用不可变数据的一些利弊。

回到顶部

会计不用橡皮擦

许多类型的计算都是如此扩展。本节将介绍通常完成这一任务的一些方法。

在仅追加计算中，观察结果被永久(或长时间)记录。导出的结果按需计算(或定期预先计算)。

这类似于DBMS，其中事务日志记录对数据库的所有更改。高速追加是更改日志的唯一方法。从这个角度来看，数据库的内容保存了日志中最新记录值的缓存。真相是木头。数据库是日志子集的缓存。缓存的子集恰好是日志中每个记录和索引值的最新值。

会计:观察和推导的事实。会计不用橡皮擦;否则他们可能会进监狱。分类帐中的所有条目都保留在分类帐中。可以更正，但必须在分类帐中增加新的分录。当一家公司公布季度业绩时，其中包括对上一季度的小幅修正。小的修复是可以的。它们也是只能附加的。

一些条目描述观察到的事实。例如，从支票帐户收到借方或贷方是观察到的事实。一些条目描述派生的事实这意味着，根据观测结果，可以计算出一些新的东西。例如，基于比率和成本的摊销资本费用是派生事实。另一个例子是应用借方和贷方的当前银行帐户余额。

只能追加的分布式单主机。单主计算意味着更改是有顺序的。命令可以来自一个集中的主服务器或类似paxos的程序¹¹提供串行排序的分布式协议。每次在语义上应用一个更改，并在它们的前身之上分层。新价值观取代旧价值观。该粒度可以是关系存储中的一组记录或文档的新版本。分布式单主计算意味着数据空间(关系记录、文档、导出文件等)从一个逻辑位置发出，随着时间的推移会有新的版本。

分布式计算“回到过去”。在电话出现之前，人们利用信使来传递信息。另一种选择是邮政服务来递送消息，这需要很长时间。有时，人们使用有许多层的奇特形式，每一层都有不同的颜色。他们在页面上有多个部分。每个参与者都填写了一段(用笔使劲压)，然后撕掉表格的背面，把它归档。每个参与者都获得了所需的数据，并向表单添加了更多的数据。以前的部分无法更新;只能在末尾追加数据。

在计算机出现之前，工作流程通常是在纸表单中获取的，表单上有多个部分和多个页面(例如，“填写第3部分并保持后面的黄花页面”)。这种“分布式计算”只是附加的。新消息是对formex的新添加，每个消息都是一个版本，每个都是不可变的。你永远不允许重写已经写好的东西。

回到顶部

外部数据vs.内部数据

令人惊讶的是(对数据库老手来说)，并不是所有的数据都保存在关系数据库系统中。本节(基于先前的一篇论文。⁷)讨论了解锁数据的一些含义。

内部数据指由经典关系数据库系统及其周围的应用程序代码保存和管理的内容。有时这被称为服务。

内部的数据存在于事务性世界中，更改以可序列化的方式应用(或类似的方式)。

外部数据被准备为消息、文件、文档和/或Web页面。这些是从一个服务发送到世界。也有可能外部数据是由使用数据库以外的其他机制创建的。

外部数据:

是不可变的。一旦写好，就永远不会改变。
是开着的。它没有被锁定在数据库中。一个副本被提取并发送到外部。
有身份。当发送到外部时，这些文件、文档和消息具有唯一的标识(可能是URL)。
可能是版本。更新不是更新，而是带有新的惟一标识符的新版本。

内外对比。内部数据与外部数据在表示、含义和使用方面存在很大差异。越来越多的数据被保存为外部(不可变)数据(参见图2)．

回到顶部

引用不可变数据

数据集是具有惟一ID的数据集合。有些数据集的结构看起来像许多带模式的表。关系数据库如何引用这些数据集，关系操作符如何跨越DBMS和数据集?

数据集是一组固定的、不可变的表。在数据集中捕获每个表的模式。在创建数据集时捕获每个表的内容。由于数据集是不可变的，所以创建数据集时，可以使用数据集进行读取，然后删除数据集。数据集可以是关系型的，也可以有其他的表示形式，如图表、层次结构，如JSON (JavaScript对象表示法)或任何其他表示形式(图3)．数据集是一组不可变表及其模式的逻辑集合。

数据集可以被RDBMS(关系DBMS)引用。元数据对DBMS是可见的。可以对数据进行读取访问，即使它可能没有更新。数据集可能在语义上出现在关系系统中，即使它在物理上存储在其他地方。因为数据集是不可变的，所以不需要锁定，也不需要担心控制更新。

不可变数据集上的关系工作。函数式计算接受一组输入，并可预测地创建一组输出。这可能发生在对关系数据库中的锁定数据或快照数据的查询中，也可能发生在大数据mapreduce风格的系统中。在这两种情况下，仍然有一个不变的数据集合。使用快照或某种形式的隔离，数据库数据在计算期间在语义上是不可变的。在大数据计算中，输入通常存储在GFS(谷歌文件系统)或HDFS (Hadoop分布式文件系统)文件中。

在跨存储在关系数据库中的数据和存储在外部数据集中的数据进行联接时，没有语义障碍。锁定(或快照隔离)提供了关系数据库的一个版本，可以进行连接。命名和冻结的数据集可以与关系数据连接(参见图4)．您可以在DBMS中的数据和不可变数据集中的数据之间有意义地应用关系操作。

在某些方面，跨不可变数据集和关系数据库工作的能力令人惊讶。不可变数据集是用标识和可选版本定义的。它的模式描述了数据集创建时的形状和形式，是描述性的，而RDBMS中保存的模式是规定性的。

这种将两者融合的模式裁剪将数据集的模式(描述写入时的数据)与RDBMS的模式(描述快照时的数据)连接起来。此外，join和其他关系操作符必须将数据集的内容合并为一组关系表。这避开了数据集中的标识概念，并专门关注表，将其解释为行和列中保存的一组值。

回到顶部

永恒存在于观察者的眼中

消费者可能认为数据集是不可变的，即使数据集在幕后发生了变化。

数据集在语义上是不可变的。它有一组表、行和列。它还可能包含半结构化数据(例如，JSON)。它可能具有专用格式的特定于应用程序的数据。

数据集可以定义为先前存在的数据集的选择、投影或连接。从语义上说，所有这些数据现在都是新数据集的一部分。

数据集的重要之处在于，从读者的角度来看，它似乎是不变的。

为读取模式优化数据集。数据集在语义上是不可变的，但可以在物理上进行更改。你可以添加一个或两个索引。可以通过反规范化表来优化读访问。可以对数据集进行分区，并将数据块放置在靠近读取器的地方。数据集的面向列表示也有意义。

您可以创建一个列少得多的表的副本，以优化快速访问(瘦表)。列值可以保留在瘦表和胖表中。

通过观察和监视数据集的读取使用情况，您可以实现新的优化(例如，新的索引)。

不变性是大数据的支柱。大规模并行计算基于不可变输入和函数计算。MapReduce^3.和森林女神⁹两者都以不可变文件作为输入。工作被切割成多个部分，每个部分都有不可变的输入。此函数计算(使用不可变输入)是幂等的，因此有可能失败并重新启动。不变性是大数据的支柱。MapReduce对不可变数据执行函数式计算，以创建不可变输出。对于可靠的大数据来说，故障和重新启动是必不可少的，它基于对不可变输入的函数计算的幂等性质。

作为语义棱镜的不变性。数据集显示了一个不可变的语义棱镜，即使底层表示被增强或完全替换。钦定版《圣经》，一个字一个字，即使用另一种字体印刷，也是不变的;即使数字化;即使配上不同的图片。

如果有到新模式表示的无损转换，是否会更改数据集?新的地址字段可以有更大的容量吗?枚举值能否映射到新的底层表示?能否将数据从UTF-8编码映射到UTF-16编码?

拥有正确的部分是不够的。你必须知道如何解读它们。例如，“总统布什”在1990年和2005年的意思不同。“napkin”一词在美国和英国有不同的解释

不可变时的描述性元数据。创建不可变数据集时，数据的语义不能更改。只能按数据集创建时的情况描述内容。

大多数程序员习惯于SQL DDL(数据定义语言)支持表元数据的动态更改。这发生在事务边界上，可以为现有数据指定一个新模式。SQL DDL可以被认为是说明性的元数据因为它规定了表示(可能会改变)。不可变数据集有描述性元数据这就解释了那里的情况。

当然，可以创建引用一个或多个现有数据集的新数据集，以创建数据的新表示。每个新的数据集都有一个唯一的ID。通过引用而不是通过值实现数据集并没有什么错。

正常化是娘娘腔的事。规范化的目标是消除更新异常。当数据不是以规范化的方式存储时，更新可能会产生不愉快的结果。典型的例子是一个不完全规范化的表，其中每个员工都有他或她的经理的姓名和电话号码。这使得更新经理的电话号码非常困难，因为它存储在许多地方。在为更新而设计的数据库中，规范化非常重要。

然而，在不可变数据集中，规范化是不必要的。规范化不可变数据集的唯一原因可能是减少它们所需的存储空间。另一方面，去正规化的数据集可能更容易更快地处理为计算的输入。

回到顶部

版本也是不可变的!

每个版本都是不可变的。本节首先介绍多版本并发控制;然后是LSM等技术，它在事务空间中提供变化的语义，同时生成描述这些变化状态的不可变数据;最后，它通过COW的透镜来观察世界，通过写入新的不可变数据来实现高性能更新。

版本和历史。版本应该有不可变的名称。除了某个东西的第一个版本之外，新版本捕获早期版本的替换或扩展。一个线性版本历史有时被称为强一致性:一个版本取代另一个版本;父母只有一个，孩子只有一个;每个版本都是不可变的;每个版本都有一个标识。线性版本历史的替代方案是版本历史的DAG(有向无环图)，其中有许多父级和/或许多子级。这有时被称为最终一致性。

多版本并发控制。强一致性，或ACID(原子性、一致性、隔离性、持久性)，事务看起来像是按串行顺序运行的。这有时称为可序列化性。²

数据库会随着版本的不同而变化。事务T1是一个版本，之后的事务T2是一个版本。事务层记录和索引更改在早期版本之上的新版本。可以将新版本捕获为整个数据库的快照(尽管这不会带来高性能)。

或者，可以将新版本捕获为对前一个版本的更改。通过这种方式，可以构建键值存储，并在键值存储的基础上构建关系数据库。通过添加墓碑来删除记录。更改数据库是通过向键值存储区添加新记录来完成的。

如果在每个新版本中添加时间戳，就可以显示数据库在给定时间点的状态。这允许用户导航数据库的状态到任何旧版本。正在进行的工作可以看到数据库版本的稳定快照。

LSM:重组不可变的东西。LSM在不可变文件上提供了façade的更改。对于LSM树，¹⁵对键值存储的更改是通过编写受影响记录的新版本来完成的。这些新版本被记录到一个不可变文件中。定期地，按键对键值的新版本进行排序，并将其写入LSM树中称为0级文件的不可变文件。0级文件被合并到1级文件的集合中(通常是10个1级文件，每个文件包含十分之一的键范围)。类似地，级别1的文件与级别2的文件按10:1的比例合并。当您向下移动LSM树时，每一层都有10倍的文件。读取记录通常涉及每层搜索一个文件。随着LSM文件的合并，可以写入具有新标识的新的不可变文件。

继续……有一头牛!LSM树可以通过执行COW从不可变文件中创建可更改的数据。拷贝的粒度通常是键-值对。对于关系数据库，这可以是每个记录或每个索引条目的键值对。更改被复制到日志中，然后被复制到LSM树中(为了合并，还要复制几次)。

高性能COW是通过日志记录和经典DBMS性能技术实现的。新版本被捕获到内存中，并记录下来以进行故障恢复。每个日志文件的标识是唯一的ID，并且日志文件是不可变的。每个新的日志文件都可以记录之前日志文件的历史，甚至还可以记录即将到来的日志文件的标识。拥有一个最近的日志文件id意味着整个LSM键值存储可以重新构建。

回到顶部

保护石碑的安全

许多文件系统保持由不可变块组成的不可变文件。本节将从较高的层面探讨GFS和HDFS的实现，以及可以用这些文件做些什么。它讨论了可以重命名的文件的变化，并考虑了在一致哈希存储中存储不可变数据的价值。

日志结构文件:循环运行。通过不变性具体化更改的早期示例是日志结构的文件系统。¹⁶在这个奇妙的发明中，文件系统写总是附加到循环缓冲区的末尾。偶尔，会向循环缓冲区添加足够的元数据来重构文件系统。旧数据必须向前复制，以免被覆盖。

日志结构文件系统有一些有趣的性能特征，有好有坏。今天，它们是一种重要的技术。随着近年来技术趋势的不断发展，它们将变得更加重要。

文件、块和复制。google文件系统,⁵HDFS,¹还有一些提供高可用性的文件。每个文件都是一堆块(也称为块)。该文件由文件名和提供字节流所需的块的描述组成。为了持久性和高可用性，在集群中复制每个块。它们通常在数据中心的不同故障带上复制三次。

每个文件都是不可变的，而且(通常)只有一个写入器。创建文件后，一个进程可以向它追加内容。该文件存在一段时间，并最终被删除。多写程序是困难的，GFS在这方面遇到了一些挑战。¹³

不可变文件和不可变块支持这种复制。文件系统没有对完整文件进行更改的概念。每个块的不可变性允许它在没有任何更新异常的情况下被轻松复制，因为它不会被更新。

广泛共享不可变文件是安全的。不可变文件具有标识和内容，这两者都不能更改。您可以随时随地复制不可变文件，并在用户之间共享不可变副本。只要管理引用计数(以便知道何时可以删除它)，就可以使用文件的一个副本在多个用户之间共享。您可以将不可变文件分发到任何您想要的地方。具有相同的标识和相同的内容，这些文件是独立于位置的。

名字和永恒……一个下坡路。GFS和HDFS都提供不可变文件。不可变块(块)是跨界复制的数据节点。不可变文件是一系列块，每个块都用GUID(全局唯一标识符)标识。文件的内容是不可变的，并使用GUID标记。文件id GUID总是只指向一个文件及其内容。

GFS和HDFS也提供了一个可以更改的命名空间。不可变文件的逻辑名可能被更改。文件名可能会反弹到不同的内容。用户在更改文件名时必须非常小心，以确保他们有可预测的结果。当一个东西的名称可以改变时，它真的是不可变的吗?

不可变数据和一致哈希。考虑一个强一致性的文件系统，其中一个主系统控制一个名称空间(可能是posix风格的名称空间)。查找文件会得到一个GUID，该GUID用于查找不可变字节流。

现在考虑使用一致哈希实现的存储。¹⁰众所周知，一致哈希在故障和/或额外的容量下提供了非常健壮的再平衡。它也有一些混乱的放置行为，而戒指是调整的变化。有时，一些参与者看到了变化，而另一些则没有。当在一致哈希键值存储区中读取和更新时，读取操作偶尔会生成该值的旧版本。为了解决这个问题，应用程序必须设计成最终数据一致。⁴这是一种负担，使应用程序开发更加困难。

当在一致哈希环中存储不可变数据时，您不能获得过时版本的数据。每个存储的块都有它将拥有的唯一版本。这提供了自管理和无主文件存储的优点，同时避免了应用程序所看到的最终一致性的异常和挑战(图5)．

使用最终一致的存储来保存不可变数据还意味着，通过允许副本落在集群中较不可预测的位置，日志写可以有更可预测的sla(服务级别协议)。在分布式集群中，您可以知道在哪里你在写或者你可以知道当写操作将完成，但不会同时完成。⁸通过从强一致的目录中预分配文件，使用文件id的日志写入只需要接触弱一致的服务器，就能够重试使块在有限的时间内持久。

不可变性和分散恢复。将名称空间与块放置控制分离有许多优点。一致性哈希环即使在流量中也可以进行写和读操作。

尽管编目是访问的中心点，但在处理集群中的故障时，它不具有与名称节点相同的变化负载。集群越大，失败的数据节点越多，每个节点都需要进行许多控制操作，以将副本数量提高到3个。当这种流量发生时，来自集群的读写操作将经历SLA变化。不可变性允许使用更可预测的sla分散恢复数据节点故障。

回到顶部

硬件朝着不变的方向变化

在新设计中利用不变性的趋势是如此普遍，在许多硬件领域都可以看到。在这里，我将研究ssd的实现和硬盘中的一些新趋势。

ssd磨损平整。大多数ssd中的闪存芯片被分成多个物理块，每个块在开始磨损并给出越来越不可靠的结果之前都有有限的写入次数。因此，芯片设计者有一个被称为磨损均衡的特性¹²为了缓解flash的这一方面。磨损均衡是COW的一种形式，它将块的每个版本视为不可变版本。

闪存芯片逻辑地址空间中的每个新块或块的更新都映射到一个不同的物理块。每一次新的写(或对新块的更新)都以循环的方式写入不同的物理块，延迟写，因此每个物理块和其他物理块一样经常被写入。

硬盘:出现带状疱疹。当硬盘制造商努力增加硬盘上数据的面积密度时，一些令人头疼的物理问题已经介入。当前设计的写轨道比读轨道大得多。文字与之前的重叠，让人联想到在屋顶上铺设瓦片，因此得名用木瓦盖磁盘系统。⁶

在带状磁盘中，大量的数据被写入形成带状模式的分层写履带，部分覆盖之前的履带。在不破坏带区剩余部分的情况下，不能覆盖带区中间的数据。

为了克服这个问题，硬件磁盘控制器在磁盘控制器中实现了日志结构的文件系统。¹⁴操作系统没有意识到瓦的使用。写入磁盘的数据(即用带状板写入的数据带)保持不变，直到丢弃为止。磁盘的用户(例如，操作系统)感知到能够在适当位置进行更新。

回到顶部

永恒可能有一些阴暗面

由于不可变性在所有这些方面都得到了利用，因此需要进行权衡。非规范化文档有助于提高读性能，但要付出额外的存储成本。使用COW可以多次复制数据。当这些机制分层时，这种情况会加剧。

反常态化:灵活但肥胖。当数据集中的数据项被多次复制时，反规范化将消耗存储空间。它的优点在于，它消除了将数据放在一起的连接，使数据的使用更加有效。不可变数据的表示有更多的选择。它可以为空间优化进行规范化，也可以为读取使用进行反规范化。

写放大vs读出汗。使用COW可以多次复制数据(例如，使用日志结构的文件系统、日志结构的合并系统、ssd中的磨损均衡和HDD中的单块管理)。这被称为写放大。¹⁸

在许多情况下，写入放大的数量与读取被管理数据的难度之间存在关系。例如，随着数据的重组和合并，一些LSM系统将或多或少地进行复制。如果数据被积极地合并和重组，那么读取记录需要检查的位置就会减少。这可以以额外的写作为代价来减少阅读的成本。

回到顶部

结论

设计正朝着不可变的方向发展，这需要在不断增加的距离上进行协调。考虑到长时间存储数据的空间，不变性是可以承受的。版本控制提供了一个变化的视图，而底层数据则用绑定到唯一标识符的新内容表示。

即写即拷。许多新兴系统利用COW语义在将不可变文件写入底层存储时提供更改的façade。反过来，底层存储提供了健壮性和可伸缩性，因为它存储的是不可变文件。例如，许多键-值系统都是用LSM树实现的(例如HBase、BigTable和LevelDB)。
干净的复制。当数据是不可变的并且具有唯一标识符时，复制的许多挑战就会得到缓解。永远不用担心会发现过时的数据版本，因为不存在过时的版本。因此，复制系统可能更加灵活，对允许副本降落的位置不那么挑剔。复制bug也更少。
不可变的数据集。不可变数据集可以通过引用与事务性数据库数据进行组合，并在数据集投射关系模式和表时提供清晰的语义。查看由不可变数据集投影的语义，您可以创建针对不同使用模式优化的新版本，但仍然投影相同的语义。投影、冗余复制、反规范化、索引和列存储都是优化不可变数据同时保留其语义的例子。
并行性和容错性。不变性和函数计算是实现大数据的关键。