Cache Techniques for Improving LevelDB Query Performance

Table of Contents

1. Two Types of Cache
2. Table Cache
3. Block Cache

1. Two Types of Cache

LevelDB employs two types of caches: Table Cache and Block Cache. While both are caches, they serve different purposes.

• Table Cache: Used to cache SSTable file descriptors, index blocks, meta blocks, and other metadata.
• Block Cache: Used to cache decompressed data blocks.

Both are implemented based on the ShardedLRUCache discussed in the previous section.

Typically, a block size ranges from 4KB to 4MB, and the block cache is configured as an 8MB LRU cache by default.

The table cache defaults to 990 files (representing 990 SSTable files or indexes), reserving around 10 files for other purposes, with the remaining 990 managed by the Table Cache.

Query Example for Key K:

1. Table Cache helps quickly locate that key K is in Block 5 of SSTable-X.
2. If Block 5 is already cached in the Block Cache, it is read directly; otherwise, Block 5 is loaded from disk and cached.
3. This layered caching design avoids repeated opening of SSTable-X and decompression of Block 5, significantly improving read efficiency under limited memory.

Next, we discuss the implementation details of these two caches.

2. Table Cache

The Table Cache is created in the DBImpl constructor:

new TableCache(dbname_, options_, TableCacheSize(options_));

This initializes an LRU cache for 990 files.

The key-value pairs in the LRU cache are:

• Key: Compressed file name
• Value: TableAndFile structure

struct TableAndFile {
  RandomAccessFile* file;  // Opened file handle
  Table* table;            // Corresponding SSTable parsed structure
};

Example of inserting into the cache:

char buf[sizeof(file_number)];
EncodeFixed64(buf, file_number);
Slice key(buf, sizeof(buf));
TableAndFile* tf = new TableAndFile;
tf->file = file;
tf->table = table;
*handle = cache_->Insert(key, tf, 1, &DeleteEntry);

Core Interfaces:

1. Evict: Removes the cache entry for a specific file.
2. FindTable:
   • Used to quickly retrieve the index/filter of an SSTable for fast data block queries.
   • If the compressed file_name is not in the cache, the SSTable file is opened and cached as <key = compressed filename, value = TableAndFile>.
   • If the key exists, the handle is retrieved from the LRU cache, and the TableAndFile is obtained.

   Status TableCache::FindTable(uint64_t file_number, uint64_t file_size, Cache::Handle** handle) {}
   

3. Get:
   • Queries whether a key exists in an SSTable. If it does, a callback function is invoked; otherwise, it returns.
   • Steps:
     1. Calls FindTable to get the cached handle.
     2. Retrieves the table from TableAndFile and calls InternalGet.
     3. Releases the handle.
   • InternalGet steps:
     1. Checks the data block index to see if the key exists.
     2. If it exists, retrieves the handle for the corresponding data block.
     3. Uses the filter to check; if not found, returns "not exists."
     4. If found, retrieves the block via BlockReader, constructs an iterator, locates the key, and invokes the callback.
4. NewIterator:
   • Looks up the cache using key = file_name and returns the cache and an iterator created based on it.

3. Block Cache

The Block Cache is used when reading actual data blocks, implemented in the BlockReader function.

Based on the input index data (binary), it parses the corresponding data block's block handle. It then checks if options.block_cache is set:

• If not set, it directly calls ReadBlock.
• If set, it queries the block cache with a 16-byte key:
  • Key: 8-byte ID + block offset
  • Value: Block

If the block is found in the cache, it is retrieved directly; otherwise, ReadBlock is called, and the result is cached.

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 (contents.cachable && options.fill_cache) {
      cache_handle = block_cache->Insert(key, block, block->size(), &DeleteCachedBlock);
    }
  }
}