Idempotency | Hacker News Reader

Idempotency

berkansasmaz.com

90 pointsthunderbong64 comments

One of the things I think I did right in my career is working on payment and billing systems early on.

It does teach you how to build at least semi-reliable software because people tend to get really mad when you screw with their money. It also is a good introduction to regulation and compliance.

Idempotency was is one of the concepts you get taught on day one in that field (as kind of demonstrated by that being the example used by the author in the article).

Interestingly, I didn’t have to be taught about idempotency early on in my career; I’m pretty sure I didn’t even know what that word meant. I’m a naturally curious person and I was always curious about the failure cases for the software I worked on—e.g., “What happens if this request is successful but times out before returning a response to the client?” I honestly assumed every programmer asked these types of questions, but I learned the hard way over the years that this isn’t the case.

The only reason I knew about idempotency is because growing up I was a little shit and I learned that you could break a LOT of electronics by getting it to do a second thing midway before finishing doing the first thing.

If it had a screen and buttons, I would try to break it.

So I started striving for highly reliable systems not because there are professional bad actors out there or spammers or to achieve high performance… but because there’s another little shit out there.

> getting it to do a second thing midway before finishing doing the first thing

I'm not sure this is the kind of failure idempotency is design to tackle.

Idempotency tackles the issue of handling multiple requests for doing the same thing, isn't it?

> Idempotency tackles the issue of handling multiple requests for doing the same thing, isn't it?

yeah... there should be no extra side effect if you call something more than once on it with the same parameters. ie foo(x) is the same as foo(foo(x)) is the same as foo(foo(foo(x)))

or in networking GET x is the same as GET x followed by a GET x etc... the GET request doesn't (*shouldn't) change anything.

It gave me an intuitive understanding of state machines and idempotency is one solution to transitions.

If you start with State A and a call changes it to State B, what does running the call again do? A->B? But you’re already at B. Shit’s going to break. Redesign your system.

In this example, it seems the API should return some 4xx error.

If there's a process with two steps, moving from Step A to B requires the process to be at Step A and it's already at step B, it should return an error. At first glance, this doesn't seem the kind of problem that idempotency is supposed to prevent...

Instead of idempotency you can return a 4xx error too. You use idempotency because it’s logistically less complicated for the client.

Hopefully many do, but it is much easier to talk about when you learn the terminology.

Yeah, I need to send this to one of my vendors. We send them an order number, and they send us back an order key from their system. However, we can only look up an order by that key, and they will happily accept and process duplicate order numbers. Therefore, if for whatever reason we don't receive a key during the order submission process, we have no way to look up the order afterwards by order number to see if it went through and what the key is. They don't seem to understand why that is bad.

Another good one is instant messaging. Both latency and reliability (exactly once delivery) are important.

Doing so using microservices will teach you a lot more (but may not be immediately applicable as it's not so favored).

Idempotency is one mathematical concept that's pretty useful for software engineers to understand. Heck, might be more useful than BigO.

- Useful to know when you work with APIs (as the article outlines).

- Very useful when working with background jobs. You're not gonna have a good time if those aren't idempotent.

- Good to know for interviews. I was asked to explain idempotency a handful of times, weird as that is.

I want to see an Up Goer Five⁰ explanation of all the ways "you will not have a good time today" with distributed systems.

0: https://xkcd.com/1133/

I've asked it a few times. Not knowing the specific word is fine -- but I expect devs touching http requests at all to understand the concept.

Interestingly, the mathematical definition (and functional programming definition) of idempotency is slightly different. Or I've seen it used slightly differently, anyways - specifically, a function is idempotent if the result of f(x) is the same result as f(f(x)).

I've seen this lead to some confusing back and forth between software engineers, where one engineer means one definition, and the other engineer meant the other definition.

One irritating thing is that there are at least 4 different senses of "idempotent" in the wild:

* In the object-oriented sense, `obj.f(args...)` does not mutate `obj` after the first time.

* For pure unary functions, `f∘f === f` - that is, repeated application does not change the result, e.g. `abs(abs(x)) === abs(x)`

* For pure binary functions, `f(x, x) === x`. I'm not sure how useful this is but it seems to be used in math.

* For pure binary functions, `f(x, a) === x` and/or `f(a, x) === x`. These would probably be individually called left-idempotent and right-idempotent in some order, along with two-sided idempotent for the combination (akin to left identity (related!), left inverse, etc.); notably these are more general than (and all imply) the above. This could be extended to further arities; usually the preserved element will be either first or last in sane functions. "and not" works in one direction; many functions like "bitwise and", "bitwise or", "min", and "max" work in both directions.

Sense 2 is an example of sense 3, where the binary function is ∘.

> Good to know for interviews. I was asked to explain idempotency a handful of times, weird as that is.

Do you now reply "I've been asked this before, so your question has no effect"?

I know it's just an introduction so perhaps it shouldn't be taken too literally, but the sequence diagram of how to make an order idempotent feels like instructions on how to create race conditions.

You can't check for existence to guard against duplicate creation without either locking or another approach to making the Exists-or-Create step atomic.

If you were to put in the sequence as described, you'd have something which is idempotent most of the time, until it isn't, when API requests come in and get forwarded to the endpoint before the caching server can cache the first creation.

Presumably unique constraints could also solve for this, in a properly written transaction.

That depends how your API is structured, and again comes back to the atomicity and idempotency.

If your API is for example: "POST /orders/create {products:[{bananas:1}], shippingAddress:{},...}", then it's not clear how you would check uniqueness, because you'd want the same person to make the same order at different times by design.

To prevent double-submit, and make it idempotent, you need to add extra information.

One way to address this is generating transaction/sequence/correlation IDs at the very start of the process. So for example when you first request the order form, a transaction / correlation ID (called in the article an Idempotency key) is generated.

Then you would include that transaction ID in the order, and could prevent duplicate use of an order ID at multiple levels of the system including the database.

One design is to have a single-source-of-truth, and have at the (internal) API layer a state machine for a transaction. Once an order has been processed then it's impossible to make another order because there's no "make order" step from the state that an order is in having been processed. Again you need some kind of correlation ID to track which state machine needs loading.

That however is less scalable than other solutions including things like event-sourced architecture, which would also prevent duplicate orders through eventual consistency although there's less (or no) guarantee in many such systems that the order submitted "first" would win the race and not be superseded by the second. Such behaviour is fine if documented.

As I understand it, it's not checking for the existence of the resource but for the existence of the request. Assuming the requests are unique to a user/client and the user has a sequential conversation with the API server, the server would process the received requests in order and would reject the duplicate.

However, if the requests of the same key (duplicates) are sent to any of several API servers, you have a problem that must be resolved as you mentioned.

In the first case, if the API server dies, the client should establish a new connection and get new idempotency keys.

Even on the same server there's still a race condition if checking the key has been used and marking the key as used aren't atomic if more than one request can be handled at once.

My day-job is Data Engineering. We've carefully built our ETL patterns/tools/data structures to be idempotent. It's amazing how freeing this is. Dealing with cascading failures, intermittent failures, delays, re-runs and time-zones are all os much more manageable when we know that just re-running any given task will do the right thing.

It's also amazing how hard of a concept idempotent data pipelines are for some folks to understand, and how much effort they'll put into _avoiding_ idempotency.

I can attest. I tried explaining Idempotency to people building an industrial laser controller once.

Idempotent calls might be used redundantly to ensure that a particular state or setting exists at a particular time.

I don't really care that a particular setting was already set yesterday or an hour ago.

Conversely, it's probably a really a good idea to be sure it's on that particular setting right now, before I fire the laser!

I try to make my pipelines idempotent, but a couple of them require us to send the output file to someone's email. Does anyone know how to send an email idempotently?

Email is quintessentially "fire and forget" message passing, so there's no way to guarantee mail has been delivered and no way to "pull it back".

You can embed tracking in your email to see if it's been opened, and not resend in that case, but this will be flakey as it's easy to disable email trackers.

Come here to learn more details and maybe find answers to my questions. Unfortunately, the article is very modest explaining how to work with idempotency.

Missing key answers like what about two requests in flight, how to store and query requests status reliably.

The article mention requests should be ACID, but the diagram has caching storage. Would redis/dynamodb work here?

Redis has SETEX that will set if not existing. Can be used as a lock.

True, generic test-and-set ops can be used. But what about if there is already a request in-flight? Do you wait or fail? What is the experience working with either? What is the experience invalidation the cache key? And similar other questions :) So more practical than theoretical side to idempotency

You might prefer my attempt at a similar explanation:

https://github.com/stickfigure/blog/wiki/How-to-%28and-how-n...

And yet, the idempotent solution in the article is not idempotent.

The author proposes a solution that needs three steps: query a cache, execute, update the cache. These are not atomic and, therefore, not thread-safe. As a result, if a second request arrives before the first is finished, the operation will be executed again.

The relevant draft spec for a standard way of signalling this: https://datatracker.ietf.org/doc/html/draft-ietf-httpapi-ide...

The diagram in the article shows “Header Idempotency Key : "A"” (honestly not sure whether the second, third and fourth of those spaces exist: the diagram’s text kerning is atrocious). This should be the header field `Idempotency-Key: "A"`, though “A” would be a bad string to use (see Security Considerations).

Idempotentancy on POST isn't just about preventing double posting. For POST the RFC says you can return 303 when the call to create a resource would have resulted in generating an existing resource. You need a Location header for allowing the client to redirect to the corresponding GET. This allows clients to POST multiple times (over time) for the same resources and not have to handle 400 errors.

> Let's say we have a food ordering application, and to keep our application simple, let's say we have two basic services, Shipping and Order. When one of our customers places an order, first the order is created, and then shipping instructions are created. If all transactions are successful, it sends a notification to the client. Even in this simple scenario, many failures can occur.

In a real-world scenario, this is what seems to happen to Uber Eats in India back in 2019 when everyone can gets free food because of a bug in Uber's backend.

https://youtu.be/PVzcWBmN2L0

I always remember this from the example my professor gave -

   'raise the control rods by 1 inch'

vs 'raise the control rods to a height of 4 inches'

Does it still count as idempotent if you achieve it by adding a timestamp parameter to each function to specify which version of the global state you want to use?

I just like saying "idempotency" so everyone thinks I am super smart. "Yeaaaa, I am going to need you to go ahead and make that idempotent, yea, great, thanksss."

Cool series, I look forward to future posts.

pet peeve: idempotency is badly named. idempotent literally translated is ‘same power.’ two or more things having the same power doesn’t necessarily mean they produce same, single result. if that were the case we wouldn’t need the special handling for idempotent instructions/commands/actions to ensure duplicates are not created.

I’m not totally sure, but in math “idempotent” elements are those for which x^2 = x. And so in software engineering it refers to operations for which doing them twice has the same effect as doing them once. Maybe this is what is meant by “same power”?

i could agree with you. my pet peeve is that the name of the phenomenon where repeated executions result in same result (where same even includes unique identifier) shouldn't be idempotency. especially in computing where, in my experience, any attempt to implement it involves some logic which checks to see if we've already observed the desired effect of the action.

It refers to functions where f(x) = x.

That's actually the formula for nullipotency, where applying it 0 times is the same as applying it any number of times.

I believe idempotency is when f(f(x)) = f(x)

No, it refers to functions f where forall x, f(f(x)) = f(x).

You can abuse notation slightly to see this as f^2(x) = f(x). (This kind of notation is actually used enough to be comfortable to most mathematicians.) From here it's not much of a stretch to eta-contract this to f^2 = f.

And so we've ended up back in the same place...

Fancy word for an obvious concept.

You say it like it's something bad. Having a common vocabulary is extremely helpful for communication. Instead of restating the obvious concept over and over all the time you can just ask your peer "is this idempotent?".

Naming something also helps us to think about it. "A square" is also an obvious concept, but by naming it you can reason about it more easily, and use it to define more abstract concepts later. One of the main reasons we - humans - dominate the earth, is because we evolved an advanced language, which allows us to name ideas and build upon them.

Vocabulary can delude and manipulate as well. Idempotent serves to delude more than it informs. In this case idempotent is taking an trivial and obvious concept and makes it seem more snobbish. Why write a whole article about an obvious and trivial concept? Perhaps the word itself is making it more complex then it is.

The software industry is littered with these words. Design patterns especially. Rob Pike once referred to it as infatuation with nomenclature.

Seconded. It make the lowly programmer feel intelligent.

"The PUT method is used to update a resource on the server. It is idempotent because sending the same request multiple times will result in the same resource state as if the request had only been sent once."

That's where I stopped reading.

Reading this article is completely safe even if you already understand idempotency.

One of the wonderful things about idempotency is how it enables caching in various systems.

I want to meet the article that isn’t safe to read even if you’re familiar with its content.

Non-idempotent actions often have Lovecraftian outcomes, so I can imagine...

Maybe some religious texts

A loved one's suicide note.

Well, it's conceivable that you could end up creating a separate copy of the information in your brain's neural network.

Now imagine you keep getting interrupted in the middle, but really want to read it all, thus gradually filling the whole of your brain capacity.

I’d like to think my brain does some deduplication on interrupt. Maybe when allocating large chunks?

I can’t find it anymore, but there was someone who had some home automation where they could open or close their garage door from the internet. However it would occasionally open automatically. Eventually they realized it happens whenever they opened their browser. Apparently, they visited the page often enough for it to be favorited on their homepage. Unfortunately, it was written to act on any request, including GET requests and so whenever they opened his browser to the home page, it would fetch the favicon or preview and trigger the automation.

That's not unsafe, just insecure.

The curse of being familiar with its content is that you know when the author of the article is giving bad advice, explaining wrong about how things work, or having an opposite opinion on a polarizing topic. If you are not familiar with the subject these things won't bother you.

A typical chain letter that implores you to pass it on or you'll suffer dire consequences?

The Theory and Practice of Oligarchical Collectivism (if you're an IngSoc outer party member, anyway)

> HTTP (Hypertext Transfer Protocol) is a widely used protocol

Uhh thanks chatgpt.

Reply on news.ycombinator.com