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

Last update: Nov 8, 2023

Overview

reconcile-rs

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

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

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

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
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

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
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