3 ms·
I'm surprised nobody mentioned the Rust crate left_right[1]. It's also a map that supports multiple readers AND a writer. It does this by maintaining two maps
by ismailmaj 3y ago
I'm surprised nobody mentioned the Rust crate left_right[1].
It's also a map that supports multiple readers AND a writer.
It does this by maintaining two maps, one used by the writer and one used by the readers and atomically swap the two when useful, the cool part is that reads are wait-free but the cost is at least double memory usage and slow writes (twice the work).
[1]: https://docs.rs/left-right/latest/left_right/ https://docs.rs/left-right/latest/left_right/
- clappski 3y agoReminds me of the shadow paging used in LMDB, which is effectively the same but at the page level rather than the whole tree and allows each reader their own context to read from, rather than a shared reader context.
- gpderetta 3y agoNice! As far as I understand, it uses RCU-like epochs, except that the reclaimed memory is immediately used for the new version of the data, bounding the memory usage at the cost of having the writer block. The oplog seems quite an additional complication, but I guess it makes sense for costly updates. The simplest solution is to just copy the last version over the stale version. edit: note this is not just a map datastructure. As far as I understand, left_right can wrap any data structure.
- legobmw99 3y agoThe author of left_right has a really great YouTube channel on Rust programming: https://youtube.com/@jonhoo https://youtube.com/@jonhoo