看看 Pat 的
关于分布式系统的零散思考
pathelland.substack.com
逃离奇点
PDF逃离奇点...
这已不再是你祖母时代的数据库
写入放大与读取开销
写入和读取之间的权衡
Pat Helland
在计算系统中，当你将内容写入持久存储时，通常需要在稍后进行重组。就我个人而言，我非常缺乏条理，而且经常丢失东西。这导致了大量的搜索，有时甚至徒劳无功。然而，将东西“存储”起来，随意放置在任何我想放的地方，却更容易。
在计算领域，有一个有趣的趋势，即写入操作会产生更多工作的需求。你需要重组、合并、重新索引等等，以使你写入的内容更有用。如果你不这样做，你必须搜索或进行其他工作来支持未来的读取。
数据库内的索引
我的第一份编程工作是实现一个数据库系统。在 1978 年，我和我的同事甚至不知道那是什么！我们如饥似渴地阅读我们能找到的每一篇 SIGMOD（数据管理特别兴趣小组）和 TODS（数据库系统事务）论文。我们了解了关系数据库这个有趣而又令人困惑的概念，以及索引如何在对应用程序透明的情况下优化访问。当然，更新索引意味着另外两次磁盘访问，因为 B+ 树的索引无法容纳在内存中。我们理解，如果你将来要读取数据，那么为数据库更改所做的额外工作是值得的。
下一个令人困惑的问题是，应该索引多少内容？我们应该索引每一列吗？何时应该将一对列一起索引？我们做的索引越多，读取查询就越快。我们做的索引越多，我们的更新能力就变得比糖浆还慢。
我了解到这是一个常见的权衡。频繁快速读取意味着写入缓慢。
行存储与列存储
我的大部分职业生涯都专注于分布式系统和 OLTP（在线事务处理）风格的数据库。对我来说，将高性能更新与今天所谓的行存储联系起来是很自然的。
另一种方法是按列组织数据：获取一批行，并按其列值组织数据。例如，每一行包含加利福尼亚州的状态，都只将单列的数据放在一起。列式数据库在执行查询时速度非常快，因为许多具有相同值的逻辑行在物理上彼此靠近。
但是，更新列存储并不容易。通常，更新会单独保存在集成的行存储中。查询以相对快速的方式检查小型行存储，因为它很小。这些查询与更快的列存储的结果相结合，以给出统一的准确答案。定期地，新的行存储更新与列存储合并，以创建一个新的列存储。这可以以级联方式完成，有点像下一节中描述的 LSM（日志结构合并）树中的合并。
当插入到列存储（或实际上是其附加的行存储）中时，你正在积累稍后需要偿还的债务。这种重写和集成新数据的债务是一种写入放大的形式，其中一次写入会在稍后变成更多次写入。
LSM：日志结构合并树
日志结构合并树最早于 1996 年提出。6 其思想是将键值存储的更改作为事务进行跟踪，新值保存在内存中。当事务提交时，最近的键值对的排序集合可以写入磁盘上的唯一命名文件中。该文件包含排序的键值对以及文件中键的索引。一旦写入磁盘，新提交的更改就不需要保存在内存中。
现在，如果你一直这样做，按键查找值开始变得像我尝试找到我随意放置在某个地方的东西时发生的情况一样。在小公寓中线性搜索你的钱包可能是可行的，但在郊区较大的房屋中搜索空间变得更大时就不是那么可行了。为了减少读取开销，LSM 树投入精力在进行中通过重写数据来组织数据。
当从存储引擎中新写入一个文件时，它会有一堆键值对。为了便于查找键，这些键值对会与较早写入的文件合并。每个 LSM 树都有某种形式的扇出，其中树的较低级别（具有较早写入的键）分布在更多文件中。例如，你可能在级别 1 拥有的文件数量是全新级别 0 的 10 倍。级别 1 的每个文件代表的键范围大约是十分之一，但代表的更新时间大约是 10 倍。类似地，移动到级别 2 会产生 100 个文件，每个文件具有更窄的键范围和更长的时间范围。
LSM 树的深度取决于扇出、每个文件的大小以及树中键值对的数量。一般来说，大多数存储都在树的最低级别。
因此，在这个越来越受欢迎的基本 LSM 结构中，存在多种实现选择。考虑
• 分级合并。当向某个级别添加新文件时，选择循环遍历中的下一个文件，并将其与下一层级别的文件合并。假设你选择 10 的扇出；你会发现，向下落入的文件的键范围通常覆盖下一层级别中大约 10 个文件的键范围。你将 11 个文件合并在一起，当一个文件落入 10 个文件上时，你会得到 11 个文件。现在，下一层级别的文件数量增加了一个，因此你重复并再次向下合并。
• 分层合并。在这种不同但相关的方法中，你让一堆文件堆积在每个级别上，然后再进行合并。假设你在每个级别向下合并之前堆积 10 个文件。这大大减少了所需的合并量。
分级合并具有较大的写入放大。写入级别 0 的每个新键值对将在其通过的每个级别被重写 10 或 11 次。另一方面，它们具有较小的读取开销，因为读取器通常每个级别只检查一个位置。
分层合并具有低得多的写入放大，但读取开销更大。由于新文件在每个级别堆积后再合并，因此合并较少，因此写入也较少。另一方面，读取需要检查更多位置，从而导致更大的读取开销。
最近有很多关于这些方案权衡的有趣工作。2,5
索引和搜索
在许多方面，搜索是数据库索引的一种变体。在数据库索引中，身份的概念隐藏在数据库中，作为行 ID 或主键。在关系系统中，索引的更新是事务性集成的，用户只能看到性能差异。
搜索系统有点不同，因为它们处理文档。大多数搜索系统在文档更改之后异步更新搜索索引。这与某种形式的文档身份结合在一起。3
搜索使读取文档变得容易得多。它大大降低了读取开销。对文档的异步更新给系统带来了对它们进行索引的债务。创建和合并搜索索引是一项复杂的工作，我认为这是一种写入放大的形式。
为了索引，你需要搜索语料库以查找最近写入或更新的文档。每个文档都需要有一个标识符，然后需要进行处理以定位搜索词（有时称为 n 元语法；https://en.wikipedia.org/wiki/N-gram）。在典型文档中找到的每个 n 元语法都需要发送到覆盖多个分片之一的索引器。因此，文档标识符现在与在可搜索文档中找到的每个术语（或 n 元语法）相关联——所有这些都是因为用户进行了写入或创建了文档！
我曾在一家互联网规模的搜索引擎工作了几年，并且了解它们的工作原理。我仍然对所有这些机器能够跟上所有这些写入放大所涉及的工作感到敬畏。对于写入的每个文档来说，这都是大量的工作——而且文档数量非常庞大。
互联网规模的搜索系统显然提供了出色且低读取开销。
大规模缓存
许多大型互联网系统都有巨大的缓存。考虑大型电子商务零售商的产品目录。每当任何内容发生变化时，许多服务器都会更新新的产品描述。这使得读取非常容易和快速，但代价是大量的写入。
规范化和反规范化
在关系数据库世界中长大，我被灌输了决心，要在数据库中包含规范化的数据。避免更新异常被认为是极其重要的。执行大量连接来获得答案是为了确保数据库不被错误的更新损坏而付出的小小代价。
我越来越认为这相当于如果你洒了盐就往肩上扔盐一样。是的……我见过别人这样做，但我不确定我是否应该这样做。
大多数系统正变得越来越分布式。其中大多数都具有包含其数据的键值对，这些键值对为了扩展而进行了分片。通过将相关数据分组到一对的值中——通常以 JSON（JavaScript 对象表示法）表示或类似的形式——很容易获取该值，可能作为字符串，并将其喷射到发出请求的远程系统。
如果你要在这个大型且分片的系统中规范化数据，则规范化的值将不会在同一个分片上。执行分布式连接比执行集中式连接更麻烦。
为了应对这种情况，人们在其数据上叠加了版本控制。这并不完美，但它比分布式连接或尝试对反规范化数据进行大规模更新更具挑战性。数据库中规范化价值的经典示例是一个反规范化的表，其中包含员工、他们的经理及其经理的电话号码。4 因为经理的电话号码在许多员工的许多表中被复制，所以很难更改它。我越来越多地看到系统在其反规范化结构中存储“截至”数据——例如，经理的电话号码被捕获为“截至 6 月 1 日”。
大型分布式系统对一致读取的语义施加了很大的压力。反过来，这可以看作是写入放大和读取开销之间的张力。
结论
我们只看了一些例子，在这些例子中，我们的系统中存在写入和读取之间的权衡。1 这在许多环境中都很常见。我们看到新兴系统在观察其使用模式时适应并优化这些权衡。有趣的东西！
参考文献
1. Athanassoulis, M., Kester, M. S., Maas, L. M., Stoica, R., Idreos, S., Ailamaki, A., Callaghan, M. 2016. 设计访问方法：RUM 推测。第 19 届国际数据库技术扩展会议论文集 (EDBT)。
2. Dayan, N., Idreos, S. 2018. Dostoevsky：通过自适应去除多余的合并，为基于 LSM 树的键值存储提供更好的时空权衡。国际数据管理会议论文集 ( SIGMOD), 505-520.
3. Helland, P. 2019. 任何其他名称的身份。 通讯 62(4), 80.
4. Helland, P. 2007. 规范化是给娘娘腔的； https://blogs.msdn.microsoft.com/pathelland/2007/07/23/normalization-is-for-sissies/。
5. Luo, C., Carey, M. J. 即将出版。基于 LSM 的存储技术。计算调查。arXiv:1812.07527。
6. O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. 1996. 日志结构合并树 (LSM 树)。Acta Informatica 33(4).
相关文章
不变性改变一切
我们需要它，我们负担得起它，现在正是时候
Pat Helland
https://queue.org.cn/detail.cfm?id=2884038
消除数据库的歧义
使用为你访问模型构建的数据库。
Rick Richardson
https://queue.org.cn/detail.cfm?id=2696453
大数据的病理学
将你的数据集放大到足够大，你所有的应用程序都会崩溃。
Adam Jacobs
https://queue.org.cn/detail.cfm?id=1563874
Pat Helland 自 1978 年以来一直从事事务系统、数据库、应用程序平台、分布式系统、容错系统和消息传递系统的实现工作。为了娱乐，他偶尔会撰写技术论文。他目前在 Salesforce 工作。
版权所有 © 2019 归所有者/作者所有。出版权已授权给 。
最初发表于 Queue vol. 17, no. 4—
在 数字图书馆 中评论本文
更多相关文章
Qian Li, Peter Kraft - 事务和无服务器是天生一对
数据库支持的应用程序是无服务器计算令人兴奋的新领域。通过紧密集成应用程序执行和数据管理，事务性无服务器平台实现了许多在现有无服务器平台或基于服务器的部署中不可能实现的新功能。
Pat Helland - 任何其他名称的身份
新兴的系统和协议都收紧和放松了我们对身份的概念，这很好！它们使完成工作变得更容易。REST、IoT、大数据和机器学习都围绕着故意保持灵活且有时模棱两可的身份概念。身份概念是我们分布式系统的基本机制的基础，包括互换性、幂等性和不变性。
Raymond Blum, Betsy Beyer - 实现数字永恒
当今的信息时代正在为世界所依赖的数据创造新的用途和新的管理方式。世界正在远离熟悉的物理人工制品，转向更接近其本质的信息的新表示方式。我们需要流程来确保知识的完整性和可访问性，以保证历史将被知晓和真实。
Graham Cormode - 数据草图
你是否曾经感到被永无止境的信息流淹没？似乎大量的新电子邮件和短信需要持续关注，还有电话要接听、文章要阅读以及敲门声要回应。将这些碎片拼凑在一起以跟踪重要事项可能是一个真正的挑战。为了应对这一挑战，流数据处理模型越来越受欢迎。其目的不再是捕获、存储和索引每一分钟的事件，而是快速处理每个观察结果，以便创建当前状态的摘要。
© 保留所有权利。