kumo_prometheus/
sharded.rs

1use crossbeam_utils::CachePadded;
2use std::sync::atomic::AtomicUsize;
3use std::sync::atomic::Ordering::Relaxed;
4
5const SHARDS: usize = 256;
6
7struct AtomicCountAndSize {
8    count: AtomicUsize,
9    size: AtomicUsize,
10}
11
12impl AtomicCountAndSize {
13    const fn new() -> Self {
14        Self {
15            count: AtomicUsize::new(0),
16            size: AtomicUsize::new(0),
17        }
18    }
19}
20
21/// Sampled totals for live items.
22#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
23pub struct CountAndSize {
24    pub count: usize,
25    pub size: usize,
26}
27
28/// Reduces contention when counting live items and their total size across
29/// threads.
30///
31/// Updates are keyed by item identity, allowing different threads to add and
32/// remove an item without accumulating per-thread imbalances. Construction and
33/// updates never allocate memory.
34pub struct ShardedCountAndSize {
35    shards: [CachePadded<AtomicCountAndSize>; SHARDS],
36}
37
38impl Default for ShardedCountAndSize {
39    fn default() -> Self {
40        Self::new()
41    }
42}
43
44impl ShardedCountAndSize {
45    /// Creates an empty counter, suitable for static initialization.
46    pub const fn new() -> Self {
47        Self {
48            shards: [const { CachePadded::new(AtomicCountAndSize::new()) }; SHARDS],
49        }
50    }
51
52    #[inline]
53    fn shard_index(key: usize) -> usize {
54        // Allocation alignment can make the low address bits identical.
55        let mut bits = key as u64;
56        bits = (bits ^ (bits >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
57        bits = (bits ^ (bits >> 27)).wrapping_mul(0x94d049bb133111eb);
58        ((bits ^ (bits >> 31)) as usize) & (SHARDS - 1)
59    }
60
61    /// Adds an item. Use the same key and size when removing it.
62    ///
63    /// The live item count and combined size must not exceed `usize::MAX`.
64    /// Updates wrap on overflow.
65    #[inline]
66    pub fn add(&self, key: usize, size: usize) {
67        let shard = &self.shards[Self::shard_index(key)];
68        shard.count.fetch_add(1, Relaxed);
69        shard.size.fetch_add(size, Relaxed);
70    }
71
72    /// Removes a previously added item, using its original key and size.
73    #[inline]
74    pub fn sub(&self, key: usize, size: usize) {
75        let shard = &self.shards[Self::shard_index(key)];
76        shard.count.fetch_sub(1, Relaxed);
77        shard.size.fetch_sub(size, Relaxed);
78    }
79
80    /// Returns sampled totals, exact when updates are idle.
81    ///
82    /// Concurrent updates may make the count and size each overestimate or
83    /// underestimate the true value independently. Totals saturate at
84    /// `usize::MAX` instead of overflowing.
85    pub fn load(&self) -> CountAndSize {
86        self.shards
87            .iter()
88            .fold(CountAndSize::default(), |total, shard| CountAndSize {
89                count: total.count.saturating_add(shard.count.load(Relaxed)),
90                size: total.size.saturating_add(shard.size.load(Relaxed)),
91            })
92    }
93
94    /// Returns the sampled total size, with the same semantics as [`Self::load`].
95    pub fn load_size(&self) -> usize {
96        self.shards.iter().fold(0_usize, |total, shard| {
97            total.saturating_add(shard.size.load(Relaxed))
98        })
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105    use std::sync::atomic::AtomicBool;
106    use std::thread;
107
108    #[test]
109    fn count_and_size() {
110        let counter = ShardedCountAndSize::new();
111        counter.add(42, 100);
112        counter.add(17, 99);
113        k9::assert_equal!(
114            counter.load(),
115            CountAndSize {
116                count: 2,
117                size: 199
118            }
119        );
120        counter.sub(42, 100);
121        k9::assert_equal!(counter.load(), CountAndSize { count: 1, size: 99 });
122        counter.sub(17, 99);
123        k9::assert_equal!(
124            (counter.load(), counter.load_size()),
125            (CountAndSize::default(), 0)
126        );
127    }
128
129    #[test]
130    fn cross_thread_removal_and_reuse() {
131        let counter = ShardedCountAndSize::new();
132        for _ in 0..32 {
133            for key in 1..=64 {
134                counter.add(key, key);
135            }
136            thread::scope(|scope| {
137                for key in 1..=64 {
138                    let counter = &counter;
139                    scope.spawn(move || counter.sub(key, key));
140                }
141            });
142            k9::assert_equal!(
143                (counter.load(), counter.load_size()),
144                (CountAndSize::default(), 0)
145            );
146        }
147    }
148
149    #[test]
150    fn aligned_keys_use_all_shards() {
151        for alignment in [16, 4096, 65536] {
152            let mut seen = [false; SHARDS];
153            for key in 1..=8192 {
154                seen[ShardedCountAndSize::shard_index(key * alignment)] = true;
155            }
156            k9::assert_equal!(seen, [true; SHARDS]);
157        }
158    }
159
160    #[test]
161    fn aggregation_saturates() {
162        let counter = ShardedCountAndSize::new();
163        counter.shards[0].count.store(usize::MAX, Relaxed);
164        counter.shards[0].size.store(usize::MAX, Relaxed);
165        counter.shards[1].count.store(1, Relaxed);
166        counter.shards[1].size.store(1, Relaxed);
167        k9::assert_equal!(
168            (counter.load(), counter.load_size()),
169            (
170                CountAndSize {
171                    count: usize::MAX,
172                    size: usize::MAX
173                },
174                usize::MAX
175            )
176        );
177    }
178
179    #[test]
180    fn concurrent_reads_remain_bounded() {
181        let counter = ShardedCountAndSize::new();
182        let done = AtomicBool::new(false);
183        thread::scope(|scope| {
184            scope.spawn(|| {
185                while !done.load(Relaxed) {
186                    let value = counter.load();
187                    assert!(value.count <= 8);
188                    assert!(value.size <= 8 * 256);
189                }
190            });
191            let mut workers = Vec::new();
192            for worker in 1..=8 {
193                let counter = &counter;
194                workers.push(scope.spawn(move || {
195                    for _ in 0..100_000 {
196                        counter.add(worker * 4096, 256);
197                        counter.sub(worker * 4096, 256);
198                    }
199                }));
200            }
201            for worker in workers {
202                worker.join().unwrap();
203            }
204            done.store(true, Relaxed);
205        });
206        k9::assert_equal!(
207            (counter.load(), counter.load_size()),
208            (CountAndSize::default(), 0)
209        );
210    }
211}