cmars / conflux Goto Github PK

Distributed database synchronization library

License: GNU General Public License v3.0

Go 100.00%

conflux's Introduction

conflux - Distributed database synchronization

Conflux synchronizes data by unique content-addressable identifiers. It does this by representing the entire set of identifiers with a polynomial. The difference between the databases is represented as a ratio of these polynomials. However, the polynomials are very large, since they represent every identifier in the database. The difference between databases is communicated by evaluating the difference ratio at a number of constants. Through the magic of rational function interpolation, the difference ratio can be reconstructed from these data points.

This algorithm is described in the papers, "Set Reconciliation with Nearly Optimal Communication Complexity" and "Practical Set Reconciliation".

The reconciliation algorithm are released under the GNU General Public License version 3. The reconciliation network protocol and prefix tree data storage interfaces are released under the Affero General Public License version 3.

Usage

Conflux API is versioned with gopkg. Use in your projects with:

import "gopkg.in/hockeypuck/conflux.v2"

conflux's People

Contributors

Stargazers

Watchers

Forkers

oftn-oswg davecheney hockeypuck bjmgeek productinfo simia-tech sportsbitenews

conflux's Issues

Need to keep recon DB in sync with key DB

The recon prefix tree needs to have insert or remove public key digests according to changes in the key database.

Prefix tree caching

Implement node caching. Maybe https://github.com/golang/groupcache?

Unit tests for Interpolate

Create a set of unit tests for the rational function interpolation function.

ReconRqstPoly set differences might be backwards

I'm finding that when Hockeypuck+conflux gets a ReconRqstPoly from SKS server-side, it tries to fetch the hashes rather than send them out. Something seems flipped.

Extend recon.Settings to support configuration of LevelDB path

Refactor recon peer tests to exercise different storage backends

It'd be nice to run the peer tests against different storage backends -- mem vs cask vs leveldb.

Make connection timeout configurable

It's useful to have short connection timeouts for testing, longer ones for real-world peering.

Poly assignment broken in self-operations

Given a p *Poly, something like p.Mul(p, p) doesn't seem to work properly. We either need to change the API design, or make this work like it does for big.Int.

Break up conflux namespace

Candidates for splitting out:

conflux.z
conflux.poly

Finite field library spin-off?

Seems like polynomials over finite fields could be useful in other applications. Maybe we should spin these off into a separate library?

Configurable finite field modulus

conflux.recon and its subpackages are hardcoded to use a constant prime from SKS for the finite field in which all arithmetic occurs. This modulus is designed for enclosing 128-bit MD5 values.

conflux could be made configurable to support arbitrary finite fields for enclosing larger keys. This would allow content-addressable key synchronization with larger, more secure, FIPS-compatible hashes: SHA1, SHA2 family & beyond.

PostgreSQL prefix tree

Need a PostgreSQL-backed prefix tree for tight integration with Hockeypuck.

Unit tests for Reconcile

Unit test for full reconciliation between two sets.

Prefix tree should ignore duplicate keys on Peer.Insert, missing keys on Peer.Remove

Need to make the prefix tree more resilient, so that users of the recon library do not need to track the existing state of the tree.

Insert should add a *Zp key only if the key is not already present in the tree. Likewise, Remove should remove the *Zp key only if the key exists in the tree. Otherwise, these methods should do nothing -- or better yet, they could return the status of the key.

In order to implement this, we'll need to record a breadcrumb trail of operations to apply to the parent nodes where a key is inserted or removed, and only apply them if the operation is valid w.r.t the prefix tree contents.

  00000000  0a 00 00 00 05 00 00 00  07 76 65 72 73 69 6f 6e  |.........version|
  00000010  00 00 00 0c 65 78 70 65  72 69 6d 65 6e 74 61 6c  |....experimental|
  00000020  00 00 00 09 68 74 74 70  20 70 6f 72 74 00 00 00  |....http port...|
  00000030  05 31 31 33 37 31 00 00  00 0a 62 69 74 71 75 61  |.11371....bitqua|
  00000040  6e 74 75 6d 00 00 00 01  32 00 00 00 04 6d 62 61  |ntum....2....mba|
  00000050  72 00 00 00 01 35 00 00  00 07 66 69 6c 74 65 72  |r....5....filter|
  00000060  73 00 00 00 00                                    |s....|
  00000065

sks:

  00000000  00 00 00 70 0a 00 00 00  05 00 00 00 0a 62 69 74  |...p.........bit|
  00000010  71 75 61 6e 74 75 6d 00  00 00 04 00 00 00 02 00  |quantum.........|
  00000020  00 00 07 66 69 6c 74 65  72 73 00 00 00 0d 79 6d  |...filters....ym|
  00000030  69 6e 73 6b 79 2e 64 65  64 75 70 00 00 00 09 68  |insky.dedup....h|
  00000040  74 74 70 20 70 6f 72 74  00 00 00 04 00 00 2c 6b  |ttp port......,k|
  00000050  00 00 00 04 6d 62 61 72  00 00 00 04 00 00 00 05  |....mbar........|
  00000060  00 00 00 07 76 65 72 73  69 6f 6e 00 00 00 05 31  |....version....1|
  00000070  2e 31 2e 33                                       |.1.3|