SingleRandomStratified

Move Type: Basic Complexity: O(strata × sample_size) instead of O(containers)

Sample containers from stratified groups (scope items) for more intelligent exploration. Reduces search space while maintaining coverage across different container types.

Overview

SingleRandomStratified evaluates single object moves but samples destination containers in a stratified manner - taking samples from different groups (scope items) rather than uniformly at random. This ensures coverage across different container types (e.g., small, medium, large) without exhaustive search.

Use when:

Containers naturally group into strata (e.g., by size, region, type)
Want balanced exploration across container types
Problem is large (>10K containers)
Random sampling alone gives poor coverage

Avoid when:

Containers are homogeneous (no natural strata)
Problem is small (<1K containers, use Single)
Don't have meaningful scope hierarchy
Need exhaustive search

Quick Example

Python
C++

# Stratified sampling across regions
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomStratifiedMoveTypeSpec(
                    destinationsToExplore=DestinationsToExploreOptions(
                        moveToCurrentScopeItem=MoveToCurrentScopeItemSpec(
                            scopeNameForExploringMovesToCurrentScopeItem="region",
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=100,  # 100 samples per region
                    ),
                ),
            ]
        )
    )
)

void quickExample() {
  // Stratified sampling across regions
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("task");
  solver.setContainerName("host");

  // Setup problem data before configuring solver spec
  solver.setAssignment(
      std::map<std::string, std::vector<std::string>>{
          {"host0", {"task0", "task1"}},
          {"host1", {}},
          {"host2", {"task2"}},
          {"host3", {}},
      });

  solver.addScope(
      "region",
      std::map<std::string, std::string>{
          {"host0", "region0"},
          {"host1", "region0"},
          {"host2", "region1"},
          {"host3", "region1"},
      });

  const std::map<std::string, double> cpu = {
      {"task0", 1.0},
      {"task1", 1.0},
      {"task2", 1.0},
  };
  solver.addObjectDimension("cpu", cpu);

  BalanceSpec balanceSpec;
  balanceSpec.name() = "balance-cpu";
  balanceSpec.scope() = "host";
  balanceSpec.dimension() = "cpu";
  solver.addGoal(balanceSpec, 1.0);

  LocalSearchSolverSpec solverSpec;

  SingleRandomStratifiedMoveTypeSpec stratifiedSpec;

  MoveToCurrentScopeItemSpec moveSpec;
  moveSpec.scopeNameForExploringMovesToCurrentScopeItem() = "region";

  DestinationsToExploreOptions destOptions;
  destOptions.moveToCurrentScopeItem() = moveSpec;
  stratifiedSpec.destinationsToExplore() = destOptions;

  SampleSize sampleSize;
  sampleSize.defaultSampleSize() = 100; // 100 samples per region
  stratifiedSpec.stratifiedSampleSize() = sampleSize;

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleRandomStratifiedMoveTypeSpec() =
      stratifiedSpec;

  solver.addSolver(solverSpec);

Parameters

Parameter	Type	Required	Default	Description
`destinationsToExplore`	DestinationsToExploreOptions	Yes	-	Defines strata (scope items) for sampling
`stratifiedSampleSize`	SampleSize	Yes	-	Sample size per stratum

Parameter Details

destinationsToExplore:

Defines the stratification - how to group containers
Typically uses moveToCurrentScopeItem to stratify by scope
Example: region scope creates strata by region

stratifiedSampleSize:

Number of containers to sample per stratum
Uses SampleSize struct with defaultSampleSize
Total samples = sample_size × number_of_strata

How It Works

Given a hot container and object to move:

Define strata: Group containers by scope (e.g., region, size class)
Sample per stratum: Take sample_size random containers from each stratum
Evaluate samples: Test moving object to each sampled container
Apply best: Apply the move that improves objective most

Visual Example

System with 30,000 containers stratified by size into 5 groups:

Stratum 1         Stratum 2         Stratum 3         Stratum 4         Stratum 5
+-------------+   +-------------+   +-------------+   +-------------+   +-------------+
| Very Small  |   | Small       |   | Medium      |   | Large       |   | Very Large  |
| 6000 cont.  |   | 6000 cont.  |   | 6000 cont.  |   | 6000 cont.  |   | 6000 cont.  |
|             |   |             |   |             |   |             |   |             |
| Sample 100  |   | Sample 100  |   | Sample 100  |   | Sample 100  |   | Sample 100  |
+-------------+   +-------------+   +-------------+   +-------------+   +-------------+

Total evaluations: 100 × 5 = 500 (instead of 30,000!)
Coverage: Guaranteed samples from each size class

Comparison with Random Sampling

Aspect	Uniform Random	Stratified Random
Sampling	Random from all containers	Random per stratum
Coverage	May miss rare types	Guarantees coverage
Bias	Toward common types	Balanced across types
Use case	Homogeneous containers	Heterogeneous containers

Complexity

Moves evaluated per iteration: O(S × K)

Where:

S = sample size per stratum (stratifiedSampleSize)
K = number of strata (scope items)

Example - Large stratified problem:

Total containers: 30,000
Strata (regions): 5
Sample per stratum: 100
Moves evaluated: 100 × 5 = 500 (vs 30,000 for full Single)
Speedup: 60x

Example - Very large problem:

Total containers: 100,000
Strata (regions): 10
Sample per stratum: 50
Moves evaluated: 50 × 10 = 500 (vs 100,000 for full Single)
Speedup: 200x

Usage Patterns

Region-Based Stratification

Sample across regions for coverage:

Python
C++

# Ensure coverage across all regions
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomStratifiedMoveTypeSpec(
                    destinationsToExplore=DestinationsToExploreOptions(
                        moveToCurrentScopeItem=MoveToCurrentScopeItemSpec(
                            scopeNameForExploringMovesToCurrentScopeItem="region",
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=50,  # Sample 50 containers per region
                    ),
                ),
            ]
        )
    )
)

void regionStratified() {
  // Ensure coverage across all regions
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

  SingleRandomStratifiedMoveTypeSpec stratifiedSpec;

  MoveToCurrentScopeItemSpec moveSpec;
  moveSpec.scopeNameForExploringMovesToCurrentScopeItem() = "region";

  DestinationsToExploreOptions destOptions;
  destOptions.moveToCurrentScopeItem() = moveSpec;
  stratifiedSpec.destinationsToExplore() = std::move(destOptions);

  SampleSize sampleSize;
  sampleSize.defaultSampleSize() = 50; // Sample 50 containers per region
  stratifiedSpec.stratifiedSampleSize() = std::move(sampleSize);

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleRandomStratifiedMoveTypeSpec() =
      stratifiedSpec;

  solver.addSolver(solverSpec);

Size-Based Stratification

Ensure coverage across container sizes:

Python
C++

# Stratify by container size class
# Assumes containers are organized into size-based scope items
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomStratifiedMoveTypeSpec(
                    destinationsToExplore=DestinationsToExploreOptions(
                        moveToCurrentScopeItem=MoveToCurrentScopeItemSpec(
                            scopeNameForExploringMovesToCurrentScopeItem="size_class",
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=100,  # 100 samples per size class
                    ),
                ),
            ]
        )
    )
)

void sizeStratified() {
  // Stratify by container size class
  // Assumes containers are organized into size-based scope items
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

  SingleRandomStratifiedMoveTypeSpec stratifiedSpec;

  MoveToCurrentScopeItemSpec moveSpec;
  moveSpec.scopeNameForExploringMovesToCurrentScopeItem() = "size_class";

  DestinationsToExploreOptions destOptions;
  destOptions.moveToCurrentScopeItem() = moveSpec;
  stratifiedSpec.destinationsToExplore() = destOptions;

  SampleSize sampleSize;
  sampleSize.defaultSampleSize() = 100; // 100 samples per size class
  stratifiedSpec.stratifiedSampleSize() = sampleSize;

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleRandomStratifiedMoveTypeSpec() =
      stratifiedSpec;

  solver.addSolver(solverSpec);

Large-Scale with Stratification

Very large problems with stratification:

Python
C++

# Large-scale: 100K containers across 10 regions
# Sample 50 per region = 500 total evaluations
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomStratifiedMoveTypeSpec(
                    destinationsToExplore=DestinationsToExploreOptions(
                        moveToCurrentScopeItem=MoveToCurrentScopeItemSpec(
                            scopeNameForExploringMovesToCurrentScopeItem="region",
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=50,  # Small sample, many strata
                    ),
                ),
            ]
        )
    )
)

void largeScale() {
  // Large-scale: 100K containers across 10 regions
  // Sample 50 per region = 500 total evaluations
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

  SingleRandomStratifiedMoveTypeSpec stratifiedSpec;

  MoveToCurrentScopeItemSpec moveSpec;
  moveSpec.scopeNameForExploringMovesToCurrentScopeItem() = "region";

  DestinationsToExploreOptions destOptions;
  destOptions.moveToCurrentScopeItem() = moveSpec;
  stratifiedSpec.destinationsToExplore() = destOptions;

  SampleSize sampleSize;
  sampleSize.defaultSampleSize() = 50; // Small sample, many strata
  stratifiedSpec.stratifiedSampleSize() = sampleSize;

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleRandomStratifiedMoveTypeSpec() =
      stratifiedSpec;

  solver.addSolver(solverSpec);

Adaptive Sample Size

Tune sample size by stratum:

Python
C++

# Start with small samples, increase later
# Stage 1: Quick exploration
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomStratifiedMoveTypeSpec(
                    destinationsToExplore=DestinationsToExploreOptions(
                        moveToCurrentScopeItem=MoveToCurrentScopeItemSpec(
                            scopeNameForExploringMovesToCurrentScopeItem="region",
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=25,  # Quick initial pass
                    ),
                ),
            ]
        )
    )
)

# Stage 2: Refined search
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomStratifiedMoveTypeSpec(
                    destinationsToExplore=DestinationsToExploreOptions(
                        moveToCurrentScopeItem=MoveToCurrentScopeItemSpec(
                            scopeNameForExploringMovesToCurrentScopeItem="region",
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=100,  # More thorough
                    ),
                ),
                SingleMoveTypeSpec(),  # Final exhaustive pass
            ]
        )
    )
)

void adaptiveSample() {
  // Start with small samples, increase later
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  // Stage 1: Quick exploration
  LocalSearchSolverSpec stage1;

  SingleRandomStratifiedMoveTypeSpec stratifiedSpec1;

  MoveToCurrentScopeItemSpec moveSpec1;
  moveSpec1.scopeNameForExploringMovesToCurrentScopeItem() = "region";

  DestinationsToExploreOptions destOptions1;
  destOptions1.moveToCurrentScopeItem() = moveSpec1;
  stratifiedSpec1.destinationsToExplore() = std::move(destOptions1);

  SampleSize sampleSize1;
  sampleSize1.defaultSampleSize() = 25; // Quick initial pass
  stratifiedSpec1.stratifiedSampleSize() = std::move(sampleSize1);

  stage1.moveTypeList()->emplace_back();
  stage1.moveTypeList()->back().singleRandomStratifiedMoveTypeSpec() =
      stratifiedSpec1;

  solver.addSolver(stage1);

  // Stage 2: Refined search
  LocalSearchSolverSpec stage2;

  SingleRandomStratifiedMoveTypeSpec stratifiedSpec2;

  MoveToCurrentScopeItemSpec moveSpec2;
  moveSpec2.scopeNameForExploringMovesToCurrentScopeItem() = "region";

  DestinationsToExploreOptions destOptions2;
  destOptions2.moveToCurrentScopeItem() = moveSpec2;
  stratifiedSpec2.destinationsToExplore() = std::move(destOptions2);

  SampleSize sampleSize2;
  sampleSize2.defaultSampleSize() = 100; // More thorough
  stratifiedSpec2.stratifiedSampleSize() = std::move(sampleSize2);

  stage2.moveTypeList()->emplace_back();
  stage2.moveTypeList()->back().singleRandomStratifiedMoveTypeSpec() =
      stratifiedSpec2;

  // Add Single for final exhaustive pass
  stage2.moveTypeList()->emplace_back();
  stage2.moveTypeList()->back().singleMoveTypeSpec() = SingleMoveTypeSpec{};

  solver.addSolver(stage2);

Performance Characteristics

Stratification Benefit

Strata	Sample/Stratum	Total Samples	Total Containers	Speedup	Coverage
5	100	500	30K	60x	Excellent
10	50	500	100K	200x	Excellent
20	25	500	100K	200x	Good
1	500	500	30K	60x	Poor (no stratification)

Key insight: More strata with smaller samples often better than fewer strata with large samples.

When Does It Help?

SingleRandomStratified helps when:

Heterogeneous containers: Different types/sizes/regions
Need coverage: Important to explore all container types
Large scale: Too many containers for exhaustive search
Scope hierarchy exists: Natural stratification available
Biased objectives: Some container types heavily preferred

SingleRandomStratified does NOT help when:

Homogeneous containers: All similar, no natural grouping
Small problems: Overhead not worth it
No scope hierarchy: Can't define meaningful strata
Equal sampling sufficient: Uniform random works fine

Comparison with Variants

Move Type	Sampling Strategy	Coverage	Use Case
Single	Exhaustive	Complete	Small problems
SingleFast	Early exit	Variable	Medium problems
SingleRandomBatches	Random batches	Uniform random	Large + multi-core
SingleRandomStratified	Stratified random	Balanced across types	Large + heterogeneous
SingleColdestStratified	Coldest-first per stratum	Balanced, greedy	Capacity-focused
SingleRandomObjectStratified	Stratified objects	Object diversity	Object stratification

Decision tree:

Small problem (<1K containers) → Single
Large + homogeneous → SingleRandomBatches
Large + heterogeneous → SingleRandomStratified
Large + capacity focus → SingleColdestStratified

Troubleshooting

Problem: Poor solution quality despite stratification

Diagnosis: Sample size too small per stratum OR stratification not meaningful

Solutions:

Increase stratifiedSampleSize
Verify scope hierarchy creates meaningful groups
Check if containers vary significantly within strata
Try different stratification (different scope)
Combine with Single for final refinement

Problem: Not seeing speedup vs uniform sampling

Diagnosis: Containers are homogeneous OR too few strata

Solutions:

Check if containers naturally group by scope
May not need stratification (use SingleRandomBatches)
Verify number of strata is reasonable (5-20 ideal)
Ensure strata have balanced sizes

Problem: Missing good moves in small strata

Diagnosis: Some strata have few containers but small sample size

Solutions:

Increase sample size for small strata
Consider stratum size when setting samples
Use per-object sample size overrides
May need different stratification approach

Problem: Non-deterministic results

Diagnosis: Random sampling produces different results

Solutions:

Set randomSeed in LocalSearchSolverSpec
Increase sample size for stability
Run multiple times and pick best
Accept variance as trade-off for speed

Choosing Stratification

Good stratification characteristics:

Meaningful groups: Containers in same stratum are similar
Balanced sizes: Strata have roughly equal number of containers
Diverse outcomes: Moving to different strata has different effects
Reasonable count: 5-20 strata ideal

Common stratification strategies:

Geographic: Region, datacenter, rack
Capacity: Size classes (small/medium/large)
Type: Container type, tier, priority
Load: Current utilization bins

Example scope hierarchies:

region > datacenter > rack > container
tier > container_type > container
size_class > region > container

Stratified variants:

SingleRandomStratified - Random sampling per stratum (this)
SingleColdestStratified - Coldest-first per stratum
SingleRandomObjectStratified - Stratify objects instead

Sampling alternatives:

Single - Full exploration (no sampling)
SingleRandomBatches - Uniform random sampling
SingleFast - Early exit

Use together:

SingleRandomStratified for quick improvement with coverage
Single for final refinement
Combine with Swap for capacity constraints

Source Code

Thrift definition: interface/thrift/SolverSpecs.thrift:616
Implementation: solver/moves/SingleRandomStratifiedMoveType.h
Tests: solver/moves/tests/

Next Steps

Try SingleColdestStratified for capacity-focused stratification
Learn about SingleRandomObjectStratified for object stratification
Review Scopes and Partitions for hierarchy design
See Move Types Overview for choosing move types

Overview​

Quick Example​

Parameters​

Parameter Details​

How It Works​

Visual Example​

Comparison with Random Sampling​

Complexity​

Usage Patterns​

Region-Based Stratification​

Size-Based Stratification​

Large-Scale with Stratification​

Adaptive Sample Size​

Performance Characteristics​

Stratification Benefit​

When Does It Help?​

Comparison with Variants​

Troubleshooting​

Problem: Poor solution quality despite stratification​

Problem: Not seeing speedup vs uniform sampling​

Problem: Missing good moves in small strata​

Problem: Non-deterministic results​

Choosing Stratification​

Related Move Types​

Source Code​

Next Steps​

Overview

Quick Example

Parameters

Parameter Details

How It Works

Visual Example

Comparison with Random Sampling

Complexity

Usage Patterns

Region-Based Stratification

Size-Based Stratification

Large-Scale with Stratification

Adaptive Sample Size

Performance Characteristics

Stratification Benefit

When Does It Help?

Comparison with Variants

Troubleshooting

Problem: Poor solution quality despite stratification

Problem: Not seeing speedup vs uniform sampling

Problem: Missing good moves in small strata

Problem: Non-deterministic results

Choosing Stratification

Related Move Types

Source Code

Next Steps