P2P substitution

[Mic92]

For https://clan.lol/ we might be interested in implementing some form of p2p binary cache substitution.
Ncps might be one candidate where this could be implemented, so we wanted to ask if this is a feature,
that you would be interested in having in your project. We would than think how we can implement it:
i.e. multiple ncps instances could start federating or there is some form of cache hierarchy (one global, multiple satellites)

[kalbasit]

@Mic92 I wasn't aware of clan.lol, it looks interesting. I don't mind adding this feature so long I get some help from your side, I'd be more than happy reviewing prs and testing it on my end...

... Off to learn more about clan.lol

Thanks!

[Kernald]

In the Kubernetes world, Spegel takes an interesting model - each node of a Kubernetes cluster runs a OCI registry shim that exposes the container images available locally to other nodes in the cluster. Meaning an image typically only gets pulled once from the internet - the rest gets pulled from other nodes. While it feels like a fairly distant model from what ncps (currently?) takes, it feels like an ideal model for clan.lol, at a glance.

[kalbasit]

In the Kubernetes world, Spegel takes an interesting model - each node of a Kubernetes cluster runs a OCI registry shim that exposes the container images available locally to other nodes in the cluster. Meaning an image typically only gets pulled once from the internet - the rest gets pulled from other nodes. While it feels like a fairly distant model from what ncps (currently?) takes, it feels like an ideal model for clan.lol, at a glance.

I don't think it's far.. In the past few weeks, I've been working hard changing/refactoring ncps to support other databases than sqlite and other storages such as s3; Keeping in mind this feature. I don't think at its current state (unreleased v0.6.0) it would take too much effort to make it support federation. Although, I would probably need to work on a design doc and present that to @Mic92 and clan.lol folks to get their comments and requirements before I go down that route... With that said, it's next on my list.

[kalbasit]

@Mic92 @Kernald here's a design doc I quickly put together based on what I was thinking to do with this: https://docs.google.com/document/d/1iXlgntP0QzZlRz3KqsRpATfMeK5Be1Tqm3RRRcypft4/edit?usp=sharing (please request comment access to add comments)

[Mic92]

Thanks a lot for working on a design. I am a bit sick at the moment so I will follow up later with looking at the design. For now just some random ideas:

• other datacenter oriented designs for software distribution often employed the BitTorrent protocol (i think Facebook… i remember windows updates are also distributed through a p2p protocol.). Now i don't know if this is a good idea for our workload - i assume that their server infrastructure is more homogeneous than what a nix cache looks like.
• @brianmcgee was playing around with bloomfilter for efficiently exchange what paths are in a different cache. Those would allow to make narinfo lookups very efficient without wasting storage doing ahead-of-time synchronization - of course that part very much depends on what you want to ncps for.

CCing some other people that have experience with distributed system design @astro @zimbatm

[zimbatm]

Can you define P2P a bit more closely? Is it:

• an open or closed network (as in; only approved people can join or not)
• is it on LAN only, or also on the Internet?
• do we expose everything that's on the machines, or only the pull-through content?
• is the replication active or passive?

A LAN only lazy pull implementation could be to add a Bonjour protocol for Nix binary cache (ncps and others). The clients keep track of what caches are available locally, and prioritize them for pulling new content (with lower timeouts). That might be the only two changes needed.

If you go over the Internet, then query latency becomes more important, and you might want to add a smart query protocol to allow querying multiple entries at once. Or have a gossip protocol to keep a local inventory of what each node has.

If you want full replications / mirrors, then it makes sense to extend the Nix cache protocol and add some sort of transaction log for new entries.

[brianmcgee]

@brianmcgee was playing around with bloomfilter for efficiently exchange what paths are in a different cache. Those would allow to make narinfo lookups very efficient without wasting storage doing ahead-of-time synchronization - of course that part very much depends on what you want to ncps for.

To expand on this, the idea is to compute a bloom filter of all the narinfo hashes in the cache. Until you run garbage collection, this is a purely additive process.

You can create smaller delta bloom filters with recent writes and merge them with the overall filter. Similarly, you can make these snapshots and delta filters available to other caches via push or pull, keeping federated caches in sync.

What this allows then is efficient negative lookup: when a cache is queried for something, it can locally determine which caches definitely do not have what it's looking for and only query the ones that might.

There's some nuance here, such as how frequently you spit out the delta filters and what's a tolerable sync lag. If you run a GC, you have to generate a fresh snapshot from scratch. I did some quick experiments with tuning the filter size but that would need more investigation.

Here's some more context: NixOS/nix#649 NixOS/nix#7221

There was also a recent issue I saw from @roberth that touched on this idea. There were some alternative filters suggested in the thread, but I can't find them.

[kalbasit]

Using bloom filters is a quite interesting idea to help find which cache has what you need. I'm wondering, however, how much of a benefit would this be if implemented in ncps alone.. I mean simple push to other ncps caches would help fill-in the cache. This would be a great benefit if implemented in other implementations as well, especially in something like cache.nixos.org so a cache doesn't need to preemptively pull everything needed locally but will not waste HTTP resources trying to figure out which caches has what it needs especially if your upstream caches list is large. In my case, I only have two configured so it's not a big deal to find what it needs...

[roberth]

issue

cache.nixos.org

• A Bloom filter to speed up all 404s NixOS/infra#776

Until you run garbage collection

Even during or after collection, the bloom filter can be used correctly as is. It would only cause a "redundant" 404 on the upstream cache and the latency of that. It's the same query that's needed for getting the real narinfo/realisation and the scenario is similar to false positives that are inherently part of this kind of probabilistic data structure.

When a significant fraction of the cache is collected, it's good to replace the filter, but not critical.

[Mic92]

Using bloom filters is a quite interesting idea to help find which cache has what you need. I'm wondering, however, how much of a benefit would this be if implemented in ncps alone.. I mean simple push to other ncps caches would help fill-in the cache. This would be a great benefit if implemented in other implementations as well, especially in something like cache.nixos.org so a cache doesn't need to preemptively pull everything needed locally but will not waste HTTP resources trying to figure out which caches has what it needs especially if your upstream caches list is large. In my case, I only have two configured so it's not a big deal to find what it needs...

I would be happy to also add support bloomfilter in niks3/harmonia.

[kalbasit]

I've been doing a deep dive into this problem space, and while bloom filters seem like the obvious choice, I've landed on a different approach after analyzing the constraints.

Why Not Bloom Filters?

The core issue is garbage collection. Bloom filters can't truly delete items—you can't unset bits because they might be shared with other valid entries. This creates two bad options:

1. Carry tombstone lists forever — Defeats the space efficiency that made blooms attractive
2. Periodically rebuild from scratch — Requires listing the entire S3 bucket to get ground truth

Note: ncps does have all narinfos stored in the database, so it could technically rebuild from there—but that's an implementation detail I don't want to bake into a generic solution.

For a homelab cache, listing S3 is fine. For cache.nixos.org with billions of objects (I'm not sure of the size actually but in 2023 Eelco said it's ~600M objects), it's prohibitively expensive. Since ncps aims to work at any scale, I want to avoid this architectural landmine.

The Alternative: HLSSI (Hybrid Log-Structured Sharded Index)

Instead of probabilistic bit arrays, store the actual hashes using Golomb-Rice compression. The key insight: sorted hashes have predictable gaps, and those gaps compress extremely well.

Space comparison (at 0.1% FPR):

• Bloom filter: ~14.4 bits/item
• Golomb-Rice: ~10-15 bits/item (depending on density)

Roughly equivalent space, but HLSSI gives us:

• ✅ Exact answers — No false positives, no HTTP verification needed
• ✅ Native deletion — Just a merge-sort during compaction
• ✅ Self-sufficient — Index never needs to query the storage backend

Architecture Summary

Layer 0: manifest.json     — Routing metadata, ~1KB
Layer 1: journal/*.log     — Append-only recent mutations (sub-second freshness)
Layer 2: shards/<prefix>.idx — Golomb-Rice encoded sorted hashes (bulk data)

Compaction is a pure function: new_index = old_index + additions - deletions. No S3 listing required for ongoing maintenance.

I've written up the full design as a draft RFC: https://gist.github.com/kalbasit/708a69403d83dac4133f5905ae4846f0

Would love feedback on it before I go ahead and file the RFC on NixOS.

[brianmcgee]

I like it 👍 I was never 100% happy about bloom filters since they didn't support deletions, I just never found a better structure.

[Mic92]

For cache.nixos.org, I think we could also have the index just being maintained for a certain time-window i.e. 3 years to keep the size manageable. Than the trade-off for downloading the index vs individual narinfos becomes better.

[Mic92]

@brianmcgee how many objects do we actually have in s3 just now?

[kalbasit]

How does hydra push to cache.nixos.org? I see the read path is CDN over S3 (as defined here). If we don't have a backend in front of S3, we'll have to implement this through a lambda triggered by S3 object changes.