time/roundtrip complexity of replication protocol

[dominictarr]

After spending quite a lot of time studying and thinking about replication protocols,
I see them as essentially as just being a remote dataset comparison.
This comparison may take advantage of structures inherent in the data being replicated,
or helpful a structure may be designed in to make remote comparison easy.
For example, scuttlebutt http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf uses append-only logs per peer, which means all that is required for remote comparison is to exchange a vector clock.
Bittorrent has a static set of blocks, known beforehand, this is exchanged as a bitfield.

scuttlebutt is O(Nodes) bandwidth and bittorrent is O(blocks) bandwidth, but both are O(1) for roundtrips. Since round-trips add a massive delay, I think it's very wise to keep the roundtrip complexity low.

Ipfs replicates a DAG. This is a somewhat more complex and interesting datastructure than scuttlebutt or bittorrent. From what is described in the draft paper, in ipfs each node requests a want list - the branches it wants to expand, which is requested and then sent.

This means the roundtrips required would vary widly with the structure of the DAG. in the worst case, you have a linked list, which would require a round trip for each item.
In general, I think the roundtrips will be something like O(depth) considering that the trees are user generated this could perform very badly in some cases, for example, a git repo has a very linked listy structure, so a large repo would go quite slow.

Some ideas for improving this, as discussed on irc etc

1. Some sort of flattening, or add index objects.
2. Maybe an append-only chain that serves as an index?
   When objects are added, the chain points to all of them.
   first you could replicate the chain (requested since the last known point)
   and then you'll know all the objects so from now on the dag is flat.
   this would require 2 round trips, which is still constant time.
3. Maybe eagerly expand objects. you request an object + a credit for the amount of data you
   want. the remote sends the object, plus objects that it links to. I notice that the
   current tree structure has hashes, names, and sizes. Maybe the sizes could be expanded to
   include branching factor? then you could eagerly expand smallish nodes that branch lots?
4. The client requests hashes + globbed paths. HASH/**/bar to request a set of objects.
   I think you'd also need to send something like to represent the objects you alread know.
   which could be, I know everything under X, to a depth of 10, but I want things from branch
   Y (but don't send me anything under X+10)

[jbenet]

Yep, the main plan right now is to do (1.) and (5.) below.

1. See "flattened tree" in the paper (S 3.6.8) for a discussion on how this would work. (basically can exploit putting / in link names. This is a weird hack that should probably be killed, as it changes users' expectations... but it does provide utility here. Alternative is to chose another delim for flattened links.
2. This is cool because it creates a massive index of everything. In practice this won't really work via the dht because of contention. And also because some content may be ephemeral by intent. What could work here is to construct an indexing object which works similarly to binary heap snapshotting and to encourage apps that write to the dag to use them. IMO, having a personal archive of all the things I want to keep (where storage is deduplicated with everyone in the world) is pretty powerful.
3. yeah this sounds pretty good.
4. globs may work on bitswap. On avg, it seems that nodes will tend to hold children of an object, so may be able to resolve the globs.
5. indexing objects (dag nodes with mainly links, so with little or no data) will be very small and can be cashed aggressively. This means that costs are significantly ammortized-- say the first load of a dagpage may be slow, but every subsequent traversal of the dag to a nearby dagpage will be pretty small.

[jbenet]

for future reference:

• https://botbot.me/freenode/dat/2014-12-13/?msg=27447852&page=1
• https://gist.github.com/jbenet/09618faa84388a58a588

% bitswap :1234
> Want <ref>
> Want <ref>/*
> Want <ref>/*/**
> Want <ref>..<ref2>
> Want <ref>^^^^
> Want <ref>~1000
> Want (<ref>~ROOT)/2 (or something for bisection)

[dysbulic]

A mechanism I used in Mimis are called "relative roots".

Almost all the directories have a ... ⇔ ../... link.

Root directories, however, have a ... ⇔ .

It allows consistent forward linking, so my pages have lots of .../style/main/css type references.

[jbenet]

for future ref: man gitrevisions