A reconciliation service to sync a key-value map over multiple instances.

Related tags

Command-line rust sync reconciliation rust-lang distributed-storage key-value-store
Overview

reconcile-rs

Crates.io MIT licensed Apache licensed Build Status

Docs

This crate provides a key-data map structure HRTree that can be used together with the reconciliation Service. Different instances can talk together over UDP to efficiently reconcile their differences.

All the data is available locally in all instances, and the user can be notified of changes to the collection with an insertion hook.

The protocol allows finding a difference over millions of elements with a limited number of round-trips. It should also work well to populate an instance from scratch from other instances.

HRTree

The core of the protocol is made possible by the HRTree data structure, which allows O(log(n)) access, insertion and removal, as well as O(log(n)) cumulated hash range-query. The latter property enables querying the cumulated (XORed) hash of all key-value pairs between two keys.

Although we did come we the idea independently, it exactly matches a paper published on Arxiv in February 2023: Range-Based Set Reconciliation, by Aljoscha Meyer

Service

The service exploits the properties of HRTree to conduct a binary-search-like search in the collections of the two instances. Once difference are found, the corresponding key-value pairs are exchanged and conflicts are resolved.

Comments
  • Rename HTree -> HRTree

    Rename HTree -> HRTree

    The name HTree is already reserved on crates.io. HRTree, or HashRangeTree, better fits the inner working of our tree, which can be queried on hash ranges.

    opened by adriendellagaspera 0
  • Add Service::insert_bulk

    Add Service::insert_bulk

    Once #12 is resolved, insert() will immediately send the value in a datagram. This can be inefficient when inserting many values at once. Instead, we should also offer an insert_bulk() method, which will try to group as many values as possible in a datagram.

    opened by qsantos 0
  • Broadcast changes immediately

    Broadcast changes immediately

    Currently, the integration test in tests/service.rs must wait until the reconciliation protocol starts. This happens after up to 100 ms (the timeout for recv_from).

    This will also happen in real conditions.

    This can be improved by having Service::insert() broadcast the change immediately to the peers.

    opened by qsantos 0
  • Spec de la réconciliation

    Spec de la réconciliation

    Pour le moment le code expose deux comportements différents pour la réconciliation :

    • reconciliate pour réconcilier deux HTrees localement. Il ne sera jamais vraiment utile, sauf à choisir de partager entièrement le HTree par UDP avec une autre instance et de le récupérer "à jour" ensuite.
    • answer_queries pour acter le processus de réconciliation entre un HTree local et un remote, par le biais de ccommunication UDP. Il agit comme une surcouche de communication réseau au-dessus de la couche de stockage (le HTree). Mais pour le moment, cette couche de communication est encore trop couplée avec la couche de stockage. Notamment, c'est à ce niveau que sont gérés les conflits.

    Je propose de mieux établir la spec pour chaque couche pour mieux s'y retrouver notamment dans la définition des comportements associés.

    opened by adriendellagaspera 0
  • Separate HRTree into an independent crate

    Separate HRTree into an independent crate

    HRTree is an implementation detail to the reconciliation Service and could be used independently from the reconcile crate.

    Dependent on https://github.com/Akvize/reconcile-rs/issues/22

    opened by adriendellagaspera 0
  • Sample peer addresses in given range

    Sample peer addresses in given range

    This could be provided with CIDR syntax:

    cargo run -- 192.168.1.0/24

    cidr_utils looks like it is the most convenient crate to sample random IPs from a given range. We could also implement our own parser, based on, e.g., std::net::IpAddr.

    opened by qsantos 0
Owner
Akvize
Faire du conseil autrement. Radicalement.
Akvize
GitHub https://crates.io/crates/reconcile
A lightweight, embedded key-value database for mobile clients (i.e., iOS, Android), written in Rust.

A lightweight, embedded key-value database for mobile clients (i.e., iOS, Android), written in Rust. ⚠️ Still in testing, not yet ready for production

Tangent 6 Sep 25, 2023
A reliable key-value storage for modern software

Quick-KV A reliable key-value storage for modern software Features Binary Based Data-Store Serde Supported Data Types Thread Safe Links Documentation

null 3 Oct 11, 2023
Dynamic, Type-Erased Key-Value Maps in Rust

Dynamic Objects in Rust Do you love Rust but are tired of being constrained by static typing when you need a map to hold values of different types? Do

Travis A. Wagner 12 Feb 25, 2024
Provide CRUD CLI for Moco Activities with Jira Cloud Sync Option for faster time tracking.

Moco CLI Provide CRUD CLI for Moco Activities with Jira Cloud Sync Option for faster time tracking. Available commands Login Jira Must be called befor

Emanuel Vollmer 7 Nov 18, 2022
A Yocto setup and management tool that helps you keep your environment up-to-date and in-sync with your team

yb (Yocto Buddy) yb is designed to make it easy to setup and (perhaps more importantly) keep Yocto environments up-to-date and in-sync with your team.

null 13 Oct 31, 2022
Keeps `.env` files in sync with `env.sample`.

envsync This is a Rust port of env-sample-sync. It keeps .env files in sync with env.sample. It checks whether the local repository has an .env file a

Matthias Endler 2 Dec 22, 2022
Blazingly fast Rust CLI app to sync data from a folder of excel workbooks into generated c# code for unity usage

Extensions supported ( .xls, .xlsx, .xlsm, .xlsb, .xla, .xlam, .ods ) Speed Test Image shows the results of 5000defs synced from 2 workbooks and 5 she

null 4 Feb 16, 2023
Proof-of-concept on how to solve Bitcoin's light node sync problem with zkSNARKs

BTC Warp Prove and verify the longest Bitcoin PoW chain BTC Warp is a proof-of-concept system that aims to solve the client-syncing problem for Bitcoi

Succinct 45 May 31, 2023
A parser combinator that is fully statically dispatched and supports both sync/async.

XParse A parser combinator that is fully statically dispatched and supports both sync & async parsing. How to use An example of a very simple JSON par

Alsein 4 Nov 27, 2023
Local-first task manager/bug tracker that stores everything right in the git repository and can sync issues from/to GitHub.

git-task Local-first task manager/bug tracker within your git repository which can import issues from GitHub. Installation Build a binary, then add it

null 15 Sep 28, 2024
Show active TCP connections on a TUI world map.

Maperick Show active TCP connections on a TUI world map. Still WIP, but it's gonna be good. Setup git clone [email protected]:schlunsen/maperick.git cd m

Rasmus Schlünsen 5 Jul 8, 2022
A cli tool that let's you map commands to a shorter alias

Runner ?? What is this? A cli tool that let's you map commands to a shorter alias. Run the mapped command using the <ALIAS_NAME>. runner <ALIAS_NAME>

Pratush Rai 3 Nov 30, 2022
Slippy map (openstreetmap) widget for egui

Slippy maps widget for egui. Limitations There are couple of limitations when using this library. Some of them will might probably be lifted at some p

Piotr 13 Jun 14, 2023
Valq - macros for querying and extracting value from structured data by JavaScript-like syntax

valq   valq provides a macro for querying and extracting value from structured data in very concise manner, like the JavaScript syntax. Look & Feel: u

Takumi Fujiwara 24 Dec 21, 2022
Execute Javascript code in the Dioxus, and get the return value ( for Dioxus )

Golde Dioxus Execute Javascript code in the Dioxus, and get the return value. This demo can help use Javascript to calc the + operator formula. use di

YuKun Liu 15 Dec 27, 2022
A crate providing a MemoryCell struct, which stores a current and previous value.

memcell What is a MemoryCell? A MemoryCell is a struct containing both a current and optional previous value. Definition #[derive(Debug, Clone)] pub s

Imajin 9 Nov 21, 2022
This project returns Queried value from SOAP(XML) in form of JSON.

About This is project by team SSDD for HachNUThon (TechHolding). This project stores and allows updating SOAP(xml) data and responds to various querie

Sandipsinh Rathod 3 Apr 30, 2023
Spawn multiple concurrent unix terminals in Discord

Using this bot can be exceedingly dangerous since you're basically granting people direct access to your shell.

Simon Larsson 11 Jun 1, 2021
🌌⭐cosmo is a wrapper for Git essentially, allowing you to compress multiple commands into one

❯ Cosmo Git tooling of the future New feature: Cosmo hooks! Click here for more info! ❯ ?? Features Config files (with defaults!) Fast Easy to use Fri

Jack 1 Oct 31, 2021