geohashim

deadline

A small Java 21 library that passes a request's time budget from service to service over HTTP. Each hop knows how long the user is still waiting, stops work nobody is waiting for, skips retries that couldn't finish, and reports where the time went.

Timeouts are usually set one hop at a time, and each looks sensible on its own. The user's app gives up after 2 s. The gateway gives orders 3.5 s and three attempts; orders gives inventory 1 s and three attempts. Together, a request the user abandoned at 2 s keeps three services busy for almost ten seconds. gRPC solves this with deadlines. Plain HTTP services usually have nothing.

View on GitHub How it works

Plays the six stages below in order, about 40 seconds. Scroll or press Esc to stop.

Language
Java 21, no runtime dependencies
Tests
49 passing with ./mvnw verify, JUnit 5
Speaks
HTTP/1.1 through the JDK's own HttpClient and HttpServer
Headers
Deadline-Budget-Ms in, Deadline-Trace back
Adoption
No header, no deadline: services can switch one at a time
License
MIT
java -jar target/deadline.jar demo user -> gateway -> orders -> inventory, each a separate JVM. The user waits 2.0 s.

Real runs of the built jar, output verbatim. The first two start three services as separate JVMs talking HTTP on loopback. The last two are curl against services started by hand with deadline service, the same three hops with the demo's settings.

1Send what's left, not a time of day

A caller sends Deadline-Budget-Ms: 1830: whole milliseconds it is still prepared to wait. The callee turns that into an instant on its own monotonic clock the moment the request arrives, so hosts with skewed clocks still agree. This is what gRPC does with grpc-timeout.

  • The cost is that network transit isn't counted. Each caller keeps a margin back for it.
  • Zero or negative means the caller had already run out. That request gets a 504 without being worked on.
  • Anything that isn't a whole number is a 400. Budgets over an hour are clamped to an hour.
  • No header means no deadline: configured timeouts, every retry, as if the library weren't there.

Building it turned up the negative case. The parser once returned -1 for both "absent" and "-20 ms", so an expired request ran with no deadline at all. A test now holds it.

One service, seven headers

    Real curl runs against deadline service --name inventory --work 1500 --slots 1 --margin 50: a hop whose work holds a worker for 1.5 s. Statuses, bodies and trace headers are verbatim. The service keeps 10 ms of each budget back to write its reply, so a 600 ms budget stops the work at 589.

    2Give each attempt the smaller of its timeout and what's left

    Before every attempt, Plan.next looks at the call's policy and the request's deadline. The caller waits min(timeout, remaining), and tells the callee that, less a margin, so the callee's answer gets back inside the wait.

    • An attempt with less than minUseful + margin left is never sent. It couldn't finish, so it would only add load.
    • Plan is a pure function of the policy and a deadline. Its tests run on a virtual clock that moves only when told to.
    • 200,000 random policies are checked against four invariants: the callee's budget is never spent on arrival, never more than what's left less the margin, the caller never waits past its own deadline, and the answer always fits inside the wait.

    The orders hop, decision by decision

      The decisions PlanTest.theDemoScenarioOnAVirtualClock asserts: a 1,890 ms deadline, a 1,000 ms timeout, three attempts, a 50 ms margin and 50 ms minimum. On the virtual clock each callee uses its whole budget, the worst case. The real run in stage 5 made the same three decisions.

      3The callee stops when the budget does

      DeadlineHandler wraps a service's handler. It rejects a request that arrives with nothing left, waits for a worker slot only as long as the budget allows, and turns DeadlineExceededException from ctx.check into a 504.

      • A queued request gives up its place when its budget runs out, instead of being served after nobody is waiting.
      • Stopping is cooperative: at ctx.check(), at a downstream call, or in the queue. Nothing interrupts threads, so a long loop that never checks runs to the end.
      • Work finished after the caller hung up is still reported. An early version skipped its listener when writing the reply threw, which hid exactly the waste the demo measures.

      Two requests, one worker

      The same one-worker inventory service, sent request a with a 1,200 ms budget and, 0.1 s later, request b with 500 ms. The bars are drawn from each reply's own Deadline-Trace: start, end and time queued, in ms from when that request arrived. The responses are verbatim.

      4Send the trace back with the reply

      Each hop returns its spans in a Deadline-Trace response header, with times relative to when it received the request. The caller shifts them by when it sent the request and nests them under the attempt, so the edge gets the whole tree with no clock synchronisation.

      • Every hop answers before its deadline, so the trace arrives on failures too. A 504 says which hop ran out and what it was doing.
      • Past 64 spans the rest are counted, not kept, so the header stays small.
      • A malformed header gives an empty trace, never an exception.

      One header, the whole chain

      curl -si -H 'Deadline-Budget-Ms: 1950' localhost:47311/ to the gateway

        Three services started by hand with the demo's settings: gateway calls orders with a 3.5 s timeout, orders works 20 ms and calls inventory with 1 s, inventory works 1.5 s. The header is verbatim; each comma-separated span is decoded below it. The budget is the user's 2 s less a 50 ms margin, as the demo's user sends.

        User stops waitingAbove this line each hop works out how much of the user's wait is left. Below it is the moment the user gives up, and whether anything is still running for them after it.

        5One slow request, three JVMs

        deadline demo starts gateway, orders and inventory as separate JVMs on loopback, with the same timeouts and retries in both runs. Inventory is having a slow day: every call takes 1.5 s. The only difference between the runs is whether the budget travels with the request.

        • Without it, the user gives up at 2 s, and nine of the twelve calls between services happen after that, for nobody.
        • With it, every hop stops when the budget runs out, and the retries that couldn't finish are never sent. The user gets a 504 before giving up, carrying inventory's own report.
        • The two runs switch only CallPolicy.withPropagate and DeadlineHandler.enforce, so the comparison is like for like.

        Nagle's algorithm nearly ate the margin. The JDK server writes headers and body separately, and a small 504 sat about 40 ms behind a delayed ACK, so it reached the user just after they gave up. The services set sun.net.httpserver.nodelay.

        Every time a service held a worker for this request

        Working while the user waitsWorking after the user stopped waiting
        One run of deadline demo --svg on this page's machine. The bars are read back out of the SVG it wrote, which draws them from the services' own logs; the summary lines are its terminal output, verbatim.

        6Under load, the waste crowds out live requests

        deadline load sends 30 requests a second for 20 seconds. Inventory has 8 workers and takes 100 ms a call, except for 5% of requests, which take 1.5 s. The timeouts are the demo's, and the same requests are slow in both runs.

        • Without deadlines each slow request becomes nine 1.5 s inventory calls. Inventory's workers fill with retries for users who have left, and the fast requests queue behind them, time out, and retry in turn.
        • With deadlines a slow request costs about two seconds of inventory time and then stops, so the fast ones keep flowing.
        • --check fails the run unless deadlines answer at least 85%, at least 30 points more than without, with under 1% of work after users left, and unless the run without them wasted most of its work. CI runs it on every push.

        600 requests, both ways

        java -jar target/deadline.jar load --rate 30 --seconds 20 --check, one run on this page's machine, verbatim. Worker time is the total time services held a worker; drain is how long they kept working after the last user stopped waiting.

        Measured, not assumed

        Everything below was re-run on one Linux machine with 12 cores, while it was busy with other jobs. The README's figures come from the same kind of setup and say so: they show the shape of the effect, not a benchmark of any real system.

        The demo, twice

        When the user heard back, with deadlines, against the README's run:

        README1.86 s
        Run 11.87 s
        Run 21.93 s

        All inside the user's 2 s. Without deadlines the services worked on until 9.69 s and 9.67 s, against the README's 9.61 s, with 12 calls and 9 after the user left every time.

        The load test, four times

        Share of users answered in time, without and with deadlines:

        30/s: 15.0% → 94.5%30/s: 15.0% → 94.5%
        8/s: 56.3% → 91.9%8/s: 57.5% → 91.9%

        The README has 15.2% and 94.5% at 30/s, and 79% and 54% without deadlines at 8/s, which it says small timing differences tip. With deadlines the misses equal the number of slow requests exactly: 13 of 160 at 8/s, 33 of 600 at 30/s.

        The suite

        ./mvnw -B verify, the two runs after the first, as Maven reported them:

        40.9 s22.3 s

        Most of it is ClusterTest, which runs the demo at half speed in one JVM, both ways, 18.9 s here. In CI the test job's verify step took 33 s, and the load check 145 s.

        49 tests, decisions to whole chain

        Counted by Surefire under ./mvnw -B verify, as CI runs it: 39 test methods, plus 10 cases of one parameterised test of malformed budgets. All passing on OpenJDK 21.

          Weighted toward the claim

          • The decisions, on a virtual clock: the boundaries, the demo's orders hop decision by decision, and 200,000 random policies against the invariants.
          • The handler and client over real HTTP: malformed and expired budgets, work cut short, retries on 5xx but not 4xx, forwarded headers, attempts not started, and traces merged across two hops.
          • The whole chain, both ways: without deadlines inventory must be called nine times and work long after the user left; with them everything stops before the user's wait is up, with no work after it, and inventory's own report reaches the user.
          • Regressions: the negative budget and the listener skipped when the caller hung up, two of the three bugs the README records. The third, Nagle, would fail the chain test's timing.

          CI also runs demo and load --check with three separate JVMs on every push.

          Deliberately missing

          Interrupting work
          Stopping is cooperative. A CPU loop or a blocking JDBC call that never checks runs to the end.
          Frameworks
          HTTP/1.1 through the JDK only. No servlet filter, Spring or Netty integration, and no gRPC, which has deadlines already.
          Backoff and retry budgets
          Retries are immediate. Backoff, jitter and hedging reduce retry storms from another direction and would combine with this.
          Trust
          The budget header is clamped to an hour but not an authorisation boundary. A caller can always ask for more time than its own caller gave it.
          Maven Central
          Not published. Build it from source.

          Run it

          git clone https://github.com/ahmed-hashim-pro/deadline.git && cd deadline
./mvnw -q package                    # builds, runs the 49 tests
java -jar target/deadline.jar demo   # one slow request, about 20 s
java -jar target/deadline.jar load   # the load table, about 3 minutes

# Only Docker:
docker run --rm -v "$PWD":/w -w /w maven:3.9-eclipse-temurin-21 \
  sh -c 'mvn -q package && java -jar target/deadline.jar demo'

          JDK 21; the Maven wrapper fetches Maven itself. demo --svg timeline.svg also draws the timeline, and load --rate N --seconds S changes the traffic.