CAS is wrong (no compare-and-swap)

[ticki]

Atomic::<T>::cas() has signature

fn cas(&self, old: Option<Shared<T>>, new: Option<Owned<T>>, ord: Ordering) -> Result<(), Option<Owned<T>>>

But this isn't CAS in the classical sense. In fact, it makes certain things impossible to do. In particular, you don't get the value which didn't match. It acts more as "compare-and-set" rather than "compare-and-swap" (which is what the short form "CAS" tend to be used for).

I propose a non-breaking change (I do so because I think this problem is a major problem that needs to be addressed), which renames

• cas → compare_and_set
• cas_and_ref → compare_and_set_ref
• cas_shared → compare_and_set_shared

And uses the old names to alias these, but mark them with #[deprecated] and changed their doc comments to "Deprecated. Do not use." (kind of like what I did in chashmap).

Futhermore, the crux is to introduce a new method, compare_and_swap, with signature

    pub fn compare_and_swap(&self, old: Option<Shared<T>>, new: Option<Shared<T>>, ord: Ordering)
               -> Result<(), Option<Shared<T>>>

As for the semantics, this method compares self against old, and if it matches, it sets self to new and returns Ok(()). If the two don't match, Err(val) is returned, where val is the value self instead holds.

The change is pretty basic, but is it something of interest?

ping @aturon @alexcrichton /

[ticki]

Implemented in https://github.com/aturon/crossbeam/pull/118

[spacejam]

I see https://github.com/crossbeam-rs/crossbeam/pull/118 was closed. What's the status on this? I just started converting from raw pointers to this library for my lock-free log-structured persistent b-link tree and hitting this was kind of a facepalm...

[ghost]

We have a new API (designed in this RFC) in the crossbeam-epoch repository, which is currently in development, but not yet in a usable state.

We'll have a new, better epoch-based GC within the next month or so.

[ghost]

@spacejam If I understand correctly, you're basically implementing Microsoft's Deuteronomy in Rust? Looks very very cool! :)

I have a few questions:

1. What is the eventual end goal? I presume it is to build an embedded database, much like RocksDB and LMDB, except vastly superior in performance?

2. Do you think it would be possible to write a wrapper around rsdb that would make it a purely in-memory B+ tree, i.e. something like Mutex<BTreeMap<K, V>>, except it would be lock-free?

[spacejam]

@stjepang thanks! yes, the design is heavily inspired by the llama / bw tree / deuteronomy papers.

1. eventual end goal: have an embedded database that has great performance on flash storage, ideally beating rocksdb on reads and lmdb for larger-than-main-memory datasets, with comparable write performance to an LSM. take pains to simplify the individual components so that they can be formally verified. eventually this could mean a lock-free DSL that you can flip between symbolic execution to model check / real fast implementation for production. Then I want to use it as the base of a distributed database for kv storage, while the distributed part also handles log and object storage on top of a generic replication layer (with eventual eventual nice multitenancy shard configuration to keep different workloads from degrading each other), then a similar DSL for distributed algorithms that plays nicely with symbolic execution / high performance IO in production.

2. yeah, run it in /dev/shm :P (and there will be a nicer configuration-free wrapper struct for such workloads shortly)

[spacejam]

I'll dig into that RFC! Thanks for the info!

[spacejam]

@stjepang ~is there roughly working code anywhere for the new RFC? I'm happy to be a guinea pig and create a "trip report" on my experiences of using it~ I'll start working against the new changes!

[ghost]

is there roughly working code anywhere for the new RFC?

There is, but it's in my local branch. I'll try to whip up something this weekend so you can test it.

[spacejam]

@stjepang awesome! my goal is to have epoch-style management in rsdb in the next week or so, so that I can shift efforts to performance and reliability for a beta release by the end of the month. Those efforts will involve burning a lot of CPU cyles on exploring the thread-interleaving space, so maybe I'll get lucky and suss-out some bugs in this implementation as well.