cloudflare / cloudflare/pingora
Consider Vec<Backend> over BTreeSet<Backend> in pingora::lb::selection::BackendSelection to preserve upstream order
- Dominant language
- Rust
- Stars
- 27.4k
- Forks
- 1.7k
- Avg merge
- 6h 22m
- Merged PRs (30d)
- 3
Description
## What is the problem your feature solves, or the need it fulfills?
I have a usecase, where the selected backend/upstream is dependent on the order of some values in a config file among other things. Currently, the backends are given to the `BackendSelection` as a `&BTreeSet`, which changes the order of the backends.
## Describe the solution you'd like
My first instinct was to change said `&BTreeSet` to `&Vec` in the entirety of the load balancing code, however that might get expensive for the insertions and deletions in the `Static` `ServiceDiscovery`.
## Describe alternatives you've considered
I don't know any data structure of the top of my head that ticks all the boxes (fast insert, fast remove, fast lookup and order preserving), but a hybrid approach, where only parts are changed to use `Vec` instead of `BTreeSet` might be possible. That should only incur a one-time penalty during startup. However, since `BackendSelection` is nested fairly deeply within the load balancing code, that might not be possible as almost everything else in the load balancing crate appears to be handling `BTreeSet`s with the sole purpose of changing the `BackendSelection`. Especially the `try_from_iter` should be able to preserve the upstream order, but that would imply a change of the `Backends` struct, because a `Backends` struct does hold the `BTreeSet` of backends.
Currently, the only way around that issue I can see is to basically recreate most of the load balancing crate, but with `Vec` instead of `BTreeSet`
Contributor guide
Assessment
This issue has not been assessed yet.