leveldb注释8–snapshot机制

snapshot，也就是快照机制的作用，就是使得读操作不受写操作影响。其巧妙的使用了SequenceNumber来实现这一机制。

上一节中，我们知道，SequenceNumber使得对写入的任何key在内部存储时都会附加一个递增的SequenceNumber。而在leveldb内部，一次snapshot也对应一个全局唯一的SequenceNumber。因此，在调用GetSnapshot获取snapshot时，leveldb所做的仅仅是生成一个SequenceNumber。db内部使用双向循环链表保存先后生成的snapshot。获取快照GetSnapshot会将新snapshot加入链表，而释放快照ReleaseSnapshot则将snapshot从链表中删除。DBImpl类中的snapshots_成员就是这个链表。这部分代码主要在snapshot.h与db_impl.cc/.h中。代码很简单，内部是一个双向循环链表的封装。

const Snapshot* DBImpl::GetSnapshot() {
  MutexLock l(&mutex_);
  return snapshots_.New(versions_->LastSequence());
}

snapshot机制主要会影响指定的读操作与所有后续的压缩操作，直到该snapshot释放。

从前面的使用接口章节中，我们知道，当读操作Get函数指定snapshot选项时，从snapshot生成至Get函数调用的这段时间里的写入操作对该次读没有影响。当指定snapshot时，Get函数会使用这个snapshot的sequencenumber+输入的key来构造要查找的LookupKey（没有指定snapshot，则使用当前已使用的最大sequencenumber）。而对于要查找的数据结构memtable、immunable memtable与sstable来讲，其内部存储的”key”都是带sequencenumber的（上一章节的分析），其最终查找到的”key”会满足key == 输入的key，而sequencenumber<=Get函数传入的sequencenumber。这样，对于那些key相同但sequencenumber比较大（也就是后续针对同一个key做写入操作）的slice，则查找不到，自动的被屏蔽掉了。关于读操作Get的详细细节，我们在后续章节进行分析。

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   std::string* value) {
  Status s;
  MutexLock l(&mutex_);
  SequenceNumber snapshot;
  if (options.snapshot != NULL) {
    snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
  } else {
    snapshot = versions_->LastSequence();
  }

  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != NULL) imm->Ref();
  current->Ref();
  —
  {
    mutex_.Unlock();
    // mem与imm是带sequence_number以保证不会查到新数据
    // 查找顺序依次是：memtable、immutable memtable、sstable文件
    // First look in the memtable, then in the immutable memtable (if any).
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // Done
    } else if (imm != NULL && imm->Get(lkey, value, &s)) {
      // Done
    } else {
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
    }
    —
  }

leveldb的snapshot机制不会在snapshot生成时直接影响系统，而是通过影响压缩操作来影响。比如redis的快照机制，其生成快照时，相当于dump整个内存中的db。
通过前面的Get分析，我们知道，因为SequenceNumber对查找的影响，使得后续的写是完全透明的。但compact操作会将写入的值与已有的值进行合并。这样，后续写入的值可能会覆盖前面已写过的值或者后续的删除操作删除了该key。实际上，在进行major compact时（minor compact只是将immunable memtable转储至1个level 0的sstable文件），会检查这些(key,value)的sequencenumber。当有相同key的多个操作序列时，正常情况下，只会按操作第一个序列（也就是最新的），后续的直接drop。但snapshot机制，会使得对于这些多个操作序列的除第一个之外的操作，只有sequencenumber比系统中最小的snapshot还小的才丢弃（实际细节比这个还复杂点）。这样，这些操作序列都会被保存下来用于后续的snapshot操作。这部分代码主要在DBImpl::DoCompactionWork函数中，更多细节有待我们讲述压缩机制时再来分析。

Status DBImpl::DoCompactionWork(CompactionState* compact) {
   ---
   if (snapshots_.empty()) {
    compact->smallest_snapshot = versions_->LastSequence();
  } else {
    compact->smallest_snapshot = snapshots_.oldest()->number_;
  }
  ---
  Iterator* input = versions_->MakeInputIterator(compact->compaction);
  input->SeekToFirst();
  Status status;
  ParsedInternalKey ikey;
  std::string current_user_key;
  bool has_current_user_key = false;
  SequenceNumber last_sequence_for_key = kMaxSequenceNumber;
  // 遍历输入
  for (; input->Valid() && !shutting_down_.Acquire_Load(); ) {
    // Prioritize immutable compaction work
    if (has_imm_.NoBarrier_Load() != NULL) {
      ---
    }

    Slice key = input->key();
    if (compact->compaction->ShouldStopBefore(key) &&
        compact->builder != NULL) {
        // 输出新文件
      status = FinishCompactionOutputFile(compact, input);
      if (!status.ok()) {
        break;
      }
    }

    // Handle key/value, add to state, etc.
    bool drop = false;
    // 因为有delete、多次插入，同一个key可能出现多次
    if (!ParseInternalKey(key, &ikey)) {
      // Do not hide error keys
      current_user_key.clear();
      has_current_user_key = false;
      last_sequence_for_key = kMaxSequenceNumber;
    } else {
      if (!has_current_user_key ||
         // 注意这里的比较是直接比较user_key，也就是不带sequencenumber
          user_comparator()->Compare(ikey.user_key,
                                     Slice(current_user_key)) != 0) {
        // First occurrence of this user key
        current_user_key.assign(ikey.user_key.data(), ikey.user_key.size());
        has_current_user_key = true;
        last_sequence_for_key = kMaxSequenceNumber;
      }

      if (last_sequence_for_key <= compact->smallest_snapshot) {
        // Hidden by an newer entry for same user key
        // 多个key，后续的是更老的，直接drop，保留第一个
        drop = true;    // (A)
      } else if (ikey.type == kTypeDeletion &&
                 ikey.sequence <= compact->smallest_snapshot &&
                 compact->compaction->IsBaseLevelForKey(ikey.user_key)) {
        // For this user key:
        // (1) there is no data in higher levels
        // (2) data in lower levels will have larger sequence numbers
        // (3) data in layers that are being compacted here and have
        //     smaller sequence numbers will be dropped in the next
        //     few iterations of this loop (by rule (A) above).
        // Therefore this deletion marker is obsolete and can be dropped.
        drop = true;
      }

      last_sequence_for_key = ikey.sequence;
    }
    ---

由于snapshot对压缩机制有影响，对snapshot后续插入的多个值都不会压缩。因此在使用时，用完后要尽可能快释放。