How long will a 64 bit Transaction-ID last in PostgreSQL?
andreas.scherbaum.la
How long will a 64 bit Transaction-ID last in PostgreSQL?
1–10 of 33 posts
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#2The 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 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).
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#3The 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 p…
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.
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#4The 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 p…
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.
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#5The 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 p…
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.
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#6The 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 p…
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.
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)
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#7The 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 p…
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.
Square rooting will get you in the proper ballpark. I imagine that's why UUIDs are 128-bit values.
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#8The 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 p…
Moving to 64-bit Transaction IDs has been discussed on HN before. 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.
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#9The 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 p…
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.
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 :)
Re: How long will a 64 bit Transaction-ID last in PostgreSQL?
#10Earlier quoted context omitted.
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.
Square rooting will get you in the proper ballpark. I imagine that's why UUIDs are 128-bit values.
Correct on both counts.