Motivation

// Define the problem to be solved.

Some benchmarks have shown we spend a lot of time to manage a free list structure.

Description

// Provide the design of the solution.

Ignite uses page memory organization to store a cache information. To use a memory more effectively a free list data structure 1 are using.
The free list is a doubly linked list that stores a reference to memory pages of approximately equal free space. For example, a free list has a different link to stores all the data pages that have up to 75% free space, and a list that keeps track of the index pages with 25% free space. Data and index pages are tracked in separate free lists.

To use a memory as effectively as possible any changes in these lists are saving into WAL in synchronize mode.

To get rid of performance degradation we can consider few approaches:

1. Lasy FreeList.

Don't save any information about FreeLists into WAL. And restore an information about page free space only after reading the page. Use new pages and need to wait for the first read, update for the page to update FreeList information.

Pro:

Exclude any IO overhead for that kind operation.

Cons:

Need to restore the free lists after restart cluster. We can read some pages after a restart in asynchrony mode to refresh the free list.

2. FreeList throttling.

The system can save not every change but selective (f.e. once per 100 change).

Pro:

Keep current algorithm. Reduce IO operations.

Cons:

After a restart, a free list information will be out of date but not all. It might lead to some redundant memory using.

3. BitMap FreeList.

We can use a BitMap approach to store an information about free space for pages. The same approach as for tracking pages.

Pro:

Keep an information for 4k pages in one 4K byte bitmap page.

Cons:

Change a current implementation

Discussion Links

// Links to discussions on the devlist, if applicable.

Reference Links

// Links to various reference documents, if applicable.

1 https://apacheignite.readme.io/docs/memory-architecture#section-free-lists

Tickets

// Links or report with relevant JIRA tickets.