libfoedus-core
FOEDUS Core Library
|
Array Storage, a dense and regular array. More...
Array Storage, a dense and regular array.
Our array-storage is an extremely simple data structure at the cost of limited applicability (fix-sized, regular, dense arrays). The page layout has little per-page information that is dynamic, meaning that most data never changes after the array storage is created. Further, as everything is pre-allocated, no phantoms, no insertion/splits, nor anything complex. Thus, little synchronization hassles.
Array storage allows very few data operations.
In other words, the following operations are NOT supported.
If these limitations do not cause an issue, array storage is a best choice as it's extremely efficient and scalable thanks to the simplicity.
Despite the name of this storage type, we do have a page hierarchy, which is required to handle switches between volatile/snapshot pages. Hence, a more precise description of this storage type is a fix-sized pre-allocated tree that has only integer-keys from 0 to array_size-1.
All data (payload) are stored in leaf pages and interior pages contain only pointers to its children. There is only one root page per array, which may or may not be a leaf page. Just like B-trees in many sense.
Fix-Sized HEADER (kHeaderSize bytes) | DATA |
---|
InteriorRecord | InteriorRecord | ... |
---|
Record | Padding | Record | Padding | ... |
---|
We do a bit special concurrency control for this storage type. Because everything is pre-allocated and no split/physical-delete/merge whatsoever, we can do the ModCount concurrency control per Record, not per page. We store ModCount for each record, instead stores no ModCount in page header. Thus, individual transactions that update records in same page have no contention except they update the exact same record. We even don't track node-set; only record-set is checked at commit.
This simplifies and increases concurrency for most data accesses, but we have to be careful when the page eviction thread drops the volatile page. We need to know the largest Epoch of records in the page at the point, but concurrent transactions might be modifying records at the same time. Thus, we do two-path optimistic concurrency control similar to our commit protocol for Masstree Storage.
Classes | |
struct | ArrayCommonUpdateLogType |
A base class for ArrayOverwriteLogType/ArrayIncrementLogType. More... | |
class | ArrayComposeContext |
ArrayComposer's compose() implementation separated from the class itself. More... | |
class | ArrayComposer |
Composer for an array storage. More... | |
struct | ArrayCreateLogType |
Log type of CREATE ARRAY STORAGE operation. More... | |
struct | ArrayIncrementLogType |
Log type of array-storage's increment operation. More... | |
struct | ArrayMetadata |
Metadata of an array storage. More... | |
struct | ArrayMetadataSerializer |
struct | ArrayOverwriteLogType |
Log type of array-storage's overwrite operation. More... | |
class | ArrayPage |
Represents one data page in Array Storage. More... | |
class | ArrayPartitioner |
Partitioner for an array storage. More... | |
struct | ArrayPartitionerData |
struct | ArrayRange |
Represents an offset range in an array storage. More... | |
struct | ArrayRootInfoPage |
Output of one compose() call, which are then combined in construct_root(). More... | |
class | ArrayStorage |
Represents a key-value store based on a dense and regular array. More... | |
struct | ArrayStorageControlBlock |
Shared data of this storage type. More... | |
class | ArrayStoragePimpl |
Pimpl object of ArrayStorage. More... | |
union | LookupRoute |
Compactly represents the route to reach the given offset. More... | |
class | LookupRouteFinder |
Packages logic and required properties to calculate LookupRoute in array storage from offset. More... | |
struct | SortEntry |
Used in sort_batch(). More... | |
Typedefs | |
typedef uint64_t | ArrayOffset |
The only key type in array storage. More... | |
Enumerations | |
enum | ValueType { kUnknown = 0, kI8 = 1, kI16, kI32, kU8, kU16, kU32, kFloat, kBool, kI64, kU64, kDouble } |
Used in ArrayIncrementLogType. More... | |
Functions | |
template<typename T > | |
ValueType | to_value_type () |
template<> | |
ValueType | to_value_type< bool > () |
template<> | |
ValueType | to_value_type< int8_t > () |
template<> | |
ValueType | to_value_type< int16_t > () |
template<> | |
ValueType | to_value_type< int32_t > () |
template<> | |
ValueType | to_value_type< int64_t > () |
template<> | |
ValueType | to_value_type< uint8_t > () |
template<> | |
ValueType | to_value_type< uint16_t > () |
template<> | |
ValueType | to_value_type< uint32_t > () |
template<> | |
ValueType | to_value_type< uint64_t > () |
template<> | |
ValueType | to_value_type< float > () |
template<> | |
ValueType | to_value_type< double > () |
template<typename T > | |
void | increment (T *payload, const T *addendum) |
template<typename T > | |
void | add_to (void *destination, const void *added) |
void | array_volatile_page_init (const VolatilePageInitArguments &args) |
volatile page initialize callback for ArrayPage. More... | |
uint16_t | to_records_in_leaf (uint16_t payload_size) |
std::ostream & | operator<< (std::ostream &o, const ArrayCreateLogType &v) |
std::ostream & | operator<< (std::ostream &o, const ArrayOverwriteLogType &v) |
template<typename T > | |
T | as (const void *address) |
std::ostream & | operator<< (std::ostream &o, const ArrayIncrementLogType &v) |
std::ostream & | operator<< (std::ostream &o, const ArrayMetadata &v) |
void | prepare_sort_entries (const Partitioner::SortBatchArguments &args, SortEntry *entries) |
subroutine of sort_batch More... | |
uint32_t | compact_logs (const Partitioner::SortBatchArguments &args, SortEntry *entries) |
subroutine of sort_batch More... | |
std::ostream & | operator<< (std::ostream &o, const ArrayPartitioner &v) |
std::ostream & | operator<< (std::ostream &o, const ArrayStorage &v) |
uint8_t | calculate_levels (const ArrayMetadata &metadata) |
Variables | |
const ArrayOffset | kMaxArrayOffset = (1ULL << 48) - 1ULL |
The maximum value allowed for ArrayOffset. More... | |
const uint16_t | kHeaderSize = 64 |
Byte size of header in each page of array storage. More... | |
const uint16_t | kDataSize = foedus::storage::kPageSize - kHeaderSize |
Byte size of data region in each page of array storage. More... | |
const uint16_t | kInteriorSize = 16 |
Byte size of an entry in interior page of array storage. More... | |
const uint16_t | kInteriorFanout = (foedus::storage::kPageSize - kHeaderSize) / kInteriorSize |
Max number of entries in an interior page of array storage. More... | |
const uint8_t | kMaxLevels = 8 |
Code in array storage assumes this number as the maximum number of levels. More... | |
struct foedus::storage::array::ArrayRootInfoPage |
Output of one compose() call, which are then combined in construct_root().
If the root page is leaf page (single-page array), this contains just one pointer to the root. If not, this contains pointers to direct children of root.
Definition at line 92 of file array_composer_impl.hpp.
Class Members | ||
---|---|---|
char | filler_[ kPageSize -sizeof(PageHeader) -kInteriorFanout *sizeof(SnapshotPagePointer)] | |
PageHeader | header_ | |
SnapshotPagePointer | pointers_[kInteriorFanout] |
Pointers to direct children of root. 0 if not set in this compose() |
Used in ArrayIncrementLogType.
Enumerator | |
---|---|
kUnknown | |
kI8 | |
kI16 | |
kI32 | |
kU8 | |
kU16 | |
kU32 | |
kFloat | |
kBool | |
kI64 | |
kU64 | |
kDouble |
Definition at line 147 of file array_log_types.hpp.
|
inline |
Definition at line 370 of file array_log_types.hpp.
|
inline |
Definition at line 70 of file array_log_types.cpp.
uint8_t foedus::storage::array::calculate_levels | ( | const ArrayMetadata & | metadata | ) |
Definition at line 194 of file array_storage_pimpl.cpp.
References foedus::assorted::align8(), foedus::storage::array::ArrayMetadata::array_size_, foedus::assorted::int_div_ceil(), kDataSize, kInteriorFanout, foedus::storage::kRecordOverhead, and foedus::storage::array::ArrayMetadata::payload_size_.
Referenced by foedus::storage::array::ArrayStoragePimpl::load(), and foedus::storage::array::ArrayStoragePimpl::load_empty().
uint32_t foedus::storage::array::compact_logs | ( | const Partitioner::SortBatchArguments & | args, |
SortEntry * | entries | ||
) |
subroutine of sort_batch
Definition at line 249 of file array_partitioner_impl.cpp.
References ASSERT_ND, foedus::storage::array::SortEntry::get_offset(), foedus::storage::array::SortEntry::get_position(), foedus::log::LogHeader::get_type(), foedus::log::BaseLogType::header_, foedus::log::kLogCodeArrayIncrement, foedus::log::kLogCodeArrayOverwrite, foedus::storage::Partitioner::SortBatchArguments::log_buffer_, foedus::log::LogHeader::log_type_code_, foedus::storage::Partitioner::SortBatchArguments::logs_count_, foedus::storage::array::ArrayIncrementLogType::merge(), foedus::storage::Partitioner::SortBatchArguments::output_buffer_, foedus::storage::array::ArrayOverwriteLogType::payload_count_, foedus::storage::array::ArrayOverwriteLogType::payload_offset_, foedus::storage::array::ArrayIncrementLogType::payload_offset_, foedus::snapshot::LogBuffer::resolve(), UNLIKELY, and foedus::storage::array::ArrayIncrementLogType::value_type_.
Referenced by foedus::storage::array::ArrayPartitioner::sort_batch().
|
inline |
Definition at line 299 of file array_log_types.hpp.
std::ostream& foedus::storage::array::operator<< | ( | std::ostream & | o, |
const ArrayMetadata & | v | ||
) |
Definition at line 33 of file array_metadata.cpp.
std::ostream& foedus::storage::array::operator<< | ( | std::ostream & | o, |
const ArrayCreateLogType & | v | ||
) |
Definition at line 48 of file array_log_types.cpp.
References foedus::storage::array::ArrayCreateLogType::metadata_.
std::ostream& foedus::storage::array::operator<< | ( | std::ostream & | o, |
const ArrayOverwriteLogType & | v | ||
) |
Definition at line 53 of file array_log_types.cpp.
References foedus::storage::array::ArrayCommonUpdateLogType::offset_, foedus::storage::array::ArrayOverwriteLogType::payload_, foedus::storage::array::ArrayOverwriteLogType::payload_count_, and foedus::storage::array::ArrayOverwriteLogType::payload_offset_.
std::ostream& foedus::storage::array::operator<< | ( | std::ostream & | o, |
const ArrayStorage & | v | ||
) |
Definition at line 60 of file array_storage.cpp.
References foedus::storage::array::ArrayStorage::get_array_size(), foedus::storage::Storage< CONTROL_BLOCK >::get_id(), foedus::storage::Storage< CONTROL_BLOCK >::get_name(), and foedus::storage::array::ArrayStorage::get_payload_size().
std::ostream& foedus::storage::array::operator<< | ( | std::ostream & | o, |
const ArrayIncrementLogType & | v | ||
) |
Definition at line 75 of file array_log_types.cpp.
References foedus::storage::array::ArrayIncrementLogType::addendum_, ASSERT_ND, foedus::storage::array::ArrayIncrementLogType::get_value_type(), kBool, kDouble, kFloat, kI16, kI32, kI64, kI8, kU16, kU32, kU64, kU8, foedus::storage::array::ArrayCommonUpdateLogType::offset_, and foedus::storage::array::ArrayIncrementLogType::payload_offset_.
std::ostream& foedus::storage::array::operator<< | ( | std::ostream & | o, |
const ArrayPartitioner & | v | ||
) |
Definition at line 347 of file array_partitioner_impl.cpp.
References foedus::storage::array::ArrayPartitionerData::array_size_, foedus::storage::array::ArrayPartitionerData::bucket_owners_, foedus::storage::array::ArrayPartitionerData::bucket_size_, and kInteriorFanout.
void foedus::storage::array::prepare_sort_entries | ( | const Partitioner::SortBatchArguments & | args, |
SortEntry * | entries | ||
) |
subroutine of sort_batch
Definition at line 228 of file array_partitioner_impl.cpp.
References ASSERT_ND, foedus::storage::Partitioner::SortBatchArguments::base_epoch_, foedus::xct::XctId::get_epoch(), foedus::xct::XctId::get_ordinal(), foedus::log::BaseLogType::header_, foedus::log::kLogCodeArrayIncrement, foedus::log::kLogCodeArrayOverwrite, foedus::storage::Partitioner::SortBatchArguments::log_buffer_, foedus::storage::Partitioner::SortBatchArguments::log_positions_, foedus::log::LogHeader::log_type_code_, foedus::storage::Partitioner::SortBatchArguments::logs_count_, foedus::storage::array::ArrayCommonUpdateLogType::offset_, foedus::snapshot::LogBuffer::resolve(), foedus::storage::array::SortEntry::set(), foedus::Epoch::subtract(), and foedus::log::LogHeader::xct_id_.
Referenced by foedus::storage::array::ArrayPartitioner::sort_batch().
|
inline |
Definition at line 71 of file array_route.hpp.
References foedus::assorted::align8(), kDataSize, and foedus::storage::kRecordOverhead.
Referenced by foedus::storage::array::LookupRoute::calculate_page_range().
ValueType foedus::storage::array::to_value_type | ( | ) |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |