Masstree Storage, 64-bit B-tries with internal B-trees. More...

Detailed Description

Masstree Storage, 64-bit B-tries with internal B-trees.

Although the package name says masstree [YANDONG12], we call our implementation Master-Tree. There are a few differences from the original Masstree.

Foster-Twin

See our paper (lame, yes).

Remainder vs Remaining Key

Througout our code, we always use the word remainder rather than remaining-key. In [YANDONG12] and [TU13], the word remaining-key meant the leftover of the entire key after removing the common prefixes in previous B-trie layers. For example, key "abcd" has remaining key "abcd" in layer-0. key "abcd12345678" has remaining keys "abcd12345678" in layer-0 and "5678" in layer-1. When the length of remaining-key is more than 8-bytes, the page also stores suffix, which is the key part after the slice in the layer. For example, "abcd12345678" stores "5678" as suffix in layer-0 while no suffix in layer-1.

Up to here, there is no difference between remainder and remaining-key. Actually, in most cases they are exactly the same.

They differ only when a record points to next layer. In the original papers/codes, the length of remaining-key is set to be 255 when the record now points to next layer, and they also overwrite the area to store suffix with next-page pointer.

In Master-Tree, we always keep the remainder even when now it points to the next layer. This simplifies many concurrency control issues, especially our foster-twin tracking algorithm. Therefore, we never change the length of remainder. It's an immutable property of the record. Instead, we have an additional mutable boolean flag "next_layer" in TID. Whether the next_layer flag is ON or OFF, all threads are safe to access the remainder. The commit protocol checks the flag and aborts if it's unexpectedly ON.

This is just a subtle difference, but allthemore subtle, it's confusing! Hence, we use a different word, remainder. Below we summarize the differences:

.	Remaining Key (Mass-Tree)	Remainder (Master-Tree)
Length	Full key length - layer*8 if not next-layer, 255 if it's now next-layer.	Full key length - layer*8 always. Keeps the original remainder length.
Suffix stored at	The beginning of data region if not next-layer, overwritten if it's now next-layer.	The beginning of data region always. Keeps the original remainder.
Length 0xFFFF means	The record is now next-layer, so the record has no suffix-region. HOWEVER, concurrent threads must be careful because it was not 0xFFFF before.	The record was initially next-layer as of creation, so the record has no suffix-region. Such a record is never moved. A record that later turned to be next-layer doesn't use this value.

References

[YANDONG12] Yandong Mao, Eddie Kohler, and Robert Tappan Morris. "Cache craftiness for fast multicore key-value storage.", EuroSys, 2012.

[TU13] Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. "Speedy transactions in multicore in-memory databases.", SOSP, 2013.

Collaboration diagram for Masstree Storage:

Files
file	fwd.hpp
	Forward declarations of classes in masstree storage package.

file	masstree_id.hpp
	Definitions of IDs in this package and a few related constant values.

file	masstree_log_types.hpp
	Declares all log types used in this storage type.

Classes
struct	foedus::storage::masstree::Adopt
	A system transaction to adopt foster twins into an intermediate page. More...

class	foedus::storage::masstree::MasstreeComposer
	Composer for an masstree storage. More...

struct	foedus::storage::masstree::MasstreeComposeContext::PathLevel
	One level in the path. More...

struct	foedus::storage::masstree::MasstreeComposeContext::FenceAndPointer

struct	foedus::storage::masstree::MasstreeComposeContext::PageBoundaryInfo
	Represents a minimal information to install a new snapshot page pointer. More...

struct	foedus::storage::masstree::MasstreeComposeContext::PageBoundarySort
	Points to PageBoundaryInfo with a sorting information. More...

class	foedus::storage::masstree::MasstreeComposeContext
	MasstreeComposer's compose() implementation separated from the class itself. More...

struct	foedus::storage::masstree::MasstreeCursor::Route
	Represents one page in the current search path from layer0-root. More...

class	foedus::storage::masstree::MasstreeCursor
	Represents a cursor object for Masstree storage. More...

struct	foedus::storage::masstree::GrowFirstLayerRoot
	A system transaction to grow a first-layer root. More...

struct	foedus::storage::masstree::GrowNonFirstLayerRoot
	A system transaction to grow a second- or depper-layer root. More...

struct	foedus::storage::masstree::MasstreeCreateLogType
	Log type of CREATE MASSTREE STORAGE operation. More...

struct	foedus::storage::masstree::MasstreeCommonLogType::RecordAddresses

struct	foedus::storage::masstree::MasstreeCommonLogType
	A base class for MasstreeInsertLogType/MasstreeDeleteLogType/MasstreeOverwriteLogType. More...

struct	foedus::storage::masstree::MasstreeInsertLogType
	Log type of masstree-storage's insert operation. More...

struct	foedus::storage::masstree::MasstreeDeleteLogType
	Log type of masstree-storage's delete operation. More...

struct	foedus::storage::masstree::MasstreeUpdateLogType
	Log type of masstree-storage's update operation. More...

struct	foedus::storage::masstree::MasstreeOverwriteLogType
	Log type of masstree-storage's overwrite operation. More...

struct	foedus::storage::masstree::MasstreeMetadata
	Metadata of a masstree storage. More...

class	foedus::storage::masstree::MasstreePage
	Common base of MasstreeIntermediatePage and MasstreeBorderPage. More...

struct	foedus::storage::masstree::MasstreeIntermediatePage::MiniPage

class	foedus::storage::masstree::MasstreeIntermediatePage
	Represents one intermediate page in Masstree Storage. More...

struct	foedus::storage::masstree::MasstreeBorderPage::SlotLengthPart
	A piece of Slot object that must be read/written in one-shot, meaning no one reads half-written values whether it reads old values or new values. More...

union	foedus::storage::masstree::MasstreeBorderPage::SlotLengthUnion

struct	foedus::storage::masstree::MasstreeBorderPage::Slot
	Fix-sized slot for each record, which is placed at the end of data region. More...

struct	foedus::storage::masstree::MasstreeBorderPage::FindKeyForReserveResult
	return value for find_key_for_reserve(). More...

class	foedus::storage::masstree::MasstreeBorderPage
	Represents one border page in Masstree Storage. More...

class	foedus::storage::masstree::MasstreePartitioner
	Partitioner for a masstree storage. More...

struct	foedus::storage::masstree::ReserveRecords
	A system transaction to reserve a physical record(s) in a border page. More...

struct	foedus::storage::masstree::SplitBorder::SplitStrategy

struct	foedus::storage::masstree::SplitBorder
	A system transaction to split a border page in Master-Tree. More...

struct	foedus::storage::masstree::SplitIntermediate::SplitStrategy
	Constructed by hierarchically reading all separators and pointers in old page. More...

struct	foedus::storage::masstree::SplitIntermediate
	A system transaction to split an intermediate page in Master-Tree. More...

struct	foedus::storage::masstree::MasstreeStorage::PeekBoundariesArguments
	Arguments for peek_volatile_page_boundaries() More...

class	foedus::storage::masstree::MasstreeStorage
	Represents a Masstree storage. More...

class	foedus::storage::masstree::MasstreeStoragePimpl
	Pimpl object of MasstreeStorage. More...

Typedefs
typedef uint8_t	foedus::storage::masstree::Layer
	Represents the depth of a B-trie layer. More...

typedef uint8_t	foedus::storage::masstree::InLayerLevel
	Represents the depth of a B-tree node in a B-trie layer. More...

typedef uint16_t	foedus::storage::masstree::KeyLength
	Represents a byte-length of a key in this package. More...

typedef uint16_t	foedus::storage::masstree::PayloadLength
	Represents a byte-length of a payload in this package. More...

typedef uint16_t	foedus::storage::masstree::DataOffset
	Byte-offset in a page. More...

typedef uint16_t	foedus::storage::masstree::SlotIndex
	Index of a record in a (border) page. More...

typedef uint64_t	foedus::storage::masstree::KeySlice
	Each key slice is an 8-byte integer. More...

Functions
template<typename T >
KeySlice	foedus::storage::masstree::normalize_primitive (T value)
	Order-preserving normalization for primitive key types. More...

template<typename T >
T	foedus::storage::masstree::denormalize_primitive (KeySlice value)
	Opposite of normalize_primitive(). More...

KeySlice	foedus::storage::masstree::normalize_be_bytes_full_aligned (const void *be_bytes)
	Convert an aligned big-endian byte array of at least 8-bytes-length to KeySlice. More...

KeySlice	foedus::storage::masstree::normalize_be_bytes_full (const void *be_bytes)
	Convert a big-endian byte array of at least 8-bytes-length to KeySlice. More...

KeySlice	foedus::storage::masstree::normalize_be_bytes_fragment (const void *be_bytes, uint32_t length)
	Convert a big-endian byte array of given length to KeySlice. More...

KeySlice	foedus::storage::masstree::slice_key (const void *be_bytes, KeyLength slice_length)
	Extract a part of a big-endian byte array of given length as KeySlice. More...

KeySlice	foedus::storage::masstree::slice_layer (const void *be_bytes, KeyLength key_length, Layer current_layer)
	Extract a part of a big-endian byte array of given length as KeySlice. More...

uint16_t	foedus::storage::masstree::count_common_slices (const void left, const void right, uint16_t max_slices)
	Returns the number of 8-byte slices that the two strings share as prefix. More...

bool	foedus::storage::masstree::is_key_aligned_and_zero_padded (const char *key, KeyLength key_length)
	Returns if the given key is 8-bytes aligned and also zero-padded to 8-bytes for easier slicing (which most of our code does). More...

Variables
const Layer	foedus::storage::masstree::kMaxLayer = 63U
	Maximum value for Layer. More...

const InLayerLevel	foedus::storage::masstree::kMaxSaneInLayerLevel = 15U
	If InLayerLevel exceeds this value, there must be something wrong. More...

const KeyLength	foedus::storage::masstree::kMaxKeyLength = 1024U
	Max length of a key. More...

const KeyLength	foedus::storage::masstree::kInitiallyNextLayer = 0xFFFFU
	A special key length value that denotes the record in a border page was initially a next-layer pointer, thus the record has no suffix region. More...

const PayloadLength	foedus::storage::masstree::kMaxPayloadLength = 1024U
	Max length of a payload. More...

const uint32_t	foedus::storage::masstree::kCommonPageHeaderSize = 80U
	Size of the base page class (MasstreePage), which is the common header for intermediate and border pages placed at the beginning. More...

const uint32_t	foedus::storage::masstree::kBorderPageAdditionalHeaderSize = 8U
	Misc header attributes specific to MasstreeBorderPage placed after the common header. More...

const uint32_t	foedus::storage::masstree::kBorderPageSlotSize = 32U
	Byte size of one slot in MasstreeBorderPage excluding slice information. More...

const SlotIndex	foedus::storage::masstree::kBorderPageMaxSlots
	Maximum number of slots in one MasstreeBorderPage. More...

const uint32_t	foedus::storage::masstree::kBorderPageDataPartSize
	Byte size of the record data part (data_) in MasstreeBorderPage. More...

const uint16_t	foedus::storage::masstree::kMaxIntermediateSeparators = 9U
	Max number of separators stored in the first level of intermediate pages. More...

const uint16_t	foedus::storage::masstree::kMaxIntermediateMiniSeparators = 15U
	Max number of separators stored in the second level of intermediate pages. More...

const uint32_t	foedus::storage::masstree::kMaxIntermediatePointers = (kMaxIntermediateSeparators + 1U) * (kMaxIntermediateMiniSeparators + 1U)
	Max number of pointers (if completely filled) stored in an intermediate pages. More...

Class Documentation

struct foedus::storage::masstree::MasstreeComposeContext::FenceAndPointer

Definition at line 253 of file masstree_composer_impl.hpp.

Class Members
KeySlice	low_fence_
SnapshotPagePointer	pointer_

struct foedus::storage::masstree::MasstreeCommonLogType::RecordAddresses

Definition at line 211 of file masstree_log_types.hpp.

Class Members
char *	record_payload_
PayloadLength *	record_payload_count_

struct foedus::storage::masstree::MasstreeBorderPage::SlotLengthPart

A piece of Slot object that must be read/written in one-shot, meaning no one reads half-written values whether it reads old values or new values.

Today's CPUs guarantee that for 64-bit integers, so we use union to switch uint64_t/struct. Of course this object must be aligned to make this work.

When these values change

Unlike hash storage, this is mutable, or it changes when the record is moved to expand, but it changes only in a restricted way.

Concurrent threads are safe to read the record before the change. Pre-commit will detect the record has been moved by checking XID.
when a record is expanded/moved, the old data at old offset_ are untouched. This means that we can retrieve the original full key for a moved record.
physical_record_length_ stays the same or increases.
A record can move at most once.
A record that is originally a next-layer record never moves.
When the slot uses the right-most record region in the page (next_offset_==offset_+physical_record_length_), we might increase physical_record_length_ without moving offset_ because record-part grows forward.

Definition at line 466 of file masstree_page_impl.hpp.

Class Members
DataOffset	offset_	Byte offset in data_ where this record starts. Invariant offset_ % 8 == 0 offset_ < kBorderPageDataPartSize
PayloadLength	payload_length_	Byte length of the payload. Padding is not included. This is mutable. Only changed with update. If the updated payload is too large for physical_record_length_, we move the record, leaving the deleted and moved flags in this old record.
DataOffset	physical_record_length_	Byte count this record occupies. Invariant physical_record_length_ % 8 == 0 physical_record_length_ >= align8(suffix_length) + align8(payload_length_)
uint16_t	unused_	unused so far

union foedus::storage::masstree::MasstreeBorderPage::SlotLengthUnion

See also: SlotLengthPart

Definition at line 490 of file masstree_page_impl.hpp.

Collaboration diagram for foedus::storage::masstree::MasstreeBorderPage::SlotLengthUnion:

[legend]

Class Members
SlotLengthPart	components
uint64_t	word

struct foedus::storage::masstree::SplitBorder::SplitStrategy

Definition at line 103 of file masstree_split_impl.hpp.

Class Members
KeySlice	largest_slice_
KeySlice	mid_slice_	This will be the new foster fence. Ideally, # of records below and above this are same.
bool	no_record_split_	whether this page seems to have had sequential insertions, in which case we do "no-record split" as optimization. This also requires the trigerring insertion key is equal or larger than the largest slice in this page.
SlotIndex	original_key_count_
KeySlice	smallest_slice_

struct foedus::storage::masstree::SplitIntermediate::SplitStrategy

Constructed by hierarchically reading all separators and pointers in old page.

Definition at line 206 of file masstree_split_impl.hpp.

Collaboration diagram for foedus::storage::masstree::SplitIntermediate::SplitStrategy:

[legend]

Class Members
	Constants

Class Members
bool	compact_adopt_	When this says true, we create a dummy foster with empty range on right side, and just re-structures target page onto left foster twin. In other words, this is compaction/restructure that is done in another page in RCU fashion.
char	dummy_[3]
uint16_t	mid_index_
KeySlice	mid_separator_
DualPagePointer	pointers_[kMaxSeparators]
KeySlice	separators_[kMaxSeparators]	pointers_[n] points to page that is responsible for keys separators_[n - 1] <= key < separators_[n]. separators_[-1] is infimum.
uint16_t	total_separator_count_

struct foedus::storage::masstree::MasstreeStorage::PeekBoundariesArguments

Arguments for peek_volatile_page_boundaries()

Definition at line 561 of file masstree_storage.hpp.

Class Members
KeySlice *	found_boundaries_	[OUT] fence-slices of border pages between from-to
uint32_t	found_boundary_capacity_	[IN] capacity of found_boundaries_.
uint32_t *	found_boundary_count_	[OUT] number of found_boundaries_ entries returned
KeySlice	from_	[IN] lists up page boundaries from this slice
uint32_t	prefix_slice_count_	[IN] size of prefix_slices_. 0 means we are interested in the first layer.
const KeySlice *	prefix_slices_	[IN] slices of higher layers that lead to the B-trie layer of interest. null if 1st layer
KeySlice	to_	[IN] lists up page boundaries up to this slice

Typedef Documentation

typedef uint16_t foedus::storage::masstree::DataOffset

Byte-offset in a page.

Definition at line 104 of file masstree_id.hpp.

typedef uint8_t foedus::storage::masstree::InLayerLevel

Represents the depth of a B-tree node in a B-trie layer.

0 is the root.

Definition at line 54 of file masstree_id.hpp.

typedef uint16_t foedus::storage::masstree::KeyLength

Represents a byte-length of a key in this package.

Definition at line 69 of file masstree_id.hpp.

typedef uint64_t foedus::storage::masstree::KeySlice

Each key slice is an 8-byte integer.

Masstree pages store and compare these key slices.

Each key-slice is in a native integer type that preserves the original order if it's made by normalizing primitive key types (eg signed ints). Note that this is a native integer type. This might NOT be big-endian (eg x86). For signed integer types, we normalize them in an order-preserving manner, namely cast to uint64_t and subtract 2^63. For unsigned integer types, no conversion needed.

Attention: Be very careful if you give value of this type directly. In most cases, this type should be only internally manipulated. The only exception is the "primitive-optimized" APIs that receive this type. In that case, make sure you use normalize_primitive(). If the primitive is a signed type, the sign bit will bite (pun intended) you otherwise.

Definition at line 126 of file masstree_id.hpp.

typedef uint8_t foedus::storage::masstree::Layer

Represents the depth of a B-trie layer.

0 is the first layer.

Definition at line 42 of file masstree_id.hpp.

typedef uint16_t foedus::storage::masstree::PayloadLength

Represents a byte-length of a payload in this package.

Definition at line 92 of file masstree_id.hpp.

typedef uint16_t foedus::storage::masstree::SlotIndex

Index of a record in a (border) page.

Definition at line 110 of file masstree_id.hpp.

Function Documentation

uint16_t foedus::storage::masstree::count_common_slices	(	const void *	left,
		const void *	right,
		uint16_t	max_slices
	)

inline

Returns the number of 8-byte slices that the two strings share as prefix.

Parameters

[in]	left	aligned string pointer. can be either big-endian or little endian.
[in]	right	aligned string pointer must be in same endian as left.
[in]	max_slices	min(left_len / 8, right_len / 8)

Returns: number of shared slices

Definition at line 298 of file masstree_id.hpp.

References ASSUME_ALIGNED.

                                                                                               {
   const uint64_t* left_casted = reinterpret_cast<const uint64_t*>(ASSUME_ALIGNED(left, 8));
   const uint64_t* right_casted = reinterpret_cast<const uint64_t*>(ASSUME_ALIGNED(right, 8));
   for (uint16_t slices = 0; slices < max_slices; ++slices) {
     if (left_casted[slices] != right_casted[slices]) {
       return slices;
     }
   }
   return max_slices;
 }

template<typename T >

T foedus::storage::masstree::denormalize_primitive ( KeySlice value )

inline

Opposite of normalize_primitive().

See also: normalize_primitive()

Definition at line 208 of file masstree_id.hpp.

                                                {
   if (std::numeric_limits<T>::is_signed) {
     return static_cast<T>(value - (1ULL << 63));
   } else {
     return static_cast<T>(value);
   }
 }

bool foedus::storage::masstree::is_key_aligned_and_zero_padded	(	const char *	key,
		KeyLength	key_length
	)

inline

Returns if the given key is 8-bytes aligned and also zero-padded to 8-bytes for easier slicing (which most of our code does).

This method is usually used for assertions.

Definition at line 314 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeCommonLogType::compare_logs(), foedus::storage::masstree::MasstreeComposeContext::PathLevel::contains_key(), foedus::storage::masstree::fill_payload_padded(), and foedus::storage::masstree::MasstreePartitionerData::find_partition().

                                                                                   {
   uintptr_t int_address = reinterpret_cast<uintptr_t>(key);
   if (int_address % 8 != 0) {
     return false;
   }
   if (key_length % 8 != 0) {
     uint16_t paddings = 8 - (key_length % 8);
     for (uint16_t i = 0; i < paddings; ++i) {
       if (key[key_length + i] != 0) {
         return false;
       }
     }
   }
   return true;
 }

Here is the caller graph for this function:

KeySlice foedus::storage::masstree::normalize_be_bytes_fragment	(	const void *	be_bytes,
		uint32_t	length
	)

inline

Convert a big-endian byte array of given length to KeySlice.

Parameters

[in]	be_bytes	a big-endian byte array.
[in]	length	key length.

Returns: normalized value that preserves the value-order

Definition at line 247 of file masstree_id.hpp.

References foedus::storage::masstree::normalize_be_bytes_full().

Referenced by foedus::storage::masstree::slice_key(), and foedus::storage::masstree::slice_layer().

                                                                                    {
   if (length >= 8) {
     return normalize_be_bytes_full(be_bytes);
   }
   uint64_t tmp = 0;
   std::memcpy(&tmp, be_bytes, length);
   return assorted::read_bigendian<uint64_t>(&tmp);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

KeySlice foedus::storage::masstree::normalize_be_bytes_full ( const void * be_bytes )

inline

Convert a big-endian byte array of at least 8-bytes-length to KeySlice.

Parameters

[in] be_bytes a big-endian byte array.

Returns: normalized value that preserves the value-order

Definition at line 233 of file masstree_id.hpp.

                                                               {
   // otherwise we have to copy to an aligned local variable first
   uint64_t tmp;  // 8-byte stack variable is guaranteed to be 8-byte aligned. at least in GCC.
   std::memcpy(&tmp, be_bytes, 8);
   return assorted::read_bigendian<uint64_t>(&tmp);
 }

Here is the caller graph for this function:

KeySlice foedus::storage::masstree::normalize_be_bytes_full_aligned ( const void * be_bytes )

inline

Convert an aligned big-endian byte array of at least 8-bytes-length to KeySlice.

Parameters

[in] be_bytes a big-endian byte array. MUST BE ALIGNED.

Returns: normalized value that preserves the value-order

Definition at line 222 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeCommonLogType::compare_logs(), foedus::storage::masstree::MasstreeComposeContext::PathLevel::contains_key(), foedus::storage::masstree::MasstreePartitionerData::find_partition(), foedus::storage::masstree::MasstreeCommonLogType::get_first_slice(), and foedus::storage::masstree::prepare_sort_entries().

                                                                       {
   // then efficient.
   return assorted::read_bigendian<uint64_t>(be_bytes);
 }

Here is the caller graph for this function:

template<typename T >

KeySlice foedus::storage::masstree::normalize_primitive ( T value )

inline

Order-preserving normalization for primitive key types.

Parameters

[in] value the value to normalize

Returns: normalized value that preserves the value-order

Template Parameters

T primitive type of the key. All standard integers (both signed and unsigned) are allowed (non-standard [u]int128_t are not supported). Floats are currently not allowed because we have to normalize it to uint64_t without changing value orders, which is doable but challenging (let's revisit this later).

See also: denormalize_primitive()

Definition at line 194 of file masstree_id.hpp.

                                              {
   if (std::numeric_limits<T>::is_signed) {
     return static_cast<uint64_t>(value) - (1ULL << 63);
   } else {
     return static_cast<uint64_t>(value);
   }
 }

KeySlice foedus::storage::masstree::slice_key	(	const void *	be_bytes,
		KeyLength	slice_length
	)

inline

Extract a part of a big-endian byte array of given length as KeySlice.

Parameters

[in]	be_bytes	a big-endian byte array.
[in]	slice_length	key length for this slice.

Returns: normalized value that preserves the value-order

Definition at line 263 of file masstree_id.hpp.

References foedus::storage::masstree::normalize_be_bytes_fragment(), and foedus::storage::masstree::normalize_be_bytes_full().

Referenced by foedus::storage::masstree::copy_input_key(), foedus::storage::masstree::MasstreeBorderPage::initialize_layer_root(), and foedus::storage::masstree::MasstreeBorderPage::track_moved_record_next_layer().

                                                                         {
   if (slice_length >= sizeof(KeySlice)) {
     return normalize_be_bytes_full(be_bytes);
   } else {
     return normalize_be_bytes_fragment(be_bytes, slice_length);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

KeySlice foedus::storage::masstree::slice_layer	(	const void *	be_bytes,
		KeyLength	key_length,
		Layer	current_layer
	)

inline

Extract a part of a big-endian byte array of given length as KeySlice.

Parameters

[in]	be_bytes	a big-endian byte array.
[in]	key_length	total key length.
[in]	current_layer	extract a slice for this layer.

Returns: normalized value that preserves the value-order

Definition at line 279 of file masstree_id.hpp.

References foedus::storage::masstree::normalize_be_bytes_fragment(), and foedus::storage::masstree::normalize_be_bytes_full().

Referenced by foedus::storage::masstree::MasstreeBorderPage::compare_key(), foedus::storage::masstree::MasstreeStoragePimpl::locate_record(), foedus::storage::masstree::MasstreeBorderPage::ltgt_key(), foedus::storage::masstree::MasstreeStoragePimpl::reserve_record(), foedus::storage::masstree::MasstreeBorderPage::will_conflict(), and foedus::storage::masstree::MasstreeBorderPage::will_contain_next_layer().

                                                                                              {
   const KeyLength skipped = current_layer * sizeof(KeySlice);
   const KeyLength remainder_length = key_length - skipped;
   const char* casted = reinterpret_cast<const char*>(be_bytes);
   if (remainder_length >= sizeof(KeySlice)) {
     return normalize_be_bytes_full(casted + skipped);
   } else {
     return normalize_be_bytes_fragment(casted + skipped, remainder_length);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

const uint32_t foedus::storage::masstree::kBorderPageAdditionalHeaderSize = 8U

Misc header attributes specific to MasstreeBorderPage placed after the common header.

Definition at line 150 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeBorderPage::prefetch_additional_if_needed().

const uint32_t foedus::storage::masstree::kBorderPageDataPartSize

Initial value:

= kPageSize
    - kCommonPageHeaderSize
    - kBorderPageAdditionalHeaderSize
    - kBorderPageMaxSlots * sizeof(KeySlice)

Byte size of the record data part (data_) in MasstreeBorderPage.

Definition at line 171 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeStorage::estimate_records_per_page().

const SlotIndex foedus::storage::masstree::kBorderPageMaxSlots

Initial value:

= (kPageSize - kCommonPageHeaderSize - kBorderPageAdditionalHeaderSize)

/ (kBorderPageSlotSize + sizeof(KeySlice))

foedus::storage::masstree::kCommonPageHeaderSize

const uint32_t kCommonPageHeaderSize

Size of the base page class (MasstreePage), which is the common header for intermediate and border pa...

Definition: masstree_id.hpp:144

foedus::storage::masstree::kBorderPageSlotSize

const uint32_t kBorderPageSlotSize

Byte size of one slot in MasstreeBorderPage excluding slice information.

Definition: masstree_id.hpp:156

foedus::storage::masstree::KeySlice

uint64_t KeySlice

Each key slice is an 8-byte integer.

Definition: masstree_id.hpp:126

foedus::storage::masstree::kBorderPageAdditionalHeaderSize

const uint32_t kBorderPageAdditionalHeaderSize

Misc header attributes specific to MasstreeBorderPage placed after the common header.

Definition: masstree_id.hpp:150

foedus::storage::kPageSize

const uint16_t kPageSize

A constant defining the page size (in bytes) of both snapshot pages and volatile pages.

Definition: storage_id.hpp:45

Maximum number of slots in one MasstreeBorderPage.

Definition at line 163 of file masstree_id.hpp.

const uint32_t foedus::storage::masstree::kBorderPageSlotSize = 32U

Byte size of one slot in MasstreeBorderPage excluding slice information.

Definition at line 156 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeStorage::estimate_records_per_page().

const uint32_t foedus::storage::masstree::kCommonPageHeaderSize = 80U

Size of the base page class (MasstreePage), which is the common header for intermediate and border pages placed at the beginning.

Definition at line 144 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::MasstreeBorderPage::prefetch_additional_if_needed().

const KeyLength foedus::storage::masstree::kInitiallyNextLayer = 0xFFFFU

A special key length value that denotes the record in a border page was initially a next-layer pointer, thus the record has no suffix region.

This value is stored in the remainder_length member iff the record was originally created as a next-layer. A record that later turned to be next-layer doesn't use this value. Also, a record with this length is never expanded.

Remainder vs Remaining Key

Definition at line 86 of file masstree_id.hpp.

const uint16_t foedus::storage::masstree::kMaxIntermediateMiniSeparators = 15U

Max number of separators stored in the second level of intermediate pages.

Todo:: Should be calculated from kPageSize. Super low-priority.

Definition at line 244 of file masstree_page_impl.hpp.

Referenced by foedus::storage::masstree::Adopt::adopt_case_b(), foedus::storage::masstree::MasstreeIntermediatePage::is_full_snapshot(), foedus::storage::masstree::SplitIntermediate::migrate_pointers(), foedus::storage::masstree::MasstreeIntermediatePage::release_pages_recursive(), foedus::storage::masstree::MasstreeIntermediatePage::release_pages_recursive_parallel(), foedus::storage::masstree::Adopt::run(), and foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_intermediate().

const uint32_t foedus::storage::masstree::kMaxIntermediatePointers = (kMaxIntermediateSeparators + 1U) * (kMaxIntermediateMiniSeparators + 1U)

Max number of pointers (if completely filled) stored in an intermediate pages.

Definition at line 251 of file masstree_page_impl.hpp.

Referenced by foedus::storage::masstree::SplitIntermediate::decide_strategy(), and foedus::storage::masstree::MasstreeComposer::drop_volatiles().

const uint16_t foedus::storage::masstree::kMaxIntermediateSeparators = 9U

Max number of separators stored in the first level of intermediate pages.

Todo:: Should be calculated from kPageSize. Super low-priority.

Definition at line 237 of file masstree_page_impl.hpp.

Referenced by foedus::storage::masstree::Adopt::adopt_case_b(), foedus::storage::masstree::MasstreeIntermediatePage::initialize_snapshot_page(), foedus::storage::masstree::MasstreeIntermediatePage::initialize_volatile_page(), foedus::storage::masstree::SplitIntermediate::migrate_pointers(), foedus::storage::masstree::MasstreeIntermediatePage::release_pages_recursive(), foedus::storage::masstree::MasstreeIntermediatePage::release_pages_recursive_parallel(), and foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_intermediate().

const KeyLength foedus::storage::masstree::kMaxKeyLength = 1024U

Max length of a key.

Definition at line 75 of file masstree_id.hpp.

const Layer foedus::storage::masstree::kMaxLayer = 63U

Maximum value for Layer.

Definition at line 48 of file masstree_id.hpp.

const PayloadLength foedus::storage::masstree::kMaxPayloadLength = 1024U

Max length of a payload.

Definition at line 98 of file masstree_id.hpp.

Referenced by foedus::storage::masstree::adjust_payload_hint(), foedus::storage::masstree::MasstreeBorderPage::can_accomodate(), foedus::storage::masstree::MasstreeStorage::insert_record(), foedus::storage::masstree::MasstreeStorage::insert_record_normalized(), foedus::storage::masstree::MasstreeStorage::upsert_record(), and foedus::storage::masstree::MasstreeStorage::upsert_record_normalized().

const InLayerLevel foedus::storage::masstree::kMaxSaneInLayerLevel = 15U

If InLayerLevel exceeds this value, there must be something wrong.

In theory, there is no limit on B-tree levels. But, in reality we can't store 16-levels of B-tree even with the biggest machine in our universe.

Definition at line 63 of file masstree_id.hpp.

Detailed Description

Foster-Twin

Remainder vs Remaining Key

References

Files

Classes

Typedefs

Functions

Variables

Class Documentation

Typedef Documentation

Function Documentation

Variable Documentation