meta_srv/procedure/drain_datanode/utils/
batch_aggregator.rs1use std::collections::{BTreeMap, btree_map};
16
17pub(crate) struct BatchAggregator<K, V> {
21 groups: BTreeMap<K, Vec<V>>,
22 batch_size: usize,
23 buffer_limit: usize,
24 buffered: usize,
25}
26
27impl<K: Ord + Clone, V> BatchAggregator<K, V> {
28 pub(crate) fn new(batch_size: usize, buffer_limit: usize) -> Self {
30 Self {
31 groups: BTreeMap::new(),
32 batch_size: batch_size.max(1),
33 buffer_limit: buffer_limit.max(1),
34 buffered: 0,
35 }
36 }
37
38 pub(crate) fn push(&mut self, key: K, item: V) -> Option<(K, Vec<V>)> {
41 let mut entry = match self.groups.entry(key) {
42 btree_map::Entry::Occupied(entry) => entry,
43 btree_map::Entry::Vacant(entry) => entry.insert_entry(Vec::new()),
44 };
45 entry.get_mut().push(item);
46 self.buffered += 1;
47 if entry.get().len() >= self.batch_size {
48 let batch = entry.remove_entry();
49 self.buffered -= batch.1.len();
50 return Some(batch);
51 }
52 if self.buffered >= self.buffer_limit {
53 let key = self
54 .groups
55 .iter()
56 .max_by_key(|(_, items)| items.len())?
57 .0
58 .clone();
59 let batch = self.groups.remove_entry(&key)?;
60 self.buffered -= batch.1.len();
61 return Some(batch);
62 }
63 None
64 }
65
66 pub(crate) fn flush(&mut self) -> Option<(K, Vec<V>)> {
68 let batch = self.groups.pop_first()?;
69 self.buffered -= batch.1.len();
70 Some(batch)
71 }
72
73 pub(crate) fn group(items: impl IntoIterator<Item = (K, V)>) -> Vec<(K, Vec<V>)> {
75 let mut groups: BTreeMap<K, Vec<V>> = BTreeMap::new();
76 for (key, item) in items {
77 groups.entry(key).or_default().push(item);
78 }
79 groups.into_iter().collect()
80 }
81}
82
83#[cfg(test)]
84mod tests {
85 use super::BatchAggregator;
86
87 #[test]
88 fn test_interleaved_groups_and_tails() {
89 let mut batches = BatchAggregator::new(2, 4);
90 assert_eq!(None, batches.push(1, 10));
91 assert_eq!(None, batches.push(2, 20));
92 assert_eq!(Some((1, vec![10, 11])), batches.push(1, 11));
93 assert_eq!(None, batches.push(1, 12));
94 assert_eq!(Some((1, vec![12])), batches.flush());
95 assert_eq!(Some((2, vec![20])), batches.flush());
96 assert_eq!(None, batches.flush());
97 assert_eq!(0, batches.buffered);
98 }
99
100 #[test]
101 fn test_bounds_buffer_with_many_groups() {
102 let mut batches = BatchAggregator::new(8, 3);
103 let mut emitted = Vec::new();
104 for i in 0..100 {
105 if let Some((_, batch)) = batches.push(i, i) {
106 assert!(batch.len() <= 8);
107 emitted.extend(batch);
108 }
109 assert!(batches.buffered < 3);
110 }
111 while let Some((_, batch)) = batches.flush() {
112 emitted.extend(batch);
113 }
114 emitted.sort_unstable();
115 assert_eq!((0..100).collect::<Vec<_>>(), emitted);
116 }
117
118 #[test]
119 fn test_evicts_largest_partial_group() {
120 let mut batches = BatchAggregator::new(10, 4);
121 assert_eq!(None, batches.push(1, 10));
122 assert_eq!(None, batches.push(2, 20));
123 assert_eq!(None, batches.push(1, 11));
124 assert_eq!(Some((1, vec![10, 11, 12])), batches.push(1, 12));
125 assert_eq!(Some((2, vec![20])), batches.flush());
126 }
127
128 #[test]
129 fn test_zero_and_singleton_limits() {
130 for (batch, buffer) in [(0, 4), (4, 0), (1, 1)] {
131 let mut batches = BatchAggregator::new(batch, buffer);
132 assert_eq!(Some((1, vec![42])), batches.push(1, 42));
133 assert_eq!(None, batches.flush());
134 }
135 }
136
137 #[test]
138 fn test_group_preserves_complete_groups() {
139 let input = (0..1200).map(|i| (i % 2, i));
140 let groups = BatchAggregator::group(input);
141 assert_eq!(2, groups.len());
142 for (key, values) in groups {
143 assert_eq!(
144 (0..1200).filter(|i| i % 2 == key).collect::<Vec<_>>(),
145 values
146 );
147 }
148 }
149}