The structure of BlockCache explains in this article that it has been explained in this articleLeveldb Internal Cache structure description。
Blockcache’s cache is the actual KV data, which is DataBlock data. In order to facilitate understanding, you can see the following bloccache structural diagram:
Figure 1
BlockCache：
- key：6 6 6 6 6 6 6 6 6 6 6 6 6 6 in the LDB file.
- Value：is the real blockdata data.
Note:
Because the BlockData in the open LDB (that is, SST) files is all stored in the global blockcache, it is stored.
and different LDB files of the BlockData offset may be the same. In order to distinguish the blockdata in different LDB files
Offset, so you need to allocate each LDB file.cache_id, so that the combination of key = cache_id + block_offset is the only one.
Blockcache is mainly encapsulated in the Table class structure. Here is a Table.cc class
namespace leveldb {
struct Table::Rep {
~Rep() {
delete filter;
delete[] filter_data;
delete index_block;
}
Options options;
Status status;
RandomAccessFile* file; // LDB file handle
uint64_t cache_id; // cache cache to the only ID of the current DataBlock
FilterBlockReader* filter; // Read FilterBlock instance
const char* filter_data; // India to Filter data
// Index Block in the LDB file location information
BlockHandle metaindex_handle; // Handle to metaindex_block: saved from footer
Block* index_block; // Index_block operation examples
};
// When opening the sstable, first read the index block,
// When used in the later query Key, first use the index block in the memory
// Judging that Key is not at this SSTable, and then decide whether to read the corresponding Data Block.
// This can obviously reduce I/O operations.
Status Table::Open(const Options& options, RandomAccessFile* file,
uint64_t size, Table** table) {
*table = nullptr;
// SSTable's Footer is 48byte
if (size < Footer::kEncodedLength) {
return Status::Corruption("file is too short to be an sstable");
}
char footer_space[Footer::kEncodedLength];
Slice footer_input;
// Read Footer to analyze the metaindex_block_handle and and
//index_block_handle。
Status s = file->Read(size - Footer::kEncodedLength, Footer::kEncodedLength,
&footer_input, footer_space);
if (!s.ok()) return s;
// 1. Analyze the metaindex_block_handle;
// 2. Pay the index_block_handle.
Footer footer;
s = footer.DecodeFrom(&footer_input);
if (!s.ok()) return s;
// Read the index block
BlockContents index_block_contents;
if (s.ok()) {
ReadOptions opt;
// Whether to open strict check data integrity, default FALSE
// After opening, the entire database may not be read after some data abnormalities.
if (options.paranoid_checks) {
opt.verify_checksums = true;
}
// Read the index_block.
// 1. Install the Office to read the data;
// 2. If you start the school inspection, you will check;
// 3. If the data is compressed, decompress it.
s = ReadBlock(file, opt, footer.index_handle(), &index_block_contents);
}
if (s.ok()) {
// We've successfully read the footer and the index block: we're
// ready to serve requests.
Block* index_block = new Block(index_block_contents);
Rep* rep = new Table::Rep;
rep->options = options;
rep->file = file;
rep->metaindex_handle = footer.metaindex_handle();
rep->index_block = index_block;
// It involves management of cache, and it is not clear about the role of this cache_id here for the time being.
rep->cache_id = (options.block_cache ? options.block_cache->NewId() : 0);
rep->filter_data = nullptr;
rep->filter = nullptr;
// Examples a table, which is used for analysis of SSTable reading
*table = new Table(rep);
// Read Filte Block
(*table)->ReadMeta(footer);
}
return s;
}
void Table::ReadMeta(const Footer& footer) {
// There is no filtering strategy, then you can determine that there is no need to read the Filter Block
if (rep_->options.filter_policy == nullptr) {
return; // Do not need any metadata
}
// TODO(sanjay): Skip this if footer.metaindex_handle() size indicates
// it is an empty block.
ReadOptions opt;
if (rep_->options.paranoid_checks) {
opt.verify_checksums = true;
}
// Read Metaindex Block according to metaindex_handle
BlockContents contents;
if (!ReadBlock(rep_->file, opt, footer.metaindex_handle(), &contents).ok()) {
// Do not propagate errors since meta info is not needed for operation
return;
}
// Here is a doubtful place! Intersection Intersection Intersection Intersection Intersection
Block* meta = new Block(contents);
Iterator* iter = meta->NewIterator(BytewiseComparator());
std::string key = "filter.";
key.append(rep_->options.filter_policy->Name());
iter->Seek(key);
if (iter->Valid() && iter->key() == Slice(key)) {
// Read Filter Block according to the offset+size of Metaindex
ReadFilter(iter->value());
}
delete iter;
delete meta;
}
void Table::ReadFilter(const Slice& filter_handle_value) {
Slice v = filter_handle_value;
BlockHandle filter_handle;
if (!filter_handle.DecodeFrom(&v).ok()) {
return;
}
// We might want to unify with ReadBlock() if we start
// requiring checksum verification in Table::Open.
ReadOptions opt;
if (rep_->options.paranoid_checks) {
opt.verify_checksums = true;
}
// Read Filter Block data
BlockContents block;
if (!ReadBlock(rep_->file, opt, filter_handle, &block).ok()) {
return;
}
// If heap_allocated is true to read
// filter block, New memory is available, and you need to delete it in follow -up
if (block.heap_allocated) {
rep_->filter_data = block.data.data(); // Will need to delete later
}
// Construct an instance of reading Filter Block
rep_->filter = new FilterBlockReader(rep_->options.filter_policy, block.data);
}
Table::~Table() {
delete rep_; }
static void DeleteBlock(void* arg, void* ignored) {
delete reinterpret_cast<Block*>(arg);
}
static void DeleteCachedBlock(const Slice& key, void* value) {
Block* block = reinterpret_cast<Block*>(value);
delete block;
}
static void ReleaseBlock(void* arg, void* h) {
Cache* cache = reinterpret_cast<Cache*>(arg);
Cache::Handle* handle = reinterpret_cast<Cache::Handle*>(h);
cache->Release(handle);
}
// According to index_value (ie Offset+size), read the corresponding block.
// Convert an index iterator value (i.e., an encoded BlockHandle)
// into an iterator over the contents of the corresponding block.
Iterator* Table::BlockReader(void* arg, const ReadOptions& options,
const Slice& index_value) {
Table* table = reinterpret_cast<Table*>(arg);
Cache* block_cache = table->rep_->options.block_cache;
Block* block = nullptr;
Cache::Handle* cache_handle = nullptr;
BlockHandle handle;
Slice input = index_value;
Status s = handle.DecodeFrom(&input);
// We intentionally allow extra stuff in index_value so that we
// can add more features in the future.
if (s.ok()) {
BlockContents contents;
if (block_cache != nullptr) {
// If the block_cache is turned on, go to this cache to find
// Key is an offset of ID+datablock. (Do not interpret Cache related implementation for the time being)
char cache_key_buffer[16];
EncodeFixed64(cache_key_buffer, table->rep_->cache_id);
EncodeFixed64(cache_key_buffer + 8, handle.offset());
Slice key(cache_key_buffer, sizeof(cache_key_buffer));
cache_handle = block_cache->Lookup(key);
// 1. If found in cache, the address is assigned directly to the block;
// 2. If you find it, go to the SSTable file to find
if (cache_handle != nullptr) {
block = reinterpret_cast<Block*>(block_cache->Value(cache_handle));
} else {
s = ReadBlock(table->rep_->file, options, handle, &contents);
if (s.ok()) {
block = new Block(contents);
// If the block reads is directly new and fill_cache, it will cache this block.
if (contents.cachable && options.fill_cache) {
cache_handle = block_cache->Insert(key, block, block->size(),
&DeleteCachedBlock);
}
}
}
} else {
// 3. If you use block_cache, go directly to SSTable to read the data.
s = ReadBlock(table->rep_->file, options, handle, &contents);
if (s.ok()) {
block = new Block(contents);
}
}
}
Iterator* iter;
if (block != nullptr) {
iter = block->NewIterator(table->rep_->options.comparator);
// 1, cache_handle is null, indicating that the block is not in the cache.
// Delete this block directly.
// 2, cache_handle non -null, indicating that the block in the cache, when iterator ITER delations,
// Through the ReleaseBlock to reduce its reference count.
if (cache_handle == nullptr) {
iter->RegisterCleanup(&DeleteBlock, block, nullptr);
} else {
iter->RegisterCleanup(&ReleaseBlock, block_cache, cache_handle);
}
} else {
// If the block is not obtained, a wrong itener will be returned directly.
iter = NewErrorIterator(s);
}
return iter;
}
// SSTABLE second layer iterator iterator.
Iterator* Table::NewIterator(const ReadOptions& options) const {
return NewTwoLevelIterator(
rep_->index_block->NewIterator(rep_->options.comparator),
&Table::BlockReader, const_cast<Table*>(this), options);
}
Status Table::InternalGet(const ReadOptions& options, const Slice& k, void* arg,
void (*handle_result)(void*, const Slice&,
const Slice&)) {
Status s;
// Through key, find a record of DataBlock in Index Block
Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator);
iiter->Seek(k);
// seek arrives
if (iiter->Valid()) {
// Hanlde_vale is the offset+size returned by the DataBlock.
Slice handle_value = iiter->value();
FilterBlockReader* filter = rep_->filter;
BlockHandle handle;
// If the filtering strategy is not empty, through the offset of DataBlock, go to the Filter to find this key
if (filter != nullptr && handle.DecodeFrom(&handle_value).ok() &&
!filter->KeyMayMatch(handle.offset(), k)) {
// Not found
} else {
// If you find it in Filte Block (not necessarily found), go to DataBlock to find.
// Create a iterator read DataBlock through the offset+size of DataBlock
Iterator* block_iter = BlockReader(this, options, iiter->value());
// Seek key to find
block_iter->Seek(k);
if (block_iter->Valid()) {
// After finding the key, execute the transmission method function
(*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;
}
// Estimated the general offset of the key.
// 1. Find it in the index_block and return to an offset of the corresponding DataBlock in Index_block.
// 2. If you find it in the index_block but you cannot decode the offset+size, you will give metaindex_block offset by default.
// 3. Seek is the value that is greater than equal to this key. If it is not found, it means that this key is relatively large, and the Officex_block of Metaindex_block by defaults.
uint64_t Table::ApproximateOffsetOf(const Slice& key) const {
Iterator* index_iter =
rep_->index_block->NewIterator(rep_->options.comparator);
index_iter->Seek(key);
uint64_t result;
if (index_iter->Valid()) {
BlockHandle handle;
Slice input = index_iter->value();
Status s = handle.DecodeFrom(&input);
if (s.ok()) {
result = handle.offset();
} else {
// Strange: we can't decode the block handle in the index block.
// We'll just return the offset of the metaindex block, which is
// close to the whole file size for this case.
result = rep_->metaindex_handle.offset();
}
} else {
// key is past the last key in the file. Approximate the offset
// by returning the offset of the metaindex block (which is
// right near the end of the file).
result = rep_->metaindex_handle.offset();
}
delete index_iter;
return result;
}
} // namespace leveldb
Through Levledb’s 16, 17, and 18, three articles, basically clarified the Cache process of Leveldb the subsequent replenishment if necessary.