...
Code Block | ||||
---|---|---|---|---|
| ||||
public interface SortedInternalStore { /** PutExclude rowlower to indexbound. */ byte voidGREATER put(Row r)= 0; /** RemoveInclude rowlower from indexbound. */ void remove(Row r) byte GREATER_OR_EQUAL = 1; /** Exclude upper bound. */ byte LESS = *0; Return rows between lower/** andInclude upper boundsbound. */ byte LESS_OR_EQUAL = 1 << 1; /** Fill results rows by* fieldsUpdate specifiedrow at the projection set.index if need: * <ul> * @param low Lower<li>put boundoperation ofif the scan. * @param up Lower bound of the scan. * @param opts Scan bound option.{@code oldR} is {@code null},</li> * <li>remove operation if the {@code newR} is {@code null},</li> * @param proj Set<li>update of the columns IDs to fill results rows.operation otherwise.</li> * </ul> */ Cursor<Row>void scanupdate(Row lowoldR, Row up, ScanBoundOption opts, BitSet projnewR); enum ScanBoundOption {/** * Return rows /**between Includelower toand resultsupper rowsbounds. that equal all bounds. */ Fill results rows by fields specified INCLUDE_INCLUDE, at the projection set. /** Include to results rows that* are@param equallow lowerLower bound andof exclude from results rows that are equal upper bounds. */ INCLUDE_EXCLUDE, the scan. * @param up Lower bound of the scan. * @param scanBoundMask /**Scan Excludebound frommask results(specify rowshow thatto arework equalwith lower bound and includerows equals to resultsthe rowsbounds: thatinclude are equal upper bounds. */or exclude). * @param EXCLUDE_INCLUDE, /** Include from results rows that equal all bounds.proj Set of the columns IDs to fill results rows. */ Cursor<Row> scan(Row low, EXCLUDE_EXCLUDE }Row up, byte scanBoundMask, BitSet proj); } |
As we aim to have more than one option of storage we need to keep storage api separated from implementation, so we'll have one module containing api and a separate module for each specific implementation.
...
Page Memory from Ignite 2.x is a good candidate as a persistent storage implementation in 3.0 although some refactoring and modifications are needed during migration.
Ideas of refactoring are covered in depth in [1], but here is a short list of proposed changes:
...
Ignite 2.x uses WAL logging to maintain data consistency on recovery, since in 3.0 uses a Raft protocol, it is proposed to get rid of WAL logging (logical and physical records) using the following ideas.
Ignite 3.x uses log-based replication protocol (IEP-61) to ensure data consistency on different nodes in the cluster. This very same log is used as a logical WAL for local state machine recovery, in this way we can get rid of WAL logging of logical records.
The Raft log represents a key-value storage for which key is always a contiguously growing unbounded integer number. In practice, it is sufficient to limit the key by a 64-bit unsigned integer. The key range consists of two segments: committed entries (the larger part of the log) cannot be changed and are immutable, and not-yet-committed entries that can be truncated and be overwritten. The non-committed entries are rarely overwritten in practice. Additionally, the Raft log can be compacted: entries with key smaller than lower bound are thrown away as they were made durable in the state machine and are no longer needed.
The replication log storage is based on WiscKey approach of log-structured storages. Multiple Raft group logs can be stored in a single storage, however, it is not neccessary to have a single storage for all Raft groups. The storage and WAL of Raft log are combined and use immutable append-only segments containing log indices and state machine commands. Segment header may contain a dictionary to reduce the size of Raft group IDs written in the segment. Each log entry contains the log index, Raft group ID and command payload (the payload itself also contains the log entry term which is essential to Raft protocol). Schematically, the segment structure can be represented as follows:
+----------------+--------------------------------+--------------------------------+-----+
| | Entry 1 | Entry 2 | ... |
+----------------+--------------------------------+--------------------------------+-----+
| Segment header | Log index | Group ID | Payload | Log index | Group ID | Payload | ... |
+----------------+--------------------------------+--------------------------------+-----+
New entries are always written to the end of the segment, even if it is an overwrite entry with the log index which was already written to the same Raft group. The Raft log maintains an index of log entries for each Raft log group which is represented as a simple array of entry offsets from the beginning of the file. The array is complemented with the base index of the first entry in the segment. The in-memory index is flushed on disk (checkpointed) only when all entries in the segment are committed. Schematically, the index structure may be represented as follows:
+----------------+----------------------------------------------+----------------------------------------------+-----+
| | Group 1 Index | Group 2 Index | ... |
+----------------+----------------------------------------------+----------------------------------------------+-----+
| Index header | Len | Index Base | Offset 1 | Offset 2 | ... | Len | Index Base | Offset 1 | Offset 2 | ... | ... |
+----------------+----------------------------------------------+----------------------------------------------+-----+
Upon recovery, the Raft log component reads all log entries from non-checkpointed segments and repopulates the in-memory index which will be later checkpointed.
Similar to Ignite 2.x native persistence, all data structures are implemented over logical pages. This include data pages, B+Tree, reuse and free lists, etc. Each Raft log command represents a single atomic change to the state machine. When a command is applied, it changes some pages in the state machine data structures, marking them dirtly. Unlike Ignite 2.x, no physical or logical records are written to WAL when these changes are applied. As a result, after applying a set of changes, certain pages will be marked dirty and need to be checkpointed. To allow for effecient checkpointing, Ignite 3.x splits storage files into main, containing only contiguous range of pages, and auxiliary files, containing dirty pages from consequtive checkpoints. Pages in auxiliary files are not necessarily contiguous and may have gaps. The files are ordered by the order in which they were written, forming a structure similar to an LSM-tree: when a page is read from disk, it is first looked up in the most recent auxiliary file, then in the second auxiliary file, and so on, until the main storage file is reached. To allow for effecient search in auxiliary files, a small reverse index is stored with each file that maps page IDs to offsets in the file. The number of auxiliary files should be kept small enough so that the full inverse index is kept in-memory; however, if the merge process does not keep up with the load, the indexes can be always evicted from memory and read on-demand.
Schematically, the structure of the main and auxiliary checkpoint files may be represented as follows:
Main storage file:
+--------+--------+--------+-----+
| Page 1 | Page 2 | Page 3 | ... |
+--------+--------+--------+-----+
Auxiliary storage file:
+-----------------------------------------------------------+-------------------------+
| Offsets Index | Pages Data |
+-----------+--------------------+--------------------+-----+---------+---------+-----+
| Index len | Page P1 ID, Offset | Page P2 ID, Offset | ... | Page P1 | Page P2 | ... |
+-----------+--------------------+--------------------+-----+---------+---------+-----+
If a process crashes when an auxiliary file is not completely written, the file is discarded upon recovery and Raft log commands are replayed again, forming another set of dirty pages that should be checkpointed.
As the number of auxiliary files grow, they can be merged back to the main storage file in the same order they were originally written. When an auxiliary file is fully merged to the main storage file, it can be safely removed provided that there are no threads intending to read from that file. If a process crashes in the middle of the merge, the file can be safely merged again (the original pages will not be used anyway).
NOTE: It will be necessary to discuss the possibility of enabling WAL logging of physical records in case of CorruptedDataStructureException's for debugging.
RocksDB [1] is
RocksDB [2] is an LSM-based K-V database that should provide better performance on write-intensive workloads and should be easy to integrate for quick start.
...
//NA
...