1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

/*同步，回调函数，引用计数，深拷贝*/
#ifndef STORAGE_LEVELDB_INCLUDE_CACHE_H_
#define STORAGE_LEVELDB_INCLUDE_CACHE_H_

#include <cstdint>

#include "leveldb/export.h"
#include "leveldb/slice.h"

namespace leveldb {

  // cache的缓存接口
class LEVELDB_EXPORT Cache;

LEVELDB_EXPORT Cache* NewLRUCache(size_t capacity);

class LEVELDB_EXPORT Cache {
 public:
  Cache() = default;

  Cache(const Cache&) = delete;
  Cache& operator=(const Cache&) = delete;

  // 回调函数销毁缓存的内容
  virtual ~Cache();

  // 指向cache中的一个缓存项
  struct Handle {};

  virtual Handle* Insert(const Slice& key, void* value, size_t charge, void (*deleter)(const Slice& key, void* value)) = 0;

  virtual Handle* Lookup(const Slice& key) = 0;
    
  virtual void Release(Handle* handle) = 0;
  virtual void* Value(Handle* handle) = 0;.
      
  virtual void Erase(const Slice& key) = 0
      
  virtual uint64_t NewId() = 0;
  virtual void Prune() {}

  virtual size_t TotalCharge() const = 0;
};

}  // namespace leveldb

#endif  // STORAGE_LEVELDB_INCLUDE_CACHE_H_

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 缓存项的结构体
struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value);
  LRUHandle* next_hash; // 哈希表handleTable为了解决哈希冲突采用拉链法的链指针
  LRUHandle* next; // 双向链表
  LRUHandle* prev;
  size_t charge;  // TODO(opt): Only allow uint32_t?
  size_t key_length;
  bool in_cache;     // Whether entry is in the cache. 
  uint32_t refs;     // References, including cache reference, if present.引用计数
  uint32_t hash;     // Hash of key(); used for fast sharding and comparisons
  char key_data[1];  // Beginning of key

  Slice key() const {
    // next is only equal to this if the LRU handle is the list head of an
    // empty list. List heads never have meaningful keys.
    assert(next != this);

    return Slice(key_data, key_length);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

// 可扩展哈希表
class HandleTable {
 public:
  HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
  ~HandleTable() { delete[] list_; }

  LRUHandle* Lookup(const Slice& key, uint32_t hash) {
    return *FindPointer(key, hash);
  }

  // ptr为空时，新缓存项作为头部，同时elem++检查是否需要扩充空间
  // ptr不为空时，采用头插法
  LRUHandle* Insert(LRUHandle* h) {
    LRUHandle** ptr = FindPointer(h->key(), h->hash);
    LRUHandle* old = *ptr;
    h->next_hash = (old == nullptr ? nullptr : old->next_hash);
    *ptr = h;
    if (old == nullptr) {
      ++elems_;
      if (elems_ > length_) {
        // Since each cache entry is fairly large, we aim for a small
        // average linked list length (<= 1).
        Resize();
      }
    }
    return old;
  }

  LRUHandle* Remove(const Slice& key, uint32_t hash) {
      // 理解二重*的链表
    LRUHandle** ptr = FindPointer(key, hash); // ptr为当前结点地址
    LRUHandle* result = *ptr;
    if (result != nullptr) {
      // *ptr就是当前结点的前一个结点，ptr为当前结点地址
      // 将当前节点的前一个节点的 next_hash 更新为要删除节点的下一个节点。
      *ptr = result->next_hash; 
      --elems_;
    }
    return result;
  }

 private:
  // The table consists of an array of buckets where each bucket is
  // a linked list of cache entries that hash into the bucket.
  uint32_t length_; // slot的数量
  uint32_t elems_; // 已经使用的slot数量
  LRUHandle** list_; // handleTable的bucket数组

  // Return a pointer to slot that points to a cache entry that
  // matches key/hash.  If there is no such cache entry, return a
  // pointer to the trailing slot in the corresponding linked list. 正常的查找操作
  LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = &list_[hash & (length_ - 1)];
    // 这里要求找到hash和key都相同的位置，然后建立链表
    // hash是因为哈希冲突，jey则可能因为版本不同的缓存或者缓存项被频繁更新
    while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
      ptr = &(*ptr)->next_hash;
    }
    return ptr;
  }

  // 确立新空间
  // 将旧的哈希表数据重新计算复制到新的哈希表中
  void Resize() {
    uint32_t new_length = 4;
    while (new_length < elems_) {
      new_length *= 2;
    }
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, 0, sizeof(new_list[0]) * new_length);
    uint32_t count = 0;
    // 这里使用头插法时，二重链表中的数据反了，但是并不影响LRU的使用，因为有另外的链表实现LRU机制
    for (uint32_t i = 0; i < length_; i++) {
      LRUHandle* h = list_[i];
      while (h != nullptr) {
        // 保存下一个元素地址
        LRUHandle* next = h->next_hash;
        uint32_t hash = h->hash;
        // 取模，找一个位置
        LRUHandle** ptr = &new_list[hash & (new_length - 1)];
        h->next_hash = *ptr;
        *ptr = h;
        h = next;
        count++;
      }
    }
    assert(elems_ == count);
    delete[] list_;
    list_ = new_list;
    length_ = new_length;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class LRUCache {
 private:
  // 删除结点，添加结点
  void LRU_Remove(LRUHandle* e); 
  void LRU_Append(LRUHandle* list, LRUHandle* e);
  void Ref(LRUHandle* e); // 引用结点，从lru list转移到in use list
  void Unref(LRUHandle* e); // 解引用，变为0时删掉，变为1则放进lru中便于以后变成0删掉
  bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_); // 完全移除e，在此之前已经从哈希表中移除

  // Initialized before use. 容量
  size_t capacity_; 

  // mutex_ protects the following state.
  mutable port::Mutex mutex_;
  size_t usage_ GUARDED_BY(mutex_); // 当前用量

  // Dummy head of LRU list.
  // lru.prev is newest entry, lru.next is oldest entry.
  // Entries have refs==1 and in_cache==true.
  LRUHandle lru_ GUARDED_BY(mutex_); // lru链表 ，缓存项

  // Dummy head of in-use list.
  // Entries are in use by clients, and have refs >= 2 and in_cache==true.
  LRUHandle in_use_ GUARDED_BY(mutex_); // in-use链表，无序保存着在LRUCache中且正在被client使用的LRUHandle

  HandleTable table_ GUARDED_BY(mutex_); // 哈希表，按照最近使用的顺序保存当前在LRUCache中但是目前没有被用户使用的LRUHandl
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

 private:
  // 实现分片的LRU缓存
  LRUCache shard_[kNumShards];
  port::Mutex id_mutex_; // 保护对共享资源的访问，确保线程安全
  uint64_t last_id_;     // 管理缓存项的唯一标识

  static inline uint32_t HashSlice(const Slice& s) {
    // 计算给定对象的哈希值
    return Hash(s.data(), s.size(), 0);
  }

  // 分片，位数为KNumShardBits时，hash二进制右移32-kNumShardBits能得到0---2^kNumShardBits-1的值，类似于提取前kNumShardBits位数。
  // 分片能让多线程访问不同分片，减少竞争；
  // 同时每个分片的数据减少，减少锁的竞争；数据分布均匀，也可以避免某个分片过于繁忙，实现负载均衡
  static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }

1
2
3
4
5
6
7
8

 private:
  // 通过filename找到sstable文件，filesize可以用于验证或者缓存的查找，handle**用于返回找到的缓存项
  Status FindTable(uint64_t file_number, uint64_t file_size, Cache::Handle**);

  Env* const env_; // 指向环境对象的指针
  const std::string dbname_; // 存储数据库的名称或路径
  const Options& options_; // 对于leveldb的配置选项的引用
  Cache* cache_; // 指向缓存对象的指针

1
2
3
4

struct TableAndFile {
  RandomAccessFile* file; // 将数据以sstable的格式持久化存储到磁盘上。
  Table* table; // 作为一个数据结构，封装了与sstable相关的逻辑，比如读取，查找，迭代等
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
* 实现了查找sstable的功能
* 缓存中查找如果失败，
* 会动态打开文件创建表对象，同时插入缓存
* 最终返回状态
*/
Status TableCache::FindTable(uint64_t file_number, uint64_t file_size,
                             Cache::Handle** handle) {
  // 初始化
  Status s;
  char buf[sizeof(file_number)];
  EncodeFixed64(buf, file_number);
  Slice key(buf, sizeof(buf));

  // 查找
  *handle = cache_->Lookup(key);
  if (*handle == nullptr) { // 检查缓存结果，从文件中查找
    std::string fname = TableFileName(dbname_, file_number); // 构造文件名
    RandomAccessFile* file = nullptr; // 初始化指针
    Table* table = nullptr;

    s = env_->NewRandomAccessFile(fname, &file);
    if (!s.ok()) { // 打开文件失败的错误处理
      std::string old_fname = SSTTableFileName(dbname_, file_number);
      if (env_->NewRandomAccessFile(old_fname, &file).ok()) {
        s = Status::OK();
      }
    }
    if (s.ok()) {
      s = Table::Open(options_, file, file_size, &table);
    }

    if (!s.ok()) { // 错误处理
      assert(table == nullptr);
      delete file;
      // We do not cache error results so that if the error is transient,
      // or somebody repairs the file, we recover automatically.
    } else { // 创建新对象插入缓存
      TableAndFile* tf = new TableAndFile;
      tf->file = file;
      tf->table = table;
      *handle = cache_->Insert(key, tf, 1, &DeleteEntry);
    }
  }
  return s;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/*从缓存中获取指定键的值*/
Status TableCache::Get(const ReadOptions& options, uint64_t file_number,
                       uint64_t file_size, const Slice& k, void* arg,
                       void (*handle_result)(void*, const Slice&,
                                             const Slice&)) {
  Cache::Handle* handle = nullptr;
  Status s = FindTable(file_number, file_size, &handle);
    /*TableCache 的 Get 方法能够同时查询这两层缓存。
    首先，它会查找第一层缓存（元数据），获取所需的 SSTable 信息。
    如果该信息存在，接着会使用这些信息查询第二层缓存（BlockCache），获取实际的数据块。
    */
  if (s.ok()) {
    // 查找成功时，从缓存句柄中获取TableAndFile对象，通过类型转换获取内部的table指针
    Table* t = reinterpret_cast<TableAndFile*>(cache_->Value(handle))->table;
      // 切片，参数，回调函数
    s = t->InternalGet(options, k, arg, handle_result); // 获取键值对，同时调用回调函数
    cache_->Release(handle); // 释放缓存句柄，减少引用计数
  }
  return s;
}

/*驱逐指定的sstable*/
void TableCache::Evict(uint64_t file_number) {
  // 创建字符数组，为文件编号编码
  char buf[sizeof(file_number)];
  EncodeFixed64(buf, file_number);
  // 从缓存中删除
  cache_->Erase(Slice(buf, sizeof(buf)));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

 private:
  friend class TableCache;
  struct Rep; // 内部实现结构体，封装table的具体实现细节

  static Iterator* BlockReader(void*, const ReadOptions&, const Slice&);

  /*私有构造函数，接收一个指向 Rep 结构体的指针，初始化 rep_ 成员*/
  explicit Table(Rep* rep) : rep_(rep) {}

  // Calls (*handle_result)(arg, ...) with the entry found after a call
  // to Seek(key).  May not make such a call if filter policy says
  // that key is not present.
  // 在表中查找给定键的条目。如果找到了，将调用 handle_result 函数处理结果
  Status InternalGet(const ReadOptions&, const Slice& key, void* arg,
                     void (*handle_result)(void* arg, const Slice& k,
                                           const Slice& v));

  // 读取元数据和过滤器的相关函数
  void ReadMeta(const Footer& footer);
  void ReadFilter(const Slice& filter_handle_value);

  Rep* const rep_;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Status Table::InternalGet(const ReadOptions& options, const Slice& k, void* arg, oid (*handle_result)(void*, const Slice&, const Slice&)) {
    // 获取indexblock的iterator
    Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator);
    iiter->Seek(k); /*1.键的查找*/
if (iiter->Valid()) {
    Slice handle_value = iiter->value(); /*2.获取与键关联的值，这个值中存储了datablock的位置，datablock存在磁盘中，减少io次数*/
    FilterBlockReader* filter = rep_->filter; /*3.获取过滤器，过滤器中可以查看数据是否存在*/
        BlockHandle handle;
    if (filter != nullptr && handle.DecodeFrom(&handle_value).ok() &&
        !filter->KeyMayMatch(handle.offset(), k)) {
      // 过滤器为空且键可能不匹配
        // not found
    } else {
      /*4.过滤器顺利找到，根据value查找相应的数据块中的迭代器*/
      Iterator* block_iter = BlockReader(this, options, iiter->value());
      block_iter->Seek(k); /* 5.在数据块中查找key*/
      if (block_iter->Valid()) {
          // 找到时采用handle_result 处理结果
        (*handle_result)(arg, block_iter->key(), block_iter->value());
      }
      // 更新状态
      s = block_iter->status();
      delete block_iter;
    }
  }
  if (s.ok()) {
    s = iiter->status();
  }
  delete iiter;
  return s;
}
}

1
2
3
4
5
6
7

/*
* 读取sstable中的footer，加载其filter block和index block的数据到内存
* 为table分配一个cache_id
* 在通过Table读取其中DataBlock的数据时，
* 会拼接cache_id与Block的offset拼接作为BlockCache的key。
*/
Status Table::Open(const Options& options, RandomAccessFile* file,  uint64_t size, Table** table) {...}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

在你提供的代码中，LevelDB 定义了几个关键的结构体，主要包括 `Options`、`ReadOptions` 和 `WriteOptions`。以下是对这些结构体的详细介绍：

### 1. `Options`

`Options` 结构体用于控制数据库的行为，包含多个参数，影响数据库的打开、性能和数据存储等。主要字段包括：

- **`comparator`**：用于定义键的顺序的比较器。
- **`create_if_missing`**：如果数据库不存在，是否创建新的数据库。
- **`error_if_exists`**：如果数据库已经存在，是否报错。
- **`paranoid_checks`**：是否进行严格的数据完整性检查。
- **`env`**：与环境交互的对象（如读写文件等）。
- **`info_log`**：用于记录信息和错误的日志记录器。
- **`write_buffer_size`**：内存中写缓冲区的大小。
- **`max_open_files`**：数据库可以打开的最大文件数量。
- **`block_cache`**：用于缓存块的对象。
- **`block_size`**：每个块的近似大小。
- **`block_restart_interval`**：用于键的增量编码的重启点之间的键数量。
- **`max_file_size`**：写入文件的最大字节数。
- **`compression`**：用于块的压缩算法。
- **`zstd_compression_level`**：zstd 压缩的压缩级别。
- **`reuse_logs`**：是否在打开数据库时追加到现有的 MANIFEST 和日志文件。
- **`filter_policy`**：用于减少磁盘读取的过滤策略。

### 2. `ReadOptions`

`ReadOptions` 结构体控制读取操作的行为，包含以下字段：

- **`verify_checksums`**：是否在读取时验证校验和。
- **`fill_cache`**：读取的数据是否应被缓存。
- **`snapshot`**：用于读取的快照对象。

### 3. `WriteOptions`

`WriteOptions` 结构体控制写入操作的行为，包含以下字段：

- **`sync`**：是否在写入完成前将数据刷新到操作系统的缓冲区。设置为 `true` 会使写入变慢，但可以确保写入数据的持久性。

这些结构体的设计使得 LevelDB 能够灵活配置数据库的行为，以适应不同的使用场景和性能需求。