1377人阅读
NoSQL（18）
源码之路（18）
leveldb会按照不同版本组织数据（level-0 -& level-n，从新到旧），这些数据以SSTable格式存储于磁盘上。一个SSTable文件可以看成一个基于磁盘、只读的map，支持顺序扫描，同时可以查找某个key。本文就来探究一下SSTable文件的格式，以及创建过程。1. SSTable文件格式
| - - - - - - - - - - - - - - - - |
| & Data Blocks & & & & &|
| - - - - - - - - - - - - - - - - |
| & Filter Block & & & & & |
| - - - - - - - - - - - - - - - - |
| & &Meta Index Block & & |
| - - - - - - - - - - - - - - - - |
| & &Index Block & & &|
| - - - - - - - - - - - - - - - - |
|& & &Footer &
| - - - - - - - - - - - - - - - - | 如上就是SSTable的文件格式，整个文件包括一系列的Block，Block是磁盘io以及内存cache的基本单位，通过Block读写可以均摊每次IO的开销，利用局部性原理。Block的大小是用户可配置的。 1) Data Blocks：存放kv对，即实际的数据。kv对会按照大小划分成Block，无法保证所有的Block大小一致，但基本接近于配置的Block大小，但是当kv对数据大于该值时，会作为一个Block。Block内部还包括其他的一些元数据，后文会深入介绍。 2) Filter Block: Filter用于确定SSTable是否包含一个key，从而在查找该key时，避免磁盘IO。Filter Block用于存储Filter序列化后的结果。 3) Meta Index Block: 用于存放元数据，目前只会kv格式存储Filter block的偏移量，key是filter.${FILTER_NAME}，value是filter block在文件的偏移量。 4) Index Block: 对Data block的索引，保存了各个Block中最小key，从而确定了Block的key的范围，加速某个key的搜索。 5) Footer: 元数据的元数据，其中包含Index Block和Meta Index Block的偏移量。Footer之所以在最后，是因为文件生成时是顺序追加的，而Footer的信息又依赖于之前的所有信息，所以只能在最后。由于包含了元数据，所以读取SSTable时首要的就是加载footer。2. 数据结构 BlockHandle: 指向文件中的一个Block，有两个属性Block的偏移量（offset_）和大小（size_）。 Footer: 表示SSTable文件的Footer，大小固定。 这两个结构提供到string的序列化和反序列化的方法。 TableBuilder: 构造SSTable的入口。将一系列的kv对构造成SSTable。 BlockBuilder: 构造Block，对添加的kv对进行序列化。 FilterBlockBuilder: 构造Filter Block。 以上便是生成SSTable文件的主要数据结构。3. BlockBuidler 上文提到Block是数据传输的基本单位，在Data Block中通过Block将连续的kv对打包处理，可以利用局部性原理。同时kv按key顺序存储，那么同一个Block中key的重复内容比例会增加，可以通过压缩提高空间利用率。 1) Block格式：
| - - Block Content: var len - - | - - Block Type: 1Byte - - | - - CRC: 4Byte - - |
一个Block包含3部分：
（1）Block Content：kv序列化后的内容，是可变长度的字节数组。
（2）Block Type：指定Block是否压缩，1个字节。
（3）CRC：CRC校验码，用于数据完整测试，4个字节。 2) Block Content格式：
| - - KV Entries: var len - - | - - Restart Point Array: 4nBytes - - | - - Num Restart Point: 4Byte - - |
（1）KV Entries：一系列kv内容，Block的实际内容，是可变长度的字节数组。
（2）Restart Point Array：Restart Point数组，每个元素就是一个整形，4n字节。后文会介绍Restart Point的作用。
（3）Num Restart Point：指定了Restart Point数组的长度，4字节。 3)&&KV Entry格式：
由于kv对按key顺序存储，所以对key采用前缀压缩以节省空间。
| - - Shared: 4Byte - - | - - Non-shared: 4Byte - - | - - Val Len: 4Byte - - | - - Key Delta: var len - - | - - Value: var len - - |
（1）Shared：与前一个key共同前缀长度。
（2）Non-shared：key非共同前缀长度，Shared + Non-shared等于key的长度。
（3）Val len：value的长度。
（4）Key Delta：存储去除共同前缀的key。
（5）Value：存放Value。
通过上面描述可以知道，在存储一个key时，不会存其与前一个key的共同前缀，只会存不同的部分。那么，从磁盘读取一个key时，就需要先把前一个key读出才能获取完整的可以。这会存在一个问题，如果读取最后一个key，那么需要把[1, n-1]个key都读出才能获得完整内容。
LevelDB通过引入Restart Point来解决上述问题，每个Restart Point相当于前缀压缩的重启点。Restart Point指向一个key，它会存储完整的内容，其Shared等于0。通过在一些kv中平均插入多个Restart Point，可以减少前缀解压缩读取的长度。默认，LevelDB中放置Restart Point的间隔为16，保证最坏情况下最多只要读取15个key就能获取一个key的完整内容。
同时，Restart Point指向的key也是排序的，可以把底层kv序列的二级索引，在进行key搜索时，先进行Restart Point的二分查找框定范围，然后再在指定的key范围内线性查找。4. FilterBlock Filter用于加快key搜索，避免无效的磁盘IO。LevelDB本身提供Bloom Filter。可以简单把Filter当做是一个集合，用于判断一个key是否存在于该集合。FilterBlock中存放的是SSTable文件中所有key组成的集合信息（就是Filter根据key进行序列化后的结果）。 1) FilterBlock格式：
| - - Encoded Filter Array: var len - - | - - Filter Offset Array: 4nByte - - | - - Offset of Offset Array: 4Byte - - | - - Base lg: 1Byte -- |
（1）Encoded Filter Array：经过Filter序列化的字节数组，由n个Filter的信息组成。
（2）Filter Offset Array：指定每个Filter在Encoded Filter Array中的偏移量。
（3）Offset of Offset Array：Filter Offset Array的偏移量。
（4）Base lg：2^(Base lg)是对数据块构造Filter的最小size。LevelDB默认是2KB。 2) 流程：
LevelDB对于创建Filter源数据的大小有要求，不能小于2KB，这么做是为了防止源数据过小，导致取Filter的粒度过小，单位Block对应Filter的空间使用率过大，会比较浪费。
Encoded Filter Array与Data Block之间的对应关系稍微复杂些，当Block小于2KB时（比如1KB），那么多个Block会使用一个Filter。如果Block大于2KB（比如4KB），那么一个Block对应一个Filter。
在每次开始一个新的Block时，会调用FilterBuilder.StartBlock()方法，这里会确定Block与Filter之间的对应关系，如果前一个Filter已经完成，会生成这个Filter。在所有Key添加完毕后，会调用FilterBuilder.Finish()方法进行整体序列化，并返回序列化后的结果。5. TableBuilder TableBuilder是对外生成SSTable的接口，通过Add方法接收一个个kv，依托于底层的BlockBuidler创建Block，如果当前的Block大小超过预设的值，会调用BlockBuilder的Finish方法进行序列化，然后追加到文件。在所有kv添加完毕后，调用TableBuilder.Finish方法追加元数据，包括Filter Block，Meta Index Block，Index Block以及Footer。
6. 总结 上述介绍的是SSTable的磁盘表现形式，设计的相当精巧，包括但不限于前缀压缩，Restart Point的引入，Filter的源数据块划分等。下一篇会介绍SSTable的读取，即内存表现形式。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：647380次
积分：6877
积分：6877
排名：第2224名
原创：116篇
评论：123条& & leveldb只是单纯的在文件末尾增加，并不改写原有的内容，那么如果删除一个key，或者更新一个key应该怎么办呢？比如：& & table&span&[&/span&&span&"liming"&/span&&span&]&/span&&span&=&/span&&span&18&/span&del table&span&[&/span&&span&"liming"&/span&&span&]&/span&table&span&[&/span&&span&"liming"&/span&&span&]&/span&&span&=&/span&&span&20&/span&table&span&[&/span&&span&"liming"&/span&&span&]&/span&&span&=&/span&&span&21&/span&& & leveldb将每一个操作变化成如下的格式：& & userkey sequence type&span&:&/span&value&span&// user_key: 即用户存储的key&/span&&span&// 比如 table["liming"] = 18 table["wangdong"] = 20&/span&&span&// "liming", "wangdong" 就是user_key。&/span&&span&// sequence为操作序列号&/span&&span&// type操作是删除还是更新&/span&&span&// value是值&/span&& & 上面的一系列操作就变为:& & liming&span&1&/span&kTypeValue&span&:&/span&&span&18&/span&liming&span&2&/span&kTypeDeletionliming&span&3&/span&kTypeValue&span&:&/span&&span&20&/span&liming&span&4&/span&kTypeValue&span&:&/span&&span&21&/span&& & 内部按照key非递减，sequence非递增，kTypeValue非递增排序(保证kTypeDeletion在前面)进行排序（存储在SkipList中），这样查询时便可以找到key对应的最新值，如果type位kTypeDeletion则不存在。& & 下面介绍一下什么是user_key MemTableKey InternalKey LookupKey& & Memtable的内容是：& & key_size&span&:&/span&varint32 of internal_key.&span&size&/span&&span&(&/span&&span&)&/span&key_bytes&span&:&/span&&span&char&/span&&span&[&/span&internal_key.&span&size&/span&&span&(&/span&&span&)&/span&&span&]&/span&value_size&span&:&/span&varint32 of value.&span&size&/span&&span&(&/span&&span&)&/span&value_bytes&span&:&/span&&span&:&/span&&span&char&/span&&span&[&/span&value.&span&size&/span&&span&(&/span&&span&)&/span&&span&]&/span&&span&[&/span&ksize&span&]&/span&&span&[&/span&&span&---&/span&InternalKey&span&---&/span&&span&]&/span&&span&[&/span&vsize&span&]&/span&&span&[&/span&&span&---&/span&value&span&---&/span&&span&]&/span&MemTableKey为：&span&[&/span&ksize&span&]&/span&&span&[&/span&&span&---&/span&InternalKey&span&---&/span&&span&]&/span&即InternalKey的序列化& & InternalKey的格式& & &span&[&/span&&span&--------&/span&user_key&span&--------&/span&&span&]&/span&&span&[&/span&sequence type&span&]&/span&&span&[&/span&低&span&8&/span&字节&span&]&/span&& & 如何获得user_key& & Slice(internal_key.data(), internal_key.size() - 8 )& & LookupKey& & &span&[&/span&klength&span&]&/span&&span&[&/span&&span&--------&/span&user_key&span&--------&/span&&span&]&/span&&span&[&/span&sequence type&span&]&/span&&span&[&/span&klength&span&]&/span&&span&[&/span&&span&-------------&/span&internal_key&span&---------------&/span&&span&]&/span&& & 为什么要LookupKey？ 主要是和内部MemTableKey一致。& & 为什么要InternalKey？把MemTableKey从内存中读出来就是InternalKey，及Memtable_key是InternalKey的序列化。
声明：该文章系网友上传分享，此内容仅代表网友个人经验或观点，不代表本网站立场和观点；若未进行原创声明，则表明该文章系转载自互联网；若该文章内容涉嫌侵权，请及时向
上一篇：下一篇：
相关经验教程
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.002 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.005 收益
的原创经验被浏览，获得 ￥0.001 收益
的原创经验被浏览，获得 ￥0.001 收益LevelDB源码之5Current文件\Manifest文件\版本信息 - 数据库当前位置:& &&&LevelDB源码之5Current文件\Manifest文件\版本信息LevelDB源码之5Current文件\Manifest文件\版本信息&&网友分享于：&&浏览：0次LevelDB源码之五Current文件\Manifest文件\版本信息版本信息有什么用？先来简要说明三个类的具体用途：
Version：代表了某一时刻的数据库版本信息，版本信息的主要内容是当前各个的SSTable数据文件列表。
VersionSet：维护了一份列表，包含当前的所有信息，列表中第一个代表数据库的当前版本。
VersionEdit：表示Version之间的变化，相当于delta&增量，表示有增加了多少文件，删除了文件。Version0&+VersionEdit--&Version1。VersionEdit会保存到MANIFEST文件中，当做数据恢复时就会从MANIFEST文件中读出来重建数据。那么，何时会触发版本变迁呢？Compaction。
有了上面的描述，再来看版本信息到底有什么用呢？
如果还不能给出答案，将上述三个类当作一个整体，再来看Version类组到底包含了哪些信息：
运行期各种递增ID值：log number(log编号)、next file number(下一个文件编号)、last sequence(单条write操作递增该编号，可认为是版本号)、prev log number(目前已弃用)。
比较器名称
数据库元信息
各Level的SSTable文件列表
SSTable缓存
Compaction信息、
Compaction Pointer
通过Seek触发Compaction信息(文件名、Level)；通过Compaction触发Compaction信息(score、level)
关于版本信息到底有什么用这个话题暂时先放一放，来看具体类。
VersionSet(维护了一份Version列表，包含当前Alive的所有Version信息，列表中第一个代表数据库的当前版本)
VersionSet类只有一个实例，在DBImpl(数据库实现类)类中，维护所有活动的Version对象，来看VersionSet的所有语境：
1. 数据库启动时：通过Current文件加载Manifset文件，读取Manifest文件完成版本信息恢复
Status VersionSet::Recover() {
// Read "CURRENT" file, which contains a pointer to the current manifest file
std::string
Status s = ReadFileToString(env_, CurrentFileName(dbname_), &current);
current.resize(current.size() - 1);
std::string dscname = dbname_ + "/" +
SequentialFile*
s = env_-&NewSequentialFile(dscname, &file);
//manifest文件
bool have_log_number = false;
bool have_prev_log_number = false;
bool have_next_file = false;
bool have_last_sequence = false;
uint64_t next_file = 0;
uint64_t last_sequence = 0;
uint64_t log_number = 0;
uint64_t prev_log_number = 0;
VersionSet::Builder builder(this, current_);
reporter.status = &s;
log::Reader reader(file, &reporter, true/*checksum*/, 0/*initial_offset*/);
std::string
while (reader.ReadRecord(&record, &scratch) && s.ok()) {
//依次读取manifest中的VersionEdit信息，构建VersionSet
s = edit.DecodeFrom(record);
if (s.ok()) {
//Comparator不一致时，返回错误信息
if (edit.has_comparator_ &&
parator_ != icmp_.user_comparator()-&Name()) {
s = Status::InvalidArgument(
parator_ + "does not match existing comparator ",
icmp_.user_comparator()-&Name());
//实际上，这里可以直接break
if (s.ok()) {
builder.Apply(&edit);
//构建当前Version
if (edit.has_log_number_) {
log_number = edit.log_number_;
have_log_number = true;
if (edit.has_prev_log_number_) {
prev_log_number = edit.prev_log_number_;
have_prev_log_number = true;
if (edit.has_next_file_number_) {
next_file = edit.next_file_number_;
have_next_file = true;
if (edit.has_last_sequence_) {
last_sequence = edit.last_sequence_;
have_last_sequence = true;
file = NULL;
if (s.ok()) {
Version* v = new Version(this);
builder.SaveTo(v);
// Install recovered version
Finalize(v);
//计算下次执行压缩的Level
AppendVersion(v);
manifest_file_number_ = next_
next_file_number_ = next_file + 1;
last_sequence_ = last_
log_number_ = log_
prev_log_number_ = prev_log_
Recover通过Manifest恢复VersionSet及Current Version信息，恢复完毕后Alive的Version列表中仅包含当Current Version对象。
2. Compaction时：Compaction(压缩)应该是LevelDB中最为复杂的功能，它需要Version类组的深度介入。来看VersionSet中所有和Compaction相关的接口声明：
// Apply *edit to the current version to form a new descriptor that
// is both saved to persistent state and installed as the new
// current version.
Will release *mu while actually writing to the file.
// REQUIRES: *mu is held on entry.
// REQUIRES: no other thread concurrently calls LogAndApply()
Status LogAndApply(VersionEdit* edit, port::Mutex* mu);
// Pick level and inputs for a new compaction.
// Returns NULL if there is no compaction to be done.
// Otherwise returns a pointer to a heap-allocated object that
// describes the compaction.
Caller should delete the result.
Compaction* PickCompaction();
// Return a compaction object for compacting the range [begin,end] in
// the specified level.
Returns NULL if there is nothing in that
// level that overlaps the specified range.
Caller should delete
// the result.
Compaction* CompactRange(
int level,
const InternalKey* begin,
const InternalKey* end);
// Create an iterator that reads over the compaction inputs for "*c".
// The caller should delete the iterator when no longer needed.
Iterator* MakeInputIterator(Compaction* c);
// Returns true iff some level needs a compaction.
bool NeedsCompaction() const {
Version* v = current_;
return (v-&compaction_score_ &= 1) || (v-&file_to_compact_ != NULL);
// Add all files listed in any live version to *live.
// May also mutate some internal state.
void AddLiveFiles(std::set&uint64_t&* live);
数据库的读、写操作都可能触发Compaction，通过调用NeedCompaction判定是否需要执行Compaction，如需Compaction则调用PickCompaction获取Compactoin信息。
其他几个方法也和Compaction操作相关，其中LogAndApply非常重要，它将VersionEdit应用于Current Version、VersoinEdit持久化到Manifest文件、将新的Version做为Current Version。
Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
if (edit-&has_log_number_) {
assert(edit-&log_number_ &= log_number_);
assert(edit-&log_number_ & next_file_number_);
edit-&SetLogNumber(log_number_);
if (!edit-&has_prev_log_number_) {
edit-&SetPrevLogNumber(prev_log_number_);
edit-&SetNextFile(next_file_number_);
edit-&SetLastSequence(last_sequence_);
//1. New Version = Current Version + VersionEdit
Version* v = new Version(this);
Builder builder(this, current_);
builder.Apply(edit);
builder.SaveTo(v);
//2. 重新计算Compaction Level\Compaction Score
Finalize(v);
//3. 打开数据库时，创建新的Manifest并保存当前版本信息
// Initialize new descriptor log file if necessary by creating
// a temporary file that contains a snapshot of the current version.
std::string new_manifest_
if (descriptor_log_ == NULL) {
// No reason to unlock *mu here since we only hit this path in the
// first call to LogAndApply (when opening the database).
assert(descriptor_file_ == NULL);
new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
edit-&SetNextFile(next_file_number_);
s = env_-&NewWritableFile(new_manifest_file, &descriptor_file_);
if (s.ok()) {
descriptor_log_ = new log::Writer(descriptor_file_);
s = WriteSnapshot(descriptor_log_);
//当前版本信息
//4. 保存增量信息，即VersionEdit信息
// Unlock during expensive MANIFEST log write
mu-&Unlock();
// Write new record to MANIFEST log
if (s.ok()) {
std::string
edit-&EncodeTo(&record);
s = descriptor_log_-&AddRecord(record);
if (s.ok()) {
s = descriptor_file_-&Sync();
// If we just created a new descriptor file, install it by writing a
// new CURRENT file that points to it.
if (s.ok() && !new_manifest_file.empty()) {
s = SetCurrentFile(env_, dbname_, manifest_file_number_);
mu-&Lock();
//5. 将新的版本添加到Alive版本列表，并将其做为Current Version
// Install the new version
if (s.ok()) {
AppendVersion(v);
log_number_ = edit-&log_number_;
prev_log_number_ = edit-&prev_log_number_;
if (!new_manifest_file.empty()) {
delete descriptor_log_;
delete descriptor_file_;
descriptor_log_ = NULL;
descriptor_file_ = NULL;
env_-&DeleteFile(new_manifest_file);
3. 读取数据时：LevelDB通过VersionSet中的TableCache对象完成数据读取。
TableCache是SSTable的缓存类，NewIterator方法通过传入指定的文件编号返回该文件的Iterator供外部使用。
class TableCache {
TableCache(const std::string& dbname, const Options* options, int entries);
~TableCache();
// Return an iterator for the specified file number (the corresponding
// file length must be exactly "file_size" bytes).
If "tableptr" is
// non-NULL, also sets "*tableptr" to point to the Table object
// underlying the returned iterator, or NULL if no Table object underlies
// the returned iterator.
The returned "*tableptr" object is owned by
// the cache and should not be deleted, and is valid for as long as the
// returned iterator is live.
Iterator* NewIterator(const ReadOptions& options,
uint64_t file_number,
uint64_t file_size,
Table** tableptr = NULL);
// Evict any entry for the specified file number
void Evict(uint64_t file_number);
Env* const env_;
const std::string dbname_;
const Options* options_;
Cache* cache_;
缓存机制主要通过Cache对象实现，关于Cache的备忘下节会讲。
Version维护了一份当前版本的SSTable的元数据，其对外暴露的接口大部分也和元数据相关：
void GetOverlappingInputs(
int level,
const InternalKey* begin,
// NULL means before all keys
const InternalKey* end,
// NULL means after all keys
std::vector&FileMetaData*&* inputs);
// Returns true iff some file in the specified level overlaps
// some part of [*smallest_user_key,*largest_user_key].
// smallest_user_key==NULL represents a key smaller than all keys in the DB.
// largest_user_key==NULL represents a key largest than all keys in the DB.
bool OverlapInLevel(int level,
const Slice* smallest_user_key,
const Slice* largest_user_key);
// Return the level at which we should place a new memtable compaction
// result that covers the range [smallest_user_key,largest_user_key].
int PickLevelForMemTableOutput(const Slice& smallest_user_key,
const Slice& largest_user_key);
int NumFiles(int level) const { return files_[level].size(); }
还有两个数据库读取操作相关的方法Get、UpdateStats，来看Get：
Status Version::Get(const ReadOptions& options,
const LookupKey& k,
std::string* value,
GetStats* stats)
Slice ikey = k.internal_key();
Slice user_key = k.user_key();
const Comparator* ucmp = vset_-&icmp_.user_comparator();
stats-&seek_file = NULL;
stats-&seek_file_level = -1;
FileMetaData* last_file_read = NULL;
int last_file_read_level = -1;
// We can search level-by-level since entries never hop across
// levels.
Therefore we are guaranteed that if we find data
// in an smaller level, later levels are irrelevant.
std::vector&FileMetaData*&
FileMetaData* tmp2;
//1. 查找包含指定Key的所有文件
for (int level = 0; level & config::kNumL level++) {
size_t num_files = files_[level].size();
if (num_files == 0) continue;
// Get the list of files to search in this level
FileMetaData* const* files = &files_[level][0];
if (level == 0) {
//1.1 Level-0可能存在多个文件均包含该Key
// Level-0 files may overlap each other.
Find all files that
// overlap user_key and process them in order from newest to oldest.
tmp.reserve(num_files);
for (uint32_t i = 0; i & num_ i++) {
FileMetaData* f = files[i];
if (ucmp-&Compare(user_key, f-&smallest.user_key()) &= 0 &&
ucmp-&Compare(user_key, f-&largest.user_key()) &= 0) {
tmp.push_back(f);
if (tmp.empty()) continue;
std::sort(tmp.begin(), tmp.end(), NewestFirst);
//将文件按更新顺序排列
files = &tmp[0];
num_files = tmp.size();
//1.2 Level-0之上，一个Key只可能存在于一个文件中
// Binary search to find earliest index whose largest key &= ikey.
uint32_t index = FindFile(vset_-&icmp_, files_[level], ikey);
if (index &= num_files) {
files = NULL;
num_files = 0;
tmp2 = files[index];
if (ucmp-&Compare(user_key, tmp2-&smallest.user_key()) & 0) {
// All of "tmp2" is past any data for user_key
files = NULL;
num_files = 0;
files = &tmp2;
num_files = 1;
//2. 遍历所有文件，查找Key值数据。
for (uint32_t i = 0; i & num_ ++i) {
if (last_file_read != NULL && stats-&seek_file == NULL) {
// We have had more than one seek for this read.
Charge the 1st file.
stats-&seek_file = last_file_
stats-&seek_file_level = last_file_read_
FileMetaData* f = files[i];
last_file_read =
last_file_read_level =
//2.1 SSTable迭代器
Iterator* iter = vset_-&table_cache_-&NewIterator(
f-&number,
f-&file_size);
iter-&Seek(ikey);
//2.2 查找指定Key
const bool done = GetValue(iter, user_key, value, &s);
//2.3 Get Value
if (!iter-&status().ok()) {
s = iter-&status();
if (done) {
return Status::NotFound(Slice());
// Use an empty error message for speed
VersionEdit
版本建变化除运行期编号修改外，最主要的是SSTable文件的增删信息。当Compaction执行时，必然会出现部分SSTable无效被移除，合并生成的新SSTable被加入到数据库中。VersionEdit提供AddFile、DeleteFile完成变更标识。
VersionEdit提供的另外一个主要功能接口声明如下：
void EncodeTo(std::string* dst) const;
Status DecodeFrom(const Slice& src);
这是一组序列化、反序列化方法，序列化文件为Manifest文件。
void VersionEdit::EncodeTo(std::string* dst) const {
//1. 序列化比较器
if (has_comparator_) {
PutVarint32(dst, kComparator);
PutLengthPrefixedSlice(dst, comparator_);
//2. 序列化运行期编号信息
if (has_log_number_) {
PutVarint32(dst, kLogNumber);
PutVarint64(dst, log_number_);
if (has_prev_log_number_) {
PutVarint32(dst, kPrevLogNumber);
PutVarint64(dst, prev_log_number_);
if (has_next_file_number_) {
PutVarint32(dst, kNextFileNumber);
PutVarint64(dst, next_file_number_);
if (has_last_sequence_) {
PutVarint32(dst, kLastSequence);
PutVarint64(dst, last_sequence_);
//3. 序列化Compact Pointer
for (size_t i = 0; i & compact_pointers_.size(); i++) {
PutVarint32(dst, kCompactPointer);
PutVarint32(dst, compact_pointers_[i].first);
PutLengthPrefixedSlice(dst, compact_pointers_[i].second.Encode());
//4. 序列化本次版本变化的SSTable文件列表
for (DeletedFileSet::const_iterator iter = deleted_files_.begin();
iter != deleted_files_.end();
PutVarint32(dst, kDeletedFile);
PutVarint32(dst, iter-&first);
PutVarint64(dst, iter-&second);
// file number
for (size_t i = 0; i & new_files_.size(); i++) {
const FileMetaData& f = new_files_[i].
PutVarint32(dst, kNewFile);
PutVarint32(dst, new_files_[i].first);
PutVarint64(dst, f.number);
PutVarint64(dst, f.file_size);
PutLengthPrefixedSlice(dst, f.smallest.Encode());
PutLengthPrefixedSlice(dst, f.largest.Encode());
回到最开始的问题：版本信息由什么用？
版本信息记录了运行期一组编号信息，该信息被序列化到Manifest文件中，当数据库再次打开时可恢复至上一次的运行状态。
版本信息记录了SSTable信息，包括每个文件所属的层级、大小、编号（名称等）；Version类组提供了查询SSTable信息功能，如每层文件的列表、数量；同时数据库的Get方法中如需通过文件查找key值数据时，也由Version类组完成。最后，SSTable的缓存机制也有Version类组提供。
版本信息提供了Compaction支持。
每个LevelDB有一个Current&File，Current&File内唯一的信息为：当前数据库的Manifest文件名。Manifest中包含了上次运行后全部的版本信息，LevelDB通过Manifest文件恢复版本信息。
LevelDB的版本信息为富语义功能组，它所包含的信息已经大大超出了版本定义本身。如果将Version类封装为结构体、VersionSet仅仅为Version列表、VersionEdit也是单纯的结构数据，再为上述结构提供多套功能类应该更为合理。目前来看，这应当算作LevelDB实现的一处臭味。
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有}