someday
is a multi-version concurrency control primitive.
A lock-free, but more memory hungry alternative to Mutex<T>
or RwLock<T>
.
Reader
's are lock-free and most of the time wait-free.
The single Writer
is lock-free, but may clone data.
When the Writer
wants to push()
updates to Reader
's, it must:
- Atomically update a pointer, at which point all future readers will see the new data
- Re-apply the patches to the old reclaimed data OR clone the data if it cannot be reclaimed
The old data can be cheaply reclaimed and re-used by the Writer
if there are no Reader
's hanging onto old Commit
's.
If there are still Reader
's hanging onto old data, the Writer
will clone the data such that it can continue.
someday
is best in situations where:
Your data:
- Is relatively cheap to clone and/or de-duplicated
and if you have many readers who:
- Want to acquire a copy of data, lock-free
- Hold onto data (for a little while or forever)
and a writer that:
- Wants to mutate data, lock-free
- Wants to push changes ASAP to new readers, lock-free
- Doesn't mutate data that often (relative to read operations)
- Is normally in contention with readers using normal locks (
Mutex
,RwLock
)
-
Increased memory use: The
Writer
keeps at least two copies of the backing data structure, andReader
's can keep an infinite amount (as long as they continue to hold onto references) -
Deterministic patches: The patches/functions applied to your data must be deterministic, since the
Writer
may apply them twice -
Slow writes: Writes are slower than they would be directly against the backing data structure
someday
's API is similar to git
and semantically does similar actions.
The Writer
:
- Calls
add()
to add aPatch
(function) to their data - Actually executes those changes by
commit()
'ing - Can see local or remote (reader) data whenever
- Can atomically
push()
those changes to theReader
's - Can continue writing without having to wait on
Reader
's
The Reader(s)
:
- Can continually call
head()
to cheaply acquire the latest "head"Commit
- Can hang onto those
Commit
objects forever (although at the peril of memory-usage) - Will eventually catch up whenever the
Writer
callspush()
![](https://private-user-images.githubusercontent.com/101352116/292063119-b190db72-c56b-4336-a601-78296040d044.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQ0MjczNzMsIm5iZiI6MTcyNDQyNzA3MywicGF0aCI6Ii8xMDEzNTIxMTYvMjkyMDYzMTE5LWIxOTBkYjcyLWM1NmItNDMzNi1hNjAxLTc4Mjk2MDQwZDA0NC5wbmc_WC1BbXotQWxnb3JpdGhtPUFXUzQtSE1BQy1TSEEyNTYmWC1BbXotQ3JlZGVudGlhbD1BS0lBVkNPRFlMU0E1M1BRSzRaQSUyRjIwMjQwODIzJTJGdXMtZWFzdC0xJTJGczMlMkZhd3M0X3JlcXVlc3QmWC1BbXotRGF0ZT0yMDI0MDgyM1QxNTMxMTNaJlgtQW16LUV4cGlyZXM9MzAwJlgtQW16LVNpZ25hdHVyZT01OGIyOTZjYmQzZGZmMmE5OWFiM2M0MGZkZmY2NmYyODU1MjJlYjg3NzE1YzkxMGFjYjBiYzgzOTIyZTIyNTA1JlgtQW16LVNpZ25lZEhlYWRlcnM9aG9zdCZhY3Rvcl9pZD0wJmtleV9pZD0wJnJlcG9faWQ9MCJ9.6Tx5tRnIkfAGoiBFGqle43e2jBBoBlkHBy8aWKUFD2M)
This example shows the typical use case where the Writer
:
- Adds some changes
- Reads their local changes
- Locks in those changes by calling
commit()
- Finally reveals those changes to the readers by calling
push()
and the Reader
:
- Continually reads their latest head
Commit
of the current data - Eventually catches up when the
Writer
publishes withpush()
The code:
use someday::{
Patch,
Writer,Reader,
Commit,CommitRef,
CommitInfo,PushInfo,
};
// Create Reader/Writer for the string "hello".
let (r, mut w) = someday::new("hello".to_string());
// The readers see the data.
let commit: CommitRef<String> = r.head();
assert_eq!(commit.data, "hello");
assert_eq!(commit.timestamp, 0);
// Writer writes some data, but does not commit.
w.add(Patch::Ptr(|w, _| w.push_str(" world")));
// Nothing committed, data still the same everywhere.
let data: &String = w.data();
assert_eq!(*data, "hello");
// Patches not yet committed:
assert_eq!(w.staged().len(), 1);
// Readers still see old data.
assert_eq!(r.head().data, "hello");
// Writer writes some more data.
w.add(Patch::Ptr(|w, _| w.push_str("!")));
// Readers still see old data.
assert_eq!(r.head().data, "hello");
// Writer commits their patches.
let commit_info: CommitInfo = w.commit();
// The 2 operation were committed locally
// (only the Writer sees them).
assert_eq!(commit_info.patches, 2);
// Readers still see old data.
assert_eq!(r.head().data, "hello");
// Writer finally reveals those
// changes by calling `push()`.
let push_info: PushInfo = w.push();
assert_eq!(push_info.commits, 1);
// Now readers see updates.
let commit: CommitRef<String> = r.head();
assert_eq!(commit.data, "hello world!");
// Each call to `.commit()` added 1 to the timestamp.
assert_eq!(commit.timestamp, 1);
These features are for (de)serialization.
You can directly (de)serialize your data T
from a:
Writer<T>
Reader<T>
Commit<T>
Feature Flag | Purpose |
---|---|
serde |
Enables serde 's Serialize & Deserialize |
bincode |
Enables bincode 2.0.0-rc.3 's Encode & Decode |
borsh |
Enables borsh 's BorshSerialize & BorshDeserialize |
The Minimum Supported Rust Version is 1.70.0
.