...

Currently batch updates on page memory level are not implemented in Ignite. Internal structures, such as BPlusTree and FreeList, do not support them. The performance of batch operations (putAll, datastreamer, preloader) can be improved by implementing batch updates on page memory level.

Competitive analysis

Profiling

Profiling the current rebalancing process shows that most of the time spent on working with FreeList and B+ Tree (details).

...

The keys of the tree (hashes) are stored on the B+ Tree pages (index pages), the cache key-value itself is stored on data pages. Each item on the index page includes a link to the data page item. In general, a B+ Tree supports find, put and remove operations. For put andremove, you must first find the point of insertion/update/removal. So, cache entry update without invoke operation should can look like this:

• Search B+ Tree for link to old key-value (find)
• The old value does not differ in length - a simple value update of key-value on the data page
• The old value differs in length - the link to it changes:
  • Store a new key-value into data page
  • Put B+ Tree key (with "secondary" find) to update link to data page item
  • Remove old key-value from data page

...

1. Remove a page from FreeList, which has enough storage space (if there is no such page - allocate a new one)
2. Lock page
3. Write cache entry data
4. Update page counters
5. Unlock page
6. Based on the remaining free space insert page to into FreeList

Advantages

The batch will improve the average :

1. Average insertion time by reducing count of FreeList actions on each data row

...

1. :
   * insert/remove

...

1. page into FreeList
   * update page counters
   * pages locking
   * WAL recording
2. Average search/update time in B+ Tree

...

Proposed changes

Implementation should consists of two major related improvements:

...