Proposal: ordered_set backend for duplicate Registry

[studzien]

Not sure if an issue is the right place to discuss this — happy to move the conversation elsewhere if needed.

Context

At Whatnot we use Phoenix.PubSub (backed by Registry) for livestreams. In #14654 we added {:duplicate, :key} partitioning which helped when we had many small livestreams, but it doesn't help with large ones (as discussed in the PR) — all subscribers for a key still end up in one duplicate_bag partition.

We hit a concrete problem: at a certain leave rate from a large livestream, the PID partition GenServer's message queue runs away because each :ets.match_delete/2 on the duplicate_bag has to scan all entries for that key to find the ones belonging to the leaving process. The partition can't keep up.

Idea

Use an ordered_set ETS table with composite keys {key, pid, counter} instead of duplicate_bag with {key,{pid, value}}. Since ordered_set sorts entries, all entries for a {key, pid} prefix are adjacent in the tree, so unregistering only touches that process's entries instead of scanning the whole key.

Combined with key-based partitioning (so lookup hits one partition, not all of them).

A PoC implementation and benchmarks are available at: https://github.com/studzien/elixir/tree/registry/duplicate-ordered-set

In our simulated load tests the lookup time increase was not noticeable in our workload and we no longer saw the queue runaway issue.

Benchmark results

Hot key workload — all N entries under a single key, 16 partitions, duplicate = pid-partitioned duplicate_bag, ordered = key-partitioned ordered_set:

Lookup

N	duplicate	ordered
100	4.0 μs	6.4 μs	ordered 1.6x slower
1,000	29.5 μs	67.3 μs	ordered 2.3x slower
10,000	315 μs	404 μs	ordered 1.3x slower
1,000,000	149 ms	94.9 ms	ordered 1.6x faster

Ordered is slower at small N due to :ets.select/2 vs :ets.lookup_element/3. The gap closes as N grows, and at 1M ordered wins because it hits one partition instead of sixteen.

Unregister

N	duplicate	ordered
100	2.9 μs	3.3 μs	~tied
1,000	4.1 μs	3.6 μs	ordered 1.1x faster
10,000	14.7 μs	4.0 μs	ordered 3.7x faster
1,000,000	5.1 ms	5.4 μs	ordered 940x faster

This is the main win. At 1M entries unregister goes from 5ms to 5μs — this is what causes the queue runaway in the partition GenServer with duplicate_bag.

Tradeoffs

Lookup is ~1.5-2x slower at small to medium scale. Unregistration and crash cleanup are dramatically faster at scale. For our use case (large channels, high join/leave rate) the tradeoff is clearly worth it.

Next steps

We're happy to work on this and prepare a production-ready version of the code, but would appreciate some guidance on structuring the solution. The current Registry implementation already has a fair amount of branching for unique, duplicate partitioned by pid, and duplicate partitioned by key — adding another backend on top of that makes the code harder to follow. Would appreciate thoughts on whether the current approach (more case branches) is acceptable, or if there's a preferred way to organize this (e.g., separate modules per backend, behaviour, etc.).

Related: #14654

[josevalim]

Quick question: should we change the duplicate key to always use ordered_set, or do you think there are still benefits for one over the other for duplicate key-partitions?

[josevalim]

Ignore me, I see the new solution uses pid partitioning.

[studzien]

Hmm, maybe I didn't commit everything. I was intending to use key partitioning at the end of the day.
One of the workarounds I tried with duplicate_bag for the issue we've seen is just to increase the number of partitions. But that's not future proof for us, I think, and there's a penalty doing N :ets.lookups.

That's a very valid question I think. The {:duplicate, :key} on duplicate_bag might no longer make sense. At least not for the use case I intended this (I wanted to avoid N serializations of the Phoenix event).

[josevalim]

Another approach is to make this a separate option that applies for both {:duplicate, :key} and {:duplicate, :pid}, which is to say forbid_duplicate_key_pid: true. Then we can use ordered_set, without the counter, and use it to reject duplicate registrations. But it may make things more complicated because now you have to test it over duplicate-key and duplicate-pid.

Anyway, those are my initial thoughts, let me know how you think is best to proceed!

[studzien]

Right now, I think that changing the implementation for {:duplicate, :key} to an ordered set is the best idea.
It makes sense for a workload with many small-to-midsize keys. For hotkeys (like in the example above), it's even more susceptible to the queue runaway issue when unregistering processes.

So for these we've been using {:duplicate, :pid} approach with a fine-tuned number of partitions, so we don't pay too much performance penalty on serialization, but also the complexity of handling a leave hasn't grown yet.

I think ordered_set has the potential to be a pretty good universal solution for various workloads (at least that's what my experiments with our production-like traffic suggest), so I'm okay with changing the current {:duplicate, :key} implementation.
My only concern is whether someone has already used it and relied on the internal representation or on lookup timings (which will get a bit worse due to the logarithmic complexity).

[josevalim]

I believe it is fine to have folks reassess the performance for duplicate key if they already adopted it and we collect their feedback accordingly.

[josevalim]

The big question is if you see any value of using {:duplicate, :key} if we have {:duplicate, :ordered}. If we can't show benefits for {:duplicate, :key} in any meaningful benchmark, then changing {:duplicate, :key} is the way to go.

[studzien]

Makes sense. Let me think about it and figure out if there's a scenario where {:duplicate, :key} will be much more beneficial than using :ordered

[josevalim]

Hi @studzien! Just a heads up that Elixir v1.20 is coming in May (towards the end) and I'd love to have this as part of that release. :)

[studzien]

Thanks for the heads up!
I will prioritize this and have something up next week!