New UUID Formats – IETF Draft

https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format

by anuragsoni • 5 years ago

525 245 5 years ago

datatracker.ietf.org

atonse• 5 years ago

TLDR they present 3 new versions that each have their own trade-offs, but are also taking into account being able to use these as DB primary keys, which is really great.

Another thing I was quite curious about (looks like you can use them in existing DB columns etc):

The UUID length of 16 octets (128 bits) remains unchanged. The textual representation of a UUID consisting of 36 hexadecimal and dash characters in the format 8-4-4-4-12 remains unchanged for human readability. In addition the position of both the Version and Variant bits remain unchanged in the layout.

lytedev4• 5 years ago

Doesn't the textual representation not matter for using them in DB columns? The DB just uses the actual bytes, no?

Macha2• 5 years ago

SQL is a textual format. Your DB driver may expect a UUID to be provided them in the standard string format. If your language lacks a standard UUID type, the drivers may expect you to provide UUIDs as strings even when using parameter binding.

e.g. MySQL accepts only "no dashes" and the standard textual format: https://dev.mysql.com/doc/refman/8.0/en/miscellaneous-functi...

Postgres is a bit more flexible, but still expects hyphens to be after multiples of four characters if present: https://www.postgresql.org/docs/9.1/datatype-uuid.html

gregoriol• 5 years ago

The important part is the number of bits used for storage; the textual version is only for humans

weird-eye-issue2• 5 years ago

Application level code validates UUIDs based on a specific format not to mention what the specific database might expect depending on the data type

dnautics2• 5 years ago

depends on the DB. And it depends on your framework. Last I checked Django from about 5 years ago? still shipped uuids as text fields to the database.

athenot• 5 years ago

For human readability, I've always prefered encoding UUIDs in base 64 and swapping a couple characters. If I'm going to have some ugly identifier in a URL, I might as well make it more concise.

I think youtube does something similar with their video IDs.

cratermoon10• 5 years ago

I prefer ksuid https://github.com/segmentio/ksuid

jrochkind13• 5 years ago

The IETF draft mentions ksuid in the "prior art consulted" section.

Do you mean you prefer ksuid to this new draft? Your comment would be more helpful if you said what about it you prefer.

cratermoon10• 5 years ago

I prefer ksuids because

they have 128 bits of pseudorandom data

Both text and binary representations are lexicographically sortable

They don't have the awkward dash ('-') to mess with url encoding

tfehring• 5 years ago

Other than the additional pseudorandom bits (which also have drawbacks), what's the advantage of ksuid over UUIDv6 as defined in the draft?

cratermoon10• 5 years ago

Both text and binary representations are lexicographically sortable

They don't have the awkward dash ('-') to mess with url encoding

nabla9• 5 years ago

The background section gives reasons derived from looking at existing implementations.

---

Due to the shortcomings of UUIDv1 and UUIDv4 details so far, many widely distributed database applications and large application vendors have sought to solve the problem of creating a better time- based, sortable unique identifier for use as a database key. This has lead to numerous implementations over the past 10+ years solving the same problem in slightly different ways.

- Timestamps MUST be k-sortable. That is, values within or close to the same timestamp are ordered properly by sorting algorithms.

- Timestamps SHOULD be big-endian with the most-significant bits of the time embedded as-is without reordering.

- Timestamps SHOULD utilize millisecond precision and Unix Epoch as timestamp source. Although, there is some variation to this among implementations depending on the application requirements.

- The ID format SHOULD be Lexicographically sortable while in the textual representation.

- IDs MUST ensure proper embedded sequencing to facilitate sorting when multiple UUIDs are created during a given timestamp.

- IDs MUST NOT require unique network identifiers as part of achieving uniqueness.

- Distributed nodes MUST be able to create collision resistant Unique IDs without a consulting a centralized resource.

rootusrootus• 5 years ago

"UUIDv8 SHOULD only be utilized if an implementation cannot utilize UUIDv1, UUIDv6, or UUIDv8." I assume that is a typo.

LukeShu5• 5 years ago

Indeed, I believe that it should read "… or UUIDv7."

    UUIDv1 non-sortable time-based
    UUIDv6 sortable time-based, Gregorian calendar
    UUIDv7 sortable time-based, Unix time
    UUIDv8 sortable time-based, custom time

That is: The custom-time version should only be used if you cannot use one of the standard time versions.

Wevah2• 5 years ago

There’s another typo in the v7 section where it’s erroneously referred to as v8.

jozvolskyef2• 5 years ago

What are the advantages of sortable UUIDs with embedded timestamps over random 128 bits and a created_at column?

munhitsu• 5 years ago

CRDT

weird-eye-issue2• 5 years ago

Not having a created_at column and the index bloat that goes with it?

notamy• 5 years ago

It works better for databases that can only sort on the primary key (iirc Cassandra is one of these)

scrollaway• 5 years ago

One data point instead of two. Which may or may not have advantages depending on your situation.

At any rate it's definitely simpler, and you don't have to forego the created_at column either.

lytedev4• 5 years ago

My understanding is that if the UUID is not sortable, inserting it into an index can be a performance hit. So if you have a write-heavy table with non-sorted primary keys, you will have a lower ceiling (higher overhead).

srcreigh2• 5 years ago

Know about primary vs secondary indexes?

Generally 1 index contains the data, all the other indexes have pointers to that index in their leaf nodes. Usually the PK index contains the data

So loading 1000 consecutive rows in a created_at secondary index takes two steps: 1) created_at index B-Tree traversal (maybe 10 pages from disk, max?) 2) Potentially loading 1000 randomly sorted pages from disk, dereferencing pointers (EXPENSIVE!)

Whereas, if your primary key is sorted by time, loading 1000 rows is 1) slightly larger primary B-Tree traversal 2) no 2, you're done :)

NyxWulf4• 5 years ago

The lack of sorting is what this rfc is fixing.

ignoramous• 5 years ago

What are the advantages of sortable UUIDs

I guess for use-cases like Instagram's: "Generated IDs should be sortable by time (so a list of photo IDs, for example, could be sorted without fetching more information about the photos)... If you use a timestamp as the first component of the ID, the IDs remain time-sortable... [but require] more storage space (96 bits or higher) to make reasonable uniqueness guarantees" [0]

[0] https://archive.is/xiMGZ

zimpenfish• 5 years ago

cf also Twitter's Snowflake[1] which is [timestamp, worker number, sequence number] to give the same "roughly sortable by time" property.

[1] https://blog.twitter.com/engineering/en_us/a/2010/announcing...

BenoitEssiambre• 5 years ago

On top of reasons given by others, if the data likely to be queried together tends to get stored together because of this, things will be much more cache efficient and queries potentially much faster since for db loads, cache efficiency (not just ram but CPU cache), alleviates some of the most important performance bottlenecks.

causasui• 5 years ago

I use KSUIDs a ton in DynamoDB; it saves me from having to create and fill another index to sort items by creation time.

The only case where I don't use them is if I don't want to create time of the item to be known to the user.

bilinguliar• 5 years ago

This allows you to keep recent records in DB cache, for example. Contrary, random keys would constantly invalidate the cache unless all your data fits in memory.

ape4• 5 years ago

Isn't that a possible security issue. MACs used to be predictable but then became random.

jozvolskyef2• 5 years ago

I presume you are referring to UUIDv4/1, which has 122 random bits. It is a common misconception that this is insecure. In reality, the UUIDv4/1 is just a way to encode 122 random bits, which is more than enough for most needs. The property of being practically unguessable comes from the random generator, not from the encoding.

Secondly, whether or not being predictable is a problem depends on the use case. The keys used on this forum are predictable and it is not an issue.

lazide3• 5 years ago

I’m pretty sure you mean ‘stable’ not predictable here re:MACs?

The issue with using Mac addresses is it essentially leaked tracking information on the machine being used to generate the uuid - you could associate every ID it ever generated back to that same machine, correlate it to things like open WiFi AP logs, whatever. Which is pretty scary sometimes.

Many OS’s now randomly generate a new MAC on every disconnect/connect for this reason, to at least give some privacy.

masklinn• 5 years ago

Random primary keys play hell on database indexes.

cratermoon10• 5 years ago

https://en.wikipedia.org/wiki/Partial_sorting

mrighele• 5 years ago

The linked RFC talks about this (it refers to UUIDv4, which is not much different from 128 random bits):

" First, most of the existing 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. As such newly inserted values SHOULD be time-ordered to address this."

LukeShu5• 5 years ago

UUIDv4, which is not much different from 128 random bits

To quantify how different: UUIDv4 has 6 fixed bits and 122 random bits.

bob10295• 5 years ago

Note that this totally-random key behavior is actually highly desirable when using dynamic programming techniques such as with the Splay Tree. It makes it statistically impossible for the tree to fall into a degenerate state.

gumby• 5 years ago

That is addressed in the introduction -- random access inserts (i.e. specularity) can be quite inefficient depending on your backing store.

jandrewrogers4• 5 years ago

There are two issues not mentioned in the other comments with a random 128-bit UUID in real systems, both related to data scale:

- They defeat data compression, which is an integral part of many database engines these days for both performance and scalability reasons.

- For some very large systems, there is a UUID collision tail risk that while small is large enough to be plausible.

neur4lnet• 5 years ago

Its compression a legitimate concern for primary keys?

orf2• 5 years ago

Imagine you’re not using a storage platform that supports that access pattern. Think S3, DynamoDB or even a directory of files. Being able to encode your sort key in your primary key is a pretty nice property.

datavirtue• 5 years ago

Hmmm...Now I'm wondering why I never bothered to prepend a timestamp to a GUID.

halfmatthalfcat• 5 years ago

Using the uuid as a PK do to cursor based pagination for one.

parhamn• 5 years ago

it depends what "created_at" means, if it means "persisted_at" then they're also a bit different because these sorts of UUIDs are generated before being persisted (often long before for offline-and sync systems).

dheera• 5 years ago

Searching records and returning the results time-sorted in O(n) time instead of O(n log n) time.

junon• 5 years ago

FWIW the linked RFC's "Background" section is really easy to understand even for people who aren't well versed in dist-sys concepts. I suggest giving it a read - it's quite well written.

runeks• 5 years ago

Follow-up question:

What are the advantages of sortable UUIDs with embedded timestamps over having an auto-incrementing id column, a created_at column, and using the composite primary key (created_at, id)?

rswail• 5 years ago

Because an auto-incrementing id column has to be coordinated between processes that are writing to the database. That means allocating ids in blocks that are large enough that processes aren't blocked in getting an allocation, but they still need to request a block to maintain writing.

That sequence allocation needs to be ACID as well, so that there is no chance of any allocation being repeated.

riffic• 5 years ago

Also see RFC 4122:

https://datatracker.ietf.org/doc/html/rfc4122

infinityplus1• 5 years ago

Does anyone have any opinion on how Firebase push keys compare to UUIDs? Firebase push keys are said to be unique and are sortable. Here's a link to the push key generator: https://gist.github.com/mikelehen/3596a30bd69384624c11

politician2• 5 years ago

I'm really excited to see k-sortable unique identifiers (flakes) be submitted as an IETF draft. This will help keep the UUID data type relevant.

However, I'd like to see the draft include a mention about the practice of embedding machine and data type identifiers into the format which helps in distributed applications.

cratermoon10• 5 years ago

the practice of embedding machine and data type identifiers into the format is a security risk

emodendroket• 5 years ago

How do you figure? There's no guarantee guids aren't supposed to be predictable, right?

politician2• 5 years ago

It might be, but whether it is depends on your threat model.

If you need to obscure both when in time and where in space, then UUIDv4 is a better option.

pjscott11• 5 years ago

Section 7, "Distributed UUID Generation", mentions that you MAY hold some of the most significant random bits constant per-machine to act as a machine identifier.

jjice• 5 years ago

I'm a bit confused as to what the use case for UUIDs are compare to incrementing integer IDs. I assume there are some big upsides (aside from the primary key issue which seems to have quite a few solutions at this point), but I'm just not aware of them.

tomschlick• 5 years ago

Because they are unique on generation, you dont need to talk to the database before generating one. This is huge for distributed systems, or systems that have offline components (think mobile apps that sync). The ids can be generated client side and passed up to be stored in the database without worry.

tschellenbach• 5 years ago

incrementing ids requires a centralized server of some sort to hand out IDs when you get to a certain scale. you don't have that issue with UUIDs. for small apps just incrementing ids works fine though

this approach also allows you to generate ids client side. which if you're working with a local db on ios/android etc this is very convenient

dangerlibrary• 5 years ago

From the "Introduction" section of the linked document:

"The motivation for using UUIDs as database keys stems primarily from the fact that applications are increasingly distributed in nature. Simplistic "auto increment" schemes with integers in sequence do not work well in a distributed system since the effort required to synchronize such numbers across a network can easily become a burden. The fact that UUIDs can be used to create unique and reasonably short values in distributed systems without requiring synchronization makes them a good candidate for use as a database key in such environments. "

lolinder• 5 years ago

One big one is distributed computing: for example, an app that can create To Do items offline and periodically syncs with a server.

If you have your To Do items identified by an incrementing integer, you have to come up with some other unique identifier to use for To Do items that have yet to be synced with the server's database (since you can't know which ID to use next).

On the other hand, if you use UUIDs, your app can just create a new UUID for the To Do item, which will continue to be its ID for subsequent updates.

marcus_holmes2• 5 years ago

The huge one for me is that if I make a mistake in code or admin and accidentally run "update users set permission = 'root' where id=$1" using an account id instead of a user id, it does nothing. If I'd used integers I'd have given root permission to a random user.

medstrom• 5 years ago

So, it's like creating a special data type for each "counter-style" identifier. For example suppose a StudentsId which is not an integer, it's a StudentsInteger, so it cannot be mixed up with UsersId. Admittedly that seems more clunky than just using uuids.

spyspy• 5 years ago

One non-performance reason is that incrementing IDs inherently leak information about your application and/or your company. If you create an account somewhere and you see that your user ID is 452 you now know how many users the company has. In the company's eyes they'd probably prefer to keep that obscured.

rjsw• 5 years ago

Also known as the German tank problem [1].

[1] https://en.wikipedia.org/wiki/German_tank_problem

thamer• 5 years ago

One of the most important is that you can't iterate over all the UUIDs. How many data leaks have come from people incrementing an ID in a URL?

This is so common, I've experienced this myself as a student with a summer job: the company I was working for used an online service for their payroll, I accessed my pay slip one day and changed ?employee=123 to 124 in the URL out of curiosity and it loaded the data for a different person in a different company. They fixed it incredibly quickly once I told them about it :)

alex_duf• 5 years ago

Incrementing an ID requires complete knowledge in a single place, which at scale becomes a challenge. This would typically be done in the database, but doesn't bode well with distributed systems as multiple servers might thing "5" is following "4" leading to multiple rows identified by the same ID => this is a collision.

So UUIDs are great because multiple servers can generate plethora of them without having to worry about collisions.

This is all explained in the first few pages of the document, although not in simple terms.

Also I haven't spotted anything about UUIDv6 trying to avoid collisions, but I haven't read very far.

bjt• 5 years ago

The last 48 bits should do it.

" node: 48-bit pseudo-random number used as a spatially unique identifier Occupies bits 80 through 127 (octets 10-15)"

remus• 5 years ago

As well as the other use cases mentioned, they're harder to guess than incrementing integer IDs so are a useful defense in depth to help stop people guessing URLs for resources.

tatersolid2• 5 years ago

This benefit can’t be understated: missing or buggy authorization checks are present in almost all real-world web apps and APIs I’ve encountered. A long random component (such as the 80 bits provided by ULIDs) covers up a lot of sins.

A ULID is 48 bits of timestamp plus 80 bits of entropy. These new formats just don’t have enough random-component entropy. 64 bits isn’t enough. Who cares in your millisecond timestamp wraps every 8900 years as they do in a ULID?

https://github.com/ulid/spec

ComputerGuru6• 5 years ago

See ulid for similar prior art. We generate Ulids in code and then store them in uuid columns in Postgres to realize the compact (binary) size benefits.

https://github.com/ulid/spec

roberto• 5 years ago

They list ULID and 15 other implementations in the document.

ComputerGuru6• 5 years ago

Ah, so they do. Thanks.

WorldMaker6• 5 years ago

I put in the work to store ULIDs in SQL Server's interesting UUIDv1-based sort order for uniqueidentifier columns. It seems to be providing the clustered index benefits I was hoping for so far (far less clustered index churn behavior than v4 Random UUIDs).

An interesting digression to bring up with respect to this RFC because it is interesting to note that none of the proposed v6, v7, v8 UUIDs match the SQL Server sort order behavior and would still have a lot of clustered index churn unless new sort behaviors were allowed to be opted in. That might be something that this RFC would help to address by also making sort orders a bit more standard, though it does not directly make recommendations on that front.

For what it is worth, it is the SQL Server sort order that is weird: it sorts the last group of the UUID string form first, which in v1 UUIDs corresponded to the MAC Address. Clustering by machine probably made sense by whoever decided on that sort order, at the time, but even with v1 UUIDs they probably would have got better results sorting by timestamp than by machine.

(The ULID timestamp fits exactly into that "MAC address" group and it's just a matter of swapping the front 6 bytes to the back of the UUID when storing to uniqueidentifier.)

Fun reference on UUID sort orders: https://devblogs.microsoft.com/oldnewthing/20190426-00/?p=10...

ComputerGuru6• 5 years ago

It’s not just a question of whether you want to cluster by MAC address, it’s more of a fundamental disagreement as to the endianness of the UUID groups themselves, which is probably the biggest difference between a GUID and a UUID in the wild. Microsoft has used GUIDs to brand OS intervals for a long, long time - long enough that there’s a chance they came before UUID was a thing, but I haven’t dug into the history of it.

Unfortunately converting between them without any db extensions is a PITA in the absence of native support. I’ve written about it at length here (SQLite in the example, but the fundamentals apply regardless): https://neosmart.net/blog/2018/converting-a-binary-blob-guid...

mgkimsal• 5 years ago

What's a bit interesting to me is having read all the negativity/criticism around ULID, and now seeing these proposals by IETF...

ComputerGuru6• 5 years ago

Most ulid criticism surrounds the ill-advised (and optional!) part of the spec that tries to achieve sub-ms ordering at the cost of requiring a singleton or cross-thread atomics to try and generate random values for the random portion of the blob from a range that would end up providing additional sort order bits. The reference implementation in JS doesn’t even offer this (although that’s likely because JS doesn’t even support multiple execution threads within the same context).

Apart from that little misadventure (last I checked, there was a request for comments on a proposal to drop that from the Ulid spec altogether) there’s really nothing else that’s not same and straightforward in the spec, and little else to complain about.

pjscott11• 5 years ago

A somewhat oversimplified summary of the new UUID formats:

UUID6: a timestamp with a weird epoch and 100 ns precision like in UUID1, but in a big-endian order that sorts naturally by time, plus some random bits instead of a predictable MAC address.

UUID7: like UUID6, but uses normal Unix timestamps and allows more timestamp precision.

UUID8: like UUID7, but relaxes requirements on where the timestamp is coming from. Want to use a custom epoch or NTP timestamps or something? UUID8 allows it for the sake of flexibility and future-proofing, but the downside is that there's no standard way to parse the time from one of these -- the time source could be anything monotonic.

zvrba4• 5 years ago

with a weird epoch and 100 ns precision

Exactly as used by windows to store file times. And the epoch is the start of the modern calendar https://en.wikipedia.org/wiki/Gregorian_calendar

Talking about dates before this epoch makes little sense (any date before the Gregorian epoch will not resemble the same stellar / planet constellation as date after the Gregorian epoch).

pjscott11• 5 years ago

A precision of 100 ns is not bad, just inflexible; I didn't mean to imply otherwise. The epoch is weird, though. Here's a thought experiment: imagine that a hundred programmers are each asked to pick an epoch for a timestamp, and will be paid $1000 for each other programmer who chooses the same epoch, but they can't talk with each other to coordinate. Which would you pick? I would pick the Unix epoch, because I think others would do the same. Anything else is, in a certain important sense, weird.

jefftk• 5 years ago

Talking about dates before this epoch makes little sense (any date before the Gregorian epoch will not resemble the same stellar / planet constellation as date after the Gregorian epoch).

That is not the only sense in which we care about dates. For example, we might want to talk about which of two events came first, and by how much. Historians have lots of uses for dates before the introduction of the Gregorian calendar.

ygra2• 5 years ago

Windows' FILETIME uses a different epoch, though. It counts since 1601 (the then-most-recent 400-year leap-year cycle when Windows NT was designed).

MrManatee• 5 years ago

I wouldn't say it makes "little sense". Just like we can talk about the year 776 BC even though no one at the time called it that, we can extend the Gregorian calendar backwards to dates when it wasn't used anywhere. The Wikipedia article on the proleptic Gregorian calendar lists some use cases. [1]

And in any case, 15 October 1582 isn't some hard cutoff point where we can stop worrying about calendar conversions. Only four countries adopted the Gregorian calendar on that day, and even in Europe there are several countries that only switched in the 20th century. If a piece of software needs to support historical dates that go anywhere near 1582, it needs to be aware of the existence of different calendars.

[1] https://en.wikipedia.org/wiki/Proleptic_Gregorian_calendar

hn_throwaway_992• 5 years ago

To clarify, are those "plus some random bits" parts intended to be randomly generated for each individual UUID that is created, or randomly generated once per machine or startup?

I ask because a common newbie bug is to use a UUID as a secure token, but currently only v4 UUIDs with a cryptographically secure PRNG can be used this way. Separately, even if not used as a token, using UUIDs with randomness for object IDs can help mitigate IDOR vulnerabilities if there are other bugs in code that aren't adequately checking object permissions.

pjscott11• 5 years ago

They're to be generated for each individual UUID. (However, this RFC recommends using the entirely random UUID4 for anything that's meant to be used in a security-related context, presumably with a CSPRNG.)

dspillett• 5 years ago

only v4 UUIDs with a cryptographically secure PRNG can be used this way

Only they should be used that way. Unfortunately other options (other UUID types, v4 with bad RNG) are sometimes used that way. At least other UUID variants are more faf to hack around than a simple increasing integer, particularly if decent request and access validation is in place, though if the wrong type of key is being used perhaps hoping for good validation elsewhere is a bit much.

rndgermandude• 5 years ago

UUIDv4 (or even worse, the other versions) are regularly used for "security", as you said, when they shouldn't. That won't change with these proposed versions.

Any randomness in the UUIDs is meant to minimize the possibility of collisions. If e.g. you only used a timestamp then you might get collisions even on the same machine, and are almost guaranteed collisions sooner than later on a global scale.

The draft mentions randomness in the background section, but not really.

Lastly, privacy and network security issues arise from using a MAC address in the node field of Version 1 UUIDs. Exposed MAC addresses can be used as an attack surface to locate machines and reveal various other information about such machines (minimally manufacturer, potentially other details). Instead "cryptographically secure" pseudo-random number generators (CSPRNGs) or pseudo-random number generators (PRNG) SHOULD be used within an application context to provide uniqueness and unguessability.

And in the Security Considerations section

Instead [of MACs] pseudo-random bits SHOULD selected from a source with sufficient entropy to ensure guaranteed uniqueness among UUID generation.

However, the rest of the document does not mention how to generate the random data, at all. If the draft advanced to RFC or even standard like this, it would be fine to use the "Debian PRNG")[1].

Then again, only the proposed v6 mandates any random data at all (and 48-bits "only"). v7 and v8 have essentially a "may use" for any randomness.

Using only UUIDs for "security" is generally a bad idea in my humble opinion, regardless, even if v4 with a crypto-secure (CS)PRNG. But I suppose, mandating the use crypto-secure (CS)PRNG would still alleviate some of the injuries to people who point the UUID-gun at their feet and pull the trigger.

[1] https://i.imgur.com/WkLh32P.png [2]

[2] https://www.debian.org/security/2008/dsa-1571

paulddraper4• 5 years ago

8 kinds of UUIDs, because we already had 4 too many.

pjscott11• 5 years ago

Which of the 5 existing kinds of UUID do you consider the One True UUID? No matter which you pick, I guarantee that there's something badly wrong with it for at least one common use-case that can be improved by switching to either v4 (IMHO the only one of the existing types worth using) or to one of the new proposed UUID types.

phkahler3• 5 years ago

> but the downside is that there's no standard way to parse the time from one of these

IMHO that should not be a concern. The goal of UUID is to create a Unique Identifier, not to record the time something was created. Maybe we should all have quantum random number generators, but with that I don't think 128 bits is enough for a UUID. Might be enough for specific applications though.

First rule of database design: Your unique IDs should not have a real-world meaning.

mulmen2• 5 years ago

First rule of database design: Your unique IDs should not have a real-world meaning.

Well, this is an opinion. I would definitely push back on making it a rule. Especially the first one.

Natural keys exist, make perfectly good unique identifiers, and have inherent meaning.

When using synthetic keys it is difficult (read: requires making trade-offs) to guarantee they were created in order and/or that they increase monotonically. But if you make those trade-offs (or just align expectations) you can still associate real world meaning to them.

These new UUIDs standardize more of those trade-offs.

koolba• 5 years ago

In theory, theory and practice are the same. In practice they’re not.

Sortable unique IDs have many performance benefits in real world systems.

wilg• 5 years ago

If you don't think that's a concern then UUID8 is for you!

iratewizard• 5 years ago

First rule of database design: Your unique IDs should not have a real-world meaning.

I see a lot of comments conflating a unique ID with a unique column. It's OK for you to have a unique contraint on something like an email column. But you wouldn't use the email column as the primary key.

remram• 5 years ago

If that's how you feel about it, why use UUID at all? You could use any 16 bytes and not format them according to any standard.

ryanisnan• 5 years ago

to record the time something was created.

I don't think that was the downside mentioned, I think it was because of the lack of standardization on how to parse the timestamp.

voidnullnil• 5 years ago

To take this one step further: Adding surprise semantics like capturing time (and the dev not being aware of it) will lead to security vulnerabilities (side channels because the code is essentially timestamping when various parts of the code are hit) as well as privacy issues (PII leaking, clock skew leaking, whatever).

My thesis is that computers are so full of unwanted unneeded things like this that there is no engineer who knows them all as well as having a good understanding software engineering as well as infosec. Most vulnerabilities are due to lack of understanding how the primitives work, as opposed to flaws in reasoning (the former is clearly distinct: the summary provided to save him from spending a month looking at the implementation is inadequate).

I have designed UUIDs myself and they are simply a long random bitstring. The random part is already necessary because we need sufficient randomness for crypto to work in the first place. IETF likes to "engineer" things.

hinkley• 5 years ago

UUID6: a timestamp with a weird epoch and 100 ns precision like in UUID1, but in a big-endian order that sorts naturally by time

So even the IETF hasn’t read Things Every Developer Should Know About Time.

LukeShu5• 5 years ago

As a quick reference for readers:

The UUID specs use the terms "variant" and "version" a little funny; "variant" is essentially the revision (so all modern UUIDs have variant=0b10 to specify RFC 4122 UUIDs), and "version" is a 4-bit number identifying the sub-type within that variant:

    UUIDv1 time-based
    UUIDv2 legacy DCE security thing, not wideley used
    UUIDv3 name-based with md5 hashing
    UUIDv4 randomness-based
    UUIDv5 name-based with sha1 hashing

This draft registers a few new sub-types:

    UUIDv6 sortable time-based, Gregorian calendar
    UUIDv7 sortable time-based, Unix time
    UUIDv8 sortable time-based, custom time

paulddraper4• 5 years ago

tl;dr

Use UUIDv4 and get on with your day.

ygra2• 5 years ago

Well, not if you need database primary keys with sensible index locality. Which is what this draft is about.

gopalv• 5 years ago

The machineID MUST NOT be an IEEE 802 MAC address.
MAC addresses pose inherent security risks and MUST not be used for node generation.

Interesting concern in the distributed generation pathway.

I've used MAC addresses in the past for absolutely unique identifiers, but this is calling out that as a security risk, because the time + arp data might be known to predict a future UUID from a machine?

WorldMaker6• 5 years ago

UUIDv1 IDs with MAC addresses have been used for tracking people down. There are especially a lot of classic examples from older Word documents where v1 UUIDs were often embedded in many places inside the documents. Groups used (and sometimes still use) the MAC addresses in such Word documents to track down specific authors (for FBI investigations on the more [extra-]legal side and for "doxxing" and such on the far less legal side).

Whether you consider this specific example threat a privacy risk versus a security risk here depends on your personal threat model, of course. But general consensus at this point is to label it a security risk.

jackpirate• 5 years ago

That makes sense, but that seems like it's a problem with any machine-unique id, not just the MAC address. Is there some specific reason MAC addresses are a worse choice than (e.g.) CPU serial number?

sudhirj3• 5 years ago

For those interested in time based UUIDs, I've written libraries in Ruby and Go to move quickly between them:

https://github.com/sudhirj/uulid.go https://github.com/sudhirj/shortuuid.rb https://github.com/sudhirj/shortuuid.go

stavros3• 5 years ago

Those look suspiciously similar to the Python one!

sudhirj3• 5 years ago

Probably is quite similar, the converting numbers between bases is a textbook algo, and the UUID format is a standard. Which python one?

RcouF1uZ4gsC• 5 years ago

48-bit pseudo-random number used as a spatially unique identifier Occupies bits 80 through 127 (octets 10-15)

Is 48 bits really enough to be a spatially unique identifier. Roughly 16 million entities would have a 50% chance of collision.

If you have a spatially unique identifier collision, it seems it might be possible for two independent entities to generate the same time stamp and counter codes resulting in an overall UUID collision.

ltbarcly3• 5 years ago

While possible, with a high precision clock it should be quite rare. In any case, UUID's aren't meant to be universally unique to the point you will never see the same one for any reason across every use case in the galaxy, although many versions do allow you to neglect to code to handle collisions for almost every practical use case.

If you need 16 million entries to get a 50% chance of collision, 100ns time resolution means you have 10^7 timestamps per second, so to actually experience a 50% chance of collision requires an instantaneous hash rate of over 10^14 per second, which I don't think you are likely to ever see in practice before these UUID versions are long obsolete.

Croftengea2• 5 years ago

To put it simply, the new standard aims to address UUID usage as primary keys in distributed systems.

But UUIDv7 is described as: Unix timestamp + fractions of second + increasing sequence + random number. Now imagine two processes start simultaneously and start generating UUIDs right away. IMHO chances of the two processes generating exactly the same UUID sequence are pretty high unless the implementation is smart enough to feed something like process id as a seed to random function.

renonce• 5 years ago

Well implemented processes usually seed their random generators from a random device, such as /dev/urandom in Linux. Such devices hand out different values for each request.

kokizzu3• 5 years ago

meanwhile.. i did make a shorter one :3 https://github.com/kokizzu/lexid

darkhorse13• 5 years ago

A bit off-topic, but does anyone know how to build webpages that look like this? Like is there any way to do it other than doing everything manually on a text editor?

Croftengea2• 5 years ago

Maybe just wrap your text into <pre> tags? :)

wrs• 5 years ago

Not sure exactly what you mean by “look like this”, but several tools for generating RFCs in the standard text format are here: https://tools.ietf.org/

LukeShu5• 5 years ago

Most new RFCs are authored in an XML format that gets rendered to the officially-submitted plaintext (well, since 2016 (RFC 7990) if you use v3 of the XML schema, that may be submitted directly as the canonical version, otherwise the rendered plaintext is the canonical version.)

So the authors wrote this XML https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u...

That XML got turned in to this plaintext https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u... by the xml2rfc tool https://xml2rfc.tools.ietf.org/

And then that plaintext got turned in to the linked HTML by the datatracker.ietf.org server software, which can be found in SVN https://svn.ietf.org/svn/tools/ietfdb/

mtwittman• 5 years ago

At the moment anyway, that XML link won't render per an XML parsing error. For anyone who wants a quick look at what these XML docs look like here's one for UUID6 [0].

[0] https://github.com/uuid6/uuid6-ietf-draft/blob/master/draft-...

fhrow4484• 5 years ago

implementations MAY dedicate a portion of the node's most significant random bits to a pseudo-random machineID which helps identify UUIDs created by a given node. This works to add an extra layer of collision avoidance.
This machine ID MUST be placed in the UUID proceeding [sic] the timestamp and sequence counter bits. This position is selected to ensure that the sorting by timestamp and clock sequence is still possible.

This guarantees uniqueness at a global level, as long as each machine doesn't run out of sequence counters within a given timestamp.

But why must that machine ID must preceding the timestamp & sequence counter? Why not have it after? (or does "proceeding" has a meaning I'm not aware of? I read it as a typo for "preceding", but I'd assume it should be succeeding, especially given what the next sentence says)

My intuition is range requests based on timestamp would work better if the machine ID is after, not before... If before, it seems it would violate the key requirement in abstract of "sortable using the monotonic creation time".

(It's already violated since each machine in distributed system doesn't have the same clock so "creation time" is all relative. But for purposes of analytics, such as querying the "last 24h", having the timestamp be at the beginning seems preferable, since range queries can be done easily)

pjscott11• 5 years ago

Since there's no valid way for part of the node to be put in front of the timestamp and sequence counter bits -- that would contradict the format specifications in section 4 -- they probably meant to write "succeeding" or "right after". (There are, alas, still some typos in this draft.)

NyxWulf4• 5 years ago

I found that confusing as well. If the machine id is before the unixts, the primary advantage of using this is lost for me. Scanning an index for a 24 hour period is only fast if you can easily find the start and stop, and they have locality. Since that is the primary problem addressed with this rfc, I hope it is just a poorly worded section, rather than a design flaw.

greggyb• 5 years ago

This machine ID MUST be placed in the UUID proceeding the timestamp and sequence counter bits.

I read this as a strange word choice, but interpret as follows: "This machine ID MUST proceed from the timestamp and sequence counter." X proceeding from Y implies that X comes after Y.

If we examine the context, it is absolutely unambiguous (emphasis mine):

This machine ID MUST be placed in the UUID proceeding [sic] the timestamp and sequence counter bits. This position is selected to ensure that the sorting by timestamp and clock sequence is still possible.

The proceeding sentence makes the intent clear, that a naive sort should preserve time ordering. The only way for this to work is for the timestamp and sequence counter bits to precede the optional machine ID.

Wevah2• 5 years ago

I think there was some proceeding/preceding confusion in GP. I misread it at first, too.

throwaway81523• 5 years ago

Machine ID? Who uses identifiable machines instead of virtual ones any more? They poof in and out of existence almost as often as vacuum polarization. Heh.

bob10295• 5 years ago

v7 sounds compelling for keying entities in our product. We use v4 right now.

What I am trying to determine is if 62 bits of entropy combined with a timestamp gives me better or worse collision resistance as with 122 bits in a purely-random format. Most of our keys only live within the scope of a single computer, but ~5% of them might be generated/shared between other systems.

Being able to order our keys by time would be really nice, and I like that they would compress/index better.

Maybe I could do a hybrid between V4 and V7 keys depending on if the type would be shared with external parties. There are many types that only ever scope to a single box.

I probably couldn't play with the idea of adding a "machine id" because the space of all possible machines is difficult to anticipate/control right now.

I think I just talked myself into sticking with v4.

jffry• 5 years ago

Probability wise, nearly doubling your entropy will significantly reduce the risk of a collision in your generated IDs, but there's lots of other considerations for you to make. But for the raw odds perspective, from https://en.wikipedia.org/wiki/Birthday_attack we can get a rough idea of collision chance. You can plug this into Wolfram Alpha [1][2] to play around with it.

For a one-in-a-million chance of having at least one collision, you'd need to generate 3.04e6 random 62-bit values or 3.26e15 random 122-bit values. For a one-in-a-thousand chance, those numbers would be 9.6e7 or 1.03e17 respectively.

In other words: If you're sustained allocating v7 IDs (with no sub-second portion of the timestamp) at a rate of 3.04 million per second, there's a 1-in-a-million chance each second of having at least one collision. Taking 1 - 0.999999^86400, that gives an 8.3% chance of at least one collision after a day, 45.4% after a week, and 92.5% after a month.

If you instead were allocating v4 IDs at the same rate for a month, you'd have allocated (3.04e6)×86400×30 IDs, and you'd have a probability of 5.84e-12 of at least one collision among all of those IDs.

[1] Collision probability given number of draws: https://www.wolframalpha.com/input/?i=n%3D3.04e6%2C+H%3D2%5E...

[2] Min number of draws to get a given collision probability: https://www.wolframalpha.com/input/?i=p%3D0.000001%2C+H%3D2%...

edit: If you are storing milliseconds in subsec_a and generating IDs at the same rate, you'd have 3040 ids per millisecond, which have a probability 1.00164e-12 of a collision in any given millisecond. Taking 1-(1-1.00164e-12)^(86400*1000) gives you a probability of 0.0087% of a collision in a day, 0.061% in a week, or 0.26% in a month. So as long as your event generation is relatively constant across that second, you will indeed have a much lower collision chance if you are using millisecond subdivisions. If you have even higher precision time or are using a sequence counter, that can be pushed down even further.

NyxWulf4• 5 years ago

v7 allows to you trade time precision for randomness. Adding time precision allows the surface area for conflicts to decrease, so the loss of random bits to higher time precision is worth it if you are generating a lot of ids. Unless it is a security application, I would use v7 for most things.

chociej2• 5 years ago

Trying to wrap my head around how this works when distributed. If v7 is used with a high time precision, it's important that each node in the distributed system have a very tightly synchronized time, right?

If so, with v7, I'd feel the need to find the right balance of time precision, time synchronization, node identification, and randomness. Just some thoughts out loud.

tialaramex4• 5 years ago

After some staring, I can't see why (beyond the obvious, I understand HN rules) this is here.

This is clearly an individual draft. OK. And it has previously expired without action (last year) but a newer draft was submitted this year.

But it doesn't seem to have been adopted by any working group, and although the word "dispatch" appears in the title it was not discussed at IETF 111's DISPATCH or GENDISPATCH or SECDISPATCH last week. If this was in fact dispatched somewhere - perhaps before it expired last time - there's no indication where it went or what its status is now.

It is the nature of these things that if everybody chooses to do exactly this, even if it was only documented in a by-then expired draft, or on the back of an envelope, then that's how it is -- the IETF has no enforcement arm. However if you support this proposal, or even if you think it'd be a good idea with minor tweaks you should find out where (and if) it's being developed and get on board with that.

villasv• 5 years ago

Maybe the community response here would provide guidance on whether this is worth pursuing?

I for one have been waiting for an IETF-standard sortable UUIDs for a while, so I'm happy to upvote this even if it is "blog post wishlist"-stage of standardization.

Waterluvian• 5 years ago

I find it peculiar that the Introduction section on these drafts is always just boilerplate.

gfody• 5 years ago

if you were about to use a uuid as a primary key in a database, wouldn't it always be better to instead use a composite key with explicit columns for sequence, timestamp, node id, etc.? if you really need to accept client side generated values and there's no opportunity to issue them a unique node id before hand, then explicitly taking their mac address and region seems better than stealthily relying on those things being embedded in a uuid - also aren't mac addresses considered PII?

geostyx• 5 years ago

This looks awesome. Can't wait till I can add this to uuid.rocks!

submeta• 5 years ago

OT: Nicely written and formated ascii document. I wonder what tools they used to create the headars / page numbers / refs.

krinchan2• 5 years ago

There are a lot of tools that let you write a source document and compile it into something that fits the RFC style guide.

XML and markdown are the most common source document formats.

https://www.rfc-editor.org/pubprocess/tools/

pawal• 5 years ago

There are a number of different tools for writing internet-drafts. See here: https://tools.ietf.org/tools/

sswaner• 5 years ago

I had the same thought: Interesting topic, but I am very distracted by how much I love the format of the document.

OliverJones• 5 years ago

If the epoch in this proposal were changed to something closer to the present day (2000-01-01 or the UNIX epoch) the format could easily recover some bits from the time fields to put in the PRNG-generated "node" fields. I wonder why they chose the Gregorian epoch?

pjscott11• 5 years ago

The Gregorian epoch was chosen for UUID v6 in order to make it as similar to v1 as possible, for ease of updating existing software. There are two more types of UUID proposed in this draft RFC: v7 which uses the Unix epoch and allows more time precision, and v8 which can use any monotonic timestamp source.

mrgleeco• 5 years ago

OT but related: a reverse-sorted UUID format seems especially useful for IoT and event data where typically we want to read newest to oldest lexicographically (eg. rowscans starting at now). Is there such a standard or OSS that does this?

jhealy• 5 years ago

The author seems to be developing the draft on GitHub and there's a few edits since the v01 version linked here

https://github.com/uuid6/uuid6-ietf-draft

thayne• 5 years ago

For UUIDv7 it isn't very clear on how the subsecond part is encoded. From the description of decoding it sounds like it would be multiplying the fraction of a second by 2^n. but that isn't very explicit. And if you want to avoid floating point arithmetic you'll need to include a 10^p in there where p is how many digits of precision you have in base 10 (such as 3 for milliseconds)

no_wizard• 5 years ago

I haven’t seen any uuid format in any project I’ve worked on get explicitly created except uuid V4.

What’s the actual advantage of the other uuids? I know what they are on paper but has anyone used other ones in practice?

Lazare2• 5 years ago

I like using standards, but the advantages of KSUIDs over existing UUIDs has led me to adopt them by default in new (and where possible, existing) projects.

I was sort of hoping this would yield something obviously superior to KSUIDs, since nominally this is an attempt to create an IETF standard to solve the same problem KSUIDs solve, but...

...I'm not seeing it. I just want enough random bits to ensure I don't need to worry about a collission, combined with enough of a timestamp I can roughly k-sort them and get acceptable performance using them in a DB index. KSUIDs do this. These proposed formats...not so much.

Specifically:

1. All three of these standards devote significant numbers of bits to providing timestamps with very high precision or very distant epochs, or both. If you're generating a v6 UUID and your device's wall clock says it's currently the year 1582 (or really, any year prior to 2021), something has gone very wrong. As for accuracy, there's nothing wrong with it, but you could also shave off a few bits and spend that space on more randomness.

2. All three of these standards devote shockingly few bits to containing raw random bits. v6 has 48, and v7 and v8 don't require any (!) and maxes out at 62 bits. If you could trust that all devices generating v6 UUIDs had super accurate, super in-sync wall clocks, I suppose 48 bits of randomness and a 100 nanosecond timestamp might make sense. But in the real world, I think you're better off focusing on randomness, with only enough of a timestamp to make your database happy.

3. Both v6 and v7 devote significant attention to a clock mechanism. Clocks make a ton of sense in a system like Boundary's Flake (and Twitter's Snowflake), where you're embedding a node ID in the generated value, but these proposed formats don't do this. (Aside from an offhand commend that you could repurpose some of the random bits for this, but that this is "out of scope" for the spec.) Which is fine, but if your UUIDs aren't namespaced per-node, then your clock now needs to be synchronized globally, which is somewhere between "unfeasible" and "outright impossible". I appreciate the review they did of prior solutions, but you can't just grab arbitrary features from successful designs without considering the context that made the feature work in that design. As far as I'm concerned, if the format doesn't have a node ID, then all the bits devoted to clocks should be spent on more randomness.

I assume/hope that these UUIDs are useful for some applications, but I'm really struggling to see it. They seem good at things that aren't going to benefit users and bad at the things they're trying to solve, particularly at scale, although there's no real point for hobbyists either.

pyuser583• 5 years ago

Ok so we’re going back to timestamps.

The wheel turns.

bmn__• 5 years ago

UUID, serial or identity columns for PostgreSQL auto-generated primary keys? (2021-05-31) https://news.ycombinator.com/item?id=27345837

Sortable Collision-Free UUIDs (2021-05-03) https://news.ycombinator.com/item?id=27030088

GUIDs Are Not the Only Answer (2021-01-05) https://news.ycombinator.com/item?id=25650907

Understanding How UUIDs Are Generated (2020-09-30) https://news.ycombinator.com/item?id=24636204

skrebbel• 5 years ago

Seems like a missed opportunity to sneak ULID right in (https://github.com/ulid/spec), given that it's already pretty widely used.

surfingdino• 5 years ago

Interesting. I'd be curious how it affects sharding.

New UUID Formats – IETF Draft

Related Stories