4 ms·

Thanks for the insight! Mind expanding on what alternatives are being used in high reliability systems instead of UUIDv4?

lazide 5mo ago
Sequences, generally.
- tremon 5mo ago
  That depends on your definition of high-availability. If high availability includes distributed writers, (global) sequences are not the best solution because generating unique sequence values requires synchronisation between all writers. In those cases, you might need to explicitly partition the ID space so that individual writers are guaranteed not to get in each others' hair.
  - lazide 5mo ago
    That is merely a sequence generation strategy.
filcuk 5mo ago
The latest UUID (7?) Uses half random gen, half timestamp. This not only makes it sortable by creation, but would also make a collision like this impossible.
- ffsm8 5mo ago
  Considering the context I think it's worth pointing out that it's technically not impossible - it's just even less likely. Everything in crypto is always a probability - never a certainty
  - nitsky 5mo ago
    True, but it makes the specific collision the post observed completely impossible.
    - stanmancan 5mo ago
      I left a more detailed comment on the parent, but it's definitely not impossible!
      - ryanmonroe 5mo ago
        The scenario in this post is that the first uuid was created one year before the duplicate uuid. That isn’t possible with v7
        ffsm8 5mo ago
        You're heavily leaning on "collision like this" to relate to the exact time stamps for your statement to be true. It's equality possible to interpret the "like this" to the collision itself, without a focus on the 1 year distance between the creation dates. So I guess both views are valid.
        calfuris 5mo ago
        The inclusion of a timestamp in v7 makes collisions impossible unless the generating systems think that the time is the same down to the millisecond, which makes the temporal distance quite relevant.
        stanmancan 5mo ago
        Plenty of systems end up generating multiple UUID's in a single millisecond. The issue with UUIDv7 is that you also have significantly less entropy since you only have a 62 bits (sometimes less, depending on implementation) of "random" data. So while the time aspect of format lowers the chances of collisions, generating two UUIDv7's in the same millisecond (depending on implementation) have a significantly higher chance of collision than two UUIDv4's. It's still incredibly unlikely, but it's also incredibly unlikely you generate two matching UUIDv4's, but it does happen. TLDR; It's possible to generate matching UUIDv7's, don't assume otherwise.
- stanmancan 5mo ago
  It's still possible in most implementations of UUIDv7. UUIDv7 assigns the first 48 bits for the timestamp in milliseconds. You can generate a lot of UUID's in a millisecond though! Then you have another 12 bits that you can use as you wish; "rand_a". The spec has a few methods they suggest on how to use these bits including 12 bits of random data, using it for sub-millisecond timestamps, or creating a monotonic counter, but each have their downsides: - Purely random data means you can still run into collisions and anything within the same millisecond is unordered - Sub millisecond you can run into collisions; there's nothing stopping you from generating two UUID's with the same 62 bits of rand_b data in the same sub-millisecond timestamp. - Monotonic counters can overflow before the next tick, then what? Rollover? Once you roll over it's no longer monotonic and you can generate the same random data within the same monotonic cycle. Also; it's only monotonic to the system that's generating the UUID. If you have a distributed system and they each have their own monotonic cycles then you'll be generating UUID's with the same timestamp + monotonic counter, and again, are relying on not generating the same random data. You can steal some of the 62 bits in rand_b if you want as well; you can use rand_a for sub-millisecond accuracy, and then use a few bits of rand_b for a monotonic counter. There's still a chance of collision here, but it's exceedingly low at the expense of less truly random data at the end. If you want truly collision free, you'd also need to assign a couple of bits to identify the subsystem generating the UUID so that the monotonic counter is unique to that subsystem. You lose the ordering part of the monotonic counter this way though, but I guess you could argue that in nearly 100% of cases the accuracy of sub-millisecond order in a distributed system is a lie anyways.
  - rootlocus 5mo ago
    We have a dedicated snowflake id generator service that returns batch ids. It's also distributed, each service adds its own instance number to the id. When it overflows it just blocks for the next ms. For our traffic, it's never a bottleneck.
    - ralferoo 5mo ago
      Something I use on my own distributed system (where I wanted 64-bit IDs), is use 32 bits for the time in seconds (with an epoch from 2020, so good until 2088), 8 bits for the device ID and 24 bits for a serial number (resets to 0 every time the seconds increments). That's generally enough IDs per second for most of my edge nodes, but the central worker nodes need more, so I give them a different split and use 4 bits for the device ID and 28 bits for serial number instead. If a node overflows its serial number that second, I kind of cheat and increment the seconds field early. Every time this happens, I persist the seconds field to the database, and when the app restarts, it starts its seconds count at the last persisted seconds plus one. If the current time in seconds is greater than the last used seconds, I also update it and reset the serial number. Works remarkably well for smoothing out very occasional spikes in ID generation while still approximately remaining globally sortable. I also "waste" a bit of the 32-bit time field by considering it to be signed, even though it's not really because I don't expect this system to last long enough to reach times where the MSB gets set. But if I ever change my system, I'll set that bit and everything will stay ordered. I'll probably reset the epoch at that point too.
- deleted 5mo ago
  [deleted]
- majorchord 5mo ago
  The spec doesn't require the use of actually random numbers though.
- erlkonig 5mo ago
  Almost impossible, it depends on how fast they're being generated and the precision of the timestamp. The real problem is two years later when someone finds and removes that usleep(10000); /* sleep 10 µs */ that was the hard speed brake needed for the UUID generator, and suddenly duplicate IDs start showing up a few times per day or something similar.
jandrewrogers 5mo ago
In high-reliability systems a criterion for identifier design is easy detection of defective identifiers. This includes buggy systems and adversarial manipulation. The problem with UUIDs that rely on entropy sources is that it is computationally expensive to detect if the statistical distribution of identifiers is diverging from what you would expect from a random oracle. I've written systems that can detect entropy source anomalies but you'll want to turn it off in production. It is pretty cheap to sanity check most non-probabilistic identifier schemes. UUIDs that use broken hash algorithms (e.g. UUIDv3/5) or leak state (e.g. UUIDv7) are exposed to adversarial exploitation. The identifier scheme is dependent on the use case. Does the uniqueness constraint apply to the instance of the object or the contents of the object? Is the generation of identifiers federated across untrusted nodes? How large is the potential universe of identifiers? The basic scheme I've seen is a 128-bit structured value that has no probabilistic component. These identifiers can be encrypted with AES-128 when exported to the public, guaranteeing uniqueness while leaking no internal state. The benefit of this scheme is that it is usually drop-in compatible with standard UUID even though it is technically not a UUID and the internal structure can carry useful metadata about the identifier if you can decrypt it. Federated generation across untrusted nodes requires a more complex scheme, particularly if the universe of identifiers is extremely large. These intrinsically have a collision risk regardless of how the identifiers are generated. All of the standardized UUID really weren't designed with the requirements of scalable high-reliability systems in mind. They were optimized for convenience and expedience which is a perfectly reasonable objective. Most people don't need an identifier system engineered for extreme reliability, even though there is relatively little cost to having one.
- eaf7e281 5mo ago
  > leak state (e.g. UUIDv7) But according to PostgreSQL, UUIDv7 provides better performance in the database, so is this essentially a trade off between security and speed?
  - jubilanti 5mo ago
    Yes, because UUIDv7 gives up some random bits in order to include the timestamp, which is done in a way that makes UUIDv7s quick to sort by timestamp.
matt-p 5mo ago
UUIDv7 is arguably better, because it is entropy plus time.
- otherme123 5mo ago
  It is what I usually use for its sorting, but some people don't want to leak time info.
- majorchord 5mo ago
  Entropy is not a requirement in the UUID spec.

lazide 5mo ago

Sequences, generally.

tremon 5mo ago
That depends on your definition of high-availability. If high availability includes distributed writers, (global) sequences are not the best solution because generating unique sequence values requires synchronisation between all writers. In those cases, you might need to explicitly partition the ID space so that individual writers are guaranteed not to get in each others' hair.
- lazide 5mo ago
  That is merely a sequence generation strategy.

filcuk 5mo ago

The latest UUID (7?) Uses half random gen, half timestamp. This not only makes it sortable by creation, but would also make a collision like this impossible.

ffsm8 5mo ago
Considering the context I think it's worth pointing out that it's technically not impossible - it's just even less likely. Everything in crypto is always a probability - never a certainty
- nitsky 5mo ago
  True, but it makes the specific collision the post observed completely impossible.
  - stanmancan 5mo ago
    I left a more detailed comment on the parent, but it's definitely not impossible!
    - ryanmonroe 5mo ago
      The scenario in this post is that the first uuid was created one year before the duplicate uuid. That isn’t possible with v7
      - ffsm8 5mo ago
        You're heavily leaning on "collision like this" to relate to the exact time stamps for your statement to be true. It's equality possible to interpret the "like this" to the collision itself, without a focus on the 1 year distance between the creation dates. So I guess both views are valid.
        calfuris 5mo ago
        The inclusion of a timestamp in v7 makes collisions impossible unless the generating systems think that the time is the same down to the millisecond, which makes the temporal distance quite relevant.
        stanmancan 5mo ago
        Plenty of systems end up generating multiple UUID's in a single millisecond. The issue with UUIDv7 is that you also have significantly less entropy since you only have a 62 bits (sometimes less, depending on implementation) of "random" data. So while the time aspect of format lowers the chances of collisions, generating two UUIDv7's in the same millisecond (depending on implementation) have a significantly higher chance of collision than two UUIDv4's. It's still incredibly unlikely, but it's also incredibly unlikely you generate two matching UUIDv4's, but it does happen. TLDR; It's possible to generate matching UUIDv7's, don't assume otherwise.
stanmancan 5mo ago
It's still possible in most implementations of UUIDv7. UUIDv7 assigns the first 48 bits for the timestamp in milliseconds. You can generate a lot of UUID's in a millisecond though! Then you have another 12 bits that you can use as you wish; "rand_a". The spec has a few methods they suggest on how to use these bits including 12 bits of random data, using it for sub-millisecond timestamps, or creating a monotonic counter, but each have their downsides: - Purely random data means you can still run into collisions and anything within the same millisecond is unordered - Sub millisecond you can run into collisions; there's nothing stopping you from generating two UUID's with the same 62 bits of rand_b data in the same sub-millisecond timestamp. - Monotonic counters can overflow before the next tick, then what? Rollover? Once you roll over it's no longer monotonic and you can generate the same random data within the same monotonic cycle. Also; it's only monotonic to the system that's generating the UUID. If you have a distributed system and they each have their own monotonic cycles then you'll be generating UUID's with the same timestamp + monotonic counter, and again, are relying on not generating the same random data. You can steal some of the 62 bits in rand_b if you want as well; you can use rand_a for sub-millisecond accuracy, and then use a few bits of rand_b for a monotonic counter. There's still a chance of collision here, but it's exceedingly low at the expense of less truly random data at the end. If you want truly collision free, you'd also need to assign a couple of bits to identify the subsystem generating the UUID so that the monotonic counter is unique to that subsystem. You lose the ordering part of the monotonic counter this way though, but I guess you could argue that in nearly 100% of cases the accuracy of sub-millisecond order in a distributed system is a lie anyways.
- rootlocus 5mo ago
  We have a dedicated snowflake id generator service that returns batch ids. It's also distributed, each service adds its own instance number to the id. When it overflows it just blocks for the next ms. For our traffic, it's never a bottleneck.
  - ralferoo 5mo ago
    Something I use on my own distributed system (where I wanted 64-bit IDs), is use 32 bits for the time in seconds (with an epoch from 2020, so good until 2088), 8 bits for the device ID and 24 bits for a serial number (resets to 0 every time the seconds increments). That's generally enough IDs per second for most of my edge nodes, but the central worker nodes need more, so I give them a different split and use 4 bits for the device ID and 28 bits for serial number instead. If a node overflows its serial number that second, I kind of cheat and increment the seconds field early. Every time this happens, I persist the seconds field to the database, and when the app restarts, it starts its seconds count at the last persisted seconds plus one. If the current time in seconds is greater than the last used seconds, I also update it and reset the serial number. Works remarkably well for smoothing out very occasional spikes in ID generation while still approximately remaining globally sortable. I also "waste" a bit of the 32-bit time field by considering it to be signed, even though it's not really because I don't expect this system to last long enough to reach times where the MSB gets set. But if I ever change my system, I'll set that bit and everything will stay ordered. I'll probably reset the epoch at that point too.
deleted 5mo ago
[deleted]
majorchord 5mo ago
The spec doesn't require the use of actually random numbers though.
erlkonig 5mo ago
Almost impossible, it depends on how fast they're being generated and the precision of the timestamp. The real problem is two years later when someone finds and removes that usleep(10000); /* sleep 10 µs */ that was the hard speed brake needed for the UUID generator, and suddenly duplicate IDs start showing up a few times per day or something similar.

jandrewrogers 5mo ago

In high-reliability systems a criterion for identifier design is easy detection of defective identifiers. This includes buggy systems and adversarial manipulation. The problem with UUIDs that rely on entropy sources is that it is computationally expensive to detect if the statistical distribution of identifiers is diverging from what you would expect from a random oracle. I've written systems that can detect entropy source anomalies but you'll want to turn it off in production. It is pretty cheap to sanity check most non-probabilistic identifier schemes. UUIDs that use broken hash algorithms (e.g. UUIDv3/5) or leak state (e.g. UUIDv7) are exposed to adversarial exploitation. The identifier scheme is dependent on the use case. Does the uniqueness constraint apply to the instance of the object or the contents of the object? Is the generation of identifiers federated across untrusted nodes? How large is the potential universe of identifiers? The basic scheme I've seen is a 128-bit structured value that has no probabilistic component. These identifiers can be encrypted with AES-128 when exported to the public, guaranteeing uniqueness while leaking no internal state. The benefit of this scheme is that it is usually drop-in compatible with standard UUID even though it is technically not a UUID and the internal structure can carry useful metadata about the identifier if you can decrypt it. Federated generation across untrusted nodes requires a more complex scheme, particularly if the universe of identifiers is extremely large. These intrinsically have a collision risk regardless of how the identifiers are generated. All of the standardized UUID really weren't designed with the requirements of scalable high-reliability systems in mind. They were optimized for convenience and expedience which is a perfectly reasonable objective. Most people don't need an identifier system engineered for extreme reliability, even though there is relatively little cost to having one.

eaf7e281 5mo ago
> leak state (e.g. UUIDv7) But according to PostgreSQL, UUIDv7 provides better performance in the database, so is this essentially a trade off between security and speed?
- jubilanti 5mo ago
  Yes, because UUIDv7 gives up some random bits in order to include the timestamp, which is done in a way that makes UUIDv7s quick to sort by timestamp.

matt-p 5mo ago

UUIDv7 is arguably better, because it is entropy plus time.

otherme123 5mo ago
It is what I usually use for its sorting, but some people don't want to leak time info.
majorchord 5mo ago
Entropy is not a requirement in the UUID spec.