Skip to main content

meta_srv/procedure/repartition/
allocate_region.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::any::Any;
16use std::collections::{HashMap, HashSet};
17
18use common_meta::affinity::{
19    AffinityFallback, AffinityReference, AffinityRequirements, AffinityResolver,
20};
21use common_meta::ddl::create_table::executor::CreateTableExecutor;
22use common_meta::ddl::create_table::template::{
23    CreateRequestBuilder, build_template_from_raw_table_info_for_physical_table,
24};
25use common_meta::ddl::utils::get_region_wal_options;
26use common_meta::lock_key::TableLock;
27use common_meta::node_manager::NodeManagerRef;
28use common_meta::peer::PeerAllocContext;
29use common_meta::rpc::router::RegionRoute;
30use common_meta::wal_provider::{
31    RegionWalOptions, acquire_remote_wal_read_locks, refresh_initial_pruned_entry_ids,
32};
33use common_procedure::{Context as ProcedureContext, Status};
34use common_telemetry::{debug, info};
35use common_wal::options::WalOptions;
36use serde::{Deserialize, Deserializer, Serialize};
37use snafu::{OptionExt, ResultExt};
38use store_api::region_request::RegionRequirements;
39use store_api::storage::{RegionId, RegionNumber, TableId};
40use table::metadata::TableInfo;
41use table::table_reference::TableReference;
42use tokio::time::Instant;
43
44use crate::error::{self, Result};
45use crate::procedure::repartition::dispatch::Dispatch;
46use crate::procedure::repartition::plan::{
47    AllocationPlanEntry, RepartitionPlanEntry, TargetRegionDescriptor,
48    convert_allocation_plan_to_repartition_plan,
49};
50use crate::procedure::repartition::{Context, State};
51
52#[derive(Debug, Clone, Serialize)]
53pub enum AllocateRegion {
54    Build(BuildPlan),
55    Execute(ExecutePlan),
56}
57
58impl<'de> Deserialize<'de> for AllocateRegion {
59    fn deserialize<D>(deserializer: D) -> std::result::Result<Self, D::Error>
60    where
61        D: Deserializer<'de>,
62    {
63        #[derive(Deserialize)]
64        enum CurrentAllocateRegion {
65            Build(BuildPlan),
66            Execute(ExecutePlan),
67        }
68
69        #[derive(Deserialize)]
70        struct LegacyAllocateRegion {
71            plan_entries: Vec<AllocationPlanEntry>,
72        }
73
74        #[derive(Deserialize)]
75        #[serde(untagged)]
76        enum AllocateRegionRepr {
77            Current(CurrentAllocateRegion),
78            Legacy(LegacyAllocateRegion),
79        }
80
81        match AllocateRegionRepr::deserialize(deserializer)? {
82            AllocateRegionRepr::Current(CurrentAllocateRegion::Build(build_plan)) => {
83                Ok(Self::Build(build_plan))
84            }
85            AllocateRegionRepr::Current(CurrentAllocateRegion::Execute(execute_plan)) => {
86                Ok(Self::Execute(execute_plan))
87            }
88            AllocateRegionRepr::Legacy(legacy) => Ok(Self::Build(BuildPlan {
89                plan_entries: legacy.plan_entries,
90            })),
91        }
92    }
93}
94
95#[derive(Debug, Clone, Serialize, Deserialize)]
96pub struct BuildPlan {
97    plan_entries: Vec<AllocationPlanEntry>,
98}
99
100impl BuildPlan {
101    async fn next(
102        &mut self,
103        ctx: &mut Context,
104        procedure_ctx: &ProcedureContext,
105    ) -> Result<(Box<dyn State>, Status)> {
106        let timer = Instant::now();
107        let table_id = ctx.persistent_ctx.table_id;
108        let table_lock = TableLock::Write(table_id).into();
109        let _guard = procedure_ctx.provider.acquire_lock(&table_lock).await;
110        let table_route_value = ctx.get_table_route_value().await?;
111        let to_allocate = AllocateRegion::count_regions_to_allocate(&self.plan_entries);
112        // A crash before the plan is persisted can leave a gap, but no datanode
113        // can create a region until its number has been durably reserved.
114        let mut next_region_number = if to_allocate > 0 {
115            ctx.reserve_region_numbers(&table_route_value, to_allocate)
116                .await?
117        } else {
118            0
119        };
120
121        // Converts allocation plan to repartition plan.
122        let repartition_plan_entries = AllocateRegion::convert_to_repartition_plans(
123            table_id,
124            &mut next_region_number,
125            &self.plan_entries,
126            table_route_value.region_routes().unwrap(),
127        )?;
128        let plan_count = repartition_plan_entries.len();
129        info!(
130            "Repartition allocate regions start, table_id: {}, groups: {}, regions_to_allocate: {}",
131            table_id, plan_count, to_allocate
132        );
133
134        // If no region to allocate, directly dispatch the plan.
135        if to_allocate == 0 {
136            ctx.persistent_ctx.plans = repartition_plan_entries;
137            ctx.update_allocate_region_elapsed(timer.elapsed());
138            return Ok((Box::new(Dispatch), Status::executing(true)));
139        }
140
141        ctx.persistent_ctx.plans = repartition_plan_entries;
142        debug!(
143            "Repartition allocate regions build plan completed, table_id: {}, elapsed: {:?}",
144            table_id,
145            timer.elapsed()
146        );
147        Ok((
148            Box::new(AllocateRegion::Execute(ExecutePlan)),
149            Status::executing(true),
150        ))
151    }
152}
153
154#[derive(Debug, Clone, Serialize, Deserialize)]
155pub struct ExecutePlan;
156
157impl ExecutePlan {
158    async fn next(
159        &mut self,
160        ctx: &mut Context,
161        procedure_ctx: &ProcedureContext,
162    ) -> Result<(Box<dyn State>, Status)> {
163        let timer = Instant::now();
164        let table_id = ctx.persistent_ctx.table_id;
165        let allocate_regions = AllocateRegion::collect_allocate_regions(&ctx.persistent_ctx.plans);
166        let region_number_and_partition_exprs =
167            AllocateRegion::prepare_region_allocation_data(&allocate_regions)?;
168        let table_info_value = ctx.get_table_info_value().await?;
169        let affinity = if let Some(resolver) = &ctx.affinity_resolver {
170            Some(resolve_allocation_affinity(ctx, resolver.as_ref()).await?)
171        } else {
172            None
173        };
174        let groups = if let Some(affinity) = &affinity {
175            group_allocations(table_id, &region_number_and_partition_exprs, affinity)
176        } else {
177            vec![AllocationGroup {
178                affinity: None,
179                regions: region_number_and_partition_exprs
180                    .iter()
181                    .map(|(number, partition)| (*number, partition.as_str()))
182                    .collect(),
183            }]
184        };
185        let mut new_allocated_region_routes = Vec::with_capacity(allocate_regions.len());
186        for AllocationGroup { affinity, regions } in groups {
187            let routes = ctx
188                .region_routes_allocator
189                .allocate(
190                    table_id,
191                    &regions,
192                    &PeerAllocContext {
193                        affinity: affinity.cloned(),
194                    },
195                )
196                .await
197                .context(error::AllocateRegionRoutesSnafu { table_id })?;
198            new_allocated_region_routes.extend(routes);
199        }
200        // Older Execute checkpoints can contain region numbers that Build did not reserve.
201        let table_route_value = ctx.get_table_route_value().await?;
202        let current = table_route_value
203            .max_region_number()
204            .context(error::TableMetadataManagerSnafu)?;
205        if let Some(required) = allocate_regions
206            .iter()
207            .map(|r| r.region_id.region_number())
208            .max()
209            && required > current
210        {
211            ctx.reserve_region_numbers(&table_route_value, (required - current) as usize)
212                .await?;
213        }
214
215        let skip_wal = table_info_value.table_info.meta.options.skip_wal;
216        let allocate_noop = if skip_wal {
217            let region_wal_options =
218                get_region_wal_options(&ctx.table_metadata_manager, &table_route_value, table_id)
219                    .await
220                    .context(error::AllocateWalOptionsSnafu { table_id })?;
221            // A table disabled after creation keeps its real providers. A table
222            // created with skip_wal has Noop providers and must keep them.
223            !table_route_value
224                .region_routes()
225                .unwrap()
226                .iter()
227                .all(|route| {
228                    region_wal_options
229                        .get(&route.region.id.region_number())
230                        .is_none_or(|option| {
231                            matches!(
232                                option,
233                                WalOptions::RaftEngine
234                                    | WalOptions::Kafka(_)
235                                    | WalOptions::ObjectStore(_)
236                            )
237                        })
238                })
239        } else {
240            false
241        };
242        let mut wal_options = ctx
243            .wal_options_allocator
244            .allocate(
245                &allocate_regions
246                    .iter()
247                    .map(|r| r.region_id.region_number())
248                    .collect::<Vec<_>>(),
249                allocate_noop,
250            )
251            .await
252            .context(error::AllocateWalOptionsSnafu { table_id })?;
253        let _remote_wal_lock_guards =
254            acquire_remote_wal_read_locks(procedure_ctx, &wal_options).await;
255        refresh_initial_pruned_entry_ids(&ctx.table_metadata_manager, &mut wal_options)
256            .await
257            .context(error::AllocateWalOptionsSnafu { table_id })?;
258
259        let new_region_count = new_allocated_region_routes.len();
260        let new_regions_brief: Vec<_> = new_allocated_region_routes
261            .iter()
262            .map(|route| {
263                let region_id = route.region.id;
264                let peer = route.leader_peer.as_ref().map(|p| p.id).unwrap_or_default();
265                format!("region_id: {}, peer: {}", region_id, peer)
266            })
267            .collect();
268        info!(
269            "Allocated regions for repartition, table_id: {}, new_region_count: {}, new_regions: {:?}",
270            table_id, new_region_count, new_regions_brief
271        );
272
273        // The table route metadata is not updated yet; register it in memory for region lease renewal.
274        let _operating_guards = Context::register_operating_regions(
275            &ctx.memory_region_keeper,
276            &new_allocated_region_routes,
277        )?;
278        // Allocates the regions on datanodes.
279        AllocateRegion::allocate_regions(
280            &ctx.node_manager,
281            &table_info_value.table_info,
282            &new_allocated_region_routes,
283            &wal_options,
284        )
285        .await?;
286
287        // Updates the table routes.
288        let table_lock = TableLock::Write(table_id).into();
289        let _guard = procedure_ctx.provider.acquire_lock(&table_lock).await;
290        // MUST refresh the table route value after acquiring the lock to avoid lost update.
291        // Otherwise, the new allocated regions might be overridden by concurrent repartition procedures.
292        let table_route_value = ctx.get_table_route_value().await?;
293        // Safety: it is physical table route value.
294        let region_routes = table_route_value.region_routes().unwrap();
295        let new_region_routes =
296            AllocateRegion::generate_region_routes(region_routes, &new_allocated_region_routes);
297        ctx.update_table_route(&table_route_value, new_region_routes, wal_options)
298            .await?;
299        ctx.invalidate_table_cache().await?;
300
301        ctx.update_allocate_region_elapsed(timer.elapsed());
302        Ok((Box::new(Dispatch), Status::executing(true)))
303    }
304}
305
306#[async_trait::async_trait]
307#[typetag::serde]
308impl State for AllocateRegion {
309    async fn next(
310        &mut self,
311        ctx: &mut Context,
312        procedure_ctx: &ProcedureContext,
313    ) -> Result<(Box<dyn State>, Status)> {
314        match self {
315            AllocateRegion::Build(build_plan) => build_plan.next(ctx, procedure_ctx).await,
316            AllocateRegion::Execute(execute_plan) => execute_plan.next(ctx, procedure_ctx).await,
317        }
318    }
319
320    fn as_any(&self) -> &dyn Any {
321        self
322    }
323}
324
325impl AllocateRegion {
326    pub fn new(plan_entries: Vec<AllocationPlanEntry>) -> Self {
327        AllocateRegion::Build(BuildPlan { plan_entries })
328    }
329
330    fn generate_region_routes(
331        region_routes: &[RegionRoute],
332        new_allocated_region_ids: &[RegionRoute],
333    ) -> Vec<RegionRoute> {
334        let region_ids = region_routes
335            .iter()
336            .map(|r| r.region.id)
337            .collect::<HashSet<_>>();
338        let mut new_region_routes = region_routes.to_vec();
339        for new_allocated_region_id in new_allocated_region_ids {
340            if !region_ids.contains(&new_allocated_region_id.region.id) {
341                new_region_routes.push(new_allocated_region_id.clone());
342            }
343        }
344        new_region_routes
345    }
346
347    /// Converts allocation plan entries to repartition plan entries.
348    ///
349    /// This method converts allocation intents into concrete repartition plans,
350    /// updates `next_region_number` for newly allocated regions, and captures
351    /// each plan's `original_target_routes` from the current table-route view.
352    ///
353    /// This also persists each plan's pre-staging target routes for rollback.
354    fn convert_to_repartition_plans(
355        table_id: TableId,
356        next_region_number: &mut RegionNumber,
357        plan_entries: &[AllocationPlanEntry],
358        current_region_routes: &[RegionRoute],
359    ) -> Result<Vec<RepartitionPlanEntry>> {
360        let region_routes_map = current_region_routes
361            .iter()
362            .map(|route| (route.region.id, route))
363            .collect::<HashMap<_, _>>();
364
365        plan_entries
366            .iter()
367            .map(|plan_entry| {
368                let mut plan = convert_allocation_plan_to_repartition_plan(
369                    table_id,
370                    next_region_number,
371                    plan_entry,
372                );
373                Self::capture_plan_original_target_routes(&mut plan, &region_routes_map)?;
374                Ok(plan)
375            })
376            .collect()
377    }
378
379    fn capture_plan_original_target_routes(
380        plan: &mut RepartitionPlanEntry,
381        region_routes_map: &HashMap<RegionId, &RegionRoute>,
382    ) -> Result<()> {
383        // Persist the pre-staging target-route view on the parent plan.
384        // Newly allocated targets are skipped because rollback deletes their
385        // route metadata rather than restoring an original target route.
386        let mut original_target_routes = Vec::with_capacity(plan.target_regions.len());
387        for target in &plan.target_regions {
388            if plan.allocated_region_ids.contains(&target.region_id) {
389                // This target region is to be allocated, so it doesn't exist in current routes.
390                continue;
391            }
392            let route = region_routes_map.get(&target.region_id).context(
393                error::RepartitionTargetRegionMissingSnafu {
394                    group_id: plan.group_id,
395                    region_id: target.region_id,
396                },
397            )?;
398            {
399                original_target_routes.push((*route).clone());
400            }
401        }
402
403        plan.original_target_routes = original_target_routes;
404        Ok(())
405    }
406
407    /// Collects all regions that need to be allocated from the repartition plan entries.
408    fn collect_allocate_regions(
409        repartition_plan_entries: &[RepartitionPlanEntry],
410    ) -> Vec<&TargetRegionDescriptor> {
411        repartition_plan_entries
412            .iter()
413            .flat_map(|p| p.allocate_regions())
414            .collect()
415    }
416
417    /// Prepares region allocation data: region numbers and their partition expressions.
418    fn prepare_region_allocation_data(
419        allocate_regions: &[&TargetRegionDescriptor],
420    ) -> Result<Vec<(RegionNumber, String)>> {
421        allocate_regions
422            .iter()
423            .map(|r| {
424                Ok((
425                    r.region_id.region_number(),
426                    r.partition_expr
427                        .as_json_str()
428                        .context(error::SerializePartitionExprSnafu)?,
429                ))
430            })
431            .collect()
432    }
433
434    /// Calculates the total number of regions that need to be allocated.
435    fn count_regions_to_allocate(plan_entries: &[AllocationPlanEntry]) -> usize {
436        plan_entries
437            .iter()
438            .map(|plan| plan.targets_to_allocate().len())
439            .sum()
440    }
441
442    async fn allocate_regions(
443        node_manager: &NodeManagerRef,
444        raw_table_info: &TableInfo,
445        region_routes: &[RegionRoute],
446        wal_options: &RegionWalOptions,
447    ) -> Result<()> {
448        let table_ref = TableReference::full(
449            &raw_table_info.catalog_name,
450            &raw_table_info.schema_name,
451            &raw_table_info.name,
452        );
453        let table_id = raw_table_info.ident.table_id;
454        // Repartition allocation targets physical regions, so exclude metric internal columns
455        // and derive primary keys from tag semantics.
456        let request = build_template_from_raw_table_info_for_physical_table(raw_table_info)
457            .context(error::BuildCreateRequestSnafu { table_id })?;
458        common_telemetry::debug!(
459            "Allocating regions request, table_id: {}, request: {:?}",
460            table_id,
461            request
462        );
463        let builder = CreateRequestBuilder::new(request, None)
464            .with_requirements(RegionRequirements::object_storage());
465        let region_count = region_routes.len();
466        let wal_region_count = wal_options.len();
467        info!(
468            "Allocating regions on datanodes, table_id: {}, region_count: {}, wal_regions: {}",
469            table_id, region_count, wal_region_count
470        );
471        let executor = CreateTableExecutor::new(table_ref.into(), false, builder);
472        executor
473            .on_create_regions(node_manager, table_id, region_routes, wal_options)
474            .await
475            .context(error::AllocateRegionsSnafu { table_id })?;
476
477        Ok(())
478    }
479}
480
481/// Selects the lowest-ID contributing source for a target spanning multiple sources.
482/// Legacy plans without a transition map fall back to the lowest-ID source in the group.
483fn collect_allocation_sources(
484    plans: &[RepartitionPlanEntry],
485    routes: &[RegionRoute],
486) -> Vec<(RegionId, Option<u64>)> {
487    let leaders: HashMap<_, _> = routes
488        .iter()
489        .filter_map(|route| {
490            route
491                .leader_peer
492                .as_ref()
493                .map(|peer| (route.region.id, peer.id))
494        })
495        .collect();
496    let mut sources = Vec::new();
497    for plan in plans {
498        let allocated: HashSet<_> = plan.allocated_region_ids.iter().copied().collect();
499        let mut target_sources = vec![None; plan.target_regions.len()];
500        if plan.transition_map.is_empty() {
501            let source = plan
502                .source_regions
503                .iter()
504                .map(|source| source.region_id())
505                .min();
506            target_sources.fill(source);
507        } else {
508            for (source, targets) in plan.source_regions.iter().zip(&plan.transition_map) {
509                for target_index in targets {
510                    if let Some(target_source) = target_sources.get_mut(*target_index) {
511                        let source_id = source.region_id();
512                        *target_source =
513                            Some(target_source.map_or(source_id, |current| current.min(source_id)));
514                    }
515                }
516            }
517        }
518        for (target, source) in plan.target_regions.iter().zip(target_sources) {
519            if allocated.contains(&target.region_id) {
520                sources.push((
521                    target.region_id,
522                    source.and_then(|source| leaders.get(&source)).copied(),
523                ));
524            }
525        }
526    }
527    sources
528}
529
530/// Owns requirements once per source; targets refer to them by index.
531#[derive(Debug)]
532struct AllocationAffinity {
533    requirements: Vec<Option<AffinityRequirements>>,
534    target_sources: HashMap<RegionId, usize>,
535}
536
537async fn resolve_allocation_affinity(
538    ctx: &Context,
539    resolver: &dyn AffinityResolver,
540) -> Result<AllocationAffinity> {
541    let table_id = ctx.persistent_ctx.table_id;
542    let routes = ctx.get_table_route_value().await?;
543    let sources =
544        collect_allocation_sources(&ctx.persistent_ctx.plans, routes.region_routes().unwrap());
545    let mut source_indices = HashMap::new();
546    let mut references = Vec::new();
547    for (_, source_id) in &sources {
548        if let Some(source_id) = source_id {
549            source_indices.entry(*source_id).or_insert_with(|| {
550                let index = references.len();
551                references.push(AffinityReference::Datanode(*source_id));
552                index
553            });
554        }
555    }
556    let resolved = resolver
557        .resolve(&references)
558        .await
559        .context(error::AllocateRegionRoutesSnafu { table_id })?;
560    snafu::ensure!(
561        resolved.len() == source_indices.len(),
562        error::UnexpectedSnafu {
563            violated: "affinity resolution must preserve the number and order of references",
564        }
565    );
566    snafu::ensure!(
567        ctx.affinity_fallback == AffinityFallback::Unconstrained
568            || sources.iter().all(|(_, source)| {
569                source.is_some_and(|id| resolved[source_indices[&id]].is_some())
570            }),
571        error::UnexpectedSnafu {
572            violated: "source affinity requirements are unavailable",
573        }
574    );
575    Ok(AllocationAffinity {
576        requirements: resolved,
577        target_sources: sources
578            .into_iter()
579            .filter_map(|(region_id, source_id)| {
580                source_id.map(|source_id| (region_id, source_indices[&source_id]))
581            })
582            .collect(),
583    })
584}
585
586#[derive(Debug, PartialEq, Eq)]
587struct AllocationGroup<'a> {
588    affinity: Option<&'a AffinityRequirements>,
589    regions: Vec<(RegionNumber, &'a str)>,
590}
591
592fn group_allocations<'a>(
593    table_id: TableId,
594    regions: &'a [(RegionNumber, String)],
595    affinity: &'a AllocationAffinity,
596) -> Vec<AllocationGroup<'a>> {
597    let mut groups: Vec<AllocationGroup<'a>> = Vec::new();
598    for (number, partition) in regions {
599        let requirements = affinity
600            .target_sources
601            .get(&RegionId::new(table_id, *number))
602            .and_then(|index| affinity.requirements[*index].as_ref());
603        if let Some(group) = groups
604            .iter_mut()
605            .find(|group| group.affinity == requirements)
606        {
607            group.regions.push((*number, partition.as_str()));
608        } else {
609            groups.push(AllocationGroup {
610                affinity: requirements,
611                regions: vec![(*number, partition.as_str())],
612            });
613        }
614    }
615    groups
616}
617
618#[cfg(test)]
619mod tests {
620    use std::ptr;
621    use std::sync::Arc;
622
623    use api::v1::region::region_request::Body;
624    use common_meta::ddl::allocator::wal_options::WalOptionsAllocator;
625    use common_meta::ddl::test_util::datanode_handler::DatanodeWatcher;
626    use common_meta::key::TableMetadataManagerRef;
627    use common_meta::key::datanode_table::DatanodeTableKey;
628    use common_meta::key::table_route::TableRouteValue;
629    use common_meta::key::test_utils::new_test_table_info_with_name;
630    use common_meta::peer::Peer;
631    use common_meta::rpc::router::{Region, RegionRoute};
632    use common_meta::test_util::MockDatanodeManager;
633    use common_procedure::{ContextProvider, ProcedureId, ProcedureState};
634    use common_procedure_test::MockContextProvider;
635    use common_wal::options::{
636        KafkaWalOptions, ObjectStoreWalOptions, WAL_OPTIONS_KEY, WalOptions,
637    };
638    use store_api::mito_engine_options::SKIP_WAL_KEY;
639    use store_api::storage::RegionId;
640    use tokio::sync::{mpsc, watch};
641    use uuid::Uuid;
642
643    use super::*;
644    use crate::procedure::repartition::State;
645    use crate::procedure::repartition::plan::SourceRegionDescriptor;
646    use crate::procedure::repartition::test_util::{
647        TestingEnv, current_parent_region_routes, new_parent_context, range_expr,
648        test_region_wal_options,
649    };
650
651    fn create_region_descriptor(
652        table_id: TableId,
653        region_number: u32,
654        col: &str,
655        start: i64,
656        end: i64,
657    ) -> SourceRegionDescriptor {
658        SourceRegionDescriptor::partitioned(
659            RegionId::new(table_id, region_number),
660            range_expr(col, start, end),
661        )
662    }
663
664    fn create_target_region_descriptor(
665        table_id: TableId,
666        region_number: u32,
667        col: &str,
668        start: i64,
669        end: i64,
670    ) -> TargetRegionDescriptor {
671        TargetRegionDescriptor {
672            region_id: RegionId::new(table_id, region_number),
673            partition_expr: range_expr(col, start, end),
674        }
675    }
676
677    fn create_allocation_plan_entry(
678        table_id: TableId,
679        source_region_numbers: &[u32],
680        target_ranges: &[(i64, i64)],
681    ) -> AllocationPlanEntry {
682        let source_regions = source_region_numbers
683            .iter()
684            .enumerate()
685            .map(|(i, &n)| {
686                let start = i as i64 * 100;
687                let end = (i + 1) as i64 * 100;
688                create_region_descriptor(table_id, n, "x", start, end)
689            })
690            .collect();
691
692        let target_partition_exprs = target_ranges
693            .iter()
694            .map(|&(start, end)| range_expr("x", start, end))
695            .collect();
696
697        AllocationPlanEntry {
698            group_id: Uuid::new_v4(),
699            source_regions,
700            target_partition_exprs,
701            transition_map: vec![],
702        }
703    }
704
705    fn create_current_region_routes(table_id: TableId, region_numbers: &[u32]) -> Vec<RegionRoute> {
706        region_numbers
707            .iter()
708            .map(|region_number| RegionRoute {
709                region: Region {
710                    id: RegionId::new(table_id, *region_number),
711                    ..Default::default()
712                },
713                leader_peer: Some(Peer::empty(1)),
714                ..Default::default()
715            })
716            .collect()
717    }
718
719    struct ConcurrentTableRouteUpdateProvider {
720        inner: MockContextProvider,
721        table_metadata_manager: TableMetadataManagerRef,
722        table_id: TableId,
723        concurrent_region_route: RegionRoute,
724        region_wal_options: RegionWalOptions,
725    }
726
727    struct TestKafkaWalOptionsAllocator;
728
729    #[async_trait::async_trait]
730    impl WalOptionsAllocator for TestKafkaWalOptionsAllocator {
731        async fn allocate(
732            &self,
733            region_numbers: &[RegionNumber],
734            skip_wal: bool,
735        ) -> common_meta::error::Result<RegionWalOptions> {
736            Ok(region_numbers
737                .iter()
738                .map(|&region_number| {
739                    let options = if skip_wal {
740                        WalOptions::Noop
741                    } else {
742                        WalOptions::Kafka(KafkaWalOptions::new("new-topic".to_string()))
743                    };
744                    (region_number, options)
745                })
746                .collect())
747        }
748    }
749
750    #[async_trait::async_trait]
751    impl ContextProvider for ConcurrentTableRouteUpdateProvider {
752        async fn procedure_state(
753            &self,
754            procedure_id: ProcedureId,
755        ) -> common_procedure::Result<Option<ProcedureState>> {
756            self.inner.procedure_state(procedure_id).await
757        }
758
759        async fn procedure_state_receiver(
760            &self,
761            procedure_id: ProcedureId,
762        ) -> common_procedure::Result<Option<watch::Receiver<ProcedureState>>> {
763            self.inner.procedure_state_receiver(procedure_id).await
764        }
765
766        async fn try_put_poison(
767            &self,
768            key: &common_procedure::PoisonKey,
769            procedure_id: ProcedureId,
770        ) -> common_procedure::Result<()> {
771            self.inner.try_put_poison(key, procedure_id).await
772        }
773
774        async fn acquire_lock(
775            &self,
776            key: &common_procedure::StringKey,
777        ) -> common_procedure::local::DynamicKeyLockGuard {
778            let current_table_route_value = self
779                .table_metadata_manager
780                .table_route_manager()
781                .table_route_storage()
782                .get_with_raw_bytes(self.table_id)
783                .await
784                .unwrap()
785                .unwrap();
786            let mut region_routes = current_table_route_value.region_routes().unwrap().clone();
787
788            if !region_routes
789                .iter()
790                .any(|route| route.region.id == self.concurrent_region_route.region.id)
791            {
792                region_routes.push(self.concurrent_region_route.clone());
793                let datanode_id = current_table_route_value.region_routes().unwrap()[0]
794                    .leader_peer
795                    .as_ref()
796                    .unwrap()
797                    .id;
798                let datanode_table_value = self
799                    .table_metadata_manager
800                    .datanode_table_manager()
801                    .get(&DatanodeTableKey::new(datanode_id, self.table_id))
802                    .await
803                    .unwrap()
804                    .unwrap();
805                let region_options = &datanode_table_value.region_info.region_options;
806
807                self.table_metadata_manager
808                    .update_table_route(
809                        self.table_id,
810                        datanode_table_value.region_info.clone(),
811                        &current_table_route_value,
812                        region_routes,
813                        region_options,
814                        &self.region_wal_options,
815                    )
816                    .await
817                    .unwrap();
818            }
819
820            self.inner.acquire_lock(key).await
821        }
822    }
823
824    #[test]
825    fn test_convert_to_repartition_plans_no_allocation() {
826        let table_id = 1024;
827        let mut next_region_number = 10;
828
829        // 2 source -> 2 target (no allocation needed)
830        let plan_entries = vec![create_allocation_plan_entry(
831            table_id,
832            &[1, 2],
833            &[(0, 50), (50, 200)],
834        )];
835
836        let result = AllocateRegion::convert_to_repartition_plans(
837            table_id,
838            &mut next_region_number,
839            &plan_entries,
840            &create_current_region_routes(table_id, &[1, 2]),
841        )
842        .unwrap();
843
844        assert_eq!(result.len(), 1);
845        assert_eq!(result[0].target_regions.len(), 2);
846        assert!(result[0].allocated_region_ids.is_empty());
847        // next_region_number should not change
848        assert_eq!(next_region_number, 10);
849    }
850
851    #[test]
852    fn test_convert_to_repartition_plans_with_allocation() {
853        let table_id = 1024;
854        let mut next_region_number = 10;
855
856        // 2 source -> 4 target (need to allocate 2 regions)
857        let plan_entries = vec![create_allocation_plan_entry(
858            table_id,
859            &[1, 2],
860            &[(0, 50), (50, 100), (100, 150), (150, 200)],
861        )];
862
863        let result = AllocateRegion::convert_to_repartition_plans(
864            table_id,
865            &mut next_region_number,
866            &plan_entries,
867            &create_current_region_routes(table_id, &[1, 2]),
868        )
869        .unwrap();
870
871        assert_eq!(result.len(), 1);
872        assert_eq!(result[0].target_regions.len(), 4);
873        assert_eq!(result[0].allocated_region_ids.len(), 2);
874        assert_eq!(
875            result[0].allocated_region_ids[0],
876            RegionId::new(table_id, 10)
877        );
878        assert_eq!(
879            result[0].allocated_region_ids[1],
880            RegionId::new(table_id, 11)
881        );
882        // next_region_number should be incremented by 2
883        assert_eq!(next_region_number, 12);
884    }
885
886    #[test]
887    fn test_convert_to_repartition_plans_multiple_entries() {
888        let table_id = 1024;
889        let mut next_region_number = 10;
890
891        // Multiple plan entries with different allocation needs
892        let plan_entries = vec![
893            create_allocation_plan_entry(table_id, &[1], &[(0, 50), (50, 100)]), // need 1 allocation
894            create_allocation_plan_entry(table_id, &[2, 3], &[(100, 150), (150, 200)]), // no allocation
895            create_allocation_plan_entry(table_id, &[4], &[(200, 250), (250, 300), (300, 400)]), // need 2 allocations
896        ];
897
898        let result = AllocateRegion::convert_to_repartition_plans(
899            table_id,
900            &mut next_region_number,
901            &plan_entries,
902            &create_current_region_routes(table_id, &[1, 2, 3, 4]),
903        )
904        .unwrap();
905
906        assert_eq!(result.len(), 3);
907        assert_eq!(result[0].allocated_region_ids.len(), 1);
908        assert_eq!(result[1].allocated_region_ids.len(), 0);
909        assert_eq!(result[2].allocated_region_ids.len(), 2);
910        // next_region_number should be incremented by 3 total
911        assert_eq!(next_region_number, 13);
912    }
913
914    #[test]
915    fn test_count_regions_to_allocate() {
916        let table_id = 1024;
917
918        let plan_entries = vec![
919            create_allocation_plan_entry(table_id, &[1], &[(0, 50), (50, 100)]), // 1 allocation
920            create_allocation_plan_entry(table_id, &[2, 3], &[(100, 200)]), // 0 allocation (deallocate)
921            create_allocation_plan_entry(table_id, &[4], &[(200, 250), (250, 300)]), // 1 allocation
922        ];
923
924        let count = AllocateRegion::count_regions_to_allocate(&plan_entries);
925        assert_eq!(count, 2);
926    }
927
928    #[test]
929    fn test_collect_allocate_regions() {
930        let table_id = 1024;
931        let mut next_region_number = 10;
932
933        let plan_entries = vec![
934            create_allocation_plan_entry(table_id, &[1], &[(0, 50), (50, 100)]), // 1 allocation
935            create_allocation_plan_entry(table_id, &[2], &[(100, 150), (150, 200)]), // 1 allocation
936        ];
937
938        let repartition_plans = AllocateRegion::convert_to_repartition_plans(
939            table_id,
940            &mut next_region_number,
941            &plan_entries,
942            &create_current_region_routes(table_id, &[1, 2]),
943        )
944        .unwrap();
945
946        let allocate_regions = AllocateRegion::collect_allocate_regions(&repartition_plans);
947        assert_eq!(allocate_regions.len(), 2);
948        assert_eq!(allocate_regions[0].region_id, RegionId::new(table_id, 10));
949        assert_eq!(allocate_regions[1].region_id, RegionId::new(table_id, 11));
950    }
951
952    #[test]
953    fn test_prepare_region_allocation_data() {
954        let table_id = 1024;
955        let regions = [
956            create_target_region_descriptor(table_id, 10, "x", 0, 50),
957            create_target_region_descriptor(table_id, 11, "x", 50, 100),
958        ];
959        let region_refs: Vec<&TargetRegionDescriptor> = regions.iter().collect();
960
961        let result = AllocateRegion::prepare_region_allocation_data(&region_refs).unwrap();
962
963        assert_eq!(result.len(), 2);
964        assert_eq!(result[0].0, 10);
965        assert_eq!(result[1].0, 11);
966        // Verify partition expressions are serialized
967        assert!(!result[0].1.is_empty());
968        assert!(!result[1].1.is_empty());
969    }
970
971    #[tokio::test]
972    async fn test_build_plan_reserves_numbers_before_region_creation() {
973        let env = TestingEnv::new();
974        let table_id = 1024;
975        let routes = create_current_region_routes(table_id, &[1]);
976        env.create_physical_table_metadata_for_repartition(
977            table_id,
978            routes.clone(),
979            test_region_wal_options(&[1]),
980        )
981        .await;
982        let mut ctx = new_parent_context(&env, Arc::new(MockDatanodeManager::new(())), table_id);
983        let mut build = BuildPlan {
984            plan_entries: vec![create_allocation_plan_entry(
985                table_id,
986                &[1],
987                &[(0, 50), (50, 100), (100, 150)],
988            )],
989        };
990        // Replaying Build after a crash before the procedure checkpoint only
991        // skips numbers. Neither attempt has published routes or created regions.
992        for first in [2, 4] {
993            build
994                .next(&mut ctx, &TestingEnv::procedure_context())
995                .await
996                .unwrap();
997            assert_eq!(
998                ctx.persistent_ctx.plans[0].allocated_region_ids,
999                [
1000                    RegionId::new(table_id, first),
1001                    RegionId::new(table_id, first + 1),
1002                ]
1003            );
1004            let current = ctx.get_table_route_value().await.unwrap();
1005            assert_eq!(current.region_routes().unwrap(), &routes);
1006            assert_eq!(current.max_region_number().unwrap(), first + 1);
1007        }
1008        let previous = ctx.get_table_route_value().await.unwrap();
1009        let mut build = BuildPlan {
1010            plan_entries: vec![create_allocation_plan_entry(table_id, &[1], &[(0, 100)])],
1011        };
1012        let (next, _) = build
1013            .next(&mut ctx, &TestingEnv::procedure_context())
1014            .await
1015            .unwrap();
1016        assert!(next.as_any().is::<Dispatch>());
1017        let current = ctx.get_table_route_value().await.unwrap();
1018        assert_eq!(previous.get_raw_bytes(), current.get_raw_bytes());
1019    }
1020
1021    #[tokio::test]
1022    async fn test_execute_plan_uses_latest_table_route_after_lock() {
1023        let env = TestingEnv::new();
1024        let table_id = 1024;
1025        let original_region_routes = create_current_region_routes(table_id, &[1]);
1026        env.create_physical_table_metadata_for_repartition(
1027            table_id,
1028            original_region_routes,
1029            test_region_wal_options(&[1]),
1030        )
1031        .await;
1032
1033        let (sender, mut receiver) = mpsc::channel(1);
1034        let node_manager = Arc::new(MockDatanodeManager::new(DatanodeWatcher::new(sender)));
1035        let mut ctx = new_parent_context(&env, node_manager, table_id);
1036        ctx.persistent_ctx.plans = vec![RepartitionPlanEntry {
1037            group_id: Uuid::new_v4(),
1038            source_regions: vec![],
1039            target_regions: vec![create_target_region_descriptor(table_id, 3, "x", 0, 100)],
1040            allocated_region_ids: vec![RegionId::new(table_id, 3)],
1041            pending_deallocate_region_ids: vec![],
1042            transition_map: vec![],
1043            original_target_routes: vec![],
1044        }];
1045        let concurrent_region_route = create_current_region_routes(table_id, &[2])
1046            .into_iter()
1047            .next()
1048            .unwrap();
1049        let procedure_ctx = ProcedureContext {
1050            procedure_id: ProcedureId::random(),
1051            provider: Arc::new(ConcurrentTableRouteUpdateProvider {
1052                inner: MockContextProvider::default(),
1053                table_metadata_manager: env.table_metadata_manager.clone(),
1054                table_id,
1055                concurrent_region_route,
1056                region_wal_options: test_region_wal_options(&[1, 2]),
1057            }),
1058            event_context: None,
1059        };
1060        let mut state = ExecutePlan;
1061
1062        state.next(&mut ctx, &procedure_ctx).await.unwrap();
1063
1064        let (_, request) = receiver.recv().await.unwrap();
1065        let Some(Body::Create(create)) = request.body else {
1066            unreachable!()
1067        };
1068        assert!(create.requirements.unwrap().object_storage);
1069
1070        let region_ids = current_parent_region_routes(&ctx)
1071            .await
1072            .into_iter()
1073            .map(|route| route.region.id)
1074            .collect::<Vec<_>>();
1075        assert_eq!(
1076            region_ids,
1077            vec![
1078                RegionId::new(table_id, 1),
1079                RegionId::new(table_id, 2),
1080                RegionId::new(table_id, 3),
1081            ]
1082        );
1083    }
1084
1085    async fn check_execute_plan_skip_wal_provider(existing_wal_options: Option<WalOptions>) {
1086        let env = TestingEnv::new();
1087        let table_id = 1024;
1088        let routes = create_current_region_routes(table_id, &[1]);
1089        let mut table_info = new_test_table_info_with_name(table_id, "test_table");
1090        table_info.meta.column_ids = vec![0, 1, 2];
1091        table_info.meta.options.skip_wal = true;
1092        let stored_wal_options = existing_wal_options
1093            .clone()
1094            .map(|options| HashMap::from([(1, options)]))
1095            .unwrap_or_default();
1096        env.table_metadata_manager
1097            .create_table_metadata(
1098                table_info,
1099                TableRouteValue::physical(routes),
1100                stored_wal_options,
1101            )
1102            .await
1103            .unwrap();
1104
1105        let (sender, mut receiver) = mpsc::channel(1);
1106        let node_manager = Arc::new(MockDatanodeManager::new(DatanodeWatcher::new(sender)));
1107        let mut ctx = new_parent_context(&env, node_manager, table_id);
1108        if matches!(&existing_wal_options, Some(WalOptions::Kafka(_))) {
1109            ctx.wal_options_allocator = Arc::new(TestKafkaWalOptionsAllocator);
1110        }
1111        ctx.persistent_ctx.plans = vec![RepartitionPlanEntry {
1112            group_id: Uuid::new_v4(),
1113            source_regions: vec![],
1114            target_regions: vec![create_target_region_descriptor(table_id, 2, "x", 0, 100)],
1115            allocated_region_ids: vec![RegionId::new(table_id, 2)],
1116            pending_deallocate_region_ids: vec![],
1117            transition_map: vec![],
1118            original_target_routes: vec![],
1119        }];
1120        let mut state = ExecutePlan;
1121        state
1122            .next(&mut ctx, &TestingEnv::procedure_context())
1123            .await
1124            .unwrap();
1125
1126        let (_, request) = receiver.recv().await.unwrap();
1127        let Some(Body::Create(create)) = request.body else {
1128            unreachable!()
1129        };
1130        assert_eq!(
1131            Some("true"),
1132            create.options.get(SKIP_WAL_KEY).map(String::as_str)
1133        );
1134        let new_wal_options: WalOptions =
1135            serde_json::from_str(create.options.get(WAL_OPTIONS_KEY).unwrap()).unwrap();
1136        let expected = match &existing_wal_options {
1137            Some(WalOptions::Noop) => WalOptions::Noop,
1138            Some(WalOptions::Kafka(_)) => WalOptions::Kafka(KafkaWalOptions {
1139                topic: "new-topic".to_string(),
1140                initial_pruned_entry_id: Some(0),
1141            }),
1142            None | Some(WalOptions::RaftEngine) | Some(WalOptions::ObjectStore(_)) => {
1143                WalOptions::RaftEngine
1144            }
1145        };
1146        assert_eq!(expected, new_wal_options);
1147        let route = ctx.get_table_route_value().await.unwrap();
1148        let wal_options = get_region_wal_options(&ctx.table_metadata_manager, &route, table_id)
1149            .await
1150            .unwrap();
1151        assert_eq!(Some(&expected), wal_options.get(&2));
1152        let legacy_default = WalOptions::RaftEngine;
1153        assert_eq!(
1154            Some(existing_wal_options.as_ref().unwrap_or(&legacy_default)),
1155            wal_options.get(&1)
1156        );
1157    }
1158
1159    #[tokio::test]
1160    async fn test_execute_plan_keeps_real_wal_provider_for_skipped_table() {
1161        check_execute_plan_skip_wal_provider(Some(WalOptions::RaftEngine)).await;
1162    }
1163
1164    #[tokio::test]
1165    async fn test_execute_plan_keeps_legacy_raft_provider_for_skipped_table() {
1166        check_execute_plan_skip_wal_provider(None).await;
1167    }
1168
1169    #[tokio::test]
1170    async fn test_execute_plan_keeps_kafka_wal_provider_for_skipped_table() {
1171        check_execute_plan_skip_wal_provider(Some(WalOptions::Kafka(KafkaWalOptions::new(
1172            "existing-topic".to_string(),
1173        ))))
1174        .await;
1175    }
1176
1177    #[tokio::test]
1178    async fn test_execute_plan_treats_object_store_as_real_wal_provider_for_skipped_table() {
1179        check_execute_plan_skip_wal_provider(Some(WalOptions::ObjectStore(
1180            ObjectStoreWalOptions::new("wal".to_string()),
1181        )))
1182        .await;
1183    }
1184
1185    #[tokio::test]
1186    async fn test_execute_plan_keeps_noop_for_table_created_without_wal() {
1187        check_execute_plan_skip_wal_provider(Some(WalOptions::Noop)).await;
1188    }
1189
1190    #[test]
1191    fn test_allocate_region_state_backward_compatibility() {
1192        // Arrange
1193        let serialized = r#"{"repartition_state":"AllocateRegion","plan_entries":[]}"#;
1194
1195        // Act
1196        let state: Box<dyn State> = serde_json::from_str(serialized).unwrap();
1197
1198        // Assert
1199        let allocate_region = state
1200            .as_any()
1201            .downcast_ref::<AllocateRegion>()
1202            .expect("expected AllocateRegion state");
1203        match allocate_region {
1204            AllocateRegion::Build(build_plan) => assert!(build_plan.plan_entries.is_empty()),
1205            AllocateRegion::Execute(_) => panic!("expected build plan"),
1206        }
1207    }
1208
1209    #[test]
1210    fn test_allocate_region_state_round_trip() {
1211        // Arrange
1212        let state: Box<dyn State> = Box::new(AllocateRegion::new(vec![]));
1213
1214        // Act
1215        let serialized = serde_json::to_string(&state).unwrap();
1216        let deserialized: Box<dyn State> = serde_json::from_str(&serialized).unwrap();
1217
1218        // Assert
1219        assert_eq!(
1220            serialized,
1221            r#"{"repartition_state":"AllocateRegion","Build":{"plan_entries":[]}}"#
1222        );
1223        let allocate_region = deserialized
1224            .as_any()
1225            .downcast_ref::<AllocateRegion>()
1226            .expect("expected AllocateRegion state");
1227        match allocate_region {
1228            AllocateRegion::Build(build_plan) => assert!(build_plan.plan_entries.is_empty()),
1229            AllocateRegion::Execute(_) => panic!("expected build plan"),
1230        }
1231    }
1232
1233    #[test]
1234    fn test_allocate_region_execute_state_round_trip() {
1235        // Arrange
1236        let state: Box<dyn State> = Box::new(AllocateRegion::Execute(ExecutePlan));
1237
1238        // Act
1239        let serialized = serde_json::to_string(&state).unwrap();
1240        let deserialized: Box<dyn State> = serde_json::from_str(&serialized).unwrap();
1241
1242        // Assert
1243        assert_eq!(
1244            serialized,
1245            r#"{"repartition_state":"AllocateRegion","Execute":null}"#
1246        );
1247        let allocate_region = deserialized
1248            .as_any()
1249            .downcast_ref::<AllocateRegion>()
1250            .expect("expected AllocateRegion state");
1251        match allocate_region {
1252            AllocateRegion::Execute(_) => {}
1253            AllocateRegion::Build(_) => panic!("expected execute plan"),
1254        }
1255    }
1256    #[test]
1257    fn test_collect_allocation_sources_use_target_overlap() {
1258        let table_id = 1024;
1259        let mut plan = RepartitionPlanEntry {
1260            group_id: Uuid::nil(),
1261            source_regions: vec![
1262                create_region_descriptor(table_id, 2, "x", 100, 200),
1263                create_region_descriptor(table_id, 1, "x", 0, 100),
1264            ],
1265            target_regions: vec![
1266                create_target_region_descriptor(table_id, 3, "x", 0, 50),
1267                create_target_region_descriptor(table_id, 4, "x", 50, 150),
1268                create_target_region_descriptor(table_id, 5, "x", 150, 200),
1269            ],
1270            allocated_region_ids: (3..=5).map(|n| RegionId::new(table_id, n)).collect(),
1271            pending_deallocate_region_ids: vec![],
1272            transition_map: vec![vec![1, 2], vec![0, 1]],
1273            original_target_routes: vec![],
1274        };
1275        let mut routes = create_current_region_routes(table_id, &[1, 2]);
1276        routes[0].leader_peer = Some(Peer::empty(10));
1277        routes[1].leader_peer = Some(Peer::empty(20));
1278        assert_eq!(
1279            collect_allocation_sources(&[plan.clone()], &routes),
1280            vec![
1281                (RegionId::new(table_id, 3), Some(10)),
1282                (RegionId::new(table_id, 4), Some(10)),
1283                (RegionId::new(table_id, 5), Some(20)),
1284            ]
1285        );
1286        // Source enumeration does not change the tie-break for overlapping targets.
1287        plan.source_regions.reverse();
1288        plan.transition_map.reverse();
1289        assert_eq!(
1290            collect_allocation_sources(std::slice::from_ref(&plan), &routes)[1],
1291            (RegionId::new(table_id, 4), Some(10))
1292        );
1293        plan.transition_map.clear();
1294        assert_eq!(
1295            collect_allocation_sources(std::slice::from_ref(&plan), &routes),
1296            (3..=5)
1297                .map(|number| (RegionId::new(table_id, number), Some(10)))
1298                .collect::<Vec<_>>()
1299        );
1300        plan.source_regions.clear();
1301        assert_eq!(
1302            collect_allocation_sources(&[plan], &routes),
1303            (3..=5)
1304                .map(|number| (RegionId::new(table_id, number), None))
1305                .collect::<Vec<_>>()
1306        );
1307    }
1308
1309    #[test]
1310    fn test_group_allocations_preserves_region_partition_mapping() {
1311        use common_meta::affinity::AffinityRequirements;
1312        let table_id = 1024;
1313        let requirements = |zone: &str| {
1314            AffinityRequirements::new(HashMap::from([("ZONE".into(), zone.into())])).unwrap()
1315        };
1316        let region_requirements = AllocationAffinity {
1317            requirements: vec![
1318                Some(requirements("a")),
1319                Some(requirements("b")),
1320                Some(requirements("a")),
1321            ],
1322            target_sources: HashMap::from([
1323                (RegionId::new(table_id, 1), 0),
1324                (RegionId::new(table_id, 2), 1),
1325                (RegionId::new(table_id, 3), 2),
1326            ]),
1327        };
1328        let regions = vec![
1329            (1, "p1".into()),
1330            (2, "p2".into()),
1331            (3, "p3".into()),
1332            (4, "p4".into()),
1333        ];
1334        let groups = group_allocations(table_id, &regions, &region_requirements);
1335        assert!(ptr::eq(
1336            groups[0].affinity.unwrap(),
1337            region_requirements.requirements[0].as_ref().unwrap(),
1338        ));
1339        assert!(!ptr::eq(
1340            region_requirements.requirements[0].as_ref().unwrap(),
1341            region_requirements.requirements[2].as_ref().unwrap(),
1342        ));
1343        assert_eq!(
1344            groups,
1345            vec![
1346                AllocationGroup {
1347                    affinity: region_requirements.requirements[0].as_ref(),
1348                    regions: vec![(1, "p1"), (3, "p3")],
1349                },
1350                AllocationGroup {
1351                    affinity: region_requirements.requirements[1].as_ref(),
1352                    regions: vec![(2, "p2")],
1353                },
1354                AllocationGroup {
1355                    affinity: None,
1356                    regions: vec![(4, "p4")],
1357                },
1358            ]
1359        );
1360    }
1361
1362    #[tokio::test]
1363    async fn test_execute_refreshes_affinity_on_retry() {
1364        use std::sync::Mutex;
1365        use std::sync::atomic::{AtomicUsize, Ordering};
1366
1367        use common_meta::affinity::AffinityResolver;
1368        use common_meta::error::{self as meta_error, Result as MetaResult};
1369        use common_meta::key::table_route::TableRouteKey;
1370        use common_meta::peer::PeerAllocator;
1371
1372        #[derive(Default)]
1373        struct ChangingResolver {
1374            calls: AtomicUsize,
1375        }
1376
1377        #[async_trait::async_trait]
1378        impl AffinityResolver for ChangingResolver {
1379            async fn resolve(
1380                &self,
1381                references: &[AffinityReference],
1382            ) -> MetaResult<Vec<Option<AffinityRequirements>>> {
1383                assert_eq!(
1384                    references,
1385                    &[
1386                        AffinityReference::Datanode(1),
1387                        AffinityReference::Datanode(2)
1388                    ]
1389                );
1390                let generation = self.calls.fetch_add(1, Ordering::Relaxed);
1391                Ok(references
1392                    .iter()
1393                    .map(|_| {
1394                        AffinityRequirements::new(HashMap::from([(
1395                            "ZONE".into(),
1396                            format!("zone-{generation}"),
1397                        )]))
1398                    })
1399                    .collect())
1400            }
1401        }
1402
1403        #[derive(Default)]
1404        struct RecordingAllocator(Mutex<Vec<Option<AffinityRequirements>>>);
1405
1406        #[async_trait::async_trait]
1407        impl PeerAllocator for RecordingAllocator {
1408            async fn alloc(&self, _num: usize, ctx: &PeerAllocContext) -> MetaResult<Vec<Peer>> {
1409                self.0.lock().unwrap().push(ctx.affinity.clone());
1410                meta_error::UnexpectedSnafu {
1411                    err_msg: "stop before creating regions",
1412                }
1413                .fail()
1414            }
1415        }
1416
1417        let env = TestingEnv::new();
1418        let table_id = 1024;
1419        let mut routes = create_current_region_routes(table_id, &[1, 2]);
1420        routes[1].leader_peer = Some(Peer::empty(2));
1421        env.create_physical_table_metadata_for_repartition(
1422            table_id,
1423            routes,
1424            test_region_wal_options(&[1, 2]),
1425        )
1426        .await;
1427        let (sender, _receiver) = mpsc::channel(1);
1428        let mut ctx = new_parent_context(
1429            &env,
1430            Arc::new(MockDatanodeManager::new(DatanodeWatcher::new(sender))),
1431            table_id,
1432        );
1433        let resolver = Arc::new(ChangingResolver::default());
1434        let allocator = Arc::new(RecordingAllocator::default());
1435        ctx.affinity_resolver = Some(resolver.clone());
1436        ctx.region_routes_allocator = allocator.clone();
1437        ctx.persistent_ctx.plans = vec![RepartitionPlanEntry {
1438            group_id: Uuid::nil(),
1439            source_regions: vec![
1440                create_region_descriptor(table_id, 1, "x", 0, 100),
1441                create_region_descriptor(table_id, 2, "x", 100, 200),
1442            ],
1443            target_regions: vec![
1444                create_target_region_descriptor(table_id, 3, "x", 0, 50),
1445                create_target_region_descriptor(table_id, 4, "x", 50, 100),
1446                create_target_region_descriptor(table_id, 5, "x", 100, 200),
1447            ],
1448            allocated_region_ids: (3..=5).map(|n| RegionId::new(table_id, n)).collect(),
1449            pending_deallocate_region_ids: vec![],
1450            transition_map: vec![vec![0, 1], vec![2]],
1451            original_target_routes: vec![],
1452        }];
1453        let procedure_ctx = ProcedureContext {
1454            procedure_id: ProcedureId::random(),
1455            provider: Arc::new(MockContextProvider::default()),
1456            event_context: None,
1457        };
1458        for _ in 0..2 {
1459            assert!(ExecutePlan.next(&mut ctx, &procedure_ctx).await.is_err());
1460        }
1461        assert_eq!(resolver.calls.load(Ordering::Relaxed), 2);
1462        assert_eq!(
1463            *allocator.0.lock().unwrap(),
1464            (0..2)
1465                .map(|generation| AffinityRequirements::new(HashMap::from([(
1466                    "ZONE".into(),
1467                    format!("zone-{generation}")
1468                ),])))
1469                .collect::<Vec<_>>()
1470        );
1471        // Without a resolver, allocation does not need source route metadata.
1472        // Removing it makes any accidental lookup fail before the recording allocator.
1473        ctx.affinity_resolver = None;
1474        env.kv_backend
1475            .delete(TableRouteKey::new(table_id).to_string().as_bytes(), false)
1476            .await
1477            .unwrap();
1478        assert!(ExecutePlan.next(&mut ctx, &procedure_ctx).await.is_err());
1479        assert_eq!(resolver.calls.load(Ordering::Relaxed), 2);
1480        let allocations = allocator.0.lock().unwrap();
1481        assert_eq!(allocations.len(), 3);
1482        assert_eq!(allocations.last(), Some(&None));
1483    }
1484
1485    #[tokio::test]
1486    async fn test_resolved_affinity_preserves_source_associations() {
1487        use common_meta::affinity::AffinityResolver;
1488        use common_meta::error::Result as MetaResult;
1489
1490        struct Resolver(Vec<Option<AffinityRequirements>>);
1491
1492        #[async_trait::async_trait]
1493        impl AffinityResolver for Resolver {
1494            async fn resolve(
1495                &self,
1496                references: &[AffinityReference],
1497            ) -> MetaResult<Vec<Option<AffinityRequirements>>> {
1498                assert_eq!(
1499                    references,
1500                    &[
1501                        AffinityReference::Datanode(2),
1502                        AffinityReference::Datanode(1)
1503                    ]
1504                );
1505                Ok(self.0.clone())
1506            }
1507        }
1508
1509        let env = TestingEnv::new();
1510        let table_id = 1024;
1511        let mut routes = create_current_region_routes(table_id, &[1, 2]);
1512        routes[1].leader_peer = Some(Peer::empty(2));
1513        env.create_physical_table_metadata_for_repartition(
1514            table_id,
1515            routes,
1516            test_region_wal_options(&[1, 2]),
1517        )
1518        .await;
1519        let (sender, _receiver) = mpsc::channel(1);
1520        let mut ctx = new_parent_context(
1521            &env,
1522            Arc::new(MockDatanodeManager::new(DatanodeWatcher::new(sender))),
1523            table_id,
1524        );
1525        ctx.persistent_ctx.plans = vec![RepartitionPlanEntry {
1526            group_id: Uuid::nil(),
1527            source_regions: vec![
1528                create_region_descriptor(table_id, 1, "x", 0, 100),
1529                create_region_descriptor(table_id, 2, "x", 100, 200),
1530            ],
1531            target_regions: vec![
1532                create_target_region_descriptor(table_id, 3, "x", 100, 200),
1533                create_target_region_descriptor(table_id, 4, "x", 0, 50),
1534                create_target_region_descriptor(table_id, 5, "x", 50, 100),
1535            ],
1536            allocated_region_ids: (3..=5).map(|n| RegionId::new(table_id, n)).collect(),
1537            pending_deallocate_region_ids: vec![],
1538            transition_map: vec![vec![1, 2], vec![0]],
1539            original_target_routes: vec![],
1540        }];
1541        let a = AffinityRequirements::new(HashMap::from([("ZONE".into(), "a".into())])).unwrap();
1542        let b = AffinityRequirements::new(HashMap::from([("ZONE".into(), "b".into())])).unwrap();
1543        assert!(matches!(
1544            resolve_allocation_affinity(&ctx, &Resolver(vec![None, Some(a.clone())])).await,
1545            Err(error::Error::Unexpected { .. })
1546        ));
1547        ctx.affinity_fallback = AffinityFallback::Unconstrained;
1548        for (resolved, expected) in [
1549            (
1550                vec![Some(b.clone()), Some(a.clone())],
1551                HashMap::from([
1552                    (RegionId::new(table_id, 3), b.clone()),
1553                    (RegionId::new(table_id, 4), a.clone()),
1554                    (RegionId::new(table_id, 5), a.clone()),
1555                ]),
1556            ),
1557            (
1558                vec![None, Some(a.clone())],
1559                HashMap::from([
1560                    (RegionId::new(table_id, 4), a.clone()),
1561                    (RegionId::new(table_id, 5), a),
1562                ]),
1563            ),
1564            (
1565                vec![Some(b.clone()), None],
1566                HashMap::from([(RegionId::new(table_id, 3), b)]),
1567            ),
1568        ] {
1569            let affinity = resolve_allocation_affinity(&ctx, &Resolver(resolved))
1570                .await
1571                .unwrap();
1572            assert_eq!(affinity.requirements.len(), 2);
1573            assert_eq!(
1574                affinity.target_sources[&RegionId::new(table_id, 4)],
1575                affinity.target_sources[&RegionId::new(table_id, 5)]
1576            );
1577            let actual = affinity
1578                .target_sources
1579                .iter()
1580                .filter_map(|(target, index)| {
1581                    affinity.requirements[*index]
1582                        .as_ref()
1583                        .map(|requirements| (*target, requirements))
1584                })
1585                .collect::<HashMap<_, _>>();
1586            if let Some(first) = actual.get(&RegionId::new(table_id, 4)) {
1587                let second = actual[&RegionId::new(table_id, 5)];
1588                assert!(ptr::eq(*first, second));
1589            }
1590            assert_eq!(
1591                actual,
1592                expected
1593                    .iter()
1594                    .map(|(target, requirements)| (*target, requirements))
1595                    .collect()
1596            );
1597        }
1598    }
1599
1600    #[tokio::test]
1601    async fn test_missing_source_leader_requires_explicit_fallback() {
1602        use common_meta::error::Result as MetaResult;
1603
1604        struct Resolver;
1605
1606        #[async_trait::async_trait]
1607        impl AffinityResolver for Resolver {
1608            async fn resolve(
1609                &self,
1610                references: &[AffinityReference],
1611            ) -> MetaResult<Vec<Option<AffinityRequirements>>> {
1612                assert!(references.is_empty());
1613                Ok(vec![])
1614            }
1615        }
1616
1617        let env = TestingEnv::new();
1618        let table_id = 1024;
1619        let mut routes = create_current_region_routes(table_id, &[1]);
1620        routes[0].leader_peer = None;
1621        env.create_physical_table_metadata_for_repartition(
1622            table_id,
1623            routes,
1624            test_region_wal_options(&[1]),
1625        )
1626        .await;
1627        let mut ctx = new_parent_context(&env, Arc::new(MockDatanodeManager::new(())), table_id);
1628        ctx.persistent_ctx.plans = vec![RepartitionPlanEntry {
1629            group_id: Uuid::nil(),
1630            source_regions: vec![create_region_descriptor(table_id, 1, "x", 0, 100)],
1631            target_regions: vec![create_target_region_descriptor(table_id, 2, "x", 0, 100)],
1632            allocated_region_ids: vec![RegionId::new(table_id, 2)],
1633            pending_deallocate_region_ids: vec![],
1634            transition_map: vec![vec![0]],
1635            original_target_routes: vec![],
1636        }];
1637        assert!(matches!(
1638            resolve_allocation_affinity(&ctx, &Resolver).await,
1639            Err(error::Error::Unexpected { .. })
1640        ));
1641        ctx.affinity_fallback = AffinityFallback::Unconstrained;
1642        assert!(
1643            resolve_allocation_affinity(&ctx, &Resolver)
1644                .await
1645                .unwrap()
1646                .target_sources
1647                .is_empty()
1648        );
1649    }
1650}