Pluggable Tree Strategies & Zero Downtime Migrations

This document explains the architecture of the pluggable tree strategy system in Framework M, how recursive CTEs are leveraged, and how to safely migrate tree strategies in a production environment without downtime.

---

Architecture Design

Framework M uses a Strategy Pattern to support multiple tree representations transparently. All tree operations are abstracted through a uniform interface:

Strategy Resolution

When a repository operation (insert, update, or fetch tree) is performed, TreeManager inspects the DocType's mixin hierarchy:

1. If the DocType inherits from NestedSetMixin, the NestedSetTreeStrategy is instantiated.
2. If it inherits from AdjacencyListMixin, the AdjacencyListTreeStrategy is instantiated.

This decoupling guarantees that the generic repository and the controller routes do not need to concern themselves with the specifics of tree bounds shifting or recursive SQL generation.

---

Recursive SQL CTEs in Adjacency List

Unlike the Nested Set model, which encodes hierarchy bounds directly in each row via lft and rgt integers, the Adjacency List model relies entirely on parent pointers (parent_value).

To query subtrees or validate relationships efficiently in SQL without making multiple roundtrips, the framework generates Recursive Common Table Expressions (CTEs).

1. Querying a Subtree

To fetch a node and all of its descendants recursively, the strategy constructs a recursive SELECT query:

• Anchor Member: Selects the target parent node by ID.
• Recursive Member: Joins the target table back to the anchor on child.parent_value = parent.id.

WITH RECURSIVE tree_cte AS (
    -- Anchor
    SELECT id, parent_value, name, is_group
    FROM todo
    WHERE id = :parent_id

    UNION ALL

    -- Recursive Join
    SELECT t.id, t.parent_value, t.name, t.is_group
    FROM todo t
    INNER JOIN tree_cte ON t.parent_value = tree_cte.id
)
SELECT id, parent_value, name, is_group FROM tree_cte;

2. Preventing Circular Dependencies (The Ancestor Trap)

When updating a node's parent, the framework must ensure the new parent is not a child (or deeper descendant) of the node itself. To check this:

• The strategy runs a CTE query starting from the proposed new parent and recursively tracing upward to all its ancestors.
• If the node's own ID appears in the ancestor list, a loop is detected, and a ValueError is raised.

---

Zero Downtime Migrations (ZDM)

Migrating an active production database table from one tree strategy to another involves schema modifications (adding or dropping lft/rgt columns) and data backfills (generating nested set bounds or rebuilding parent pointers).

warning

• Rebuilding bounds synchronously locks the entire table, causing request queues to back up.
• High-concurrency environments will experience deadlocks and OOMs.
• Schema changes and data backfills must be performed as asynchronous, multi-phase operations.

Scenario A: Migrating from Adjacency List to Nested Set

To switch a table from AdjacencyListMixin to NestedSetMixin in production:

1. Phase 1: Schema Extension (Additive)

   • Create an Alembic migration to add nullable lft and rgt columns to the table.
   • Run the migration. The application continues running on the old code (using the adjacency list logic).

2. Phase 2: Asynchronous Data Backfill

   • Write a background worker script (using Taskiq) to calculate and backfill lft and rgt bounds in chunks or within a controlled transaction:

     # Run as a background task to avoid blocking the web server
     async def backfill_nested_set_bounds():
         # Calculate lft/rgt bounds based on parent_value hierarchy
         # and update rows in small batches or with an exclusive table lock
         # during a low-traffic window.

3. Phase 3: Code Deployment & Constraints

   • Update the DocType in python to inherit from NestedSetMixin instead of AdjacencyListMixin.
   • Run m migrate sync to register the schema shift.
   • Deploy the new application version. The framework now uses NestedSetTreeStrategy for all reads and writes.
   • Run a final Alembic patch to set NOT NULL constraints on lft and rgt columns once all rows have been backfilled.

---

Scenario B: Migrating from Nested Set to Adjacency List

To switch a table from NestedSetMixin to AdjacencyListMixin in production:

1. Phase 1: Code Update

   • Update the DocType class to inherit from AdjacencyListMixin instead of NestedSetMixin.
   • Deploy the code. The application immediately switches to using recursive CTEs. lft and rgt columns are ignored by the application but still exist in the database.

2. Phase 2: Cleanup (Schema Reduction)

   • After confirming the application is stable under the new strategy, generate an Alembic migration to drop the lft and rgt columns.
   • Run the migration. This frees up database pages and reduces storage overhead.