flowblok’s blog
Last year, I wrote an article for ACM Queue describing an algorithm I co-invented for backend subsetting (and recently Netflix published that they’d adopted parts of it). This post is really just a footnote to that article, something which was originally included but had to be dropped due to word limits.
As a quick recap, to build our algorithm we start with Consistent Hashing and extend it to return a subset of backend tasks rather than just a single task (coined Consistent Subsetting). Ringsteady Subsetting is then a specific case of Consistent Subsetting that improves connection balance, by replacing the randomly chosen positions with positions from a low-discrepancy sequence.
The particular sequence we chose was the binary van der Corput sequence, and the article notes that one of the reasons is the ease of computing any individual element, but another reason is that it enables a particular optimisation.
The most straightforward way to implement this is to generate pairs of each backend’s index and position, and sort them by position. Here’s a Rust implementation1 (this uses backend scaling2, so corresponds to Figure 4c in the article):
// Copyright 2023 Google LLC.
// SPDX-License-Identifier: Apache-2.0
struct Backend {
/// The backend's index in the range [0, n)
index: usize,
/// Its position on the circle, as a fixed-point number
/// (i.e. usize::MAX / 2 is halfway around the circle)
position: usize,
}
impl Backend {
pub fn new(index: usize, position: usize) -> Self {
Backend { index, position }
}
}
fn ringsteady_naive(num_backends: usize, frontend_index: usize, subset_size: usize) -> Vec<usize> {
// Generate a vector of [index, position] for each backend.
let mut backends = Vec::new();
for backend_index in 0..num_backends {
let backend_position = backend_index.reverse_bits();
backends.push(Backend::new(backend_index, backend_position));
}
// Sort the vector by each backend's position.
backends.sort_by(|a, b| a.position.cmp(&b.position));
// Get position of this frontend on the circle as a float in the range [0, 1).
let frontend_unit_position = (frontend_index.reverse_bits() as f64) / 2f64.powi(64);
// Figure out how many backends this frontend needs to rotate by.
let rotation = (frontend_unit_position * (num_backends as f64)).ceil() as usize;
// Output the backend indices.
let mut subset = Vec::new();
for i in 0..subset_size {
subset.push(backends[(i + rotation) % num_backends].index);
}
subset
}
fn main() {
// OUTPUT:
// Frontend #0: [0, 4]
// Frontend #1: [1, 5]
// Frontend #2: [2, 1]
// Frontend #3: [3, 0]
// Frontend #4: [4, 2]
for m in 0..5 {
let subset = ringsteady_naive(6, m, 2);
println!("Frontend #{}: {:?}", m, subset);
}
}
Sorting these pairs is the most expensive part of this algorithm. Wouldn’t it be neat if we could side-step that and just write out the backends in the correct order?
The key insight is that if we have 2w backends (for some integer w), then the positions of our backends will be a bit-reversal permutation, which is an involution (i.e. reversing the bits of a number twice gives the same number). This means that not only does reversing the bits give us the position for a backend index, it also gives us the backend index for a position. For example, here’s w = 3:
| Backend Index | Position | Position | Backend Index | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 1 | 4 | 1 | 4 | |
| 2 | 2 | 2 | 2 | |
| 3 | 6 | 3 | 6 | |
| 4 | 1 | 4 | 1 | |
| 5 | 5 | 5 | 5 | |
| 6 | 3 | 6 | 3 | |
| 7 | 7 | 7 | 7 |
To extend this to any number of backends N, we just need to find the smallest integer w such that N ≤ 2w, iterate over the positions [0, 2w), reversing each position (as a w bit number) to get the backend index at that position, skipping any backend index that isn’t in [0, N).
Here’s what that looks like in Rust:
// Copyright 2023 Google LLC.
// SPDX-License-Identifier: Apache-2.0
fn ringsteady_linear_time(num_backends: usize, frontend_index: usize, subset_size: usize) -> Vec<usize> {
// Generate a vector of backend indices in the correct order.
let mut backends = Vec::new();
let num_positions = num_backends.next_power_of_two();
let w = num_positions.trailing_zeros();
for backend_position in 0..num_positions {
let backend_index = backend_position.reverse_bits() >> (usize::BITS - w);
if backend_index < num_backends {
backends.push(backend_index);
}
}
// Get position of this frontend on the circle as a float in the range [0, 1).
let frontend_unit_position = (frontend_index.reverse_bits() as f64) / 2f64.powi(64);
// Figure out how many backends this frontend needs to rotate by.
let rotation = (frontend_unit_position * (num_backends as f64)).ceil() as usize;
// Output the backend indices.
let mut subset = Vec::new();
for i in 0..subset_size {
subset.push(backends[(i + rotation) % num_backends]);
}
subset
}
fn main() {
// OUTPUT:
// Frontend #0: [0, 4]
// Frontend #1: [1, 5]
// Frontend #2: [2, 1]
// Frontend #3: [3, 0]
// Frontend #4: [4, 2]
for m in 0..5 {
let subset = ringsteady_linear_time(6, m, 2);
println!("Frontend #{}: {:?}", m, subset);
}
}
It’s fairly straightforward to show that 2w < 2N (if it wasn’t, there would be a smaller valid choice of w), so the time complexity is linear in N. It’s also much faster in practice (even for small N), since we avoid the memory read/writes from swapping items in the sort algorithm.
Disclaimer: Any opinions stated here are my own, and not necessarily shared by my employer (Google).
-
I have preferred readability over performance or idiomatic code in these snippets, in the hope that it will be understandable to readers unfamiliar with Rust. For instance, there is no need for floating-point when calculating the frontend rotation, but I couldn’t figure out how to do that without distracting amounts of boilerplate. ↩
-
It’s possible to use this optimization without backend scaling, but it made the sample code too verbose for this blog post. ↩