DSN L1 lookup and cuckoo-filters

Research
1

When we hit an L2 cache miss in DSN (can’t find a piece in farmer piece caches) we try to get a missing piece from other farmers’ archival storage (L1). Our initial design had a notion of “cuckoo filters” or “bloom filters” for the archival storage pieces that allowed us to know which peer contained the required piece. We exchanged this information between peers on the established connection and on each new sector plot. We pushed updates about newly plotted sectors only between currently connected peers. The set of connected peers is maintained by connected-peers protocol.

However, this approach had several disadvantages:

  • we need to push through the network relatively large portions of data (cuckoo-filters). The well-known and tested library use 1 byte per entry, which means 1MB of filter per 1TB of plot. And if we have 30 connected peers we need to push it 30 times on each connection. If we have a 1PB plot we’ll need to push 1GB, etc. Also, with large plots we run could run into memory issues on both local and remote peers.
  • cuckoo-filter and its analogs degrade their characteristics (false positives and negatives) after entry deletion.

There are multiple optimizations could be made:

  • recreate cuckoo-filter after some sector replotting rounds
  • persist large cuckoo-filters from connected peers to preserve RAM
  • create a more space-efficient version of the filter
  • maintain a collection of small and immutable filters
  • try to find and implement a perfect data structure with the following characteristics: space efficiency, low characteristics degradation after deletion operation, support of add/delete/(merge filters with different size) which to the best of my knowledge (arxiv, google, chatgpt) doesn’t exist at the moment.

Even if we manage to optimize the filter exchange - we get only a piece of knowledge from which exact peer from the currently connected we should ask.

Since it’s a relatively rare and expensive operation we removed the whole concept of filters and knowledge about other peers’ plots and query each peer from the connected peers set sequentially. Also, we already have a connection and we don’t occupy a new connection slot, it’s a cheap request if the peer doesn’t have it (it has its L1 piece indexes in the memory cache).
The downside of this approach is potentially a couple of dozens of unnecessary requests.

Related links:

1 Like
2

Thanks @shamil for this good summary! I feel that the new approach is effective. In order to reduce the number of unnecessary requests, we can try some simple yet efficient gossip algorithms such as the one proposed by Bernhard Haeupler.

3

Gossip is not really applicable here though

4

Each peer has a limited set of neighboring peers and pushes its data directly. We won’t benefit from gossiping when we have active connections to all peers from the set. And we don’t push filters beyond our limited peer set otherwise we will exceed both RAM and network bandwidth handling all the cuckoo-filters from the entire network.