My solution is to leave original array untouched, and write delta log into free space after main array.
So that is the trick. New store design uses free space on pages to write delta log. This delta log is latter merged with main data on page by background worker.
This has some key benefits:
several updates of same page in short interval, are merged together into single write (if several keys are inserted into BTree node, sorted array is only updated once with all changes)
it reduces write amplification by several magnitudes at expense of temporary slower reads (until background worker kicks in, reader has to replay write log to get most recent version)
there is no complex free space allocator (fixed size page), yet unused space on pages is not wasted
“compaction” is very simple, localized and atomic; only single page IO. No traversal or inter-page dependencies
read and write IO is localized on single page, great for cache locality etc…
it is universal, works on most shapes of data, not just sorted BTree nodes. For example JSON documents have similar write amplification problem, and can use delta logs
opens road to new features (snapshots, isolation…)
write log can be used for different scenarios (streaming over network, write ahead log…)
I am working on proof of concept implementation. It will provide PageLogStore and
SortedMap<Long,Long> implementation. After performance is verified, I will move to MapDB 4 development again.