StackSaga Cassandra Recovery Directory Caching & Calculations Guide

1. Executive Overview

In StackSaga’s Cassandra reactive architecture, recovery transactions are discovered through a 5-tier hierarchical active directory:

es_days_by_year                             ← Tier 1: Which calendar days have pending work?
  └── es_recovery_windows_by_day            ← Tier 2: Which UTC minute windows on that day?
        └── es_instances_by_recovery_window ← Tier 3: Which pod instances wrote work in that window?
              └── es_buckets_by_instance    ← Tier 4: Which bucket partitions did that pod create?
                    └── es_recovery_transactions_by_instance ← Tier 5: The actual transaction pointers.

1.1. The 5x Write Amplification Hazard

In a naive implementation, every single transaction write would execute 5 database write statements (one per tier):

Tx #1  ──> Write Tier 1, Write Tier 2, Write Tier 3, Write Tier 4, Write Tier 5  (5 writes)
Tx #2  ──> Write Tier 1, Write Tier 2, Write Tier 3, Write Tier 4, Write Tier 5  (5 writes)
Tx #3  ──> Write Tier 1, Write Tier 2, Write Tier 3, Write Tier 4, Write Tier 5  (5 writes)
...
Tx #50000 ─> Write Tier 1, Write Tier 2, Write Tier 3, Write Tier 4, Write Tier 5 (5 writes)

Under a load of 100,000 transactions, the database would endure 500,000 writes — 400,000 of which are completely redundant upserts to metadata tables that already contain those exact directory keys. This creates severe performance degradation:

  1. CommitLog and Memtable bloat from redundant metadata writes.

  2. Unnecessary SSTable compaction pressure on directory tables.

  3. 5x network round-trips / reactive publisher overhead on live traffic paths.

1.2. The Solution: Optimistic Idempotent Upsert with Deferred Confirmation

Parent directory tiers (Tiers 1–4) act strictly as directory signposts to guide recovery workers. They do not store transaction payloads or individual transaction IDs.

To avoid both write amplification and unnecessary thread waiting:

  1. Zero Thread Waiting (Pure Non-Blocking):

    • Concurrent threads do not wait or block on each other.

    • If a bucket is not yet confirmed in Cassandra, any arriving thread simply executes the upsert of Tiers 1–4.

    • Because Cassandra writes are idempotent, multiple concurrent upserts to Tiers 1–4 overwrite the exact same keys with identical values without error or duplication.

  2. Deferred Confirmation:

    • As soon as any thread successfully completes writing Tiers 1–4 to Cassandra, it calls markBucketConfirmed.

    • From that moment forward, all subsequent threads see requiresParentDirectoryInsert == false and write Tier 5 ONLY (the fast path).

  3. Automatic Fault Tolerance & Self-Healing:

    • If a thread encounters a database glitch or network timeout while writing Tiers 1–4, it does not confirm.

    • Concurrent or subsequent threads will naturally attempt the upsert until one succeeds, guaranteeing that directory paths are never orphaned.

[Start of Bucket 0 (Unconfirmed)]
  │
  ├─► Tx #1: Confirmed? NO  ──► Upserts Tiers 1–4 + Tier 5 ──► DB OK! ──► markConfirmed(0) ✔️
  │                                                                             │
  ├─► Tx #2: Confirmed? NO  ──► Upserts Tiers 1–4 + Tier 5 ──► DB OK!          │ (Now Confirmed!)
  │   (proceeds concurrently, zero waiting)                                     │
  │                                                                             ▼
  │                                                             [Confirmed State Active]
  │                                                                             │
  ├─► Tx #3: Confirmed? YES ────────────────────────────────────► Write Tier 5 ONLY (Fast Path)
  ├─► Tx #4: Confirmed? YES ────────────────────────────────────► Write Tier 5 ONLY (Fast Path)
  └─► Tx #50,000: Confirmed? YES ───────────────────────────────► Write Tier 5 ONLY (Fast Path)

For a 50,000-transaction bucket, only a tiny handful of initial concurrent threads (typically 2 to 5 requests during the first 10ms) upsert Tiers 1–4. The remaining 49,995+ transactions insert directly into Tier 5 with zero waiting, achieving an immediate ~80% reduction in database write traffic.


2. Mathematical Calculation Engine

The caching and tracking manager (RecoveryDirectoryTracker) performs three discrete mathematical calculations per transaction in ~5 nanoseconds without distributed locks.

2.1. Calculation 1: Target Window Index & UTC Midnight Rollover

Transaction scheduling is partitioned into discrete time windows of granularity windowIntervalMinutes (default: 1, giving 1440 windows per 24h day). Each saga domain entity can configure independent delay horizons:

  • Retry (RETRY): Transient downstream failures target immediate future window W + delayWindows (default: W + 1).

  • Restore (RESTORE): Dead-man’s switch watchdog rows target far-future window W + delayWindows (default: W + 600, i.e. 10 hours ahead).

2.1.1. Formulas & Pseudocode

Target Window and UTC Midnight Rollover Calculation
totalWindowsPerDay = 1440 / windowIntervalMinutes
minutesSinceMidnight = (utcHour * 60) + utcMinute

currentWindowIndex = minutesSinceMidnight / windowIntervalMinutes
targetWindowIndex  = currentWindowIndex + delayWindows

// Calculate Calendar Day Offset (handles midnight UTC rollover)
daysOffset        = targetWindowIndex / totalWindowsPerDay
targetWindowInDay = targetWindowIndex % totalWindowsPerDay

targetDate  = utcDate + daysOffset days
minuteOfDay = targetWindowInDay * windowIntervalMinutes

2.1.2. Step-by-Step Breakdown

  1. Total Daily Windows (totalWindowsPerDay):

    • If windowIntervalMinutes = 1: totalWindowsPerDay = 1440 / 1 = 1440.

    • If windowIntervalMinutes = 5: totalWindowsPerDay = 1440 / 5 = 288.

  2. Current Window Index (currentWindowIndex):

    • Computes minutes elapsed since midnight UTC (minutesSinceMidnight) and divides by windowIntervalMinutes.

  3. Target Window Index (targetWindowIndex):

    • Adds the domain-configured delayWindows to currentWindowIndex.

  4. UTC Midnight Rollover (daysOffset and targetWindowInDay):

    • If targetWindowIndex < totalWindowsPerDay: the write stays within today’s calendar date (daysOffset = 0).

    • If targetWindowIndex >= totalWindowsPerDay: the write crosses midnight UTC:

    • daysOffset advances the calendar date by targetWindowIndex / totalWindowsPerDay days.

    • targetWindowInDay wraps to the beginning of the next day using modulo arithmetic (%).

  5. Cassandra Clustering Key (minuteOfDay):

    • Scaled back to the discrete minute of the day (0 to 1439) to match table clustering definitions (minute_of_day ASC).


2.2. Calculation 2: Monotonic Slot Allocation & Odd/Even Bucket Segregation

Every target window maintains a JVM-local AtomicLong counter. When a transaction is assigned to that window, it atomically claims a monotonic sequence slot (1, 2, 3…​).

2.2.1. Formulas & Pseudocode

Slot Allocation and Bucket Index Calculation
slot = counter.incrementAndGet()  // Monotonic: 1, 2, 3...
bucketSequence = (slot - 1) / bucketSize

// RETRY uses Even Bucket Indexes: 0, 2, 4, 6...
retryBucketIndex = bucketSequence * 2

// RESTORE uses Odd Bucket Indexes: 1, 3, 5, 7...
restoreBucketIndex = (bucketSequence * 2) + 1

2.2.2. Why Segregate Even and Odd Buckets?

Dimension Even Buckets (RETRY) Odd Buckets (RESTORE)

Bucket Indexes

0, 2, 4, 6…​

1, 3, 5, 7…​

Trigger Condition

Transient step failure (rare, e.g. HTTP 503)

Transaction start (every single saga execution)

Deletion Pattern

Dropped via O(1) Partition Tombstone when bucket finishes

Deleted via individual row deletes on normal transaction success

Tombstone Status

0% cell tombstones (100% live scan path for workers)

Absorbs high-frequency completion cell tombstones

Cassandra Safety

Completely eliminates ReadFailureException (>100,000 tombstones)

Isolates tombstone churn away from retry scan paths


2.3. Calculation 3: In-Memory Boundary Tracking (requiresParentDirectoryInsert)

To determine whether Tiers 1–4 need to be inserted, each window state tracks confirmed bucket indexes using a concurrent thread-safe set:

Set<Long> confirmedBuckets = ConcurrentHashMap.newKeySet();

When an allocation claims a slot and calculates bucketIndex, it checks:

boolean requiresParentDirectoryInsert = !confirmedBuckets.contains(bucketIndex);
  • If confirmedBuckets.contains(bucketIndex) is false:

  • The bucket has not yet been confirmed as written in Cassandra.

  • requiresParentDirectoryInsert is true.

  • The thread executes the idempotent upsert of Tiers 1–4, and upon database success calls:

    tracker.markBucketConfirmed(domain, type, allocation);
  • If confirmedBuckets.contains(bucketIndex) is true:

  • The directory hierarchy for this bucket is already confirmed written in Cassandra.

  • requiresParentDirectoryInsert is false.

  • The thread bypasses Tiers 1–4 completely and inserts directly into Tier 5 ONLY.


3. Complete Step-by-Step Numerical Walkthrough

Assume the following configuration: * bucketSize = 50,000 * windowIntervalMinutes = 1 * Current UTC Time: 10:00:00 UTC (minutesSinceMidnight = 600, currentWindow = 600) * Operation: RETRY (delay = 1 window → target window 601)

Step / Transaction Slot Bucket Seq Bucket Index requiresParentInsert Cassandra Database Operations

Tx #1
(Window & Bucket Initializer)

1

(1 - 1) / 50000 = 0

0 * 2 = 0

true
(unconfirmed)

5-Tier Initializer Writes:
1. INSERT INTO es_days_by_year …​ (Tier 1)
2. INSERT INTO es_recovery_windows_by_day …​ minute_of_day = 601 (Tier 2)
3. INSERT INTO es_instances_by_recovery_window …​ instance_id (Tier 3)
4. INSERT INTO es_buckets_by_instance …​ bucket_index = 0 (Tier 4)
5. INSERT INTO es_recovery_transactions_by_instance …​ bucket_index = 0, tx_1 (Tier 5)
On success: calls markBucketConfirmed(0).

Tx #2
(Concurrent before confirmation)

2

(2 - 1) / 50000 = 0

0 * 2 = 0

true
(if Tx #1 in-flight)

Concurrent Idempotent Upsert:
Executes Tiers 1–4 in parallel without waiting.
Cassandra handles the duplicate write idempotently with zero error.

Tx #3 .. #50,000
(Confirmed Fast Path)

3 .. 50000

0

0

false
(confirmed!)

Fast Path Writes:
INSERT INTO es_recovery_transactions_by_instance …​ bucket_index = 0, tx_N (Tier 5 ONLY)
Zero metadata table overhead across 49,997+ writes.

Tx #50,001
(Bucket Rollover Boundary)

50001

(50001 - 1) / 50000 = 1

1 * 2 = 2

true
(bucket 2 unconfirmed)

Bucket Rollover Writes:
1. Upsert Tiers 1–3 markers (idempotent no-op in Cassandra)
2. INSERT INTO es_buckets_by_instance …​ bucket_index = 2 (Tier 4: registers new bucket)
3. INSERT INTO es_recovery_transactions_by_instance …​ bucket_index = 2, tx_50001 (Tier 5)
On success: calls markBucketConfirmed(2).

Tx #50,002
(Fast Path in Bucket 2)

50002

1

2

false
(bucket 2 confirmed)

Fast Path Write:
INSERT INTO es_recovery_transactions_by_instance …​ bucket_index = 2, tx_50002 (Tier 5 ONLY)


4. Architecture of the Implemented Tracking Classes

All tracking classes reside in org.stacksaga.cassandra.recovery:

Class Name Architectural Role

RecoveryType

Enum distinguishing RETRY (computes even buckets 0, 2, 4…​) and RESTORE (computes odd buckets 1, 3, 5…​).

RecoveryWindow

Immutable record encapsulating (LocalDate date, int minuteOfDay) corresponding directly to Cassandra composite partition and clustering keys.

RecoveryAllocationResult

Carrier record containing the target RecoveryWindow, computed bucketIndex, allocated sequence slot, and the boolean flag requiresParentDirectoryInsert.

RecoveryBucketTrackingState

JVM-local thread-safe tracking state holding the AtomicLong counter and ConcurrentHashMap.newKeySet() of confirmed buckets for a given window.

RecoveryWindowCalculator

Component that converts timestamps and domain configurations into target RecoveryWindow instances with automatic UTC midnight rollover.

RecoveryDirectoryTracker

Central tracking service managing the cache of active RecoveryWindowKey states, providing non-blocking allocation methods, confirmation callbacks (markBucketConfirmed), and memory pruning.


5. Reactive Integration Example (Project Reactor)

Here is how the reactive service layer uses RecoveryDirectoryTracker with deferred confirmation:

package org.stacksaga.cassandra.recovery;

import lombok.RequiredArgsConstructor;
import org.springframework.stereotype.Service;
import reactor.core.publisher.Mono;

@Service
@RequiredArgsConstructor
public class ReactiveRecoveryService {

    private final RecoveryDirectoryTracker tracker;
    private final CassandraRecoveryDao recoveryDao;

    /**
     * Registers a transient retry failure.
     */
    public Mono<Void> registerRetry(String domain, String transactionId, byte[] payload) {
        // Step 1: Allocate slot non-blockingly (~5 nanoseconds)
        return tracker.allocateReactive(domain, RecoveryType.RETRY)
            .flatMap(allocation -> {
                // Step 2: Branch based on deferred confirmation check
                if (allocation.requiresParentDirectoryInsert()) {
                    // Unconfirmed: Upsert Tiers 1-4, mark confirmed on DB success, then append Tier 5
                    return Mono.when(
                        recoveryDao.insertTier1DaysByYear(allocation.targetDate()),
                        recoveryDao.insertTier2WindowsByDay(allocation.targetDate(), allocation.targetMinuteOfDay()),
                        recoveryDao.insertTier3InstanceMarker(allocation.targetDate(), allocation.targetMinuteOfDay()),
                        recoveryDao.insertTier4BucketIndex(allocation.targetDate(), allocation.targetMinuteOfDay(), allocation.bucketIndex())
                    )
                    // Once Cassandra confirms success, flip confirmed flag in memory!
                    .doOnSuccess(unused -> tracker.markBucketConfirmed(domain, RecoveryType.RETRY, allocation))
                    .then(recoveryDao.insertTier5RetryTransaction(allocation, transactionId, payload));
                } else {
                    // Fast Path (Already confirmed): Append to Tier 5 ONLY with zero waiting
                    return recoveryDao.insertTier5RetryTransaction(allocation, transactionId, payload);
                }
            });
    }

    /**
     * Registers a dead-man's switch watchdog at transaction start.
     */
    public Mono<String> registerRestoreWatchdog(String domain, String transactionId) {
        return tracker.allocateReactive(domain, RecoveryType.RESTORE)
            .flatMap(allocation -> {
                if (allocation.requiresParentDirectoryInsert()) {
                    return Mono.when(
                        recoveryDao.insertTier1DaysByYear(allocation.targetDate()),
                        recoveryDao.insertTier2WindowsByDay(allocation.targetDate(), allocation.targetMinuteOfDay()),
                        recoveryDao.insertTier3InstanceMarker(allocation.targetDate(), allocation.targetMinuteOfDay()),
                        recoveryDao.insertTier4BucketIndex(allocation.targetDate(), allocation.targetMinuteOfDay(), allocation.bucketIndex())
                    )
                    .doOnSuccess(unused -> tracker.markBucketConfirmed(domain, RecoveryType.RESTORE, allocation))
                    .then(recoveryDao.insertTier5RestoreWatchdog(allocation, transactionId))
                    .thenReturn(buildWatchdogPath(allocation, transactionId));
                } else {
                    return recoveryDao.insertTier5RestoreWatchdog(allocation, transactionId)
                            .thenReturn(buildWatchdogPath(allocation, transactionId));
                }
            });
    }

    private String buildWatchdogPath(RecoveryAllocationResult alloc, String txId) {
        return alloc.targetDate() + "/" + alloc.targetMinuteOfDay() + "/" + alloc.bucketIndex() + "/" + txId;
    }
}

6. Memory Bound Invariant: Stale Window Pruning

Because orchestrator pods run indefinitely in containerized production environments, in-memory tracking states must not grow without bound.

Standard-Nodes write only into future horizons:

  • Retry writes into W + 1 (or domain delay W + D).

  • Restore writes into W + 600 (or domain delay W + D).

Once wall-clock UTC time has progressed past window W, no pod will ever write to that window again. RecoveryDirectoryTracker provides the pruneExpiredWindows method:

@Scheduled(fixedDelay = 300_000) // Runs every 5 minutes
public void pruneStaleRecoveryWindows() {
    LocalDateTime nowUtc = LocalDateTime.now(ZoneOffset.UTC);
    int currentMinuteOfDay = nowUtc.getHour() * 60 + nowUtc.getMinute();

    // Purges any window tracking state strictly in the past
    tracker.pruneExpiredWindows(nowUtc.toLocalDate(), currentMinuteOfDay);
}

This guarantees that:

  • Active heap footprint of RecoveryDirectoryTracker is strictly bounded to under 50 KB.

  • Zero memory leaks occur regardless of how many days or months the microservice runs.