
Implementing Stripe-Like Idempotency Keys in Postgres - craigkerstiens
https://brandur.org/idempotency-keys
======
aejnsn
Craig, attended your talk at ATO earlier this week--good talk. I was the guy
who asked about performance considerations of joins in Postgres using UUIDs.

This post reads like it's vaguely implementing what should be in a queue
backend. There's a locked_at field in the schema, furthermore should this not
be performed via ...FOR UPDATE?

~~~
skrebbel
Care to share the answer to your question about uuid join performance? I've
had a hard time finding much about that on the internet.

~~~
craigkerstiens
Sure, there is definitely a little extra overhead on the join performance,
though my experience I've seen so many other issues become the biggest
bottleneck before joins of UUIDs. We regularly used UUID as identifies at
Heroku Postgres and use them at Citus as well and they work extremely well for
us.

It is of note that we're actually using the UUID datatype though and not just
generating a UUID and throwing it into a text field.

~~~
kbenson
> It is of note that we're actually using the UUID datatype though and not
> just generating a UUID and throwing it into a text field.

I was thinking that a UUID datatype implemented as a series of ints could have
fairly good join performance, since you can effectively treat it as a series
of separate smaller int indices that you join across, and I imagine that's a
well understood and optimized problem for years now. A text UUID field though,
ugh, that just seems so wasteful even before you get to optimization
techniques.

~~~
grzm
Reading your comment, it's not clear to me whether you're aware that the UUID
datatype in PostgreSQL is a 128-bit value as opposed to a text field; or if
you're just speaking of applications that use a database where native UUID is
not available. If the latter, feel free to ignore the rest of this :)

For comparison in storage:

    
    
        select pg_column_size('DDB5E9ED-60B6-4405-A6A8-18E339C7B172'::uuid) AS uuid_bytes,
               pg_column_size('DDB5E9ED-60B6-4405-A6A8-18E339C7B172'::text) AS text_bytes;
         uuid_bytes | text_bytes 
        ------------+------------
                 16 |         40
        (1 row)
    

As 'craigkerstiens points out, the index performance of the native UUID
datatype is very good: it's not a string comparison.

If you're using the UUID type to encode information that you may want to
access subfields of, you could create function indexes to do so. Otherwise, I
think indexing on the native UUID type is going to be better than a collection
of narrower fields and indexes.

Edit: Spell 'craigkerstiens correctly.

~~~
kbenson
> Reading your comment, it's not clear to me whether you're aware that the
> UUID datatype in PostgreSQL is a 128bit value as opposed to a text field

I was speaking towards the idea that some people throw UUIDs into text fields,
as implied by the parent;s clarification that they were _not_ doing that. For
example, in years past when that type may not have existed yet. People have
been talking about "just use a uuid for the primary key" for at least around a
decade now.

> As 'craigkierstens points out, the index performance of the native UUID
> datatype is very good: it's not a string comparison.

I would assume so! Any database that implemented an actual 128 bit numeric
type (no matter if it's converted to hexidecimal notation for display, ints
aren't stored in decimal either) as a text field would deserve quite a bit of
ridicule, in my opinion.

> If you're using the UUID type to encode information that you may want to
> access subfields of

And that answers a question I raised somewhat implicitly in my other comment,
which is why use a UUID in the first place. Because you can encode specific
sub type information into the parts. Thanks!

Edit: Forgot some words in my paragraph that mentioned ridicule, so I added
them to make sure it was obvious what and why I thought they would deserve
some ridicule (which is actually a bit stronger than how I generally like to
come across).

------
ianamartin
This is a really great article. I especially like that the author pointed out
some of the pitfalls with non-acid systems.

I started wondering at the beginning of the article how many people were going
to read it, try to implement it in mongo, and faceplant.

The only thing that strikes me as odd about the hypothetical example is that I
can’t imagine a universe where you would want a request for a ride to complete
72 hours after it initially failed.

I get the point of keeping the information around for 3 days in case of
errors. And perhaps my imagination is lacking, but most of the cases where I
would want to implement this model are time-sensitive. I need a ride now. I
need a message guaranteed to deliver exactly once.

Actually, the message queue aspect is how I think of this in general. It’s an
application/database layer that takes an at least once mq system and forces it
to be at most once. The combination then seems to imply exactly once.

Actually, after writing that out l, I can now think of a really great use case
for this that isn’t time sensitive. ETL systems.

Let’s say you are streaming live updates from some third party system to some
staging area and triggering processes from there through a broker to transform
and load data into a warehouse.

Your team pushes an update that breaks something on Friday night. Nobody works
that much on the weekend, so no ones cares. The dev lead gets notifications,
but gets to take it easy until Monday morning because they (trigger warning:
intentional singular they) know that everything can be replayed and resolved
after the bug is fixed. Even in the case of frequently changing api data, you
have the entire mutation history stored in your table and can accurately
replay it.

I can get on board with this.

And yeah. Sorry for thinking out loud. Now I’m thinking of all kinds of place
in my web apps this can be applied, as the article suggests. I think I need to
write a Python wrapper around this concept and make it dead simple to include
in projects.

Thank you again to the author for this very clear and excellent article.

------
Dowwie
Why not use Twitter's snowflake id? Instagram blogged about a Postgres
function that generates them

[http://rob.conery.io/2014/05/28/a-better-id-generator-for-
po...](http://rob.conery.io/2014/05/28/a-better-id-generator-for-postgresql/)

~~~
bgentry
Which of the problems covered in this post would be solved by Snowflake?

------
mazerackham
This is a really great article that lays out a proper implementation of
idempotent requests, something that many people (even very experienced
developers) regularly mess up. Thanks for sharing

------
no1youknowz
I'm using Memsql and it doesn't seem to have a UUID type, but after a quick
search with Mysql and UUID, the binary type is being used.

Can this be used with Memsql with the binary type and will I get the same
benefits?

Thanks

~~~
positr0n
Yes I've seen uuids in databases in both binary and varchar(36) forms.
Interacting with them with your tools/ORM won't be as nice as the native type,
but it's definitely doable and you get most of the benefits.

~~~
no1youknowz
Don't use an ORM, but otherwise thanks for the clarification!

------
poorman
I always throughly enjoy reading Brandur's articles.

------
sandGorgon
how do you guys implement atomic_phase ? im not a ruby guy, so am not able to
figure out the definition.

It looks like a atomic check-and-update, but more sophisticated.

------
koolba
This is a fantastic article.

------
naasking
"Idempotency keys", sheesh. Just use standard terminology: these are just
futures/promises.

~~~
dboreham
Wait...what? I'm all for "standard terminology" but they're for sure just not
the same thing. At all.

~~~
naasking
Sure they are. The idempotency key is simply a representation of a promise.
The E language and the Waterken server implement promise semantics exactly
like this: bind the results of a local or remote computation to a durable
representation, and that representation is used to store the result upon
completion. All future requests return the that stored result, ie.
idempotency.

In case of network partition where the client doesn't receive a reply, it can
safely and simply retry the operation on the promise, which returns the stored
result.

The E language popularized futures/promises, and it's still the gold standard.

~~~
saltcured
I think you are arguing a very niche perspective here.

The concept of idempotence in mathematics predates futures/promises by about a
century and is part of the general background understood by most people
exposed to any CS concepts. It has been prevalent across a wide range of
communities discussing networking protocol and message-passing designs since
the inception of the Internet. It appears in countless RFCs and other
standards documents which are read by people building web-based systems.

The concept of futures/promises you are promoting is honestly a niche part of
computer science from the 1970s which persists in an intersection of
distributed systems research and programming language research. It was never
the prevalent formalism shared by general CS or network engineering
communities. Meanwhile, a different aspect of the same 1970s concept has had a
rebirth as an asynchronous programming syntax and appears in widely consumed
languages. This different camp of PL researchers has essentially won the
popularity contest which defines the new "standard" meaning of futures and
promises for the general technical audience.

~~~
naasking
I'm not arguing against idempotency, or attempting to redefine it, I'm
pointing out that "idempotent key" as used in this article precisely denotes a
future. You might as well write an article on a "text-based client/server
GET/PUT/POST protocol" without labelling it HTTP.

It's stupid and unnecessarily obfuscated. This abstraction has a well-known
technical name, so use it, don't invent a new term.

And I frankly find it bizarre that you call futures/promises "niche" when
they're now part of every web browser in the world and millions of programmers
use them every day. The fact that these futures aren't durable isn't relevant
since the browser environment itself is transient.

~~~
saltcured
I find it bizarre for you to invoke the niche E programming language as if it
is obviously relevant to any use of unique identifiers for detecting replay of
messages. Why don't we criticize the author for his lack of Petri nets, or his
glaring omission of a denotational semantics in the appendix to his article?

At this point in the discussion, I am unsure that you understand promises in
distributed systems formalism, because you seem to be conflating it with the
ones recently en vogue in Javascript and other popular languages. Those
futures/promises in every web browser in the world are a purely local
asynchronous programming idiom, or what I like to think of as CPS
unconversion. I didn't suggest that browser programming is a niche concept,
but it also has nothing to do with organizing idempotent remote state changes
over a lossy message channel.

There is a vast literature using many different forms of explicit identifier
tied to some form of idempotence. Do you run around the IETF and W3C telling
them to stop saying "Message-ID" when they really mean futures/promises? Or
security researchers with their nonces? How about those pesky IPv4 and IPv6
designers with their silly ports, SYN cookies, and sequence numbers?

~~~
naasking
> Why don't we criticize the author for his lack of Petri nets, or his glaring
> omission of a denotational semantics in the appendix to his article?

Oh, was I asleep when Petri nets and denotational semantics are now used by
millions of programmers around the world?

> Those futures/promises in every web browser in the world are a purely local
> asynchronous programming idiom, or what I like to think of as CPS
> unconversion. I didn't suggest that browser programming is a niche concept,
> but it also has nothing to do with organizing idempotent remote state
> changes over a lossy message channel.

Of course it does, and I already made this point so I don't know why you're
ignoring it. Add durability to browser promises, and there you go. The
durability is irrelevant to the semantics.

> Do you run around the IETF and W3C telling them to stop saying "Message-ID"
> when they really mean futures/promises? Or security researchers with their
> nonces?

Nonces and Message-IDs have different semantics than promises. It's like
you're not even listening.

Idempotency keys have the same semantics as promises. Ergo, they are promises.
Promises are idempotent, but not every idempotent abstraction is a promise.
It's simple, I'm not sure where the confusion lies.

~~~
saltcured
You seemed fixated on establishing the primacy of the E programming language
as the inventor or rightful heir to the use of keys to correlate messages and
establish idempotent operations. So, I casually mentioned "prior art" of keys
used to manage message retry, deduplication, and replay avoidance.

For more complete examples, consider SMTP, NNTP, and their UUCP predecessors
which provided idempotent message transfer and eventually-consistent
replication using client-generated, globally distinct IDs. I absolutely fail
to see how these are different than a tweet ID or any similar solution for the
web. It is such standard practice, we take it for granted like the use of 2's
complement arithmetic.

The concept's reappearance in Twitter, Instagram, countless bespoke CRUD
applications, or the PostgreSQL example in this article are not "actually
promises" just because they're on the web. They are just the umpteenth
instance of source-labeled resources being tracked in a distributed system.
That is the web abstraction: a resource is created and we do not care whether
it is an event, object, message, computational job, bank transaction, or
packet of curry being delivered to my doorstep next Tuesday.

A Javascript promise is a local transform for asynchronous control flow. It
has zero intrinsic connection to any IO performed in that flow, nor in the
remote computation or storage that might occur. The programming language stops
where the message leaves the language's runtime and enters the real world of
distributed systems. It is not the control flow syntax which makes my
communication idempotent, it is me and the recipient agreeing to overlay
idempotence semantics on some data we agree to encode into our messages.

Message formats have nothing to do with programming languages. This is how we
understand Internet architecture. The local programming language and
programming paradigm of each node in the distributed system is immaterial to
the messaging semantics and interop standards and their concepts.

