(NBS) *Prevent* noms sync from actively *hurting* chunk locality

[ghost]

#2880 focused on offering guarantees about good chunk locality (related chunks being stored near each other in NBS), but it's now clear that two mechanisms in noms are actively working against this goal: (1) writing over http and (2) sync.

While we work on a design for retaining and enforcing locality throughout noms (including over http & sync), I think there's some low hanging fruit which would be compatible with the existing wire protocol, and that is to just start with preventing writing over http from destroying locality.

If we can do this, at least we will accomplish the common case of writing to a remote server the first time having decent locality.

Right now writing to a remote server involves temporarily storing chunks in a ldb instances and then shipping them all over on commit. The trouble is that what the code currently does is store them in ldb ordered by ascending ref height and then ascending hash. This has the effect of essentially shuffling all chunks of a given height on their way over to the server.

So here's my idea: just for the case of writing to a remote noms server, simply buffer out chunks in the order they were written (e.g. to a file), and then send them up to the server in exactly that order. The in-process validation will already retain the one required wire invariant: that no chunk shall be written before the server has seen all referenced chunks.

Implementation idea for this: essentially use a local nbs store rather than ldb. As we are writing keep a in-memory list of hashes written. On commit, just read them out in that order (which will be ideal read-order for nbs) as we ship them over to the server.

If this works, I think something slightly more complicated, but similar could work for the case of sync.

cc @cmasone-attic

[cmasone-attic]

hmmm...I think this works, yes. There's a nagging concern about this in-memory list of hashes blowing up RAM, but it's probably OK to TODO that for now, yes?

[ghost]

Yup. I think todo is fine. Also, it might be literally just as much work to add a feature to nbs to just iterate all chunks in "store" (insertion) order

[ghost]

Now that I think about this more, it might actually have the happy side effect of improving the perf of writing over http (even if the server is backed by ldb) because the tmp ldb store is currently doing a ton of pointless compactions as we write.

[ghost]

Re-opened and modified the bug title to reflect what's left of this. I think sync still effectively randomizes chunks within each height level.

[ghost]

Here's a half an idea for this. Sync progressively writes chunks of lower & lower heights. That means as soon as a chunk of a given height X seen, we can learn nothing more about the locality of chunks of greater height. Thus, it seems reasonable to

-Keep of buffer of incoming chunks
-Record the lowest height seen
-When a chunk of height < lowest is encountered, flush all buffered.

This doesn't explain how we organize buffered yet, but it's a start.