Alexander BelangerCo-FounderHatchet

After reading Caity Weaver’s “I Found It: The Best Free Restaurant Bread in America”—a hero’s journey that starts with a rather simple question, posed at a local favorite restaurant, and ends with considerations of bread’s place in American culture—I realized two things. First, that I, too, greatly value a restaurant’s offering of free bread. Second, she and I share an interest in exploring seemingly trivial and impossible questions, such as is this the best free restaurant bread in America?

As a software engineer, I often find myself wondering if the thing I’m looking at is the first instance of that thing. In other words, is this thing—usually a feature, product or platform—truly novel?

So as I was drafting up a post about our latest feature, idempotency keys, I set out to answer one such question: what was the first instance of an idempotency key?

What’s an idempotency key?

Idempotency keys are unique identifiers that allow API handlers or downstream consumers to de-duplicate messages that have been delivered more than once. If the handler has seen that string before, it’ll ignore the message.

Consider my dog, Ringo (this is going somewhere, I promise). Ringo really likes his kibble (shoutout to Purina Pro Plan 30/20 Sport), so much so that exactly at 6pm, he’ll wake up from a coma-like slumber, grab his slow feeder bowl, and drop it at my feet.

Ringo’s a sneaky bastard. He’ll get his dinner from me, and then amble into the adjacent room to beg his (non-biological) mother for more food. He knows that she doesn’t know he’s already been fed. On more than one occasion, he’s gotten double dinner.

If my wife and I were a web server, we’d store an idempotency key to record the first instance of the meal. Instead we resort to yelling “I’M FEEDING RINGO” two times a day.

(For a deeper dive on how to implement a system like this on an actual web server, I’m a fan of this post.)

Idempotency keys are a method of solving a fundamental problem in distributed systems, which is that exactly-once delivery is impossible, and we need some additional tooling to guarantee exactly-once processing. Ringo with his food bowl is an at-least-once delivery. My yelling guarantees exactly-once processing. With me so far?

Stripe and AWS

I live in Claude now, so naturally I asked it first: “When was the first instance of an idempotency key?” It responds:

Around 2011, with Stripe’s Idempotency-Key header.

I don’t know if this is accurate or not, but I like to test Claude. Sun Tzu puts it, “So in war, the way is to avoid what is strong, and strike at what is weak.” As in battle, so in Claude chat. My next move, a bluff:

This is wrong. Both the date and the provider.

And Claude says:

Fair pushback—and I should own something here: my previous answer presented a confident single fact where none really exists. Searching now, I can’t find any authoritative record of a “first” idempotency key. Stripe popularized the name, but I was wrong to state it as the origin—and the “2011” date was my inference, not a documented fact.

There it is, humankind’s small win for the day. Claude spews out some more random paragraphs and apologizes again.

From what I can tell, Stripe’s Idempotency-Key header was published circa 2015 (though some blogs cite it without primary sources to be earlier). Stripe was indeed the first API I used which advertised this header. Good job Collisons.

Drunk with power, I bully Claude some more. It also cites Amazon EC2’s ClientToken behavior, which permitted clients to attach a unique string to mutating requests like RunInstances. If you use the same ClientToken with the same parameters, EC2 returns the original result; if you modify the parameters, you get an IdempotentParameterMismatch error.

This behavior was recently codified in an IETF draft specification, which credits the idempotency patterns documented by Stripe, and also credits a 2005 Internet-Draft by Mark Nottingham called “POST Once Exactly.” I open my browser to read some old specs and forums, satisfied with my victory.

POST Once Exactly

POST Once Exactly, which you can find here, describes the motivating use-case for idempotency key behavior to be the following from the HTTP specification (RFC 2616):

Non-idempotent methods or sequences MUST NOT be automatically retried, although user agents MAY offer a human operator the choice of retrying the request(s).

To solve this problem, in the POE specification, it’s proposed that a client issues a GET request first, which retrieves a POST URL. This POST URL must only accept a single successful POST. The “idempotency key” (note: this isn’t explicitly what it’s called in Nottingham’s implementation) is the unique part of the URL.

POE wasn’t widely adopted, but it’s one of the first specifications I could find with some guidelines on how a RESTful API could easily implement idempotency-key behavior.

Idempotency at the transport level

Going back to ancient times of the early 2000s—a time of the spec wars between SOAP and REST—there were a number of abstruse specifications that aimed to implement exactly-once-processing with idempotency-key behavior. Two of these were the OASIS ebXML Message Service spec and the related WS-ReliableMessaging, co-published by Microsoft, IBM, BEA, and TIBCO. These are “transport-level” specifications, so if a service defines its contract as NoDuplicateDelivery, the transport implements message deduplication.

Compare this with the RESTful way of doing things, where the application (or business layer) would send a custom header back to the client, and the business layer would decide how to handle this custom header in a future request. Whether exactly-once-processing should be handled at the transport layer is an interesting question; this article is a good read.

Anyway, after spending an afternoon reading the OASIS ebXML spec and Microsoft’s WS-ReliableMessaging, I came to the realization that WS-ReliableMessaging was released for two reasons: (1) Microsoft was butthurt that it wasn’t in the conversation, and (2) they wanted to make reliable messaging more confusing. I Google pictures of sweaty Steve Ballmer to feel better.

Why am I writing this?

The more I think about it, the more I realize humanity has invented and re-invented idempotency guarantees thousands of times throughout the years.

The Incas, for example, used quipu—a sophisticated knot-tying system—to record important data like census counts, labor obligations, and inventories. In the mit’a labor obligation system, it was expected that able-bodied men would provide their labor to community projects on a rotational system. It would be recorded when a community received their labor obligation in the knot record; if they returned with another request, it would be denied.

Another example could be tally sticks, splitting a notched piece of wood down the middle between a creditor and a debtor, the number of notches representing the debt. In order to establish that the debt was repaid, the grain of both halves of the stick would be joined and need to match. (Granted, one could try to create a fake stick. Or you could lose your stick.)

Admittedly I’ve lost the plot a bit. Do I really want my “final answer” to be an Incan quipu? Was the Incan empire perhaps the first example of a distributed system? A computer, even?

No, I need something that rules out the incas, ledgers, a random thought about carrier pigeon networks, and my wife and I yelling at each other in our apartment.

New rule: idempotency keys must touch electronic computers. I do some more research, which finally brings me to a fascinating and salient paper…

Birrell and Nelson’s “Implementing RPCs”

Well before the emergence of the internet and the world wide web, distributed systems research was built around the remote procedure call (RPC), which aimed to solve the problem of invoking a specific function (or procedure) on a different machine, usually within a trusted network. These RPC implementations were packages that were tightly coupled to a runtime or environment, like the Cedar programming environment at Xerox PARC—an experimental language and development environment that powered much of PARC’s systems research in the early 1980s.

One of the papers emerging from this research was Birrell and Nelson’s “Implementing Remote Procedure Calls,” published in 1984, which builds upon Bruce Jay Nelson’s original PhD thesis—where he coined the term Remote Procedure Call—to document an implementation of an RPC package for use in distributed computation at Xerox PARC.

This paper outlines the earliest example that I can find of an “idempotency key,” which is a call identifier for each RPC. Here it is, my actual answer. I’ll let Birrell and Nelson tell it:

The call identifier serves two purposes. It allows the caller to determine that the result packet is truly the result of his current call (not, for example, a much delayed result of some previous call), and it allows the callee to eliminate duplicate call packets (caused by retransmissions, for example)… The RPCRuntime on a callee machine maintains a table giving the sequence number of the last call invoked by each calling activity. When a call packet is received, its call identifier is looked up in this table. The call packet can be discarded as a duplicate (possibly after acknowledgment) unless its sequence number is greater than that given in this table.

After all this “research,” I’m still not sure if this is the oldest example of idempotency keys that meets my criteria. But I do know that ours is the newest. Go check it out!