1use 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#[derive(Debug, Clone)]
33pub struct RegionMigrationTaskBatch {
34 pub region_ids: Vec<RegionId>,
36 pub from_peer: Peer,
38 pub to_peer: Peer,
40 pub timeout: Duration,
42 pub trigger_reason: RegionMigrationTriggerReason,
44}
45
46impl RegionMigrationTaskBatch {
47 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 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#[derive(Debug, Clone, Default, PartialEq)]
100pub(crate) struct RegionMigrationAnalysis {
101 pub(crate) migrating: Vec<RegionId>,
103 pub(crate) migrated: Vec<RegionId>,
105 pub(crate) leader_changed: Vec<RegionId>,
107 pub(crate) peer_conflict: Vec<RegionId>,
109 pub(crate) table_not_found: Vec<RegionId>,
111 pub(crate) region_not_found: Vec<RegionId>,
113 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
129fn 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
139fn 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
146fn 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
155fn 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
178pub 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 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 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, ®ion_route, 2, 1).unwrap();
284 assert_eq!(
285 result,
286 RegionMigrationAnalysis {
287 migrated: vec![region_id],
288 ..Default::default()
289 }
290 );
291
292 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, ®ion_route, 2, 3).unwrap();
304 assert_eq!(
305 result,
306 RegionMigrationAnalysis {
307 leader_changed: vec![region_id],
308 ..Default::default()
309 }
310 );
311
312 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, ®ion_route, 1, 2).unwrap();
324 assert_eq!(
325 result,
326 RegionMigrationAnalysis {
327 peer_conflict: vec![region_id],
328 ..Default::default()
329 }
330 );
331
332 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, ®ion_route, 1, 3).unwrap();
344 assert_eq!(
345 result,
346 RegionMigrationAnalysis {
347 pending: vec![region_id],
348 ..Default::default()
349 }
350 );
351
352 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, ®ion_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 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 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 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 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 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}