Block check latency

Posted on

When implementing a backup system we may need the client to ask the server if it already has a certain block. There are several ways we can implement this in order to reduce latency impacts;

Option 1

  • Client sends block hash to server
  • Server replies Y/N
    • High latency impact

Option 2

  • Server sends client a list of all block hashes on server
  • Client is then free to stream in new blocks as fast as it can
    • No latency impact
    • Sensitive data release?
    • Large initial download?

For blocks averaging 4KB against a 1TB storage pool, using a 256-bit = 64-byte hash, that’s a 16GB download (infeasibly large). Increasing average block size to 64KB makes it a 1GB download - still infeasible even if the bloom filter is rsynced.

Option 3

  • Server sends a prebuilt bloom filter of all block hashes on server
  • Client can quickly stream new blocks that definitely don’t exist on server, and has to request for blocks that might exist on server
    • Since duplicate blocks are reasonably unlikely (dedup gives ~3% space improvement in typical scenario), this gets most of the performance benefit without much sensitive data release
    • Bloom filter size should be quite large to minimise false positives - but “quite large” depends on size of installation

For blocks averaging 4KB and a 5% false positive rate against a 1TB storage pool, we need a 200MB bloom filter. Increasing the average block size to 64KB makes it a 12MB download, probably feasible to perform on every backup or to cache for a while (client can update the cache themselves when submitting blocks!)

Option 4

  • Client builds local knowledge of remotely stored blocks
  • Client sends blocks to server regardless of whether server already has them
  • Server checks for block already existing but does not inform server
    • No sensitive data release
    • Negatively impacts bandwidth