foedus::cache Namespace Reference

Snapshot Cache Manager, which caches data pages retrieved from snapshot files. More...

Detailed Description

Snapshot Cache Manager, which caches data pages retrieved from snapshot files.

Overview

Snapshot Cache is a node-local read-only cache of snapshot pages. In some sense, it is a special kind of bufferpool that is much simpler and faster than traditional implementations due to the special requirements; no modifications, no interaction with logging module nor commit protocol, no guarantee needed for uniqueness (no problem to occasionally have two cached instances of the same page; just a bit waste of space). The operation to retrieve a snapshot page, especially when the page is in this cache, must be VERY fast. Thus, this cache manager must be highly optimized for read operations.

Structure

For each NUMA node memory, we have a hashtable structure whose key is snapshot-id/page-id and whose value is offset in cache memory.

Classes
struct	CacheBucket
	Hash bucket in cache table. More...
class	CacheHashtable
	A NUMA-local hashtable of cached snapshot pages. More...
class	CacheManager
	Snapshot cache manager. More...
class	CacheManagerPimpl
	Pimpl object of CacheManager. More...
struct	CacheOptions
	Set of options for snapshot cache manager. More...
struct	CacheOverflowEntry
	An entry in the overflow linked list for snapshot cache. More...
struct	CacheRefCount
	A loosely maintained reference count for CLOCK algorithm. More...
struct	HashFunc
	A simple hash function logic used in snasphot cache. More...
class	SnapshotFileSet
	Holds a set of read-only file objects for snapshot files. More...

Typedefs
typedef uint32_t	BucketId
	Offset in hashtable bucket. More...
typedef memory::PagePoolOffset	ContentId
	Offset of the actual page image in PagePool for snapshot pages. More...
typedef uint32_t	PageIdTag
	This is a lossy-compressed representation of SnapshotPagePointer used to quickly identify whether the content of a bucket may represent the given SnapshotPagePointer or not. More...
typedef uint32_t	OverflowPointer
	Position in the overflow buckets. More...

Functions
BucketId	determine_logical_buckets (BucketId physical_buckets)
uint32_t	determine_overflow_list_size (BucketId physical_buckets)
std::ostream &	operator<< (std::ostream &o, const HashFunc &v)
std::ostream &	operator<< (std::ostream &o, const SnapshotFileSet &v)

Variables
const uint16_t	kHopNeighbors = 16U
	Starting from the given position, we consider this many buckets for the entry. More...

---

Class Documentation

struct foedus::cache::CacheOverflowEntry

An entry in the overflow linked list for snapshot cache.

Entries that didn't find an empty slot are soted in a single linked list. There should be very few entries that go in the linked list. It should be almost empty. As the size of bucket is negligibly smaller than the actual page anyway (8-bytes vs 4kb), we allocate a generous (16x-ish) number of buckets compared to the total count of pages. The hashtable is guaranteed to be very sparse. We don't need anything advanced. Simple stupid.

Definition at line 191 of file cache_hashtable.hpp.

Collaboration diagram for foedus::cache::CacheOverflowEntry:

Class Members
CacheBucket	bucket_
OverflowPointer	next_	Note that we don't have to atomically maintain/follow this pointer thanks to the loose requirements. If we miss an entry, it's just a cache miss. If we couldn't evict some page, it's just one page of wasted DRAM.
uint16_t	padding_
CacheRefCount	refcount_

Typedef Documentation

typedef uint32_t foedus::cache::BucketId

Offset in hashtable bucket.

Definition at line 49 of file cache_hashtable.hpp.

typedef memory::PagePoolOffset foedus::cache::ContentId

Offset of the actual page image in PagePool for snapshot pages.

0 means not set yet.

As each page is 4kb and we expect to spend GBs of DRAM for snapshot cache, the table will have many millions of buckets. However, we can probably assume that the size is within 32 bit. Even with 50% fullness, 2^32 / 2 * 4kb = 8TB. We will not have that much DRAM per NUMA node.

Definition at line 58 of file cache_hashtable.hpp.

typedef uint32_t foedus::cache::OverflowPointer

Position in the overflow buckets.

Index-0 is always unused, thus it means null.

Definition at line 72 of file cache_hashtable.hpp.

typedef uint32_t foedus::cache::PageIdTag

This is a lossy-compressed representation of SnapshotPagePointer used to quickly identify whether the content of a bucket may represent the given SnapshotPagePointer or not.

This value is calculated via another simple formula, which should be as independent as possible from hash function (otherwise it can't differentiate entries with similar hash values). This value avoids 0 for sanity checks. If our formula results in 0, we change it to 1.

Definition at line 67 of file cache_hashtable.hpp.

Function Documentation

BucketId foedus::cache::determine_logical_buckets

(

BucketId

physical_buckets

)

Definition at line 35 of file cache_hashtable.cpp.

References ASSERT_ND, foedus::assorted::generate_almost_prime_below(), and kHopNeighbors.

                                                              {
  ASSERT_ND(physical_buckets >= 1024U);
  // to speed up, leave space in neighbors of the last bucket.
  // Instead, we do not wrap-around.
  // Also, leave space for at least one cacheline so that we never overrun when we prefetch.
  BucketId buckets = physical_buckets - kHopNeighbors - 64ULL;

  // to make the division-hashing more effective, make it prime-like.
  BucketId logical_buckets = assorted::generate_almost_prime_below(buckets);
  ASSERT_ND(logical_buckets <= physical_buckets);
  ASSERT_ND((logical_buckets & (logical_buckets - 1U)) != 0);  // at least not power of 2
  return logical_buckets;
}

Here is the call graph for this function:

uint32_t foedus::cache::determine_overflow_list_size

(

BucketId

physical_buckets

)

Definition at line 49 of file cache_hashtable.cpp.

                                                                 {
  // there should be very few overflow entries. This can be super small.
  const uint32_t kOverflowFraction = 128U;
  const uint32_t kOverflowMinSize = 256U;
  uint32_t overflow_size = physical_buckets / kOverflowFraction;
  if (overflow_size <= kOverflowMinSize) {
    overflow_size = kOverflowMinSize;
  }
  return overflow_size;
}

std::ostream& foedus::cache::operator<<	(	std::ostream &	o,
		const SnapshotFileSet &	v
	)

Definition at line 127 of file snapshot_file_set.cpp.

                                                                {
  o << "<SnapshotFileSet>";
  for (const auto& snapshot : v.files_) {
    o << "<snapshot id=\"" << snapshot.first << "\">";
    for (const auto& entry : snapshot.second) {
      o << "<node id=\"" << entry.first
        << "\" fd=\"" << entry.second->get_descriptor() << "\" />";
    }
    o << "</snapshot>";
  }
  return o;
}

std::ostream& foedus::cache::operator<<	(	std::ostream &	o,
		const HashFunc &	v
	)

Definition at line 332 of file cache_hashtable.cpp.

References foedus::cache::HashFunc::logical_buckets_, and foedus::cache::HashFunc::physical_buckets_.

                                                         {
  o << "<HashFunc>"
    << "<logical_buckets_>" << v.logical_buckets_ << "<logical_buckets_>"
    << "<physical_buckets_>" << v.physical_buckets_ << "<physical_buckets_>"
    << "</HashFunc>";
  return o;
}

Variable Documentation

const uint16_t foedus::cache::kHopNeighbors = 16U

Starting from the given position, we consider this many buckets for the entry.

When there is no empty bucket, the entry goes to the overflow linked-list. Setting a larger number means we have to read this many buckets at least for cache-miss case. It is anyway cheap because it's a sequential read, but still must not be too large.

Definition at line 80 of file cache_hashtable.hpp.

Referenced by determine_logical_buckets(), foedus::cache::CacheHashtable::find(), foedus::cache::CacheHashtable::find_batch(), and foedus::cache::CacheHashtable::install().