Skip to main content

meta_srv/procedure/drain_datanode/utils/
batch_aggregator.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::collections::{BTreeMap, btree_map};
16
17/// Groups items by key while bounding both batch size and total buffered items.
18/// Full groups are emitted immediately; at the buffer limit the largest partial
19/// group is emitted. Equal-sized groups are ordered by key.
20pub(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    /// Creates an aggregator. Zero limits behave as one, emitting each item immediately.
29    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    /// Adds an item and returns a full group, or the largest group at the buffer limit.
39    /// The returned key can differ from the input key when a partial group is emitted.
40    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    /// Removes one remaining group, including its key, until the buffer is empty.
67    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    /// Groups a finite input without splitting groups or imposing a streaming buffer limit.
74    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}