Sequential Storage, an append/scan only data structure. More...

Detailed Description

Sequential Storage, an append/scan only data structure.

This data structure is also called Heap in database literature, but probably not a good naming (Heap usually means min/max Heap, which is totally different). So, we call this data structure as Sequential Storage.

Basic Structure and Supported Operations

A sequential storage is VERY simple thus efficient. The only access pattern is append and scan, which makes everything simple. Further, the scan does not provide any guarantee in ordering (similar to Heap in DBMS). It just returns records in the order the underlying storage natively stores them.

Page Hierarchy

There are only two types of pages; root pages (foedus::storage::sequential::SequentialRootPage) and data pages (foedus::storage::sequential::SequentialPage).

Root pages are merely a set of pointers to head pages, which are the beginnings of singly-linked list of data pages.

All contents of root pages are stable. They are never dynamically changed. The volatile part of Sequential Storage is maintained as a set of singly-linked list pointed directly from the storage object, so there is no root page for it.

Data pages contain records that are contiguously placed each other. They form a singly linked list starting from a head page.

For each snapshotting, we add a new set of head pages (one for each node) and pointers to them from the root page. As root pages are singly-linked list, we re-write entire root pages for every sequential storage that had some change for each snapshotting (*). Unless there are huge number of head pages, this should be a negligible overhead.

(*) We only are placing a few head page pointers at the last root page only, but that means we have to install a new version of the last root page, which requires installing a new version of the second-to-last root page just for changing the next pointer, which requires... But, again, most sequential storage's root page should be just one or two pages. A similar overhead happens to all other storage types, too.

Page Layout

Both data pages and root pages form a singly linked list of pages. The next pointer is stored in the header part.

Layout of Data Page (foedus::storage::sequential::SequentialPage)

Fix-Sized HEADER (kHeaderSize bytes)
Record Data part, which grows forward
Unused part
Record Lengthes part, which grows backward

Layout of Root Page (foedus::storage::sequential::SequentialRootPage)

Fix-Sized HEADER (kRootPageHeaderSize bytes)
Pointers to head pages..

In-memory List

As described above, the volatile part of sequential storage is a set of singly-linked list pointed directly from the storage object. The storage object maintains such in-memory list for each epoch. When snapshotting happens, it retires those lists whose epochs are upto the snapshot's "until" epoch.

Because we have to efficiently append to the in-memory list, we maintain head and tail pointers to each list. Updating the tail page and replacing tail pointers involve a few atomic operations, but no expensive locks as done in other storages. For more details, see SequentialVolatileList.

Classes
struct	HeadPagePointer
	Each pointer to a snapshot head page comes with a bit more information to help reading. More...

struct	SequentialAppendLogType
	Log type of sequential-storage's append operation. More...

class	SequentialComposer
	Composer for an sequential storage. More...

struct	SequentialCreateLogType
	Log type of CREATE SEQUENTIAL STORAGE operation. More...

class	SequentialCursor
	A cursor interface to read tuples from a sequential storage. More...

struct	SequentialMetadata
	Metadata of a sequential storage. More...

struct	SequentialMetadataSerializer

class	SequentialPage
	Represents one data page in Sequential Storage. More...

class	SequentialPartitioner
	Partitioner for an sequential storage. More...

struct	SequentialRecordBatch
	A chunk of records returned by SequentialCursor. More...

class	SequentialRecordIterator
	Iterator for one SequentialRecordBatch, or a page. More...

class	SequentialRootPage
	Represents one stable root page in Sequential Storage. More...

class	SequentialStorage
	Represents an append/scan-only store. More...

struct	SequentialStorageControlBlock
	Shared data of this storage type. More...

class	SequentialStoragePimpl
	Lock-free list of records stored in the volatile part of sequential storage. More...

struct	SequentialTruncateLogType
	Log type of TRUNCATE SEQUENTIAL STORAGE operation. More...

struct	StreamStatus
	Unlike other composers, this one doesn't need merge sort. More...

Functions
void	_dummy_static_size_check__COUNTER__ ()

void	get_pointer_page_and_index (uint16_t thread_id, uint16_t page, uint16_t index)
	Calculate the page/index of the thread-private head/tail pointer. More...

Epoch	max_from_epoch_snapshot_epoch (Epoch from_epoch, Epoch latest_snapshot_epoch)

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

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

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

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

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

std::ostream &	operator<< (std::ostream &o, const SequentialPartitioner &)

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

Variables
const uint16_t	kMaxSlots = 1 << 15
	We have to represent the record count in 15 bits. More...

const uint16_t	kHeaderSize = 64
	Byte size of header in each data page of sequential storage. More...

const uint16_t	kDataSize = foedus::storage::kPageSize - kHeaderSize
	Byte size of data region in each data page of sequential storage. More...

const uint16_t	kMaxPayload = kDataSize
	Payload must be shorter than this length. More...

const uint16_t	kRootPageHeaderSize = 56
	Byte size of header in each root page of sequential storage. More...

const uint16_t	kRootPageMaxHeadPointers = (foedus::storage::kPageSize - kRootPageHeaderSize) / sizeof(HeadPagePointer)
	Maximum number of head pointers in one root page. More...

const uint16_t	kRootPageDataSize = foedus::storage::kPageSize - kRootPageHeaderSize
	Byte size of data region in each root page of sequential storage. More...

const uint16_t	kPointerPageCount = 1U << 6
	Each poiner page can contain 2^10 pointers (as the node is implicit, PagePoolOffset suffices) and we can have at most 2^16 cores. More...

const uint16_t	kPointersPerPage = 1U << 10

Function Documentation

void foedus::storage::sequential::_dummy_static_size_check__COUNTER__ ( )

inline

Definition at line 468 of file sequential_cursor.hpp.

void foedus::storage::sequential::get_pointer_page_and_index	(	uint16_t	thread_id,
		uint16_t *	page,
		uint16_t *	index
	)

inline

Calculate the page/index of the thread-private head/tail pointer.

Definition at line 108 of file sequential_id.hpp.

References kPointersPerPage.

Referenced by foedus::storage::sequential::SequentialStoragePimpl::get_head_pointer(), and foedus::storage::sequential::SequentialStoragePimpl::get_tail_pointer().

                                                                                             {
   *page = thread_id / kPointersPerPage;
   *index = thread_id % kPointersPerPage;
 }

Here is the caller graph for this function:

Epoch foedus::storage::sequential::max_from_epoch_snapshot_epoch	(	Epoch	from_epoch,
		Epoch	latest_snapshot_epoch
	)

Definition at line 39 of file sequential_cursor.cpp.

References foedus::Epoch::is_valid().

                                                                                    {
   if (!latest_snapshot_epoch.is_valid()) {
     return from_epoch;
   }
   if (from_epoch > latest_snapshot_epoch) {
     return from_epoch;
   } else {
     return latest_snapshot_epoch;
   }
 }

Here is the call graph for this function:

std::ostream& foedus::storage::sequential::operator<<	(	std::ostream &	o,
		const SequentialMetadata &	v
	)

Definition at line 34 of file sequential_metadata.cpp.

                                                                    {
   o << SequentialMetadataSerializer(const_cast<SequentialMetadata*>(&v));
   return o;
 }

std::ostream& foedus::storage::sequential::operator<<	(	std::ostream &	o,
		const SequentialCreateLogType &	v
	)

Definition at line 47 of file sequential_log_types.cpp.

References foedus::storage::sequential::SequentialCreateLogType::metadata_.

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

std::ostream& foedus::storage::sequential::operator<<	(	std::ostream &	o,
		const SequentialPartitioner &
	)

Definition at line 60 of file sequential_partitioner_impl.cpp.

                                                                       {
   o << "<SequentialPartitioner>"
     << "</SequentialPartitioner>";
   return o;
 }

std::ostream& foedus::storage::sequential::operator<<	(	std::ostream &	o,
		const SequentialTruncateLogType &	v
	)

Definition at line 61 of file sequential_log_types.cpp.

References foedus::log::BaseLogType::header_, foedus::storage::sequential::SequentialTruncateLogType::new_truncate_epoch_, and foedus::log::LogHeader::storage_id_.

                                                                           {
   o << "<SequentialTruncateLog>"
     << "<storage_id_>" << v.header_.storage_id_ << "</storage_id_>"
     << "<new_truncate_epoch_>" << v.new_truncate_epoch_ << "</new_truncate_epoch_>"
     << "</SequentialTruncateLog>";
   return o;
 }

std::ostream& foedus::storage::sequential::operator<<	(	std::ostream &	o,
		const SequentialAppendLogType &	v
	)

Definition at line 69 of file sequential_log_types.cpp.

References foedus::storage::sequential::SequentialAppendLogType::payload_, and foedus::storage::sequential::SequentialAppendLogType::payload_count_.

                                                                         {
   o << "<SequentialAppendLog>"
     << "<payload_count_>" << v.payload_count_ << "</payload_count_>";
   // show first few bytes
   o << "<data_>";
   for (uint16_t i = 0; i < std::min<uint16_t>(8, v.payload_count_); ++i) {
     o << i << ":" << static_cast<int>(v.payload_[i]) << " ";
   }
   o << "...</data_>";
   o << "</SequentialAppendLog>";
   return o;
 }

std::ostream& foedus::storage::sequential::operator<<	(	std::ostream &	o,
		const SequentialStorage &	v
	)

Definition at line 86 of file sequential_storage.cpp.

References foedus::storage::sequential::SequentialStoragePimpl::for_every_page(), foedus::storage::Storage< CONTROL_BLOCK >::get_id(), foedus::storage::Storage< CONTROL_BLOCK >::get_name(), foedus::storage::sequential::SequentialPage::get_record_count(), foedus::storage::sequential::SequentialStorage::get_truncate_epoch(), and foedus::kErrorCodeOk.

                                                                   {
   uint64_t page_count = 0;
   uint64_t record_count = 0;
   SequentialStoragePimpl pimpl(const_cast<SequentialStorage*>(&v));
   pimpl.for_every_page([&page_count, &record_count](SequentialPage* page){
     ++page_count;
     record_count += page->get_record_count();
     return kErrorCodeOk;
   });
   o << "<SequentialStorage>"
     << "<id>" << v.get_id() << "</id>"
     << "<name>" << v.get_name() << "</name>"
     << "<truncate_epoch>" << v.get_truncate_epoch() << "</truncate_epoch>"
     << "<page_count>" << page_count << "</page_count>"
     << "<record_count>" << record_count << "</record_count>"
     << "</SequentialStorage>";
   return o;
 }

Here is the call graph for this function:

std::ostream& foedus::storage::sequential::operator<<	(	std::ostream &	o,
		const SequentialCursor &	v
	)

Definition at line 652 of file sequential_cursor.cpp.

References foedus::storage::sequential::SequentialCursor::get_from_epoch(), foedus::storage::sequential::SequentialCursor::get_storage(), and foedus::storage::sequential::SequentialCursor::get_to_epoch().

                                                                  {
   o << "<SequentialCursor>" << std::endl;
   o << "  " << v.get_storage() << std::endl;
   o << "  <from_epoch>" << v.get_from_epoch() << "</from_epoch>" << std::endl;
   o << "  <to_epoch>" << v.get_to_epoch() << "</to_epoch>" << std::endl;
   o << "  <order_mode>" << v.order_mode_ << "</order_mode>" << std::endl;
   o << "  <node_filter>" << v.node_filter_ << "</node_filter>" << std::endl;
   o << "  <snapshot_only_>" << v.snapshot_only_ << "</snapshot_only_>" << std::endl;
   o << "  <safe_epoch_only_>" << v.safe_epoch_only_ << "</safe_epoch_only_>" << std::endl;
   o << "  <buffer_>" << v.buffer_ << "</buffer_>" << std::endl;
   o << "  <buffer_size>" << v.buffer_size_ << "</buffer_size>" << std::endl;
   o << "  <buffer_pages_>" << v.buffer_pages_ << "</buffer_pages_>" << std::endl;
   o << "  <current_node_>" << v.current_node_ << "</current_node_>" << std::endl;
   o << "  <finished_snapshots_>" << v.finished_snapshots_ << "</finished_snapshots_>" << std::endl;
   o << "  <finished_safe_volatiles_>" << v.finished_safe_volatiles_
     << "</finished_safe_volatiles_>" << std::endl;
   o << "  <finished_unsafe_volatiles_>" << v.finished_unsafe_volatiles_
     << "</finished_unsafe_volatiles_>" << std::endl;
   o << "</SequentialCursor>";
   return o;
 }

Here is the call graph for this function:

Variable Documentation

const uint16_t foedus::storage::sequential::kPointersPerPage = 1U << 10

Definition at line 105 of file sequential_id.hpp.

Referenced by get_pointer_page_and_index().

Detailed Description

Basic Structure and Supported Operations

Page Hierarchy

Page Layout

Layout of Data Page (foedus::storage::sequential::SequentialPage)

Layout of Root Page (foedus::storage::sequential::SequentialRootPage)

In-memory List

Classes

Functions

Variables

Function Documentation

Variable Documentation