1.leveldb之数据存储结构
2.深入源码解析LevelDB

leveldb之数据存储结构

       leveldb中的数据存储结构设计巧妙，尽管在源码中编码和反编码较为复杂，但理解时可以将其当作黑盒子。本文主要讨论几个关键组件：Slice、Varint/、InternalKey、hadoop 2.4.1 源码Comparator、SSTable、DataBlock、IndexBlock、FilterBlock、MetaIndexBlock以及Log和WriteBatch。

       Slice是一个轻量级的数据结构，类似Go语言的切片，用于方便传递和引用数据子串，尤其在处理C++标准库中的源码打包成apkstd::string时，Slice更轻便，不需复制子串。

       Varint/是变长编码，用于节省存储空间，如位整型，通过MSB和后续7位表示数据，最长可编码到5字节。这种编码方式使得数字存储更加紧凑。

       InternalKey是存储用户数据的关键，由user_key、sequence和type组成，sequence用于版本控制和数据合并，type区分值类型和删除标记。删除时，leveldb通过日志追加而非直接修改，app源码转小程序确保数据一致性。

       Comparator接口用于自定义key的比较逻辑，而InternalKeyComparator结合user_comparator，通过用户键和序列进行排序，保证新数据在旧数据的前面。

       SSTable由DataBlock、MetaIndexBlock和IndexBlock组成，DataBlock采用前缀压缩和重启点设计，提高了空间效率。IndexBlock则用于记录DataBlock的映射，采用跳点策略来压缩key。

       FilterBlock在构建Block的同时生成BloomFilter，用于快速过滤查找。MetaIndexBlock存储元信息到MetaBlock的映射。

       Footer用于文件校验和解析，mac 源码安装jdk包含索引和元数据信息。MemTable使用skiplist结构，支持高效查找，通过墓碑标记删除，保持数据一致性。

       Log负责持久化数据，避免内存丢失。WriteBatch用于批量操作，保证原子性，并进行序列化，便于数据恢复。

深入源码解析LevelDB

       深入源码解析LevelDB

       LevelDB总体架构中，sstable文件的生成过程遵循一系列精心设计的步骤。首先，遍历immutable memtable中的大漠中文模块源码key-value对，这些对被写入data_block，每当data_block达到特定大小，构造一个额外的key-value对并写入index_block。在这里，key为data_block的最大key，value为该data_block在sstable中的偏移量和大小。同时，构造filter_block，默认使用bloom filter，用于判断查找的key是否存在于data_block中，显著提升读取性能。meta_index_block随后生成，存储所有filter_block在sstable中的偏移和大小，此策略允许在将来支持生成多个filter_block，进一步提升读取性能。meta_index_block和index_block的偏移和大小保存在sstable的脚注footer中。

       sstable中的block结构遵循一致的模式，包括data_block、index_block和meta_index_block。为提高空间效率，数据按照key的字典顺序存储，采用前缀压缩方法处理。查找某一key时，必须从第一个key开始遍历才能恢复，因此每间隔一定数量（block_restart_interval）的key-value，全量存储一个key，并设置一个restart point。每个block被划分为多个相邻的key-value组成的集合，进行前缀压缩，并在数据区后存储起始位置的偏移。每一个restart都指向一个前缀压缩集合的起始点的偏移位置。最后一个位存储restart数组的大小，表示该block中包含多少个前缀压缩集合。

       filter_block在写入data_block时同步存储，当一个new data_block完成，根据data_block偏移生成一份bit位图存入filter_block，并清空key集合，重新开始存储下一份key集合。

       写入流程涉及日志记录，包括db的sequence number、本次记录中的操作个数及操作的key-value键值对。WriteBatch的batch_data包含多个键值对，leveldb支持延迟写和停止写策略，导致写队列可能堆积多个WriteBatch。为了优化性能，写入时会合并多个WriteBatch的batch_data。日志文件只记录写入memtable中的key-value，每次申请新memtable时也生成新日志文件。

       在写入日志时，对日志文件进行划分为多个K的文件块，每次读写以这样的每K为单位。每次写入的日志记录可能占用1个或多个文件块，因此日志记录块分为Full、First、Middle、Last四种类型，读取时需要拼接。

       读取流程从sstable的层级结构开始，0层文件特别，可能存在key重合，因此需要遍历与查找key有重叠的所有文件，文件编号大的优先查找，因为存储最新数据。非0层文件，一层中的文件之间key不重合，利用版本信息中的元数据进行二分搜索快速定位，仅需查找一个sstable文件。

       LevelDB的sstable文件生成与合并管理版本，通过读取log文件恢复memtable，仅读取文件编号大于等于min_log的日志文件，然后从日志文件中读取key-value键值对。

       LevelDB的LruCache机制分为table cache和block cache，底层实现为个shard的LruCache。table cache缓存sstable的索引数据，类似于文件系统对inode的缓存；block cache缓存block数据，类似于Linux中的page cache。table cache默认大小为，实际缓存的是个sstable文件的索引信息。block cache默认缓存8M字节的block数据。LruCache底层实现包含两个双向链表和一个哈希表，用于管理缓存数据。

       深入了解LevelDB的源码解析，有助于优化数据库性能和理解其高效数据存储机制。