5 ms·

>The Postgres patch solves the problem by repurposing 12 bits of the UUID’s random component to increase the precision of the timestamp down to nanosecond granu

>The Postgres patch solves the problem by repurposing 12 bits of the UUID’s random component to increase the precision of the timestamp down to nanosecond granularity [...] >It makes a repeated UUID between processes more likely, but there’s still 62 bits of randomness left to make use of, so collisions remain vastly unlikely. Does it? Even though the number of random bits has decreased, the time interval to create such a duplicate has also decreased, namely to an interval of one nanosecond.

paulddraper 2y ago
Depends if you think sub-millisecond locality is significant.
londons_explore 2y ago
I could imagine that certain nanoseconds might be vastly more likely than other nanoseconds. For example, imagine you have a router that sends network packets out at the start of each microsecond, synced to wall time. Or the OS scheduler always wakes processes up on a millisecond timer tick or some polling loop. Now, when those packets are received by a postgres server and processed, the time to do that is probably fairly consistent - meaning that X nanoseconds past the microsecond you probably get most records being created.
- UltraSane 2y ago
  But only one nanosecond slower or faster and you get another set of 4.611 billion billion random IDs. I think random variations in buffer depths and CPU speeds will easily introduce hundreds of nanoseconds of timing variations. syncing any two things to less than 1 nanosecond is incredibly hard and doesn't happen by accident.
  - zamadatix 2y ago
    The important part is the events in time aren't going to be as random as the actual random source. The chances of an actual collision remain low but the distribution of events over time is a weaker (in relative terms) source of random bits compared to proper "random" sources which won't have obvious bias at all.
    - UltraSane 2y ago
      I am sure there is bias but 1 nanosecond is an incredibly narrow window. It really would be an interesting experiment to evaluate the optimal balance of bits for timestamp and for random value. What about hostname and even process ID? Snowflake IDs are 63 bits long with 41 bits as a millisecond timestamp, 10 bits as a machine ID, and 12 bits as a sequential counter.
      - WorldMaker 2y ago
        Similarly for direct comparison, ULID has 48-bit timestamps, also at the millisecond, and 80 random bits. Also to compare, the ULID spec technique for monotonicity is to take a single random value and then start incrementing the lowest bits, trading random entropy for direct "nearness", one after another. Versus the rand_a approach is effectively using the most significant bits, but keeping more random entropy.
      - zamadatix 2y ago
        I suppose that would depend entirely on how you measure what optimal is. Optimal randomness is 128 bits from the best random source and 0 bits from anything else, like time. Optimal "just random enough for my use case but no more so I can fit other information in the value" depends entirely on the requirement of your use case (more specifically, not just "for databases" but "for my database to... on the hardware... in which the access is... on the presumed growth..." and so on). For picking a "good enough" value 12 bits is probably as reasonable as one will find generic reason for.
        fc417fc802 2y ago
        [dead]
  - mlyle 2y ago
    We're not talking about nanoseconds of real time; we're talking about nanoseconds as measured by the CPU doing the processing. Nanoseconds are not likely to be a uniform variate.
    - UltraSane 2y ago
      Yes and they are also not likely to be so non-uniform that more than 6.411 billion billion events all happen in one nanosecond.
      - mlyle 2y ago
        Note it's not that number, but roughly the square root of that number, that matters. And they might be quite non-uniform. If the scheduler tick and the nanosecond clock are synchronous, you could end up with a few thousand popular values instead of a billion. It's not a real concern today, and probably won't be a real concern in 10 years, but it's not so far removed from possibility that no one has to think about it.
        UltraSane 2y ago
        Good point about the square root of the random part. I guess that is why the 63 bit Snowflake ID uses a sequential counter.
  - deepsun 2y ago
    System doesn't give you 1 nanosecond precision really. It varies by OS+hardware, from what I remember you may get like 641 nanosecond precision. The number is nanoseconds, yes, but you never get "next nanosecond". In other words, every number you get has the same mod 641. In other systems you may get like 40,000 precision or even worse on SPECTRE/MELTDOWN-protected systems.
michaelt 2y ago
Imagine if you were generating 16 UUIDs per nanosecond, every nanosecond. According to [1] due to the birthday paradox, the probability of a collision in any given nanosecond would be 3E−17 which of course sounds pretty low But there are 3.154e+16 nanoseconds in a year - and if you get out your high-precision calculator, it'll tell you there's a 61.41% chance of a collision in a year. Of course you might very well say "Who needs 16 UUIDs per nanosecond anyway?" [1] https://www.bdayprob.com/ https://www.bdayprob.com/
- Horffupolde 2y ago
  So what if there’s a collision? If the column is UNIQUE at most it’ll ROLLBACK on INSERT. 16 INSERTS per nanosecond is 16 billion TPS. At that scale you’ll have other problems.

paulddraper 2y ago

Depends if you think sub-millisecond locality is significant.

londons_explore 2y ago

I could imagine that certain nanoseconds might be vastly more likely than other nanoseconds. For example, imagine you have a router that sends network packets out at the start of each microsecond, synced to wall time. Or the OS scheduler always wakes processes up on a millisecond timer tick or some polling loop. Now, when those packets are received by a postgres server and processed, the time to do that is probably fairly consistent - meaning that X nanoseconds past the microsecond you probably get most records being created.

UltraSane 2y ago
But only one nanosecond slower or faster and you get another set of 4.611 billion billion random IDs. I think random variations in buffer depths and CPU speeds will easily introduce hundreds of nanoseconds of timing variations. syncing any two things to less than 1 nanosecond is incredibly hard and doesn't happen by accident.
- zamadatix 2y ago
  The important part is the events in time aren't going to be as random as the actual random source. The chances of an actual collision remain low but the distribution of events over time is a weaker (in relative terms) source of random bits compared to proper "random" sources which won't have obvious bias at all.
  - UltraSane 2y ago
    I am sure there is bias but 1 nanosecond is an incredibly narrow window. It really would be an interesting experiment to evaluate the optimal balance of bits for timestamp and for random value. What about hostname and even process ID? Snowflake IDs are 63 bits long with 41 bits as a millisecond timestamp, 10 bits as a machine ID, and 12 bits as a sequential counter.
    - WorldMaker 2y ago
      Similarly for direct comparison, ULID has 48-bit timestamps, also at the millisecond, and 80 random bits. Also to compare, the ULID spec technique for monotonicity is to take a single random value and then start incrementing the lowest bits, trading random entropy for direct "nearness", one after another. Versus the rand_a approach is effectively using the most significant bits, but keeping more random entropy.
    - zamadatix 2y ago
      I suppose that would depend entirely on how you measure what optimal is. Optimal randomness is 128 bits from the best random source and 0 bits from anything else, like time. Optimal "just random enough for my use case but no more so I can fit other information in the value" depends entirely on the requirement of your use case (more specifically, not just "for databases" but "for my database to... on the hardware... in which the access is... on the presumed growth..." and so on). For picking a "good enough" value 12 bits is probably as reasonable as one will find generic reason for.
      - fc417fc802 2y ago
        [dead]
- mlyle 2y ago
  We're not talking about nanoseconds of real time; we're talking about nanoseconds as measured by the CPU doing the processing. Nanoseconds are not likely to be a uniform variate.
  - UltraSane 2y ago
    Yes and they are also not likely to be so non-uniform that more than 6.411 billion billion events all happen in one nanosecond.
    - mlyle 2y ago
      Note it's not that number, but roughly the square root of that number, that matters. And they might be quite non-uniform. If the scheduler tick and the nanosecond clock are synchronous, you could end up with a few thousand popular values instead of a billion. It's not a real concern today, and probably won't be a real concern in 10 years, but it's not so far removed from possibility that no one has to think about it.
      - UltraSane 2y ago
        Good point about the square root of the random part. I guess that is why the 63 bit Snowflake ID uses a sequential counter.
- deepsun 2y ago
  System doesn't give you 1 nanosecond precision really. It varies by OS+hardware, from what I remember you may get like 641 nanosecond precision. The number is nanoseconds, yes, but you never get "next nanosecond". In other words, every number you get has the same mod 641. In other systems you may get like 40,000 precision or even worse on SPECTRE/MELTDOWN-protected systems.

michaelt 2y ago

Imagine if you were generating 16 UUIDs per nanosecond, every nanosecond. According to [1] due to the birthday paradox, the probability of a collision in any given nanosecond would be 3E−17 which of course sounds pretty low But there are 3.154e+16 nanoseconds in a year - and if you get out your high-precision calculator, it'll tell you there's a 61.41% chance of a collision in a year. Of course you might very well say "Who needs 16 UUIDs per nanosecond anyway?" [1] https://www.bdayprob.com/ https://www.bdayprob.com/

Horffupolde 2y ago
So what if there’s a collision? If the column is UNIQUE at most it’ll ROLLBACK on INSERT. 16 INSERTS per nanosecond is 16 billion TPS. At that scale you’ll have other problems.