use super::slots::SLOTS;
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Planned {
pub(crate) node: usize,
pub(crate) slots: Option<(u16, u16)>,
pub(crate) replicates: Option<usize>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Note {
Slots(usize, u16, u16),
Replica(usize, usize),
ExtraReplicas,
}
pub(crate) fn interleave(hosts: &[&[u8]]) -> Vec<usize> {
let mut groups: Vec<(&[u8], Vec<usize>)> = Vec::new();
for (i, host) in hosts.iter().enumerate() {
match groups.iter_mut().find(|(h, _)| h == host) {
Some((_, members)) => members.push(i),
None => groups.push((host, vec![i])),
}
}
let longest = groups.iter().map(|(_, m)| m.len()).max().unwrap_or(0);
(0..longest)
.flat_map(|row| groups.iter().filter_map(move |(_, m)| m.get(row).copied()))
.collect()
}
pub(crate) fn slot_range(i: usize, masters: usize) -> (u16, u16) {
let per = SLOTS as f64 / masters as f64;
let last = |k: usize| ((k + 1) as f64 * per - 1.0).round() as u16;
let first = if i == 0 { 0 } else { last(i - 1) + 1 };
let end = if i + 1 == masters { (SLOTS - 1) as u16 } else { last(i) };
(first, end)
}
pub(crate) fn plan(hosts: &[&[u8]], replicas: usize) -> (Vec<Planned>, Vec<Note>) {
let order = interleave(hosts);
let masters_count = hosts.len() / (replicas + 1);
let (masters, rest) = order.split_at(masters_count.min(order.len()));
let mut notes = Vec::new();
let mut planned: Vec<Planned> = Vec::new();
for (i, &m) in masters.iter().enumerate() {
let (a, b) = slot_range(i, masters_count);
notes.push(Note::Slots(i, a, b));
planned.push(Planned { node: m, slots: Some((a, b)), replicates: None });
}
let mut spare: Vec<usize> = rest.iter().skip(1).chain(rest.first()).copied().collect();
let mut assign = |master: usize, spare: &mut Vec<usize>, notes: &mut Vec<Note>| {
let pick = spare.iter().position(|&n| hosts[n] != hosts[master]).unwrap_or(0);
let replica = spare.remove(pick);
notes.push(Note::Replica(replica, master));
planned.push(Planned { node: replica, slots: None, replicates: Some(master) });
};
for &m in masters {
for _ in 0..replicas {
if !spare.is_empty() {
assign(m, &mut spare, &mut notes);
}
}
}
if !spare.is_empty() {
notes.push(Note::ExtraReplicas);
for &m in masters.iter().cycle().take(spare.len()) {
assign(m, &mut spare, &mut notes);
}
}
planned.sort_by_key(|p| p.node);
(planned, notes)
}
pub(crate) fn affinity_score(hosts: &[&[u8]], planned: &[Planned]) -> (usize, usize) {
let (mut with_master, mut together) = (0, 0);
for p in planned {
let Some(m) = p.replicates else { continue };
with_master += usize::from(hosts[p.node] == hosts[m]);
together += planned
.iter()
.filter(|q| {
q.node > p.node && q.replicates == Some(m) && hosts[q.node] == hosts[p.node]
})
.count();
}
(with_master, together)
}
pub(crate) fn optimize(hosts: &[&[u8]], planned: &mut [Planned]) {
let score = |p: &[Planned]| {
let (a, b) = affinity_score(hosts, p);
a * 10000 + b
};
let replicas: Vec<usize> =
(0..planned.len()).filter(|&i| planned[i].replicates.is_some()).collect();
let mut best = score(planned);
let mut improved = true;
while improved && best > 0 {
improved = false;
for (x, &i) in replicas.iter().enumerate() {
for &j in &replicas[x + 1..] {
let (a, b) = (planned[i].replicates, planned[j].replicates);
if a == b {
continue;
}
(planned[i].replicates, planned[j].replicates) = (b, a);
let now = score(planned);
if now < best {
best = now;
improved = true;
} else {
(planned[i].replicates, planned[j].replicates) = (a, b);
}
}
}
}
}
#[cfg(test)]
mod tests {
use super::{Note, affinity_score, interleave, optimize, plan, slot_range};
#[test]
fn slots_are_split_as_evenly_as_rounding_allows() {
let ranges = |n| (0..n).map(|i| slot_range(i, n)).collect::<Vec<_>>();
assert_eq!(ranges(3), [(0, 5460), (5461, 10922), (10923, 16383)]);
assert_eq!(
ranges(5),
[(0, 3276), (3277, 6553), (6554, 9829), (9830, 13106), (13107, 16383)]
);
assert_eq!(ranges(7)[2..4], [(4681, 7021), (7022, 9361)]);
}
fn replicas_of(hosts: &[&[u8]], replicas: usize) -> Vec<(usize, usize)> {
plan(hosts, replicas)
.1
.into_iter()
.filter_map(|n| if let Note::Replica(r, m) = n { Some((r, m)) } else { None })
.collect()
}
#[test]
fn replicas_are_offered_in_the_order_redis_cli_announces() {
let one: &[&[u8]] = &[&b"a"[..]; 8];
assert_eq!(replicas_of(&one[..6], 1), [(4, 0), (5, 1), (3, 2)]);
assert_eq!(replicas_of(&one[..7], 1), [(4, 0), (5, 1), (6, 2), (3, 0)]);
assert_eq!(replicas_of(one, 1), [(5, 0), (6, 1), (7, 2), (4, 3)]);
let (l, i): (&[u8], &[u8]) = (b"localhost", b"127.0.0.1");
assert_eq!(interleave(&[l, l, l, i, i, i]), [0, 3, 1, 4, 2, 5]);
assert_eq!(replicas_of(&[l, l, l, i, i, i], 1), [(5, 0), (2, 3), (4, 1)]);
assert_eq!(replicas_of(&[l, i, l, i, l, i, i], 1), [(5, 0), (4, 1), (6, 2), (3, 0)]);
}
#[test]
fn optimizing_swaps_only_when_it_helps() {
let (a, b): (&[u8], &[u8]) = (b"a", b"b");
let hosts = [a, b, a, b];
let (mut planned, _) = plan(&hosts, 1);
assert_eq!(affinity_score(&hosts, &planned), (0, 0));
planned[2].replicates = Some(0);
planned[3].replicates = Some(1);
optimize(&hosts, &mut planned);
assert_eq!(affinity_score(&hosts, &planned), (0, 0));
let same: &[&[u8]] = &[a; 6];
let (mut planned, _) = plan(same, 1);
let before = planned.clone();
optimize(same, &mut planned);
assert_eq!(planned, before);
}
}