xiangpenghao / congee Goto Github PK
View Code? Open in Web Editor NEWConcurrent ART (adaptive radix tree)
License: MIT License
Concurrent ART (adaptive radix tree)
License: MIT License
If can be optimistic
The current range scan is too restrictive on locking yet it's neither sound nor complete.
Many operations implement traverse_to_leaf (with small variations). It's better to extract this logic into a function for better readibility.
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.
please consider add c api interface to be used for other language.
... 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.
Add a new API compute_on_random
to better support randomized algorithms
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.
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.
Implement ArtUsize<K, V> where usize: from<K>, usize: from<V>
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.