I'm currently working on a project based on the Dynamo paper, utilizing a no_std approach in Rust with `io_uring` and the NVMe interface. The system involves records formatted as `@account/collection/key`. I employ a rendezvous tree for locating the node containing the value, and the corresponding hash table indicates which NVMe sector stores that value.
I've allocated all necessary memory at startup, which amounts to 1.5 GB of RAM for every TB of NVMe storage for my hash table. While this makes management straightforward, it also feels inefficient. I'm hesitant to switch to a resizable hash table due to the risk of running out of memory during resizing operations, especially considering each physical node has 370 TB of NVMe divided among 24 virtual nodes.
Moreover, resizing would likely introduce significant slowdowns and could complicate collision handling when the table isn't fully utilized. Since I'm prioritizing performance, particularly for P99 metrics over P50, and I prefer not to utilize a disk-based B-tree due to the need for rapid access, I'm seeking advice on potential strategies or data structures that could alleviate these concerns. My background is in mathematics, which doesn't provide me with robust computer science knowledge, so I appreciate any insights!
1 Answer
It sounds like you're trying to optimize a complex setup, but dismissing B-trees may be a misstep. They have been utilized for decades in database design for good reason. Trying to push boundaries with a naive hash implementation might not yield the results you want. You might want to dive back into some of that foundational literature on databases to see what can be applied here.
Also, keeping your hash table fixed size can work, but make sure you're aware of how that might limit future scalability.
You raise a valid point about B-trees and their history in databases. I am using B-trees at a higher level, planning to manage them within records while keeping lower-level structures unaware. I appreciate the insight!