kumo_prometheus/
sharded.rs1use 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#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
23pub struct CountAndSize {
24 pub count: usize,
25 pub size: usize,
26}
27
28pub 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 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 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 #[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 #[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 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 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}