search

rust-crdt / rust-crdt

a collection of well-tested, serializable CRDTs for Rust
Apache License 2.0
1.32k stars 58 forks source link

Use BigRational for LSeq Identifiers and Rename LSeq to List #104

Closed davidrusu closed 3 years ago

davidrusu commented 3 years ago

LSeq Identifiers as implemented faithfully to the papers have some undesirable properties, namely around their sensitivity to mis-used allocation strategies.

In practice we were seeing panics due to the exponential tree growing beyond our max height.

This PR:

  1. replaces our Identifiers with the tuple (BigRationals, Dot)
  2. Expands the interval for allowable identifiers from (0,1) to all of the rationals (this is more efficient given how BigRationals are represented internally)
  3. The allocation strategy is now a deterministic algorithm, we simply choose the midpoint between identifiers we would like to insert between.
iancoleman commented 3 years ago

This removed bitvec but it is still listed in Cargo.toml

davidrusu commented 3 years ago

@iancoleman thanks for catching that, removed in #108