Skip to main content

meta_srv/procedure/drain_datanode/utils/
scan.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::fmt;
16
17use common_meta::DatanodeId;
18use common_meta::key::TableMetadataManagerRef;
19use common_meta::key::datanode_table::DatanodeTableValue;
20use common_meta::key::table_route::TableRouteValue;
21use common_meta::rpc::router::RegionRoute;
22use common_meta::wal_provider::extract_topic_from_wal_options;
23use futures::TryStreamExt;
24use futures::stream::BoxStream;
25use snafu::ResultExt;
26use store_api::storage::RegionId;
27
28use crate::error::{self, Result};
29use crate::procedure::drain_datanode::utils::batch_aggregator::BatchAggregator;
30
31/// A paused scan owns at most a metadata page, one table's routes/WAL options,
32/// and the bounded topic accumulator. It never collects all of the node's regions.
33pub(crate) struct RegionScan {
34    /// Metadata source used for both table enumeration and authoritative route reads.
35    metadata: TableMetadataManagerRef,
36    /// Datanode whose leaders and followers are being scanned.
37    node_id: DatanodeId,
38    /// Remaining datanode table entries, fetched page by page.
39    tables: BoxStream<'static, common_meta::error::Result<DatanodeTableValue>>,
40    /// WAL options and unconsumed routes of the current table.
41    current_table: Option<(DatanodeTableValue, std::vec::IntoIter<RegionRoute>)>,
42    /// Partial groups waiting for more regions sharing their WAL topic.
43    batches: BatchAggregator<String, RegionId>,
44    /// Emitted group remainder retained across calls with smaller region budgets.
45    remaining_group: Vec<RegionId>,
46    /// Whether all table entries have been consumed; buffered groups may remain.
47    exhausted: bool,
48    /// Whether this scan has returned any region group.
49    produced_group: bool,
50    /// Number of source-node followers encountered in this scan.
51    follower_count: usize,
52}
53
54impl fmt::Debug for RegionScan {
55    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56        f.debug_struct("RegionScan")
57            .field("exhausted", &self.exhausted)
58            .field("follower_count", &self.follower_count)
59            .finish_non_exhaustive()
60    }
61}
62
63impl RegionScan {
64    /// Creates a bounded scan, grouping regions that can share a migration procedure.
65    pub(crate) fn new(
66        metadata: &TableMetadataManagerRef,
67        node_id: DatanodeId,
68        batch_size: usize,
69        buffer_limit: usize,
70    ) -> Self {
71        Self {
72            metadata: metadata.clone(),
73            node_id,
74            tables: metadata.datanode_table_manager().tables(node_id),
75            current_table: None,
76            batches: BatchAggregator::new(batch_size, buffer_limit),
77            remaining_group: vec![],
78            exhausted: false,
79            produced_group: false,
80            follower_count: 0,
81        }
82    }
83
84    /// Returns whether this scan has emitted any group, including previous calls.
85    pub(crate) fn has_produced_group(&self) -> bool {
86        self.produced_group
87    }
88
89    /// Returns the number of source-node followers encountered so far.
90    pub(crate) fn follower_count(&self) -> usize {
91        self.follower_count
92    }
93
94    /// Returns at most `max_regions` regions that can share a migration procedure.
95    /// Applies `should_skip` to source leaders before buffering them.
96    /// Retains the rest of the group for the next call. A zero limit behaves as one.
97    /// Returns `None` only after the metadata stream and buffered groups are exhausted.
98    pub(crate) async fn next_group(
99        &mut self,
100        mut should_skip: impl FnMut(RegionId) -> bool,
101        max_regions: usize,
102    ) -> Result<Option<Vec<RegionId>>> {
103        loop {
104            if !self.remaining_group.is_empty() {
105                let count = max_regions.max(1).min(self.remaining_group.len());
106                self.produced_group = true;
107                return Ok(Some(self.remaining_group.drain(..count).collect()));
108            }
109            if let Some(regions) = self.scan_current_table(&mut should_skip) {
110                self.remaining_group = regions;
111                continue;
112            }
113
114            if self.exhausted {
115                let Some((_, mut regions)) = self.batches.flush() else {
116                    return Ok(None);
117                };
118                regions.sort_unstable();
119                regions.dedup();
120                self.remaining_group = regions;
121                continue;
122            }
123            self.read_next_table().await?;
124        }
125    }
126
127    /// Scans the current table until a group is ready or all its routes are consumed.
128    fn scan_current_table(
129        &mut self,
130        should_skip: &mut impl FnMut(RegionId) -> bool,
131    ) -> Option<Vec<RegionId>> {
132        let (value, routes) = self.current_table.as_mut()?;
133        for route in routes.by_ref() {
134            if route
135                .follower_peers
136                .iter()
137                .any(|peer| peer.id == self.node_id)
138            {
139                self.follower_count += 1;
140            }
141            if route.leader_peer.as_ref().map(|peer| peer.id) != Some(self.node_id)
142                || should_skip(route.region.id)
143            {
144                continue;
145            }
146            let region_id = route.region.id;
147            let Some(topic) =
148                extract_topic_from_wal_options(region_id, &value.region_info.region_wal_options)
149            else {
150                // Regions without a shared WAL topic must migrate independently.
151                return Some(vec![region_id]);
152            };
153            if let Some((_, mut regions)) = self.batches.push(topic, region_id) {
154                regions.sort_unstable();
155                regions.dedup();
156                return Some(regions);
157            }
158        }
159        self.current_table = None;
160        None
161    }
162
163    /// Loads the next table's authoritative routes, skipping dropped and logical tables.
164    async fn read_next_table(&mut self) -> Result<()> {
165        let Some(value) = self
166            .tables
167            .try_next()
168            .await
169            .context(error::TableMetadataManagerSnafu)?
170        else {
171            self.exhausted = true;
172            return Ok(());
173        };
174        let route = self
175            .metadata
176            .table_route_manager()
177            .table_route_storage()
178            .get(value.table_id)
179            .await
180            .context(error::TableMetadataManagerSnafu)?;
181        if let Some(TableRouteValue::Physical(route)) = route {
182            self.current_table = Some((value, route.region_routes.into_iter()));
183        }
184        Ok(())
185    }
186}
187
188#[cfg(test)]
189mod tests {
190    use store_api::storage::RegionId;
191
192    use super::RegionScan;
193    use crate::procedure::drain_datanode::test_util::{
194        TestEnv, create_kafka_table, follower_region, leader_region,
195    };
196
197    #[tokio::test]
198    async fn test_topic_scan_pauses_and_preserves_interleaved_regions() {
199        let env = TestEnv::new().await;
200        create_kafka_table(&env, 1024, 9, 2).await;
201        create_kafka_table(&env, 1025, 3, 2).await;
202        let mut scan = RegionScan::new(&env.table_metadata_manager, 1, 2, 8);
203        let first = scan.next_group(|_| false, 2).await.unwrap().unwrap();
204        assert_eq!(vec![RegionId::new(1024, 0), RegionId::new(1024, 2)], first);
205        // The first child can be dispatched before even the first table is exhausted.
206        assert_eq!(6, scan.current_table.as_ref().unwrap().1.len());
207        assert!(!scan.exhausted);
208        let mut seen = first;
209        while let Some(group) = scan.next_group(|_| false, 2).await.unwrap() {
210            assert!(group.len() <= 2);
211            let first = group[0];
212            assert!(
213                group
214                    .iter()
215                    .all(|id| id.region_number() % 2 == first.region_number() % 2)
216            );
217            seen.extend(group);
218        }
219        seen.sort_unstable();
220        let expected = (0..9)
221            .map(|i| RegionId::new(1024, i))
222            .chain((0..3).map(|i| RegionId::new(1025, i)))
223            .collect::<Vec<_>>();
224        assert_eq!(expected, seen);
225    }
226
227    #[tokio::test]
228    async fn test_scan_leaders_and_count_followers() {
229        let env = TestEnv::new().await;
230        let first = RegionId::new(1024, 1);
231        let second = RegionId::new(1024, 2);
232        env.create_table(vec![leader_region(first, 1), follower_region(second, 2, 1)])
233            .await;
234
235        let mut scan = RegionScan::new(&env.table_metadata_manager, 1, 4, 16);
236        let mut leaders = vec![];
237        while let Some(group) = scan.next_group(|_| false, 4).await.unwrap() {
238            leaders.extend(group);
239        }
240        assert_eq!(vec![first], leaders);
241        assert_eq!(1, scan.follower_count());
242    }
243
244    #[tokio::test]
245    async fn test_scan_empty_datanode() {
246        let env = TestEnv::new().await;
247
248        let mut scan = RegionScan::new(&env.table_metadata_manager, 1, 4, 16);
249        let mut leaders = vec![];
250        while let Some(group) = scan.next_group(|_| false, 4).await.unwrap() {
251            leaders.extend(group);
252        }
253        assert!(leaders.is_empty());
254        assert_eq!(0, scan.follower_count());
255    }
256
257    #[tokio::test]
258    async fn test_scan_uses_authoritative_table_route() {
259        let env = TestEnv::new().await;
260        let region_id = RegionId::new(1024, 1);
261        // The datanode is listed as a follower of the region, so it is not a leader even
262        // though the table index of the datanode contains the table.
263        env.create_table(vec![follower_region(region_id, 2, 1)])
264            .await;
265
266        let mut scan = RegionScan::new(&env.table_metadata_manager, 1, 4, 16);
267        let mut leaders = vec![];
268        while let Some(group) = scan.next_group(|_| false, 4).await.unwrap() {
269            leaders.extend(group);
270        }
271        assert!(leaders.is_empty());
272        assert_eq!(1, scan.follower_count());
273    }
274    #[tokio::test]
275    async fn test_scan_retains_group_remainder_across_budgets() {
276        let env = TestEnv::new().await;
277        create_kafka_table(&env, 1024, 4, 1).await;
278        let mut scan = RegionScan::new(&env.table_metadata_manager, 1, 4, 16);
279        for (limit, expected) in [(1, vec![0]), (2, vec![1, 2]), (1, vec![3])] {
280            let group = scan.next_group(|_| false, limit).await.unwrap().unwrap();
281            assert_eq!(
282                expected
283                    .into_iter()
284                    .map(|i| RegionId::new(1024, i))
285                    .collect::<Vec<_>>(),
286                group
287            );
288        }
289        assert!(scan.next_group(|_| false, 4).await.unwrap().is_none());
290    }
291
292    #[tokio::test]
293    async fn test_scan_skips_regions_selected_by_predicate() {
294        for kafka in [false, true] {
295            let env = TestEnv::new().await;
296            if kafka {
297                create_kafka_table(&env, 1024, 6, 1).await;
298            } else {
299                env.create_table(
300                    (0..6)
301                        .map(|i| leader_region(RegionId::new(1024, i), 1))
302                        .collect(),
303                )
304                .await;
305            }
306            let skipped = [
307                RegionId::new(1024, 1),
308                RegionId::new(1024, 3),
309                RegionId::new(1024, 5),
310            ];
311            let mut scan = RegionScan::new(&env.table_metadata_manager, 1, 2, 8);
312            let mut checked = Vec::new();
313            let mut regions = Vec::new();
314            while let Some(group) = scan
315                .next_group(
316                    |region| {
317                        checked.push(region);
318                        skipped.contains(&region)
319                    },
320                    1,
321                )
322                .await
323                .unwrap()
324            {
325                regions.extend(group);
326            }
327            assert_eq!(
328                (0..6).map(|i| RegionId::new(1024, i)).collect::<Vec<_>>(),
329                checked
330            );
331            assert_eq!(
332                vec![
333                    RegionId::new(1024, 0),
334                    RegionId::new(1024, 2),
335                    RegionId::new(1024, 4)
336                ],
337                regions
338            );
339        }
340    }
341
342    #[tokio::test]
343    async fn test_scan_keeps_local_wal_regions_separate() {
344        let env = TestEnv::new().await;
345        env.create_table(
346            (0..3)
347                .map(|i| leader_region(RegionId::new(1024, i), 1))
348                .collect(),
349        )
350        .await;
351        let mut scan = RegionScan::new(&env.table_metadata_manager, 1, 4, 16);
352        for i in 0..3 {
353            assert_eq!(
354                Some(vec![RegionId::new(1024, i)]),
355                scan.next_group(|_| false, 4).await.unwrap()
356            );
357        }
358        assert!(scan.next_group(|_| false, 4).await.unwrap().is_none());
359    }
360}