1s

leveldb源码分析10 本系列《leveldb源码分析》共有22篇文章，这是第十篇 6.SSTable之四 6.6 遍历Table 6.6.1 遍历接口 Table导出了一个返回Iterator的接口，通过Iterator对象，调用者就可以遍历Table的内容，它简单的返回了一个TwoLevelIterator对象。见函数实现： Iterator* NewIterator(const ReadOptions&options) const; { return NewTwoLevelIterator(rep_->index_block->NewIterator(rep_->options.comparator), &Table::BlockReader,const_cast<Table*>(this), options); } // 函数NewTwoLevelIterator创建了一个TwoLevelIterator对象： Iterator* NewTwoLevelIterator(Iterator* index_iter,BlockFunction block_function, void* arg, constReadOptions& options) { return newTwoLevelIterator(index_iter, block_function, arg, options); } 这里有一个函数指针BlockFunction，类型为： typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, constSlice&); 为什么叫TwoLevelIterator呢，下面就来看看。 6.6.2 TwoLevelIterator 它也是Iterator的子类，之所以叫two level应该是不仅可以迭代其中存储的对象，它还接受了一个函数BlockFunction，可以遍历存储的对象，可见它是专门为Table定制的。 我们已经知道各种Block的存储格式都是相同的，但是各自block data存储的k/v又互不相同，于是我们就需要一个途径，能够在使用同一个方式遍历不同的block时，又能解析这些k/v。这就是BlockFunction，它又返回了一个针对block data的Iterator。Block和block data存储的k/v对的key是统一的。 先来看类的主要成员变量： BlockFunction block_function_; // block操作函数 void* arg_; // BlockFunction的自定义参数 const ReadOptions options_; // BlockFunction的read option参数 Status status_; // 当前状态 IteratorWrapper index_iter_; // 遍历block的迭代器 IteratorWrapper data_iter_; // May be NULL-遍历block data的迭代器 // 如果data_iter_ != NULL，data_block_handle_保存的是传递给 // block_function_的index value，以用来创建data_iter_ std::string data_block_handle_; 下面分析一下对于Iterator几个接口的实现。 S1 对于其Key和Value接口都是返回的data_iter_对应的key和value： virtual bool Valid() const { return data_iter_.Valid(); } virtual Slice key() const { assert(Valid()); return data_iter_....

leveldb源码分析11 本系列《leveldb源码分析》共有22篇文章，这是第十一篇 7.TableCache 这章的内容比较简单，篇幅也不长。 7.1 TableCache简介 TableCache缓存的是Table对象，每个DB一个，它内部使用一个LRUCache缓存所有的table对象，实际上其内容是文件编号{file number, TableAndFile}*。TableAndFile是一个拥有2个变量的结构体：RandomAccessFile和Table； TableCache类的主要成员变量有： Env* const env_; // 用来操作文件 const std::string dbname_; // db名 Cache* cache_; // LRUCache 三个函数接口，其中的参数**@file_number是文件编号，@file_size**是文件大小： void Evict(uint64_tfile_number); // 该函数用以清除指定文件所有cache的entry， //函数实现很简单，就是根据file number清除cache对象。 EncodeFixed64(buf,file_number); cache_->Erase(Slice(buf, sizeof(buf))); Iterator* NewIterator(constReadOptions& options, uint64_t file_number, uint64_t file_size, Table**tableptr = NULL); //该函数为指定的file返回一个iterator(对应的文件长度必须是"file_size"字节). //如果tableptr不是NULL，那么tableptr保存的是底层的Table指针。 //返回的tableptr是cache拥有的，不能被删除，生命周期同返回的iterator Status Get(constReadOptions& options, uint64_t file_number,uint64_t file_size, const Slice& k,void* arg, void(*handle_result)(void*, const Slice&, const Slice&)); // 这是一个查找函数，如果在指定文件中seek 到internal key "k" 找到一个entry， //就调用 (*handle_result)(arg,found_key, found_value). 7.2 TableCache::Get() 先来看看**Get接口，**只有几行代码： Cache::Handle* handle = NULL; Status s =FindTable(file_number, file_size, &handle); if (s.ok()) { Table* t =reinterpret_cast<TableAndFile*>(cache_->Value(handle))->table; s = t->InternalGet(options,k, arg, saver); cache_->Release(handle); } return s; 首先根据file_number找到Table的cache对象，如果找到了就调用Table::InternalGet，对查找结果的处理在调用者传入的saver回调函数中。 Cache在Lookup找到cache对象后，如果不再使用需要调用Release减引用计数。这个见Cache的接口说明。...

leveldb源码分析12 本系列《leveldb源码分析》共有22篇文章，这是第十二篇 8.FilterPolicy&Bloom之1 8.1 FilterPolicy 因名知意，FilterPolicy是用于key过滤的，可以快速的排除不存在的key。前面介绍Table的时候，在Table::InternalGet函数中有过一面之缘。 FilterPolicy有3个接口： virtual const char* Name() const = 0; // 返回filter的名字 virtual void CreateFilter(const Slice* keys, int n, std::string* dst)const = 0; virtual bool KeyMayMatch(const Slice& key, const Slice& filter)const = 0; CreateFilter接口，它根据指定的参数创建过滤器，并将结果append到dst中，注意：不能修改dst的原始内容，只做append。 参数@keys[0,n-1]包含依据用户提供的comparator排序的key列表–可重复，并把根据这些key创建的filter追加到@*dst中。 KeyMayMatch，参数@filter包含了调用CreateFilter函数append的数据，如果key在传递函数CreateFilter的key列表中，则必须返回true。 注意：它不需要精确，也就是即使key不在前面传递的key列表中，也可以返回true，但是如果key在列表中，就必须返回true。 涉及到的类如图8.1-1所示。 8.2InternalFilterPolicy 这是一个简单的FilterPolicy的wrapper，以方便的把FilterPolicy应用在InternalKey上，InternalKey是Leveldb内部使用的key，这些前面都讲过。它所做的就是从InternalKey拆分得到user key，然后在user key上做FilterPolicy的操作。 它有一个成员： constFilterPolicy* const user_policy_; 其Name()返回的是user_policy_->Name()； bool InternalFilterPolicy::KeyMayMatch(const Slice& key, constSlice& f) const { returnuser_policy_->KeyMayMatch(ExtractUserKey(key), f); } void InternalFilterPolicy::CreateFilter(const Slice* keys, int n,std::string* dst) const { Slice* mkey =const_cast<Slice*>(keys); for (int i = 0; i < n; i++)mkey[i] = ExtractUserKey(keys[i]); user_policy_->CreateFilter(keys, n, dst); } 8.3 BloomFilter 8.3.1 基本理论 Bloom Filter实际上是一种hash算法，数学之美系列有专门介绍。它是由巴顿.布隆于一九七零年提出的，它实际上是一个很长的二进制向量和一系列随机映射函数。 Bloom Filter将元素映射到一个长度为m的bit向量上的一个bit，当这个bit是1时，就表示这个元素在集合内。使用hash的缺点就是元素很多时可能有冲突，为了减少误判，就使用k个hash函数计算出k个bit，只要有一个bit为0，就说明元素肯定不在集合内。下面的图8.3-1是一个示意图。 在leveldb的实现中，Name()返回"leveldb.BuiltinBloomFilter"，因此metaindex block** 中的key就是”filter.leveldb.BuiltinBloomFilter”。Leveldb使用了double hashing来模拟多个hash函数，当然这里不是用来解决冲突的。 和线性再探测（linearprobing）一样，Double hashing从一个hash值开始，重复向前迭代，直到解决冲突或者搜索完hash表。不同的是，double hashing使用的是另外一个hash函数，而不是固定的步长。 给定两个独立的hash函数h1和h2，对于hash表T和值k，第i次迭代计算出的位置就是：h(i, k) = (h1(k) + i*h2(k)) mod |T|。 对此，Leveldb选择的hash函数是：...

leveldb源码分析13 本系列《leveldb源码分析》共有22篇文章，这是第十三篇 8.FilterPolicy&Bloom之二 8.5 构建FilterBlock 8.5.1 FilterBlockBuilder 了解了filter机制，现在来看看filter block的构建，这就是类FilterBlockBuilder。它为指定的table构建所有的filter，结果是一个string字符串，并作为一个block存放在table中。它有三个函数接口： // 开始构建新的filter block，TableBuilder在构造函数和Flush中调用 void StartBlock(uint64_tblock_offset); // 添加key，TableBuilder每次向data block中加入key时调用 void AddKey(const Slice&key); // 结束构建，TableBuilder在结束对table的构建时调用 Slice Finish(); FilterBlockBuilder的构建顺序必须满足如下范式：(StartBlock AddKey*)* Finish，显然这和前面讲过的BlockBuilder有所不同。 其成员变量有： const FilterPolicy* policy_; // filter类型，构造函数参数指定 std::string keys_; //Flattened key contents std::vector<size_t> start_; // 各key在keys_中的位置 std::string result_; // 当前计算出的filter data std::vector<uint32_t>filter_offsets_; // 各个filter在result_中的位置 std::vector<Slice> tmp_keys_;// policy_->CreateFilter()参数 前面说过base是2KB，这对应两个常量kFilterBase =11, kFilterBase =(1<<kFilterBaseLg)；其实从后面的实现来看tmp_keys_完全不必作为成员变量，直接作为函数GenerateFilter()的栈变量就可以。下面就分别分析三个函数接口。 8.5.2 FilterBlockBuilder::StartBlock() 它根据参数block_offset计算出filter index，然后循环调用GenerateFilter生产新的Filter。 uint64_t filter_index =(block_offset / kFilterBase); assert(filter_index >=filter_offsets_.size()); while (filter_index >filter_offsets_.size()) GenerateFilter(); 我们来到GenerateFilter这个函数，看看它的逻辑。 //S1 如果filter中key个数为0，则直接压入result_.size()并返回 const size_t num_keys =start_.size(); if (num_keys == 0) { // there are no keys for this filter filter_offsets_.push_back(result_.size()); //result_.size()应该是0 return; } //S2 从key创建临时key list，根据key的序列字符串kyes_和各key在keys_ //中的开始位置start_依次提取出key。 start_....

leveldb源码分析14 本系列《leveldb源码分析》共有22篇文章，这是第十四篇 9 LevelDB框架之1 到此为止，基本上Leveldb的主要功能组件都已经分析完了，下面就是把它们组合在一起，形成一个高性能的k/v存储系统。这就是leveldb::DB类。 这里先看一下LevelDB的导出接口和涉及的类，后面将依次以接口分析的方式展开。 而实际上leveldb::DB只是一个接口类，真正的实现和框架类是DBImpl这个类，正是它集合了上面的各种组件。 此外，还有Leveldb对版本的控制，执行版本控制的是Version和VersionSet类。 在leveldb的源码中，DBImpl和VersionSet是两个庞然大物，体量基本算是最大的。对于这两个类的分析，也会分散在打开、销毁和快照等等这些功能中，很难在一个地方集中分析。 作者在文档impl.html中描述了leveldb的实现，其中包括文件组织、compaction和recovery等等。下面的9.1和9.2基本都是翻译子impl.html文档。 在进入框架代码之前，先来了解下leveldb的文件组织和管理。 9.1 DB文件管理 9.1.1 文件类型 对于一个数据库Level包含如下的6种文件: 1/[0-9]+.log：db操作日志 这就是前面分析过的操作日志，log文件包含了最新的db更新，每个更新都以append的方式追加到文件结尾。当log文件达到预定大小时（缺省大约4MB），leveldb就把它转换为一个有序表（如下-2），并创建一个新的log文件。 当前的log文件在内存中的存在形式就是memtable，每次read操作都会访问memtable，以保证read读取到的是最新的数据。 2/[0-9]+.sst：db的sstable文件 这两个就是前面分析过的静态sstable文件，sstable存储了以key排序的元素。每个元素或者是key对应的value，或者是key的删除标记（删除标记可以掩盖更老sstable文件中过期的value）。 Leveldb把sstable文件通过level的方式组织起来，从log文件中生成的sstable被放在level 0。当level 0的sstable文件个数超过设置（当前为4个）时，leveldb就把所有的level 0文件，以及有重合的level 1文件merge起来，组织成一个新的level 1文件（每个level 1文件大小为2MB）。 Level 0的SSTable文件（后缀为.sst）和Level>1的文件相比有特殊性：这个层级内的.sst文件，两个文件可能存在key重叠。对于Level>0，同层sstable文件的key不会重叠。考虑level>0，level中的文件的总大小超过10^level MB时（如level=1是10MB，level=2是100MB），那么level中的一个文件，以及所有level+1中和它有重叠的文件，会被merge到level+1层的一系列新文件。Merge操作的作用是将更新从低一级level迁移到最高级，只使用批量读写（最小化seek操作，提高效率）。 3/MANIFEST-[0-9]+：DB元信息文件 它记录的是leveldb的元信息，比如DB使用的Comparator名，以及各SSTable文件的管理信息：如Level层数、文件名、最小key和最大key等等。 4/CURRENT：记录当前正在使用的Manifest文件 它的内容就是当前的manifest文件名；因为在LevleDb的运行过程中，随着Compaction的进行，新的SSTable文件被产生，老的文件被废弃。并生成新的Manifest文件来记载sstable的变动，而CURRENT则用来记录我们关心的Manifest文件。 当db被重新打开时，leveldb总是生产一个新的manifest文件。Manifest文件使用log的格式，对服务状态的改变（新加或删除的文件）都会追加到该log中。 上面的log文件、sst文件、清单文件，末尾都带着序列号，其序号都是单调递增的（随着next_file_number从1开始递增），以保证不和之前的文件名重复。 5/log：系统的运行日志，记录系统的运行信息或者错误日志。 6/dbtmp：临时数据库文件，repair时临时生成的。 这里就涉及到几个关键的number计数器，log文件编号，下一个文件（sstable、log和manifest）编号，sequence。 所有正在使用的文件编号，包括log、sstable和manifest都应该小于下一个文件编号计数器。 9.1.2 Level 0 当操作log超过一定大小时（缺省是1MB），执行如下操作： S1 创建新的memtable和log文件，并重导向新的更新到新memtable和log中； S2 在后台： S2.1 将前一个memtable的内容dump到sstable文件； S2.2 丢弃前一个memtable； S2.3 删除旧的log文件和memtable S2.4 把创建的sstable文件放到level 0 9.2 Compaction 当level L的总文件大小查过限制时，我们就在后台执行compaction操作。Compaction操作从level L中选择一个文件f，以及选择中所有和f有重叠的文件。如果某个level (L+1)的文件ff只是和f部分重合，compaction依然选择ff的完整内容作为输入，在compaction后f和ff都会被丢弃。 另外：因为level 0有些特殊（同层文件可能有重合），从level 0到level 1的compaction就需要特殊对待：level 0的compaction可能会选择多个level 0文件，如果它们之间有重叠。 Compaction将选择的文件内容merge起来，并生成到一系列的level (L+1)文件中，如果输出文件超过设置（2MB），就切换到新的。当输出文件的key范围太大以至于和超过10个level (L+2)文件有重合时，也会切换。后一个规则确保了level (L+1)的文件不会和过多的level (L+2)文件有重合，其后的level (L+1) compaction不会选择过多的level (L+2)文件。 老的文件会被丢弃，新创建的文件将加入到server状态中。 Compaction操作在key空间中循环执行，详细讲一点就是，对于每个level，我们记录上次compaction的ending key。Level的下一次compaction将选择ending key之后的第一个文件（如果这样的文件不存在，将会跳到key空间的开始）。 Compaction会忽略被写覆盖的值，如果更高一层的level没有文件的范围包含了这个key，key的删除标记也会被忽略。 9.2.1 时间 Level 0的compaction最多从level 0读取4个1MB的文件，以及所有的level 1文件（10MB），也就是我们将读取14MB，并写入14BM。 Level > 0的compaction，从level L选择一个2MB的文件，最坏情况下，将会和levelL+1的12个文件有重合（10：level L+1的总文件大小是level L的10倍；边界的2：level L的文件范围通常不会和level L+1的文件对齐）。因此Compaction将会读26MB，写26MB。对于100MB/s的磁盘IO来讲，compaction将最坏需要0.5秒。 如果磁盘IO更低，比如10MB/s，那么compaction就需要更长的时间5秒。如果user以10MB/s的速度写入，我们可能生成很多level 0文件（50个来装载5*10MB的数据）。这将会严重影响读取效率，因为需要merge更多的文件。 解决方法1：为了降低该问题，我们可能想增加log切换的阈值，缺点就是，log文件越大，对应的memtable文件就越大，这需要更多的内存。 解决方法2：当level 0文件太多时，人工降低写入速度。 解决方法3：降低merge的开销，如把level 0文件都无压缩的存放在cache中。...

leveldb源码分析15 本系列《leveldb源码分析》共有22篇文章，这是第十五篇 9 LevelDB框架之2 9.4 版本控制 当执行一次compaction后，Leveldb将在当前版本基础上创建一个新版本，当前版本就变成了历史版本。还有，如果你创建了一个Iterator，那么该Iterator所依附的版本将不会被leveldb删除。 在leveldb中，Version就代表了一个版本，它包括当前磁盘及内存中的所有文件信息。在所有的version中，只有一个是CURRENT。 VersionSet是所有Version的集合，这是个version的管理机构。 前面讲过的VersionEdit记录了Version之间的变化，相当于delta增量，表示又增加了多少文件，删除了文件。也就是说：Version0 + VersionEdit –> Version1。 每次文件有变动时，leveldb就把变动记录到一个VersionEdit变量中，然后通过VersionEdit把变动应用到current version上，并把current version的快照，也就是db元信息保存到MANIFEST文件中。 另外，MANIFEST文件组织是以VersionEdit的形式写入的，它本身是一个log文件格式，采用log::Writer/Reader的方式读写，一个VersionEdit就是一条log record。 9.4.1 VersionSet 和DBImpl一样，下面就初识一下Version和VersionSet。 先来看看Version的成员： std::vector<FileMetaData*>files_[config::kNumLevels]; // sstable文件列表 // Next fileto compact based on seek stats. 下一个要compact的文件 FileMetaData* file_to_compact_; int file_to_compact_level_; // 下一个应该compact的level和compaction分数. // 分数 < 1 说明compaction并不紧迫. 这些字段在Finalize()中初始化 double compaction_score_; int compaction_level_; 可见一个Version就是一个sstable文件集合，以及它管理的compact状态。Version通过Version* prev和*next指针构成了一个Version双向循环链表，表头指针则在VersionSet中（初始都指向自己）。 下面是VersionSet的成员。可见它除了通过Version管理所有的sstable文件外，还关心manifest文件信息，以及控制log文件等编号。 //=== 第一组，直接来自于DBImple，构造函数传入 Env* const env_; // 操作系统封装 const std::string dbname_; const Options* const options_; TableCache* const table_cache_; // table cache const InternalKeyComparatoricmp_; //=== 第二组，db元信息相关 uint64_t next_file_number_; // log文件编号 uint64_t manifest_file_number_; // manifest文件编号 uint64_t last_sequence_; uint64_t log_number_; // log编号 uint64_t prev_log_number_; // 0 or backingstore for memtable being compacted //=== 第三组，menifest文件相关 WritableFile* descriptor_file_; log::Writer* descriptor_log_; //=== 第四组，版本管理 Version dummy_versions_; // versions双向链表head....

Leveldb源码分析16 本系列《leveldb源码分析》共有22篇文章，这是第十六篇 10.Version分析之一 先来分析leveldb对单版本的sstable文件管理，主要集中在Version类中。前面的10.4节已经说明了Version类的功能和成员，这里分析其函数接口和代码实现。 Version不会修改其管理的sstable文件，只有读取操作。 10.1 Version接口 先来看看Version类的接口函数，接下来再一一分析。 // 追加一系列iterator到 @*iters中， //将在merge到一起时生成该Version的内容 // 要求: Version已经保存了(见VersionSet::SaveTo) void AddIterators(constReadOptions&, std::vector<Iterator*>* iters); // 给定@key查找value，如果找到保存在@*val并返回OK。 // 否则返回non-OK，设置@ *stats. // 要求：没有hold lock struct GetStats { FileMetaData* seek_file; int seek_file_level; }; Status Get(constReadOptions&, const LookupKey& key, std::string* val,GetStats* stats); // 把@stats加入到当前状态中，如果需要触发新的compaction返回true // 要求：hold lock bool UpdateStats(constGetStats& stats); void GetOverlappingInputs(intlevel, const InternalKey*begin, // NULL 指在所有key之前 const InternalKey* end, // NULL指在所有key之后 std::vector<FileMetaData*>* inputs); // 如果指定level中的某些文件和[*smallest_user_key,*largest_user_key] //有重合就返回true。 // @smallest_user_key==NULL表示比DB中所有key都小的key. // @largest_user_key==NULL表示比DB中所有key都大的key. bool OverlapInLevel(int level,const Slice*smallest_user_key, const Slice* largest_user_key); // 返回我们应该在哪个level上放置新的memtable compaction， // 该compaction覆盖了范围[smallest_user_key,largest_user_key]. int PickLevelForMemTableOutput(const Slice& smallest_user_key, const Slice& largest_user_key); // 指定level的sstable个数 int NumFiles(int level) const {return files_[level].size(); 10.2 Version::AddIterators() 该函数最终在DB::NewIterators()接口中被调用，调用层次为： DBImpl::NewIterator()->DBImpl::NewInternalIterator()->Version::AddIterators()。 函数功能是为该Version中的所有sstable都创建一个Two Level Iterator，以遍历sstable的内容。...

leveldb源码分析17 本系列《leveldb源码分析》共有22篇文章，这是第十七篇 10 Version分析之2 10.5 Version::UpdateStats() 当Get操作直接搜寻memtable没有命中时，就需要调用Version::Get()函数从磁盘load数据文件并查找。如果此次Get不止seek了一个文件，就记录第一个文件到stat并返回。其后leveldb就会调用UpdateStats(stat)。 Stat表明在指定key range查找key时，都要先seek此文件，才能在后续的sstable文件中找到key。 该函数是将stat记录的sstable文件的allowed_seeks减1，减到0就执行compaction。也就是说如果文件被seek的次数超过了限制，表明读取效率已经很低，需要执行compaction了。所以说allowed_seeks是对compaction流程的有一个优化。 函数声明：boolVersion::UpdateStats(const GetStats& stats) 函数逻辑很简单： FileMetaData* f =stats.seek_file; if (f != NULL) { f->allowed_seeks--; if (f->allowed_seeks <=0 && file_to_compact_ == NULL) { file_to_compact_ = f; file_to_compact_level_ =stats.seek_file_level; return true; } } return false; 变量allowed_seeks的值在sstable文件加入到version时确定，也就是后面将遇到的VersionSet::Builder::Apply()函数。 10.6 Version::GetOverlappingInputs() 它在指定level中找出和**[begin, end]**有重合的sstable文件，函数声明为： void Version::GetOverlappingInputs(int level, const InternalKey* begin, constInternalKey* end, std::vector<FileMetaData*>* inputs); 要注意的是，对于level0，由于文件可能有重合，其处理具有特殊性。当在level 0中找到有sstable文件和**[begin, end]**重合时，会相应的将begin/end扩展到文件的min key/max key，然后重新开始搜索。 了解了功能，下面分析函数实现代码，逻辑还是很直观的。 S1 首先根据参数初始化查找变量。 inputs->clear(); Slice user_begin, user_end; if (begin != NULL) user_begin =begin->user_key(); if (end != NULL) user_end = end->user_key(); const Comparator* user_cmp =vset_->icmp_.user_comparator(); S2 遍历该层的sstable文件，比较sstable的**{minkey,max key}和传入的[begin, end]**，如果有重合就记录文件到@inputs中，需要对level 0做特殊处理。 for (size_t i = 0; i <files_[level].size(); ) { FileMetaData* f =files_[level][i++]; const Slice file_start =f->smallest....

leveldb源码分析18 本系列《leveldb源码分析》共有22篇文章，这是第十八篇 11 VersionSet分析之1 Version之后就是VersionSet，它并不是Version的简单集合，还肩负了不少的处理逻辑。这里的分析不涉及到compaction相关的部分，这部分会单独分析。包括log等各种编号计数器，compaction点的管理等等。 11.1 VersionSet接口 1 首先是构造函数，VersionSet会使用到TableCache，这个是调用者传入的。TableCache用于Get k/v操作。 VersionSet(const std::string& dbname, const Options* options, TableCache*table_cache, const InternalKeyComparator*); VersionSet的构造函数很简单，除了根据参数初始化，还有两个地方值得注意： N1 next_file_number_从2开始； N2 创建新的Version并加入到Version链表中，并设置CURRENT=新创建version； 其它的数字初始化为0，指针初始化为NULL。 2 恢复函数，从磁盘恢复最后保存的元信息 Status Recover(); 3 标记指定的文件编号已经被使用了 void MarkFileNumberUsed(uint64_t number); 逻辑很简单，就是根据编号更新文件编号计数器： if (next_file_number_ <= number) next_file_number_ = number + 1; 4 在current version上应用指定的VersionEdit，生成新的MANIFEST信息，保存到磁盘上，并用作current version。 要求：没有其它线程并发调用；要用于mu； Status LogAndApply(VersionEdit* edit, port::Mutex* mu)EXCLUSIVE_LOCKS_REQUIRED(mu); 5 对于@v中的@key，返回db中的大概位置 uint64_t ApproximateOffsetOf(Version* v, const InternalKey& key); 6 其它一些简单接口，信息获取或者设置，如下： //返回current version Version* current() const { return current_; } // 当前的MANIFEST文件号 uint64_t ManifestFileNumber() const { return manifest_file_number_; } // 分配并返回新的文件编号 uint64_t NewFileNumber() { return next_file_number_++; } // 返回当前log文件编号 uint64_t LogNumber() const { return log_number_; } // 返回正在compact的log文件编号，如果没有返回0 uint64_t PrevLogNumber() const { return prev_log_number_; } // 获取、设置last sequence，set时不能后退 uint64_t LastSequence() const { return last_sequence_; } void SetLastSequence(uint64_t s) { assert(s >=last_sequence_); last_sequence_ = s; } // 返回指定level中所有sstable文件大小的和 int64_t NumLevelBytes(int level) const; // 返回指定level的文件个数 int NumLevelFiles(int level) const; // 重用@file_number，限制很严格：@file_number必须是最后分配的那个 // 要求: @file_number是NewFileNumber()返回的....

leveldb源码分析19 本系列《leveldb源码分析》共有22篇文章，这是第十九篇 11.VersionSet分析之2 11.4 LogAndApply() 函数声明： Status LogAndApply(VersionEdit*edit, port::Mutex* mu) 前面接口小节中讲过其功能：在currentversion上应用指定的VersionEdit，生成新的MANIFEST信息，保存到磁盘上，并用作current version，故为Log And Apply。 参数edit也会被函数修改。 11.4.1 函数流程 下面就来具体分析函数代码。 S1 为edit设置log number等4个计数器。 if (edit->has_log_number_) { assert(edit->log_number_ >= log_number_); assert(edit->log_number_ < next_file_number_); } else edit->SetLogNumber(log_number_); if (!edit->has_prev_log_number_) edit->SetPrevLogNumber(prev_log_number_); edit->SetNextFile(next_file_number_); edit->SetLastSequence(last_sequence_); 要保证edit自己的log number是比较大的那个，否则就是致命错误。保证edit的log number小于next file number，否则就是致命错误-见9.1小节。 S2 创建一个新的Version v，并把新的edit变动保存到v中。 Version* v = new Version(this); { Builder builder(this, current_); builder.Apply(edit); builder.SaveTo(v); } Finalize(v); //如前分析，只是为v计算执行compaction的最佳level S3 如果MANIFEST文件指针不存在，就创建并初始化一个新的MANIFEST文件。这只会发生在第一次打开数据库时。这个MANIFEST文件保存了current version的快照。 std::string new_manifest_file; Status s; if (descriptor_log_ == NULL) { // 这里不需要unlock *mu因为我们只会在第一次调用LogAndApply时 // 才走到这里(打开数据库时). assert(descriptor_file_ == NULL); // 文件指针和log::Writer都应该是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_); // 写入快照 } } S4 向MANIFEST写入一条新的log，记录current version的信息。在文件写操作时unlock锁，写入完成后，再重新lock，以防止浪费在长时间的IO操作上。...