a collection of well-tested, serializable CRDTs for Rust

Here is an implementation of a causality buffer based on the algorithm presented in

D. Malkhi and D. Terry, “Concise Version Vectors in WinFS,” p. 13.

The idea is to ensure we re-order messages so that they respect a causal order, which is important for datastructures like LSEQ where we need to receive each peer's messages in order but don't want to pay the cost of sending a full vector clock with each operation.

The Causality Barrier is composed of two components: a version vector (with exceptions) and an unapplied operations buffer.

The Version Vector with Exceptions works by tracking two pieces of information for every known peer: the maximum message timestamp and a list of exceptions. The list of exceptions is composed of the timestamps less than the maximum which we haven't seen yet.

When we receive a new operation we follow the following algorithm in pseudo-pseudo-code:

0. Update the version vector with A's timestamp, if A > max then we set max = A and we add the range [old max, A) to the exceptions. Otherwise if A is in the exception set, we remove it's timestamp.
1. Check if the operation A must occur after another operation B
2. Check if we've seen B a. If yes, then allow A, and check the unapplied buffer for opeations that transitively depend on A b. If no, buffer A

Hi,

I've been implementing a version of LSEQ focused on correctness (I've found bugs in every OSS implementation so far :/). Would there be any interest in having it merged into this library?

I still need to rewrite the id generation code to more cleanly integrate all the fixes to all the bugs I discovered along the way and write more property tests, but once that's done I can prepare a PR.

I'm opening this pull request now so that everyone can see the implementation.

The major thing I'd like to do before considering this ready to merge is to write more property tests. I'd also like to write longer docs and cite the relevant [2][3]papers in those.

It could also be possible to use an actual exponential tree structure to store the LSEQ but I'm not convinced that it would be more efficient at least without some significant unsafe code.

If you have a causal network layer then this implementation is correct :tm:. I also have an implementation of a "Version Vector with Exceptions"[1] which turns any reliable network into a causal one with low overhead.

relevant: #58 #70

cc: @FintanH

[1]D. Malkhi and D. Terry, “Concise Version Vectors in WinFS,” p. 13. [2]S. Weiss, P. Urso, and P. Molli, “Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks,” in 2009 29th IEEE International Conference on Distributed Computing Systems, Montreal, Quebec, Canada, Jun. 2009, pp. 404–412, doi: 10.1109/ICDCS.2009.75. [3]B. Nédelec, P. Molli, A. Mostefaoui, and E. Desmontils, “LSEQ: an adaptive structure for sequences in distributed collaborative editing,” in Proceedings of the 2013 ACM symposium on Document engineering - DocEng ’13, Florence, Italy, 2013, p. 37, doi: 10.1145/2494266.2494278.

@davidrusu , I'm not fully sure, but I'm trying to use the Dot of each LSEQ operation to populate a VClock that I'm planning to use as a context.

When I get the Dot from the very first append op on an LSEQ its counter is 0, so when I want to compare that with the context, where this op didn't happen, (using VClock::partial_cmp) they happen to be Equal. Thus, shouldn't the Dot's counter of the very first op be 1 instead of 0?

As I was browsing through the Orswot implementation it struck me by surprise that the set is not updated underneath.

This could be because I have a different idea of what would happen while using these CRDTs. In my head, I would think that if I call add that it gets added to the set and I now have my view of the world. I also get the Op as an output which I broadcast to other's that I collaborate with. They can then apply this to their view.

The current behaviour, however, leaves me with an empty set and two ops. Do I have to apply the ops myself?

I wanted to check if there might be some known state of the art for a vector-like CRDT.

I believe what I want is a grow-only vector where I can also edit the items using an index. I started playing around with the concept of a grow-only vector using sorted-vec. This seemed to work and make sense as a CvRDT. It covers the case of creating a new vector and inserting based on ordering. Introducing editing, however, would mean that I need a CmRDT.

Does this make sense? Have you heard of something like this? And would someone like to help implement this with me? :grin:

I need to implement (again!) a sync solution on top of SQL (sqlite/postgresql) and have found about CRDt and wonder if is a good fit. Next, how actually could be used.

My apps are traditional business apps (like invoices) that have central databases and only sync with stable schemas (if a schema changes, the clients MUST first migrate).

So this is maybe simpler than https://github.com/rust-crdt/rust-crdt/issues/51 (JSON), where things go recursive.

P.D: I need to load all the database records to apply CRDt, and if yes, is possible to separate the storage and querying from the resolution algorithm?

The documentation for crdts::lwwreg::LWWReg mentions not to use timestamps "unless you are comfortable with divergence" without explaining why.

But to me, timestamps are a fairly obvious way of determining the "last" write. If they are precise enough, you should never have an equal timestamp (and if they do happen to be equal, you could probably just choose arbitrary).

Is there something I'm not seeing here that would cause timestamps to be more of an issue?

Right now it seems LSeq is the only CRDT type to automatically apply ops when funcs are called on a given instance.

This PR brings Lseq inline in requiring that lseq.apply(op) to be called to change the lseq itself

Hey! :wave:

I've just picked up your library to implement a convergent issue tracker and it's been nice to work with so far. So thank you for providing such a useful crate in the Rust ecosystem :grin:

What I wanted to bring up was that the bounds imposed on stuff like mvreg::Val, i.e Debug and Clone seem very restrictive. I've cloned the repo locally and tried removing them. Debug wasn't used anywhere and Clone is only used on a few of the functions.

I think it might be better to localise the trait bounds where they are needed rather than have blanket bounds. This localises the needs for the traits indicating to the caller when they are needed. Maybe they don't even need the bound in the first place :man_shrugging:

Just wanted to get your thoughts on this and ask would you mind a pull request that included these changes?

In some use-cases I would like to be able to add/remove multiple members to/from an Orswot at a time. It seems that Op::Rm already tracks multiple members and Op::Add (and the corresponding apply logic) could be adapted as well to apply the actor's dot to each individual member's clock.

Do you think this would cause any unforeseen problems?

Happy to submit a PR if interested.

The source file art/crdt_merge.png contains an embedded ICC profile which is copyright Apple and not freely licensed, effectively making that image non-free.

Please strip that ICC profile from the image (assuming there is no actual need for it).

In case you are curious how to check for (e.g. license and copyright) metadata in ICC profiles embedded in images, the most convenient way I am aware of is to use commandline tool exiftool part of perl CPAN module Image::ExifTool.

I have read most of the A comprehensive study of Convergent and Commutative Replicated Data Types paper, but as far as I can tell, it contains no notion similar to ResetRemove, and I can't figure out what purpose that trait serves.

The following explanation can be found in the docs for Map, but not for ResetRemove:

Reset-remove means that if one replica removes an entry while another actor concurrently edits that entry, once we sync these two maps, we will see that the entry is still in the map but all edits seen by the removing actor will be gone.

1. For some reason, only CRDTs which fulfill ResetRemove are a Val and can be used in Map. Why?
2. The above quote should be in ResetRemove probably?
3. I don't understand why the property as described in the quote makes sense. There is no info on it in the paper either. How does that help maintain the CRDT properties? I am confused.

It seems like the intended way to use the Map::update function is to use the context given in the closure, e.g. |set, c| set.add("erik", c):

https://github.com/rust-crdt/rust-crdt/blob/b405f77361d8cddc8d0b5375e7d6c50f2de16698/examples/reset_remove.rs#L18-L22

However, with GCounter instead of Orswot as the inner CRDT, this is more awkward, since the GCounter::inc function takes an actor directly, and not a context. Feels like an inconsistency. Or maybe I just missed docs somewhere, since I'm still exploring CRDTs.

My code so far, which feels wrong:

type A = &'static str;
let mut m: Map<String, GCounter<A>, A> = Map::new();
let add_ctx: AddCtx<A> = m.read_ctx().derive_add_ctx("Actor1");
m.apply(m.update(
    "Kiiya",
    add_ctx,
    |previous: &GCounter<A>, add_ctx: AddCtx<A>| {
        // return type of this closure is a `Dot<A>`.
        previous.inc(add_ctx.dot.actor) // This feels very wrong. I should be able to use the add_ctx directly here.
    }
));

This is a POC for an append only CRDT.

The idea is to use VClock partial order when possible, and fall back to ordering by Actor when VClock's are concurrent.

Take the example below:

1. We start with the empty chain
2. A then appends a₁ with context {A1}
3. Then B and C concurrently append b₁ and c₁ respectively.

Note that B and C's context dominates A's context.

If we try to resolve the final chain order, it's clear that the chain begins with a₁, ... but it's not clear how to order b₁ and c₁ since their contexts are concurrent ({A1, B1} is not bigger than {A1, C1} and vice-versa).

To resolve this ambiguity, we need a total order over the competing contexts. The rule used for this chain CRDT here is as follows:

1. first try to order by VClock's partial order, if that succeeds, use that ordering.
2. Otherwise, remove any dots that have been seen by the other side
3. sort the remaining dots by (Actor, Counter) for each side respectively.
4. Pairwise compare the two sorted sets to find the final ordering.

In our case, step 2. produces {A1, B1} => {B1} and {A1, C1} => {C1} since A1 has been seen by both sides. Then we see that B's value will come before C's since B < C lexigraphically.

So the final sequence is a₁, b₁, c₁.

As discussed in #72 it can be perceived as weird by users that a function such as Orswot::add does not actually add to the underlying set.

For example, if I were to call add followed by read the addition would not be seen on my side. One idea would be to have another function called apply_add that mutates the underlying set as well as outputting the Op to write to a log/broadcast the changes.