xiangpenghao / congee Goto Github PK

Concurrent ART (adaptive radix tree)

License: MIT License

Rust 99.64% Dockerfile 0.15% Shell 0.21%

rust concurrent index adaptive-radix-tree containers database range-index high-performance

congee's Introduction

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) fixed sized 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 codebase is extensively tested with {address|leak} sanitizer as well as libfuzzer. Congee's performance is continuously tracked here.

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));

Performance

Benchmarked with the conc-map-bench

congee's People

Contributors

Stargazers

Watchers

Forkers

moontrade fabianmurariu iq-scm elbow-jason syaojun amdahl-rs

congee's Issues

Some thoughts on generic keys

Current generic key support in Congee is broken: every key type is stored as usize and compared as usize. The ordering of the original generic key is ignored.
ART is a radix tree and implicitly assumes keys to be strings. It supports integer numbers because it happens to have a meaningful byte-order (depending on the endian).

Therefore only two types of keys are meaningful to Congee: string and integer numbers. In fact, production database may only support string keys as the index (e.g., BigTable).
In the future, Congee will only support string. Support for integer numbers will be a syntax sugar.

Interface for comare_exchange

... should be

pub fn compare_exchange(
    &self,
    key: &K,
    old: Option<&V>,
    new: Option<V>,
    guard: &epoch::Guard,
) -> Result<Option<V>, Option<V>> {...}

Currently the old value is &V, it should be Option<&V>. Once this is done, the compute_or_insert is not necessary.

[feature] compute on random

Add a new API compute_on_random to better support randomized algorithms

Range scan needs a overhaul

The current range scan is too restrictive on locking yet it's neither sound nor complete.

Compute_if_present doesn't need a exclusive lock over the whole node

If can be optimistic

compute if present share the same code of traversing to leaf

Many operations implement traverse_to_leaf (with small variations). It's better to extract this logic into a function for better readibility.

Implement `ArtUsize<K, V>`

Implement ArtUsize<K, V> where usize: from<K>, usize: from<V>

Implementing clone

Congee can't be cloned (at least not with https://doc.rust-lang.org/std/clone/trait.Clone.html) due to the linearizability requirement (#8 (comment)).

Consider two threads:

T1:  ------|<----------- clone ---- ------>|-----
T2: ----------|insert(0)|---|insert(1000)|------

The cloned tree from T1 may contain 1000 but not 0, violating linearizability.

Two ways to mitigate this:
(1) Provide a fn clone(&mut self), and ask the caller to ensure no concurrent access. Since we don't provide a safe way to get mutable reference, users must go into unsafe (even UB) to get the mutable reference.
(2) Users can do a range scan over the tree and reconstruct the tree using the records scanned. Each range scan will read several records in a linearizable manner; to scan the entire tree, users must call range scan multiple times. There's no guarantee on multiple scans to be linearizable, but this is a performance-correctness tradeoff.

(I personally don't believe anybody needs linearizability over the entire tree clone; if such thing happens, I don't believe there's any better method than locking the entire tree)
So cloning over congee is a bad idea and if you frequently uses clone, congee might not be best data structure.

add c api interface

please consider add c api interface to be used for other language.

Goals and non goals

The high level API of congee is not locking based. It always returns a copy of the data (not reference), i.e., a snapshot of the value at the moment of reading. This also means that the returned value may not be the latest. Users need to incorporate the compare_exchange API (similar to the ones in std::atomic) to implement locking operations.