hasher.rs (2737B)
1 use sha2::{Digest, Sha256}; 2 3 /// Pick `count` volumes for a key by hashing key+volume, sorting by score. 4 /// Same idea as minikeyvalue's key2volume — stable in volume name, not position. 5 pub fn volumes_for_key(key: &str, volumes: &[String], count: usize) -> Vec<String> { 6 let mut scored: Vec<(u64, &String)> = volumes 7 .iter() 8 .map(|v| { 9 let hash = Sha256::digest(format!("{key}:{v}").as_bytes()); 10 let score = u64::from_be_bytes(hash[..8].try_into().unwrap()); 11 (score, v) 12 }) 13 .collect(); 14 scored.sort_by_key(|(score, _)| *score); 15 scored 16 .into_iter() 17 .take(count) 18 .map(|(_, v)| v.clone()) 19 .collect() 20 } 21 22 #[cfg(test)] 23 mod tests { 24 use super::*; 25 26 #[test] 27 fn test_deterministic() { 28 let volumes: Vec<String> = (1..=3).map(|i| format!("http://vol{i}")).collect(); 29 let a = volumes_for_key("my-key", &volumes, 2); 30 let b = volumes_for_key("my-key", &volumes, 2); 31 assert_eq!(a, b); 32 } 33 34 #[test] 35 fn test_count_capped() { 36 let volumes: Vec<String> = (1..=2).map(|i| format!("http://vol{i}")).collect(); 37 let selected = volumes_for_key("key", &volumes, 5); 38 assert_eq!(selected.len(), 2); 39 } 40 41 #[test] 42 fn test_even_distribution() { 43 let volumes: Vec<String> = (1..=3).map(|i| format!("http://vol{i}")).collect(); 44 let mut counts = std::collections::HashMap::new(); 45 for i in 0..3000 { 46 let key = format!("key-{i}"); 47 let primary = &volumes_for_key(&key, &volumes, 1)[0]; 48 *counts.entry(primary.clone()).or_insert(0u32) += 1; 49 } 50 for (vol, count) in &counts { 51 assert!( 52 *count > 700 && *count < 1300, 53 "volume {vol} got {count} keys, expected ~1000" 54 ); 55 } 56 } 57 58 #[test] 59 fn test_stability_on_add() { 60 let volumes: Vec<String> = (1..=3).map(|i| format!("http://vol{i}")).collect(); 61 let mut volumes4 = volumes.clone(); 62 volumes4.push("http://vol4".into()); 63 64 let total = 10000; 65 let mut moved = 0; 66 for i in 0..total { 67 let key = format!("key-{i}"); 68 let before = &volumes_for_key(&key, &volumes, 1)[0]; 69 let after = &volumes_for_key(&key, &volumes4, 1)[0]; 70 if before != after { 71 moved += 1; 72 } 73 } 74 let pct = moved as f64 / total as f64 * 100.0; 75 assert!( 76 pct > 15.0 && pct < 40.0, 77 "expected ~25% of keys to move, got {pct:.1}%" 78 ); 79 } 80 81 #[test] 82 fn test_empty() { 83 assert_eq!(volumes_for_key("key", &[], 1), Vec::<String>::new()); 84 } 85 }