首页 云计算 服务器 大数据 存储 IT 安全 物联网 软件

存储

存储频道旗下栏目:

支撑现代分布式存储系统的算法

来源:今日头条   发布时间:2019-05-13
摘要:随着应用程序处理的数据量不断增长,扩展存储变得愈发具有挑战性。每个数据库系统都有自己的方案。为了从这些方案中做出正确的选择,了解它们是至关重要的。 每个应用程序在读写负载平衡、一致性、延迟和访问模式方面各不相同。熟悉数据库和底层存储能帮助

随着应用程序处理的数据量不断增长,扩展存储变得愈发具有挑战性。每个数据库系统都有自己的方案。为了从这些方案中做出正确的选择,了解它们是至关重要的。

每个应用程序在读写负载平衡、一致性、延迟和访问模式方面各不相同。熟悉数据库和底层存储能帮助你进行架构决策、解释系统行为、排除故障以及根据具体情况调优。

优化一个系统不可能做到面面俱到。我们当然希望有一个数据结构既能保证最佳的读写性能,又不需要任何存储开销,但显然,这是不存在的。

本文深入讨论了大多数现代数据库中使用的两种存储系统设计 —— 读优化 B-Tree [1] 和写优化 LSM(log-structured merge)-Tree [5] —— 并描述了它们的用例和优缺权衡。

B-Tree

B-Tree 是一种流行的读优化索引数据结构,是二叉树的泛化。它有许多变种,并且被用于多种数据库(包括 MySQL InnoDB [4]、PostgreSQL [7])甚至文件系统(HFS+ [8]、HTrees ext4 [9])。B-Tree 中的 B 代表原始数据结构的作者 Bayer,或是他当时就职的公司 Boeing。

在搜索二叉树中,每个节点都有两个孩子(称为左右孩子)。左子树的节点值小于当前节点值,右子树反之。为了保持树的深度最小,搜索二叉树必须是平衡的:当随机顺序的值被添加到树中时,如果不加调整,终会导致树的倾斜。

一种平衡二叉树的方法是所谓的旋转:重新排列节点,将较深子树的父节点向下推到其子节点下方,并将该子节点拉上来,将其放在原父节点的位置。图 1 是平衡二叉树中的旋转示例。在左侧添加节点 2 后,二叉树失去平衡。为了使该树平衡,将其以节点 3 为轴旋转(树围绕它旋转)。然后节点 5(旋转前是根节点和节点 3 的父节点)成为其子节点。旋转完成后,左侧子树的深度减少 1,右侧子树的深度增加 1。树的最大深度已经减小。

二叉树是最有用的内存数据结构。然而由于平衡(保持所有子树的深度最小)和低出度(每个节点最多两个子节点),它们在磁盘上水土不服。B-Tree 允许每个节点存储两个以上的指针,并通过将节点大小与页面大小(例如,4 KB)进行匹配来与块设备协同工作。今天的一些实现将使用更大的节点大小,跨越多个页面。

B-Tree 有以下几个性质:

• 有序。这允许顺序扫描并简化查找。

• 自平衡。在插入和删除时不需要平衡树:当 B-Tree 节点已满时,它被分成两部分,并且当相邻节点的利用率低于某个阈值时,合并这两个节点。这也意味着各叶子节点与根节点的距离相等,并且在查找过程中定位的步数是相同的。

• 对数级查找时间复杂度。查找时间是非常重要的,这使得 B-Tree 成为数据库索引的理想选择。

• 易变。插入、更新、删除(包括因此导致的拆分和合并)过程在磁盘上进行。为了使就地更新成为可能,需要一定的空间开销。B-Tree 可以作为聚集索引,实际数据存储在叶子节点上,也可以作为非聚集索引,称为一个堆文件。

本文讨论的 B+Tree [3] 是一种经常用于数据库存储的 B-Tree 现代变种。B+Tree 与原始 B-Tree [1] 的不同之处在于:(1)它采用额外链接的叶节点存储值;(2)值不能存储在内部节点上。

剖析 B-Tree

我们先来仔细看看 B-Tree 的结构,如图 2 所示。B-Tree 的节点有几种类型:根节点,内部节点和叶子节点。根节点(顶部)是没有双亲的节点(即,它不是任何节点的子节点)。内部节点(中间)有双亲和孩子节点;他们将根节点和叶子节点连接起来。叶子节点(底部)持有数据并且没有孩子节点。图 2 描绘了分支因子为 4(4 个指针,内部节点中有 3 个键,叶上有 4 个键/值对)的 B-Tree。

B-Tree 的特性如下:

• 分支因子 —— 指向子节点的指针数(N)。除指针外,根节点和内部节点还持有 N-1 个键。

• 利用率 —— 节点当前持有的指向子节点的指针数量与可用最大值之比。例如,若某树分支因子是 N,且其中某节点当前持有 N/2 个指针,则该节点利用率为 50%。

• 高度 —— B-Tree 的数量级,表示在查找过程中必须经过多少指针。

树中的每个非叶节点最多可持有 N 个键(索引条目),这些键将树分为 N+1 个子树,这些子树可以通过相应的指针定位。项 Ki 中的指针 i 指向某子树,该子树中包含所有 Ki-1 <= K目标 < Ki(其中 K 是一组键)的索引项。首尾指针是特殊的,它们指向的子树中所有的项都小于等于最左子节点的 K0 或大于最右子节点的 KN-1。叶子节点同时持有其同级前后节点的指针,形成兄弟节点间的双向链表。所有节点中的键总是有序的。

查找

进行查找时,将从根节点开始搜索,并经过内部节点递归向下到叶子节点层。在每层中,通过指向子节点的指针将搜索范围缩小到某子树(包含搜索目标值的子树)。图 3 展示了 B-Tree 的一次从根到叶的搜索过程,指针在两个键之间,其中一个大于(或等于)搜索目标,另一个小于搜索目标。进行点查询时,搜索将在定位到叶子节点后完成。进行范围扫描时,遍历所找到的叶子节点的键和值,然后遍历范围内的兄弟叶子节点。


在复杂度方面,B-Tree 保证查询的时间复杂度为 log(n),因为查找一个节点中的键使用二分查找,如图 4 所示。二进制搜索可以通俗的解释为在字典中查找以某字母开头的单词,字典中所有单词都按字母顺序排序。首先你翻开正好在字典中间的一页。如果要查找的单词字母顺序小于(在前面)当前页,你继续在字典的左半边查找;否则就继续在右半边查找。你继续像这样将剩余的页码范围分为一半,选择一边,直到找到期望的字母。每一步都将搜索范围减半,因此查找的时间复杂度为对数级。 B-Tree 节点上的键是有序的,且使用二分查找算法进行匹配,因此 B-Tree 的搜索复杂度是对数级的。这也说明了保持树的高利用率和统一访问的重要性。


插入、更新、删除

进行插入时,第一步是定位目标叶子节点。此过程使用前序搜索算法。在定位目标叶子节点后,键和值将被添加至该节点。如果该节点没有足够的可用空间,这种情况称为溢出,则将叶子节点分割成两部分。这是通过分配一个新的叶子节点,将一半元素移动到新节点并将一个指向这个新节点的指针添加到父节点来完成的。如果父节点没有足够的空间,则也会在父节点上进行分割。操作一直持续到根节点为止。当根节点溢出时,其内容在新分配的节点之间被分割,根节点本身被覆盖以避免重定位。这也意味着树(及其高度)总是通过分裂根节点而增长。

LSM-Tree

结构化日志合并树是一个不可变的基于磁盘的写优化数据结构。它适用于写入比查询操作更频繁的场景。LSM-Tree 已经获得了更多的关注,因为它可以避免随机插入,更新和删除。

剖析 LSM-Tree