...
Let's describe the B+ Tree in more detail to understand the need for invoke operation.
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 can look like this:
...
- Batch writing to data pages
- Batch updates in B+ Tree
Diagram overview
TBD
Batch
...
writing to data pages
Divide the input data rows into 2 lists:
...
Sequentially write objects and fragments that occupy the whole page. The data page is taken from "reuse" bucket, if there is no page in reuse bucket - allocate a new one.
For remaining (regular) objects (including the remainders ("heads") of large objects) , find the most free page with enough space in FreeList (allocate new one if there is no such page) and fill it up to the end.
...
- Implement insertDataRows operation in FreeList - insert several data rows at once.
- Preloader should insert a batch of data rows before initializing cache entries and should remove additional rows in case of fallback (if cache entry was not initialized). In the case when the cache entry is initialized incorrectly, preloader should rollback changes and remove pre-created data row.
Phase 2: DataStreamer support
...
- Add support for MVCC (TRANSACTIONAL_SNAPSHOT) cache mode.
Risks and Assumptions
...
- For BPlusTree batch operations, ordered keys are required, moreover, an attempt to simultaneously lock the same keys in a different order lead to a deadlock, so batch insertion into the page memory must be performed on an unlocked entries. Alternatively, keys passed in batches from different components (preloader, datastreamer, putAll) should be locked in the same order.
- Heap usage/GC pressure.
...
Jira |
---|
server | ASF JIRA |
---|
columns | key,summary,type,updated,assignee,reporter,priority,status,resolution |
---|
maximumIssues | 20 |
---|
jqlQuery | project = Ignite AND labels IN (iep-32) order by key |
---|
serverId | 5aa69414-a9e9-3523-82ec-879b028fb15b |
---|
|
The improvement in rebalancing time when using batch insertion is mostly noticeable when writing small objects and decreases with increasing object size.the improvement in total rebalancing time is reduced in cases of demander idle waiting for the next messages from the supplier