Excerpt |
---|
This article covers the internal design of Durable Memory. Intended for Ignite developers. The reasoning behind the durable memory is described in the main documentation: https://apacheignite.readme.io/docs/durable-memory |
Table of Contents
...
Using this page identifier it's possible to link pages together to build dependencies between them. For instance, this is how we can link 2 pages together by keeping child page ID in the root page:
The ability to link the pages gives a way to organize pages into more complex structures such as trees. Ignite taps into this by using B+Tree for index and data pages arrangements.
If Ignite Persistence is used then after a restart Ignite will load the tree's root node (metadata page) and be able to iterate over the tree layers preloading each new missing page in memory from disk on demand. Also, the tree pages can be merged into one if less of 50% of space within page is used by payload data.
B+Tree are used for SQL indexes: tree maps field value to reference to entry value.
...
Gliffy Diagram size 600 name segmentsAndPageTable pagePin 2
Since Ignite version 2.5 Loaded Pages Id Table uses Robin Hood hashing: backward shift deletion algorithm for maintatining HashMap of FullPageId (CacheId, PageId)->(Address, PartGeneration).
...
Gliffy Diagram name segmentsAndPagesLocks pagePin 2
Since Ignite version 2.5 there are two optimizations introduced. Segment write lock
...
During first page rotated warning message is printed to logs
No Format |
---|
Page replacements started, pages will be rotated with disk, this will affect storage performance (consider increasing DataRegionConfiguration#setMaxSize). |
...
Expand | ||
---|---|---|
|
...
If this message appeared in log it means segment is full and for allocation of new page it is required to purge some other page.
...
Deletion of lastest latest added item is trivial. We can just remove Item, and Key-Value pair without any additional changes (see It3, K,V3 at picture).
...
This techique brings advantage: at inserting new K,V pair we don’t need to iterate over page to find free space. We can insert after latest item instead.
...
Example of re-insertion new K,V4 element after some other K,V2 deleted. Following picture shows Indirect Item to direct Item replacement
B+Tree structure is build mostly the same as binary tree. If requied value was not found, it is compared with some value in the tree. Greater values can be found using rigth link, less - using left.
Binary search is used to find required K. It is required to touch log N of data pages to complete search of value.
...
Ignite node with persistent store enabled may now start to operate without reading all pages data from disk.
See also
https://apacheignite.readme.io/v2.1/docs/durable-memory
...