A NUMA-local hashtable of cached snapshot pages. More...

Detailed Description

A NUMA-local hashtable of cached snapshot pages.

Structure Overview: Each key (SnapshotPagePointer) has its own best position calculated from its hash value. If the key exists in this table, it is either in some bucket between the best position (including) and best position + kHopNeighbors (excluding) or in the overflow linked list. Simple, stupid, thus fast.

Modularity for Testability: Yes, we love them. Classes in this file are totally orthogonal to the actual page pool and other stuffs in the engine. This class only handles content (eg offset in page pool) as the data linked to the key. It's left to the caller on how the content is created, consumed, or reclaimed so that we can test/debug/tune the classes easily. In fact, test_hash_table.cpp (the testcase for this class) doesn't even instantiate an engine.

Hash Function in cache table: We have a fixed type of key, SnapshotPagePointer. For the fastest calculation of the hash we simply divide by the size of hashtable, which we adjust to be almost a prime number (in many cases actually a prime). We use assorted::ConstDiv to speed up the division.

Some history on choice of algorithm: We were initially based on Herlihy's Hopscotch, but we heavily departed from it to exploit our loose requirements for eliminitating all locks and atomic operations. The only Currently, we even don't do the bucket migration in hopscotch, so it's no longer correct to call this a hop-scotch. Instead, we use an overflow linked list, which should be almost always empty or close-to-empty.

Definition at line 233 of file cache_hashtable.hpp.

#include <cache_hashtable.hpp>

Collaboration diagram for foedus::cache::CacheHashtable:

[legend]

Classes
struct	EvictArgs
	Parameters for evict() More...

struct	Stat

Public Types
enum	Constants { kMaxFindBatchSize = 32 }

Public Member Functions
	CacheHashtable (BucketId physical_buckets, uint16_t numa_node)

ContentId	find (storage::SnapshotPagePointer page_id) const __attribute__((always_inline))
	Returns an offset for the given page ID opportunistically. More...

ErrorCode	find_batch (uint16_t batch_size, const storage::SnapshotPagePointer page_ids, ContentId out) const
	Batched version of find(). More...

ErrorCode	install (storage::SnapshotPagePointer page_id, ContentId content)
	Called when a cached page is not found. More...

void	evict (EvictArgs *args)
	Evict some entries from the hashtable. More...

BucketId	get_logical_buckets () const __attribute__((always_inline))

BucketId	get_physical_buckets () const __attribute__((always_inline))

BucketId	get_bucket_number (storage::SnapshotPagePointer page_id) const __attribute__((always_inline))
	Returns a bucket number the given page ID should belong to. More...

ErrorStack	verify_single_thread () const
	only for debugging. More...

const CacheBucket &	get_bucket (BucketId bucket_id) const

Stat	get_stat_single_thread () const
	only for debugging. More...

Protected Member Functions
BucketId	evict_main_loop (EvictArgs *args, BucketId cur, uint16_t loop)

void	evict_overflow_loop (EvictArgs *args, uint16_t loop)

Protected Attributes
const uint16_t	numa_node_

const uint32_t	overflow_buckets_count_

const HashFunc	hash_func_

memory::AlignedMemory	buckets_memory_

memory::AlignedMemory	refcounts_memory_

memory::AlignedMemory	overflow_buckets_memory_

CacheBucket *	buckets_

CacheRefCount *	refcounts_

CacheOverflowEntry *	overflow_buckets_

OverflowPointer	overflow_buckets_head_
	This forms a singly-linked list of active overflow entries. More...

OverflowPointer	overflow_free_buckets_head_
	This forms another singly-linked list of free overflow entries. More...

soc::SharedMutex	overflow_free_buckets_mutex_
	The mutex to protect free overflow entries. More...

BucketId	clockhand_
	We previously stopped eviction here for usual buckets. More...

Friends
std::ostream &	operator<< (std::ostream &o, const CacheHashtable &v)

Member Enumeration Documentation

enum foedus::cache::CacheHashtable::Constants

Enumerator
kMaxFindBatchSize	Max size for find_batch()

Definition at line 235 of file cache_hashtable.hpp.

                  {
     kMaxFindBatchSize = 32,
   };

Constructor & Destructor Documentation

foedus::cache::CacheHashtable::CacheHashtable	(	BucketId	physical_buckets,
		uint16_t	numa_node
	)

Definition at line 66 of file cache_hashtable.cpp.

References foedus::memory::AlignedMemory::alloc(), foedus::cache::CacheOverflowEntry::bucket_, buckets_, buckets_memory_, foedus::cache::CacheRefCount::count_, foedus::memory::AlignedMemory::get_block(), foedus::memory::AlignedMemory::kNumaAllocOnnode, foedus::cache::CacheOverflowEntry::next_, overflow_buckets_, overflow_buckets_count_, overflow_buckets_head_, overflow_buckets_memory_, overflow_free_buckets_head_, foedus::cache::CacheOverflowEntry::padding_, foedus::cache::CacheOverflowEntry::refcount_, refcounts_, refcounts_memory_, and foedus::cache::CacheBucket::reset().

   : numa_node_(numa_node),
   overflow_buckets_count_(determine_overflow_list_size(physical_buckets)),
   hash_func_(physical_buckets),
   clockhand_(0) {
   buckets_memory_.alloc(
     sizeof(CacheBucket) * physical_buckets,
     1U << 21,
     memory::AlignedMemory::kNumaAllocOnnode,
     numa_node);
   refcounts_memory_.alloc(
     sizeof(CacheRefCount) * physical_buckets,
     1U << 21,
     memory::AlignedMemory::kNumaAllocOnnode,
     numa_node);
   buckets_ = reinterpret_cast<CacheBucket*>(buckets_memory_.get_block());
   refcounts_ = reinterpret_cast<CacheRefCount*>(refcounts_memory_.get_block());
 
   // index-0 should be never used. 0 means null.
   buckets_[0].reset();
   refcounts_[0].count_ = 0;
 
   // for overflow list
   overflow_buckets_memory_.alloc(
     sizeof(CacheOverflowEntry) * overflow_buckets_count_,
     1U << 21,
     memory::AlignedMemory::kNumaAllocOnnode,
     numa_node);
   overflow_buckets_ = reinterpret_cast<CacheOverflowEntry*>(overflow_buckets_memory_.get_block());
   overflow_buckets_head_ = 0;
   // index-0 should be never used. 0 means null.
   overflow_buckets_[0].bucket_.reset();
   overflow_buckets_[0].next_ = 0;
   overflow_buckets_[0].padding_ = 0;
   overflow_buckets_[0].refcount_.count_ = 0;
 
   // initially all entries are in free list.
   overflow_free_buckets_head_ = 1;
   for (OverflowPointer i = 1U; i < overflow_buckets_count_; ++i) {
     if (i < overflow_buckets_count_ - 1U) {
       overflow_buckets_[i].next_ = i + 1U;
     } else {
       overflow_buckets_[i].next_ = 0;
     }
   }
 }

Here is the call graph for this function:

Member Function Documentation

void foedus::cache::CacheHashtable::evict ( CacheHashtable::EvictArgs * args )

Evict some entries from the hashtable.

Compared to traditional bufferpools, this is much simpler and more scalable thanks to the loose requirements and epoch-based reclamation of the evicted pages. This method only evicts the hashtable entries, so reclaiming the pages pointed from the entries is done by the caller.

Definition at line 171 of file cache_hashtable.cpp.

References ASSERT_ND, clockhand_, evict_main_loop(), evict_overflow_loop(), foedus::cache::CacheHashtable::EvictArgs::evicted_count_, get_physical_buckets(), numa_node_, overflow_buckets_head_, and foedus::cache::CacheHashtable::EvictArgs::target_count_.

Referenced by foedus::cache::CacheManagerPimpl::handle_cleaner_evict_pages().

                                                         {
   LOG(INFO) << "Snapshot-Cache eviction starts at node-" << numa_node_
     << ", clockhand_=" << clockhand_ << ", #target=" << args->target_count_;
   const BucketId end = get_physical_buckets();
   BucketId cur = clockhand_;
 
   // we check each entry in refcounts_, which are 2 bytes each.
   // for quicker checks, we want 8-byte aligned access.
   // also, we should anyway do prefetch, so make it 64-byte aligned
   cur = (cur >> 5) << 5;
   ASSERT_ND(cur % (1U << 5) == 0);
   if (cur >= end) {
     cur = 0;
   }
 
   // evict on the normal buckets first.
   args->evicted_count_ = 0;
   uint16_t loops;
   const uint16_t kMaxLoops = 16;  // if we need more loops than this, something is wrong...
   for (loops = 0; loops < kMaxLoops; ++loops) {
     cur = evict_main_loop(args, cur, loops);
     if (cur >= get_physical_buckets()) {
       cur = 0;
       // we went over all buckets in usual entries. now check the overflow linked list.
       if (overflow_buckets_head_) {
         evict_overflow_loop(args, loops);
       }
     }
     if (args->evicted_count_ >= args->target_count_) {
       break;
     } else {
       ASSERT_ND(cur == 0);  // we checked all buckets and wrapped around, right? go on to next loop
     }
   }
 
   clockhand_ = cur;
   LOG(INFO) << "Snapshot-Cache eviction completed at node-" << numa_node_
     << ", clockhand_=" << clockhand_ << ", #evicted=" << args->evicted_count_
     << ", looped-over the whole hashtable for " << loops << " times";
 }

Here is the call graph for this function:

Here is the caller graph for this function:

BucketId foedus::cache::CacheHashtable::evict_main_loop	(	CacheHashtable::EvictArgs *	args,
		BucketId	cur,
		uint16_t	loop
	)

protected

Definition at line 212 of file cache_hashtable.cpp.

References foedus::cache::CacheHashtable::EvictArgs::add_evicted(), ASSERT_ND, ASSUME_ALIGNED, buckets_, clockhand_, foedus::cache::CacheBucket::data_, foedus::cache::CacheRefCount::decrement(), foedus::debugging::StopWatch::elapsed_us(), foedus::cache::CacheHashtable::EvictArgs::evicted_count_, get_physical_buckets(), foedus::assorted::kCachelineSize, LIKELY, numa_node_, foedus::assorted::prefetch_cachelines(), refcounts_, foedus::debugging::StopWatch::stop(), and foedus::cache::CacheHashtable::EvictArgs::target_count_.

Referenced by evict().

                  {
   ASSERT_ND(cur % (1U << 5) == 0);
   ASSERT_ND((assorted::kCachelineSize >> 5) == sizeof(CacheRefCount));
   const uint16_t decrements = 1U << loop;
   debugging::StopWatch watch;
 
   // the main idea is as follows.
   // whenever the bucket has never been used or been used but released without unlucky races,
   // the corresponding refcount is zero. hence, we just check for non-zeros in refcounts_.
   // this is trivially vectorized and the only observable cost is L1 cache miss.
   // we reduce L1 cache miss cost by prefetching a lot.
   uint32_t cur_cacheline = cur >> 5;
   const uint32_t end_cacheline = (get_physical_buckets() >> 5) + 1ULL;
   // for example, we prefetch cacheline 16-23 while reading cacheline 0-7.
   const uint16_t kL1PrefetchBatch = 8;
   const uint16_t kL1PrefetchAhead = 16;
   for (; cur_cacheline < end_cacheline; ++cur_cacheline) {
     if (cur_cacheline / kL1PrefetchBatch == 0) {
       assorted::prefetch_cachelines(
         refcounts_ + ((cur_cacheline + kL1PrefetchAhead) << 5),
         kL1PrefetchBatch);
     }
 
     BucketId bucket = cur_cacheline << 5;
     // gcc, you should be smart enough to optimize this. at least with O3.
     uint64_t* ints = reinterpret_cast<uint64_t*>(ASSUME_ALIGNED(refcounts_ + bucket, 64));
     bool all_zeros = true;
     for (uint16_t i = 0; i < 8U; ++i) {
       if (ints[i] != 0) {
         all_zeros = false;
         break;
       }
     }
 
     if (LIKELY(all_zeros)) {
       continue;
     } else {
       // this should be a rare case as far as we keep the hashtable sparse.
       CacheRefCount* base = reinterpret_cast<CacheRefCount*>(refcounts_ + bucket);
       for (uint16_t i = 0; i < 32U; ++i) {
         if (base[i].count_ > 0) {
           bool still_non_zero = base[i].decrement(decrements);
           if (!still_non_zero) {
             args->add_evicted(buckets_[bucket + i].get_content_id());
             buckets_[bucket + i].data_ = 0;
           }
         }
       }
     }
 
     if (args->evicted_count_ >= args->target_count_) {
       break;
     }
   }
 
   watch.stop();
   LOG(INFO) << "Snapshot-Cache eviction main_loop at node-" << numa_node_ << ", checked "
     << ((cur_cacheline << 5) - clockhand_) << " buckets in " << watch.elapsed_us() << "us";
 
   return cur_cacheline << 5;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::cache::CacheHashtable::evict_overflow_loop	(	CacheHashtable::EvictArgs *	args,
		uint16_t	loop
	)

protected

Definition at line 277 of file cache_hashtable.cpp.

References foedus::cache::CacheHashtable::EvictArgs::add_evicted(), foedus::cache::CacheOverflowEntry::bucket_, foedus::cache::CacheBucket::data_, foedus::cache::CacheRefCount::decrement(), foedus::debugging::StopWatch::elapsed_us(), foedus::cache::CacheBucket::get_content_id(), foedus::cache::CacheOverflowEntry::next_, numa_node_, overflow_buckets_, overflow_buckets_head_, overflow_free_buckets_mutex_, foedus::cache::CacheOverflowEntry::refcount_, and foedus::debugging::StopWatch::stop().

Referenced by evict().

                                                                                      {
   const uint16_t decrements = 1U << loop;
   uint32_t checked_count = 0;
 
   // store evicted entries into
   OverflowPointer evicted_head = 0;  // evicted
   debugging::StopWatch watch;
   {
     // We block this method entirely with the free buckets mutex.
     // This does NOT block usual transactions unless they actually have to newly add to overflow,
     // which should be very rare. This is cheap yet enough to make the free-list safe.
     soc::SharedMutexScope scope(&overflow_free_buckets_mutex_);
 
     // no interesting optimization. overflow list should be empty or almost empty.
     OverflowPointer head = overflow_buckets_head_;
     if (head != 0) {
       // skip the head. we handle it at the last.
       OverflowPointer prev = head;
       for (OverflowPointer cur = overflow_buckets_[prev].next_; cur != 0;) {
         CacheOverflowEntry* cur_entry = overflow_buckets_ + cur;
         OverflowPointer next = cur_entry->next_;
         bool still_non_zero = cur_entry->refcount_.decrement(decrements);
         if (!still_non_zero) {
           args->add_evicted(cur_entry->bucket_.get_content_id());
           CacheOverflowEntry* prev_entry = overflow_buckets_ + prev;
           prev_entry->next_ = next;
           cur_entry->bucket_.data_ = 0;
           cur_entry->next_ = evicted_head;
           evicted_head = cur;
         }
 
         prev = cur;
         cur = next;
         ++checked_count;
       }
 
       // finally check the head
       CacheOverflowEntry* cur_entry = overflow_buckets_ + head;
       bool still_non_zero = cur_entry->refcount_.decrement(decrements);
       if (!still_non_zero) {
         args->add_evicted(cur_entry->bucket_.get_content_id());
         overflow_buckets_head_ = cur_entry->next_;
         cur_entry->bucket_.data_ = 0;
         cur_entry->next_ = evicted_head;
         evicted_head = head;
       }
       ++checked_count;
     }
   }
   watch.stop();
   LOG(INFO) << "Snapshot-Cache eviction overflow_loop at node-" << numa_node_ << ", checked "
     << (checked_count) << " buckets in " << watch.elapsed_us() << "us";
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ContentId foedus::cache::CacheHashtable::find ( storage::SnapshotPagePointer page_id ) const

inline

Returns an offset for the given page ID opportunistically.

Parameters

[in] page_id Page ID to look for

Returns: offset that contains the page. 0 if not found.

This doesn't take a lock, so a concurrent thread might have inserted the wanted page concurrrently. It's fine. Then we read the page from snapshot, just wasting a bit. Instead, an entry is removed from the cache gracefully, thus an offset we observed will not become invalid soon (pages are garbage collected with grace period). No precise concurrency control needed.

However, it might (very occasionally) cause a false negative due to the way we verify (each CacheBucket contains only a compressed version of the page Id). So, the caller must check whether the returned ContentId really points to a correct page, and invoke install() in that case. Again, no precise concurrency control required. Even for false positives/negatives, we just get a bit slower. No correctness issue.

Definition at line 415 of file cache_hashtable.hpp.

References ASSERT_ND, foedus::cache::CacheOverflowEntry::bucket_, buckets_, get_bucket_number(), foedus::cache::CacheBucket::get_content_id(), get_logical_buckets(), foedus::cache::HashFunc::get_tag(), foedus::cache::CacheBucket::get_tag(), foedus::cache::CacheRefCount::increment(), foedus::cache::kHopNeighbors, foedus::cache::CacheOverflowEntry::next_, overflow_buckets_, overflow_buckets_head_, foedus::assorted::prefetch_cachelines(), foedus::cache::CacheOverflowEntry::refcount_, and refcounts_.

Referenced by foedus::thread::ThreadPimpl::find_or_read_a_snapshot_page().

                                                                               {
   ASSERT_ND(page_id > 0);
   BucketId bucket_number = get_bucket_number(page_id);
   ASSERT_ND(bucket_number < get_logical_buckets());
 
   // we prefetch up to 128 bytes (16 entries).
   assorted::prefetch_cachelines(buckets_ + bucket_number, 2);
 
   PageIdTag tag = HashFunc::get_tag(page_id);
   ASSERT_ND(tag != 0);
   for (uint16_t i = 0; i < kHopNeighbors; ++i) {
     const CacheBucket& bucket = buckets_[bucket_number + i];
     if (bucket.get_tag() == tag) {
       // found (probably)!
       refcounts_[bucket_number + i].increment();
       return bucket.get_content_id();
     }
   }
 
   // Not found. let's check overflow list
   if (overflow_buckets_head_) {
     for (OverflowPointer i = overflow_buckets_head_; i != 0;) {
       if (overflow_buckets_[i].bucket_.get_tag() == tag) {
         overflow_buckets_[i].refcount_.increment();
         return overflow_buckets_[i].bucket_.get_content_id();
       }
       i = overflow_buckets_[i].next_;
     }
   }
 
   return 0;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorCode foedus::cache::CacheHashtable::find_batch	(	uint16_t	batch_size,
		const storage::SnapshotPagePointer *	page_ids,
		ContentId *	out
	)		const

Batched version of find().

Parameters

[in]	batch_size	Batch size. Must be kMaxFindBatchSize or less.
[in]	page_ids	Array of Page IDs to look for, size=batch_size
[out]	out	Output

Returns: Only possible error is kErrorCodeInvalidParameter for too large batch_size

This might perform much faster because of parallel prefetching, SIMD-ized hash calculattion (planned, not implemented yet) etc.

Definition at line 376 of file cache_hashtable.cpp.

References ASSERT_ND, foedus::cache::CacheOverflowEntry::bucket_, buckets_, get_bucket_number(), foedus::cache::CacheBucket::get_content_id(), get_logical_buckets(), foedus::cache::HashFunc::get_tag(), foedus::cache::CacheBucket::get_tag(), foedus::cache::CacheRefCount::increment(), foedus::kErrorCodeInvalidParameter, foedus::kErrorCodeOk, foedus::cache::kHopNeighbors, kMaxFindBatchSize, foedus::cache::CacheOverflowEntry::next_, overflow_buckets_, overflow_buckets_head_, foedus::assorted::prefetch_cachelines(), foedus::cache::CacheOverflowEntry::refcount_, refcounts_, and UNLIKELY.

Referenced by foedus::thread::ThreadPimpl::find_or_read_snapshot_pages_batch().

                         {
   if (batch_size == 0) {
     return kErrorCodeOk;
   }
   ASSERT_ND(batch_size <= kMaxFindBatchSize);
   if (UNLIKELY(batch_size > kMaxFindBatchSize)) {
     return kErrorCodeInvalidParameter;
   }
 
   // first, calculate hash values and prefetch
   BucketId bucket_numbers[kMaxFindBatchSize];
   for (uint16_t b = 0; b < batch_size; ++b) {
     if (page_ids[b] == 0) {
       continue;
     } else if (b > 0 && page_ids[b - 1] == page_ids[b]) {
       continue;
     }
 
     bucket_numbers[b] = get_bucket_number(page_ids[b]);
     ASSERT_ND(bucket_numbers[b] < get_logical_buckets());
     // we prefetch up to 128 bytes (16 entries).
     assorted::prefetch_cachelines(buckets_ + bucket_numbers[b], 2);
   }
 
   for (uint16_t b = 0; b < batch_size; ++b) {
     out[b] = 0;
     if (page_ids[b] == 0) {
       continue;
     } else if (b > 0 && page_ids[b - 1] == page_ids[b]) {
       out[b] = out[b - 1];
       continue;
     }
 
     PageIdTag tag = HashFunc::get_tag(page_ids[b]);
     ASSERT_ND(tag != 0);
     BucketId bucket_number = bucket_numbers[b];
     for (uint16_t i = 0; i < kHopNeighbors; ++i) {
       const CacheBucket& bucket = buckets_[bucket_number + i];
       if (bucket.get_tag() == tag) {
         // found (probably)!
         refcounts_[bucket_number + i].increment();
         out[b] = bucket.get_content_id();
         break;
       }
     }
 
     // Not found. let's check overflow list
     if (out[b] == 0 && overflow_buckets_head_) {
       for (OverflowPointer i = overflow_buckets_head_; i != 0;) {
         if (overflow_buckets_[i].bucket_.get_tag() == tag) {
           overflow_buckets_[i].refcount_.increment();
           out[b] = overflow_buckets_[i].bucket_.get_content_id();
           break;
         }
         i = overflow_buckets_[i].next_;
       }
     }
   }
 
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

const CacheBucket& foedus::cache::CacheHashtable::get_bucket ( BucketId bucket_id ) const

inline

Definition at line 326 of file cache_hashtable.hpp.

References buckets_.

326 { return buckets_[bucket_id]; }

foedus::cache::CacheHashtable::buckets_

CacheBucket * buckets_

Definition: cache_hashtable.hpp:346

BucketId foedus::cache::CacheHashtable::get_bucket_number ( storage::SnapshotPagePointer page_id ) const

inline

Returns a bucket number the given page ID should belong to.

Definition at line 319 of file cache_hashtable.hpp.

References foedus::cache::HashFunc::get_bucket_number(), and hash_func_.

Referenced by find(), find_batch(), and install().

                                                                                      {
     return hash_func_.get_bucket_number(page_id);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

BucketId foedus::cache::CacheHashtable::get_logical_buckets ( ) const

inline

Definition at line 313 of file cache_hashtable.hpp.

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

Referenced by find(), and find_batch().

313 { return hash_func_.logical_buckets_; }

foedus::cache::HashFunc::logical_buckets_

const BucketId logical_buckets_

Number of logical (actually used) buckets in this table.

Definition: cache_hashtable.hpp:92

foedus::cache::CacheHashtable::hash_func_

const HashFunc hash_func_

Definition: cache_hashtable.hpp:340

Here is the caller graph for this function:

BucketId foedus::cache::CacheHashtable::get_physical_buckets ( ) const

inline

Definition at line 314 of file cache_hashtable.hpp.

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

Referenced by evict(), evict_main_loop(), get_stat_single_thread(), and verify_single_thread().

314 { return hash_func_.physical_buckets_; }

foedus::cache::CacheHashtable::hash_func_

const HashFunc hash_func_

Definition: cache_hashtable.hpp:340

foedus::cache::HashFunc::physical_buckets_

const BucketId physical_buckets_

Number of buckets that are physically allocated, at least kHopNeighbors more than logical...

Definition: cache_hashtable.hpp:94

Here is the caller graph for this function:

CacheHashtable::Stat foedus::cache::CacheHashtable::get_stat_single_thread ( ) const

only for debugging.

you can call this in a race, but the results are a bit inaccurate.

Definition at line 351 of file cache_hashtable.cpp.

References buckets_, get_physical_buckets(), foedus::cache::CacheOverflowEntry::next_, foedus::cache::CacheHashtable::Stat::normal_entries_, overflow_buckets_, overflow_buckets_head_, and foedus::cache::CacheHashtable::Stat::overflow_entries_.

                                                                 {
   Stat result;
   result.normal_entries_ = 0;
   result.overflow_entries_ = 0;
 
   BucketId end = get_physical_buckets();
   for (BucketId i = 0; i < end; ++i) {
     if (buckets_[i].is_content_set()) {
       ++result.normal_entries_;
     }
   }
 
   if (overflow_buckets_head_) {
     for (OverflowPointer i = overflow_buckets_head_; i != 0;) {
       if (overflow_buckets_[i].bucket_.is_content_set()) {
         ++result.overflow_entries_;
       }
       i = overflow_buckets_[i].next_;
     }
   }
 
   return result;
 }

Here is the call graph for this function:

ErrorCode foedus::cache::CacheHashtable::install	(	storage::SnapshotPagePointer	page_id,
		ContentId	content
	)

Called when a cached page is not found.

Returns: the only possible error code is kErrorCodeCacheTooManyOverflow, which is super-rare.

This method installs the new content to this hashtable. We are anyway doing at least 4kb memory copy in this case, so no need for serious optimization.

Definition at line 114 of file cache_hashtable.cpp.

References ASSERT_ND, foedus::cache::CacheOverflowEntry::bucket_, buckets_, foedus::cache::CacheRefCount::count_, get_bucket_number(), foedus::cache::HashFunc::get_tag(), foedus::kErrorCodeCacheTooManyOverflow, foedus::kErrorCodeOk, foedus::cache::kHopNeighbors, foedus::assorted::memory_fence_release(), foedus::cache::CacheOverflowEntry::next_, overflow_buckets_, overflow_buckets_count_, overflow_buckets_head_, overflow_free_buckets_head_, overflow_free_buckets_mutex_, foedus::cache::CacheOverflowEntry::refcount_, refcounts_, and foedus::cache::CacheBucket::reset().

Referenced by foedus::thread::ThreadPimpl::find_or_read_a_snapshot_page(), and foedus::thread::ThreadPimpl::find_or_read_snapshot_pages_batch().

                                                                                        {
   ASSERT_ND(content != 0);
 
   // Grab a bucket to install a new page.
   // The bucket does not have to be the only bucket to serve the page, so
   // the logic below is much simpler than typical bufferpool.
   BucketId ideal_bucket = get_bucket_number(page_id);
   PageIdTag tag = HashFunc::get_tag(page_id);
   ASSERT_ND(tag != 0);
 
   CacheBucket new_bucket;
   new_bucket.reset(content, tag);
 
   // An opportunistic optimization. if the exact bucket already has the same page_id,
   // most likely someone else is trying to install it at the same time. let's wait.
   for (BucketId bucket = ideal_bucket; bucket < ideal_bucket + kHopNeighbors; ++bucket) {
     if (!buckets_[bucket].is_content_set()) {
       // looks like this is empty!
       buckets_[bucket] = new_bucket;  // 8-byte implicitly-atomic write
       refcounts_[bucket].count_ = 1;
       // this might be immediately overwritten by someone else, but that's fine.
       // that only causes a future cache miss. no correctness issue.
       return kErrorCodeOk;
     }
   }
 
   // unlucky, no empty slot. If this happens often, we are seriously troubled.
   DVLOG(0) << "Ohhh, we have to add this to overflow list! This should be really rare."
     << " page_id=" << assorted::Hex(page_id)
     << ", content=" << assorted::Hex(content)
     << ", ideal_bucket=" << assorted::Hex(ideal_bucket)
     << ", tag=" << assorted::Hex(tag)
     << ", page_id=" << assorted::Hex(page_id);
 
   // we come here anyway very occasionally, so taking mutex here wouldn't cause performance issue.
   // note that this mutex just protects the free-list, which is rarely used.
   soc::SharedMutexScope scope(&overflow_free_buckets_mutex_);
   OverflowPointer new_overflow_entry = overflow_free_buckets_head_;
   if (new_overflow_entry == 0) {
     LOG(ERROR) << "Oh my god. we consumed all overflow entries, which means we have too many"
       << " hash collisions. page_id=" << assorted::Hex(page_id)
       << ", content=" << assorted::Hex(content)
       << ", ideal_bucket=" << assorted::Hex(ideal_bucket)
       << ", tag=" << assorted::Hex(tag)
       << ", page_id=" << assorted::Hex(page_id);
     return kErrorCodeCacheTooManyOverflow;
   }
   ASSERT_ND(new_overflow_entry < overflow_buckets_count_);
   overflow_free_buckets_head_ = overflow_buckets_[new_overflow_entry].next_;
   overflow_buckets_[new_overflow_entry].next_ = overflow_buckets_head_;
   overflow_buckets_[new_overflow_entry].refcount_.count_ = 1;
   overflow_buckets_[new_overflow_entry].bucket_ = new_bucket;
   assorted::memory_fence_release();
   overflow_buckets_head_ = new_overflow_entry;
   return kErrorCodeOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::cache::CacheHashtable::verify_single_thread ( ) const

only for debugging.

don't call this in a race

Definition at line 340 of file cache_hashtable.cpp.

References ASSERT_ND, buckets_, get_physical_buckets(), and foedus::kRetOk.

                                                       {
   for (BucketId i = 0; i < get_physical_buckets(); ++i) {
     if (buckets_[i].is_content_set()) {
       ASSERT_ND(buckets_[i].get_tag() != 0);
     } else {
       ASSERT_ND(buckets_[i].get_tag() == 0);
     }
   }
   return kRetOk;
 }

Here is the call graph for this function:

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	o,
		const CacheHashtable &	v
	)

friend

Member Data Documentation

CacheBucket* foedus::cache::CacheHashtable::buckets_

protected

Definition at line 346 of file cache_hashtable.hpp.

Referenced by CacheHashtable(), evict_main_loop(), find(), find_batch(), get_bucket(), get_stat_single_thread(), install(), and verify_single_thread().

memory::AlignedMemory foedus::cache::CacheHashtable::buckets_memory_

protected

Definition at line 341 of file cache_hashtable.hpp.

Referenced by CacheHashtable().

BucketId foedus::cache::CacheHashtable::clockhand_

protected

We previously stopped eviction here for usual buckets.

We will resume from this number +1 next time. We will then sequetnially check. The overflow list is fully checked after each wrap-around of this clockhand, so we don't have a dedicated clock hand for overflow list.

Definition at line 378 of file cache_hashtable.hpp.

Referenced by evict(), and evict_main_loop().

const HashFunc foedus::cache::CacheHashtable::hash_func_

protected

Definition at line 340 of file cache_hashtable.hpp.

Referenced by get_bucket_number(), get_logical_buckets(), and get_physical_buckets().

const uint16_t foedus::cache::CacheHashtable::numa_node_

protected

Definition at line 338 of file cache_hashtable.hpp.

Referenced by evict(), evict_main_loop(), and evict_overflow_loop().

CacheOverflowEntry* foedus::cache::CacheHashtable::overflow_buckets_

protected

Definition at line 350 of file cache_hashtable.hpp.

Referenced by CacheHashtable(), evict_overflow_loop(), find(), find_batch(), get_stat_single_thread(), and install().

const uint32_t foedus::cache::CacheHashtable::overflow_buckets_count_

protected

Definition at line 339 of file cache_hashtable.hpp.

Referenced by CacheHashtable(), and install().

OverflowPointer foedus::cache::CacheHashtable::overflow_buckets_head_

protected

This forms a singly-linked list of active overflow entries.

This is initially 0 (null), and usually remains 0.

Definition at line 355 of file cache_hashtable.hpp.

Referenced by CacheHashtable(), evict(), evict_overflow_loop(), find(), find_batch(), get_stat_single_thread(), and install().

memory::AlignedMemory foedus::cache::CacheHashtable::overflow_buckets_memory_

protected

Definition at line 343 of file cache_hashtable.hpp.

Referenced by CacheHashtable().

OverflowPointer foedus::cache::CacheHashtable::overflow_free_buckets_head_

protected

This forms another singly-linked list of free overflow entries.

A new entry is consumed from the head (by transactions). A returned entry is added back to the head (by cleaner). This overflow free-list is the only data structure we access with atomic operation/mutex. As a new entry is added to overflow list very occasionally, this should be fine.

Definition at line 364 of file cache_hashtable.hpp.

Referenced by CacheHashtable(), and install().

soc::SharedMutex foedus::cache::CacheHashtable::overflow_free_buckets_mutex_

protected

The mutex to protect free overflow entries.

Actually this is not a shared mutex, but we reuse the class to reduce code.

Definition at line 370 of file cache_hashtable.hpp.

Referenced by evict_overflow_loop(), and install().

CacheRefCount* foedus::cache::CacheHashtable::refcounts_

protected

Definition at line 347 of file cache_hashtable.hpp.

Referenced by CacheHashtable(), evict_main_loop(), find(), find_batch(), and install().

memory::AlignedMemory foedus::cache::CacheHashtable::refcounts_memory_

protected

Definition at line 342 of file cache_hashtable.hpp.

Referenced by CacheHashtable().

The documentation for this class was generated from the following files:

/home/shino/foedus_code/foedus-core/include/foedus/cache/cache_hashtable.hpp
/home/shino/foedus_code/foedus-core/src/foedus/cache/cache_hashtable.cpp

Detailed Description

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation