19 ms·

New UUID Formats – IETF Draft

525 points by anuragsoni 5y ago

atonse 5y 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.
- lytedev 5y ago
  Doesn't the textual representation not matter for using them in DB columns? The DB just uses the actual bytes, no?
  - Macha 5y 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-functions.html#function_is-uuid 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 https://www.postgresql.org/docs/9.1/datatype-uuid.html
    - lytedev 5y ago
      This is a good point. Thank you!
  - gregoriol 5y ago
    The important part is the number of bits used for storage; the textual version is only for humans
  - weird-eye-issue 5y 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
    - lytedev 5y ago
      This sounds like a mistake? When/why should the application validate the format of a UUID?
      - cratermoon 5y ago
        Why shouldn't they?
      - therealdrag0 5y ago
        When our services get Strings in requests that are UUIDs we convert them to typed java.util.Uuid objects, if they're not valid they get rejected.
  - dnautics 5y 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.
    - Macha 5y ago
      DB supports from "None" (SQLite) to "We'll give you some functions to work on text/ints that are supposed to be UUIDs" (MySQL) to "It's an actual native data type" (Postgres) among the 3 most common databases used by Django users, so it's hard to blame Django for going with a lowest common denominator approach.
      - dnautics 5y ago
        I have since switched to Elixir/Ecto, and it just "does the right thing" in all of the above databases. Also, I think SQLite is capabale of supporting uuid with one of the plugins that you can add into the amalgamation with a compile switch, in either case ideally the framework would support it transparently.
    - techdragon 5y ago
      I’m not sure this isn’t true, at least for PostgreSQL… I’m maintaining a ULID field library for Django and I’m reasonably sure that it’s getting sent to PostgreSQL as a UUID specific data type.
- athenot 5y 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.
cratermoon 5y ago
I prefer ksuid https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid
- jrochkind1 5y 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.
  - cratermoon 5y 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
    - leo_bloom 5y ago
      > They don't have the awkward dash ('-') to mess with url encoding Can you explain what you mean by that? I have experienced issues with " " as "+" vs. "%20", but dashes... ?
      - cratermoon 5y ago
        Not in URLs per se, but in HTML URL Encoded Multipart Forms, i.e. enctype="multipart/form-data" ETA: also, when you put a UUID as text into a lot of search engines, it treats the dashes as token delimiters.
    - jrochkind1 5y ago
      Which of those things are not true of these new UUID formats proposed? Let's see if I can figure it out (correct me if I'm wrong). I think maybe these new UUIDs proposed ARE lexigraphicaly sortable (in timestamp order, i think is the implication) in text and binary, these newly proposed UUIDs above? I got the impression that was one of the main things they provide, compared to older UUID formats, one of the main reasons for their proposal? Am I wrong? I know the new UUIDs look the same as the ones we're used to, where they often have dashes (although there's certainly no requirement you display them with dashes, you can strip the dashes out before putting them in a URL if you want, although yeah it's an extra step). [If we're talking about URL-encoding we're talking about putting them in URLs? ksuid's 160 bits insead of UUID's 128 , making a longer URL, seems like a downside?] Not sure how many bits of psuedorandom/entropy they have... Looks like... UUIDv6 has 48 bits of psuedorandom in addition to timestamp, to reduce timestamp collisions. UUIDv7 is variable and can let the application decide (am I understanding right?), but supports up to 62 bits of pseudorandom data. [I guess you prefer a longer ID with more bytes of psuedorandom... just to further minimize possibility of timestamp collission, or other reasons? I am not sure how often existing UUID timestamp collisions happen in practice, anyone know? Anyone ever had one?]
deleted 5y ago
[deleted]
nabla9 5y 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 5y ago
"UUIDv8 SHOULD only be utilized if an implementation cannot utilize UUIDv1, UUIDv6, or UUIDv8." I assume that is a typo.
- LukeShu 5y 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.
  - Wevah 5y ago
    There’s another typo in the v7 section where it’s erroneously referred to as v8.
- deleted 5y ago
  [deleted]
jozvolskyef 5y ago
What are the advantages of sortable UUIDs with embedded timestamps over random 128 bits and a created_at column?
- munhitsu 5y ago
  CRDT
- weird-eye-issue 5y ago
  Not having a created_at column and the index bloat that goes with it?
- notamy 5y ago
  It works better for databases that can only sort on the primary key (iirc Cassandra is one of these)
- scrollaway 5y 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.
- lytedev 5y 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).
  - srcreigh 5y 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 :)
riffic 5y ago
Also see RFC 4122: https://datatracker.ietf.org/doc/html/rfc4122 https://datatracker.ietf.org/doc/html/rfc4122
infinityplus1 5y 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 https://gist.github.com/mikelehen/3596a30bd69384624c11
politician 5y 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.
- cratermoon 5y ago
  the practice of embedding machine and data type identifiers into the format is a security risk
  - emodendroket 5y ago
    How do you figure? There's no guarantee guids aren't supposed to be predictable, right?
    - lazide 5y ago
      For one? It allows you to figure out which machine is generating UUIDs, how fast, and all UUIDs it has ever generated. Which 1) is info leakage that is useful to many people in many ways, 2) can be a security risk as it tells you who to attack. 3) at a minimum is a privacy risk.
  - politician 5y 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.
- pjscott 5y 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 5y 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 5y 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 5y 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 5y 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 5y 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.
ComputerGuru 5y 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 https://github.com/ulid/spec
- roberto 5y ago
  They list ULID and 15 other implementations in the document.
  - ComputerGuru 5y ago
    Ah, so they do. Thanks.
- WorldMaker 5y 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=102450 https://devblogs.microsoft.com/oldnewthing/20190426-00/?p=10...
  - ComputerGuru 5y ago
pjscott 5y 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.
- deleted 5y ago
  [deleted]
- zvrba 5y 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 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).
  - pjscott 5y 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.
    - ericb 5y ago
      This is a great example of a Schelling Point! I'd also argue that you're right, and that as a principle, good UI/UX and software architecture should default to following natural Schelling Points.
LukeShu 5y 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
- deleted 5y ago
  [deleted]
- paulddraper 5y ago
  tl;dr Use UUIDv4 and get on with your day.
  - ygra 5y ago
    Well, not if you need database primary keys with sensible index locality. Which is what this draft is about.
    - phkahler 5y ago
      Aren't indexes sorted? I suppose using time as the MSBs means new batches are always appended (after sorting just the new ones).
      - mianos 5y ago
        Yes they are. But, consider the common query, for records based on an time index on the last day. This index will point to a bunch of primary keys and those, being random, will be spread across a much wider range of blocks. If the primary key was just the time, those items would be on the same or close blocks.
gopalv 5y 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?
- WorldMaker 5y 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 5y 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?
    - WorldMaker 5y ago
      This RFC has reason to call out MAC addresses directly as a security risk because they were standardized way back in UUIDv1. (To generate a standards compliant v1 UUID you are still required to use a MAC address, which is why everyone suggests you use UUIDv4 today, and exactly why UUIDv6 exists in the RFC, it's basically exactly UUIDv1 without the MAC address.) The RFC leaves finding a machine-unique ID that isn't a security risk as an exercise to the user. (Mentioned directly in the v7 description where some bytes are optionally allocated for "flake"-like machine IDs.)
sudhirj 5y 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/uulid.go https://github.com/sudhirj/shortuuid.rb https://github.com/sudhirj/shortuuid.rb https://github.com/sudhirj/shortuuid.go https://github.com/sudhirj/shortuuid.go
- stavros 5y ago
  Those look suspiciously similar to the Python one!
  - sudhirj 5y ago
    Probably is quite similar, the converting numbers between bases is a textbook algo, and the UUID format is a standard. Which python one?
    - stavros 5y ago
      This one: https://pypi.org/project/shortuuid/ https://pypi.org/project/shortuuid/
      - sudhirj 5y ago
        Oh, nice. Won’t do one with Python, then :D But yeah, I’ve found the ability to move IDs between alphabets quite useful.
RcouF1uZ4gsC 5y 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 5y 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.
Croftengea 5y 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 5y 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 5y ago
meanwhile.. i did make a shorter one :3 https://github.com/kokizzu/lexid https://github.com/kokizzu/lexid
darkhorse13 5y 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?
- Croftengea 5y ago
  Maybe just wrap your text into <pre> tags? :)
- wrs 5y 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/ https://tools.ietf.org/
- LukeShu 5y 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-uuid-format-01.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-uuid-format-01.txt https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u... by the xml2rfc tool https://xml2rfc.tools.ietf.org/ 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/ https://svn.ietf.org/svn/tools/ietfdb/
  - mtwittman 5y 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-peabody-dispatch-new-uuid-format-01.xml https://github.com/uuid6/uuid6-ietf-draft/blob/master/draft-...
fhrow4484 5y 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)
- pjscott 5y 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.)
- NyxWulf 5y 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 5y 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.
bob1029 5y 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 5y 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 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%5E62%2C+1-e%5E%28-n*%28n-1%29%2F%282H%29%29 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%5E62%2C+sqrt%282*H*ln%281%2F%281-p%29%29%29 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.
tialaramex 5y 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 5y 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 5y ago
I find it peculiar that the Introduction section on these drafts is always just boilerplate.
gfody 5y 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 5y ago
This looks awesome. Can't wait till I can add this to uuid.rocks!
submeta 5y ago
OT: Nicely written and formated ascii document. I wonder what tools they used to create the headars / page numbers / refs.
- krinchan 5y 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/ https://www.rfc-editor.org/pubprocess/tools/
- pawal 5y ago
  There are a number of different tools for writing internet-drafts. See here: https://tools.ietf.org/tools/ https://tools.ietf.org/tools/
- sswaner 5y ago
  I had the same thought: Interesting topic, but I am very distracted by how much I love the format of the document.
OliverJones 5y 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?
- pjscott 5y 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 5y 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 5y 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 https://github.com/uuid6/uuid6-ietf-draft
thayne 5y 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 5y 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?
Lazare 5y 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 5y ago
Ok so we’re going back to timestamps. The wheel turns.
bmn__ 5y ago
UUID, serial or identity columns for PostgreSQL auto-generated primary keys? (2021-05-31) https://news.ycombinator.com/item?id=27345837 https://news.ycombinator.com/item?id=27345837 Sortable Collision-Free UUIDs (2021-05-03) https://news.ycombinator.com/item?id=27030088 https://news.ycombinator.com/item?id=27030088 GUIDs Are Not the Only Answer (2021-01-05) https://news.ycombinator.com/item?id=25650907 https://news.ycombinator.com/item?id=25650907 Understanding How UUIDs Are Generated (2020-09-30) https://news.ycombinator.com/item?id=24636204 https://news.ycombinator.com/item?id=24636204
skrebbel 5y ago
Seems like a missed opportunity to sneak ULID right in (https://github.com/ulid/spec https://github.com/ulid/spec), given that it's already pretty widely used.
surfingdino 5y ago
Interesting. I'd be curious how it affects sharding.

525 points by anuragsoni 5y 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.

lytedev 5y ago
Doesn't the textual representation not matter for using them in DB columns? The DB just uses the actual bytes, no?
- Macha 5y 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-functions.html#function_is-uuid 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 https://www.postgresql.org/docs/9.1/datatype-uuid.html
  - lytedev 5y ago
    This is a good point. Thank you!
- gregoriol 5y ago
  The important part is the number of bits used for storage; the textual version is only for humans
- weird-eye-issue 5y 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
  - lytedev 5y ago
    This sounds like a mistake? When/why should the application validate the format of a UUID?
    - cratermoon 5y ago
      Why shouldn't they?
    - therealdrag0 5y ago
      When our services get Strings in requests that are UUIDs we convert them to typed java.util.Uuid objects, if they're not valid they get rejected.
- dnautics 5y 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.
  - Macha 5y ago
    DB supports from "None" (SQLite) to "We'll give you some functions to work on text/ints that are supposed to be UUIDs" (MySQL) to "It's an actual native data type" (Postgres) among the 3 most common databases used by Django users, so it's hard to blame Django for going with a lowest common denominator approach.
    - dnautics 5y ago
      I have since switched to Elixir/Ecto, and it just "does the right thing" in all of the above databases. Also, I think SQLite is capabale of supporting uuid with one of the plugins that you can add into the amalgamation with a compile switch, in either case ideally the framework would support it transparently.
  - techdragon 5y ago
    I’m not sure this isn’t true, at least for PostgreSQL… I’m maintaining a ULID field library for Django and I’m reasonably sure that it’s getting sent to PostgreSQL as a UUID specific data type.
athenot 5y 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.

cratermoon 5y ago

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

jrochkind1 5y 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.
- cratermoon 5y 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
  - leo_bloom 5y ago
    > They don't have the awkward dash ('-') to mess with url encoding Can you explain what you mean by that? I have experienced issues with " " as "+" vs. "%20", but dashes... ?
    - cratermoon 5y ago
      Not in URLs per se, but in HTML URL Encoded Multipart Forms, i.e. enctype="multipart/form-data" ETA: also, when you put a UUID as text into a lot of search engines, it treats the dashes as token delimiters.
  - jrochkind1 5y ago
    Which of those things are not true of these new UUID formats proposed? Let's see if I can figure it out (correct me if I'm wrong). I think maybe these new UUIDs proposed ARE lexigraphicaly sortable (in timestamp order, i think is the implication) in text and binary, these newly proposed UUIDs above? I got the impression that was one of the main things they provide, compared to older UUID formats, one of the main reasons for their proposal? Am I wrong? I know the new UUIDs look the same as the ones we're used to, where they often have dashes (although there's certainly no requirement you display them with dashes, you can strip the dashes out before putting them in a URL if you want, although yeah it's an extra step). [If we're talking about URL-encoding we're talking about putting them in URLs? ksuid's 160 bits insead of UUID's 128 , making a longer URL, seems like a downside?] Not sure how many bits of psuedorandom/entropy they have... Looks like... UUIDv6 has 48 bits of psuedorandom in addition to timestamp, to reduce timestamp collisions. UUIDv7 is variable and can let the application decide (am I understanding right?), but supports up to 62 bits of pseudorandom data. [I guess you prefer a longer ID with more bytes of psuedorandom... just to further minimize possibility of timestamp collission, or other reasons? I am not sure how often existing UUID timestamp collisions happen in practice, anyone know? Anyone ever had one?]

deleted 5y ago

[deleted]

nabla9 5y 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 5y ago

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

LukeShu 5y 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.
- Wevah 5y ago
  There’s another typo in the v7 section where it’s erroneously referred to as v8.
deleted 5y ago
[deleted]

jozvolskyef 5y ago

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

munhitsu 5y ago
CRDT
weird-eye-issue 5y ago
Not having a created_at column and the index bloat that goes with it?
notamy 5y ago
It works better for databases that can only sort on the primary key (iirc Cassandra is one of these)
scrollaway 5y 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.
lytedev 5y 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).
- srcreigh 5y 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 :)

riffic 5y ago

Also see RFC 4122: https://datatracker.ietf.org/doc/html/rfc4122 https://datatracker.ietf.org/doc/html/rfc4122

infinityplus1 5y 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 https://gist.github.com/mikelehen/3596a30bd69384624c11

politician 5y 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.

cratermoon 5y ago
the practice of embedding machine and data type identifiers into the format is a security risk
- emodendroket 5y ago
  How do you figure? There's no guarantee guids aren't supposed to be predictable, right?
  - lazide 5y ago
    For one? It allows you to figure out which machine is generating UUIDs, how fast, and all UUIDs it has ever generated. Which 1) is info leakage that is useful to many people in many ways, 2) can be a security risk as it tells you who to attack. 3) at a minimum is a privacy risk.
- politician 5y 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.
pjscott 5y 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 5y 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 5y 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 5y 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 5y 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 5y 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.

ComputerGuru 5y 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 https://github.com/ulid/spec

roberto 5y ago
They list ULID and 15 other implementations in the document.
- ComputerGuru 5y ago
  Ah, so they do. Thanks.
WorldMaker 5y 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=102450 https://devblogs.microsoft.com/oldnewthing/20190426-00/?p=10...
- ComputerGuru 5y ago

pjscott 5y 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.

deleted 5y ago
[deleted]
zvrba 5y 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 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).
- pjscott 5y 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.
  - ericb 5y ago
    This is a great example of a Schelling Point! I'd also argue that you're right, and that as a principle, good UI/UX and software architecture should default to following natural Schelling Points.

LukeShu 5y 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

deleted 5y ago
[deleted]
paulddraper 5y ago
tl;dr Use UUIDv4 and get on with your day.
- ygra 5y ago
  Well, not if you need database primary keys with sensible index locality. Which is what this draft is about.
  - phkahler 5y ago
    Aren't indexes sorted? I suppose using time as the MSBs means new batches are always appended (after sorting just the new ones).
    - mianos 5y ago
      Yes they are. But, consider the common query, for records based on an time index on the last day. This index will point to a bunch of primary keys and those, being random, will be spread across a much wider range of blocks. If the primary key was just the time, those items would be on the same or close blocks.

gopalv 5y 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?

WorldMaker 5y 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 5y 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?
  - WorldMaker 5y ago
    This RFC has reason to call out MAC addresses directly as a security risk because they were standardized way back in UUIDv1. (To generate a standards compliant v1 UUID you are still required to use a MAC address, which is why everyone suggests you use UUIDv4 today, and exactly why UUIDv6 exists in the RFC, it's basically exactly UUIDv1 without the MAC address.) The RFC leaves finding a machine-unique ID that isn't a security risk as an exercise to the user. (Mentioned directly in the v7 description where some bytes are optionally allocated for "flake"-like machine IDs.)

sudhirj 5y 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/uulid.go https://github.com/sudhirj/shortuuid.rb https://github.com/sudhirj/shortuuid.rb https://github.com/sudhirj/shortuuid.go https://github.com/sudhirj/shortuuid.go

stavros 5y ago
Those look suspiciously similar to the Python one!
- sudhirj 5y ago
  Probably is quite similar, the converting numbers between bases is a textbook algo, and the UUID format is a standard. Which python one?
  - stavros 5y ago
    This one: https://pypi.org/project/shortuuid/ https://pypi.org/project/shortuuid/
    - sudhirj 5y ago
      Oh, nice. Won’t do one with Python, then :D But yeah, I’ve found the ability to move IDs between alphabets quite useful.

RcouF1uZ4gsC 5y 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 5y 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.

Croftengea 5y 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 5y 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 5y ago

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

darkhorse13 5y 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?

Croftengea 5y ago
Maybe just wrap your text into <pre> tags? :)
wrs 5y 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/ https://tools.ietf.org/
LukeShu 5y 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-uuid-format-01.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-uuid-format-01.txt https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u... by the xml2rfc tool https://xml2rfc.tools.ietf.org/ 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/ https://svn.ietf.org/svn/tools/ietfdb/
- mtwittman 5y 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-peabody-dispatch-new-uuid-format-01.xml https://github.com/uuid6/uuid6-ietf-draft/blob/master/draft-...

fhrow4484 5y 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)

pjscott 5y 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.)
NyxWulf 5y 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 5y 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.

bob1029 5y 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 5y 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 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%5E62%2C+1-e%5E%28-n*%28n-1%29%2F%282H%29%29 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%5E62%2C+sqrt%282*H*ln%281%2F%281-p%29%29%29 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.

tialaramex 5y 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 5y 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 5y ago

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

gfody 5y 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 5y ago

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

submeta 5y ago

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

krinchan 5y 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/ https://www.rfc-editor.org/pubprocess/tools/
pawal 5y ago
There are a number of different tools for writing internet-drafts. See here: https://tools.ietf.org/tools/ https://tools.ietf.org/tools/
sswaner 5y ago
I had the same thought: Interesting topic, but I am very distracted by how much I love the format of the document.

OliverJones 5y 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?

pjscott 5y 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 5y 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 5y 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 https://github.com/uuid6/uuid6-ietf-draft

thayne 5y 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 5y 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?

Lazare 5y 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 5y ago

Ok so we’re going back to timestamps. The wheel turns.

bmn__ 5y ago

UUID, serial or identity columns for PostgreSQL auto-generated primary keys? (2021-05-31) https://news.ycombinator.com/item?id=27345837 https://news.ycombinator.com/item?id=27345837 Sortable Collision-Free UUIDs (2021-05-03) https://news.ycombinator.com/item?id=27030088 https://news.ycombinator.com/item?id=27030088 GUIDs Are Not the Only Answer (2021-01-05) https://news.ycombinator.com/item?id=25650907 https://news.ycombinator.com/item?id=25650907 Understanding How UUIDs Are Generated (2020-09-30) https://news.ycombinator.com/item?id=24636204 https://news.ycombinator.com/item?id=24636204

skrebbel 5y ago

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

surfingdino 5y ago

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