foedus::storage::hash Namespace Reference

Hashtable Storage, a concurrent hashtable. More...

Detailed Description

Hashtable Storage, a concurrent hashtable.

What we have here is a quite simple hash storage. Allthemore simple, more robust and scalable.

Hash Interemediate page and Data page

The hash storage has two types of pages: HashIntermediatePage and HashDataPage. HashIntermediatePage, starting from the root page, points down to other intermediate pages, and the level-0 intermediate pages point to HashDataPage. HashDataPage has a next-pointer. One entry (pointer) in a level-0 intermediate page corresponds to a hash bin. Usually one hash bin corresponds to a very small number of data pages, zero, one or rarely two.

foedus::storage::hash::HashIntermediatePage foedus::storage::hash::HashDataPage

Singly-linked data pages, hopefully rarely used

When a hash bin receives many records or very long key or values, a data page contains a link to next page that forms a singly-linked list of pages. Although this is a dual page pointer, we use only one of them. Snapshot hash pages of course point to only snapshot hash pages. Volatile hash pages, to simplify, also point to only volatile hash pages.

In other words, when we make a volatile version of any page in a hash bin, we instantiate volatile pages for all pages in the hash bin. This might sound costly, but there should be only 1 or only occasionaly a few pages in the bin, assuming 1) bin-bits that is large enough, and 2) good hash function.

Locking Protocol

Intermediate pages are completely lock-free. Data pages do have per-page and per-tuple locks. Hopefully most locks are per-tuple, meaning just taking the TID of the tuple as read-set or write-set. However, there are a few cases the thread must take an exclusive lock in page-header.

• Inserting a new tuple. A system-transaction takes a page-lock, places a logically-deleted tuple with the hash/key, modifies the page header, releases the lock.
• Installing a next-page pointer. A system-transaction creates an empty next-page, takes a page-lock, installs the pointer to the new page, modifies the page header, releases the lock.
• Migrating a tuple for expansion. Also a system transaction. Detailed in next section.
• Miss-search. A user-transaction adds the page header of the tail page to PageVersionSet and verifies it at pre-commit.

All of the above are quite similar to masstree package's insertion/splits/miss-search. Like masstree package, the full-hash/key of a physical tuple is immutable once installed. We only use logical deletion flags and "moved" bits to allow record expansion. Also like masstree, other operations proceed without locks or in many cases even atomic operations, just a few memory barriers. For example, deletion just puts a logical deletion flag to the record without page-lock. Reading is completely atomics-free as far as you find the exact record (miss-search is a bit more complicated as above).

Flags in TID of Hash storages

To implement the above protocol, the moved bit in TID has a bit different meaning from masstree package. It means that the corresponding record for the full-hash/key is somewhere later in the list. When we need to expand a record space that is not at the end, we insert a new physical tuple for the record with large space, then put the "moved" bit in the original physical record. If threads see the flag while processing, it skips such a record. If pre-commit sees the flag because of concurrent migration, it tracks the moved record just like Master-Tree protocol. The idea is almost the same, but here the tracking is much simpler. Just follow the linked list.

History note, or a tombstone

We initially considered a bit more fancy hash storages (namely Cuckoo Hashing), but we didn't see enough benefits to justify its limitations (eg, how to structure snapshot pages if a tuple might be placed in two bins!). The only case it is useful is when the hash bins are really close to full, but we'll just have larger hash storages to avoid such a case. On huge NVRAM (whose density will also quickly grow), 100% fill-factor doesn't buy us anything significant over 50%. Hence discarded that plan. A sad war story, but ain't gonna win all wars. Keep it simple stupid, men.

Classes
struct	BloomFilterFingerprint
	A fingerprint for bloom filter in each HashDataPage. More...
struct	ComposedBin
	Represents an output of composer on one bin. More...
struct	ComposedBinsBuffer
	Abstracts how we batch-read several HashComposedBinsPage emit from individual composers. More...
struct	ComposedBinsMergedStream
	Packages all ComposedBinsBuffer to easily extract bins of current interest. More...
struct	DataPageBloomFilter
	To quickly check whether a HashDataPage might contain a specific hash value, we maintain a non-counting bloom filter in each page. More...
struct	HashBinRange
	Represents a range of hash bins in a hash storage, such as what an intermediate page is responsible for. More...
struct	HashCombo
	A set of information that are used in many places, extracted from the given key. More...
struct	HashCommonLogType
	A base class for HashInsertLogType/HashDeleteLogType/HashOverwriteLogType. More...
class	HashComposeContext
	HashComposer's compose() implementation separated from the class itself. More...
struct	HashComposedBinsPage
	A page to pack many ComposedBin as an output of composer. More...
class	HashComposer
	Composer for a hash storage. More...
struct	HashCreateLogType
	Log type of CREATE HASH STORAGE operation. More...
class	HashDataPage
	Represents an individual data page in Hashtable Storage. More...
struct	HashDeleteLogType
	Log type of hash-storage's delete operation. More...
struct	HashInsertLogType
	Log type of hash-storage's insert operation. More...
class	HashIntermediatePage
	Represents an intermediate page in Hashtable Storage. More...
struct	HashMetadata
	Metadata of an hash storage. More...
struct	HashMetadataSerializer
struct	HashOverwriteLogType
	Log type of hash-storage's overwrite operation. More...
class	HashPartitioner
	Partitioner for a hash storage. More...
struct	HashPartitionerData
class	HashStorage
	Represents a key-value store based on a dense and regular hash. More...
struct	HashStorageControlBlock
	Shared data of this storage type. More...
class	HashStoragePimpl
	Pimpl object of HashStorage. More...
class	HashTmpBin
	An in-memory single-threaded data structure to compose tuples in a hash bin. More...
struct	HashUpdateLogType
	Log type of hash-storage's update operation. More...
union	IntermediateRoute
	Compactly represents the route of intermediate pages to reach the given hash bin. More...
struct	RecordLocation
	return value of locate_record(). More...
struct	ReserveRecords
	A system transaction to reserve a physical record(s) in a hash data page. More...
struct	SortEntry
	Used in sort_batch(). More...
struct	TmpSnashotPage

Typedefs
typedef HashIntermediatePage	HashRootInfoPage
	Output of one compose() call, which are then combined in construct_root(). More...
typedef uint64_t	HashValue
	Represents a full 64-bit hash value calculated from a key. More...
typedef uint64_t	HashBin
	Represents a bin of a hash value. More...
typedef uint16_t	DataPageSlotIndex
typedef uint16_t	KeyLength
	Represents a byte-length of a key in this package. More...
typedef uint16_t	PayloadLength
	Represents a byte-length of a payload in this package. More...

Functions
HashValue	hashinate (const void *key, uint16_t key_length)
	Calculates hash value for general input. More...
template<typename T >
HashValue	hashinate (T key)
	Calculates hash value for a primitive type. More...
uint64_t	fanout_power (uint8_t exponent)
uint8_t	bins_to_level (uint64_t bins)
void	hash_intermediate_volatile_page_init (const VolatilePageInitArguments &args)
	volatile page initialize callback for HashIntermediatePage. More...
void	hash_data_volatile_page_init (const VolatilePageInitArguments &args)
	volatile page initialize callback for HashDataPage. More...
std::ostream &	operator<< (std::ostream &o, const HashCombo &v)
HashDataPage *	resolve_data_impl (const memory::GlobalVolatilePageResolver &resolver, VolatilePagePointer pointer)
HashIntermediatePage *	resolve_intermediate_impl (const memory::GlobalVolatilePageResolver &resolver, VolatilePagePointer pointer)
std::ostream &	operator<< (std::ostream &o, const BloomFilterFingerprint &v)
std::ostream &	operator<< (std::ostream &o, const IntermediateRoute &v)
std::ostream &	operator<< (std::ostream &o, const DataPageBloomFilter &v)
std::ostream &	operator<< (std::ostream &o, const HashBinRange &v)
std::ostream &	operator<< (std::ostream &o, const HashCreateLogType &v)
std::ostream &	operator<< (std::ostream &o, const HashInsertLogType &v)
std::ostream &	operator<< (std::ostream &o, const HashDeleteLogType &v)
std::ostream &	operator<< (std::ostream &o, const HashUpdateLogType &v)
std::ostream &	operator<< (std::ostream &o, const HashOverwriteLogType &v)
std::ostream &	operator<< (std::ostream &o, const HashMetadata &v)
std::ostream &	operator<< (std::ostream &o, const HashIntermediatePage &v)
std::ostream &	operator<< (std::ostream &o, const HashDataPage &v)
void	release_parallel (Engine *engine, VolatilePagePointer pointer)
void	design_partition_thread (HashPartitioner *partitioner, uint16_t task)
void	prepare_sort_entries (uint8_t bin_shifts, const Partitioner::SortBatchArguments &args, SortEntry *entries)
	subroutine of sort_batch More...
uint32_t	compact_logs (uint8_t, const Partitioner::SortBatchArguments &args, SortEntry *entries)
	subroutine of sort_batch More...
std::ostream &	operator<< (std::ostream &o, const HashPartitioner &v)
std::ostream &	operator<< (std::ostream &o, const HashStorage &v)
uint16_t	adjust_payload_hint (uint16_t payload_count, uint16_t physical_payload_hint)
std::ostream &	operator<< (std::ostream &o, const HashTmpBin &v)

Variables
const uint16_t	kHashComposedBinsPageMaxBins = (kPageSize - 80) / sizeof(ComposedBin)
const uint64_t	kXxhashKeySeed = 0x3f119e0435262a17ULL
	Default seed value used for xxhash's xxh32/64 to hashinate keys. More...
const uint16_t	kHashDataPageBloomFilterBytes = 64
	Byte size of bloom filter in each HashDataPage. More...
const uint16_t	kHashDataPageBloomFilterBits = kHashDataPageBloomFilterBytes * 8
	Bit size of bloom filter in each HashDataPage. More...
const uint8_t	kHashDataPageBloomFilterIndexSize = 9U
	How many bits we need in order to represent an index in bloom filter in each HashDataPage. More...
const HashValue	kHashDataPageBloomFilterIndexMask = (1U << kHashDataPageBloomFilterIndexSize) - 1U
const uint8_t	kHashDataPageBloomFilterHashes = 3
	Number of hash functions (k) of bloom filter in each HashDataPage. More...
const uint16_t	kHashIntermediatePageHeaderSize = 64
	Byte size of header in an intermediate page of hash storage. More...
const uint8_t	kHashIntermediatePageFanout
	Number of pointers in an intermediate page of hash storage. More...
const uint64_t	kFanout64 = kHashIntermediatePageFanout
	just to write the following concisely More...
const uint64_t	kHashMaxBins []
	kHashTotalBins[n] gives the maximum number of hash bins n-level hash can hold. More...
const uint8_t	kHashMaxLevels = 8
	Max level of intermediate pages. More...
const uint16_t	kHashDataPageHeaderSize = 128
	Byte size of header in data page of hash storage. More...
const uint16_t	kHashDataPageDataSize = kPageSize - kHashDataPageHeaderSize
	Body data byte size in data page of hash storage. More...
const uint8_t	kHashMinBinBits = 7U
	Minimum number allowed for bin-bits. More...
const uint8_t	kHashMaxBinBits = 48U
	Maximum number allowed for bin-bits. More...
const HashBin	kInvalidHashBin = 1ULL << kHashMaxBinBits
	This value or larger never appears as a valid HashBin. More...
const DataPageSlotIndex	kSlotNotFound = 0xFFFFU

Typedef Documentation

typedef uint16_t foedus::storage::hash::DataPageSlotIndex

Definition at line 196 of file hash_id.hpp.

Function Documentation

uint16_t foedus::storage::hash::adjust_payload_hint	(	uint16_t	payload_count,
		uint16_t	physical_payload_hint
	)

Definition at line 250 of file hash_storage_pimpl.cpp.

References foedus::assorted::align8(), and ASSERT_ND.

Referenced by foedus::storage::hash::HashStoragePimpl::insert_record(), and foedus::storage::hash::HashStoragePimpl::upsert_record().

                                                                                     {
  ASSERT_ND(physical_payload_hint >= payload_count);  // if not, most likely misuse.
  if (physical_payload_hint < payload_count) {
    physical_payload_hint = payload_count;
  }
  physical_payload_hint = assorted::align8(physical_payload_hint);
  return physical_payload_hint;
}

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t foedus::storage::hash::compact_logs	(	uint8_t	,
		const Partitioner::SortBatchArguments &	args,
		SortEntry *	entries
	)

subroutine of sort_batch

Definition at line 261 of file hash_partitioner_impl.cpp.

References foedus::storage::hash::SortEntry::get_position(), foedus::storage::Partitioner::SortBatchArguments::logs_count_, and foedus::storage::Partitioner::SortBatchArguments::output_buffer_.

Referenced by foedus::storage::hash::HashPartitioner::sort_batch().

                      {
  // TASK(Hideaki) mapper side compaction.
  // Unlike array, we have to consider all combinations of insert/delete/overwrite.
  // Also needs to exactly compare keys. We probably need to store hashes in log to make it worth.
  for (uint32_t i = 0; i < args.logs_count_; ++i) {
    args.output_buffer_[i] = entries[i].get_position();
  }
  return args.logs_count_;
/*
  // CPU profile of partition_hash_perf: ??%.
  uint32_t result_count = 1;
  args.output_buffer_[0] = entries[0].get_position();
  HashBin prev_bin = entries[0].get_bin();
  for (uint32_t i = 1; i < args.logs_count_; ++i) {
    // compact the logs if the same offset appears in a row, and covers the same data region.
    // because we sorted it by offset and then ordinal, later logs can overwrite the earlier one.
    HashBin cur_bin = entries[i].get_bin();
    if (UNLIKELY(cur_bin == prev_bin)) {
      const log::RecordLogType* prev_p = args.log_buffer_.resolve(entries[i - 1].get_position());
      log::RecordLogType* next_p = args.log_buffer_.resolve(entries[i].get_position());
      if (prev_p->header_.log_type_code_ != next_p->header_.log_type_code_) {
        // increment log can be superseded by overwrite log,
        // overwrite log can be merged with increment log.
        // however, these usecases are probably much less frequent than the following.
        // so, we don't compact this case so far.
      } else if (prev_p->header_.get_type() == log::kLogCodeHashOverwrite) {
        // two overwrite logs might be compacted
        const HashOverwriteLogType* prev = reinterpret_cast<const HashOverwriteLogType*>(prev_p);
        const HashOverwriteLogType* next = reinterpret_cast<const HashOverwriteLogType*>(next_p);
        // is the data region same or superseded?
        uint16_t prev_begin = prev->payload_offset_;
        uint16_t prev_end = prev_begin + prev->payload_count_;
        uint16_t next_begin = next->payload_offset_;
        uint16_t next_end = next_begin + next->payload_count_;
        if (next_begin <= prev_begin && next_end >= prev_end) {
          --result_count;
        }

        // the logic checks data range against only the previous entry.
        // we might have a situation where 3 or more log entries have the same hash offset
        // and the data regions are like following
        // Log 1: [4, 8) bytes, Log 2: [8, 12) bytes, Log 3: [4, 8) bytes
        // If we check further, Log 3 can eliminate Log 1. However, the check is expensive..
      } else {
        // two increment logs of same type/offset can be merged into one.
        ASSERT_ND(prev_p->header_.get_type() == log::kLogCodeHashIncrement);
        const HashIncrementLogType* prev = reinterpret_cast<const HashIncrementLogType*>(prev_p);
        HashIncrementLogType* next = reinterpret_cast<HashIncrementLogType*>(next_p);
        if (prev->value_type_ == next->value_type_
          && prev->payload_offset_ == next->payload_offset_) {
          // add up the prev's addendum to next, then delete prev.
          next->merge(*prev);
          --result_count;
        }
      }
    } else {
      prev_bin = cur_bin;
    }
    args.output_buffer_[result_count] = entries[i].get_position();
    ++result_count;
  }
  return result_count;
  */
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::hash::design_partition_thread	(	HashPartitioner *	partitioner,
		uint16_t	task
	)

Definition at line 64 of file hash_partitioner_impl.cpp.

References foedus::storage::hash::HashPartitioner::design_partition_task().

Referenced by foedus::storage::hash::HashPartitioner::design_partition().

                                                                          {
  partitioner->design_partition_task(task);
}

Here is the call graph for this function:

Here is the caller graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashBinRange &	v
	)

Defined in hash_id.cpp

Definition at line 28 of file hash_id.cpp.

References foedus::storage::hash::HashBinRange::begin_, and foedus::storage::hash::HashBinRange::end_.

                                                             {
  o << "<HashBinRange from=\""
    << assorted::Hex(v.begin_)
    << "\" to=\"" << assorted::Hex(v.end_) << "\" />";
  return o;
}

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashIntermediatePage &	v
	)

Definition at line 31 of file hash_page_debug.cpp.

References foedus::storage::hash::HashBinRange::begin_, foedus::storage::hash::HashIntermediatePage::get_bin_range(), foedus::storage::hash::HashIntermediatePage::get_level(), foedus::storage::hash::HashIntermediatePage::get_pointer(), foedus::storage::hash::HashIntermediatePage::header(), foedus::storage::DualPagePointer::is_both_null(), kHashIntermediatePageFanout, and kHashMaxBins.

                                                                     {
  o << "<HashIntermediatePage>";
  o << std::endl << "  <vaddr>" << assorted::Hex(reinterpret_cast<uintptr_t>(&v), 16) << "</vaddr>";
  o << std::endl << "  " << v.header();
  o << std::endl << "  <level>" << static_cast<int>(v.get_level()) << "</level>";
  o << std::endl << "  " << v.get_bin_range();
  HashBin total_begin = v.get_bin_range().begin_;
  HashBin interval = kHashMaxBins[v.get_level()];
  for (uint16_t i = 0; i < kHashIntermediatePageFanout; ++i) {
    DualPagePointer pointer = v.get_pointer(i);
    if (pointer.is_both_null()) {
      continue;
    }
    o << std::endl << "  <Pointer index=\"" << static_cast<int>(i)
      << "\" bin_begin=\"" << (total_begin + i * interval)
      << "\">" << pointer << "</Pointer>";
  }
  o << "</HashIntermediatePage>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashMetadata &	v
	)

Definition at line 34 of file hash_metadata.cpp.

                                                             {
  o << HashMetadataSerializer(const_cast<HashMetadata*>(&v));
  return o;
}

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashCombo &	v
	)

Definition at line 37 of file hash_combo.cpp.

References foedus::storage::hash::HashCombo::bin_, foedus::storage::hash::HashCombo::fingerprint_, foedus::storage::hash::HashCombo::hash_, and foedus::storage::hash::HashCombo::route_.

                                                          {
  o << "<HashCombo>"
    << "<hash>" << assorted::Hex(v.hash_, 16) << "</hash>"
    << "<bin>" << v.bin_ << "</bin>"
    << v.fingerprint_
    << v.route_
    << "</HashCombo>";
  return o;
}

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashCreateLogType &	v
	)

Definition at line 47 of file hash_log_types.cpp.

References foedus::storage::hash::HashCreateLogType::metadata_.

                                                                  {
  o << "<HashCreateLog>" << v.metadata_ << "</HashCreateLog>";
  return o;
}

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashDataPage &	v
	)

Definition at line 52 of file hash_page_debug.cpp.

References foedus::storage::hash::DataPageBloomFilter::extract_fingerprint(), foedus::storage::hash::HashDataPage::Slot::get_aligned_key_length(), foedus::storage::hash::HashDataPage::get_bin(), foedus::storage::hash::HashDataPage::get_record_count(), foedus::storage::hash::HashDataPage::get_slot_address(), foedus::storage::hash::HashDataPage::Slot::hash_, foedus::storage::hash::HashDataPage::header(), foedus::storage::hash::HashDataPage::Slot::key_length_, foedus::storage::hash::HashDataPage::next_page(), foedus::storage::hash::HashDataPage::Slot::offset_, foedus::storage::hash::HashDataPage::Slot::payload_length_, foedus::storage::hash::HashDataPage::Slot::physical_record_length_, foedus::storage::hash::HashDataPage::record_from_offset(), and foedus::storage::hash::HashDataPage::Slot::tid_.

                                                             {
  o << "<HashDataPage>";
  o << std::endl << "  <vaddr>" << assorted::Hex(reinterpret_cast<uintptr_t>(&v), 16) << "</vaddr>";
  o << std::endl << v.header();
  o << std::endl << "  <bin>" << assorted::Hex(v.get_bin()) << "</bin>";
  uint16_t records = v.get_record_count();
  o << std::endl << "  <record_count>" << records << "</record_count>";
  o << std::endl << "  <next_page>" << v.next_page() << "</next_page>";
  o << std::endl << "  <records>";
  for (DataPageSlotIndex i = 0; i < records; ++i) {
    const HashDataPage::Slot* slot = v.get_slot_address(i);
    o << std::endl << "  <record index=\"" << i
      << "\" hash=\"" << assorted::Hex(slot->hash_, 16)
      << "\" physical_record_len=\"" << slot->physical_record_length_
      << "\" key_length_=\"" << slot->key_length_
      << "\" offset=\"" << slot->offset_
      << "\" payload_len=\"" << slot->payload_length_
      << "\">";
    const char* data = v.record_from_offset(slot->offset_);
    std::string key(data, slot->key_length_);
    o << "<key>" << assorted::HexString(key) << "</key>";
    if (slot->payload_length_ > 0) {
      std::string payload(data + slot->get_aligned_key_length(), slot->payload_length_);
      o << "<payload>" << assorted::HexString(payload) << "</payload>";
    }
    BloomFilterFingerprint fingerprint = DataPageBloomFilter::extract_fingerprint(slot->hash_);
    o << fingerprint;
    o << slot->tid_;
    o << "</record>";
  }
  o << std::endl << "  </records>";
  o << std::endl << "  <BloomFilter>" << v.bloom_filter_ << "</BloomFilter>";
  o << "</HashDataPage>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashInsertLogType &	v
	)

Definition at line 52 of file hash_log_types.cpp.

References foedus::storage::hash::HashCommonLogType::bin_bits_, foedus::storage::hash::HashCommonLogType::get_key(), foedus::storage::hash::HashCommonLogType::get_payload(), foedus::storage::hash::HashCommonLogType::hash_, foedus::storage::hash::HashCommonLogType::key_length_, and foedus::storage::hash::HashCommonLogType::payload_count_.

                                                                  {
  o << "<HashInsertLogType>"
    << "<key_length_>" << v.key_length_ << "</key_length_>"
    << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
    << "<bin_bits_>" << static_cast<int>(v.bin_bits_) << "</bin_bits_>"
    << "<hash_>" << assorted::Hex(v.hash_, 16) << "</hash_>"
    << "<payload_count_>" << v.payload_count_ << "</payload_count_>"
    << "<payload_>" << assorted::Top(v.get_payload(), v.payload_count_) << "</payload_>"
    << "</HashInsertLogType>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const BloomFilterFingerprint &	v
	)

Definition at line 55 of file hash_hashinate.cpp.

References foedus::storage::hash::BloomFilterFingerprint::indexes_, and kHashDataPageBloomFilterHashes.

                                                                       {
  o << "<Fingerprint indexes=\"";
  for (uint8_t i = 0; i < kHashDataPageBloomFilterHashes; ++i) {
    o << v.indexes_[i] << ",";
  }
  o << "\" />";
  return o;
}

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashDeleteLogType &	v
	)

Definition at line 64 of file hash_log_types.cpp.

References foedus::storage::hash::HashCommonLogType::bin_bits_, foedus::storage::hash::HashCommonLogType::get_key(), foedus::storage::hash::HashCommonLogType::hash_, and foedus::storage::hash::HashCommonLogType::key_length_.

                                                                  {
  o << "<HashDeleteLogType>"
    << "<key_length_>" << v.key_length_ << "</key_length_>"
    << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
    << "<bin_bits_>" << static_cast<int>(v.bin_bits_) << "</bin_bits_>"
    << "<hash_>" << assorted::Hex(v.hash_, 16) << "</hash_>"
    << "</HashDeleteLogType>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const IntermediateRoute &	v
	)

Definition at line 64 of file hash_hashinate.cpp.

References foedus::storage::hash::IntermediateRoute::route.

                                                                  {
  o << "<Route>";
  for (uint8_t i = 0; i < 8U; ++i) {
    o << assorted::Hex(v.route[i], 2) << " ";
  }
  o << "</Route>";
  return o;
}

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const DataPageBloomFilter &	v
	)

Definition at line 73 of file hash_hashinate.cpp.

References kHashDataPageBloomFilterBytes, and foedus::storage::hash::DataPageBloomFilter::values_.

                                                                    {
  o << "<DataPageBloomFilter>" << std::endl;
  // one line for 8 bytes
  for (uint16_t i = 0; i * 8U < kHashDataPageBloomFilterBytes; ++i) {
    o << "  <Bytes row=\"" << i << "\">";
    for (uint16_t j = i * 8U; j < (i + 1U) * 8U && j < kHashDataPageBloomFilterBytes; ++j) {
      o << assorted::Hex(v.values_[j], 2) << " ";
    }
    o << "</Bytes>" << std::endl;
  }
  o << "</DataPageBloomFilter>";
  return o;
}

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashUpdateLogType &	v
	)

Definition at line 74 of file hash_log_types.cpp.

References foedus::storage::hash::HashCommonLogType::bin_bits_, foedus::storage::hash::HashCommonLogType::get_key(), foedus::storage::hash::HashCommonLogType::get_payload(), foedus::storage::hash::HashCommonLogType::hash_, foedus::storage::hash::HashCommonLogType::key_length_, and foedus::storage::hash::HashCommonLogType::payload_count_.

                                                                  {
  o << "<HashUpdateLogType>"
    << "<key_length_>" << v.key_length_ << "</key_length_>"
    << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
    << "<bin_bits_>" << static_cast<int>(v.bin_bits_) << "</bin_bits_>"
    << "<hash_>" << assorted::Hex(v.hash_, 16) << "</hash_>"
    << "<payload_count_>" << v.payload_count_ << "</payload_count_>"
    << "<payload_>" << assorted::Top(v.get_payload(), v.payload_count_) << "</payload_>"
    << "</HashUpdateLogType>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashOverwriteLogType &	v
	)

Definition at line 86 of file hash_log_types.cpp.

References foedus::storage::hash::HashCommonLogType::bin_bits_, foedus::storage::hash::HashCommonLogType::get_key(), foedus::storage::hash::HashCommonLogType::get_payload(), foedus::storage::hash::HashCommonLogType::hash_, foedus::storage::hash::HashCommonLogType::key_length_, foedus::storage::hash::HashCommonLogType::payload_count_, and foedus::storage::hash::HashCommonLogType::payload_offset_.

                                                                     {
  o << "<HashOverwriteLog>"
    << "<key_length_>" << v.key_length_ << "</key_length_>"
    << "<key_>" << assorted::Top(v.get_key(), v.key_length_) << "</key_>"
    << "<bin_bits_>" << static_cast<int>(v.bin_bits_) << "</bin_bits_>"
    << "<hash_>" << assorted::Hex(v.hash_, 16) << "</hash_>"
    << "<payload_offset_>" << v.payload_offset_ << "</payload_offset_>"
    << "<payload_count_>" << v.payload_count_ << "</payload_count_>"
    << "<payload_>" << assorted::Top(v.get_payload(), v.payload_count_) << "</payload_>"
    << "</HashOverwriteLog>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashStorage &	v
	)

Definition at line 247 of file hash_storage.cpp.

References foedus::storage::hash::HashMetadata::bin_bits_, foedus::Attachable< CONTROL_BLOCK >::control_block_, foedus::storage::Storage< CONTROL_BLOCK >::get_id(), foedus::storage::Storage< CONTROL_BLOCK >::get_name(), and foedus::storage::hash::HashStorageControlBlock::meta_.

                                                            {
  o << "<HashStorage>"
    << "<id>" << v.get_id() << "</id>"
    << "<name>" << v.get_name() << "</name>"
    << "<bin_bits>" << static_cast<int>(v.control_block_->meta_.bin_bits_) << "</bin_bits>"
    << "</HashStorage>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashTmpBin &	v
	)

Definition at line 287 of file hash_tmpbin.cpp.

References foedus::storage::hash::HashTmpBin::get_first_record(), foedus::storage::hash::HashTmpBin::Record::get_key(), foedus::storage::hash::HashTmpBin::Record::get_payload(), foedus::storage::hash::HashTmpBin::get_record(), foedus::storage::hash::HashTmpBin::get_records_consumed(), foedus::storage::hash::HashTmpBin::Record::hash_, foedus::storage::hash::HashTmpBin::kBucketCount, foedus::storage::hash::HashTmpBin::Record::key_length_, foedus::storage::hash::HashTmpBin::Record::next_, foedus::storage::hash::HashTmpBin::Record::payload_length_, and foedus::storage::hash::HashTmpBin::Record::xct_id_.

                                                           {
  // Each bin shouldn't have that many records... so, output everything!
  o << "<HashTmpBin>" << std::endl;
  o << "  " << v.memory_ << std::endl;
  o << "  <records_capacity_>" << v.records_capacity_ << "</records_capacity_>" << std::endl;
  o << "  <records_consumed_>" << v.records_consumed_ << "</records_consumed_>" << std::endl;
  o << "  <buckets_>" << std::endl;
  for (uint32_t i = 0; i < HashTmpBin::kBucketCount; ++i) {
    if (v.buckets_[i] != 0) {
      o << "    <bucket idx=\"" << i << "\" head_rec=\"" << v.buckets_[i] << "\" />" << std::endl;
    }
  }
  o << "  </buckets_>" << std::endl;
  o << "  <records_>" << std::endl;
  uint32_t begin = v.get_first_record();
  for (uint32_t i = begin; i < v.get_records_consumed(); ++i) {
    HashTmpBin::Record* record = v.get_record(i);
    o << "    <record id=\"" << i << "\" hash=\"" << assorted::Hex(record->hash_, 16) << "\"";
    if (record->next_) {
      o << " next_rec=\"" << record->next_ << "\"";
    }
    o << ">";
    o << "<key>" << assorted::HexString(std::string(record->get_key(), record->key_length_))
      << "</key>";
    o << "<payload>"
      << assorted::HexString(std::string(record->get_payload(), record->payload_length_))
      << "</payload>";
    o << record->xct_id_;
    o << "</record>" << std::endl;
  }
  o << "  </records_>" << std::endl;
  o << "</HashTmpBin>";
  return o;
}

Here is the call graph for this function:

std::ostream& foedus::storage::hash::operator<<	(	std::ostream &	o,
		const HashPartitioner &	v
	)

Definition at line 364 of file hash_partitioner_impl.cpp.

References foedus::storage::hash::HashPartitionerData::levels_, and foedus::storage::hash::HashPartitionerData::total_bin_count_.

                                                                {
  o << "<HashPartitioner>";
  if (v.data_) {
    o << "<levels_>" << static_cast<int>(v.data_->levels_) << "</levels_>"
      << "<total_bin_count_>" << v.data_->total_bin_count_ << "</total_bin_count_>";
  } else {
    o << "Not yet designed";
  }
  o << "</HashPartitioner>";
  return o;
}

void foedus::storage::hash::prepare_sort_entries	(	uint8_t	bin_shifts,
		const Partitioner::SortBatchArguments &	args,
		SortEntry *	entries
	)

subroutine of sort_batch

Definition at line 236 of file hash_partitioner_impl.cpp.

References ASSERT_ND, foedus::storage::hash::HashCommonLogType::assert_type(), foedus::storage::Partitioner::SortBatchArguments::base_epoch_, foedus::xct::XctId::get_epoch(), foedus::xct::XctId::get_ordinal(), foedus::storage::hash::HashCommonLogType::hash_, foedus::log::BaseLogType::header_, foedus::storage::Partitioner::SortBatchArguments::log_buffer_, foedus::storage::Partitioner::SortBatchArguments::log_positions_, foedus::storage::Partitioner::SortBatchArguments::logs_count_, foedus::snapshot::LogBuffer::resolve(), foedus::storage::hash::SortEntry::set(), foedus::Epoch::subtract(), and foedus::log::LogHeader::xct_id_.

Referenced by foedus::storage::hash::HashPartitioner::sort_batch().

                      {
  // CPU profile of partition_hash_perf: ??%.
  const Epoch base_epoch = args.base_epoch_;
  for (uint32_t i = 0; i < args.logs_count_; ++i) {
    const HashCommonLogType* log_entry = reinterpret_cast<const HashCommonLogType*>(
      args.log_buffer_.resolve(args.log_positions_[i]));
    log_entry->assert_type();
    Epoch epoch = log_entry->header_.xct_id_.get_epoch();
    ASSERT_ND(epoch.subtract(base_epoch) < (1U << 16));
    uint16_t compressed_epoch = epoch.subtract(base_epoch);
    // this is expensive.. should keep hash in log entries
    HashValue hash = log_entry->hash_;
    entries[i].set(
      hash >> bin_shifts,
      compressed_epoch,
      log_entry->header_.xct_id_.get_ordinal(),
      args.log_positions_[i]);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::hash::release_parallel	(	Engine *	engine,
		VolatilePagePointer	pointer
	)

Definition at line 260 of file hash_page_impl.cpp.

References ASSERT_ND, foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), foedus::storage::PageHeader::get_page_type(), foedus::storage::hash::HashIntermediatePage::header(), foedus::storage::kHashIntermediatePageType, foedus::storage::hash::HashIntermediatePage::release_pages_recursive(), and foedus::memory::GlobalVolatilePageResolver::resolve_offset().

Referenced by foedus::storage::hash::HashIntermediatePage::release_pages_recursive_parallel().

                                                                   {
  const memory::GlobalVolatilePageResolver& page_resolver
    = engine->get_memory_manager()->get_global_volatile_page_resolver();
  HashIntermediatePage* p
    = reinterpret_cast<HashIntermediatePage*>(page_resolver.resolve_offset(pointer));
  ASSERT_ND(p->header().get_page_type() == kHashIntermediatePageType);
  memory::PageReleaseBatch release_batch(engine);
  p->release_pages_recursive(page_resolver, &release_batch);
  release_batch.release_all();
}

Here is the call graph for this function:

Here is the caller graph for this function:

HashDataPage* foedus::storage::hash::resolve_data_impl ( const memory::GlobalVolatilePageResolver &  resolver, VolatilePagePointer  pointer  )

inline

Definition at line 59 of file hash_composer_impl.cpp.

References ASSERT_ND, foedus::storage::construct_volatile_page_pointer(), foedus::storage::PageHeader::get_page_type(), foedus::storage::hash::HashDataPage::header(), foedus::storage::VolatilePagePointer::is_equivalent(), foedus::storage::VolatilePagePointer::is_null(), foedus::storage::kHashDataPageType, foedus::storage::PageHeader::page_id_, and foedus::memory::GlobalVolatilePageResolver::resolve_offset().

                               {
  if (pointer.is_null()) {
    return nullptr;
  }
  HashDataPage* ret = reinterpret_cast<HashDataPage*>(resolver.resolve_offset(pointer));
  ASSERT_ND(ret->header().get_page_type() == kHashDataPageType);
  ASSERT_ND(pointer.is_equivalent(construct_volatile_page_pointer(ret->header().page_id_)));
  return ret;
}

Here is the call graph for this function:

HashIntermediatePage* foedus::storage::hash::resolve_intermediate_impl ( const memory::GlobalVolatilePageResolver &  resolver, VolatilePagePointer  pointer  )

inline

Definition at line 71 of file hash_composer_impl.cpp.

References ASSERT_ND, foedus::storage::construct_volatile_page_pointer(), foedus::storage::PageHeader::get_page_type(), foedus::storage::hash::HashIntermediatePage::header(), foedus::storage::VolatilePagePointer::is_equivalent(), foedus::storage::VolatilePagePointer::is_null(), foedus::storage::kHashIntermediatePageType, foedus::storage::PageHeader::page_id_, and foedus::memory::GlobalVolatilePageResolver::resolve_offset().

                               {
  if (pointer.is_null()) {
    return nullptr;
  }
  HashIntermediatePage* ret
    = reinterpret_cast<HashIntermediatePage*>(resolver.resolve_offset(pointer));
  ASSERT_ND(ret->header().get_page_type() == kHashIntermediatePageType);
  ASSERT_ND(pointer.is_equivalent(construct_volatile_page_pointer(ret->header().page_id_)));
  return ret;
}

Here is the call graph for this function:

Variable Documentation

const uint64_t foedus::storage::hash::kFanout64 = kHashIntermediatePageFanout

just to write the following concisely

Definition at line 65 of file hash_id.hpp.

const uint16_t foedus::storage::hash::kHashComposedBinsPageMaxBins = (kPageSize - 80) / sizeof(ComposedBin)

Definition at line 90 of file hash_composed_bins_impl.hpp.

const HashValue foedus::storage::hash::kHashDataPageBloomFilterIndexMask = (1U << kHashDataPageBloomFilterIndexSize) - 1U

Definition at line 88 of file hash_hashinate.hpp.

Referenced by foedus::storage::hash::DataPageBloomFilter::extract_fingerprint().

const HashBin foedus::storage::hash::kInvalidHashBin = 1ULL << kHashMaxBinBits

This value or larger never appears as a valid HashBin.

Definition at line 162 of file hash_id.hpp.

Referenced by foedus::storage::hash::ComposedBinsMergedStream::init(), foedus::storage::hash::ComposedBinsMergedStream::open_path(), foedus::storage::hash::ComposedBinsMergedStream::process_a_bin(), and foedus::storage::hash::ComposedBinsMergedStream::switch_path().

const DataPageSlotIndex foedus::storage::hash::kSlotNotFound = 0xFFFFU

Definition at line 197 of file hash_id.hpp.

Referenced by foedus::storage::hash::RecordLocation::clear(), foedus::storage::hash::ReserveRecords::find_or_create_or_expand(), foedus::storage::hash::RecordLocation::is_found(), foedus::storage::hash::HashStoragePimpl::locate_record(), foedus::storage::hash::HashStoragePimpl::locate_record_in_snapshot(), foedus::storage::hash::HashDataPage::search_key_physical(), and foedus::storage::hash::HashStoragePimpl::track_moved_record_search().