5 ms·

"Unique IDs" _can_ be super really easy to work with if they're not so baffling complicated. A random string generated using quality randomness can be adjusted

by zbuf 4y ago

"Unique IDs" _can_ be super really easy to work with if they're not so baffling complicated. A random string generated using quality randomness can be adjusted to length to suit the quantity of data (negligible probability of a collision) which in most cases is very short. It's easy to increase the length as you get more data. They are visually very different for each item of data. They're evenly spread which means they hash/index well. You can tune a subset of characters if you want to decrease ambiguity eg. when exchanged by voice (no zero vs. letter O, upper/lower case etc.) And a final bonus, when working with user input only a a short prefix is needed to uniquely identify an item (in contrast, it seems like UUIDs deliberately share a common prefix) I'm very happy to concede I must be missing something here, and would be interested to know. But the above approach has served me well in a range of uses. I can see how UUIDs work, and perhaps "looks like a UUID" is a useful feature. But reading the URL above and a bit of Wikipedia doesn't give me much to go on as to _why_ any of this is happening, and why the hyphens aim to retain meaning to what is ostensibly a 'unique' number.

jasonwatkinspdx 4y ago
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?
jxcole 4y ago
We used almost this exact scheme for app id indices and the curious problem we had to design against was inadvertent profanity. At some point we decided to just never use vowels to avoid ever having a complaint about 12f*ck if in the URL
- manigandham 4y ago
  Use integer IDs and a library like Hashids for friendly alphanumeric representations: https://hashids.org/ https://hashids.org/ This particular implementation is available in dozens of languages.
- jasonwatkinspdx 4y ago
  Another approach is to use something like EFF's dice words lists. One of the smaller lists in particular is interesting as it's 6^4 words, filtered for profanity, and where all words have both a unique 3 letter prefix and an edit distance of 3. That makes them robust for the use case of someone reading out the phrase to someone typing or such. Never using vowells is a smart idea I wish I'd used in the past. Previously when I've needed something like this I've used other dictionary lists vs EFF's, and those were not curated sufficiently to avoid some really unfortunate combinations.
  - dolmen 4y ago
    https://www.eff.org/dice https://www.eff.org/dice
manigandham 4y ago
> "They're evenly spread which means they hash/index well." What do you mean by this? Why would you hash it further? Hash distribution is primarily down to the hashing algorithm, not the input data. Also indexes are better with somewhat ordered and smaller data. A 64-bit int sequential counter is much faster and half the size, and compatible everywhere without the annoyances of a UUID.

by zbuf 4y ago

jasonwatkinspdx 4y ago

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?

jxcole 4y ago

We used almost this exact scheme for app id indices and the curious problem we had to design against was inadvertent profanity. At some point we decided to just never use vowels to avoid ever having a complaint about 12f*ck if in the URL

manigandham 4y ago
Use integer IDs and a library like Hashids for friendly alphanumeric representations: https://hashids.org/ https://hashids.org/ This particular implementation is available in dozens of languages.
jasonwatkinspdx 4y ago
Another approach is to use something like EFF's dice words lists. One of the smaller lists in particular is interesting as it's 6^4 words, filtered for profanity, and where all words have both a unique 3 letter prefix and an edit distance of 3. That makes them robust for the use case of someone reading out the phrase to someone typing or such. Never using vowells is a smart idea I wish I'd used in the past. Previously when I've needed something like this I've used other dictionary lists vs EFF's, and those were not curated sufficiently to avoid some really unfortunate combinations.
- dolmen 4y ago
  https://www.eff.org/dice https://www.eff.org/dice

manigandham 4y ago

> "They're evenly spread which means they hash/index well." What do you mean by this? Why would you hash it further? Hash distribution is primarily down to the hashing algorithm, not the input data. Also indexes are better with somewhat ordered and smaller data. A 64-bit int sequential counter is much faster and half the size, and compatible everywhere without the annoyances of a UUID.