Page History

...

Structure of segments and Loaded Pages Map is shown at fugure:

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).

...

This method allows to clean up big continuous segment of memory (usually whole page)

Image Removed Image Added

Eviction policy only makes sense when native persistence is disabled because what it does is actually freeing up memory when a user hits the memory limit.

...

Free list - list of pages, structured by amount of space remained within page.

Image RemovedImage Added

During selection of page to store new value pair Ignite does the following:

...

For object part which is less than page size, we can use partially filled page from free list.

Image RemovedImage Added

Let's consider object field update. If marshaller reported that updated field requires same size optimization may be used. Such update does not require page structure change or memory movement.

...

See page structure at picture below:

Image RemovedImage Added

Values are inserted into data page from the end to beginning. Items are filled from beginning to end.

...

• We keep Item (2 bytes) at same place for moved K,V3. 
• Indirect pointer is written into Item for K,V3 referring to Item with order 2. Item with order 2 refers to real data. See picture below.
  

Image RemovedImage Added

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.

...

To transform Page ID into Link it is possible to write offset to highest bits of Page ID.

 Image Added

Example of re-insertion new K,V4 element after some other K,V2 deleted. Following picture shows Indirect Item to direct Item replacement

Image Removed 

BPlus Tree Structure

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.

Image RemovedImage Added

Binary search is used to find required K. It is required to touch log N of data pages to complete search of value.

...

In 2.0 Ignite version it is possible to control it using DataRegionConfiguration (before 2.3 was named Memory Policy). One data region may include several caches (relation is 1.to.N).

All data may be separated by user to following classes: archive data and operational data:

User now can specify how much memory it is possible to allocate for cache group.

...