开发单机存储需要考虑的技术点及代码实现

网络模型。cli
内存结构
文件结构。写入的 buf,flush,sync。页保证完整性
内存池
并发。网络，写入并发（批量写入，写 log 并发，写文件落盘并发，compact 并发）
ACID 版本控制，日志
cache
复制
备份，快照
崩溃恢复

崩溃恢复

先从 manifest 恢复 version.version_set,logid,seqid 等，先合并删除再 manifest 再改 current 和 versionset。再获取所有日志，比较 log>manifest 中的 log 的进行恢复。到 mem 可能还要 compact。manifest 若是未写成功则就当没有此次压缩。如果 log 未写成功，则 mem 不会有此数据。

并发

只有个批量写入 log 和 mem

版本控制

见其他两篇文章，一个是读取内存时候比较 seq。
一个是文件中 compact 后维护不同 version。对不同 version 如果有引用则不删除，manifest 中维护所有 open 以来的版本。详见另外两篇
若不带 snapshot。赋值为 snapshot = versions_->LastSequence();
文件的 Version* current = versions_->current();
根据 snapshot 的 seq 构造 key 比较查找。每个的引用次数 ++，结束后 –。每次 compact 结束后决定是否删除。

cache

http://www.pandademo.com/2016…
上面这个说的不错，两层，一个是文件索引的 cache，调用 Table::Open 读取 footer,index 等，block_cache 分片的，找到文件后定位到哪个 block_cache，cache 中是块信息。

内存结构

跳表，两个 mem 切换

文件结构

内存维护 buf。4k 一次调用 write 写入一个块。64k 补一个 sync。
页完整的保证：mysql 的二次写，mongodb 的固定块大小。
leveldb
1.log 写入：若 Block 已经小于 header，填充 0 下一个 Block。否则写入 block 剩余和 left 小的，加入 first 等标识。一段调一次加入头信息 /crc32c 校验和和数据，走 append 和 flush。每段日志都会 write。block 为 32k 一个大小
2.log 读取：每 32k 读一次。校验和，读类型等，若未到结尾继续读，若校验和等出错，抛弃 32k，继续读。考虑每次出问题的时候有一个块可能部分写。抛弃读取部分，但每次恢复遇到问题会指向下一个块或者读取部分就好。
3. 数据写入：4k 加一个 index。调用一次 write。一个 table 一次 fsync
提供的 file->append 每 64K 一个 buffer. 但是数据和日志都分别在外面调用 flush 保证 4k 一次 write，和一条日志一次 write。
数据 4k 一个校验和写入，其他 filter_block,meta_index_block,index_block,rooter 算好最后在写入
每 4 看写入所有重启点（16 个一个，重启点是指向重启点的 offset），压缩，写入文件，写入检验和
4. 数据读取：mm->imm->current->get
table_cache_->Get. sst 文件放入 table_cache
Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator);
iiter->Seek(k);
Iterator* block_iter = BlockReader(this, options, iiter->value());
block_iter->Seek(k);
到 BlockReader：
Cache* block_cache = table->rep_->options.block_cache;
block_cache 没有，ReadBlock
Status s = file->Read(handle.offset(), n + kBlockTrailerSize, &contents, buf);
校验，解压缩，校验不对直接返回错误。在一个块里搜索通过二分重启点，后线性找记录。数据校验有问题的直接错误并不处理。（看看 recover 会处理吗）

内存池：

glibc malloc 和 C ++ 标准库的 new 返回的地址均是内存对齐的，这里由于是定制内存分配，指针预分配的大块内存（page 页面大小），当连续分配小块内存时就需要做额外对齐。内存对齐有利于提高访存速度，因为内存按字节编址，根据 CPU 字长即 sizeof(void *)大小做对齐，有利于减少访存指令次数，防止跨对齐边界访存，也能充分利用硬件体系，提高 CPU 性能。

 char* alloc_ptr_;
 size_t alloc_bytes_remaining_;
 std::vector<char*> blocks_;

inline char* Arena::Allocate(size_t bytes) {assert(bytes > 0);
  if (bytes <= alloc_bytes_remaining_) {
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }
  return AllocateFallback(bytes);
}
char* Arena::AllocateFallback(size_t bytes) {if (bytes > kBlockSize / 4) {char* result = AllocateNewBlock(bytes);
    return result;
  }

  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}
char* Arena::AllocateNewBlock(size_t block_bytes) {char* result = new char[block_bytes];
  blocks_.push_back(result);
  memory_usage_.fetch_add(block_bytes + sizeof(char*),
                          std::memory_order_relaxed);
  return result;
}

对其版本：每次从 8 申请
char* Arena::AllocateAligned(size_t bytes) {const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1);
  size_t slop = (current_mod == 0 ? 0 : align - current_mod);
  size_t needed = bytes + slop;
  char* result;
  if (needed <= alloc_bytes_remaining_) {
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  } else {
    // AllocateFallback always returned aligned memory
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == 0);
  return result;
}