xiangpenghao / congee Goto Github PK

... 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.

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

Add a new API compute_on_random to better support randomized algorithms

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

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

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.

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

If can be optimistic

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.

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.