4 ms·

Using purely random ids in your database destroys locality. They mention this in the introduction: > Non-time-ordered UUID versions such as UUIDv4 have poor da

Using purely random ids in your database destroys locality. They mention this in the introduction: > Non-time-ordered UUID versions such as UUIDv4 have poor database index locality. Meaning new values created in succession are not close to each other in the index and thus require inserts to be performed at random locations. The negative performance effects of which on common structures used for this (B-tree and its variants) can be dramatic. The V7 ids work similarly to what you like, as they're just a unix timestamp and 74 bits of pseudorandom data (they present several different schemes you could use to generate this randomness, but the basic birthday bound says we'd need to be above 100 billion id's generated in a single millisecond to worry about collisons. Obviously most systems are nowhere near that territory. So using these id's gives you the practical advantages of random uinique ids, but with the performance of autoincrement ids.

zbuf 4y ago
Thanks for drawing my attention to that, it's the useful answer I was looking for; my use cases haven't been bound by write performance in this manner. However, I'd still be considering carefully before making use of these UUID schemes.
- jasonwatkinspdx 4y ago
  If you want something like this, and need a "I just want it to work, require no central coordination, and to have vanishingly small probability of collision" then just use the same concepts but wider than the 128 bit footprint limit of this scheme. This limit makes sense for the RFC in the post, as there backwards compatibility is an explicit goal. But if you used say a 64 bit nanosecond counter (to preserve best case precision on a single machine) along with 128+ bits of random data and you'll need to worry more about gamma ray bursts than collisions.
jandrewrogers 4y ago
100 billion UUIDs per millisecond is the 50% collision probability threshold. Achieving an acceptable collision probability for most applications would limit the UUID generation rate to more like thousands of UUIDs per millisecond. Even if one was not generating millions of UUIDs per second on average, the risk of spiky temporal distributions when generating UUIDs would still need to be considered.
- jasonwatkinspdx 4y ago
  I'm aware of what the bound I quoted is, and am just too lazy to type the refinement into Wolfram for a discussion like this. But just knowing the value off the top of my head for 64 bits is 200k for 1e-9 probability of collision, I'm pretty happy with 74 bits. And although this standard obviously wants to stick within the existing UUID footprint, if you were say doing some IoT software that would run on billions of nodes simultaneously, just add another 32/64/whatever bits of random data and deal with the minor annoyance of longer ids and lack of UUID RFC compatibility. But even then, you can truncate and reformat these these to v4 UUIDs trivially without meaningfully impacting the collision resistance, for unsorted external ids in systems that need the compatability. The actual big risk with this sort of scheme is vm initialization. You need to be sure the CSPRNG you're using is initialized, which can be slightly tricky in cloud environments with configuration/control layer stuff that's racy. Mess this up and two nodes hydrated from the same snapshot may overlap in sequence as they start generating ids, and of course the time component cannot be trusted to save you in this instance.
- 11235813213455 4y ago
  Is it even possible to reach that rate given that generating a random hash takes some time?

zbuf 4y ago

Thanks for drawing my attention to that, it's the useful answer I was looking for; my use cases haven't been bound by write performance in this manner. However, I'd still be considering carefully before making use of these UUID schemes.

jasonwatkinspdx 4y ago
If you want something like this, and need a "I just want it to work, require no central coordination, and to have vanishingly small probability of collision" then just use the same concepts but wider than the 128 bit footprint limit of this scheme. This limit makes sense for the RFC in the post, as there backwards compatibility is an explicit goal. But if you used say a 64 bit nanosecond counter (to preserve best case precision on a single machine) along with 128+ bits of random data and you'll need to worry more about gamma ray bursts than collisions.

jandrewrogers 4y ago

100 billion UUIDs per millisecond is the 50% collision probability threshold. Achieving an acceptable collision probability for most applications would limit the UUID generation rate to more like thousands of UUIDs per millisecond. Even if one was not generating millions of UUIDs per second on average, the risk of spiky temporal distributions when generating UUIDs would still need to be considered.

jasonwatkinspdx 4y ago
I'm aware of what the bound I quoted is, and am just too lazy to type the refinement into Wolfram for a discussion like this. But just knowing the value off the top of my head for 64 bits is 200k for 1e-9 probability of collision, I'm pretty happy with 74 bits. And although this standard obviously wants to stick within the existing UUID footprint, if you were say doing some IoT software that would run on billions of nodes simultaneously, just add another 32/64/whatever bits of random data and deal with the minor annoyance of longer ids and lack of UUID RFC compatibility. But even then, you can truncate and reformat these these to v4 UUIDs trivially without meaningfully impacting the collision resistance, for unsorted external ids in systems that need the compatability. The actual big risk with this sort of scheme is vm initialization. You need to be sure the CSPRNG you're using is initialized, which can be slightly tricky in cloud environments with configuration/control layer stuff that's racy. Mess this up and two nodes hydrated from the same snapshot may overlap in sequence as they start generating ids, and of course the time component cannot be trusted to save you in this instance.
11235813213455 4y ago
Is it even possible to reach that rate given that generating a random hash takes some time?