4 ms·

The author talks a bit about the architecture of PostgreSQL transactions, touching on lazy transaction ID consumption and vacuuming. Notably, writes require IDs

The author talks a bit about the architecture of PostgreSQL transactions, touching on lazy transaction ID consumption and vacuuming. Notably, writes require IDs but reads do not. So this is focused on write-optimized workloads. If you want to get the basic tl;dr which answers the headline: these IDs will last so long it’s almost not worth quantifying. This is an obvious calculation even if you assume ostentatatious performance requirements three orders of magnitude greater than the author’s: 2^64 / (86,000 * 1,000,000,000) = 213,503.9 The author uses 1,000,000 writes/second; I prefer 1,000,000,000 since it’s more ridiculous. There are 86,000 seconds in a day. It will take you the better part of a millenium to exhaust those IDs, assuming you consume an average of one billion every single second. The author didn’t talk about collisions, but those are worth mentioning because you could even confidently assign these randomly instead of incrementally. Since a collision will occur (in expectation) after 2^63 transactions, you shouldn’t even have to worry about a single one occuring (on average) for almost 300 years. Of course, using 64-bit IDs comes with nontrivial space increase - every single tuple will increase by a factor of 2. EDIT: Original collision estimate is wrong, see corrections. I took (2^n)/2 = 2^(n-1) as the birthday bound instead of 2^(n/2).

loeg 8y ago
Another way of looking at it is: CPUs run at about 3 GHz; assume you can increment your 64 bit variable once per cycle (extremely optimistic); it will still take a ludicrous amount of time to overflow the 64-bit variable. I find this is a good rough intuition for upper bound on writes/sec. (Your 1 billion writes/sec figure works out to more or less the same assumption, at 1 Ghz.) The conclusion is the same, of course.
simcop2387 8y ago
Actually you'd expect a collision with 50% probability after only a much smaller fraction of the 2^64 space. This would be the birthday paradox, and unfortunately I can't find a calculator or software at the moment that can handle 2^64 power factorial to calculate it properly.
- Gasparila 8y ago
  Back of the envelope math for birthday paradox is root n. So in this case with ~50% probability you'll get a collision after 2^32 IDs (or after 4 seconds of 1 billion writes a second)
- andreareina 8y ago
  Square rooting will get you in the proper ballpark. I imagine that's why UUIDs are 128-bit values.
  - garmaine 8y ago
    Correct on both counts.
- throwawaymath 8y ago
  Ah, good point. I'm aware of the birthday paradox but I took (2^n)/2 = 2^(n-1) instead of 2^(n/2) as the birthday bound. Nice correction :)
hamandcheese 8y ago
My admittedly naive understanding of transaction IDs and MVCC is that they can’t be random because transactions are ordered and (depending on your isolation level) that ordering controls what’s visible inside a given transaction. Generally speaking a transaction can’t see any rows with a transaction ID greater than its own transaction ID.
- anarazel 8y ago
  We can't use transaction ids for that however, because they're necessarily assigned by the time a transaction starts to write, whereas visibility is determined by the time transactions commit. Snapshots, the datastructure that determines which transaction's writes ought to be visible and which not, use transaction ids as cutoff values however, to make visibility determinations cheaper. A second large reasons why we'd not want to go for randomness is that we need to store data for each transaction id, namely whether it committed or not. If we'd assign them randomly we'd need to keep around a lot more of that data, and accesses would be a lot more expensive because there'd basically not be any locality.
- KMag 8y ago
  The transaction ordering you mentioned is sufficient if transactions are always retired in the order they begin, but it's not a necessary condition for even the highest transaction isolation levels. However, I don't think anyone has discovered a trick to getting high concurrent performance out of a database that strictly retires transactions in chronological order. At the highest transaction isolation levels, you need to be able to perform a topological sort of the transaction dependency graph. That does require that the graph is acyclic, but doesn't preclude the DB engine from pretending a transaction that started later actually started earlier (or even had its first write chronologically earlier). For full transaction isolation, the DB engine just needs to be able to pretend transactions happened in a linear order, but that order isn't dictated by the chronological order of the first operation of each transaction. (It's not even constrained by the chronological order of the first write operation of each transaction in DBs that only track write-write conflicts.) The easiest way to keep track of this consistency is some kind of monotonically increasing counter "timestamp" (or something like a vector of them in an asynchronous / distributed system ... Lamport vector clocks or similar), but this timestamp doesn't need to be identical to a transaction ID, and doesn't have to be unique. It's possible that most databases make unique transaction IDs moonlight as timestamps, but it's not a fundamental constraint.
vinayan3 8y ago
Moving to 64-bit Transaction IDs has been discussed on HN before. https://news.ycombinator.com/item?id=9936711 https://news.ycombinator.com/item?id=9936711 The discussion to move within Postgres was early as 2005. Moving to 48-bit seems possible but like as the other HN discussions says supposedly other real world systems have wrapped around with that too.

loeg 8y ago

Another way of looking at it is: CPUs run at about 3 GHz; assume you can increment your 64 bit variable once per cycle (extremely optimistic); it will still take a ludicrous amount of time to overflow the 64-bit variable. I find this is a good rough intuition for upper bound on writes/sec. (Your 1 billion writes/sec figure works out to more or less the same assumption, at 1 Ghz.) The conclusion is the same, of course.

simcop2387 8y ago

Actually you'd expect a collision with 50% probability after only a much smaller fraction of the 2^64 space. This would be the birthday paradox, and unfortunately I can't find a calculator or software at the moment that can handle 2^64 power factorial to calculate it properly.

Gasparila 8y ago
Back of the envelope math for birthday paradox is root n. So in this case with ~50% probability you'll get a collision after 2^32 IDs (or after 4 seconds of 1 billion writes a second)
andreareina 8y ago
Square rooting will get you in the proper ballpark. I imagine that's why UUIDs are 128-bit values.
- garmaine 8y ago
  Correct on both counts.
throwawaymath 8y ago
Ah, good point. I'm aware of the birthday paradox but I took (2^n)/2 = 2^(n-1) instead of 2^(n/2) as the birthday bound. Nice correction :)

hamandcheese 8y ago

My admittedly naive understanding of transaction IDs and MVCC is that they can’t be random because transactions are ordered and (depending on your isolation level) that ordering controls what’s visible inside a given transaction. Generally speaking a transaction can’t see any rows with a transaction ID greater than its own transaction ID.

anarazel 8y ago
We can't use transaction ids for that however, because they're necessarily assigned by the time a transaction starts to write, whereas visibility is determined by the time transactions commit. Snapshots, the datastructure that determines which transaction's writes ought to be visible and which not, use transaction ids as cutoff values however, to make visibility determinations cheaper. A second large reasons why we'd not want to go for randomness is that we need to store data for each transaction id, namely whether it committed or not. If we'd assign them randomly we'd need to keep around a lot more of that data, and accesses would be a lot more expensive because there'd basically not be any locality.
KMag 8y ago
The transaction ordering you mentioned is sufficient if transactions are always retired in the order they begin, but it's not a necessary condition for even the highest transaction isolation levels. However, I don't think anyone has discovered a trick to getting high concurrent performance out of a database that strictly retires transactions in chronological order. At the highest transaction isolation levels, you need to be able to perform a topological sort of the transaction dependency graph. That does require that the graph is acyclic, but doesn't preclude the DB engine from pretending a transaction that started later actually started earlier (or even had its first write chronologically earlier). For full transaction isolation, the DB engine just needs to be able to pretend transactions happened in a linear order, but that order isn't dictated by the chronological order of the first operation of each transaction. (It's not even constrained by the chronological order of the first write operation of each transaction in DBs that only track write-write conflicts.) The easiest way to keep track of this consistency is some kind of monotonically increasing counter "timestamp" (or something like a vector of them in an asynchronous / distributed system ... Lamport vector clocks or similar), but this timestamp doesn't need to be identical to a transaction ID, and doesn't have to be unique. It's possible that most databases make unique transaction IDs moonlight as timestamps, but it's not a fundamental constraint.

vinayan3 8y ago

Moving to 64-bit Transaction IDs has been discussed on HN before. https://news.ycombinator.com/item?id=9936711 https://news.ycombinator.com/item?id=9936711 The discussion to move within Postgres was early as 2005. Moving to 48-bit seems possible but like as the other HN discussions says supposedly other real world systems have wrapped around with that too.