Azure Storage backend: ExecutionTerminated message is never deleted when the Instances row is absent, causing permanent control-queue poison (regression in 2.7.0 from #1256)

Start in src/DurableTask.AzureStorage/AzureStorageOrchestrationService.cs around IsExecutableInstanceAsync and the acknowledgement path, then inspect UpdateStatusForTerminationAsync in src/DurableTask.AzureStorage/Tracking/AzureTableTrackingStore.cs. Read the existing TerminatePendingOrchestration test from #1256 and add coverage for a missing Instances row. Done means the termination message is discarded without recurring 404 failures while the pending-instance behavior remains covered.

---

Title: Azure Storage backend: ExecutionTerminated message is never deleted when the Instances row is absent, causing permanent control-queue poison (regression in 2.7.0 from #1256)

---

Environment

Microsoft.Azure.DurableTask.AzureStorage: 2.8.0 (defect also present in 2.7.0, 2.9.1 and main @ b385165)
Microsoft.Azure.DurableTask.Core: 3.x
Runtime: .NET 10
Host: self-hosted TaskHubWorker (not Azure Functions)
Backend: Azure Storage, partitioned control queues
Non-default settings: ControlQueueVisibilityTimeout, PartitionCount, TaskOrchestrationDispatcherCount = 1

Summary

If an ExecutionTerminated control message is dequeued for an instance whose Instances table row no longer exists, the message can never be acknowledged. It returns to the control queue on every visibility timeout and is redelivered forever.

This is a regression introduced in 2.7.0 by #1256 ("Fix Terminating Pending Orchestrations"). Before that change this exact case returned "No such instance" and the caller deleted the message cleanly.

Each such message permanently degrades the partition it sits on, because every failed fetch costs a fixed backoff and those stalls serialise per task hub. We are currently carrying 834 of these messages across 11 storage accounts in one region, one per affected orchestration instance, with DequeueCount observed above 22,000 and message age pinned at the int32 ceiling (24.86 days).

Root cause

IsExecutableInstanceAsync handles "history is empty" by checking for a terminate message first
(src/DurableTask.AzureStorage/AzureStorageOrchestrationService.cs L1081-1089 on main):

TaskMessage executionTerminatedEventMessage = newMessages.LastOrDefault(msg => msg.Event is ExecutionTerminatedEvent);
if (executionTerminatedEventMessage is not null)
{
    var executionTerminatedEvent = (ExecutionTerminatedEvent)executionTerminatedEventMessage.Event;
    await this.trackingStore.UpdateStatusForTerminationAsync(
        instanceId,
        executionTerminatedEvent);
    return $"Instance is {OrchestrationStatus.Terminated}";
}

// falls through to: runtimeState.Events.Count == 0 ? "No such instance" : "Invalid history (...)"

UpdateStatusForTerminationAsync then merges the Instances row
(src/DurableTask.AzureStorage/Tracking/AzureTableTrackingStore.cs L884-904 on main):

Stopwatch stopwatch = Stopwatch.StartNew();
await this.InstancesTable.MergeEntityAsync(instanceEntity, ETag.All, cancellationToken);

ETag.All waives the version check, but a merge still requires the row to exist — it is not an upsert. When the row is absent the call returns 404 ResourceNotFound, and there is no try/catch around it.

That exception propagates out of IsExecutableInstanceAsync and is awaited at the caller
(AzureStorageOrchestrationService.cs L805), which is before the block that would acknowledge the message:

string warningMessage = await this.IsExecutableInstanceAsync(   // L805 - throws here
    session.RuntimeState, orchestrationWorkItem.NewMessages, settings.AllowReplayingTerminalInstances, cancellationToken);
if (!string.IsNullOrEmpty(warningMessage))                      // L810 - never reached
{
    ...
    // The instance has already completed or never existed. Delete this message batch.
    await this.DeleteMessageBatchAsync(session, messagesToDiscard);   // L861 - never reached
}

The runtime has already classified the message as discardable and is a few lines from removing it, but throws instead. The message is therefore immortal.

Why the two cases are indistinguishable at that point

#1256 targeted terminating a Pending orchestration, where the Instances row exists and history is empty. A purged instance also has empty history, but the row is gone. Both reach the same branch, and the new code assumes the row is present. The test added in #1256 (TerminatePendingOrchestration) only covers the Pending case.

Affected versions (verified by diffing the release tags)

Version	Released	Terminate path	MergeEntityAsync
2.6.1	2025-10-20	absent	n/a — not affected
2.7.0	2025-11-03	present	unguarded — first affected
2.8.0	2026-01-05	present	unguarded
2.9.1	2026-06-24	present	unguarded
main @ b385165	—	present	unguarded

Repro

1. Start an orchestration and let it run.
2. Call ForceTerminateTaskOrchestrationAsync(instanceId, reason). This only enqueues an ExecutionTerminated control message; it does not wait.
3. Before a worker dequeues that message, call PurgeInstanceStateAsync(instanceId) — the Instances row and history are deleted.
4. A worker dequeues the terminate message, finds no history, enters the branch above, and 404s on the merge.
5. Observe the message redeliver on every visibility timeout indefinitely, with DequeueCount climbing without bound.

Any caller that terminates and then purges without waiting for the termination to land will hit this. It is a narrow window per attempt, but it is deterministic under load and the damage is permanent.

Impact

Because the exception leaves workItem null, nothing is dispatched that iteration and GetDelayInSecondsAfterOnFetchException imposes a flat 10 s backoff. With TaskOrchestrationDispatcherCount = 1 those stalls serialise, so the break-even point is:

orphans per partition = ControlQueueVisibilityTimeout / 10s

At the default 300 s, roughly 30 of these messages fully saturate a partition — legitimate orchestration messages then queue behind the redelivery loop. We measured 15 of 52 partitions saturated (worst duty cycle 4.37x) before mitigating by raising the visibility timeout to 1800 s, which raises the threshold to ~180 but does not fix anything.

Customer-visible symptom: orchestrations queued on an affected partition sat for hours. Mean wait on the worst storage account was 152 min, P95 569 min.

Two properties make this worse than a single stuck message:

• The message carries ExecutionId = null (ForceTerminateTaskOrchestrationAsync builds the TaskMessage with only an instance ID), so it matches any future execution of that instance ID. If instance IDs are stable per logical entity, the orphan will terminate that entity's next run too.
• Nothing ages these out. DequeueCount and message age simply grow until the queue message TTL, which for these is effectively infinite.

Suggested fix

A missing Instances row means the instance is definitionally gone, so there is nothing to update and the termination is trivially satisfied. Either:

1. Catch the 404 inside AzureTableTrackingStore.UpdateStatusForTerminationAsync and treat it as a no-op, or
2. Catch it at the IsExecutableInstanceAsync call site and still return $"Instance is {OrchestrationStatus.Terminated}".

Either way the caller proceeds into the discard block and the message is acknowledged and deleted, which is exactly what happened before 2.7.0.

Option 1 seems preferable — it keeps the invariant local to the tracking store, and InstanceStoreBackedTrackingStore.UpdateStatusForTerminationAsync has the same exposure via instanceEntity.Single(), which throws when the instance is absent.

Happy to open a PR if that would help.

Related observation (lower confidence, may warrant a separate issue)

While tracing this we also saw the mirror case: a purge landing after a fresh orchestration wrote its history leaves the Instances row Running with an empty History table. The activity completes successfully, but the TaskCompleted message cannot be applied — it is treated as out-of-order, retried, and finally dropped with DiscardingWorkItem: No such instance. The orchestration is then permanently stuck in Running with no pending message and nothing to advance it.

That one is provoked by our own purge, so we are fixing it on our side. Flagging it only because there appears to be no mechanism in the framework that detects or reaps an instance in that state.

Questions

1. Is the 404-on-merge case one you would accept a PR for, and do you prefer the fix in the tracking store or at the call site?
2. Is there a supported way for a client to know that a termination has been applied rather than merely enqueued? ForceTerminateTaskOrchestrationAsync returns as soon as the message is sent, which is what makes terminate-then-purge racy for any caller.
3. Would you consider making PurgeInstanceStateAsync refuse to purge a non-terminal instance, or is guarding that the caller's responsibility?