Skip to main content

meta_srv/procedure/region_migration/
utils.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::{HashMap, HashSet};
16use std::fmt::Display;
17use std::time::Duration;
18
19use common_meta::key::TableMetadataManagerRef;
20use common_meta::peer::Peer;
21use common_meta::rpc::router::RegionRoute;
22use itertools::Itertools;
23use snafu::{OptionExt, ResultExt};
24use store_api::storage::{RegionId, TableId};
25
26use crate::error::{self, Result};
27use crate::procedure::region_migration::{
28    DEFAULT_REGION_MIGRATION_TIMEOUT, RegionMigrationProcedureTask, RegionMigrationTriggerReason,
29};
30
31/// A migration task describing how regions are intended to move between peers.
32#[derive(Debug, Clone)]
33pub struct RegionMigrationTaskBatch {
34    /// Region ids involved in this migration.
35    pub region_ids: Vec<RegionId>,
36    /// Source peer where regions currently reside.
37    pub from_peer: Peer,
38    /// Destination peer to migrate regions to.
39    pub to_peer: Peer,
40    /// Timeout for migration.
41    pub timeout: Duration,
42    /// Reason why this migration was triggered.
43    pub trigger_reason: RegionMigrationTriggerReason,
44}
45
46impl RegionMigrationTaskBatch {
47    /// Constructs a [`RegionMigrationTaskBatch`] from a vector of region migration procedure tasks.
48    ///
49    /// Aggregates region IDs, determines source and destination peers, sets an appropriate timeout,
50    /// and assigns the trigger reason for the migration batch.
51    ///
52    /// # Panic
53    /// if the `tasks` are empty.
54    pub fn from_tasks(tasks: Vec<(RegionMigrationProcedureTask, u32)>) -> Self {
55        let max_count = tasks.iter().map(|(_, count)| *count).max().unwrap_or(1);
56        let region_ids = tasks.iter().map(|(r, _)| r.region_id).collect::<Vec<_>>();
57        let from_peer = tasks[0].0.from_peer.clone();
58        let to_peer = tasks[0].0.to_peer.clone();
59        let timeout = DEFAULT_REGION_MIGRATION_TIMEOUT * max_count;
60        let trigger_reason = RegionMigrationTriggerReason::Failover;
61        Self {
62            region_ids,
63            from_peer,
64            to_peer,
65            timeout,
66            trigger_reason,
67        }
68    }
69}
70
71impl Display for RegionMigrationTaskBatch {
72    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
73        write!(
74            f,
75            "RegionMigrationTask {{ region_ids: {:?}, from_peer: {:?}, to_peer: {:?}, timeout: {:?}, trigger_reason: {:?} }}",
76            self.region_ids, self.from_peer, self.to_peer, self.timeout, self.trigger_reason
77        )
78    }
79}
80
81impl RegionMigrationTaskBatch {
82    /// Returns the table regions map.
83    ///
84    /// The key is the table id, the value is the region ids of the table.
85    pub(crate) fn table_regions(&self) -> HashMap<TableId, HashSet<RegionId>> {
86        let mut table_regions = HashMap::new();
87        for region_id in &self.region_ids {
88            table_regions
89                .entry(region_id.table_id())
90                .or_insert_with(HashSet::new)
91                .insert(*region_id);
92        }
93        table_regions
94    }
95}
96
97/// Classifies regions during migration batch construction.
98/// Route analysis fills metadata categories; the builder adds tracker-owned regions.
99#[derive(Debug, Clone, Default, PartialEq)]
100pub(crate) struct RegionMigrationAnalysis {
101    /// Regions already owned by another migration, populated by the batch builder.
102    pub(crate) migrating: Vec<RegionId>,
103    /// Regions already migrated to the `to_peer`.
104    pub(crate) migrated: Vec<RegionId>,
105    /// Regions where the leader peer has changed.
106    pub(crate) leader_changed: Vec<RegionId>,
107    /// Regions where `to_peer` is already a follower (conflict).
108    pub(crate) peer_conflict: Vec<RegionId>,
109    /// Regions whose table is not found.
110    pub(crate) table_not_found: Vec<RegionId>,
111    /// Regions whose table exists but region route is not found (e.g., removed after repartition).
112    pub(crate) region_not_found: Vec<RegionId>,
113    /// Regions still pending migration.
114    pub(crate) pending: Vec<RegionId>,
115}
116
117fn leader_peer(region_route: &RegionRoute) -> Result<&Peer> {
118    region_route
119        .leader_peer
120        .as_ref()
121        .with_context(|| error::UnexpectedSnafu {
122            violated: format!(
123                "Region route leader peer is not found in region({})",
124                region_route.region.id
125            ),
126        })
127}
128
129/// Returns true if the region has already been migrated to `to_peer`.
130fn has_migrated(region_route: &RegionRoute, to_peer_id: u64) -> Result<bool> {
131    if region_route.is_leader_downgrading() {
132        return Ok(false);
133    }
134
135    let leader_peer = leader_peer(region_route)?;
136    Ok(leader_peer.id == to_peer_id)
137}
138
139/// Returns true if the leader peer of the region has changed.
140fn has_leader_changed(region_route: &RegionRoute, from_peer_id: u64) -> Result<bool> {
141    let leader_peer = leader_peer(region_route)?;
142
143    Ok(leader_peer.id != from_peer_id)
144}
145
146/// Returns true if `to_peer` is already a follower of the region (conflict).
147fn has_peer_conflict(region_route: &RegionRoute, to_peer_id: u64) -> bool {
148    region_route
149        .follower_peers
150        .iter()
151        .map(|p| p.id)
152        .contains(&to_peer_id)
153}
154
155/// Updates the verification result based on a single region route.
156fn update_result_with_region_route(
157    result: &mut RegionMigrationAnalysis,
158    region_route: &RegionRoute,
159    from_peer_id: u64,
160    to_peer_id: u64,
161) -> Result<()> {
162    if has_migrated(region_route, to_peer_id)? {
163        result.migrated.push(region_route.region.id);
164        return Ok(());
165    }
166    if has_leader_changed(region_route, from_peer_id)? {
167        result.leader_changed.push(region_route.region.id);
168        return Ok(());
169    }
170    if has_peer_conflict(region_route, to_peer_id) {
171        result.peer_conflict.push(region_route.region.id);
172        return Ok(());
173    }
174    result.pending.push(region_route.region.id);
175    Ok(())
176}
177
178/// Analyzes the migration task and categorizes regions by their current state.
179///
180/// Returns a [`RegionMigrationAnalysis`] based on table routes.
181/// The `migrating` category remains empty because this function does not access the tracker.
182pub async fn analyze_region_migration_task(
183    task: &RegionMigrationTaskBatch,
184    table_metadata_manager: &TableMetadataManagerRef,
185) -> Result<RegionMigrationAnalysis> {
186    if task.to_peer.id == task.from_peer.id {
187        return error::InvalidArgumentsSnafu {
188            err_msg: format!(
189                "The `from_peer_id`({}) can't equal `to_peer_id`({})",
190                task.from_peer.id, task.to_peer.id
191            ),
192        }
193        .fail();
194    }
195    let table_regions = task.table_regions();
196    let table_ids = table_regions.keys().cloned().collect::<Vec<_>>();
197    let mut result = RegionMigrationAnalysis::default();
198
199    let table_routes = table_metadata_manager
200        .table_route_manager()
201        .table_route_storage()
202        .batch_get_with_raw_bytes(&table_ids)
203        .await
204        .context(error::TableMetadataManagerSnafu)?;
205
206    for (table_id, table_route) in table_ids.into_iter().zip(table_routes) {
207        let region_ids = table_regions.get(&table_id).unwrap();
208        let Some(table_route) = table_route else {
209            result.table_not_found.extend(region_ids);
210            continue;
211        };
212        // Throws error if the table route is not a physical table route.
213        let region_routes = table_route.region_routes().with_context(|_| {
214            error::UnexpectedLogicalRouteTableSnafu {
215                err_msg: format!("TableRoute({table_id:?}) is a non-physical TableRouteValue."),
216            }
217        })?;
218
219        let existing_region_ids = region_routes
220            .iter()
221            .map(|r| r.region.id)
222            .collect::<HashSet<_>>();
223
224        for region_route in region_routes
225            .iter()
226            .filter(|r| region_ids.contains(&r.region.id))
227        {
228            update_result_with_region_route(
229                &mut result,
230                region_route,
231                task.from_peer.id,
232                task.to_peer.id,
233            )?;
234        }
235
236        for region_id in region_ids {
237            if !existing_region_ids.contains(region_id) {
238                result.region_not_found.push(*region_id);
239            }
240        }
241    }
242
243    Ok(result)
244}
245
246#[cfg(test)]
247mod tests {
248
249    use std::assert_matches;
250    use std::sync::Arc;
251    use std::time::Duration;
252
253    use common_meta::key::TableMetadataManager;
254    use common_meta::key::table_route::{
255        LogicalTableRouteValue, PhysicalTableRouteValue, TableRouteValue,
256    };
257    use common_meta::kv_backend::TxnService;
258    use common_meta::kv_backend::memory::MemoryKvBackend;
259    use common_meta::peer::Peer;
260    use common_meta::rpc::router::{Region, RegionRoute};
261    use store_api::storage::RegionId;
262
263    use crate::error::Error;
264    use crate::procedure::region_migration::RegionMigrationTriggerReason;
265    use crate::procedure::region_migration::utils::{
266        RegionMigrationAnalysis, RegionMigrationTaskBatch, analyze_region_migration_task,
267        update_result_with_region_route,
268    };
269
270    #[test]
271    fn test_update_result_with_region_route() {
272        // The region is already migrated to the to_peer.
273        let mut result = RegionMigrationAnalysis::default();
274        let region_id = RegionId::new(1, 1);
275        let region_route = RegionRoute {
276            region: Region::new_test(region_id),
277            leader_peer: Some(Peer::empty(1)),
278            follower_peers: vec![],
279            leader_state: None,
280            leader_down_since: None,
281            write_route_policy: None,
282        };
283        update_result_with_region_route(&mut result, &region_route, 2, 1).unwrap();
284        assert_eq!(
285            result,
286            RegionMigrationAnalysis {
287                migrated: vec![region_id],
288                ..Default::default()
289            }
290        );
291
292        // Test region leader changed.
293        let mut result = RegionMigrationAnalysis::default();
294        let region_id = RegionId::new(1, 1);
295        let region_route = RegionRoute {
296            region: Region::new_test(region_id),
297            leader_peer: Some(Peer::empty(1)),
298            follower_peers: vec![],
299            leader_state: None,
300            leader_down_since: None,
301            write_route_policy: None,
302        };
303        update_result_with_region_route(&mut result, &region_route, 2, 3).unwrap();
304        assert_eq!(
305            result,
306            RegionMigrationAnalysis {
307                leader_changed: vec![region_id],
308                ..Default::default()
309            }
310        );
311
312        // Test region peer conflict.
313        let mut result = RegionMigrationAnalysis::default();
314        let region_id = RegionId::new(1, 1);
315        let region_route = RegionRoute {
316            region: Region::new_test(region_id),
317            leader_peer: Some(Peer::empty(1)),
318            follower_peers: vec![Peer::empty(2)],
319            leader_state: None,
320            leader_down_since: None,
321            write_route_policy: None,
322        };
323        update_result_with_region_route(&mut result, &region_route, 1, 2).unwrap();
324        assert_eq!(
325            result,
326            RegionMigrationAnalysis {
327                peer_conflict: vec![region_id],
328                ..Default::default()
329            }
330        );
331
332        // Test normal case.
333        let mut result = RegionMigrationAnalysis::default();
334        let region_id = RegionId::new(1, 1);
335        let region_route = RegionRoute {
336            region: Region::new_test(region_id),
337            leader_peer: Some(Peer::empty(1)),
338            follower_peers: vec![],
339            leader_state: None,
340            leader_down_since: None,
341            write_route_policy: None,
342        };
343        update_result_with_region_route(&mut result, &region_route, 1, 3).unwrap();
344        assert_eq!(
345            result,
346            RegionMigrationAnalysis {
347                pending: vec![region_id],
348                ..Default::default()
349            }
350        );
351
352        // Test leader peer not set
353        let mut result = RegionMigrationAnalysis::default();
354        let region_id = RegionId::new(1, 1);
355        let region_route = RegionRoute {
356            region: Region::new_test(region_id),
357            leader_peer: None,
358            follower_peers: vec![],
359            leader_state: None,
360            leader_down_since: None,
361            write_route_policy: None,
362        };
363        let err = update_result_with_region_route(&mut result, &region_route, 1, 3).unwrap_err();
364        assert_matches!(err, Error::Unexpected { .. });
365    }
366
367    #[tokio::test]
368    async fn test_analyze_region_migration_task_invalid_task() {
369        let task = &RegionMigrationTaskBatch {
370            region_ids: vec![RegionId::new(1, 1)],
371            from_peer: Peer::empty(1),
372            to_peer: Peer::empty(1),
373            timeout: Duration::from_millis(1000),
374            trigger_reason: RegionMigrationTriggerReason::Manual,
375        };
376        let kv_backend = Arc::new(MemoryKvBackend::default());
377        let table_metadata_manager = Arc::new(TableMetadataManager::new(kv_backend.clone()));
378        let err = analyze_region_migration_task(task, &table_metadata_manager)
379            .await
380            .unwrap_err();
381        assert_matches!(err, Error::InvalidArguments { .. });
382    }
383
384    #[tokio::test]
385    async fn test_analyze_region_migration_table_not_found() {
386        let task = &RegionMigrationTaskBatch {
387            region_ids: vec![RegionId::new(1, 1)],
388            from_peer: Peer::empty(1),
389            to_peer: Peer::empty(2),
390            timeout: Duration::from_millis(1000),
391            trigger_reason: RegionMigrationTriggerReason::Manual,
392        };
393        let kv_backend = Arc::new(MemoryKvBackend::default());
394        let table_metadata_manager = Arc::new(TableMetadataManager::new(kv_backend.clone()));
395        let result = analyze_region_migration_task(task, &table_metadata_manager)
396            .await
397            .unwrap();
398        assert_eq!(
399            result,
400            RegionMigrationAnalysis {
401                table_not_found: vec![RegionId::new(1, 1)],
402                ..Default::default()
403            }
404        );
405    }
406
407    #[tokio::test]
408    async fn test_analyze_region_migration_unexpected_logical_table() {
409        let kv_backend = Arc::new(MemoryKvBackend::default());
410        let table_metadata_manager = Arc::new(TableMetadataManager::new(kv_backend.clone()));
411        let (txn, _) = table_metadata_manager
412            .table_route_manager()
413            .table_route_storage()
414            .build_create_txn(
415                1024,
416                &TableRouteValue::Logical(LogicalTableRouteValue::new(1024)),
417            )
418            .unwrap();
419        kv_backend.txn(txn).await.unwrap();
420        let task = &RegionMigrationTaskBatch {
421            region_ids: vec![RegionId::new(1024, 1)],
422            from_peer: Peer::empty(1),
423            to_peer: Peer::empty(2),
424            timeout: Duration::from_millis(1000),
425            trigger_reason: RegionMigrationTriggerReason::Manual,
426        };
427        let err = analyze_region_migration_task(task, &table_metadata_manager)
428            .await
429            .unwrap_err();
430        assert_matches!(err, Error::UnexpectedLogicalRouteTable { .. });
431    }
432
433    #[tokio::test]
434    async fn test_analyze_region_migration_normal_case() {
435        let kv_backend = Arc::new(MemoryKvBackend::default());
436        let table_metadata_manager = Arc::new(TableMetadataManager::new(kv_backend.clone()));
437        let (txn, _) = table_metadata_manager
438            .table_route_manager()
439            .table_route_storage()
440            .build_create_txn(
441                1024,
442                &TableRouteValue::Physical(PhysicalTableRouteValue::new(vec![
443                    // Already migrated to the to_peer.
444                    RegionRoute {
445                        region: Region::new_test(RegionId::new(1024, 1)),
446                        leader_peer: Some(Peer::empty(2)),
447                        follower_peers: vec![],
448                        leader_state: None,
449                        leader_down_since: None,
450                        write_route_policy: None,
451                    },
452                    // Leader peer changed.
453                    RegionRoute {
454                        region: Region::new_test(RegionId::new(1024, 2)),
455                        leader_peer: Some(Peer::empty(3)),
456                        follower_peers: vec![],
457                        leader_state: None,
458                        leader_down_since: None,
459                        write_route_policy: None,
460                    },
461                    // Peer conflict.
462                    RegionRoute {
463                        region: Region::new_test(RegionId::new(1024, 3)),
464                        leader_peer: Some(Peer::empty(1)),
465                        follower_peers: vec![Peer::empty(2)],
466                        leader_state: None,
467                        leader_down_since: None,
468                        write_route_policy: None,
469                    },
470                    // Normal case.
471                    RegionRoute {
472                        region: Region::new_test(RegionId::new(1024, 4)),
473                        leader_peer: Some(Peer::empty(1)),
474                        follower_peers: vec![],
475                        leader_state: None,
476                        leader_down_since: None,
477                        write_route_policy: None,
478                    },
479                ])),
480            )
481            .unwrap();
482
483        kv_backend.txn(txn).await.unwrap();
484        let task = &RegionMigrationTaskBatch {
485            region_ids: vec![
486                RegionId::new(1024, 1),
487                RegionId::new(1024, 2),
488                RegionId::new(1024, 3),
489                RegionId::new(1024, 4),
490                // Region of existing table but route removed (e.g., after repartition).
491                RegionId::new(1024, 5),
492                RegionId::new(1025, 1),
493            ],
494            from_peer: Peer::empty(1),
495            to_peer: Peer::empty(2),
496            timeout: Duration::from_millis(1000),
497            trigger_reason: RegionMigrationTriggerReason::Manual,
498        };
499        let result = analyze_region_migration_task(task, &table_metadata_manager)
500            .await
501            .unwrap();
502        assert_eq!(
503            result,
504            RegionMigrationAnalysis {
505                pending: vec![RegionId::new(1024, 4)],
506                migrated: vec![RegionId::new(1024, 1)],
507                leader_changed: vec![RegionId::new(1024, 2)],
508                peer_conflict: vec![RegionId::new(1024, 3)],
509                region_not_found: vec![RegionId::new(1024, 5)],
510                table_not_found: vec![RegionId::new(1025, 1)],
511                migrating: vec![],
512            }
513        );
514    }
515}