Skip to content

[Bug]: DurableFuture.anyOf can return a different winner on replay than on the original invocation #900

Open

Description

@zhongkechen

Summary

DurableFuture.anyOf does not record which future settled first. On replay, every
input future whose operation is already complete in the checkpoint history is settled
before anyOf runs, and the SDK returns the first one in argument order. When the
original invocation saw a different future settle first, the same handler input and
checkpoint history produce a different anyOf result.

Code that branches on the result can then start a different durable operation than
the checkpoint history records. The execution fails with
NonDeterministicExecutionException. Code that only uses the value can return a
different handler result without raising an error.

Expected Behavior

For identical handler input and checkpoint history, anyOf returns the same value
(or throws the same failure) on every replay as on the invocation that first
observed the winner. Branches based on it stay stable.

The other SDKs document this guarantee for their equivalent combinators:

  • Go durable.Race/Any (durable/combinators.go): "Race uses RunInChildContext
    internally, so the winner is checkpointed: on replay, the same outcome is returned
    deterministically regardless of future settlement order."
  • Rust ctx.race/ctx.select_ok (cross-language docs, sdk-reference/languages/rust):
    "Each records its outcome as one operation, so replay returns the same outcome."
  • JavaScript context.promise.race/any (handlers/promise-handler/promise-handler.ts)
    wraps the native combinator in runInChildContext, so the winner is persisted as a
    child-context result.

Actual Behavior

On replay, anyOf returns the first already-completed future in argument order, no
matter which one won originally.

Observed with LocalDurableTestRunner on main at 2918c69d34cad5cf13525fe1e46eaafe9a89d999
(3.1.1-SNAPSHOT):

Scenario Invocation that first observed the winner Replay Outcome
anyOf(callback, step), step finishes while callback pending, then callback.get() "s" (step) "ok" (callback) SUCCEEDED with "ok|ok" instead of "s|ok"
Same, then if (winner == "s") step("step-won") else step("callback-won") step callback FAILED: NonDeterministicExecutionException: Operation name mismatch ... Expected "step-won", got "callback-won"
anyOf(approvalCallback, waitAsync("deadline")), deadline fires, step("escalate"), then the approval arrives late deadline approval FAILED: NonDeterministicExecutionException ... Expected "escalate", got "record-approval"
anyOf(cb1, cb2), cb2 completes first, later cb1 completes "T" (cb2) "O" (cb1) SUCCEEDED with "O|O,T" instead of "T|O,T"
Control: anyOf(step, callback) (argument order matches the real completion order) step step correct

The approval-versus-deadline race is a common human-in-the-loop pattern. A late approval
makes the execution fail permanently.

Steps to Reproduce

Minimal handler (in sdk-integration-tests):

var runner = LocalDurableTestRunner.create(String.class, (input, ctx) -> {
    var cb = ctx.createCallback("approval", String.class);
    var s = ctx.stepAsync("fast", String.class, sc -> "s");
    var winner = DurableFuture.anyOf(cb, s); // invocation 1: "s" (callback still pending)
    if ("s".equals(winner)) {
        ctx.step("step-won", String.class, sc -> "A");
    } else {
        ctx.step("callback-won", String.class, sc -> "B");
    }
    return winner + "|" + cb.get(); // invocation 1 suspends here
});

assertEquals(ExecutionStatus.PENDING, runner.run("in").getStatus());
runner.completeCallback(runner.getCallbackId("approval"), "\"ok\"");

var replay = runner.run("in");
// Expected: SUCCEEDED, "s|ok"
// Actual:   FAILED, NonDeterministicExecutionException
//           (Operation name mismatch ... Expected "step-won", got "callback-won")
Full probe test (5 scenarios)
// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
package software.amazon.lambda.durable;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;

import java.time.Duration;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import org.junit.jupiter.api.Test;
import software.amazon.lambda.durable.model.ExecutionStatus;
import software.amazon.lambda.durable.testing.LocalDurableTestRunner;

/**
 * Probe: {@code DurableFuture.anyOf} must return the same winner on replay as on the invocation that first observed
 * it. Every test asserts the deterministic (expected) behavior; the {@code winners} list records the value anyOf
 * returned in each invocation (test instrumentation only).
 */
class AnyOfReplayDeterminismProbeTest {

    private static final Duration DEADLINE = Duration.ofSeconds(30);

    private final List<Object> winners = new CopyOnWriteArrayList<>();

    /** Step settles while the callback is pending; on replay both are complete. */
    @Test
    void stepBeatsPendingCallback_replayKeepsStepAsWinner() {
        var runner = LocalDurableTestRunner.create(String.class, (input, ctx) -> {
            var cb = ctx.createCallback("approval", String.class);
            var s = ctx.stepAsync("fast", String.class, sc -> "s");
            var winner = DurableFuture.anyOf(cb, s);
            winners.add(winner);
            return winner + "|" + cb.get();
        });

        var first = assertTimeoutPreemptively(DEADLINE, () -> runner.run("in"));
        assertEquals(ExecutionStatus.PENDING, first.getStatus());

        runner.completeCallback(runner.getCallbackId("approval"), "\"ok\"");
        var second = assertTimeoutPreemptively(DEADLINE, () -> runner.run("in"));

        System.out.println("[probe] stepBeatsPendingCallback winners=" + winners + " result=" + second.getResult(String.class));
        assertEquals(ExecutionStatus.SUCCEEDED, second.getStatus());
        assertEquals(List.of("s", "s"), winners, "anyOf winner changed between invocation 1 and replay");
        assertEquals("s|ok", second.getResult(String.class));
    }

    /** Control: same scenario with the argument order matching the real completion order. */
    @Test
    void control_argumentOrderMatchesCompletionOrder() {
        var runner = LocalDurableTestRunner.create(String.class, (input, ctx) -> {
            var cb = ctx.createCallback("approval", String.class);
            var s = ctx.stepAsync("fast", String.class, sc -> "s");
            var winner = DurableFuture.anyOf(s, cb);
            winners.add(winner);
            return winner + "|" + cb.get();
        });

        assertEquals(ExecutionStatus.PENDING, runner.run("in").getStatus());
        runner.completeCallback(runner.getCallbackId("approval"), "\"ok\"");
        var second = runner.run("in");

        System.out.println("[probe] control winners=" + winners + " result=" + second.getResult(String.class));
        assertEquals(List.of("s", "s"), winners);
        assertEquals("s|ok", second.getResult(String.class));
    }

    /** Downstream effect: branching on the winner starts a different durable operation on replay. */
    @Test
    void branchOnWinner_replayTakesSameBranch() {
        var runner = LocalDurableTestRunner.create(String.class, (input, ctx) -> {
            var cb = ctx.createCallback("approval", String.class);
            var s = ctx.stepAsync("fast", String.class, sc -> "s");
            var winner = DurableFuture.anyOf(cb, s);
            winners.add(winner);
            String branch;
            if ("s".equals(winner)) {
                branch = ctx.step("step-won", String.class, sc -> "A");
            } else {
                branch = ctx.step("callback-won", String.class, sc -> "B");
            }
            return branch + "|" + cb.get();
        });

        assertEquals(ExecutionStatus.PENDING, runner.run("in").getStatus());
        runner.completeCallback(runner.getCallbackId("approval"), "\"ok\"");
        var second = assertTimeoutPreemptively(DEADLINE, () -> runner.run("in"));

        System.out.println("[probe] branchOnWinner winners=" + winners + " status=" + second.getStatus() + " error="
                + second.getError().map(e -> e.errorType() + ": " + e.errorMessage()).orElse("none"));
        assertEquals(ExecutionStatus.SUCCEEDED, second.getStatus());
        assertEquals("A|ok", second.getResult(String.class));
    }

    /** Realistic pattern: approval raced against a durable timeout; approval arrives late. */
    @Test
    void approvalVersusDeadline_lateApprovalDoesNotRewriteHistory() {
        var runner = LocalDurableTestRunner.create(String.class, (input, ctx) -> {
            var approval = ctx.createCallback("approval", String.class);
            var deadline = ctx.waitAsync("deadline", Duration.ofSeconds(5));
            var winner = DurableFuture.anyOf(approval, deadline);
            winners.add(winner == null ? "<deadline>" : winner);
            if (winner == null) {
                ctx.step("escalate", String.class, sc -> "escalated");
                return "late:" + approval.get();
            }
            ctx.step("record-approval", String.class, sc -> "recorded");
            return "on-time:" + winner;
        });

        // Invocation 1: both pending -> suspend.
        assertEquals(ExecutionStatus.PENDING, runner.run("in").getStatus());
        // Invocation 2: deadline fires first -> escalate, then wait for the late approval.
        runner.advanceTime();
        assertEquals(ExecutionStatus.PENDING, runner.run("in").getStatus());
        // Invocation 3: approval arrives; replay must still see the deadline as the winner.
        runner.completeCallback(runner.getCallbackId("approval"), "\"yes\"");
        var third = assertTimeoutPreemptively(DEADLINE, () -> runner.run("in"));

        System.out.println("[probe] approvalVersusDeadline winners=" + winners + " status=" + third.getStatus()
                + " error=" + third.getError().map(e -> e.errorType() + ": " + e.errorMessage()).orElse("none"));
        assertEquals(ExecutionStatus.SUCCEEDED, third.getStatus());
        assertEquals("late:yes", third.getResult(String.class));
    }

    /** Two callbacks: the second-listed one completes first. */
    @Test
    void twoCallbacks_secondListedWinsFirst_replayKeepsIt() {
        var runner = LocalDurableTestRunner.create(String.class, (input, ctx) -> {
            var one = ctx.createCallback("one", String.class);
            var two = ctx.createCallback("two", String.class);
            var winner = DurableFuture.anyOf(one, two);
            winners.add(winner);
            return winner + "|" + one.get() + "," + two.get();
        });

        assertEquals(ExecutionStatus.PENDING, runner.run("in").getStatus());
        runner.completeCallback(runner.getCallbackId("two"), "\"T\"");
        assertEquals(ExecutionStatus.PENDING, runner.run("in").getStatus());
        runner.completeCallback(runner.getCallbackId("one"), "\"O\"");
        var third = assertTimeoutPreemptively(DEADLINE, () -> runner.run("in"));

        System.out.println("[probe] twoCallbacks winners=" + winners + " result=" + third.getResult(String.class));
        assertEquals(ExecutionStatus.SUCCEEDED, third.getStatus());
        assertEquals(List.of("T", "T"), winners, "anyOf winner changed between invocation 2 and replay");
        assertEquals("T|O,T", third.getResult(String.class));
    }
}

Run it with:

mvn -pl sdk-integration-tests -am test -Dtest=AnyOfReplayDeterminismProbeTest -Dsurefire.failIfNoSpecifiedTests=false

Root Cause

  • sdk/src/main/java/software/amazon/lambda/durable/DurableFuture.java:64-79:
    anyOf passes the operations to BaseDurableOperation.waitForFirstOperationCompletion
    and returns future.get() of whichever operation comes back. It creates no operation
    and records no winner.
  • sdk/src/main/java/software/amazon/lambda/durable/execution/ExecutionManager.java:706-708:
    waitForFirstOperationCompletion combines the operations' completion futures with
    CompletableFuture.anyOf(...). When more than one input is already complete,
    CompletableFuture.anyOf relays the first completed element in array order.
  • On replay, operations that the checkpoint history records as complete settle their
    completion futures while the handler re-creates them
    (BaseDurableOperation.markAlreadyCompleted), before anyOf runs. So every
    input that finished by the time of the replay counts as already complete, and argument
    order decides the winner instead of the order observed on the original invocation.

Existing coverage (BaseDurableOperationFirstCompletionTest,
DurableFutureAnyOfSuspensionTest) checks the pending-plus-settled and all-pending
cases, but not replay with several inputs already settled.

SDK Version

main at 2918c69d (3.1.1-SNAPSHOT); first observed at 067dbe05. This behavior
probably dates from the original anyOf implementation (#91). #730 changed how the
calling thread waits, but not how the winner is chosen.

Java Version

Reproduced on OpenJDK 25.0.4 (the project targets Java 17). The behavior comes from
CompletableFuture.anyOf, so the JDK version does not matter.

Is this a regression?

No.

Additional Context

Impact

  • The replay invariant breaks: identical input and checkpoint history no longer yield
    identical durable execution. Users can't avoid this by writing deterministic code,
    because the nondeterminism comes from the SDK combinator.
  • Branching on the winner turns into a terminal NonDeterministicExecutionException
    once the losing future also completes before a later replay. Using only the value
    silently changes results.
  • The in-repo examples/.../wait/WaitExample.java uses anyOf(continued, wait5seconds).
    It is exposed only if a replay happens after both inputs completed and before
    complete-processing is checkpointed.

Open questions for maintainers

  1. Fix shape. Do we follow the other SDKs and record the outcome as a durable
    operation, for example by running the race in a child context whose result is the
    winner? Or do we derive the winner from checkpoint data with no new operation, for
    example the earliest completion in the history? The second option adds nothing to
    history, but it must reproduce exactly what the live invocation observed. That is
    hard when completions are batched or close together, so recording the outcome looks
    safer.
  2. Compatibility. Recording a new operation changes the operation sequence. In-flight
    executions that were started on an older SDK and already passed an anyOf would hit
    a replay mismatch after an upgrade. Is a migration/versioning boundary needed, or a
    new API (for example a named ctx.anyOf(name, ...)/race) with the static method
    deprecated? The static method has no name or context to attach an operation to.
  3. Return shape. anyOf returns Object, so callers can't tell which future won
    when values overlap (for example null from a wait). Should a fix also expose the
    winner's identity, like Go's Select?
  4. Failures. Should the first failure win (race semantics, which anyOf uses today)
    or the first success (any semantics)? Should the recorded outcome include failures so
    replay rethrows the same error?
  5. Interaction with [Bug]: Unresolved Async Callback Keeps Execution Idly Running #734. A losing callback that is still pending keeps the execution
    alive. A child-context-based fix should settle that lifecycle at the same time.
  6. Conformance. No language-neutral conformance requirement covers race/any
    combinator replay. Should we propose one in
    aws/aws-durable-execution-conformance-tests? This repo's guidance says not to add
    conformance tests here.

Related: #91 (original anyOf design), #707 / #730 (anyOf suspension fix),
#734 (an unresolved losing callback keeps the execution running), #296, and #10, where
anyOf(waitAsync, stepAsync) is suggested as a step-timeout workaround. That is the
race-against-a-timer pattern this issue affects.

Activity

  1. added
    BREAKINGSomething that is going to break existing users
    parityProvides parity with other language implementations of the SDK
    on Nov 20, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    BREAKINGSomething that is going to break existing usersbugSomething isn't workingneeds-triageIssue needs triageparityProvides parity with other language implementations of the SDKpkg:sdkModule: sdk

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions