Universal chunk/block size

[emizzle]

The idea of universal chunk sizes was brought up in a discussion around the introduction of an LRU cache in codex-storage/nim-codex#50. The issue arose when discussing if a chunk size should be configurable on the command line.

If nodes need to be be able to configure their cache size (in terms of max memory used for caching), and considering that nodes need to be able to store blocks in a cache, the maximum block size will need to be known such that the number of allowed blocks in a cache can be determined. This is likely going to require a universal chunk/block size across the dagger/codex network, otherwise caching becomes more difficult to solve and likely less performant, because the caches will need to have their own internal chunking rules or continually resize themselves on every put/delete operation.

An optimal universal chunk size may need to be determined over the lifetime of a live network based on empirical evidence.

[Menduist]

cc @cskiraly to give more background on the proof side of things

Obviously, the issue with fixed block size N is that storing data of size 1, N+1, N2+1, N3+1 etc becomes wildly inefficient, since you store (and pay for) N-1 bytes for nothing
So you have to keep N pretty small, which incurs more overhead for big files, and have to find a balance

If we can have a fixed max-size, but a dynamic size, that would be ideal. I don't think the LRU would stop us from doing so? Seems to me we can easily do something like (pseudo code):

type
  SizedLru[K, V] = ref object
    fixedLru: LruCache[K, V]
    capacity: int
    size: int

proc add[K, V](l: SizedLru[K, V], key: K, val: V) =
  k.fixedLru.add(key, val)
  k.size.inc(val.len)
  while k.size > k.capacity: k.removeLeastUsed() # should also update `k.size`

proc remove[K, V](l: SizeLru[K, V], key: K) =
  k.size.dec(l[key].len)
  k.fixedLru.remove(key)

add is no longer O(1), but it stays between O(1) and O(N) (N being max block size), so it should be reasonable

Again, having fixed block size would indeed simplify a lot of things, but as long as nothing is blocking having dynamic one, imo we should aim for the dynamic sized blocks. (maybe not in the mvp though)

[cskiraly]

It is a good question whether chunks should be of fixed size, of a fixed maximum size, or of arbitrary size (did I miss any option?)

I think we should first clarify what chunks are here, because we are using chunk as the unit at which data is stored, addressed, and transmitted in the system. That coupling of functionality means chunk size influences lots of things. If chunks are also the unit of erasure coding, we are adding one more to those constraints.

[emizzle]

The LRU cache PR has been updated to allow for dynamically sized blocks: codex-storage/nim-codex#50. We used the ideas above as a starter, thank you!

[Menduist]

Another option could be multiple possible fixed size, eg only power of two increments
Not sure if it make sense