|
libfoedus-core
FOEDUS Core Library
|
|
libfoedus-core
FOEDUS Core Library
|
Sequential Storage, an append/scan only data structure. More...
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.
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.
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.
Both data pages and root pages form a singly linked list of pages. The next pointer is stored in the header part.
| Fix-Sized HEADER (kHeaderSize bytes) |
|---|
| Record Data part, which grows forward |
| Unused part |
| Record Lengthes part, which grows backward |
| Fix-Sized HEADER (kRootPageHeaderSize bytes) |
|---|
| Pointers to head pages.. |
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.
|
Files | |
| file | fwd.hpp |
| Forward declarations of classes in sequential storage package. | |
| file | sequential_id.hpp |
| Definitions of IDs in this package and a few related constant values. | |
| file | sequential_log_types.hpp |
| Declares all log types used in this storage type. | |
Variables | |
| const uint16_t | foedus::storage::sequential::kMaxSlots = 1 << 15 |
| We have to represent the record count in 15 bits. More... | |
| const uint16_t | foedus::storage::sequential::kHeaderSize = 64 |
| Byte size of header in each data page of sequential storage. More... | |
| const uint16_t | foedus::storage::sequential::kDataSize = foedus::storage::kPageSize - kHeaderSize |
| Byte size of data region in each data page of sequential storage. More... | |
| const uint16_t | foedus::storage::sequential::kMaxPayload = kDataSize |
| Payload must be shorter than this length. More... | |
| const uint16_t | foedus::storage::sequential::kRootPageHeaderSize = 56 |
| Byte size of header in each root page of sequential storage. More... | |
| const uint16_t | foedus::storage::sequential::kRootPageMaxHeadPointers = (foedus::storage::kPageSize - kRootPageHeaderSize) / sizeof(HeadPagePointer) |
| Maximum number of head pointers in one root page. More... | |
| const uint16_t | foedus::storage::sequential::kRootPageDataSize = foedus::storage::kPageSize - kRootPageHeaderSize |
| Byte size of data region in each root page of sequential storage. More... | |
| const uint16_t | foedus::storage::sequential::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... | |
| struct foedus::storage::sequential::SequentialComposer::RootInfoPage |
Output of one compose() call, which are then combined in construct_root().
Each compose() returns just one pointer to a head page.
Definition at line 66 of file sequential_composer_impl.hpp.
| Class Members | ||
|---|---|---|
| char | filler_[kPageSize-sizeof(PageHeader)-sizeof(HeadPagePointer)] | |
| PageHeader | header_ | |
| HeadPagePointer | pointer_ | |
| struct foedus::storage::sequential::HeadPagePointer |
Each pointer to a snapshot head page comes with a bit more information to help reading.
Definition at line 66 of file sequential_id.hpp.
| Class Members | ||
|---|---|---|
| Epoch | from_epoch_ | Inclusive beginning of epochs in the pointed pages. |
| uint64_t | page_count_ |
In a sequential storage, all pages from the head page is guaranteed to be contiguous (that's how SequentialComposer write them out). This enables us to read a large number of sequential pages in one-go rather than reading one-page at a time. |
| SnapshotPagePointer | page_id_ | ID of the page that begins the linked list. |
| Epoch | to_epoch_ | Exclusive end of epochs in the pointed pages. |
| struct foedus::storage::sequential::SequentialStoragePimpl::PointerPage |
Definition at line 141 of file sequential_storage_pimpl.hpp.
| Class Members | ||
|---|---|---|
| PagePoolOffset | pointers_[kPointersPerPage] | |
| const uint16_t foedus::storage::sequential::kDataSize = foedus::storage::kPageSize - kHeaderSize |
Byte size of data region in each data page of sequential storage.
Definition at line 48 of file sequential_id.hpp.
Referenced by foedus::storage::sequential::SequentialPage::append_record_nosync(), foedus::storage::sequential::SequentialPage::assert_consistent(), foedus::storage::sequential::SequentialPage::can_insert_record(), foedus::storage::sequential::SequentialRecordBatch::get_owner_id_from_offset(), foedus::storage::sequential::SequentialRecordBatch::get_payload_from_offset(), foedus::storage::sequential::SequentialPage::get_payload_length(), and foedus::storage::sequential::SequentialPage::set_payload_length().
| const uint16_t foedus::storage::sequential::kHeaderSize = 64 |
Byte size of header in each data page of sequential storage.
Definition at line 43 of file sequential_id.hpp.
| const uint16_t foedus::storage::sequential::kMaxPayload = kDataSize |
Payload must be shorter than this length.
Definition at line 54 of file sequential_id.hpp.
Referenced by foedus::storage::sequential::SequentialStorage::append_record(), and foedus::storage::sequential::SequentialAppendLogType::assert_valid().
| const uint16_t foedus::storage::sequential::kMaxSlots = 1 << 15 |
We have to represent the record count in 15 bits.
Definition at line 38 of file sequential_id.hpp.
Referenced by foedus::storage::sequential::SequentialPage::append_record_nosync(), and foedus::storage::sequential::SequentialPage::can_insert_record().
| const uint16_t foedus::storage::sequential::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.
Thus we have 2^6 pointers here. This means we can waste 64*2=128 volatile pages (=512kb) per one sequential storage.. shouldn't be a big issue.
Definition at line 104 of file sequential_id.hpp.
| const uint16_t foedus::storage::sequential::kRootPageDataSize = foedus::storage::kPageSize - kRootPageHeaderSize |
Byte size of data region in each root page of sequential storage.
Definition at line 95 of file sequential_id.hpp.
| const uint16_t foedus::storage::sequential::kRootPageHeaderSize = 56 |
Byte size of header in each root page of sequential storage.
Definition at line 60 of file sequential_id.hpp.
| const uint16_t foedus::storage::sequential::kRootPageMaxHeadPointers = (foedus::storage::kPageSize - kRootPageHeaderSize) / sizeof(HeadPagePointer) |
Maximum number of head pointers in one root page.
Definition at line 89 of file sequential_id.hpp.
Referenced by foedus::storage::sequential::SequentialComposer::construct_root(), and foedus::storage::sequential::SequentialRootPage::set_pointers().
1.8.10 
