IPFS Repo - BlockStore directory sharding

[masylum]

I'm trying to implement fs-repo for js and I'm not really sure the spec reflects the current go implementation. This is how the blocks are stored right now in my machine (0.3.8-dev).

blocks/
├── 1220025c
│   └── 1220025cfbe6331dd3b9403dbcd9b4810149d2fef328c8f8445454d0e684acf350be.data
├── 122003ba
│   └── 122003baa5a30b05babad30b53ee3f4a6f967f82cc0e4cf3510a145145a926211d4b.data
├── 1220053b
│   └── 1220053b4dd1c32d8400f1588a36c57a567278bb4462d403e53dac5db8ce07d13d11.data
...

While in the spec directory partitioning looks like:

# locations of the blocks
.ipfs/blocks/1114/f6/23/e0ec7f8719fb14a18838d2a3ef4e550b5e53
.ipfs/blocks/1220/fe/38/9b55ea958590769f9046b0f7268bca90a92e4a9f45cbb30930f4bf89269d

[daviddias]

0.4.0 should respect whatever is defined on the spec and if the spec is missing something, now is a good time to add it, so that we can all trust the spec to create our implementations :) @whyrusleeping might have some thoughts though :)

[greglook]

In the Clojure blocks library the file-store implementation follows the spec, with three subdirectory levels. I'm definitely interested to hear if there are any changes I should be making to stay in sync.

[masylum]

oh! that's relevant to my interests @greglook.

[jbenet]

flatfs in go-ipfs ended up deviating from the spec. its my fault for not pressing for it -- or not updating the spec.

i think we can migrate go-ipfs to follow the 3 tiers. (ls-ing huge directories is annoying anyway. not all filesystems are good)

[jbenet]

@tv42 was there a strong reason you opted for single tiering instead of a larger fanout? i recall you mentioning it might be slower (more dirs to traverse?), but this likely varies by fs?

[greglook]

For filesystem-based stores with good performance you'll probably want to use something like Camlistore's diskpacked store (or the logical version, blobpacked) anyway.

[tv42]

@jbenet It really comes down to this: single level split is easier to understand and easier to program.

Typical Linux modern FS performs well all the way up to hundreds of thousands or even a few million files in one dir, and the current setting of 4-byte fanout (actual amount of entropy depending on whether the slash prefix actually gets stripped or not, that's been changed by others enough that I'm no longer clear on that) oughta work well enough up to tens of terabytes that something else becomes a problem first. I made the split size configurable, so people can fiddle with that, if needed.

https://github.com/ipfs/go-ipfs/blob/b9e8c001cf58b59eadea48cdb691c48924d44355/repo/fsrepo/fsrepo.go#L356-L364

Multi-level split only makes sense if the one-level split would result in the top level dir containing too many entries (once again, I'd expect >> 100k). By that time I expect you'll have other problems; then each directory ought to contain at least 100k items in it, leading to the total storage being easily over 100k * 100k * 256kB = 2PB.

Personally, I've seen affordable large storage only work well in JBOD mode, so the amount of data in a single flatfs is likely in the low tens of TB anyway for the near future. That's < 100M objects tops at 256kB per object, even a 256-way split brings that to ~400k objects per dir, which I expect to show no significant deterioration in performance (= even that split is wide enough). You'll suffer more from things like FS inode record keeping overhead than from the fact that it's a single level sharding.

@greglook That's yet another variation of what I've been calling arena storage. The decision to go with flatfs was because of the combo 1) it's simple 2) we can get it going fast. I agree arena storage can smoke it in performance, mostly because done right, it can manage disk syncs better.

[tv42]

As for the spec:

1. "N tiers", nothing specifies N as far as I can see
2. If N is a configured value (basically like the current flatfs prefixLen, but a/b/c/ instead of abc/, cannot change while there are objects stored), the current single-tier setup with a good prefixLen is just as good until the top-level dir gets too crowded. By which time, I want to take a photo of your hard drive.
3. If N is not a configured value but dynamic, lookups get costly as they need to probe all possible locations.
4. If N is not a configured value but dynamic, the spec has a possibility for object and prefix dir name collision.
5. Even if N is a configured value, for short object names the spec has a possibility for object and prefix dir name collision.