how does replication work?

[dominictarr]

discussion that started here

Level/leveldown#229 (comment)

@timkuijsten how is the DAG used? how are concurrent updates managed?

[timkuijsten]

Concurrent updates are managed/merged via a perspective bound^* three-way-merge. There is only a conflict if an attribute is changed but in a different way. If this happens, a version is marked so that it can be resolved at any time in the application layer. Multiple heads are possible, but there should be only one non-conflicting head in the local DAG, one valid current version.

Each database synchronizes over TCP. It's encouraged to keep the connection open and replicate updates as soon as they are made since the smaller the window, the less chance that a merge conflict will arise. Of course batch wise updates and periodic connections are supported as well.

^* Perspective bound means each database has their own perspective. Say I have a product database that contains the following two tyres:

{
  h: { id: 'tyre1', v: 'j7Sa', pa: [] },   // object header, v = version, pa = parent versions
  b: {                                     // object body, application specific
    name: 'Bridgestone',
    location: 'New York',
    price: 10
  }
}

{
  h: { id: 'tyre2', v: 'Xhsk', pa: [] },
  b: {
    name: 'Goodyear',
    location: 'Amsterdam',
    price: 15
  }
}

If I want to replicate these two documents to you, it's possible for me to transform the documents before I send them. For instance I could register a hook that removes the price like this:

function(product, cb) {
  delete product.price;
  cb(null, product);
}

After replicating you will have the following two documents from me in your local database:

{
  h: { id: 'tyre1', v: 'j7Sa', pa: [] },
  b: {
    name: 'Bridgestone',
    location: 'New York'
  }
}

{
  h: { id: 'tyre2', v: 'Xhsk', pa: [] },
  b: {
    name: 'Goodyear',
    location: 'Amsterdam'
  }
}

In similar fashion it's possible for a transform hook to call back without the product in order to filter the document so that it won't be shared with a peer.

[dominictarr]

cool! I have also been thinking about the idea like "perspective bound" but I have been calling it "a subjective datastructure" I don't have any code yet though... just day dreaming about it.

How does the replication work? I if I recall, in couch it requests the sequences since it has last talked to that instance, and then requests any versions it needs.

do you versions go all the way back like git? it looks like you have a distinction between primary-primary and primary-secondary replications - if I have deleted a property in a transform then I wouldn't want you to replicate that back to me.

[timkuijsten]

How does the replication work? I if I recall, in couch it requests the sequences since it has last talked to that instance, and then requests any versions it needs.

A peer initiates a connection with an optional offset (the last version it has local of the peer it's connecting to). The peer then sends all versions created since then.

do you versions go all the way back like git? it looks like you have a distinction between primary-primary and primary-secondary replications - if I have deleted a property in a transform then I wouldn't want you to replicate that back to me.

I version all the way back, although in the new format I've created with LevelDB (tree.js) it will be possible to prune old versions up to user specified limits (i.e. only keep the last three versions of each item or x amount of versions in total).

If you configured and are authorized to get versions from your peer as well, you might get back the transformed object (the tyre without the price). Each database has one tree per perspective, that's where the perspective aware merges come in. Hopefully Snappy plus the ability to remove older versions mitigates enough in reducing the required storage size. Preliminary tests look positive.