元数据
精通LevelDB
- 书名： 精通LevelDB
- 作者： 廖环宇 张仕华
- 简介： 本书详细剖析LevelDB从使用到设计实现的方方面面，读后可了解谷歌Bigtable数据库的设计精髓，逻辑上可分为两部分。第一部分着重讲解LevelDB的基础知识，主要内容如下。1）基本数据结构，这是理解后续内容的基础，也可以加深对比较器、迭代器等常见数据结构的理解。2）基本使用，如数据库打开、关闭以及基本的读写操作。3）总体架构与设计思想，读后可掌握LevelDB的整体情况与设计思路。4）公用基础类，读后可了解LevelDB中如何实现数值编码、内存管理以及文件读取等。第二部分着重讲解LevelDB各模块的实现细节，主要内容如下。1）Log模块的实现细节，以及如何通过Log进行崩溃恢复，并生成一个MemTable文件。2）MemTable模块的实现细节，以及MemTable超过内存阈值时如何生成一个SSTable文件。3）SSTable模块的实现细节。4）Compaction原理与多版本管理。
- 出版时间： 2021-11-01 00:00:00
- ISBN： 9787111693260
- 分类： 计算机-编程设计
- 出版社： 机械工业出版社
- PC地址：https://weread.qq.com/web/reader/9f932e70727ac58e9f9d8cc
高亮划线
内容简介
📌 Bigtable ⏱ 2022-01-09 10:38:37
1.1 键-值数据库的提出与价值
📌 键-值数据库主要用于存取、管理关联性的数组。 ⏱ 2022-01-09 10:47:15
📌 NoSQL运动 ⏱ 2022-01-09 10:47:51
1.2 LevelDB的诞生过程
📌 LevelDB就是一种为分布式而生的键-值数据库。 ⏱ 2022-01-09 10:48:12
📌 为了能将Bigtable的实现原理与技术细节分享给大众开发者，于2011年基于Bigtable的基本原理，采用C++开发了一个高性能的键-值数据库——LevelDB。 ⏱ 2022-01-09 10:48:42
📌 因此LevelDB可看作Bigtable的简化版或单机版。 ⏱ 2022-01-09 10:48:47
1.3 LevelDB的特性
📌 LevelDB的优点 ⏱ 2022-01-09 10:49:46
📌 LevelDB的缺点 ⏱ 2022-01-09 10:49:49
1.5 LevelDB的衍生产品
📌 RocksDB（https://github.com/facebook/rocksdb）是基于LevelDB开发的，并保留、继承了LevelDB原有的基本功能，也是一个嵌入式的键-值数据存储库。 ⏱ 2022-01-09 10:50:55
📌 针对SSD硬盘的数据存储产品，从而有了后面的RocksDB。RocksDB采用嵌入式的库模式，充分发挥了SSD的性能。 ⏱ 2022-01-09 10:51:05
📌 针对SSD硬盘进行优化，支持更多的IOPS（I/O Operation per Second），并改进数据压缩，减少数据写入，尽可能延长SSD的使用寿命。 ⏱ 2022-01-09 10:51:56
📌 针对多CPU、多核环境进行优化 ⏱ 2022-01-09 10:52:02
📌 MVCC，并将数据库的只读与读写操作分开，减少了锁的使用，从而更适合、进行高并发操作。 ⏱ 2022-01-09 10:52:17
📌 数据合并、多种压缩算法、按范围查询，以及一些管理统计维护工具。 ⏱ 2022-01-09 10:52:25
2.1 string与Slice
📌 Slice是LevelDB中的一种基本的、以字节为基础的数据存储单元，既可以存储key，也可以存储数据（data）。Slice对数据字节的大小没有限制，其内部采用一个const char*的常量指针存储数据，具有两个接口data()和size()，分别返回其表示的数据及数据的长度。 ⏱ 2022-01-09 10:53:44
2.5 系统参数
📌 参数Options主要在DB::Open方法中进行函数的参数传递。 ⏱ 2022-01-09 12:04:19
📌 在实际调用时，客户端需要保证排序时所使用的comparator与数据库进行Open操作时传入的comparator名字相同。 ⏱ 2022-01-09 12:04:58
📌 内存中最多同时保存2个写缓存。此外，写缓存越大，则DB在下次打开过程中恢复的时间越长。 ⏱ 2022-01-09 12:06:33
📌 Snappy是一种轻量且快速的压缩算法。 ⏱ 2022-01-09 12:07:57
3.2 创建（打开）与关闭数据库
📌 针对函数参数的顺序，一般输入参数在前，输出参数在后。 ⏱ 2022-01-09 12:25:09
3.3 数据的读、写与删除
📌 LevelDB中的删除操作并不是直接将数据从磁盘中清除，而是在对应位置插入一个key的删除标志，然后在后续的Compaction（见第9章）过程中才最终去除这条key-value记录。 ⏱ 2022-01-09 12:26:18
3.4 数据批量操作
📌 这种批量操作方法主要具有两个作用：一是提供了一种原子性的批量操作方法；二是提高了整体的数据操作速度。 ⏱ 2022-01-10 10:49:10
3.5 迭代器与key的查询操作
📌 接口返回的Iterator对象并不能直接使用，只有在调用相应的Seek方法之后才能进行对应的迭代操作。 ⏱ 2022-01-12 00:33:19
3.6 性能优化方案
📌 根据排序结果，相邻的key所对应的数据记录一般均会存储在同一个块中。正是由于这一特性，用户针对自身的应用场景需要充分考虑如何优化key的命名设计，从而最大限度地提升整体的读取性能。 ⏱ 2022-01-12 00:37:24
4.1 键-值存储系统的基本要求
📌 LevelDB是基于LSM树（Log-Strucrued Merge Tree，日志结构合并树）进行存储。 ⏱ 2022-01-12 00:38:51
📌 存储系统中用于管理内存的算法与技术。一个优秀的内存管理模块，对于发挥键-值存储系统的性能具有重要的影响。 ⏱ 2022-01-12 00:39:00
4.2 Bigtable与LevelDB
📌 LSM树是一种基于磁盘的、支持频繁大量数据写操作的数据结构。 ⏱ 2022-01-12 08:26:08
4.3 主要模块功能介绍
📌 一般而言，在常规的物理硬盘存储介质上，顺序写比随机写速度要快，而LSM树正是充分利用了这一物理特性，从而实现对频繁、大量数据写操作的支持。 ⏱ 2022-01-12 08:28:23
📌 当需要插入一条新的数据记录时，首先在Log文件末尾顺序添加一条数据插入的记录，然后将这个新的数据添加到驻留在内存的C0树中，当C0树的数据大小达到某个阈值时，则会自动将数据迁移、保留在磁盘中的C1树 ⏱ 2022-01-12 08:29:16
📌 对于数据读过程，LSM树将首先从C0树中进行索引查询，如果不存在，则转向C1中继续进行查询，直至找到最终的数据记录。 ⏱ 2022-01-12 08:29:29
4.4 主要操作流程分析
📌 Get函数在查询读取数据时，依次从MemTable、Immutable MemTable以及当前保存的SSTable文件中进行查找。 ⏱ 2022-01-12 10:30:14
📌 在内部获取机制中还有一个时间序列尺度的标识，用于决定究竟获取该key哪一个时间序列的数值，而这个时间序列就是SequenceNumber。 ⏱ 2022-01-12 10:30:32
📌 SequenceNumber的主要作用是对DB的整个存储空间进行时间刻度上的序列备份，即要从DB中获取某一个数据，不仅需要其对应的键key，而且需要其对应的时间序列号。 ⏱ 2022-01-12 10:30:54
📌 对数据库进行写操作会改变序列号，每进行一次写操作，则序列号加1 ⏱ 2022-01-12 10:31:08
📌 某一个指针对象在实例化后，调用Ref()则引用计数加1，调用Unref()则引用计数减1，如果该对象引用计数为0，则说明当前没有用户需要该对象，从而可以触发指针对象的删除与回收。 ⏱ 2022-01-12 10:34:30
📌 Put函数其实也是将单条数据的操作变更为一个批量操作，然后调用Write函数进行实现。 ⏱ 2022-01-12 10:35:12
📌 LevelDB中的快照并不是将所有数据进行完整的物理空间备份，而是保存每一个快照备份记录创建时刻的序列号。 ⏱ 2022-01-12 12:03:48
📌 而LookupKey主要由两部分构成：用户key与对应的序列号，而LookupKey中的序列号来自Get方法中的选项参数snapshot。 ⏱ 2022-01-12 12:05:00
5.1 LevelDB跨平台编程
📌 Signal()一般只唤醒其中某一个阻塞的线程，而SignalAll()会唤醒所有正在等待的线程。 ⏱ 2022-01-12 12:08:22
📌 正是由于采用这两个内存屏障进行读写的方法，从而保证了程序在数据读写时上下文逻辑的正确性。 ⏱ 2022-01-12 12:09:37
📌 pthread_cond_wait有可能被意外唤醒，而如果此时并没有满足真正的唤醒条件，则该程序将不会按照我们预定的思路进行执行。发生意外唤醒的原因有可能来自程序本身的缺陷，也有可能来自虚假唤醒（spurious wakeup）。 ⏱ 2022-01-12 18:23:46
📌 整体而言有两种方法：一是直接采用硬件平台提供的内存屏障，结合原始的指针类型进行实现；二是采用高版本的GCC编译环境所支持的原子类型，以实现原子指针的功能。 ⏱ 2022-01-12 18:24:31
📌 内存屏障可以避免程序在编译过程中或运行过程中因读写操作乱序所带来的一系列问题。 ⏱ 2022-01-12 18:25:40
📌 NoBarrier_Load与NoBarrier_Store两个方法主要就是void指针的直接读取或写入，而Acquire_Load方法在对result赋值后以及最终return返回前调用了MemoryBarrier()方法。而Release_Store方法则是在对void指针rep_进行写入前调用了MemoryBarrier()方法。 ⏱ 2022-01-17 11:13:30
📌 std::memory_order，相当于定义了6种应用于原子变量的内存序 ⏱ 2022-01-17 11:14:45
5.2 文件操作
📌 无论是Read方法还是Skip方法，对于多线程环境而言均不是线程安全的访问方法，需要开发者在调用过程中采用外部手段进行线程同步操作。 ⏱ 2022-01-17 11:29:38
📌 Read方法底层主要通过调用fread_unlocked来实现。在主流的Linux与UNIX平台中，并没有fread_unlocked函数，而这里的fread_unlocked只是一个宏定义，实际上真正执行的是fread。fread是C标准库中的函数， ⏱ 2022-01-17 12:16:17
📌 fread函数并不是一种线程安全的文件读方法，在读文件时不会锁住文件来对其独占，因而外部的并发访问需要自行提供同步机制。 ⏱ 2022-01-17 12:16:46
📌 文件写操作，本质上是将数据保存到硬盘的过程。 ⏱ 2022-01-17 16:52:22
📌 一般会在应用层与系统层间设立一定的缓冲区，从而尽可能地减少I/O次数，提高写入速度。然而采用缓冲区的机制也有一个局限，当数据只是存储在缓冲区，而系统还没有来得及对这些缓冲数据进行保存到磁盘的处理，而这时恰恰系统掉电，那么缓冲区的数据就无法保存到磁盘，从而造成数据丢失。 ⏱ 2022-01-17 16:52:38
5.3 Env操作环境抽象接口
📌 Env是一个抽象接口类，用纯虚函数的形式定义了一些与平台操作的相关接口，如文件系统、多线程、时间操作等。 ⏱ 2022-01-17 17:00:24
📌 Schedule函数是将某个函数调度到后台线程中执行，后台线程长期存在，并不会随着函数执行完毕而销毁，而如果没有需要执行的函数，后台线程处于等待状态；StartThread函数则是启动一个新的线程，并且在新的线程中执行指定的函数操作，当指定的函数执行完毕后，该线程也将被销毁。 ⏱ 2022-01-17 17:26:54
📌 首先创建了一个StarThreadState的结构体对象，并将StartThread函数的两个参数：函数指针function与函数参数arg封装到StarThreadState结构体对象state中。然后通过pthread_create命令启动一个新的线程，执行StartThreadWrapper函数。 ⏱ 2022-01-17 17:27:46
📌 后台进程bgthread始终会运行BGThread函数，该函数是一个死循环，采用条件变量等待相关的信号，以从非空队列中获取队首元素，并执行BGQueue对象所封装的具体任务。 ⏱ 2022-01-17 17:28:22
📌 NowMicros()用于获取当前时刻的时间，返回从1970年1月1日起到当前时间的绝对值，以μs数表示 ⏱ 2022-01-17 17:29:17
📌 基于EnvWrapper的派生类，易于实现用户在某一个Env派生类的基础上改写其中一部分接口的需求。 ⏱ 2022-01-17 17:37:24
📌 InMemoryEnv设计了一种实现全内存读写操作的解决方案 ⏱ 2022-01-17 17:39:03
📌 FileSystem主要由string的字符串与FileState的对象构成。字符串作为文件名 ⏱ 2022-01-17 17:39:15
📌 全内存的读写机制是FileState实现的关键。 ⏱ 2022-01-17 17:40:14
5.4 int数值编码
📌 LevelDB为了减少数值型内容对内存空间的占用，分别针对不同的需求定义了两种编码方式：一种是定长的编码，另一种是变化编码。 ⏱ 2022-01-17 18:01:43
📌 在直接存储的过程中，主要考虑的是数据字节的存放顺序。 ⏱ 2022-01-17 18:03:06
📌 LevelDB为了便于操作，编码的数据统一采用小端模式，并存放到对应的字符串中，即数据低位存在内存低地址，数据高位存在内存高地址。 ⏱ 2022-01-17 18:03:17
📌 varint是一种将整数用1个或多个字节表示的一种序列化方法，其编码后的字节序也采用小端模式，即低位数据在前，高位数据在后。 ⏱ 2022-01-17 18:04:28
📌 varint将实际的一个字节分成了两个部分，最高位定义为MSB（most significant bit），后续低7位表示实际数据 ⏱ 2022-01-17 18:04:38
5.5 内存管理
📌 Arena主要表示一段较大且连续的内存空间，或称之为内存池。 ⏱ 2022-01-17 18:06:09
📌 内存申请本身就需要占用一定的资源，消耗空间与时间。而Arena内存池的基本思路就是预先申请一大块内存，然后多次分配给不同的对象，从而减少malloc或new的调用次数。 ⏱ 2022-01-17 18:06:20
📌 C++中的STL就提供了一套复杂的内存池机制。 ⏱ 2022-01-17 21:27:07
📌 Arena内存池主要是提供给MemTable使用的。 ⏱ 2022-01-17 21:27:16
📌 ，AllocateAligned不仅要分配指定字节大小的内存，还保证了内存首地址满足内存对齐的相关原则。 ⏱ 2022-01-17 18:12:50
📌 Arena的内存申请与销毁机制，即在需要使用时申请，当应用退出时一次性释放。 ⏱ 2022-01-17 21:29:27
📌 第一种情况Allocate函数直接返回alloc_ptr_指向的地址空间，然后对alloc_ptr_与alloc_bytes_remaining_进行更新。第二种情况Allocate函数则需要调用AllocateFallback方法进行实现。 ⏱ 2022-01-18 12:13:35
📌 这是因为在申请完Block后，Block的首地址需要存储在一个vector<char*>的动态数组blocks_中，因而需要额外占用一个指针的空间。 ⏱ 2022-01-18 12:24:29
📌 LevelDB使用TCMalloc进行优化。TCMalloc（Thread-Caching Malloc）是google-perftool中一个管理堆内存的内存分配器工具，可以降低内存频繁分配与释放所造成的性能损失，并有效控制内存碎片。 ⏱ 2022-01-18 12:24:54
第6章 Log模块
📌 预写日志（Write-Ahead Log，WAL），又称重做日志。这是一个追加修改、顺序写入磁盘的文件。当宕机或者程序崩溃时WAL能够保证写入成功的数据不会丢失。 ⏱ 2022-01-18 12:25:42
6.2 Log文件读写操作
📌 而一个记录的头部就需要7个字节，因此再有新记录插入时，则不能继续使用该块。此时会将该块剩余的6字节置为\x00\x00\x00\x00\x00\x00，即图6-4所示的尾部（trailer）。 ⏱ 2022-01-19 08:55:58
📌 ReadRecord读取一条记录到fragment变量中，并且返回该条记录的类型，如果是一条完整的记录则直接赋值给record并返回true；否则会先将数据临时存储到scratch变量，并且将中间记录追加到scratch变量，直到读取出类型为kLastType的记录并且追加到scratch，此时再将scratch的值赋给record，并返回true。 ⏱ 2022-02-13 10:31:24
6.3 记录Log文件
📌 LevelDB每次进行写操作时，都需要调用AddRecord方法向Log文件写入此次增加的键-值对，并且根据WriteOptions中sync的值（布尔型）来决定是否需要进行刷新磁盘操作（Linux环境下执行的是fsync()函数）。 ⏱ 2022-02-13 10:42:55
8.1 SSTable文件格式
📌 SSTable文件由一个个块组成，块中可以保存数据、数据索引、元数据或者元数据索引。 ⏱ 2022-02-13 22:59:49
📌 SSTable文件整体分为4个部分：数据区域（保存具体的键-值对数据），元数据区域（保存元数据，例如布隆过滤器），索引区域（分为数据索引和元数据索引），尾部（总大小为48个字节）。 ⏱ 2022-02-13 22:59:59
📌 通过这两个BlockHandle可以分别定位数据索引区域（indexblock）以及元数据索引区域（meta index block） ⏱ 2022-02-13 23:00:32
📌 因为BlockHandle的成员变量使用可变长度编码，每个BlockHandle最多占用20字节 ⏱ 2022-02-13 23:00:28
📌 BlockHandle只需要关注其中的两个成员变量offset_和size_，分别表示数据在SSTable中的偏移位置以及大小，通过BlockHandle可以指定一块数据区域。offset_和size_会分别编码为可变长度的64位整型，因此每个BlockHandle最多占用20字节。 ⏱ 2022-02-14 08:33:32
📌 重启点 ⏱ 2022-02-14 08:34:13
📌 存储键-值对时都是有序的，所以必然会有很多键具有相同的前缀，为了去掉这部分冗余空间，LevelDB设计了如图8-3所示的存储格式 ⏱ 2022-02-14 08:34:51
📌 而要读取到完整的键数据则需要依次向前读取，直到找到第一组完整的键-值对数据（即共享部分长度为0的键-值对）。 ⏱ 2022-02-14 08:36:04
📌 每一个重启点指向一个偏移量，该偏移量指向的就是第一组完整键-值对数据开始的位置。 ⏱ 2022-02-14 08:36:16
📌 。一个块中键的范围可以通过数据索引区域得到，接下来我们继续观察数据索引区域。 ⏱ 2022-02-14 08:38:06
📌 实际上数据索引块中的键为前一个数据块的最后一个键（即一个数据块中最大的键，因为键是有序排列保存的）与后一个数据块的第一个键（即一个数据块中的最小键）的最短分隔符。 ⏱ 2022-02-14 08:38:28
📌 block_size指明每个块的大小，默认为4KB，block_restart_interval表明保存多少个键-值对之后需要开启一个新的重启点，默认值为16，即每当保存16个键-值对后需要一个新的重启点。 ⏱ 2022-02-14 08:39:30
📌 LevelDB为加速查找，将布隆过滤器数据保存到元数据中，元数据索引块可指示如何查找该布隆过滤器的数据。 ⏱ 2022-02-14 08:39:42
📌 SSTable中，每2KB键-值对数据会生成一个过滤器，过滤器的内容保存在filter部分。 ⏱ 2022-02-14 08:40:52
📌 3）过滤器内容大小与过滤器基数：前者代表过滤器内容总的大小，后者在LevelDB中为一个常量11（2的11次幂为2KB，因此11代表每2KB数据生成一个过滤器）。 ⏱ 2022-02-14 08:41:26
📌 在布隆过滤器的场景下，块类型type为kNoCompression，即不压缩。块校验为4字节的CRC校验。 ⏱ 2022-02-14 08:41:34