作者:Jeff Dean, Sanjay Ghemawat
原文:leveldb.googlecode.com
译者:phylips@bmy
译文:duanple.blog.163.com
Files
LevelDB的实现本质上类似于Bigtable中的tablet(参见Bigtable论文5.3节)。但是,与论文中的具体的文件组织方式稍有不同,解释如下:
每个数据库由一组存储在指定目录下的一个文件集合组成。有如下几种文件类型:
Log files
日志文件(*.log)存储了最近的一系列更新。每个更新操作会被追加到当前的日志文件中。当日志文件达到预定义的大小后,会被转化为一个sorted table,同时一个新的日志文件会被创建出来以接受未来的更新。
同时会在一个内存结构(memtable)中保存一份当前的日志文件的一个copy。该copy会参与到每次读操作中,这样最新的已日志化的更新就能够反映到读操作中。
Sorted tables
sorted table (*.sst) 存储了一系列根据key值排好序的记录。每条记录要么是某key值对应的value,要么是一个针对该key值的删除标记。(删除标记会被用来去掉那些老的sorted tables中已过时的value值)。
sorted tables集合是通过一系列的level来进行组织的。从日志文件生成的sorted table会被放置在一个特殊的young level(也称作level 0)内。当该level下的文件数超过一定阈值(当前是4)时,该level下的所有文件会与level 1下与之有重叠的那些文件merge到一块,从而产生一系列新的level 1下的文件(我们会为每2MB的数据创建一个level 1文件)。
在level 0下的不同文件可能包含重叠的key值。但是其他level下的文件,它们的key range都是不重叠的(是指同一个level内部的文件不会重叠,不同的level之间会存在重叠)。设现有level L(L>=1),当level L下的文件总大小超过(10^L)MB时(比如,对应level 1就是10MB,level 2就是100MB,…),level L下的一个文件就会与level L+1下的所有与它有重叠的key的文件merge成一系列level L+1下的新文件。为最小化昂贵的seek开销,这些merge操作通过批量的读写操作,逐步的将新的更新从young
level迁移到最大的level下。
Manifest
MANIFEST文件列出了组成每个level的sorted tables集合,对应的key range,以及其他一些重要的元数据。只要数据库被重新打开,就会产生一个新的MANIFEST文件(文件名会嵌入一个新的数字)。MANIFEST文件会被格式化为一个log,所有导致状态改变(文件增加或删除)的变更都会追加到该log里。
Current
CURRENT 是一个包含了最新的MANIFEST文件名称的文本文件。
Info logs
一些信息会被输出到名为LOG及LOG.old的文件中。
Others
其他用于各种目的的可能会产生的文件 (LOCK, *.dbtmp).
Level 0
当日志文件超过一定大小(默认1MB)时,会进行如下操作:
- 创建一个全新的memtable结构和log文件,同时将未来的更新指向它们
- 同时在后台进行如下操作:
- 将之前的memtable的内容写入到sstable里
- 丢弃该memtable
- 删除老的log文件及memtable
- 将新的sstable添加到level 0下
Compactions
当level L的大小超过自身的限制时,我们会在一个后台线程中进行compact操作。该操作会选择来自level L的一个文件,以及那些level L+1中所有与该文件重叠的文件。需要注意的是,即使level L下的这个文件只与level L+1下的某文件的一部分有重叠,也需要读取整个level L+1下的那个文件进行compaction,之后这个旧的level L+1下的文件就会被丢弃。另外:因为level 0很特殊(文件相互之间可能是有重叠的),因此对于从level 0到level 1的compaction需要特殊对待:当level
0的某些文件相互重叠时,它的compaction就需要选择不止一个level 0的下的文件。Compaction会merge它选定的那些文件产生一系列新的level L+1下的文件。当当前输出文件大小达到目标大小(2MB)时,我们就会产生出一个新的level L+1下的文件。另外当当前输出文件的key range已经大的与10个以上的level L+2下的文件有重叠时,我们也会立即产生出一个新文件,而不一定非要等到它达到2MB,这是为了保证后面针对level L+1的Compaction不会从level L+2下获取过多数据。
老的文件会被丢弃,新的文件会被添加到服务状态。针对特定level下的Compaction是在整个key值空间内螺旋式地进行的。详细来说,比如对于Level L,我们会记住它上次compaction的那个最后的key值,在对于Level L的下次compaction时,我们会选择排在该key之后的第一个文件开始(如果没有这样的文件,那我们就再从头开始)。
Compaction会丢弃掉被覆盖的那些value值。同时如果更高level下的文件的key range不包含当前key时,针对它的删除标记也可以被丢弃掉{!更高level下的文件实际上是一些更老的值,如果它们包含该key,那么如果我们丢弃该低level下的删除标记,会导致该删除操作的丢失}
Timing
Level 0的compaction可能会从level 0下读取最多4个1MB文件,以及最坏情况下会读取所有的level 1下的文件(10MB),这意味着,我们可能需要读14MB,写14MB。
除了比较特殊的Level 0的compaction,其他情况下我们会选取level L下的一个2MB的文件。最坏情况下,level L+1下可能有12个文件与它重叠(10是因为level L+1比level L大10倍,另外的2是因为在level L下的文件边界通常与level L+1下的边界并不是对其的)。因此compaction会读26MB,写26MB。假设磁盘IO带宽是100MB/s,最坏情况下的compaction可能需要大概0.5秒。
如果我们对后台操作进行一些限制,比如限制在全部IO带宽的10%,那么compaction时间可能会达到5秒。如果用户在用户以10MB/s的速度写入,我们就可能会创建出大量的level 0下的文件(可能会达到50,因为compaction需要5秒,而5秒内客户端已经又写入了50MB,而每个1MB,因此是50个)。这可能会显著增加读操作的开销,因为每次读操作都需要merge更多的文件。
- 解决方案 1:为了减少这种问题,我们可以在level-0下的文件数很大的时候,增加log切换的阈值。缺点是,阈值越大,相对应的memtable用掉的内存也就会越多。
- 解决方案2: 当level 0下的文件数上升很快时,我们可以人为地降低写操作速率。
- 解决方案3: 尽量降低merge的开销。由于大多数的level 0下的文件的block都已经缓存在cache里了,因此我们只需要关注merge迭代过程中的O(N)的复杂度。
Number of files
为降低文件数,我们可以为更高level下的文件使用更大的文件大小,取代固定的2MB文件。当然这可能导致更多的compactions过程中的波动。另外我们也可以将文件集合划分到多个目录下。
2011-02-04,我们在ext3文件系统下做了一个关于目录下的文件数与文件打开时间的关系的实验:
Files in directory Microseconds to open a file
1000 9
10000 10
100000 16
看起来在现代文件系统中,没有必要进行目录切分。
Recovery
- 读取CURRENT文件找到最新提交的MANIFEST文件名
- 读取该 MANIFEST文件
- 清空垃圾文件
- 我们可以打开所有的sstable,但是使用惰性加载的方式会更好些…
- 将日志转化为一个新的level 0下的sstable
- Start directing new writes to a new log file with recovered sequence#
- Garbage collection of files
DeleteObsoleteFiles()会在每次compaction结束及recovery结束后调用。它会找到数据库中所有文件的名称。删掉除当前日志文件的所有日志文件。删掉那些不属于任何level及任何活动的compaction输出的table文件。
Immutable table文件格式
文件格式如下:
===========
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer] (fixed size; starts at file_size - sizeof(Footer))
文件包含一些内部指针。每个这样的指针被称为一个BlockHandle,包含如下信息:
- offset: varint64
- size: varint64
- (1)文件内的key/value对序列有序排列,然后划分到一系列的data blocks里。这些blocks一个接一个的分布在文件的开头。每个data block会根据block_builder.cc里的代码进行格式化,然后进行可选地压缩。
- (2)在数据blocks之后存储的一些meta blocks,目前支持的meta block类型会在下面进行描述。未来也可能添加更多的meta block类型。每个meta block也会根据block_builder.cc里的代码进行格式化,然后进行可选地压缩。
- (3) A “metaindex” block.会为每个meta block保存一条记录,记录的key值就是meta block的名称,value值就是指向该meta block的一个BlockHandle。
- (4) An “index” block. 会为每个data block保存一条记录,key值是>=对应的data block里最后那个key值,同时在后面的那个data block第一个key值之前的那个key值,value值就是指向该meta block的一个BlockHandle。
- (5) 文件的最后是一个定长的footer,包含了metaindex和index这两个blocks的BlockHandle,以及一个magic number。
metaindex_handle: char[p]; // Block handle for metaindex
index_handle: char[q]; // Block handle for index
padding: char[40-p-q]; // 0 bytes to make fixed length
// (40==2*BlockHandle::kMaxEncodedLength)
magic: fixed64; // == 0xdb4775248b80fb57
"stats" Meta Block
------------------
该meta block包含一系列统计信息。Key就是该统计单元的名称,value包含一系列统计信息如下:
data size
index size
key size (uncompressed)
value size (uncompressed)
number of entries
number of data blocks
日志文件格式
日志文件内容由一系列的32KB blocks组成。唯一的异常是文件的末尾可能只包含一个部分块。每个block由一系列记录组成:
block := record* trailer?
{!‘*’可以看做是正则表达式里的*,代表0个或n个record。‘?’也是,代表0个或者1个trailer }
record :=
checksum: uint32 // crc32c of type and data[]
length: uint16
type: uint8 // One of FULL, FIRST, MIDDLE, LAST
data: uint8[length]
一条记录永远都不会从block的最后6个字节开始(因为它肯定放不下,看上面的记录checksum+length+type就占了7个字节了)。在这里组成trailer的最左处那些字节,要么完全是由0字节组成要么必须被读取者跳过。
此外: 如果当前block目前只剩下7个字节,然后现在需要添加一个非0长度的记录,那么写入者需要输出一个FIRST记录(不包含任何的用户数据)来填充该block剩余的7字节的空,然后将用户数据存放到下一个block里。
未来可以添加更多的类型。某些读取者可能会直接skip掉那些它不理解的记录,其他的一些可能会报告某些数据被skip掉了。
FULL == 1
FIRST == 2
MIDDLE == 3
LAST == 4
FULL 类型的记录包含了完整的用户记录
FIRST, MIDDLE, LAST 用于那些被分成多个片段(通常是因为block的边界导致的)的用户记录的。FIRST表明是用户记录的第一个片段,FIRST表明是用户记录的最后一个片段,MID表明用户记录的中间片段类型。
Example: consider a sequence of user records:
A: length 1000
B: length 97270
C: length 8000
A会作为一个FULL类型的记录存放在第一个block里。B 会被划分成三个片段:第一个片段会填充第一个block的剩余部分, 第二个片段会填充整个的第二个block, 第二个片段会填充第三个block的前面一部分. 最后,第三个block就只剩下6个字节,会作为trailer而留空。C将会作为一个FULL类型的记录存放在第四个block里。
===================
Some benefits over the recordio format:
- (1) We do not need any heuristics for resyncing – just go to next block boundary and scan. If there is a corruption, skip to the next block. As a side-benefit, we do not get confused when part of the contents of one log file are embedded as a record inside
another log file.
- (2) Splitting at approximate boundaries (e.g., for mapreduce) is simple: find the next block boundary and skip records until we hit a FULL or FIRST record.
- (3) We do not need extra buffering for large records.
Some downsides compared to recordio format:
- (1) No packing of tiny records. This could be fixed by adding a new record type, so it is a shortcoming of the current implementation,not necessarily the format.
(2) No compression. Again, this could be fixed by adding new record types.
相关推荐
leveldb内部使用了多个基本概念,如下: - Slice:轻量级的字符串封装,不包含结束符。 - Option:创建leveldb数据库时的配置选项。 - Env:代表了底层的环境抽象,比如文件操作、时间等。 - Varint:变长整数的...
此外,熟悉leveldb的内部机制,对于自定义数据库系统、优化现有应用或开发新的键值存储解决方案都有极大的帮助。 总之,《leveldb-1.18 源码及 leveldb实现解析》这份资料是学习和研究leveldb的重要参考资料,它将...
1. **内部排序机制**:LevelDB 内部实现了基于B+树变体的排序机制,支持范围查询。 2. **Merge-Dump模式**:即合并-转储模式,在数据管理方面采用了这种策略。 3. **MemTable**:在内存中使用 MemTable 来存储新写入...
**正文** 《LevelDB实现解析》 ...总的来说,LevelDB是一个高性能、低开销的键值存储解决方案,其设计思路和实现技术对于理解分布式系统、数据库内部工作原理以及数据存储优化等方面都有重要的参考价值。
《LevelDB实现解析》 LevelDB是由Google开发的一个开源、轻量级的键值存储库,主要用于嵌入式系统和云存储服务。它提供了一种高效、可靠的方式来存储和检索大量键值对数据,适用于数据库、日志记录、元数据存储等...
leveldb源码分析 比较全面讲解leveldb leveldb 是 Google 开源...这里对 leveldb 的实现做具体解析,但并不采用对代码注释的方式,而是意图从上层设计的角度,将内部的 实现逻辑串联起来,尽量发现策略设计背后的原因。
总的来说,这个源码包为Windows开发者提供了一个良好的起点,用于学习和研究leveldb的实现细节,或者将其集成到自己的Windows应用程序中。通过深入阅读源码和实践编译,可以进一步提升对分布式存储系统、数据结构和...
《LevelDB在Windows环境下使用与理解》 LevelDB是由Google开发的一个...了解其内部的数据结构和API,能帮助开发者更好地利用LevelDB来满足特定的需求。无论是单机应用还是分布式系统,LevelDB都是一个值得考虑的选择。
LevelDB的源码分析可以帮助我们理解其内部机制,包括数据结构、算法和存储策略。 **源码结构** 解压后的`leveldb-develop`文件夹包含了LevelDB的完整源码。主要的目录和文件如下: 1. **include/leveldb**: 包含...
在 LevelDB 1.18 版本中,我们能够深入理解其内部实现机制,从而获得关于数据库引擎设计的宝贵知识。 1. **数据结构与文件组织** LevelDB 使用 SSTable(Sorted String Table)作为其基本的数据存储结构。SSTable ...
- NoSQL数据库的基础:许多NoSQL数据库如MongoDB的部分内部存储使用了LevelDB。 - 分布式系统:作为分布式系统中的局部存储,支持快速数据交换。 **总结** "leveldb-1.15.0修正版"是一个优化后的LevelDB版本,解决...
通过阅读和理解LevelDB的源码,开发者可以深入学习其内部机制,包括数据结构的设计、优化策略以及并发控制等,从而为自己的项目选择或设计合适的数据库解决方案。LevelDB-1.20版本的源码包含了实现这些功能的代码,...
3. **排序的键**:所有的键在内部都是按照字典序排序的,这使得范围查询变得非常高效。 4. **数据的持久化**:LevelDB能够将内存中的数据定期写入到磁盘上,确保即使在系统崩溃后数据也能被恢复。 5. **自动的压缩**...
在学习leveldb的过程中,你可以尝试自己编写一个简单的应用程序,使用leveldb作为存储后端,这将有助于更好地理解其内部工作原理。同时,阅读源代码也是加深理解的好方法,通过分析源码,可以学习到C++高级编程技巧...