企业网站手机端,wordpress 登陆可见,网站建设交互效果,网站认证打的钱怎么做分录我们将深入探讨日志结构合并树#xff0c;也称为LSM Tree#xff1a;这是许多高度可扩展的NoSQL分布式键值型数据库的基础数据结构#xff0c;例如Amazon的DynamoDB、Cassandra和ScyllaDB。这些数据库的设计被认为支持比传统关系数据库更高的写入速率。我们将看到LSM Tree如… 我们将深入探讨日志结构合并树也称为LSM Tree这是许多高度可扩展的NoSQL分布式键值型数据库的基础数据结构例如Amazon的DynamoDB、Cassandra和ScyllaDB。这些数据库的设计被认为支持比传统关系数据库更高的写入速率。我们将看到LSM Tree如何使它们能够实现宣称的写入速度并以及如何促进读取。 在开始之前 •首先我们需要一些背景信息。典型的数据库管理系统DBMS由多个组件组成每个组件负责处理数据存储、检索和管理的不同方面。•其中一个组件是存储引擎它负责提供可靠的接口以从/向底层存储设备高效读写数据。•存储引擎的性能在选择数据库时非常重要因为它是最接近正在使用的存储设备的组件。•用于实现存储引擎的两种流行数据结构是B树和LSM树。在本文中我们将覆盖LSM树。 LSM Tree 深度解析 •LSM Tree并不是一个完整的单一数据结构而是结合了多个数据结构利用存储层次结构中不同存储设备的响应时间。•由于是追加写入它提供了高写入速率同时通过在RAM中维护的索引仍然提供低成本的读取。•与基于B树的存储引擎相比它执行原地更新但在LSM Tree中没有原地更新这有助于避免随机I/O。在我们深入研究之前让我们详细讨论在写入密集工作负载中使用基于B树的数据库存储引擎的缺点。•大多数传统的关系型/SQL数据库使用基于B树的存储引擎。在这些数据库中每次写入都必须执行不仅是记录的请求写入还必须执行对B树不变式的任何所需的元数据更新这涉及在B树结构中移动/拆分/合并节点。 解剖LSM Tree •LSM Trees凸显了磁盘上的随机I/O存在大量写入开销的问题而顺序写入则更快因为磁盘写入头紧挨着上一个记录的位置且旋转和寻道延迟最小。•“Log-structured”这个术语意味着数据结构像追加日志一样被组织。•“merge”这个术语指的是用于管理结构中数据的算法。其名称中的“tree”一词来自于数据被组织成多个级别类似于典型计算机中存储层次结构中的设备其中顶层设备包含较小的数据子集访问速度更快而较低级别包含较大的数据段访问速度较慢。•在最基本的设置中LSM Tree由两个数据结构组成充分利用RAM和持久磁盘的优势LSM树被优化用于快速写入。 1. Memtable •LSM树的工作方式不同。写入在内存中按到达的顺序进行批处理存储在称为Mem table的结构中。Mem table按对象-键对进行排序通常实现为平衡二叉树。 •当Mem table达到一定大小时它将被刷新到磁盘作为不可变的有序字符串表。一个SS table以有序序列存储键值对。这些写入都是顺序I/O在任何存储介质上都很快。 2. SS Tables •新的SS表成为LSM树的最新段。随着更多数据的到来越来越多的这些不可变SS表被创建并添加到LSM树中每个都代表传入更改的小时间段。 •由于SS表是不可变的对现有对象键的更新不会覆盖旧的SS表。相反将在最新的SS表中添加新条目这将取代旧的SS表中对象键的任何条目。 LSM Tree上的操作 1. 删除 •删除对象需要特殊处理因为我们无法标记SS表中的任何内容为已删除。•为执行删除操作它会在对象键的最新SS表上添加一个称为墓碑的标记。当我们在读取时遇到墓碑时我们知道该对象已被删除。是的删除会占用额外的空间。 2. 读取 •为了响应读取请求我们首先尝试在Mem table中查找键然后在LSM树中的最新访问表中查找然后在下一个SS表中查找依此类推。由于SS表是有序的查找可以有效进行。 •SS表的积累产生了两个问题。随着SS表数量的增加查找键将需要越来越长的时间。随着SS表的累积随着键的更新和墓碑的添加旧条目变得越来越多。这些会占用宝贵的磁盘空间。•为了解决这些问题后台运行定期的合并和压缩过程以合并SS表并丢弃过时或已删除的值。这可以回收磁盘空间并限制读取时必须查找的SS表数量。由于SS表是有序的因此这个合并和压缩过程是简单而高效的。该方法类似于归并排序算法的合并阶段。 3. 写入 •LSM树会在内存中缓冲传入的写入。当缓冲区填满时我们对其进行排序并将其刷新到磁盘作为不可变的SS表。•随着更多的缓冲区刷新到磁盘这会为读取创建问题因为每个读取都必须搜索这些SS表以执行查找。•为了限制每个读取时必须搜索的SS表数量LSM树会在后台合并SS表并进行压缩。 4. 压缩策略 •让我们更仔细地看看压缩过程。当合并SS表时它们会被组织成级别。这是LSM树名称中“树”的部分发挥作用的地方。 •有不同的策略来确定何时以及如何合并和压缩SS表。有两种广泛的策略大小分层压缩和级别压缩。大小分层压缩针对写入吞吐量进行了优化而级别压缩则更多地针对读取进行了优化。•压缩可以使SS表数量保持在可管理的水平。SS表被组织成级别每个级别的SS表随着来自上一级别的SS表的出现而呈指数增长。•压缩会消耗大量I/O。错误调整的压缩可能会使系统饿死并减慢读取和写入速度。 LSM Tree 的增强 最后让我们了解一些生产系统中LSM树的标准优化。 •为了查找键它会在每个级别的SS表上执行搜索。尽管在排序数据上搜索很快但在所有这些SS表上进行搜索会消耗大量I/O。•许多系统在内存中保留一个摘要表其中包含每个级别的每个磁盘块的最小/最大范围。这允许系统跳过那些键不在范围内的磁盘块上的搜索从而节省大量随机I/O。•另一个可能昂贵的问题是查找不存在的键。这将需要查找所有级别的所有合格块。大多数系统在每个级别上保留了一个Bloom过滤器。•Bloom过滤器是一种空间高效的数据结构如果键不存在则返回确定的“不存在”如果键可能存在则返回“可能存在”。这允许系统跳过一个级别如果键在那里不存在从而大大减少了需要的随机I/O数量。 LSM Tree 的缺点 •LSM树的主要缺点是压缩的成本它影响读取和写入性能。由于涉及数据的压缩/解压缩、复制和比较压缩是LSM树中资源占用最高的阶段。•所选的压缩策略必须试图最小化读取放大、写入放大和空间放大。•LSM树的另一个缺点是执行读取在最坏情况下会变慢。由于是追加方式读取必须在最低级别的SSTable中进行搜索。这涉及到寻找的文件I/O这会导致读取变慢。
