15 ms·

A Brief History of the UUID

304 points by mrbbk 9y ago

skrebbel 9y ago
I really like the ideas behind ksuid (near the end of the article). However, two quotes: > Those concerned with UUID collision in a properly-configured system would find their time better spent pondering far more probable events like solar flares, thermonuclear war, and alien invasion on their systems. And then further down: > A “custom” epoch is used that ensures >100 years of useful life. Wait, so the last 128 bits of a KSUID won't get me in trouble before the sun explodes, but the first 32 bits (the timestamp) will cause trouble well before my grandkids die? I really wonder why they didn't reserve some more bits for the timestamp, if necessary at the cost of some less randomness. Could've made this stuff last for millenia at no extra collision risk, in practice.
- OzzyB 9y ago
  That's because now matter how many times we're told to simply trust uuids we will always want to add a timestamp just in case :) Maybe we should just admit that no amount of poetic hyperbole like "until an alien invasion" will quell our innate fear of having uuid that will collide.
  - reitanqild 9y ago
    I have heard people laugh at the risk of UUID collisions and thought we were safe but heard two years ago that a consulting company I worked with had seen real issues with UUID collisions on a production system.
    - treebeard901 9y ago
      I doubt many people would argue with the math behind modern uuid generation functions. Those of us that have been around for a while know the problem can come from the implementation and the storage for the UUID. For example: Bugs in code that may generate a unique ID once and then use it multiple places. Imaged OS installations that may cause a UUID to be duplicated Spoofing another ID for malicious reasons Accidental database update statement People tend to give UUIDs magical properties but it needs to be treated similar to an unique integer.
    - sroussey 9y ago
      If you are using uuid generation that uses MAC address and time stamp, then you can have problems with multiple processes generating uuid for the same system. There are other uuid generation algorithms though.
- fenwick67 9y ago
  The 100 years thing is a peeve of mine too. Especially if they want to see this widely adopted. That is how things like IPv4 address exhaustion and Y2K problem happen. It's 2017, add another byte to your timestamps.
- stock_toaster 9y ago
  Yeah. Not sure why they didn't just go straight for 64bit timestamps (maybe 10^-8 second granularity ~= 5.8k years) and 64bits of random data. I also wonder if base58 would have been a bit nicer. base62 is of course slightly more compact, but base58 is nice that it reduces visual character ambiguity.
  - tytso 9y ago
    The original UUID's (from Apollo, as used in OSF DCE, e2fsprogs, Microsoft, etc.) used a 64-bit timestamp, with 100ns granularity. It uses as the start of its Epoch the beginning of the Gregorian Calendar (00:00:00.00, 15 October 1582), so it's good up to 3400 A.D. before it hits the 2038 problem. :-) Note that UUID's, like IPv6 addresses, are sufficiently long that if users are needing to interact with them directly, You're Doing Something Wrong. So the whole base-62 versus using hyphens versus base58 discussion misses the point, in my view. Computers will generally be exchanging them in 128-bit binary format, and they should only really be dumped out for debugging reasons.
    - stock_toaster 9y ago
      > Note that UUID's, like IPv6 addresses, are sufficiently > long that if users are needing to interact with the > directly, You're Doing Something Wrong One would think so, but you would be surprised how many times someone has typed out to me (or copy/pasted) a UUID for debugging purposes, or how often I have had to eyeball UUIDs in production logs.
      - kijin 9y ago
        We eyeball, compare and copy/paste git commit IDs all the time, and they're longer than UUIDs. I don't see any problem with it as long as there's good tooling to help us interact with these IDs (e.g. git allows us to use the first few characters of a commit ID if there's no collision).
    - rbranson 9y ago
      [Author here: Hey there Theodore -- first of all thank you so much for that other comment with first-hand knowledge about Apollo => UUID. This is the kind of priceless nugget that makes HN such an interesting place.] From a systems perspective I can definitely see why one could reach the conclusion that if users are interacting with them directly, they're doing something wrong. What we've seen is that IDs are routinely copied between different systems for debugging purposes. An example at least for Segment it is common to have IDs pasted into support tickets, and the search engine that indexes these will tokenize on the "-" in a UUID. The difference between finding the solution in minutes vs hours could be that two systems can be correlated by searching using the UUID. Leaving these out is a minor tweak that pays dividends over time. For anything human-exposed (and in JSON or URLs) we use the 27-byte base62 encoding. In the database we store KSUIDs in their 20-byte binary (base256?) encoding.
- grawlinson 9y ago
  Yeah, which is why I'm toying with using ulid identifiers, which won't face timestamp issues until around 10900 AD. Source here: https://github.com/alizain/ulid/ https://github.com/alizain/ulid/
  - Sevein 9y ago
    Related: https://github.com/oklog/ulid https://github.com/oklog/ulid
    - eriknstr 9y ago
      The repo in the comment parent to yours has a list that includes the one you mentioned and several others in various languages :) https://github.com/alizain/ulid#implementations-in-other-languages https://github.com/alizain/ulid#implementations-in-other-lan...
- graphememes 9y ago
  I'm banking on ULID and surprised that they didn't adopt it, it's a much more approachable solution and battle tested.
- philip1209 9y ago
  Are UUIDs secure for creating a unique user session identifier?
  - __s 9y ago
    No, UUIDs aren't meant to be cryptographically unique. Session identifiers should be generated by your friendly neighbourhood crypto rng man
    - MichaelGG 9y ago
      If you're not specifically requesting a time based ID, any proper uuid lib should just return 16 bytes of randomness from the system rng.
      - johncolanduoni 9y ago
        Not quite, most generate v4 uuids which have a few fixed bits.
      - nucleardog 9y ago
        Getting pedantic, but a proper uuid lib should be returning 122 bits of randomness, and six bits of fixed information that specify the uuid version and generation method ("random").
        MichaelGG 9y ago
        For what purpose? Where's the real world reason and interop? Just because an RFC says to set some bits? Is there any code you're likely to hit in your app that actually cares?
        vog 9y ago
        I guess the purpose is to be able to put different UUID generation schemes into separate kind-of "namespaces". That way, a UUIDv4 (random) will never collide with a UUIDv1 (timestamp+mac+...), which again will never collide with UUIDv5 (SHA-1). So if one of the UUID generation schemes is flawed, these are easily filtered out, and moreover, will never interfere with any other UUID version/scheme.
Animats 9y ago
In the early days of network interface, unique IDs were a problem. It was once suggested that each network interface have a $1 bill attached, with the serial number of the bill being the adapter ID. This was a real problem in the early days of low-cost Ethernet controllers. Some manufacturers didn't buy their own address space [1], but reused that of some major vendor. (Usually 3COM) This resulted in occasional real-world duplicates. [1] https://regauth.standards.ieee.org/standards-ra-web/pub/view.html#registries https://regauth.standards.ieee.org/standards-ra-web/pub/view...
- X-Istence 9y ago
  Somewhere I have two network cards with the same MAC address burned into them. That was a lot of fun to figure out when I was younger and things started going haywire!
  - tonyarkles 9y ago
    Just like the sibling post, I had the same thing happen on cheap NE2K nics. Imagine my surprise when pinging one machine and getting two replies back! Edit: it was on a hub too, so nothing kept the two machines from seeing the packet.
- ecopoesis 9y ago
  In the late nineties when I was in college working at the helpdesk we had a problem during freshmen orientation where all of NE2000 clones in the desktops from HP or Packard Bell (definitely had Packard in the name) had the same MAC set. It was a lot of fun reinstalling everyone's drivers via sneakernet.
- Navarr 9y ago
  > It was once suggested that each network interface have a $1 bill attached I'm assuming this was a joke, but was it actually serious? Because things would've gotten hilarious at the first replacement banknote [1] [1]: https://en.wikipedia.org/wiki/Replacement_banknote https://en.wikipedia.org/wiki/Replacement_banknote
wolfgang42 9y ago
Vaguely related story: I inherited a system which generates SSCCs to identify each box being shipped from a warehouse. These are supposed to be globally unique, and are generated from a company's GS1 number (the same used for UPCs) plus another number which the company is supposed to make sure is unique. This particular system generated them on the client-side, based on the current timestamp in microseconds, with a random pause to prevent two computers from generating identical runs if they both printed labels at the same time. In a fairly small warehouse, this generated collisions about every six months or so. I instead changed the program to use an (already existing!) auto-increment column on the shared database, thus precluding any possibility of collision and making the program a lot faster since it was no longer delaying for a quarter-second per label (on shipments of 200+ boxes).
mnarayan01 9y ago
Having 32 bits of 1-second resolution time and 128 bits of random payload makes the idea that these are "semi-sortable" a bit odd. Consider: 1. Let's be super-lenient and say that we'll consider an average size bucket of up to 64k (2^16) equivalent entries to be "semi-sortable". 2. If you generate anymore than 2^48 (2^32 * 2^16) IDs over the full 100ish year lifetime of the ID, then your giving up on even that super-lenient definition of "semi-sortable". 3. If you're only ever going to generate 2^48 IDs, then 2^128 bits of random payload (in addition to the 32 bits of timestamp!) seems like absurd overkill. Given the amount of thought that obviously went into this, I'm guessing that there's probably a good reason that they decided to go with 32 bit timestamps (I can certainly think of many, SHA1 length assumptions being a likely component), but if it's in the article, I missed it.
tytso 9y ago
I can actually fill in some of the details about the history of UUID's. Paul Leach was an architect who worked at Apollo, OSF, and later Microsoft. I met Paul in the mid-90's when he was an architect at OSF, and I was the tech load for Kerberos v5 development at MIT. OSF DCE was going to use Kerberos for authentication, and was going to use Apollo RFC as its RPC layer. It was from talking to Paul that I learned about UUID's, and I added libuuid into e2fsprogs 1.05, released September 7, 1996. UUID's were used in Linux in the ext2 superblock, and later on, GNOME picked it up and used it extensively, which meant among other things that if you wanted to run GNOME on FreeBSD or NetBSD or Solaris, you had to compile e2fsprogs to get libuuid. :-) Later on Paul went on to Microsoft, and I'm fairly certain that it was due to Paul that Microsoft adopted the OSF DCE RPC layer for its internal use, and UUID's started being used extensively inside Microsoft. UUID's also got used in Intel's EFI specification for the GPT partition table, although somewhere along the way they got renamed "Globally Unique ID's" --- it's the same spec, though. While Paul was at Microsoft, the specs for UUID's finally got standardized by the IETF as RFC 4122, so you no longer needed to get find dated copies of the OSF DCE specification (or download e2fsprogs since I had an early version of the UUID Internet Draft in the sources long before it finally squirted out the other end of the RFC publication pipeline). As far as uuidd is concerned, the reason why it exists is because a certain very large Enterprise Resource Planning system was using libuuid to generate uuid's for its objects, and it needed to create them very, very quickly so they can initalize the customer's ERP database in finite time. They were also using the time-based UUID's, with the UUID stored in the database with the bytes cleverly rearranged so the time bits would be stored in the LSB, and the Ethernet MAC address would be in the MSB, so that a database using a B-tree (plus prefix key compression) for its indexing would be able to very efficiently index the UUID's. This is similar to k-ordering trick that Flake was using, but this very large enterprise planning company was doing in 2007, five years before team at Boundary came up with Flake, and they were doing it using standard UUID's, but simply storing the Time-based UUID bytes in a different order. (I believe they were also simply storing the ID in binary form, instead of base-62 encoding, since if you're going to have jillions of objects in your ERP database, you want them to be as efficient as possible.) Anyway, a certain Linux distribution company contacted me on behalf of this very large Enterprise Resource Planning company, and we came up with a scheme where the uuidd daemon could issue blocks of time-based UUID's to clients, so we could amortize the UUID generation over blocks of 50 or 100 UUID's at a time. (This ERP was generating a huge number of UUID's.) I did it as a freebie, because I was tickled pick that libuuid was such a critical part of a large ERP system, and it wasn't that hard to implement the uuidd extension to libuuid.
mappu 9y ago
There's also "ULID" in this neo-UUID space: https://github.com/alizain/ulid https://github.com/alizain/ulid 48-bit timestamp plus 80 bits randomness, base32 encoding (no hyphens), and lexicographic sort order.
- stock_toaster 9y ago
  That does seem pretty nice. Thanks for the link.
foreigner 9y ago
At first I read this as "A Brief History of the IUD" - that's not the same thing at all :-)
smaili 9y ago
It's a little buried, but here's the primary tldr of their KSUID library: > Thus KSUID was born. KSUID is an abbreviation for K-Sortable Unique IDentifier. It combines the simplicity and security of UUID Version 4 with the lexicographic k-ordering properties of Flake. KSUID makes some trade-offs to achieve these goals, but we believe these to be reasonable for both our use cases and many others out there.
MichaelGG 9y ago
Why would you ever want to use UUID format, which only has 122 bits, versus just making a random 128 bit number? In which realistic scenario would simply reading 16 bytes from urandom not be fine and actually cause issues that removing 6 of those bits to identify the UUID type help? Also, 32 bit timestamp + 128 random? I guess, but that sounds sort of overkill-ish - if you're going to go to 20 bytes (and thus not fit in a DB's UUID type, require more than 2 registers, etc.), why not make it 24 or 32 bytes and have a proper timestamp? Or if 32-bit timestamp is really acceptable, are you sure that 96-bits of randomness are not?
- joneholland 9y ago
  And then two machines have the same seed and bam collision.
  - MichaelGG 9y ago
    If two machines have the same csrng seed and can't fix that, then they have the same time, too, so that doesn't help at all.
- GuB-42 9y ago
  The point of the timestamp is to make UUIDs somewhat sortable. It is an interesting property for debugging or optimizing. But yeah 20 bytes is an odd compromise.
- dblohm7 9y ago
  AFAICT the only reason is that you need it for compatibility. If your variant and version fields aren't valid, you don't have a UUID anymore -- you have something else.
  - MichaelGG 9y ago
    Compatibility with what though? What's an example of a real world system that takes UUIDs and uses the standard to do stuff with the fields? Does any popular software treat them as anything beyond a 128bit number? Genuinely curious what people are giving up 6 bits for.
gnu8 9y ago
Is 996238e1-28d1-4b53-b81b-beae25f8edde working for anyone?
- cpeterso 9y ago
  works for me. https://google.com/search?q=996238e1-28d1-4b53-b81b-beae25f8edde https://google.com/search?q=996238e1-28d1-4b53-b81b-beae25f8...
danielbankhead 9y ago
Created something similar called "bronze". It tackles the problem of creating unique identifiers at a slightly different angle, while allowing high collision resistance: https://github.com/AltusAero/bronze https://github.com/AltusAero/bronze
cat199 9y ago
Related tangent: Anyone have any Domain/OS stories or resources they want to share? This system always seemed like an interesting one, but details are fairly scarce..
gumby 9y ago
The phone number was hardly the "first unique identifier in a network" and switchboards worked just fine before phone numbers; phone numbers were first added in the 1890s because of the Stronger switch. The first UUIDs in networks were probably titles (nobility or job titles in a byzantine empire like China, Russia or, less, the Ottoman Empire). "Chief Assistant to the Assistant Chief of Shipbuilding" is a unique node identifier (doesn't identify a person, but then again phone numbers are reused too).
odbol_ 9y ago
> It borrows core ideas from the ubiquitous UUID standard, adding time-based ordering. Isn't time-based ordering bad, since it might allow hackers to predict UUID generation and use it to compromise security systems based on UUID?
Valodim 9y ago
> However, on a mobile device, almost anything goes: mobile devices cannot be trusted. While most of these are just as good as what’s available in the scenario above, it’s routine that the PRNG source on these devices isn’t very random at all. Given that there’s no way to certify the quality of these, it’s a big gamble to bet on mobile PRNGs. ID generation on low-trust mobile devices is an interesting and active area of academic research[1]. This is true for highly specialized systems like sensor nodes maybe. For what is generally understood as a "mobile device", i.e. mobile phones or tablets, it is bollocks.
tuupola 9y ago
Since am big fan of everything Base62 I started to work on a PHP implementation of KSUID. https://github.com/tuupola/ksuid https://github.com/tuupola/ksuid
rphlx 9y ago
/dev/urandom is a major liability on any machine with low uptime booted for the first time from a widely-used image (i.e. a VPS), and on embedded systems which have few sources of entropy & do not (or cannot) save/restore it across boots. As a result there can be a much higher than pure-random chance of a collision in the "random" portion of a UUID.

304 points by mrbbk 9y ago

I really like the ideas behind ksuid (near the end of the article). However, two quotes: > Those concerned with UUID collision in a properly-configured system would find their time better spent pondering far more probable events like solar flares, thermonuclear war, and alien invasion on their systems. And then further down: > A “custom” epoch is used that ensures >100 years of useful life. Wait, so the last 128 bits of a KSUID won't get me in trouble before the sun explodes, but the first 32 bits (the timestamp) will cause trouble well before my grandkids die? I really wonder why they didn't reserve some more bits for the timestamp, if necessary at the cost of some less randomness. Could've made this stuff last for millenia at no extra collision risk, in practice.

OzzyB 9y ago
That's because now matter how many times we're told to simply trust uuids we will always want to add a timestamp just in case :) Maybe we should just admit that no amount of poetic hyperbole like "until an alien invasion" will quell our innate fear of having uuid that will collide.
- reitanqild 9y ago
  I have heard people laugh at the risk of UUID collisions and thought we were safe but heard two years ago that a consulting company I worked with had seen real issues with UUID collisions on a production system.
  - treebeard901 9y ago
    I doubt many people would argue with the math behind modern uuid generation functions. Those of us that have been around for a while know the problem can come from the implementation and the storage for the UUID. For example: Bugs in code that may generate a unique ID once and then use it multiple places. Imaged OS installations that may cause a UUID to be duplicated Spoofing another ID for malicious reasons Accidental database update statement People tend to give UUIDs magical properties but it needs to be treated similar to an unique integer.
  - sroussey 9y ago
    If you are using uuid generation that uses MAC address and time stamp, then you can have problems with multiple processes generating uuid for the same system. There are other uuid generation algorithms though.
fenwick67 9y ago
The 100 years thing is a peeve of mine too. Especially if they want to see this widely adopted. That is how things like IPv4 address exhaustion and Y2K problem happen. It's 2017, add another byte to your timestamps.
stock_toaster 9y ago
Yeah. Not sure why they didn't just go straight for 64bit timestamps (maybe 10^-8 second granularity ~= 5.8k years) and 64bits of random data. I also wonder if base58 would have been a bit nicer. base62 is of course slightly more compact, but base58 is nice that it reduces visual character ambiguity.
- tytso 9y ago
  The original UUID's (from Apollo, as used in OSF DCE, e2fsprogs, Microsoft, etc.) used a 64-bit timestamp, with 100ns granularity. It uses as the start of its Epoch the beginning of the Gregorian Calendar (00:00:00.00, 15 October 1582), so it's good up to 3400 A.D. before it hits the 2038 problem. :-) Note that UUID's, like IPv6 addresses, are sufficiently long that if users are needing to interact with them directly, You're Doing Something Wrong. So the whole base-62 versus using hyphens versus base58 discussion misses the point, in my view. Computers will generally be exchanging them in 128-bit binary format, and they should only really be dumped out for debugging reasons.
  - stock_toaster 9y ago
    > Note that UUID's, like IPv6 addresses, are sufficiently > long that if users are needing to interact with the > directly, You're Doing Something Wrong One would think so, but you would be surprised how many times someone has typed out to me (or copy/pasted) a UUID for debugging purposes, or how often I have had to eyeball UUIDs in production logs.
    - kijin 9y ago
      We eyeball, compare and copy/paste git commit IDs all the time, and they're longer than UUIDs. I don't see any problem with it as long as there's good tooling to help us interact with these IDs (e.g. git allows us to use the first few characters of a commit ID if there's no collision).
  - rbranson 9y ago
    [Author here: Hey there Theodore -- first of all thank you so much for that other comment with first-hand knowledge about Apollo => UUID. This is the kind of priceless nugget that makes HN such an interesting place.] From a systems perspective I can definitely see why one could reach the conclusion that if users are interacting with them directly, they're doing something wrong. What we've seen is that IDs are routinely copied between different systems for debugging purposes. An example at least for Segment it is common to have IDs pasted into support tickets, and the search engine that indexes these will tokenize on the "-" in a UUID. The difference between finding the solution in minutes vs hours could be that two systems can be correlated by searching using the UUID. Leaving these out is a minor tweak that pays dividends over time. For anything human-exposed (and in JSON or URLs) we use the 27-byte base62 encoding. In the database we store KSUIDs in their 20-byte binary (base256?) encoding.
grawlinson 9y ago
Yeah, which is why I'm toying with using ulid identifiers, which won't face timestamp issues until around 10900 AD. Source here: https://github.com/alizain/ulid/ https://github.com/alizain/ulid/
- Sevein 9y ago
  Related: https://github.com/oklog/ulid https://github.com/oklog/ulid
  - eriknstr 9y ago
    The repo in the comment parent to yours has a list that includes the one you mentioned and several others in various languages :) https://github.com/alizain/ulid#implementations-in-other-languages https://github.com/alizain/ulid#implementations-in-other-lan...
graphememes 9y ago
I'm banking on ULID and surprised that they didn't adopt it, it's a much more approachable solution and battle tested.
philip1209 9y ago
Are UUIDs secure for creating a unique user session identifier?
- __s 9y ago
  No, UUIDs aren't meant to be cryptographically unique. Session identifiers should be generated by your friendly neighbourhood crypto rng man
  - MichaelGG 9y ago
    If you're not specifically requesting a time based ID, any proper uuid lib should just return 16 bytes of randomness from the system rng.
    - johncolanduoni 9y ago
      Not quite, most generate v4 uuids which have a few fixed bits.
    - nucleardog 9y ago
      Getting pedantic, but a proper uuid lib should be returning 122 bits of randomness, and six bits of fixed information that specify the uuid version and generation method ("random").
      - MichaelGG 9y ago
        For what purpose? Where's the real world reason and interop? Just because an RFC says to set some bits? Is there any code you're likely to hit in your app that actually cares?
        vog 9y ago
        I guess the purpose is to be able to put different UUID generation schemes into separate kind-of "namespaces". That way, a UUIDv4 (random) will never collide with a UUIDv1 (timestamp+mac+...), which again will never collide with UUIDv5 (SHA-1). So if one of the UUID generation schemes is flawed, these are easily filtered out, and moreover, will never interfere with any other UUID version/scheme.

Animats 9y ago

In the early days of network interface, unique IDs were a problem. It was once suggested that each network interface have a $1 bill attached, with the serial number of the bill being the adapter ID. This was a real problem in the early days of low-cost Ethernet controllers. Some manufacturers didn't buy their own address space [1], but reused that of some major vendor. (Usually 3COM) This resulted in occasional real-world duplicates. [1] https://regauth.standards.ieee.org/standards-ra-web/pub/view.html#registries https://regauth.standards.ieee.org/standards-ra-web/pub/view...

X-Istence 9y ago
Somewhere I have two network cards with the same MAC address burned into them. That was a lot of fun to figure out when I was younger and things started going haywire!
- tonyarkles 9y ago
  Just like the sibling post, I had the same thing happen on cheap NE2K nics. Imagine my surprise when pinging one machine and getting two replies back! Edit: it was on a hub too, so nothing kept the two machines from seeing the packet.
ecopoesis 9y ago
In the late nineties when I was in college working at the helpdesk we had a problem during freshmen orientation where all of NE2000 clones in the desktops from HP or Packard Bell (definitely had Packard in the name) had the same MAC set. It was a lot of fun reinstalling everyone's drivers via sneakernet.
Navarr 9y ago
> It was once suggested that each network interface have a $1 bill attached I'm assuming this was a joke, but was it actually serious? Because things would've gotten hilarious at the first replacement banknote [1] [1]: https://en.wikipedia.org/wiki/Replacement_banknote https://en.wikipedia.org/wiki/Replacement_banknote

wolfgang42 9y ago

Vaguely related story: I inherited a system which generates SSCCs to identify each box being shipped from a warehouse. These are supposed to be globally unique, and are generated from a company's GS1 number (the same used for UPCs) plus another number which the company is supposed to make sure is unique. This particular system generated them on the client-side, based on the current timestamp in microseconds, with a random pause to prevent two computers from generating identical runs if they both printed labels at the same time. In a fairly small warehouse, this generated collisions about every six months or so. I instead changed the program to use an (already existing!) auto-increment column on the shared database, thus precluding any possibility of collision and making the program a lot faster since it was no longer delaying for a quarter-second per label (on shipments of 200+ boxes).

mnarayan01 9y ago

Having 32 bits of 1-second resolution time and 128 bits of random payload makes the idea that these are "semi-sortable" a bit odd. Consider: 1. Let's be super-lenient and say that we'll consider an average size bucket of up to 64k (2^16) equivalent entries to be "semi-sortable". 2. If you generate anymore than 2^48 (2^32 * 2^16) IDs over the full 100ish year lifetime of the ID, then your giving up on even that super-lenient definition of "semi-sortable". 3. If you're only ever going to generate 2^48 IDs, then 2^128 bits of random payload (in addition to the 32 bits of timestamp!) seems like absurd overkill. Given the amount of thought that obviously went into this, I'm guessing that there's probably a good reason that they decided to go with 32 bit timestamps (I can certainly think of many, SHA1 length assumptions being a likely component), but if it's in the article, I missed it.

tytso 9y ago

I can actually fill in some of the details about the history of UUID's. Paul Leach was an architect who worked at Apollo, OSF, and later Microsoft. I met Paul in the mid-90's when he was an architect at OSF, and I was the tech load for Kerberos v5 development at MIT. OSF DCE was going to use Kerberos for authentication, and was going to use Apollo RFC as its RPC layer. It was from talking to Paul that I learned about UUID's, and I added libuuid into e2fsprogs 1.05, released September 7, 1996. UUID's were used in Linux in the ext2 superblock, and later on, GNOME picked it up and used it extensively, which meant among other things that if you wanted to run GNOME on FreeBSD or NetBSD or Solaris, you had to compile e2fsprogs to get libuuid. :-) Later on Paul went on to Microsoft, and I'm fairly certain that it was due to Paul that Microsoft adopted the OSF DCE RPC layer for its internal use, and UUID's started being used extensively inside Microsoft. UUID's also got used in Intel's EFI specification for the GPT partition table, although somewhere along the way they got renamed "Globally Unique ID's" --- it's the same spec, though. While Paul was at Microsoft, the specs for UUID's finally got standardized by the IETF as RFC 4122, so you no longer needed to get find dated copies of the OSF DCE specification (or download e2fsprogs since I had an early version of the UUID Internet Draft in the sources long before it finally squirted out the other end of the RFC publication pipeline). As far as uuidd is concerned, the reason why it exists is because a certain very large Enterprise Resource Planning system was using libuuid to generate uuid's for its objects, and it needed to create them very, very quickly so they can initalize the customer's ERP database in finite time. They were also using the time-based UUID's, with the UUID stored in the database with the bytes cleverly rearranged so the time bits would be stored in the LSB, and the Ethernet MAC address would be in the MSB, so that a database using a B-tree (plus prefix key compression) for its indexing would be able to very efficiently index the UUID's. This is similar to k-ordering trick that Flake was using, but this very large enterprise planning company was doing in 2007, five years before team at Boundary came up with Flake, and they were doing it using standard UUID's, but simply storing the Time-based UUID bytes in a different order. (I believe they were also simply storing the ID in binary form, instead of base-62 encoding, since if you're going to have jillions of objects in your ERP database, you want them to be as efficient as possible.) Anyway, a certain Linux distribution company contacted me on behalf of this very large Enterprise Resource Planning company, and we came up with a scheme where the uuidd daemon could issue blocks of time-based UUID's to clients, so we could amortize the UUID generation over blocks of 50 or 100 UUID's at a time. (This ERP was generating a huge number of UUID's.) I did it as a freebie, because I was tickled pick that libuuid was such a critical part of a large ERP system, and it wasn't that hard to implement the uuidd extension to libuuid.

mappu 9y ago

There's also "ULID" in this neo-UUID space: https://github.com/alizain/ulid https://github.com/alizain/ulid 48-bit timestamp plus 80 bits randomness, base32 encoding (no hyphens), and lexicographic sort order.

stock_toaster 9y ago
That does seem pretty nice. Thanks for the link.

foreigner 9y ago

At first I read this as "A Brief History of the IUD" - that's not the same thing at all :-)

smaili 9y ago

It's a little buried, but here's the primary tldr of their KSUID library: > Thus KSUID was born. KSUID is an abbreviation for K-Sortable Unique IDentifier. It combines the simplicity and security of UUID Version 4 with the lexicographic k-ordering properties of Flake. KSUID makes some trade-offs to achieve these goals, but we believe these to be reasonable for both our use cases and many others out there.

MichaelGG 9y ago

Why would you ever want to use UUID format, which only has 122 bits, versus just making a random 128 bit number? In which realistic scenario would simply reading 16 bytes from urandom not be fine and actually cause issues that removing 6 of those bits to identify the UUID type help? Also, 32 bit timestamp + 128 random? I guess, but that sounds sort of overkill-ish - if you're going to go to 20 bytes (and thus not fit in a DB's UUID type, require more than 2 registers, etc.), why not make it 24 or 32 bytes and have a proper timestamp? Or if 32-bit timestamp is really acceptable, are you sure that 96-bits of randomness are not?

joneholland 9y ago
And then two machines have the same seed and bam collision.
- MichaelGG 9y ago
  If two machines have the same csrng seed and can't fix that, then they have the same time, too, so that doesn't help at all.
GuB-42 9y ago
The point of the timestamp is to make UUIDs somewhat sortable. It is an interesting property for debugging or optimizing. But yeah 20 bytes is an odd compromise.
dblohm7 9y ago
AFAICT the only reason is that you need it for compatibility. If your variant and version fields aren't valid, you don't have a UUID anymore -- you have something else.
- MichaelGG 9y ago
  Compatibility with what though? What's an example of a real world system that takes UUIDs and uses the standard to do stuff with the fields? Does any popular software treat them as anything beyond a 128bit number? Genuinely curious what people are giving up 6 bits for.

gnu8 9y ago

Is 996238e1-28d1-4b53-b81b-beae25f8edde working for anyone?

cpeterso 9y ago
works for me. https://google.com/search?q=996238e1-28d1-4b53-b81b-beae25f8edde https://google.com/search?q=996238e1-28d1-4b53-b81b-beae25f8...

danielbankhead 9y ago

Created something similar called "bronze". It tackles the problem of creating unique identifiers at a slightly different angle, while allowing high collision resistance: https://github.com/AltusAero/bronze https://github.com/AltusAero/bronze

cat199 9y ago

Related tangent: Anyone have any Domain/OS stories or resources they want to share? This system always seemed like an interesting one, but details are fairly scarce..

gumby 9y ago

The phone number was hardly the "first unique identifier in a network" and switchboards worked just fine before phone numbers; phone numbers were first added in the 1890s because of the Stronger switch. The first UUIDs in networks were probably titles (nobility or job titles in a byzantine empire like China, Russia or, less, the Ottoman Empire). "Chief Assistant to the Assistant Chief of Shipbuilding" is a unique node identifier (doesn't identify a person, but then again phone numbers are reused too).

odbol_ 9y ago

> It borrows core ideas from the ubiquitous UUID standard, adding time-based ordering. Isn't time-based ordering bad, since it might allow hackers to predict UUID generation and use it to compromise security systems based on UUID?

Valodim 9y ago

> However, on a mobile device, almost anything goes: mobile devices cannot be trusted. While most of these are just as good as what’s available in the scenario above, it’s routine that the PRNG source on these devices isn’t very random at all. Given that there’s no way to certify the quality of these, it’s a big gamble to bet on mobile PRNGs. ID generation on low-trust mobile devices is an interesting and active area of academic research[1]. This is true for highly specialized systems like sensor nodes maybe. For what is generally understood as a "mobile device", i.e. mobile phones or tablets, it is bollocks.

tuupola 9y ago

Since am big fan of everything Base62 I started to work on a PHP implementation of KSUID. https://github.com/tuupola/ksuid https://github.com/tuupola/ksuid

rphlx 9y ago

/dev/urandom is a major liability on any machine with low uptime booted for the first time from a widely-used image (i.e. a VPS), and on embedded systems which have few sources of entropy & do not (or cannot) save/restore it across boots. As a result there can be a much higher than pure-random chance of a collision in the "random" portion of a UUID.