Flexible Migration in Blue-Green Deployments within a Fixed Cost (PolyPod)

A high-performance C++ solver with Python bindings for optimizing tenant migration in blue-green deployments, based on the research paper Flexible Migration in Blue-Green Deployments within a Fixed Cost.

>> Live Demo <<

📚 Resources

• Paper (PDF): Local Copy
• Paper (Online): ACM Digital Library / ResearchGate

💡 Concepts

This solver implements the "PolyPod" concept, which balances migration flexibility with resource costs. It addresses the problem of migrating $T$ tenants from an old version (Blue) to a new version (Green) under a fixed total capacity $S$.

Modes

The solver supports two migration strategies discussed in the paper:

1. In-Place Migration (s=1):

   • Corresponds to Opt-in No-Restart.
   • Resources are dynamically adjusted without restarting the container.
   • Efficiency: Higher. Can typically host more tenants or migrate faster.
   • Constraint: u2*m <= (u1-u2)*t + (S - (b1 + u1*T + b2))

2. Recreate Migration (s=2):

   • Corresponds to Opt-out / Rolling Upgrade.
   • Pods must be restarted (or new ones created) to change resource allocation.
   • Efficiency: Lower. Incurs a higher "surge cost" because both old and new resources might temporarily coexist during the transition.
   • Constraint: u2*m <= (u1 - 2*u2)*t + (S - (b1 + u1*T + b2)) (simplified approximation)

Variables

• $S$: Total system capacity (e.g., CPU millicores).
• $T$: Total number of tenants to migrate.
• $u_1$: Unit resource cost per tenant for the old version.
• $u_2$: Unit resource cost per tenant for the new version.
• $b_1, b_2$: Base overhead for old and new versions (optional).

🛠 Installation

This project is managed with uv.

Prerequisites

• Python 3.8+
• C++ Compiler (GCC/Clang/MSVC) supporting C++11
• uv (Universal Python Package Manager)

Setup

# 1. Install uv (if not already installed)
curl -LsSf https://astral.sh/uv/install.sh | sh

# 2. Clone the repository
git clone <your-repo-url>
cd polypod-solver

# 3. Create environment and install dependencies
uv venv
uv pip install -e .

🚀 Usage

Quick Start

import polypod

# Define System Parameters
# S=1750 capacity, u1=90 (old cost), u2=65 (new cost)
params = polypod.PolyPodParameters(S=1750, b1=0, u1=90, b2=0, u2=65)

# 1. Create a Solver (Recreate Mode)
solver = polypod.create_polypod(params, T=10, mode="recreate")

# 2. Find Shortest Migration Schedule
solution = solver.find_shortest_solution()
print(f"Migration Waves: {solution}")
# Output: e.g., [5, 5] -> Migrate 5 tenants, then another 5.

# 3. Iterate All Valid Solutions (BFS)
solver.bfs_reset()
while True:
    sol = solver.bfs_next_solution()
    if not sol: break
    print(f"Found solution: {sol}")

Advanced Usage: Exploring Capacity

Find the maximum number of tenants ($T$) that can be supported given the fixed capacity.

# Create specific solver type directly
solver = polypod.InPlacePolyPod(params, T=1)

# Find max T
schedule = solver.find_maximum_T_with_solution()
max_tenants = solver.getT()

print(f"Max Tenants: {max_tenants}")
print(f"Schedule: {schedule}")

🧪 Testing

Run the included test script to verify the installation and solver logic:

uv run python test_polypod.py