Expand description
Congee
A Rust implementation of ART-OLC concurrent adaptive radix tree. It implements the optimistic lock coupling with proper SIMD support.
It only supports (and is optimized for) 8 byte key; due to this specialization, congee has great performance – basic operations are faster than most hash tables, range scan is an order of magnitude faster.
The code is extensively tested with {address|leak} sanitizer as well as libfuzzer.
Why Congee?
- Fast performance, faster than most hash tables.
- Concurrent, super scalable, it reaches 150Mop/s on 32 cores.
- Super low memory consumption. Hash tables often have exponential bucket size growth, which often lead to low load factors. ART is more space efficient.
Why not Congee?
- Not for arbitrary key size. This library only supports 8 byte key.
Design principles
Congee aims to be a simple and reliable primitive for building database systems.
Example:
use congee::Art;
let art = Art::default();
let guard = art.pin(); // enter an epoch
art.insert(0, 42, &guard); // insert a value
let val = art.get(&0, &guard).unwrap(); // read the value
assert_eq!(val, 42);
let mut scan_buffer = vec![(0, 0); 8];
let scan_result = art.range(&0, &10, &mut scan_buffer, &guard); // scan values
assert_eq!(scan_result, 1);
assert_eq!(scan_buffer[0], (0, 42));Modules
Types needed to safely access shared data concurrently.
Structs
The adaptive radix tree.
Currently we only support only one type of memory, the allocator must return the type of memory requested.