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.
Once he convinced me of the uniqueness of correctly generated UUIDs I coined the phrase "the likelihood of a UUID collision is the same as an avocado spontaneously turning into a grapefruit."
A fun tid-bit: At one point I was the maintainer of the list of static UUIDs with the Microsoft bit set. It was a flat text file checked into the windows source. I reserved a chunk of them for my own projects because having all those zeros was useful in debugging. E.g. "00000000-0000-0000-c000-000000000046" (the c000 indicates MS reserved).
In '97 I wrote the internet-draft  that Paul & Rich Salz finally turned into RFC 4122 in 2005 .
If another UUID version is used, I'm extremely wary. MAC addresses are explicitly not unique. Worse, there are plenty of bargain mfgs that make cards all with the same MAC. There's a story of a local college that ordered several hundred cards for workstations and discovered every single one had the exact same hardware MAC. Large orgs will spot this easily, but there could be hundreds or thousands of individuals that never tried connecting the same bad cards on the same network segment.
In practice, you can usually depend on it to be truly unique. But there are several failure modes that you absolutely need to be aware of if you plan on using this in production.
The DCE library “surprisingly distributed by Apple” is used by their CIFS server and NetLogon daemon. From memory, it originally came from the OSF DCE RPC source code drop, which I then slightly modernised for use in XAD (the first Active Directory-compatible domain controller replacement, which became Domain Services for Windows at Novell), and then found its way to Apple via Likewise.
How many millions/sec did they need?
If you use random number generator to generate random UUID's, then you will be inserting the objects all over the b-tree and once the tree is too big to fit into memory, performance goes down the toilet.
This was a real problem in the early days of low-cost Ethernet controllers. Some manufacturers didn't buy their own address space , but reused that of some major vendor. (Usually 3COM)
This resulted in occasional real-world duplicates.
That was a lot of fun to figure out when I was younger and things started going haywire!
Edit: it was on a hub too, so nothing kept the two machines from seeing the packet.
I'm assuming this was a joke, but was it actually serious?
Because things would've gotten hilarious at the first replacement banknote 
> 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.
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.
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.
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.
> 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
I wonder how people manage to keep a straight face while calling something "universally unique" that can't even cover a time period corresponding to the recorded history of our own species. Perhaps it never occurred to them that archeologists and paleontologists might also find time-based UUIDs useful?
Space is cheap now. We don't have to fit everything in 128 bits. We could just use good ol' 64 bit time_t, add another 32 bits for nanosecond granularity, throw in a decent amount of random data, and still get identifiers somewhere between the size of a git commit ID (160 bits) and a bitcoin transaction ID (256 bits). Nobody writes these things by hand anyway.
Archeologists of the year 8017 might also thank us if we were kind enough to label each piece of our data in a way that makes sense to them, including precise timestamps. Heck, they might still be using the same format if we did come up with something truly universal!
I've rarely seen dates encoded because they don't provide much useful information. Sites themselves rarely have firm dates and individual excavations get their own (infinite) ID blocks. Each feature and artifact within that excavation is tagged with the block, alongside a bunch of metadata and paperwork. Every artifact carries with it a stack of paperwork documenting where it came from and how it was buried, making shipping the things expensive.
These collections eventually get bundled into larger site or regional packages alongside computational models and research papers, adding yet another hierarchial later.
The whole thing is very bureaucratic and a bit crusty at times, but still very scalable for a system designed before computers were even imagined. As with most things, the friction comes from trying to move things between the physical and digital worlds, not the IDs themselves (which are just guaranteed unique tags).
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.
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.
That is how things like IPv4 address exhaustion and Y2K problem happen. It's 2017, add another byte to your timestamps.
It's easier to just read 16 bytes from /dev/urandom and encode it in hex/base64 yourself for a random token.
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.
48-bit timestamp plus 80 bits randomness, base32 encoding (no hyphens), and lexicographic sort order.
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?
But yeah 20 bytes is an odd compromise.
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.
> 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.
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..
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.
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?
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).