ACM通信
实践
写作放大vs阅读流汗
图片来源:Getty Images
在计算系统中，越来越多的情况是，当您将某些内容写入持久存储时，它稍后需要重新组织。就我个人而言，我是一个非常没有条理的人，我经常丢东西。这会导致大量的搜索，有时是徒劳的。然而，把东西放在我想放的地方就更容易了。
在计算机领域，有一个有趣的趋势，那就是写作需要做更多的工作。您需要重新组织、合并、重新索引等等，以使您编写的内容更有用。如果你没有，你必须搜索或做其他工作来支持未来的阅读。
数据库内的索引。我的第一份编程工作是实现一个数据库系统。1978年，我和同事甚至不知道那是什么!我们如饥似渴地阅读ACM特别兴趣小组关于数据和管理的每一篇论文ACM数据库系统汇刊我们能拿到的。我们了解了关系数据库这个有趣而又令人困惑的概念，以及索引如何在对应用程序透明的同时优化访问。当然，更新一个索引意味着另一个双磁盘访问，因为B+树的索引不适合内存。我们知道，如果您以后要读取数据库，那么更改数据库所需要的额外工作是值得的。
下一个令人困惑的问题是:多少应该被编入索引?我们应该索引每一列吗?何时应该将一对列一起索引?我们做的索引越多，读查询就会变得越快。我们做的索引越多，更新的速度就越慢。
我了解到这是一种常见的交易。经常快速阅读意味着慢速写作。
行店vs.列店。我把我虚度的大部分职业生涯都集中在分布式系统和在线事务处理(OLTP)风格的数据库上。我很自然地将高性能更新与今天所谓的row-store。
另一种方法是按列组织数据:取一组行，按列值组织数据。例如，包含加利福尼亚州的每一行只保存单个列的数据。列数据库的查询速度非常快，因为许多具有相同值的逻辑行在物理上彼此非常接近。
但是，更新柱形储存并不容易。通常，更新单独保存在集成的行存储中。查询以一种相对较快的方式检查小行存储，因为它很小。这些查询与更快的列存储的结果相结合，以给出统一的准确答案。新的行存储更新会定期与列存储合并，以生成新的列存储。这可能以级联方式完成，有点像日志结构合并(LSM)树中的合并，将在下一节中介绍。
当插入到列存储(或者实际上是它的附属行存储)时，您将产生一笔稍后需要偿还的债务。这种债务对新数据的重写和集成是一种形式写放大在这里，一个单独的写操作会变成更多的写操作。
LSM树在1996年首次提出。6其思想是跟踪作为事务的键值存储的更改，新值保存在内存中。当事务提交时，最近键-值对的排序集合可以在一个唯一命名的文件中写入磁盘。该文件包含已排序的键-值对以及文件中键的索引。一旦写入磁盘，新提交的更改就不需要保存在内存中。
现在，如果你一直这样做，按键查找值就像我试图在某个随机位置找到某个值时发生的事情一样。对钱包的线性搜索在小公寓里可能是容易的，但当搜索空间在郊区的大房子里变得更大时就不那么容易了。为了减少读的汗水， LSM树投入精力，通过随时重写数据来组织数据。
搜索使阅读文档变得容易得多。它能显著降低出汗。
当从存储引擎新写入一个新文件时，它有一堆键-值对。为了便于查找键，将这些键与先前写入的文件合并。每个LSM树都有某种形式的扇出，其中树的较低级别(键写得较早)跨更多的文件保存。例如，您在级别1上的文件数量可能是在全新的级别0上的10倍。第1级的每个文件所表示的键范围大约是第1级的十分之一，但所表示的更新时间大约是第1级的10倍。类似地，向下移动到第2级会产生100个文件，每个文件的键范围更窄，时间范围更长。
LSM树的深度取决于扇出、每个文件的大小以及树中的键-值对的数量。通常，大多数存储都位于树的最底层。
因此，在这个越来越流行的基本LSM结构中，有各种各样的实现选择。考虑:
- 平合并。当一个新文件被添加到一个关卡时，在循环遍历中选择下一个文件，并将其与下一个关卡中的文件合并。假设你从10个粉丝中选出一个;你会发现下拉文件中的键范围通常涵盖了以下级别中大约10个文件中的键范围。你把11个文件合并在一起，一个文件掉到10个，你得到11个文件。现在，下一层增加了一个文件，所以您重复并再次合并。
- 分层合并。在这种不同但相关的方法中，在进行合并之前，让一堆文件在每个级别上堆叠起来。假设你堆叠了10个文件，然后每层合并。这大大减少了所需的合并量。
水平合并有一个很大的写放大。每次向级别0写入一个新的键值对，在它通过的每个级别上都将被重写10或11次。另一方面，他们会有少量的阅读消耗，因为读者通常在每个关卡只检查一个地方。
分层合并有一个低得多的写放大，但一个大的读流汗。因为在合并之前，新文件会在每一层堆叠起来，合并就会减少，因此写入也会减少。另一方面，阅读必须检查更多的地方，导致更大的阅读流汗。
索引和搜索。在许多方面，搜索是数据库索引的一种变体。在数据库索引中，标识的概念作为行id或主键隐藏在数据库中。在关系系统中，对索引的更新是事务集成的，用户只能看到性能上的差异。
搜索系统在处理文档方面有点不同。大多数搜索系统都异步更新搜索索引后文档的更改发生了。这与某种形式的文档标识交织在一起。3.
搜索使阅读文档变得容易得多。它能显著降低出汗。对文档的异步更新将债务强加给系统，以使它们被索引。创建和合并搜索索引是一项复杂的工作，我认为它是一种写扩展的形式。
要建立索引，必须在语料库中查找最近编写或更新的文档。其中每一个都需要有一个标识符，然后必须处理以定位搜索词(有时称为n-grams;https://en.wikipedia.org/wiki/n-gram)．在典型文档中发现的这些n-gram中的每一个都需要被发送到一个索引器，该索引器覆盖了多个碎片中的一个。因此，文档标识符现在与位于可搜索文档中的每个术语(或n-gram)相关联——所有这一切都是因为用户写了文档或创建了文档!
我在一个互联网规模的搜索引擎工作过几年，知道它们是如何工作的。我仍然对所有这些机器能够跟上所有写放大所涉及的工作感到敬畏。每一个文件都要做很多工作，而且有很多很多的文件。
互联网规模的搜索系统显然提供了优秀的低阅读效率。
大规模的缓存。许多大型互联网系统都有巨大的缓存。以一家大型电子商务零售商的产品目录为例。只要有任何变化，就会用新的产品描述更新大量服务器。这使得非常容易和快速的读取，以交换大量的写操作。
正常化和非正常化。在关系数据库的世界中长大，我被灌输了一种决心，那就是在数据库中包含规范化的数据。努力避免更新异常被认为是极其重要的。为了确保数据库不被错误的更新破坏，执行大量的连接来获得一个答案是一个很小的代价。
越来越多的人认为，这就相当于你把盐洒在肩膀上。是的…我见过别人这么做，但我不确定我是否应该这么做。
大多数系统正变得更加分布式。其中大多数都有包含它们的数据的键-值对，这些数据是分片的。通过将相关数据分组到一对的值中(通常是JSON (JavaScript对象表示法)表示或类似的东西)，很容易获取值，可能是一个字符串，并将其发送到发出请求的远程系统。
如果你是为了规范化这个大的分片系统中的数据，规范化的值不会在同一个分片上。执行分布式连接比执行集中式连接更麻烦。
为了解决这个问题，人们在数据上叠加版本控制。它不是完美的，但它比分布式连接或尝试跨非规范化数据进行大规模更新的挑战性要小。数据库中标准化价值的经典示例是一个包含员工、经理和经理电话号码的非规范化表。4因为经理的电话号码在许多表格中为许多员工复制，所以很难更改它。我越来越多地看到系统以非规范化的结构存储“截至”数据，例如，经理的电话被捕获为“截至”6月1日。
大规模分布式系统给一致性读取的语义带来了很大压力。反过来，这可以被视为写放大和读出汗之间的紧张关系。
结论
我只看了几个例子，其中我们的系统在写和读之间存在权衡。1它在许多环境中都是地方性的。我们看到新兴的系统在观察自己的使用模式时，会对这些权衡进行调整和优化。有趣的东西!
相关文章
在queue.acm.org
不变性改变一切
帕特Helland
https://queue.acm.org/detail.cfm?id=2884038
二义性消除数据库
里克·理查森
https://queue.acm.org/detail.cfm?id=2696453
大数据的病态
亚当·雅各布斯
https://queue.acm.org/detail.cfm?id=1563874
参考文献
1.Athanassoulis, M.， Kester, m.s.， Maas, l.m, Stoica, R.， Idreos, S.， Ailamaki, A.和Callaghan, M.设计访问方法:RUM猜想。在十九届会议记录th扩展数据库技术国际会议(2016)。
2.Dayan, N.和Idreos, S. Dostoevsky:基于lsm树的键值存储的更好的时空权衡，通过自适应去除多余的合并。在《实习生会议录》数据配置管理(2018), 505520。
3.赫兰，p，别的名字都行。Commun。ACM 62(2019年4月)，80。
4.正常化是给娘娘腔的(2007年7月23日);http://bit.ly/30iL7g3
5.罗，C，和凯里，m。j。基于lsm的存储技术。计算调查；arXiv: 1812.07527。
6.O'Neil, P.， Cheng, E.， Gawlick, D.和O'Neil, E.对数结构合并树(lsm -树)。信息学报334(1996)。
数字图书馆是由计算机协会出版的。版权所有©2019 ACM, Inc.
没有找到条目