Otto: a unified approach to CRDTs and OT

Related tags

Testing otto-test
Overview

Otto: a unified approach to CRDTs and OT

This repo contains tests for otto. otto enables any boring Rust data structure (without Rc, RefCell etc.) to be used as a replicated data type. It supports achieving convergence via multiple approaches, including:

It also supports combining these approaches to synchronise a mix of clients using both CRDT and OT techniques.

Project aims

  • Minimal bookkeeping (no timestamps, IDs or similar)
  • Rich set of data types and operations (e.g. Map<K, V>, RichText, sort and group_by operations on List<T>)
  • Composability (support arbitrary nesting of types, e.g. List<(u64, List<u8>)>)
  • Differential dataflow support
  • Performance, sufficient for overhead to be negligible in real-world use (within ~1 OoM of Diamond types)
  • Achieve the strongest known useful properties (e.g. convergence and inverse properties)

Data types supported

Data type Operations supported
List<T> insert_at, delete_at, map_at
Register<T> set, map
(A, B, ...) map_a, map_b, ...
#[derive(State)] for arbitrary structs and enums map_field_a, map_field_b, ...
bool u8 u16 u32 u64 u128 i8 i16 i32 i64 i128 f32 f64 char usize isize -

License

Licensed under either of

at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

You might also like...
Experiments with Rust CRDTs using Tokio web application framework Axum.

crdt-genome Synopsis Experiments with Rust CRDTs using Tokio web application framework Axum. Background Exploring some ideas of Martin Kleppmann, part

a collection of well-tested, serializable CRDTs for Rust
a collection of well-tested, serializable CRDTs for Rust

crdts: family of thoroughly tested hybrid crdt's. A family of CRDT's supporting both State and Op based replication. what is a CRDT? CRDT's are the so

Parallel finance a decentralized lending protocol built on top of the Polkadot ecosystem. Our unique approach will allow users to earn
Parallel finance a decentralized lending protocol built on top of the Polkadot ecosystem. Our unique approach will allow users to earn "double interests" from staking and lending their tokens simultaneously.

Parallel Finance A new Cumulus-based Substrate node, ready for hacking ๐Ÿš€ Getting Started Follow these steps to get started with the Cumulus Template

A fast, iterative, correct approach to Stackblur, resulting in a very smooth and high-quality output, with no edge bleeding

A fast, iterative, correct approach to Stackblur, resulting in a very smooth and high-quality output, with no edge bleeding. This crate implements a t

A CI inspired approach for local job automation.

nauman A CI inspired approach for local job automation. Features โ€ข Installation โ€ข Usage โ€ข FAQ โ€ข Examples โ€ข Job Syntax About nauman is an easy-to-use j

Another approach to thread stack spoofing.
Another approach to thread stack spoofing.

Description This Twitter thread inspired the creation of this tool. Unwinder is a PoC of how to parse PE's UNWIND_INFO structs in order to achieve "pr

Easy to use cryptographic framework for data protection: secure messaging with forward secrecy and secure data storage. Has unified APIs across 14 platforms.
Easy to use cryptographic framework for data protection: secure messaging with forward secrecy and secure data storage. Has unified APIs across 14 platforms.

Themis provides strong, usable cryptography for busy people General purpose cryptographic library for storage and messaging for iOS (Swift, Obj-C), An

hy-rs, pronounced high rise, provides a unified and portable to the hypervisor APIs provided by various platforms.

Introduction The hy-rs crate, pronounced as high rise, provides a unified and portable interface to the hypervisor APIs provided by various platforms.

Obvious Unified Compression Helper is a CLI tool to help you compress and decompress files of several formats

Ouch! ouch stands for Obvious Unified Compression Helper and is a CLI tool to help you compress and decompress files of several formats. Features Usag

Design token framework โ€” adopt a unified design language across platforms, codebases, and teams
Design token framework โ€” adopt a unified design language across platforms, codebases, and teams

Palette Design tokens framework with atomic classes for React and Master CSS. Deliver a consistent visual identity across your apps with design tokens

MIPI Display Serial Interface unified driver

mipidsi This crate provides a generic display driver to connect to TFT displays that implement the MIPI DSI. Uses display_interface to talk to the har

Unified directories for different use cases of an application, providing standard directories for local development, when run as service or when run by a user.

UniDirs Unified directories for different use cases of an application, providing standard directories for local development, when run as service or wh

UniSBOM is a tool to build a software bill of materials on any platform with a unified data format.

UniSBOM is a tool to build a software bill of materials on any platform with a unified data format. Work in progress Support MacOS Uses system_profile

Travis CI and AppVeyor template to test your Rust crate on 5 architectures and publish binary releases of it for Linux, macOS and Windows

trust Travis CI and AppVeyor template to test your Rust crate on 5 architectures and publish binary releases of it for Linux, macOS and Windows Featur

A crate to convert bytes to something more useable and the other way around in a way Compatible with the Confluent Schema Registry. Supporting Avro, Protobuf, Json schema, and both async and blocking.
A crate to convert bytes to something more useable and the other way around in a way Compatible with the Confluent Schema Registry. Supporting Avro, Protobuf, Json schema, and both async and blocking.

#schema_registry_converter This library provides a way of using the Confluent Schema Registry in a way that is compliant with the Java client. The rel

Warp is a blazingly fast, Rust-based terminal that makes you and your team more productive at running, debugging, and deploying code and infrastructure.
Warp is a blazingly fast, Rust-based terminal that makes you and your team more productive at running, debugging, and deploying code and infrastructure.

Warp is a blazingly fast, Rust-based terminal that makes you and your team more productive at running, debugging, and deploying code and infrastructure.

Comments
  • Investigate otto vs diamond types divergence

    Investigate otto vs diamond types divergence

    We have run diamond types' fuzzing test, comparing otto and diamond types side-by-side.

    Otto agents converge to a common state. Diamond types agents converge to a common state.

    In some cases, however, this common state isn't the same for otto and diamond types.

    Even on unordered document contents โ€“ i.e. excluding cases where the changes appear in reverse order.

    It would be interesting to see if we can tweak otto's behaviour to match diamond types' exactly.


    Test case:

    https://github.com/tablyinc/otto-test/blob/a986dd31ba1bf0574b2893f4e1fc5f441e795614/tests/oplog_merge_fuzzer.rs#L196-L199

    Raw dump:

    i 0
    random operations at agent: 0
    Operation { loc: RangeRev { span: T 0..1, fwd: true }, kind: Ins, content: Some("a") }
    random operations at agent: 2
    Operation { loc: RangeRev { span: T 0..1, fwd: true }, kind: Ins, content: Some("a") }
    syncing agents: 0 โ†” 2
    diamond types (before): a
    diamond types (before): a
    diamond types (after): aa
    otto (before): a
    otto (before): a
    otto (after): aa
    
    
    i 1
    random operations at agent: 1
    Operation { loc: RangeRev { span: T 0..1, fwd: true }, kind: Ins, content: Some("a") }
    random operations at agent: 0
    Operation { loc: RangeRev { span: T 1..2, fwd: true }, kind: Del, content: Some("a") }
    syncing agents: 1 โ†” 2
    diamond types (before): a
    diamond types (before): aa
    diamond types (after): aaa
    otto (before): a
    otto (before): aa
    otto (after): aaa
    
    
    i 2
    random operations at agent: 2
    Operation { loc: RangeRev { span: T 0..2, fwd: true }, kind: Del, content: Some("aa") }
    random operations at agent: 1
    Operation { loc: RangeRev { span: T 2..3, fwd: true }, kind: Del, content: Some("a") }
    syncing agents: 0 โ†” 2
    diamond types (before): a
    diamond types (before): a
    diamond types (after): 
    otto (before): a
    otto (before): a
    otto (after): a
    

    Diagrams showing otto's behaviour:

    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜
    
    random operations at agent: 0
    
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜
    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜
    
    random operations at agent: 2
    
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜    โ”‚ 2 ins a โ”‚
    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜                   โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜
    
    syncing agents: 0 โ†” 2
    
         โ”Œ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”
         |                             โ–ผ
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜    โ”‚ 2 ins a โ”‚
    โ”‚ 2 ins a โ”‚                   โ”‚ 0 ins a โ”‚
    โ””โ”€โ”€โ”€โ”€aaโ”€โ”€โ”€โ”˜                   โ””โ”€โ”€โ”€โ”€aaโ”€โ”€โ”€โ”˜
         โ–ฒ                             |
         โ”” โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”˜
    
    
    
    random operations at agent: 1
    
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚    โ”‚ 2 ins a โ”‚
    โ”‚ 2 ins a โ”‚    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜    โ”‚ 0 ins a โ”‚
    โ””โ”€โ”€โ”€โ”€aaโ”€โ”€โ”€โ”˜                   โ””โ”€โ”€โ”€โ”€aaโ”€โ”€โ”€โ”˜
    
    random operations at agent: 0
    
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚    โ”‚ 2 ins a โ”‚
    โ”‚ 2 ins a โ”‚    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜    โ”‚ 0 ins a โ”‚
    โ”‚ 0 del a โ”‚                   โ””โ”€โ”€โ”€โ”€aaโ”€โ”€โ”€โ”˜
    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜
    
    syncing agents: 1 โ†” 2
    
                        โ”Œ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€โ”
                        |              โ–ผ
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚    โ”‚ 2 ins a โ”‚
    โ”‚ 2 ins a โ”‚    โ”‚ 2 ins a โ”‚    โ”‚ 0 ins a โ”‚
    โ”‚ 0 del a โ”‚    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚
    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜    โ””โ”€โ”€โ”€aaaโ”€โ”€โ”€โ”˜    โ””โ”€โ”€โ”€aaaโ”€โ”€โ”€โ”˜
                        โ–ฒ              |
                        โ””โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”˜
    
    
    
    random operations at agent: 2
    
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚    โ”‚ 2 ins a โ”‚
    โ”‚ 2 ins a โ”‚    โ”‚ 2 ins a โ”‚    โ”‚ 0 ins a โ”‚
    โ”‚ 0 del a โ”‚    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚
    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜    โ””โ”€โ”€โ”€aaaโ”€โ”€โ”€โ”˜    โ”‚ 2 del aaโ”‚
                                  โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜
    
    random operations at agent: 1
    
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚    โ”‚ 2 ins a โ”‚
    โ”‚ 2 ins a โ”‚    โ”‚ 2 ins a โ”‚    โ”‚ 0 ins a โ”‚
    โ”‚ 0 del a โ”‚    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚
    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜    โ”‚ 1 del a โ”‚    โ”‚ 2 del aaโ”‚
                   โ””โ”€โ”€โ”€โ”€aaโ”€โ”€โ”€โ”˜    โ””โ”€โ”€โ”€โ”€aโ”€โ”€โ”€โ”€โ”˜
    
    syncing agents: 0 โ†” 2
    
         โ”Œ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”
         |                             โ–ผ
    โ”Œโ”€โ”€โ”€โ”€0โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€1โ”€โ”€โ”€โ”€โ”    โ”Œโ”€โ”€โ”€โ”€2โ”€โ”€โ”€โ”€โ”
    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚    โ”‚ 2 ins a โ”‚
    โ”‚ 2 ins a โ”‚    โ”‚ 2 ins a โ”‚    โ”‚ 0 ins a โ”‚
    โ”‚ 0 del a โ”‚    โ”‚ 0 ins a โ”‚    โ”‚ 1 ins a โ”‚
    โ”‚ 1 ins a โ”‚    โ”‚ 1 del a โ”‚    โ”‚ 2 del aaโ”‚
    โ”‚ 2 del aaโ”‚    โ””โ”€โ”€โ”€โ”€aaโ”€โ”€โ”€โ”˜    โ”‚ 0 del a โ”‚
    โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜                   โ””โ”€โ”€โ”€โ”€โˆ…โ”€โ”€โ”€โ”€โ”˜
         โ–ฒ                             |
         โ”” โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”€ โ”˜
    
    opened by amascolo 1
Owner
Tably
Building the future of data.
Tably
Playwright is a rust library to automate Chromium, Firefox and WebKit built on top of Node.js library.

?? Playwright for Rust Playwright is a rust library to automate Chromium, Firefox and WebKit built on top of Node.js library. Installation [dependenci

octaltree 132 Jan 6, 2023
Advanced Fuzzing Library - Slot your Fuzzer together in Rust! Scales across cores and machines. For Windows, Android, MacOS, Linux, no_std, ...

LibAFL, the fuzzer library. Advanced Fuzzing Library - Slot your own fuzzers together and extend their features using Rust. LibAFL is written and main

Advanced Fuzzing League ++ 1.2k Dec 29, 2022
A fast Rust-based safe and thead-friendly grammar-based fuzz generator

Intro fzero is a grammar-based fuzzer that generates a Rust application inspired by the paper "Building Fast Fuzzers" by Rahul Gopinath and Andreas Ze

null 203 Nov 9, 2022
Breaking your Rust code for fun and profit

Breaking your Rust code for fun & profit this is an architecture-preview, not all components are there This is a mutation testing framework for Rust c

null 533 Dec 18, 2022
TestDrive automatically scrapes input/output data from BOJ(Baekjoon Online Judge) and runs tests for your executable binary file!

?? TestDrive What does it do? TestDrive automatically scrapes input/output data from BOJ(Baekjoon Online Judge) and runs tests for your executable bin

Hyeonseok Jung 3 Mar 5, 2022
A series of test cases to evaluate async Rust on the nrf52840 in terms of power usage and ergonomics.

A series of test cases to evaluate async Rust on the nrf52840 in terms of power usage and ergonomics. This is an experiment that uses unstable features only available on nightly rust.

Tweede golf 1 Oct 15, 2021
A tiny, super simple and portable benchmarking library.

benchmark-simple A tiny benchmarking library for Rust. Trivial to use Works pretty much everywhere, including WebAssembly (WASI, but also in-browser)

Frank Denis 3 Dec 26, 2022
Very minimalist tmux status bar that displays used memory and CPU usage.

woot-bar Ultra minimalist status bar that displays used memory and CPU usage woot-bar is made for tmux but it is compatible with anything that eats st

Nicolas Gryman 3 Dec 27, 2022
Notes and whatnot!

Noted CLI & TUI application to take and track notes. Generate Coverage (with cargo-llvm-cov): LCOV: cargo llvm-cov --all-features --workspace --lcov -

Tony B 2 May 3, 2022
A simple CLI for creating and managing Solana Lookup Tables.

LUT - A simple CLI for creating and managing Solana Lookup Tables Commands lut create Creates a new LUT using the default keypair in the Solana config

Metaplex Foundation 5 Oct 29, 2022