Use faster data structure for Redwood versioned page table in memory
- Dominant language
- C++
- Stars
- 16.7k
- Forks
- 1.6k
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 126
Description
The current data type is `std::unordered_map>`.
The outer hash is probably fine. The inner map, however, will be doing memory allocations and frees for every insertion and removal of entries which is not ideal.
The replacement inner structure must be ordered by Version and support lower / upper bound queries. Deletion will always be at the lowest Version in the map, and insertion will always be at a new highest Version.
One possible replacement is a FastAllocated circular array of pair that can be binary searched, and when it overflows its memory allocation it can be doubled in size. The minimum allocation can be something small, perhaps 4 or 8 entries in size.
The current type is declared here:
https://github.com/apple/foundationdb/blob/master/fdbserver/VersionedBTree.actor.cpp#L2046
Contributor guide
Research direction
Start in fdbserver/VersionedBTree.actor.cpp around line 2046, where the current versioned page table type is declared, and trace its insertion, removal, lower-bound, and upper-bound uses. Replace the inner structure while preserving Version ordering, lowest-Version deletion, newest-Version insertion, and both bound queries; verify the existing Redwood behavior remains correct.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- databases, performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100