6 ms·

Implementing Stripe-Like Idempotency Keys in Postgres

182 points by craigkerstiens 9y ago

mazerackham 9y ago
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
aejnsn 9y ago
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 9y ago
  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 9y ago
    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 9y ago
      > 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.
      - netcraft 9y ago
        We use a combination of both - the app is old enough that uuid's weren't an option when it was started - and like the gp said, even in the case of text fields theres a bunch of other things that degrade perf before those joins become an issue. that being said, we are hopeful that the new pg10 hash indexes will be a good fit for these (we already cant do range lookups on a uuid) and are hopeful that we will get a speed improvement with them when we get to that point.
        kbenson 9y ago
        I'm curious, did you ever do testing on whether converting a UUID to a a pair of 64-bit ints and using a composite primary key worked well? I imagine it's annoying to deal with at both the schema and application level, but it is space efficient. Depending on how optimized numeric/decimal types are, those might by a good fit as well. You said other things degrade perf before that matters, so it may be moot, but wasting space for what's going to be in an index seems likely to have performance problems that affect other things subtly (such as ballooning your index memory usage). If we're storing UUID's in canonical form that's 36 bytes of information (32+4 for separators, and if you're stripping separators why not convert to a numeric form anyway...). Even if we assume we're only storing 32 characters, that's 256 bits, so we're doubling the storage requirements and memory usage for an index. Assuming you're using UUID's because you have a lot of records and want to keep them unique, that space presumably matters (especially if you're using it multiple places because there are relations). If you don't have a huge amount of records, a sufficiently large auto-incrementing int field that increments by a random amount between 1 and 255, and a randomized bit shuffle codified into a reversible function (extend int to 128 bits, use previously decided bit shuffle to rearrange bits. Fully reversible) would solve that need and make everyone who has to deal with the DB's life easier. Just convert the ints to and from UUID representations between your view and controller. I've never had to actually deal with UUID's at the DB level, so there could be some major downsides to these that I'm not thinking of. At this point, I'm just not sure what storing a UUID in a database gets you.
        netcraft 9y ago
    - Dowwie 9y ago
      Snowflake id is a BIGINT. How does it contrast from UUID, other than joining faster?
      - grzm 9y ago
        Trivially, a UUID is wider (128 bits as opposed to 64). You can choose to generate your UUIDs using a Instragram[0]-like strategy so you can, for example, benefit from temporal/spatial locality in the indexes. There may be performance consequences of using the wider datatype, but I suspect this could be overwhelmed by other application concerns if you're dealing with data that benefits from the wider type. [0] https://engineering.instagram.com/sharding-ids-at-instagram-1cf5a71e5a5c https://engineering.instagram.com/sharding-ids-at-instagram-... Edit: Update to correct snowflake to Instagram's strategy. I make this mistake often enough that it's now self-reinforcing :/
        Dowwie 9y ago
        So you are presumably agreeing that snowflake makes sense?
        grzm 9y ago
        Oh, of course! Depending on your application needs, it certainly can work. The benefit of PostgreSQL UUID is that you effectively have twice the bits, so you have more room to encode data and satisfy your uniqueness guarantees.
- craigkerstiens 9y ago
  Hi online :) I'll wait a bit to see if Brandur (author chimes in first), otherwise happy to pile in some thoughts.
  - brandur 9y ago
    > 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? Yeah, I'm relying on transactional semantics to guarantee no contention during the lock, but the part that I'd intended as important here is really just the idea of locking the key — not the particular implementation. I think alternatively using a `FOR UPDATE` is totally plausible and likely even to be more performant than what I've written here. Try to imagine this as more of a "ideas guide" rather than a dictation on precise implementation.
poorman 9y ago
I always throughly enjoy reading Brandur's articles.
Dowwie 9y ago
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-postgresql/ http://rob.conery.io/2014/05/28/a-better-id-generator-for-po...
- bgentry 9y ago
  Which of the problems covered in this post would be solved by Snowflake?
naasking 9y ago
"Idempotency keys", sheesh. Just use standard terminology: these are just futures/promises.
- pbreit 9y ago
  Futures/promises means nothing to me. But I always thought an idempotency key was just sending in a time stamp or something else unique.
  - naasking 9y ago
    Time stamps are not unique, you definitely need something unique, like a GUID to distinguish it from such tokens bound to other client requests. And you'd be better served learning about the more general abstraction rather than learning a single domain-specific trick. This solution is obvious once you know about promises.
- dboreham 9y ago
  Wait...what? I'm all for "standard terminology" but they're for sure just not the same thing. At all.
  - naasking 9y ago
    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 9y ago
      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.
koolba 9y ago
This is a fantastic article.
sandGorgon 9y ago
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.
no1youknowz 9y ago
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 9y ago
  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 9y ago
    Don't use an ORM, but otherwise thanks for the clarification!
ianamartin 9y ago
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.

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

aejnsn 9y ago

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 9y ago
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 9y ago
  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 9y ago
    > 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.
    - netcraft 9y ago
      We use a combination of both - the app is old enough that uuid's weren't an option when it was started - and like the gp said, even in the case of text fields theres a bunch of other things that degrade perf before those joins become an issue. that being said, we are hopeful that the new pg10 hash indexes will be a good fit for these (we already cant do range lookups on a uuid) and are hopeful that we will get a speed improvement with them when we get to that point.
      - kbenson 9y ago
        I'm curious, did you ever do testing on whether converting a UUID to a a pair of 64-bit ints and using a composite primary key worked well? I imagine it's annoying to deal with at both the schema and application level, but it is space efficient. Depending on how optimized numeric/decimal types are, those might by a good fit as well. You said other things degrade perf before that matters, so it may be moot, but wasting space for what's going to be in an index seems likely to have performance problems that affect other things subtly (such as ballooning your index memory usage). If we're storing UUID's in canonical form that's 36 bytes of information (32+4 for separators, and if you're stripping separators why not convert to a numeric form anyway...). Even if we assume we're only storing 32 characters, that's 256 bits, so we're doubling the storage requirements and memory usage for an index. Assuming you're using UUID's because you have a lot of records and want to keep them unique, that space presumably matters (especially if you're using it multiple places because there are relations). If you don't have a huge amount of records, a sufficiently large auto-incrementing int field that increments by a random amount between 1 and 255, and a randomized bit shuffle codified into a reversible function (extend int to 128 bits, use previously decided bit shuffle to rearrange bits. Fully reversible) would solve that need and make everyone who has to deal with the DB's life easier. Just convert the ints to and from UUID representations between your view and controller. I've never had to actually deal with UUID's at the DB level, so there could be some major downsides to these that I'm not thinking of. At this point, I'm just not sure what storing a UUID in a database gets you.
        netcraft 9y ago
  - Dowwie 9y ago
    Snowflake id is a BIGINT. How does it contrast from UUID, other than joining faster?
    - grzm 9y ago
      Trivially, a UUID is wider (128 bits as opposed to 64). You can choose to generate your UUIDs using a Instragram[0]-like strategy so you can, for example, benefit from temporal/spatial locality in the indexes. There may be performance consequences of using the wider datatype, but I suspect this could be overwhelmed by other application concerns if you're dealing with data that benefits from the wider type. [0] https://engineering.instagram.com/sharding-ids-at-instagram-1cf5a71e5a5c https://engineering.instagram.com/sharding-ids-at-instagram-... Edit: Update to correct snowflake to Instagram's strategy. I make this mistake often enough that it's now self-reinforcing :/
      - Dowwie 9y ago
        So you are presumably agreeing that snowflake makes sense?
        grzm 9y ago
        Oh, of course! Depending on your application needs, it certainly can work. The benefit of PostgreSQL UUID is that you effectively have twice the bits, so you have more room to encode data and satisfy your uniqueness guarantees.
craigkerstiens 9y ago
Hi online :) I'll wait a bit to see if Brandur (author chimes in first), otherwise happy to pile in some thoughts.
- brandur 9y ago
  > 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? Yeah, I'm relying on transactional semantics to guarantee no contention during the lock, but the part that I'd intended as important here is really just the idea of locking the key — not the particular implementation. I think alternatively using a `FOR UPDATE` is totally plausible and likely even to be more performant than what I've written here. Try to imagine this as more of a "ideas guide" rather than a dictation on precise implementation.

poorman 9y ago

I always throughly enjoy reading Brandur's articles.

Dowwie 9y ago

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-postgresql/ http://rob.conery.io/2014/05/28/a-better-id-generator-for-po...

bgentry 9y ago
Which of the problems covered in this post would be solved by Snowflake?

naasking 9y ago

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

pbreit 9y ago
Futures/promises means nothing to me. But I always thought an idempotency key was just sending in a time stamp or something else unique.
- naasking 9y ago
  Time stamps are not unique, you definitely need something unique, like a GUID to distinguish it from such tokens bound to other client requests. And you'd be better served learning about the more general abstraction rather than learning a single domain-specific trick. This solution is obvious once you know about promises.
dboreham 9y ago
Wait...what? I'm all for "standard terminology" but they're for sure just not the same thing. At all.
- naasking 9y ago
  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 9y ago
    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.

koolba 9y ago

This is a fantastic article.

sandGorgon 9y ago

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.

no1youknowz 9y ago

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 9y ago
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 9y ago
  Don't use an ORM, but otherwise thanks for the clarification!

ianamartin 9y ago

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.