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)

---

**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`):

```csharp
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`):

```csharp
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:

```csharp
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?

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.

Written by the indexing model from the issue text.