cache_hashtable.hpp File Reference

#include <stdint.h>
#include <iosfwd>
#include "foedus/assert_nd.hpp"
#include "foedus/compiler.hpp"
#include "foedus/cxx11.hpp"
#include "foedus/error_code.hpp"
#include "foedus/error_stack.hpp"
#include "foedus/assorted/atomic_fences.hpp"
#include "foedus/assorted/cacheline.hpp"
#include "foedus/assorted/const_div.hpp"
#include "foedus/cache/fwd.hpp"
#include "foedus/memory/aligned_memory.hpp"
#include "foedus/memory/fwd.hpp"
#include "foedus/memory/memory_id.hpp"
#include "foedus/soc/shared_mutex.hpp"
#include "foedus/storage/page.hpp"
#include "foedus/storage/storage_id.hpp"
#include "foedus/thread/fwd.hpp"

Include dependency graph for cache_hashtable.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	foedus::cache::HashFunc
	A simple hash function logic used in snasphot cache. More...
struct	foedus::cache::CacheBucket
	Hash bucket in cache table. More...
struct	foedus::cache::CacheRefCount
	A loosely maintained reference count for CLOCK algorithm. More...
struct	foedus::cache::CacheOverflowEntry
	An entry in the overflow linked list for snapshot cache. More...
class	foedus::cache::CacheHashtable
	A NUMA-local hashtable of cached snapshot pages. More...
struct	foedus::cache::CacheHashtable::EvictArgs
	Parameters for evict() More...
struct	foedus::cache::CacheHashtable::Stat

Namespaces
	foedus
	Root package of FOEDUS (Fast Optimistic Engine for Data Unification Services).
	foedus::cache
	Snapshot Cache Manager, which caches data pages retrieved from snapshot files.

Typedefs
typedef uint32_t	foedus::cache::BucketId
	Offset in hashtable bucket. More...
typedef memory::PagePoolOffset	foedus::cache::ContentId
	Offset of the actual page image in PagePool for snapshot pages. More...
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. More...
typedef uint32_t	foedus::cache::OverflowPointer
	Position in the overflow buckets. More...

Variables
const uint16_t	foedus::cache::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_