linkrs_storage/edge/node_group/
address.rs

1//! Group and leaf-region address arithmetic plus density calibration.
2//!
3//! Pure functions over the locked address width: group/region mapping,
4//! address validation, and the calibrator-tree density model derived from
5//! the packed-CSR target.
6
7use linkrs_core::{StorageError, StorageResult};
8
9use super::super::mutable_csr::PACKED_CSR_DENSITY;
10
11/// Default address bits per node group: 12 bits cover 4096 rows.
12///
13/// Selection guidance: dense id spaces below 1M vertices keep the default;
14/// sparse wide spans prefer smaller widths to keep each materialized group
15/// dense, while huge dense tables may raise it to cut group counts. Width
16/// changes are offline only via `EdgeStore::reshard` followed by a
17/// checkpoint; see the group-width drill in `checkpoint/tests.rs`.
18pub const DEFAULT_NODE_GROUP_BITS: u32 = 12;
19/// Rows per leaf region inside a group. A default group holds 16 regions;
20/// region dirt and density merges operate at this granularity.
21pub const LEAF_REGION_ROWS: usize = 256;
22
23/// Group index for a global vertex id.
24pub fn group_id_for(vid: u32, group_bits: u32) -> usize {
25    (vid >> group_bits) as usize
26}
27
28/// First global vertex id covered by a group.
29pub fn group_base(group: usize, group_bits: u32) -> u32 {
30    (group as u32) << group_bits
31}
32
33/// Rows covered by one group.
34pub fn group_size(group_bits: u32) -> usize {
35    1usize << group_bits
36}
37
38/// Row address inside its group.
39pub fn local_vid(vid: u32, group_bits: u32) -> u32 {
40    vid & ((group_size(group_bits) as u32).wrapping_sub(1))
41}
42
43/// Validate the configured address width.
44pub fn validate_group_bits(group_bits: u32) -> StorageResult<()> {
45    if group_bits == 0 || group_bits > 20 {
46        return Err(StorageError::invalid_operation(format!(
47            "node_group_bits must be within 1..=20, got {}",
48            group_bits
49        )));
50    }
51    Ok(())
52}
53
54/// Leaf regions covering one group of `group_size` rows.
55pub fn regions_per_group(group_size: usize) -> usize {
56    group_size.div_ceil(LEAF_REGION_ROWS).max(1)
57}
58
59/// Leaf region owning a group-local row.
60pub fn region_id_for_local(local: u32) -> usize {
61    local as usize / LEAF_REGION_ROWS
62}
63
64/// Group-local `[start, end)` row window of one leaf region.
65pub fn region_local_range(region: usize, group_size: usize) -> (u32, u32) {
66    let start = (region * LEAF_REGION_ROWS).min(group_size) as u32;
67    let end = ((region + 1) * LEAF_REGION_ROWS).min(group_size) as u32;
68    (start, end)
69}
70
71/// Leaf-level density ceiling of the packed-CSR calibrator tree: leaf
72/// regions may pack full, higher levels grade down toward the packed target.
73pub const LEAF_HIGH_CSR_DENSITY: f32 = 1.0;
74
75/// Height of the density calibrator tree for one address width: group rows
76/// halve down to leaf regions, so the height is the group-bits minus the
77/// leaf-region-rows log2.
78pub fn calibrator_tree_height(group_bits: u32) -> u32 {
79    group_bits.saturating_sub(LEAF_REGION_ROWS.trailing_zeros())
80}
81
82/// Density ceiling for one calibrator-tree level: full at the leaf level,
83/// grading linearly down to the packed row target at the top. Levels above
84/// the top clamp to the packed target.
85pub fn calibrator_max_density(level: u32, tree_height: u32) -> f32 {
86    if level == 0 || tree_height == 0 {
87        return LEAF_HIGH_CSR_DENSITY;
88    }
89    let step = (LEAF_HIGH_CSR_DENSITY - PACKED_CSR_DENSITY) / tree_height as f32;
90    PACKED_CSR_DENSITY + step * tree_height.saturating_sub(level.min(tree_height)) as f32
91}
92
93/// Reserved tail gap for a region holding `live` entries at the packed
94/// density target. Empty regions hold no gap; gaps live at the region tail,
95/// never inside rows.
96pub fn region_tail_gap(live: usize) -> usize {
97    if live == 0 {
98        return 0;
99    }
100    ((live as f32 / PACKED_CSR_DENSITY).ceil() as usize).saturating_sub(live)
101}
linkrs_storage/edge/node_group/address.rs

linkrs_storage/edge/node_group/
address.rs
