6 ms·
What Is Idempotence?
- js2 8y agoAt 13:45 in this interview from 2003, Sergey Brin and Larry Page try to explain idempotence to Terry Gross (NPR's Fresh Air host): http://www.npr.org/2003/10/14/167643282/google-founders-larry-page-and-sergey-brin-part-2 http://www.npr.org/2003/10/14/167643282/google-founders-larr... (It does not go very well.) Edit: I can't find a transcript, so I just transcribed that portion of the interview myself, starting at 13:45: TG: Now I'll tell you, in preparing for this, I decided, let me Google Google, so I typed in "Google" into the Google search, and I came up with a lot of Google things in the regular search, but in the "Are you feeling lucky?" search, I got nothing. LP: Well you just got Google itself. TG: Yeah, I just got Google itself. Oh, I see, Google was giving me itself. LP: Yeah. TG: Oh. LP: In computer science, we call that recursion. [laugh]. TG: Oh, you even have a name for it. [laugh]. I didn't quite get that. I kept thinking it was just repeating itself. I didn't realize it was giving me itself. [laugh]. LP: [laugh] TG: And what's the name for it? LP: Uh, recursion. It's... kind of... Sergey is giving me a dirty look. TG: Why? LP: It's a loose definition. [laugh] TG: Lighten up Sergey. [laugh] LP: It's a loose interpretation of... [laugh]... recursion. TG: Sergey, what's the more literal interpretation? SB: The technical term is you got itself back. TG: Right? SB: There's not really much beyond that. [laugh] TG: Okay. SB: Idempotence. How about that. TG: Say it again. SB: Idempotence. TG: What is it? SB: That's when you uh... [laugh]... Maybe I should stop while I'm ahead... TG: ...You're just making this up, aren't you... SB: ...Before I dig a deeper hole. Idempotence is when you do something and you get the original thing back. TG: Oh, so that's a real word? LP: It's a mathematical term. SB: Yeah, yeah, but it's also just as loose an interpretation as Larry's was of recursion.
- jolmg 8y agoVery cringy. :)
- dang 8y agoI remember listening to that interview way back when and feeling so uncomfortable that I almost turned off the radio. But now, reading that transcript, I just find it satisfying that they said the words recursion and idempotence on Fresh Air. With Terry Gross!
- cgrand-net 8y agoIsn’t it a fix point rather?
- Tomminn 8y agoBy the way, one way to describe idempotence is a function whose range is the fixed points of the function. Fixed point is very close. Your idea here is that google_search_lucky(search_string), where search_string="google" returns itself. Which would be a fixed point. The rub is that the function google_search_lucky(search_string) would in all likelihood return the URL of a website if it was to return a string (necessary for even the possibility of a fix point), so the proper fix point would be "https://www.google.com" https://www.google.com". If I was trying to map this to mathematical ideas, I'd say the point here is that the function google_search(search_string, is_lucky) with the argument ("google", is_lucky= true) returns the _function_ google_search(search_string, is_lucky) . So it's more like the argument ("google", is_lucky= true) is an identity for the function google_search(search_string, is_lucky).
- ummonk 8y agoYeah! It's a fixed point.
- ams6110 8y agoClassic illustration of why conversations between geeky technology people and "normal" people usually and in awkward silence after about two minutes.
- maxxxxx 8y agoI have totally given up on even trying to explain what I do at work. It never leads to anything.
- hombre_fatal 8y agoAt the same time, I used to do speed dating and too often had to hear the poor guy next to me confuse "what do you do?" with "what exactly do you do day to day in as painstakingly technical detail as possible?" when the other party doesn't even know if they're an astronaut vs full-time dog walker.
- didibus 8y agoI've been struggling lately with distinguishing between things that are inherently idempotent and things that are made to be using deduplication. For example, assignment is inherently idempotent. Assign the same thing twice, and the world is still in the same state as before. Calling assign over and over with the same arguments thus results in the same outcome. For example: a = 10; a = 10; But, incrementing is not: a++; a++; That said, you can dedupe the incrementing operation: increment(a, id1); increment(a, id1); Where increment keeps track of if it has already been called for a and id1, and cached the result. Thus subsequent calls dedupe on the cache and return the same result. In my opinion, these are different. While increment is made idempotent, it requires a deduplication strategy to achieve it. It is not an inherent property of incrementing. Deduplication is really hard to get right. And it prevents retrying an operation. When someone says, this is safe to retry, its actually saying, you can't retry this, subsequent calls are noop. Is there a better vocabulary for these two things? I don't like how idempotency is ambiguous and refers to both. I'd like to be able to know if something is idempotent by its design, or if it is through the use of deduplication.
- gwillz 8y agoI'm just spitballing here. Could it be that either deduplication or idempotency are a sub category of the other? Or perhaps describe different aspects of the operation? Like, you could argue that deduplication is a form of idempotency. Or that deduplication is an effect of idempotency. I've always thought that an idempotent operation could actually continue an operation where it left off, rather than repeating the whole operation. Deduplication is a side effect of that process. Is reentrant the right word? Like, you can repeat or continue this operation. This may mean no-op calls, or may mean it repeats everything but still achieves deduplication.
- theoh 8y agoWhat you call "deduplication" is usually called memoization. https://en.wikipedia.org/wiki/Memoization https://en.wikipedia.org/wiki/Memoization It only works for pure functions (functions which have no side effects). It is unaffected by concurrency for that reason. Idempotency doesn't come into the picture because the state of the world doesn't affect the return value. Assignment is an operation with a side effect: it changes the state of the world (as well as possibly returning a value, depending on the language). So assignment of the same value more than once is idempotent only in single-threaded code. If there's more than one thread in play, you might find that assigning twice has a different result that assigning once. So, the rule is that whenever the return value of a function can be cached (memoization or what you are calling deduplication) then it is implicit that the function has no side effects. There is no overlap between that category of functions and idempotent operations with side effects. NB there is another meaning of idempotence which relates to function composition, e.g. abs(abs(x)) = abs(x). You can probably see that in that case idempotence refers to a single expression rather than the state of the whole program.
- mbushey 8y agoI wrote a blog with this exact title from the standpoint of a SysAdmin/DevOps Engineer: https://www.sendthemtomir.com/blog/what-is-idempotence https://www.sendthemtomir.com/blog/what-is-idempotence
- lxe 8y agoAfter reading this I realized I’ve been conflating indempotence with purity.
- phamilton 8y agoReferential integrity is the ~synonym for purity that is often used.
- Animats 8y agoThere's a similar property of interest - order independence. That is, doing A, then B has the same final state as doing B, then A. Does that have a cool name?
- kylebarron 8y agohttps://en.m.wikipedia.org/wiki/Commutative_property https://en.m.wikipedia.org/wiki/Commutative_property ?
- GhostVII 8y agoThat's the commutative property. It is really nice to have operations that are commutative monoids, where you can re-order the operands, and combine them in any order, and get the same result. Then if you want to perform that operation (ex. Addition) over a set of operands (ex. Integers), you can do it in parallel, where each process can take any set of intermediate results, and perform the operation on them.
- Veedrac 8y agoThe standard term seems to be ‘permutable’, for A(B(x)) = B(A(x)). One can also say these functions commute with respect to composition. This is slightly different from the classical notion of commutativity, since the operator (composition) isn't generally commutative.
- Animats 8y agoAh. That's the right term. Thanks. This is an important property for database updates.
- phamilton 8y agoLately I've been trying hard to not just get idempotence but to get a full CRDT. While established CRDTs like an OR-set are great, simply framing a problem in terms of a max value has been really useful. Also useful are fuse values, where you record the first non zero value. Getting commutativity in addition to idempotence is great. Examples where this is useful tend to be pretty obvious in hindsight (things like accepting partially reported data, or recording a high water mark), and most people have built systems using these properties but taking a more formal approach has made it easier to identify and confirm that the order of operations doesn't need to be strict and at least once delivery is fine.
- matt-attack 8y agoI would have thought that pressing an elevator call button is non-idempotent, since it affected something on the backend. It changed state. An elevator button is a POST. I thought POSTs like that that perform an action are non-idempotent. Where as asking for the current floor is idempotent (i.e. a GET). Do I have this all wrong?
- GhostVII 8y agoI think you have it wrong. As far as I understand, an operation is idempotent if you can perform it any number of times consecutively (without another operation taking place), and have the resulting state be the same. So for the elevator, you can press it 1 time, or 100 times, and it will have the same result of calling the elevator to your floor, so long as no operation (ex. The elevator arriving at your floor) takes place in between button presses.
- rswail 8y agoI don't agree. Idempotency in terms of REST (or equivalent) is about the effect on the receiver of the call. Pressing the button each time is definitely not idempotent, because it is a change of state of the button. The fact that the server may choose to ignore this change in terms of the travel of the elevator is not relevant to the change of state of the button transmitted by it being pressed.
- GhostVII 8y agoSo what is an example of a call that is idempotent? Are only requests that don't modify state considered idempotent, by your definition?
- Izkata 8y ago...which is weird because in the elevator example, the state isn't being modified. The effect on the receiver, to use their terminology, is always to set the button to "on" or "called" or whatever you want to name it. Hence, the elevator button example is idempotent. Quick edit: Someone else below makes a good point - in at least one part of the world, a second button press does act as "cancel". Maybe that's the confusion here?
- xiaodai 8y agoIt's impotence for people living in Deutschland
- latchkey 8y agoThe elevator analogy doesn't work in Vietnam, pressing the button again sometimes cancels the elevator.
- j7ake 8y agoAn analogy from linear algebra might help with the intuition: a projection is idempotent. Projecting a projection still gives you the same output.
- fibo 8y agoActually idempotent comes from algebra, in particular from ring theory. An ideal is idempotent if its generator, say it a, multiplied by itself n times, equals the ring identity. See also https://en.wikipedia.org/wiki/Idempotent_(ring_theory) https://en.wikipedia.org/wiki/Idempotent_(ring_theory) The definition of idempotent used in IT, assumes that n=2. Another concept stolen from Mathematics and misused in IT is Topology.
- jhanschoo 8y ago> Actually idempotent comes from algebra, in particular from ring theory. An ideal is idempotent if its generator, say it a, multiplied by itself n times, equals the ring identity. The Wikipedia article you linked to defined it for ring elements rather than for ideals of rings and for n=2. I agree that it is sometimes useful to define it more generally where it is in respect to some integer n, analogous to nilpotence. You may have encountered this notion first in ring theory which may have led to this impression, but it is by no means an idea originating from this specific context. For example, another comment points out that in linear algebra, a projection operator is said to have the idempotence property.