log-structed结构

📌

Log-Structured 结构 - mzjnumber1 - 博客园

Log-structed结构介绍

Log-Structured 结构，有时候也会被称作是 Append-only Sequence of Data，因为所有的写操作都会不停地添加进这个数据结构中，而不会更新原来已有的值，这也是 Log-Structured 结构的一大特性。

比如说，Google 的三驾马车之一，Bigtable 文件系统的底层存储数据结构采用的就是Log-Structured结构， MongoDB 和 HBase 这类的 NoSQL 数据库，它们的底层存储数据结构其实也是 Log-Structured 结构。

一个常见的问题应用：

假设一个视频网站需要一个统计视频观看次数的功能，如果设计的话，会采用哪种数据结构呢？

可以运用哈希表这个数据结构，以视频的 URL 作为键、观看次数作为值，保存在哈希表里面。所有保存在哈希表里面的初始值都为 0，表示并无任何人观看，而每次有人观看了一个视频之后，就将这个视频所对应的值取出然后加 1。刚开始的时候，这个设计思路可能运行得很好。可当用户量增大了之后，会发现在更新哈希表的时候必须要加锁，不然的话，大量的这种并行 +1 操作可能会覆盖掉各自的值。

那有没有方法可以不用顾及写操作的高并发问题，同时也可以最终获得一个准确的结果呢？答案就是使用 Log-Structured 结构。

上面是 Log-Structured 结构的本质了（写操作不更新而添加到后面）

（1）一个数组不可能在内存中无限地增长下去,如何处理呢？

（2）如果每次想要知道结果，就必须遍历一遍这样的数组，时间复杂度会非常高，那该怎么优化呢？

（3）平衡树是如何被应用在里面的呢？

Log-Structured 结构的优化

首先，可以定义一个大小为 N 的固定数组，我们称它为 Segment，一个 Segment 最多可以存储 N 个数据，

当有第 N+1 个数据需要写入 Log-Structured 结构的时候，我们会创建一个新的 Segment，然后将 N+1 个数据写入到新的 Segment 中。以下图为示，定义一个 Segment 的大小为 16，当 Segment 1 写满了 16 个数据之后，会将新的数据写入到 Segment 2 里。

Log-Structured 结构还是一直在往内存里添加数据，并没有解决最终会消耗完内存的问题。这时候就到Compaction 大显身手的时候了，在当 Segment 到达一定数量的时候，compaction 会通过后台的线程，把不同的 Segments 合并在一起。假设我们定义当 Segment 的数量到达两个的时候，后台线程就会执行 Compaction 来合并结果。

在 Compaction 完成了之后，对于结果的读取就可以从 Compacted Segment 里面读取了。因为这时候所有的结果已经存放在 Compacted Segment 里面了，所以就可以删除 Segment 1 和 Segment 2 来腾出内存空间了。

整个 Compaction 的过程会不断地递归进行下去，当 Compacted Segment 满了以后，后台线程又可以对 Compacted Segment 进行 Compaction 操作，再次合并所有结果。

Compaction的位置和时机：

在Log-Structured 存储系统中，Compaction的核心操作是合并多个 **SSTable(Sorted String Table)**文件，这个过程确实需要读取多个 SSTable 的数据，并进行排序、去重和合并。然而，是否将所有数据完全加载到内存中，以及如何高效地执行合并操作，取决于系统的设计和优化策略。以下是详细的说明。

1. Compaction 的基本流程

（1）选择需要合并的 SSTable：根据 Compaction 策略（如层级 Compaction 或分层 Compaction），选择需要合并的 SSTable 文件。

（2）读取 SSTable 数据：从磁盘读取选中的 SSTable 文件。

（3）合并数据：将多个 SSTable 的数据按键排序、去重（保留最新的值）并合并。

（4）写入新的 SSTable：将合并后的数据写入新的 SSTable 文件。

（5）清理旧的 SSTable：删除旧的 SSTable 文件，释放磁盘空间。

2. 数据读取和合并的方式

在 Compaction 过程中，是否需要将所有数据加载到内存中，取决于系统的设计和优化策略。

（1）全内存合并

• 过程：将所有需要合并的 SSTable 文件完全加载到内存中，然后在内存中进行排序、去重和合并。

（2）外部排序合并（External Merge Sort）

• 过程：

1. 将每个 SSTable 文件的数据分块读取到内存中。
2. 对每个块进行排序（如果未排序）。
3. 使用多路归并（Multiway Merge）算法，将多个有序块合并成一个更大的有序文件。
4. 将合并后的数据写入新的 SSTable 文件。

• 优点：

• 内存占用低，适合大规模数据场景。

• 可以处理远大于内存容量的数据。

• 缺点：

• 实现复杂度较高。

• 由于涉及磁盘 I/O，速度比全内存合并慢。

memtable

memtable内存中的数据结构(表)，用于临时存储新写入的数据。

memtable Memory Table，即内存表，它的作用是高效地缓存新写入的数据，并在达到一定大小后将数据写入磁盘，形成有序的文件（SSTable）。

1. memtable 的作用

（1）临时存储新写入的数据：所有新写入的数据首先会被插入到 memtable 中。

（2）保持数据有序：memtable 通常是一个有序的数据结构(如平衡二叉查找树、跳表等)，数据在插入时会自动按键排序。由于 memtable 位于内存中，读写速度非常快。

（3）为后续写入磁盘做准备：当 memtable 达到一定大小时，它会被冻结并写入磁盘，形成有序的 SSTable。

memtable 通常使用以下数据结构实现：

• 平衡二叉查找树:红黑树,AVL 树等。这些树结构可以保证数据的有序性，并且插入、删除和查找操作的时间复杂度为 O(log n)。
• 跳表(SkipList):跳表是一种概率性的有序数据结构，它的性能与平衡树类似，但实现更简单。
• 其他有序结构:如 B 树、B+ 树等。

memtable 在 LSM 树中的典型工作流程：

1. 写入数据

当新数据写入时，首先会被插入到 memtable 中，memtable 会将其按键排序存储。

1. 读取数据

当需要读取数据时，系统会先检查 memtable。如果数据在 memtable 中，则直接返回。如果 memtable 中没有找到数据，则会继续检查磁盘上的 SSTable。

1. memtable 写满

当 memtable 的大小达到阈值时，它会被冻结(变为不可变)，并创建一个新的 memtable 来接收新写入的数据。被冻结的 memtable 会被写入磁盘，形成一个有序的 SSTable。

1. Compaction

当磁盘上有多个 SSTable 时，系统会定期进行 Compaction，将多个 SSTable 合并成一个更大的 SSTable。Compaction 过程中会去除重复的键和删除标记，从而优化存储空间和读取性能。

在memtable中插入重复键的元素时，常见的处理方式包括:

1.覆盖旧值(默认行为)。2.保留历史记录(多版本控制)。3.自定义冲突解决策略。

SSTable

SSTable（Sorted String Table）数据结构是在 Log-Structured 结构的基础上，多加了一条规则，就是所有保存在 Log-Structured 结构里的数据都是键值对，并且键必须是字符串，在经过了 Compaction 操作之后，所有的 Compacted Segment 里保存的键值对都必须按照字符排序。

当我们要查找一个单词出现的次数时，可以遍历所有的 Compacted Segment，因为所有数据都是按照字符串排好序的，如果当遍历到的字符串已经大于我们要找的字符串时，就表示并没有出现过这个单词。