Duroxide-PG Deadlock Issue in Parallel Orchestrations

Summary

We're using duroxide-pg as the storage backend for an orchestration system. When executing orchestrations with parallel branches (e.g., joining multiple sub-orchestrations), a deadlock occurs in the fetch_orchestration_item function when multiple workers attempt to acquire locks on the instance_locks table simultaneously.

🔴 Critical Finding: The deadlock itself is handled by PostgreSQL (aborts one transaction after 1 second). However, the sub-orchestration completion notification is lost when this happens. Sub-orchestrations complete successfully, but the parent orchestration never gets notified and waits forever.

Context: How We Use Duroxide-PG

We have a PostgreSQL extension that embeds the Duroxide runtime as a background worker. Users define orchestration graphs (sequences, conditionals, parallel joins, loops) which get executed by the Duroxide runtime using duroxide-pg for persistence.

Our setup:

Duroxide runtime runs as a PostgreSQL background worker
We use PostgresProvider::new_with_schema() to create the store in a duroxide schema
Orchestrations are started via Worker::start_orchestration()
The runtime processes orchestration items via the standard Duroxide polling loop

Orchestration types we support:

Sequential execution (A → B → C)
Conditional branching (if/else)
Parallel join (execute A and B concurrently, wait for both)
Loops with continue-as-new

The deadlock only occurs with parallel operations (joins).

Environment

PostgreSQL: 17.7 (Debian 17.7-3.pgdg12+1)
duroxide-pg: Latest version from crates.io
Platform: linux/amd64 (Docker container)
Schema: duroxide (custom schema passed to new_with_schema)

Problem Description

When an orchestration has parallel branches that need to execute concurrently:

The Duroxide runtime schedules multiple sub-orchestrations (or activities) to run in parallel
Multiple async tasks call fetch_orchestration_item() to acquire work
Both workers attempt to INSERT/UPDATE the instance_locks table
PostgreSQL detects a deadlock and aborts one transaction
After deadlock resolution, the orchestration instance gets stuck in a non-terminal state

The orchestration never completes - it remains in "Pending" or "Running" state indefinitely.

Reproduction Scenario

Orchestration Structure (Pseudo-code)

Orchestration: ParallelJoinTest
├── JOIN
│   ├── Branch A: Execute SQL "INSERT INTO log VALUES ('A')"
│   └── Branch B: Execute SQL "INSERT INTO log VALUES ('B')"
└── (wait for both branches to complete)

What Happens

Main orchestration starts
JOIN node schedules Branch A and Branch B as parallel work items
Worker Task 1 calls fetch_orchestration_item() for Branch A
Worker Task 2 calls fetch_orchestration_item() for Branch B
DEADLOCK - both tasks wait for each other's transaction

Three-Way Join (Even More Likely to Deadlock)

Orchestration: ThreeWayJoinTest
├── JOIN
│   ├── Branch A: Activity 1
│   ├── Branch B: Activity 2
│   └── Branch C: Activity 3
└── (wait for all three)

Join Followed by Continuation

Orchestration: JoinThenContinue
├── JOIN
│   ├── Branch A: Count users
│   └── Branch B: Count orders
├── THEN
│   └── Log "counts complete"

Logs

Deadlock Detection

2025-12-07 21:59:56.770 UTC [76] ERROR:  deadlock detected
2025-12-07 21:59:56.770 UTC [76] DETAIL:  Process 76 waits for ShareLock on transaction 794; blocked by process 79.
	Process 79 waits for ShareLock on transaction 795; blocked by process 76.
	Process 76: SELECT * FROM duroxide.fetch_orchestration_item($1, $2)
	Process 79: SELECT * FROM duroxide.fetch_orchestration_item($1, $2)
2025-12-07 21:59:56.770 UTC [76] HINT:  See server log for query details.
2025-12-07 21:59:56.770 UTC [76] CONTEXT:  while inserting index tuple (0,12) in relation "instance_locks"
	SQL statement "INSERT INTO duroxide.instance_locks (instance_id, lock_token, locked_until, locked_at)
	            VALUES (v_instance_id, v_lock_token, v_locked_until, p_now_ms)
	            ON CONFLICT(instance_id) DO UPDATE
	            SET lock_token = EXCLUDED.lock_token,
	                locked_until = EXCLUDED.locked_until,
	                locked_at = EXCLUDED.locked_at
	            WHERE duroxide.instance_locks.locked_until <= p_now_ms"
	PL/pgSQL function duroxide.fetch_orchestration_item(bigint,bigint) line 28 at SQL statement
2025-12-07 21:59:56.770 UTC [76] STATEMENT:  SELECT * FROM duroxide.fetch_orchestration_item($1, $2)

Slow Query Warnings (from sqlx, post-deadlock)

[2m2025-12-07T21:59:56.787686Z[0m [33m WARN[0m [2msqlx::query[0m[2m:[0m slow statement: execution time exceeded alert threshold 
    [3msummary[0m[2m=[0m"SELECT * FROM duroxide.fetch_orchestration_item($1, …)" 
    [3mdb.statement[0m[2m=[0m"\n\nSELECT\n  *\nFROM\n  duroxide.fetch_orchestration_item($1, $2)\n" 
    [3mrows_affected[0m[2m=[0m0 
    [3mrows_returned[0m[2m=[0m0 
    [3melapsed[0m[2m=[0m1.008913542s 
    [3melapsed_secs[0m[2m=[0m1.008913542 
    [3mslow_threshold[0m[2m=[0m1s

[2m2025-12-07T21:59:56.789412Z[0m [33m WARN[0m [2msqlx::query[0m[2m:[0m slow statement: execution time exceeded alert threshold 
    [3msummary[0m[2m=[0m"SELECT * FROM duroxide.fetch_orchestration_item($1, …)" 
    [3mdb.statement[0m[2m=[0m"\n\nSELECT\n  *\nFROM\n  duroxide.fetch_orchestration_item($1, $2)\n" 
    [3mrows_affected[0m[2m=[0m0 
    [3mrows_returned[0m[2m=[0m1 
    [3melapsed[0m[2m=[0m1.02701925s 
    [3melapsed_secs[0m[2m=[0m1.02701925 
    [3mslow_threshold[0m[2m=[0m1s

Full Timeline

-- Duroxide runtime initialization --
2025-12-07 21:59:35.021 UTC [1] LOG:  database system is ready to accept connections
2025-12-07 21:59:35.024 UTC [72] LOG:  pg_durable: duroxide background worker starting...
2025-12-07 21:59:35.033 UTC [72] LOG:  pg_durable: initializing duroxide runtime with PostgreSQL store...
2025-12-07 21:59:35.036 UTC [72] LOG:  pg_durable: connecting to PostgreSQL at postgres://postgres@127.0.0.1:5432/postgres (schema: duroxide)
2025-12-07 21:59:35.259 UTC [72] LOG:  PostgreSQL store created in schema 'duroxide'
2025-12-07 21:59:35.301 UTC [72] LOG:  duroxide runtime started, processing...

-- User starts an orchestration with parallel JOIN --
-- (orchestration_id: 780d0395, has 2 parallel branches) --

-- ~21 seconds later, deadlock occurs --
2025-12-07 21:59:56.770 UTC [76] ERROR:  deadlock detected
2025-12-07 21:59:56.770 UTC [76] DETAIL:  Process 76 waits for ShareLock on transaction 794; blocked by process 79.
	Process 79 waits for ShareLock on transaction 795; blocked by process 76.
	Process 76: SELECT * FROM duroxide.fetch_orchestration_item($1, $2)
	Process 79: SELECT * FROM duroxide.fetch_orchestration_item($1, $2)

-- Orchestration stays stuck, never completes --
-- Status check 60 seconds later still shows "pending" --

Technical Analysis

The Problematic SQL Statement

The deadlock occurs at line 28 of fetch_orchestration_item, in this SQL:

INSERT INTO duroxide.instance_locks (instance_id, lock_token, locked_until, locked_at)
VALUES (v_instance_id, v_lock_token, v_locked_until, p_now_ms)
ON CONFLICT(instance_id) DO UPDATE
SET lock_token = EXCLUDED.lock_token,
    locked_until = EXCLUDED.locked_until,
    locked_at = EXCLUDED.locked_at
WHERE duroxide.instance_locks.locked_until <= p_now_ms

Root Cause Analysis

Concurrent INSERT ... ON CONFLICT: When two workers try to fetch orchestration items (potentially for different instances, or different items of the same parent orchestration), they both execute the INSERT with ON CONFLICT.
Index tuple insertion deadlock: The error states "while inserting index tuple (0,12) in relation 'instance_locks'". The unique index on instance_id is causing lock contention.
ShareLock circular wait:
- Transaction 794 (Process 76) holds a lock and waits for Transaction 795
- Transaction 795 (Process 79) holds a lock and waits for Transaction 794
- Classic deadlock scenario
Lost completion notifications: After PostgreSQL aborts one transaction to break the deadlock, the sub-orchestration completion signal is lost. The sub-orchestration is marked complete in its own record, but the parent orchestration never receives notification.

🔴 CRITICAL FINDING: Lost Completion Notifications

PostgreSQL's deadlock_timeout is 1 second. After detecting a deadlock, PostgreSQL aborts one transaction. However, this doesn't fix the problem - the orchestration remains stuck forever.

Evidence from Database State

After a deadlock occurs, querying the duroxide.executions table shows:

    instance_id    | execution_id |  status   
-------------------+--------------+-----------
 7e98f125          |            1 | Running     <-- Parent stuck!
 7e98f125::sub::10 |            1 | Completed   <-- Child completed
 7e98f125::sub::11 |            1 | Completed   <-- Child completed
 8cb6f497          |            1 | Running     <-- Parent stuck!
 8cb6f497::sub::10 |            1 | Completed   <-- Child completed
 8cb6f497::sub::11 |            1 | Completed   <-- Child completed

Both sub-orchestrations completed successfully, but the parent orchestrations are stuck in "Running" forever!

The queues are empty - no pending work:

SELECT * FROM duroxide.orchestrator_queue;  -- 0 rows
SELECT * FROM duroxide.worker_queue;         -- 0 rows
SELECT * FROM duroxide.instance_locks;       -- 0 rows

What's Happening

Sub-orchestration A completes its work
Sub-orchestration A tries to notify parent (signal completion)
DEADLOCK occurs during this notification
PostgreSQL aborts the notification transaction
Sub-orchestration A's status is updated to "Completed" (separate transaction)
But the parent never receives the completion signal
Parent waits forever for children that already finished

The Real Bug

The deadlock itself isn't the main problem - PostgreSQL handles it correctly by aborting one transaction after 1 second. The real bug is that the completion notification is lost and never retried.

When a sub-orchestration completes, duroxide-pg needs to:

Mark the sub-orchestration as complete ✅ (this works)
Signal the parent orchestration to wake up ❌ (this gets lost on deadlock)

If step 2 fails due to deadlock, it should be retried. Currently it appears to be silently dropped.

Why This Only Affects Parallel Operations

Sequential orchestrations: Only one item is fetched at a time → no concurrent fetch_orchestration_item calls → no deadlock
Parallel orchestrations (JOIN): Multiple items need to be fetched concurrently → multiple fetch_orchestration_item calls → potential deadlock

Potential Solutions

Priority 1: Fix Lost Completion Notifications (Critical)

The most important fix is ensuring completion notifications are never lost:

// When sub-orchestration completes, retry notification until successful
async fn signal_parent_completion(parent_id: &str, child_id: &str) -> Result<()> {
    loop {
        match notify_parent(&pool, parent_id, child_id).await {
            Ok(_) => return Ok(()),
            Err(e) if e.is_deadlock() => {
                // Deadlock - retry with backoff
                tokio::time::sleep(Duration::from_millis(rand::random::<u64>() % 100)).await;
                continue;
            }
            Err(e) => return Err(e),
        }
    }
}

Or use a transactional outbox pattern:

Write completion + notification to an outbox table in same transaction
Background process reads outbox and delivers notifications
Notifications are guaranteed to be delivered eventually

Priority 2: Prevent the Deadlock

Option A: Use Advisory Locks

-- Before attempting to acquire instance lock
SELECT pg_advisory_xact_lock(hashtext(v_instance_id));
-- Then do the INSERT ... ON CONFLICT

This serializes access at a higher level, preventing the deadlock.

Option B: Use SELECT FOR UPDATE with SKIP LOCKED

-- First, try to lock the existing row
SELECT * FROM duroxide.instance_locks 
WHERE instance_id = v_instance_id 
FOR UPDATE SKIP LOCKED;

-- If row exists and we got the lock, update it
-- If row doesn't exist, insert it
-- If row exists but SKIP LOCKED skipped it, return nothing (item already being processed)

Option C: Retry on Deadlock in fetch_orchestration_item

loop {
    match fetch_orchestration_item(&pool, now_ms, lock_duration_ms).await {
        Ok(item) => return Ok(item),
        Err(e) if e.is_deadlock() => {
            // Random backoff and retry
            tokio::time::sleep(Duration::from_millis(rand::random::<u64>() % 100)).await;
            continue;
        }
        Err(e) => return Err(e),
    }
}

Option D: Serialize Lock Acquisition

Single dispatcher acquires all pending items and distributes to workers:

let items = fetch_orchestration_items_batch(&pool, count).await?;
for item in items {
    worker_pool.submit(item);
}

Option E: Deterministic Lock Ordering

If multiple rows are being inserted, ensure they're always inserted in the same order (e.g., sorted by instance_id) to avoid circular wait conditions.

Priority 3: Add Orphan Detection

As a safety net, periodically scan for "orphaned" parent orchestrations:

-- Find parents stuck waiting for already-completed children
SELECT DISTINCT p.instance_id as stuck_parent
FROM duroxide.executions p
JOIN duroxide.executions c ON c.instance_id LIKE p.instance_id || '::sub::%'
WHERE p.status = 'Running'
AND NOT EXISTS (
    SELECT 1 FROM duroxide.executions c2 
    WHERE c2.instance_id LIKE p.instance_id || '::sub::%'
    AND c2.status != 'Completed'
);

Then re-queue these parents for processing.

Observed Behavior Summary

Orchestration Type	Result
Single activity	✅ Works
Sequence (A → B → C)	✅ Works
Conditional (if/else)	✅ Works
Timer/Sleep	✅ Works
Loop with continue-as-new	✅ Works
Parallel JOIN (2 branches)	❌ Deadlock (intermittent)
Parallel JOIN (3 branches)	❌ Deadlock (intermittent)
JOIN then continue	❌ Deadlock (intermittent)

Intermittent Nature

The deadlock doesn't occur 100% of the time. It depends on the exact timing of when workers call fetch_orchestration_item:

If workers acquire locks in a consistent order → success
If workers happen to acquire locks in conflicting order → deadlock

In our testing, roughly 50-70% of parallel JOIN operations result in a deadlock.

Additional Context

We're happy to provide more information or test patches. This is blocking our ability to use Duroxide for any workflows that require parallel execution.

Our Rust initialization code:

use duroxide::{
    OrchestrationContext, OrchestrationRegistry,
    runtime::{self, registry::ActivityRegistry},
};
use duroxide_pg::PostgresProvider;
use std::sync::Arc;

// Create the PostgreSQL store
let store = PostgresProvider::new_with_schema(&pg_conn_str, Some("duroxide"))
    .await
    .expect("Failed to create PostgreSQL store");

// Register activities
let activities = ActivityRegistry::builder()
    .register("ExecuteSQL", |ctx: ActivityContext, query: String| async move {
        // ... execute SQL ...
    })
    .build();

// Register orchestrations
let orchestrations = OrchestrationRegistry::builder()
    .register("ExecuteWorkflow", |ctx: OrchestrationContext, input: String| async move {
        // ... workflow logic ...
    })
    .register("ExecuteSubtree", |ctx: OrchestrationContext, input: String| async move {
        // Used for parallel branches - each branch runs as a sub-orchestration
    })
    .build();

// Start the runtime
let runtime = runtime::Runtime::start_with_store(
    Arc::new(store),
    Arc::new(activities),
    orchestrations
).await;

How we handle JOIN (parallel execution):

// In our "join" node handler within the orchestration:
"join" => {
    let left_id = node.left_node.as_ref().ok_or("Missing left branch")?;
    let right_id = node.right_node.as_ref().ok_or("Missing right branch")?;
    
    ctx.trace_info("Executing JOIN branches in parallel");
    
    // Serialize graph and results state for sub-orchestrations
    let graph_json = serde_json::to_string(&graph)?;
    let results_json = serde_json::to_string(&results)?;
    
    let left_input = serde_json::json!({
        "graph": graph_json,
        "node_id": left_id,
        "results": results_json
    }).to_string();
    
    let right_input = serde_json::json!({
        "graph": graph_json,
        "node_id": right_id,
        "results": results_json
    }).to_string();
    
    // Schedule sub-orchestrations for each branch
    // THIS IS WHERE THE DEADLOCK OCCURS - when Duroxide tries to fetch
    // orchestration items for both sub-orchestrations concurrently
    let mut join_handles = Vec::new();
    for input in vec![left_input, right_input] {
        let fut = ctx.schedule_sub_orchestration("ExecuteSubtree", input)
            .into_sub_orchestration();
        join_handles.push(fut);
    }
    
    // Wait for all branches to complete
    let results_vec = futures::future::join_all(join_handles).await;
    
    // Process results...
}

The deadlock scenario:

Main orchestration reaches JOIN node
ctx.schedule_sub_orchestration() is called twice, scheduling two sub-orchestrations
Duroxide runtime has multiple async tasks that poll for work
Task A calls fetch_orchestration_item() to pick up the first sub-orchestration
Task B calls fetch_orchestration_item() to pick up the second sub-orchestration
Both tasks try to INSERT/UPDATE the instance_locks table simultaneously
DEADLOCK - both tasks wait for each other's transaction

Key observation: The deadlock is in duroxide-pg's fetch_orchestration_item() function, not in our application code. The issue is how duroxide-pg handles concurrent lock acquisition when multiple orchestration items become available at the same time.

Reporter: pg_durable development team
Date: December 8, 2025
duroxide-pg version: Latest from crates.io
PostgreSQL deadlock_timeout: 1s (default)

FilesExpand file tree

DUROXIDE_PG_DEADLOCK_ISSUE.md

Latest commit

History