4 ms·

> first component (prefix) of the identifier is a sortable timestamp > values generated are practically sequential These statements aren’t strict enough to be

> first component (prefix) of the identifier is a sortable timestamp > values generated are practically sequential These statements aren’t strict enough to be relied on. Maybe you have engineered the hell out of your distributed clock scheme, and your IDs actually are completely monotonic, which is great. But you probably haven’t done that, which means conflicts will surely happen and you must handle them gracefully.

QuadrupleA 3y ago
But the timestamp is less than half the bits. The rest are random. So timestamp conflicts don't matter.
- erik_seaberg 3y ago
  By “conflict” I don’t mean a UUID collision, I agree with the logic that 2^128 is so much entropy that memory corruption is the more likely culprit. I mean that you can’t rely for correctness on time(X) < time(Y) when X happened before Y. It’s damn hard to keep two commodity server clocks within ±1 ms of each other even within a single LAN, and across production you’re more likely to see ±10 ms, or worse if your sysadmins don’t realize you intend to bet the farm on no clock skew.
  - jpgvm 3y ago
    It's not designed for this use case. It's for cases where events in the same epoch may as well of happened concurrently. ULID on the other hand does address this case by providing monotonicity within an epoch for a given producer. So would still need to treat each producer as a separate partition of the key space but you could order X > Y as long as both were produced by same producer (which effectively acts like a sequencer in this case). EDIT: nvm, the UUIDv7 spec -allows- for arbitrary allocation of the remaining 62 bits which can be used as a counter: https://www.ietf.org/archive/id/draft-peabody-dispatch-new-uuid-format-01.html#name-uuidv7-layout-and-bit-order https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u... All points for ULID can also apply to UUIDv7 depending on generation algorithm.
__MatrixMan__ 3y ago
When I'm using integer surrogate keys to manipulate subsets of a table, they usually correspond to some kind of out-of-band predicate. Like this is the data that appeared today, or this is everything after the bug happened, etc. Maybe there are applications where the monotonicity matters, but in my experience reasoning by surrogate key is rather coarse grained and you manually scrutinize the boundaries, so unless your clocks are quite wrong, your worries are probably better placed elsewhere.
- erik_seaberg 3y ago
  I’ve seen too many people write a query like where ts between txn_start and txn_end order by ts and not even realize that what they’re seeing is incomplete and misleading. Clock skew is very common, and we shouldn’t sweep that under the rug to promote time ordering, because people want to believe this works the way they think.
  - Foobar8568 3y ago
    Clock skews in a single node database? Actual question.
    - erik_seaberg 3y ago
      Usually Hive or Dremel, with rows ingested from frontend instance logs. I get that it would actually work on a smaller system with a single server assigning times (or a quorum, if leader election ensures a monotonic clock).
      - Foobar8568 3y ago
        Thank you, I was just wondering if it was something I missed out on simpler systems and not distributed ones.
        erik_seaberg 3y ago
        Nah, places I’ve worked are just choosing commodity hardware and geographically distributed systems over (very expensive) centralized ones.
LAC-Tech 3y ago
I feel like it's well beyond the scope of UUIDs to get into "are your clocks really monotonic?". They give you 48 bits for a timestamp, what that timestamp signifies (transactional time, valid time...) and how that's generated is up to you. Out of curiosity, are you into hybrid logical clocks?
- erik_seaberg 3y ago
  I only raise this when I see promises that IDs are ordered and can be sorted, not merely grouped by approximate time for storage locality. Yeah, though I’m more likely to go with a region ID and monotonic version number to compare-and-set and verify gapless data, where versions from different regions aren’t comparable. Actually I think earlier UUID RFCs talk about a “clock sequence” to distinguish timestamps from separate monotonic sources, but this paper doesn’t bring that up (or mention multiple clocks at all).
  - LAC-Tech 3y ago
    The reason I ask is because I'm always looking for material around this kind of thing. I read the Hybrid Logical Clocks paper from the university of Buffalo, but then found it if one of your clocks is inaccurate all your timestamps get dragged forward forever. So any thing you can link, let me know.
ianbutler 3y ago
This was my first reaction as well. The keys use a unix timestamp, which are clearly not going to be synchronized by default so for event ordering purposes across a distributed system this is dodgy. For providing better query locality it probably doesn't matter significantly though which seems to be the main benefit here while preserving the other benefits UUIDs provide.
Dylan16807 3y ago
Well yes, but were they even implying that? Even if it was infinitely strict, clocks being perfect, two server processes can touch the same data at the same time. In other words: Sorting by millisecond-or-so is just as good as sorting by picosecond in most situations. The reason you have to deal with conflicts gracefully isn't particularly because timestamps can be imperfect.
oittaa 3y ago
https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis-11#name-distributed-uuid-generation https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc...
jhealy 3y ago
I'm not the author but I work at the same company. None of our systems require perfect ordering of IDs generated across our distributed system. Most of the system was built with random UUIDv4 identifiers so no code assumes the ID ordering is significant. However, in much of our system recent data is frequently accessed while old data is rarely accessed. In that world, just having the IDs *approximately* clustered in creation order has been a huge performance boost for many queries, and we've seen significant reduction in postgres Write Ahead Log rates, because writes to UID indexes happen in a smaller number of pages.
- XCSme 3y ago
  Just curious, if there is no ordering of the data (no sequential ID), how is it even "ordered" on the file system? Is it random? Or, even without a sequential ID can you know which data was written earlier and which later?
- sgarland 3y ago
  > In that world, just having the IDs approximately clustered in creation order has been a huge performance boost for many queries, and we've seen significant reduction in postgres Write Ahead Log rates, because writes to UID indexes happen in a smaller number of pages. Thank you. I’m so tired of seeing the same groupthink on UUIDv4 trotted out - “it only matters if you have a clustered index, Postgres is immune!” The hell it is.

QuadrupleA 3y ago

But the timestamp is less than half the bits. The rest are random. So timestamp conflicts don't matter.

erik_seaberg 3y ago
By “conflict” I don’t mean a UUID collision, I agree with the logic that 2^128 is so much entropy that memory corruption is the more likely culprit. I mean that you can’t rely for correctness on time(X) < time(Y) when X happened before Y. It’s damn hard to keep two commodity server clocks within ±1 ms of each other even within a single LAN, and across production you’re more likely to see ±10 ms, or worse if your sysadmins don’t realize you intend to bet the farm on no clock skew.
- jpgvm 3y ago
  It's not designed for this use case. It's for cases where events in the same epoch may as well of happened concurrently. ULID on the other hand does address this case by providing monotonicity within an epoch for a given producer. So would still need to treat each producer as a separate partition of the key space but you could order X > Y as long as both were produced by same producer (which effectively acts like a sequencer in this case). EDIT: nvm, the UUIDv7 spec -allows- for arbitrary allocation of the remaining 62 bits which can be used as a counter: https://www.ietf.org/archive/id/draft-peabody-dispatch-new-uuid-format-01.html#name-uuidv7-layout-and-bit-order https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u... All points for ULID can also apply to UUIDv7 depending on generation algorithm.

__MatrixMan__ 3y ago

When I'm using integer surrogate keys to manipulate subsets of a table, they usually correspond to some kind of out-of-band predicate. Like this is the data that appeared today, or this is everything after the bug happened, etc. Maybe there are applications where the monotonicity matters, but in my experience reasoning by surrogate key is rather coarse grained and you manually scrutinize the boundaries, so unless your clocks are quite wrong, your worries are probably better placed elsewhere.

erik_seaberg 3y ago
I’ve seen too many people write a query like where ts between txn_start and txn_end order by ts and not even realize that what they’re seeing is incomplete and misleading. Clock skew is very common, and we shouldn’t sweep that under the rug to promote time ordering, because people want to believe this works the way they think.
- Foobar8568 3y ago
  Clock skews in a single node database? Actual question.
  - erik_seaberg 3y ago
    Usually Hive or Dremel, with rows ingested from frontend instance logs. I get that it would actually work on a smaller system with a single server assigning times (or a quorum, if leader election ensures a monotonic clock).
    - Foobar8568 3y ago
      Thank you, I was just wondering if it was something I missed out on simpler systems and not distributed ones.
      - erik_seaberg 3y ago
        Nah, places I’ve worked are just choosing commodity hardware and geographically distributed systems over (very expensive) centralized ones.

LAC-Tech 3y ago

I feel like it's well beyond the scope of UUIDs to get into "are your clocks really monotonic?". They give you 48 bits for a timestamp, what that timestamp signifies (transactional time, valid time...) and how that's generated is up to you. Out of curiosity, are you into hybrid logical clocks?

erik_seaberg 3y ago
I only raise this when I see promises that IDs are ordered and can be sorted, not merely grouped by approximate time for storage locality. Yeah, though I’m more likely to go with a region ID and monotonic version number to compare-and-set and verify gapless data, where versions from different regions aren’t comparable. Actually I think earlier UUID RFCs talk about a “clock sequence” to distinguish timestamps from separate monotonic sources, but this paper doesn’t bring that up (or mention multiple clocks at all).
- LAC-Tech 3y ago
  The reason I ask is because I'm always looking for material around this kind of thing. I read the Hybrid Logical Clocks paper from the university of Buffalo, but then found it if one of your clocks is inaccurate all your timestamps get dragged forward forever. So any thing you can link, let me know.

ianbutler 3y ago

This was my first reaction as well. The keys use a unix timestamp, which are clearly not going to be synchronized by default so for event ordering purposes across a distributed system this is dodgy. For providing better query locality it probably doesn't matter significantly though which seems to be the main benefit here while preserving the other benefits UUIDs provide.

Dylan16807 3y ago

Well yes, but were they even implying that? Even if it was infinitely strict, clocks being perfect, two server processes can touch the same data at the same time. In other words: Sorting by millisecond-or-so is just as good as sorting by picosecond in most situations. The reason you have to deal with conflicts gracefully isn't particularly because timestamps can be imperfect.

oittaa 3y ago

https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis-11#name-distributed-uuid-generation https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc...

jhealy 3y ago

I'm not the author but I work at the same company. None of our systems require perfect ordering of IDs generated across our distributed system. Most of the system was built with random UUIDv4 identifiers so no code assumes the ID ordering is significant. However, in much of our system recent data is frequently accessed while old data is rarely accessed. In that world, just having the IDs *approximately* clustered in creation order has been a huge performance boost for many queries, and we've seen significant reduction in postgres Write Ahead Log rates, because writes to UID indexes happen in a smaller number of pages.

XCSme 3y ago
Just curious, if there is no ordering of the data (no sequential ID), how is it even "ordered" on the file system? Is it random? Or, even without a sequential ID can you know which data was written earlier and which later?
sgarland 3y ago
> In that world, just having the IDs approximately clustered in creation order has been a huge performance boost for many queries, and we've seen significant reduction in postgres Write Ahead Log rates, because writes to UID indexes happen in a smaller number of pages. Thank you. I’m so tired of seeing the same groupthink on UUIDv4 trotted out - “it only matters if you have a clustered index, Postgres is immune!” The hell it is.