use std::cmp::Ordering;
use xxhash_rust::xxh3::xxh3_64_with_seed;
pub(crate) const SCAN_WINDOWS: usize = 256;
const WINDOW_SHIFT: u32 = 56;
#[inline]
pub(crate) fn key_hash(key: &[u8], seed: u64) -> u64 {
xxh3_64_with_seed(key, seed)
}
#[inline]
pub(crate) fn shard_for_hash(h: u64, shard_count: usize) -> usize {
((h as u128 * shard_count as u128) >> 64) as usize
}
pub(crate) fn overlapping_shards(
planner: &[usize],
planner_count: usize,
real_count: usize,
) -> crate::error::DbResult<Vec<usize>> {
if planner_count == 0 || real_count == 0 || planner.iter().any(|&p| p >= planner_count) {
return Err(crate::error::DbError::Internal(
"invalid segmented shard topology",
));
}
let mut real = Vec::new();
for &p in planner {
let (lo, hi) = shard_range(p, planner_count);
real.extend(shard_for_hash(lo, real_count)..=shard_for_hash(hi, real_count));
}
real.sort_unstable();
real.dedup();
Ok(real)
}
pub(crate) fn shard_range(shard: usize, shard_count: usize) -> (u64, u64) {
debug_assert!(shard < shard_count);
let n = shard_count as u128;
let lo = ((shard as u128) << 64).div_ceil(n);
let hi = ((shard as u128 + 1) << 64).div_ceil(n) - 1;
(lo as u64, hi as u64)
}
#[inline]
#[cfg(test)]
pub(crate) fn window_of(h: u64) -> usize {
(h >> WINDOW_SHIFT) as usize
}
pub(crate) fn window_range(window: usize) -> (u64, u64) {
debug_assert!(window < SCAN_WINDOWS);
let lo = (window as u64) << WINDOW_SHIFT;
(lo, lo | ((1u64 << WINDOW_SHIFT) - 1))
}
#[inline]
pub(crate) fn filter_partition(h: u64, bits: u8) -> usize {
if bits == 0 {
0
} else {
(h >> (64 - u32::from(bits))) as usize
}
}
pub(crate) fn partition_bits_for(keys: u64, target: u64, max_bits: u8) -> u8 {
let target = target.max(1);
let mut bits = 0u8;
while bits < max_bits && keys.div_ceil(1u64 << bits) > target {
bits += 1;
}
bits
}
#[inline]
pub(crate) fn cmp_hk(ah: u64, ak: &[u8], bh: u64, bk: &[u8]) -> Ordering {
ah.cmp(&bh).then_with(|| ak.cmp(bk))
}
#[cfg(test)]
mod tests {
use super::*;
use std::cmp::Ordering;
fn splitmix(state: &mut u64) -> u64 {
*state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = *state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
const SHARD_COUNTS: [usize; 7] = [1, 2, 3, 7, 16, 64, 255];
#[test]
fn overlapping_shards_cover_edges_and_nondivisible_topologies() {
for planner_count in SHARD_COUNTS {
for real_count in SHARD_COUNTS {
for p in 0..planner_count {
let real = overlapping_shards(&[p, p], planner_count, real_count).unwrap();
assert!(real.windows(2).all(|w| w[0] < w[1]));
let (lo, hi) = shard_range(p, planner_count);
let mut hashes = vec![
0,
u64::MAX,
lo,
hi,
lo.saturating_sub(1),
hi.saturating_add(1),
];
for r in 0..real_count {
let (a, b) = shard_range(r, real_count);
hashes.extend([a, b, a.saturating_sub(1), b.saturating_add(1)]);
}
for h in hashes {
if (lo..=hi).contains(&h) {
assert!(
real.contains(&shard_for_hash(h, real_count)),
"P={planner_count} R={real_count} p={p} h={h}"
);
}
}
}
}
}
assert_eq!(
overlapping_shards(&[2, 0, 2], 3, 7).unwrap(),
vec![0, 1, 2, 4, 5, 6]
);
for (shards, p, r) in [(&[0][..], 0, 3), (&[0][..], 3, 0), (&[3][..], 3, 7)] {
assert!(overlapping_shards(shards, p, r).is_err());
}
}
#[test]
fn routing_is_monotone_in_the_hash() {
let mut state = 7u64;
for shard_count in SHARD_COUNTS {
let mut hashes: Vec<u64> = (0..10_000).map(|_| splitmix(&mut state)).collect();
hashes.extend([0, 1, u64::MAX - 1, u64::MAX]);
hashes.sort_unstable();
let mut previous = 0usize;
for h in hashes {
let shard = shard_for_hash(h, shard_count);
assert!(shard < shard_count);
assert!(shard >= previous, "routing went backwards at {h:#x}");
previous = shard;
}
}
}
#[test]
fn extreme_hashes_route_to_the_first_and_last_bucket() {
for shard_count in SHARD_COUNTS {
assert_eq!(shard_for_hash(0, shard_count), 0);
assert_eq!(shard_for_hash(u64::MAX, shard_count), shard_count - 1);
}
assert_eq!(window_of(0), 0);
assert_eq!(window_of(u64::MAX), SCAN_WINDOWS - 1);
for bits in 0..=16u8 {
assert_eq!(filter_partition(0, bits), 0);
assert_eq!(filter_partition(u64::MAX, bits), (1usize << bits) - 1);
}
}
#[test]
fn shard_range_agrees_with_routing_at_both_edges() {
for shard_count in SHARD_COUNTS {
for shard in 0..shard_count {
let (lo, hi) = shard_range(shard, shard_count);
assert!(lo <= hi);
assert_eq!(shard_for_hash(lo, shard_count), shard);
assert_eq!(shard_for_hash(hi, shard_count), shard);
if lo > 0 {
assert_eq!(shard_for_hash(lo - 1, shard_count), shard - 1);
}
if hi < u64::MAX {
assert_eq!(shard_for_hash(hi + 1, shard_count), shard + 1);
}
}
assert_eq!(shard_range(0, shard_count).0, 0);
assert_eq!(shard_range(shard_count - 1, shard_count).1, u64::MAX);
}
}
#[test]
fn windows_tile_the_hash_space() {
let mut expected_lo = 0u64;
for window in 0..SCAN_WINDOWS {
let (lo, hi) = window_range(window);
assert_eq!(lo, expected_lo);
assert_eq!(window_of(lo), window);
assert_eq!(window_of(hi), window);
expected_lo = hi.wrapping_add(1);
}
assert_eq!(expected_lo, 0, "the last window must end at u64::MAX");
}
#[test]
fn partition_bits_keep_the_average_under_the_target() {
assert_eq!(partition_bits_for(0, 524_288, 16), 0);
assert_eq!(partition_bits_for(524_288, 524_288, 16), 0);
assert_eq!(partition_bits_for(524_289, 524_288, 16), 1);
assert_eq!(partition_bits_for(25_920_000, 524_288, 16), 6);
assert_eq!(partition_bits_for(u64::MAX, 1, 16), 16);
}
#[test]
fn order_is_hash_first_then_key_bytes() {
assert_eq!(cmp_hk(1, b"zz", 2, b"aa"), Ordering::Less);
assert_eq!(cmp_hk(2, b"aa", 2, b"ab"), Ordering::Less);
assert_eq!(cmp_hk(2, b"ab", 2, b"ab"), Ordering::Equal);
assert_eq!(cmp_hk(2, &[0x7f], 2, &[0x80]), Ordering::Less);
}
#[test]
fn the_seed_changes_the_hash() {
let key = [7u8; 32];
assert_ne!(key_hash(&key, 1), key_hash(&key, 2));
assert_eq!(key_hash(&key, 1), key_hash(&key, 1));
}
}