cloudflare / cloudflare/pingora

Consider Vec<Backend> over BTreeSet<Backend> in pingora::lb::selection::BackendSelection to preserve upstream order

Open
#109 3 comments 0 reactions 1 assignee Claimed by @andrewhavck View on GitHub
enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.