A distributed go-datastore implementation using Merkle-CRDTs.
go-ds-crdt is a key-value store implementation using Merkle CRDTs, as
described in
the paper by Héctor Sanjuán, Samuli Pöyhtäri and Pedro Teixeira.
It satisfies the
Datastore
and Batching
interfaces from go-datastore.
This means that you can create a network of nodes that use this datastore, and that each key-value pair written to it will automatically replicate to every other node. Updates can be published by any node. Network messages can be dropped, reordered, corrupted or duplicated. It is not necessary to know beforehand the number of replicas participating in the system. Replicas can join and leave at will, without informing any other replica. There can be network partitions but they are resolved as soon as connectivity is re-established between replicas.
Internally it uses a delta-CRDT Add-Wins Observed-Removed set. The current value for a key is the one with highest priority. Priorities are defined as the height of the Merkle-CRDT node in which the key was introduced.
Implementation is independent from Broadcaster and DAG syncer layers, although the easiest is to use out of the box components from the IPFS stack (see below).
Using batching, Any go-ds-crdt replica can easily process and sync 400 keys/s at least. The largest known deployment has 100M keys.
go-ds-crdt is used in production as state-synchronization layer for IPFS Clusters.
go-ds-crdt needs:
- A user-provided, thread-safe,
go-datastoreimplementation to be used as permanent storage. We recommend using the Badger implementation. - A user-defined
Broadcastercomponent to broadcast and receive updates from a set of replicas. If your application uses libp2p, you can use libp2p PubSub and the providedPubsubBroadcaster. - A user-defined "DAG syncer" component (
ipld.DAGService) to publish and retrieve Merkle DAGs to the network. For example, you can use IPFS-Lite which casually satisfies this interface.
The permanent storage layout is optimized for KV stores with fast indexes and key-prefix support.
See https://pkg.go.dev/github.com/ipfs/go-ds-crdt for more information.
This project is captained by @hsanjuan.
This library is dual-licensed under Apache 2.0 and MIT terms.
Copyright 2019. Protocol Labs, Inc.
