UUIDv7 has been taking HN by storm for years now! When is it going to become a proper standard, and when are libraries and databases and all the rest going to natively support it?
Its been going through drafts and improvements. It's very close to being standardized, and many libraries are supporting it already, or new offerings are being added. For example I maintain the Dart UUID library, and my latest beta major release has v6, v7 and a custom v8. There is a list of them somewhere, I know I get pinged on every new draft by the authors because I am listed as a library maintainer on one of their pages.
Seeing as how its nearly done, it doesn't change much. It changed more often in the beginning, but its like on its final draft, or near final draft. I think the IETF plans to make final soon.
What kind of support do you expect? I'm pretty sure that absolute majority of software does not care about any particular bits in UUID, so you can use it today. If some software cared about any particular bits, just imitate UUIDv4, I mean those bits could be randomly generated as well. If you need generation procedure, write it yourself, it's easy.
Unrelated, but this links to "Crockford's alphabet", https://www.crockford.com/base32.html , which is a base-32 system that includes all alphanumeric characters except I and L (which are confusable with 1), O (which is confusable with 0), and U (????). The page says the reason for excluding U is "accidental obscenity'. What the heck is it talking about?
You can prevent any obscenity, O and 0 confusion, and I and L confusion, just by excluding vowels. If someone interprets "f4g" in an offensive way, then they have bigger issues than can be dealt with in software.
There was that time Delta generated an "H8GAYS" PNR. [1] Pretty sure that's valid Crockford encoding too :) however, to your point, it does rely on 'A'. "H8G4YS" would likely still offend someone out there, though, given the kerfuffle in [1].
> But as White points out, it’s a bit surprising that Delta didn’t block this particular combination as a possibility. “I’m sure they removed many four-letter words that would be seen as offensive,” he tells the Post. “I’m surprised that ‘gays’ and ‘H8’ weren’t blocked as well.”
Oh sweet summer child (meaning Jeff White, not OP/GP). As someone who has implemented a censorship/filtering list, this is a UX problem on the same level of decideability as the halting problem. You can spend boundless time curating a list to flag/grawlix every possible string that would offend even the most prudish of prudes, and some would still get through. Such as the superficially benign "EATTHE"
The problem is not being offended per se, but having your user id accidentally become "user_123fuck567" — that's akin to having a vulgar license plate on your car's forehead. People don't appreciate how lucky they sometimes are.
Using Stripe-style prefixing is most useful if they are—it makes interacting with customer support easier because everyone is on the same page about what this ID identifies.
A coworker and I came up with basically this same set about 4 years before Crockford. We were trying to solve the url slug problem, and they were long enough that we felt 5 bits per byte would reduce transcription annoyances.
In the end I think we had a couple of characters to spare, and so, sitting by ourselves because everyone else had gone home for the day, we ranked swear words by how offensive they were to prioritize removal of a few extra letters. Then I convinced him that slurs were a bigger problem so we focused on that, which got rid of the letter n, instead of u
tggr is just cute, n**r is an uncomfortable conversation with multiple HR teams (we were B2B)
I'm a bit fuzzy now on what our ultimate character set was, because typically you're talking [a-z][0-9], an there are a lot of symbols you can't use in urls and some that are difficult to dictate. My recollection is that we eliminated both 0, l, and 1, but I think we relied on transcription happening either from all caps or all lowercase.
0o are not a problem. Nor are 1L.
Other comments are jogging my memory. I think we went case sensitive (62 characters -> 30 spares), eliminated aA4, eE3, iI1l oO0 (maybe Q), uU, which is 16 characters, 14 to go. Remove the remaining 7 numbers (once you remove most for leetspeak what's the point of the rest?), nN, yY. That leaves 2 left and I can't recall what we did with those. Maybe kK or rR.
If I and O are already excluded and you also exclude U that removes a lot of potential rude looking three letter combinations like *** and *** and *** and also the four letter ones like **** and **** and the dreaded ****. Of course because you have A then **** is still a possibility but very very unlikely
Wow I didn't know HN even had obscenity filters, and I've been here for many years.
Guess that's a credit to the general civility of the community.
EDIT: It appears that other people in this thread are freely using profanity, so either your comment was targeted by automation due to the unusual density of banned words, or it's a joke that went over my head :)
That explains it, I was very confused by what I assumed was self-censoring, since the comment didn’t actually clarify anything. I wish there was an accepted way to disambiguate asterisks from server side filters.
> The page says the reason for excluding U is "accidental obscenity'.
Crockford is being cheeky. To make a nice base32 alphabet out of non-confusable alphanumeric characters you only need to exclude O, I, and L. This leaves you with 33 characters still, so you need to remove one more, and it doesn't matter which one you remove, so you might as well pick an arbitrary reason for the last character that gets removed (and it's not the worst reason, if your goal is to use these as user-readable IDs, although obviously it's not even remotely bulletproof).
A vaguely related historical tangent is that V and U used to be just two ways of writing the same letter in Early Modern English. Which I imagine is why W is named as "double U" in speaking.
Same thing in Norwegian. But W is also not really a part of Norwegian orthography, it's just kind of there in the alphabet anyway. Only useful for names and maybe a couple loanwords.
Assuming you don't need to use UUIDv7 (or any UUID's) then https://github.com/segmentio/ksuid provides a much bigger keyspace. You could just append a string prefix if you wanted to namespace, but the chance of collisions of a ksuid is many times smaller than a UUID of any version.
ksuid is the best general purpose id generator with sort-able timestamps I've found and has libraries in most languages. UUID v1-7 are wasteful.
We maintain a couple of popular ksuid libraries[1][2] and use it, so we definitely like ksuid. Though one big issue with ksuid is that being 160bit means that it doesn't fit into native uuid types in databases (e.g. postgres), which means that they come with a performance penalty.
I'm curious, why do you not store these as binary data or do you and you're saying that the UUID operations are better optimized than sorts on binary data?
The spec has a really weird choice in it - it attempts to guarantee monotonicity. There's a few problems with that, namely that it's almost entirely pointless, it's impossible to actually guarantee it, and the spec mandates it be done in a bad way. Breaking those down:
* There's no particular reason why you'd expect UIDs to give you monotonic ordering, and no particular use case for it either. Being roughly k-sortable is very useful (eg, to allow efficient DB indexes), but strict monotonicity? There's just very few cases where that's needed, and when it is, you'd probably want a dedicated system to coordinate that. Even worse, if you do need it, ULIDs don't actually guarantee it. Which brings us to:
* UIDs are generally most useful in distributed systems, and the more you scale the more that will become required. The second you have a second system generating UIDs, your monotonicity guarantees go out the window, and without work that the various ULID libraries have not done, that's even true the moment you have a second process generating them. And the ULID spec doesn't even try and work around this (nor do all ULID libraries try to guarantee monoticity even when used in a single threaded manner), which in turn means you have no idea if any given ULID was generated in a way where monoticity is being attempted.
* The actual ULID spec says the UID is broken up into a timestamp and a random component, and if you ever generate a second ULID in the same millisecond, you must increment the random component, and if you can't due to overflow, generation must fail. Which is wild; it means you can only generate a random number of ULIDs per millisecond, and there's a chance you can only generate one. Even worse, if you can ever manage to cause a system to generate a ULID for you in the same millisecond as it generates one for your target, you can trivially guess the other ULID! Many use cases for UIDs assume they're effectively unguessable, but this is not true for compliant ULIDs.
The ULID spec is, a best, a bit underbaked. (And as others have noted, I find that Crockford's base32 encoding is a suboptimal choice.)
I have a thin JavaScript package published which generates type-prefixed KSUIDs. KSUID is a great format assuming you can spare the extra bits (which is most people)
Naive Question: The type safe part is just appending a string at the beginning? What if I do that with UUIDv4? is user_49b9cd12-9964-4b9c-8512-742f0a2c9be4 type safe now?
That's how the type is encoded as a string, but type-safety ultimately comes from how the TypeID libraries allow you to validate that the type is correct.
For example, the PostgresSQL implementation of TypeID, would let you use a "domain type" to define a typeid subtype. Thus ensuring that the database itself always checks the validity of the type prefix. An example is here: https://github.com/jetpack-io/typeid-sql/blob/main/example/e...
In go, we're considering it making it easy to define a new Go type, that enforces a particular type prefix. If you can do that, then the Go type system would enforce you are passing the correct type of id.
Yep. The whole point is that you /never/ assign ids that begin with "user" to types that are not users. Because of that, you can be sure nobody can accidentally copy an id that begins with "user" when meaning to address a different type and get back a result other than "not found".
Example:
I have userId=4 and userId=2. Suppose a user can have multiple bank accounts and userId=4 has accountId=5 and accountId=6 and a defaultAccound accountId=5. userId=2 has an account, accountId=7; I want to send userId=4 some money so I use the function `sendUserMoneyFromAccount(to: int, from: int)`. This is a bad interface but these things exist in the wild a lot. I could accidentally assume that because I want to send userId=4 the money to their default account that I would call it using `sendUserMoneyFromAccount(4, 7)` and that would work, but if under the hood it wants 2 accountIds, I've just sent accountId=4 money rather than userId=4's defaultAccount, accountId=5.
With prefixed ids that indicate type, a function that assumes type differently from the one supplied will not accidentally succeed.
In addition, humans who copy ids will be less likely to mistake them. This is just an ergonomic/human centric typing.
I have some complaints about UUIDs. Why not just combining time + random number without the ceremony of UUID versioning. And for when locality doesn't matter, just use a 128bit random number directly.
And in my experience most people somehow think a UUID must be stored into the human friendly hex representation, dashes included. Wasting so much space in database, network, memory.
I have single datasets with trillions of UUID. Collision probability becomes a thing.
That aside, UUIDv4 is banned in many orgs because there have been several instances in the wild where the “random” number wasn’t nearly as random as advertised from some sources for a variety of reasons, leading to collisions. It is relatively easy to screw this up so many orgs don’t risk it.
While this isn't the worst area I see this in, there does seem to be a tendency in the UUID space to speak as if one use case stands for all and therefore there is a best UUID format.
The reality is that it is just like any other engineering situation. Sit down, write down your requirements, and see what, if anything, solves it.
Reading about the advantages of various formats is very helpful in helping you skip learning about certain things the hard way and use somebody else's experience of learning them the hard way instead. From that point of view I recommend at least glancing through them all. Sortability and time-based locality is one that you may not naturally think about, and if you need it, you will appreciate not learning that the hard way four years into a project after you threw that data away and then realizing you needed it. And some UUID formats actually managed to introduce small security issues into themselves (thinking MAC address leak from UUID v1 here), nice to avoid those too.
If you have a use case where there's an existing solution then, hey, great, go ahead and use it. Maybe if anyone ever needs that but in another language they can pull a library there too.
But if not, don't sweat it. The biggest use of UUIDs I personally have I specified as "just send me a unique string, use a UUID library of your choice if it makes you feel better". I think I've got a unique format per source of data in this system and it's fine. I don't have volume problems, it's tens of thousands of things per day. I don't have any need to sort on the UUID, they're not really the "identifier", they're just a unique token generated for a particular message by the originator of the message so we can detect duplicate arrivals downstream in a heterogenous system where I can't just defer that task to the queue itself since we have multiple. I don't even need them to be globally unique, I just need them unique within a rather small shard, and in principle I wouldn't even mind if they get repeated after a certain amount of time (though I left the system enforcing across all time anyhow for simplicity). In this particular case, I do indeed generate my own UUIDs for the stuff I'm originating by just grabbing some stuff from /dev/urandom and encoding it base64, with a size selected such that base64 doesn't end the encoding with ==. Even that's just for aesthetic's sake rather than any actual problem it would cause.
The only worthwhile UUID standard IMO is v4 (simple random), and I still don't get why it needs dashes. The other ones don't really accomplish anything.
I implemented something similar recently, but opted to write my own UUIDv7 that uses the last 16 flexible bits for a "type ID". That allows 65K different data models, which should be more than enough. Could even partition that further to store a node ID for a globally distributed setup.
So it's got all of the above perks, but it also an actual UUID and fits in a Postgres UUID column.
It's very cool to be able to resolve a UUID to a particular database table and record with almost zero performance overhead (cached table lookup + indexed record select).
Ideally, you should version that as UUIDv8. Since that is a more custom implementation, but I guess changing the random bits with type info works fine for UUIDv7, they jsut arent random anymore.
I am aware, just saying per spec, its supposed to be random bit data, thats all I was saying. I am familiar with a spec since I maintain a UUID library that has 6,7, and a custom 8 implemented.
It can have extra monotonicity data instead, per section 6.2 but ideally its random. Again, Not saying you can't do what you are doing, I just know per the conversations while the draft was gathering feedback, your type of change was intended to be done as uuidv8
Well, which is it? These are incompatible requirements.
If I give you a standard UUIDv7 sample, it is impossible for you to interpret the last 62 bits. You cannot determine how they were generated. If I give you two samples with the same timestamp, you cannot say which was generated first. These bits are de facto uninterpretable, unlike e.g. the 48 MSB, which have clearly defined semantics.
For list item #3 it says "Random data for each new UUIDv7 generated for any remaining space." without the word "optional" and the bit layout diagram says `rand_b`
But when you read the description for `rand_b` it says: "The final 62 bits of pseudo-random data to provide uniqueness as per Section 6.8 and/or an optional counter to guarantee additional monotonicity as per Section 6.2."
If you can guarantee that you custom uuidv7 is globally unique for 10000 values per second or more, I don't see why you can't do what you do and treat your custom data as random outside of your implementation.
I think part of this is my mistake, because I assumed you replaced most of the random data with information, but reading it now, I read that you replaced just the last 16 bits. Also since most people used random data for UUIDv1's remaining 48bits of `node` then your variation is no worse than UUIDv1 (or 6) while also being compatible with v7.
I think I just got too caught up on the the bit layout calling it `random` and misread your information. Sorry for the misunderstanding, and thanks for discussing it.
Well UUIDv7 can be consumed as a UUIDv4 in the same way, its just 16 bytes. The point of the standard is to define how the particular bytes are chosen.
The latest standard for v7 does not meaningfully describe how to interpret the last segment.
It says they could be pseudorandom and non-monotonic. Or it could be monotonic and non-random. These are completely disjoint cases! "X or not X" is tautological. And there is no way to determine which (e.g. there could be a flag that indicates this mode, but there is not).
To be clear, the standard should be amended to resolve this ambiguity. Say the last bits MAY be monotonic or MAY be pseudorandom. Or add a flag that indicates which.
As there is currently no standard way to interpret these bits, I feel perfectly justified in using the a few of the least significant ones to encode additional information.
I think the purpose of the standard is so that different software implementations work the same way, so that once you've picked a standard, you can use it everywhere and know that keys are assigned the same way regardless of which software stack is generating a particular key. Its not so that systems can "interpret" it. Obviously they are your bytes to use however you want if you are rolling your own generator.
Also, they are safe to use within filenames and directory names (Filesystem paths) without conversion (at least in today's Filesystem not limited to e.g. 8.3 characters) .
Compare that with otherwise nice ISO 8601 datetime format (e.g. 2023-06-28T21:47:59+00:00): it requires conversion for file systems that don't allow colons and plus signs.
This is very similar to how I generate IDs in a project I'm working on.
Example:
|-A-|-|------------B--------------|
NMSPC-9TWN1-HR7SV-MTX00-0H8VP-YCCJZ
A = Namespace, padded to 5 chars. Max 5 chars. Uppercase.
B = Blake3 hashed microtime with a random key.
I like how it folds in a time component but that it also doesn't reveal the time it was generated.
Namespacing identifiers in general is a great idea for handling those class of integration tests which cannot be fully isolated. It makes it easy to write all kinds of garbage from even concurrently running tests all without any of them colliding or accidentally reading each others writes (because they are themselves namespace aware!). It's low effort to get all the pieces of your system to play along (often entirely transparent via DI), but gives a huge power to weight ratio. Basically deletes an entire class of problems which usually plague large, mature test suits
Do you generate a random key for each id? If so, you loose the time component of your I'd, because two hashes made at a different time can produce the same hash when using a different key (I think). If you use a single key you need to manage it and keep it secret which isn't really ideal for something simple like id's. If you reveal the key you could as well use an unkeyed hash, right? Maybe a salted hash with the same salt for every key to make dictionary attacks on the creation time harder. But then again it's probably easier to just generate random bits for the id, as you don't have sortability in any case.
An important aspect of identifiers is to not leak any information in the identifier. In some scenarios a prefix might be fine but less important things have been blocked by our dpo department.
Yeah, this idea makes me uneasy as well for the same reason. The natural conclusion would be to have DB frameworks automatically do this based upon code type names and that definitely feels like a leak, handing the world at large a roadmap to your internal system architecture.
Yeah and Twitter IDs used to be 32-bit integers. In this case it is kind of obvious that the IDs leaks information about internal data types. Which is not ok at many companies.
I do a similar thing [1]. One of the great advantages to formally namespaced IDs is including a systematic conversion into strong types in your code. It's harder to accidentally mix things up when coding; function parameters and return tuples are more 'self documented' (and enforced by compiler where applicable).
How does this compare to a SQUUID for sorting or nano-id for human readability? Both are options I've used in the past when using databases like Datomic or XTDB. SQUUIDs in particular because I have a UUID that can be ordered by timestamp, nano-id when prototyping things and I want meaningful prefixes in my entity IDs rather than a bunch of UUIDs.
That if a hundred servers are generating (uuid, timestamp) tuples that are subsequently merged on a single machine, and sorted by uuid, it would have almost the same order as if sorted by timestamp.
This property is useful for RDBMS writes, when the UUID is used as a primary key and this locality ensures that fewer slotted pages need to be modified to write the same amount of data.
Is that what they mean by "used as the primary key in a database while ensuring good locality"/"database locality"? That read/write access will hit fewer disk pages?
> it would have almost the same order as if sorted by timestamp.
Is there documentation covering the scenarios on how the order can become out of sync and what the odds are? There's a big difference between "almost" and "always" if we're talking about using this as a database PK.
> There's a big difference between "almost" and "always"
Not in the context of an RDBMS, which use b+/b*-tree variants (or LSM sstables). Sequentially generated UUID's will end up near each other when sorted lexicographically, regardless of the fact that the sort order doesn't perfectly match the timestamp order.
The key seems to be based on UUIDv7, starting with a timestamp in milliseconds.
So the order can become out of sync if multiple events happen in the same millisecond; or if your servers' clock error is greater than a millisecond (i.e. if you're an NTP user)
More than sufficient for things like ordering tweets. If you're ordering bank account transactions, well, you'd probably be using transactions in an ACID-compliant relational database.
That it is a nearly sorted sequence. Typically the first part of the ID is a timestamp. So you may sort the IDs down to the second it was created. But for IDs created at the same time the order is random. This can be used for caching, database performance and so on.
Neat! Love the "type-safe" prefix; we'd called them "tagged ids" in our ORM that auto-prefixes the otherwise-ints-in-the-db with similar per-entity tags:
We'd used `:` as our delimiter, but kinda regretting not using `_` because of the "double-click to copy/paste" aspect...
In theory it'd be really easy to get Joist to take "uuid columns in the db" and turn them into "typeids in the domain model", but probably not something that could be configured/done via userland atm...that'd be a good idea though.
Reddit does something similar, but optimized for string length: elements have ids like "t3_15bfi0" where t3_ is a prefix for the type (t3 is a post, t1 a comment, t5 a subreddit, etc) and the remaining is a base36 encoding of the autoincrementing primary key.
The `t<X>` makes sense; we currently guess a tag name of "FooBarZaz" --> "fbz", but allow the user to override it, so you could hand-assign "t1", "t2", etc. as you added entities to the system.
Abbreviating/base36-ing even the auto-incremented numeric primary key to optimize lengths is neat; we haven't gotten to the size of ids where that is a concern, but it sounds like a luxurious problem to have! :-)
My company has a typed internal ID system that originally used colons as delimiters but we quickly switched to dots (.) as the delimiter because it’s very annoying to have url-encoded IDs balloon in size because colons need to be %-encoded. Makes your urls ugly and long.
I have one idea which is perhaps nerdy enough to make the list but I've never fully fleshed it out, it's that one can encode the nonnegative integers {0, 1, 2, ...} into the finite bitstrings {0, 1}* in a way which preserves ordering.
So if we use hexits for the encoding the idea would be that 0=0, 1=1, ... E=14, then
so the format is F, which is the overflow sigil, followed by a recursive representation of the length of the coming string, followed by a string of hexits that long.
What if you need 16 hexits? That's where the recursion comes in,
F F00 0123456789ABCDEF
\ \ \
\ \ \----- 16 hexits
\ \
\ \-- the number 15, "there are 15+1 digits to follow"
\ (consisting of overflow, 0+1 digits to follow, and hex 0)
\
\--- overflow sigil
Kind of goofy but would allow a bunch of things like "timestamp * 1024 + 10-bit machine ID" etc without worrying about the size of the numbers involved
Any time you ever read a string, its type is always just going to be "string" (modulo whatever passes for a "string" in your programming language of choice). To get an actual non-string type, you'd need to parse that string, and presumably your parsing function would read the prefix and reject the string if it was passed an ID whose type doesn't match. So it's dynamically type-safe, if not statically type-safe.
I don't know go, but in C# I'd probably do something like the code below. The object really only needs to carry the uuid/guid, let the language type system worry about the difference between a user and post id. We just need a generic mechanism to ensure that UserId object can only be constructed from a valid type id string with type = user. For production use you'd obviously need more methods to construct it from a database tuple (mentioned elsewhere in the comments), etc.
interface ITypeIdPrefix
{
static abstract string Prefix { get; }
}
abstract class TypeId<T>
where T : TypeId<T>, ITypeIdPrefix, new()
{
public Guid Id { get; private init; }
public override string ToString() => $"{T.Prefix}_{Id.ToBase32String()}";
// Override GetHashcode(), Equals(), etc.
public static bool TryParse(string s, out T? result)
{
if (!s.StartsWith(T.Prefix) || !TrySplitStringAndParseBase32ToGuid(s, out var id))
{
result = default;
return false;
}
result = new T { Id = id };
return true;
}
}
class UserId : TypeId<UserId>, ITypeIdPrefix
{
public static string Prefix => "user";
}
class PostId : TypeId<PostId>, ITypeIdPrefix
{
public static string Prefix => "post";
}
It's based on UUIDv7 (in fact, a TypeID can be decoded into an UUIDv7). The main reasons to use TypeID over "raw" UUIDv7 are: 1) For the type safety, and 2) for the more compact string encoding.
If you don't need either of those, then UUIDv7 is the right choice.
Does the prefix ("user_") get recorded in the DB (so every string in the column starts with the same "user_"), or does are there constraints and other clever chicanery to save those bytes in every record? Or do modern DB engines even care? Is this premature optimization?
This is more optimal for Postgres while making it slightly more difficult to interop between the db and the language (db driver needs to handle custom types, and you need to inject a custom type converter).
And while there are hacks you can do to make storing uuid-alikes as strings less terrible for db engines, if you want the best performance and smallest space consumption (compressed or not) make sure to use native ID types or convert to BINARY/numeric types.
In my experience, using just uuid as a pkey in Postgres already causes noticeable slowdowns vs the typical bigint. I wouldn't jump into anything other than bigint pkeys unless I'm solving an existing problem and have benchmarks to prove it.
I've been doing this kind of thing for years with two notable differences:
1. I don't believe people actually hand type-in these values, so I'm not really concerned about the 'l' vs '1' issue. I do base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in.
2. I add two base-32 characters as a checksum (salted of course). This is prevents having to go look at the datastore when the value is bogus either by accident or malice. I'm unsure why other implementations don't do this.
Why not use base-31 and (optionally) more characters? (Or go upper and lower or add a symbol if you had to stay with a fixed-size and base-32 for some reason)
I realise you posted this as a joke, but the first time I saw this, I was so confused. I thought the comment was starting with "I anal" before I read the rest of the post only to compute it means "I Am Not A Lawyer"
I implemented number two as part of an encoding scheme a few months ago. I'm not sure how much it's saved in terms of database lookups but it's aesthetically pleasing to know it won't hit a more inscrutable error while trying to decode.
The benefit is that you can reject bad requests to an API more easily.
For one application I used a base 58 encoded value. Part of it was a truncated hmac, which I used like check digits. This meant I could validate IDs before hitting the DB. As an attacker or script kiddie could otherwise try a resource exhaustion attack.
So in the age of public internet faceing APIs and app urls, I think built in optional check digit support is a good idea.
Storage can get corrupted, columns can be truncated. For the applications I tend to touch correctness and the ability to detect errors and tamper are more important that a couple of bytes per row.
But every application and domain is different.
I agree with the addition of the checksum, however I’m curious:
> either by accident or malice
1. if you don’t believe people hand type these then how else will they accidentally enter an invalid? I suppose copy/paste errors, or if a page renders it as uppercase, though you should just normalize the case if it’s base 32.
2. How does a 2 byte (non-cryptographically secure) checksum help in the case of malice?
This looks great! Is there a reason one couldn't use this with v4 UUIDs? A quick test shows that they encode/decode just fine. Wondering if I could use the encoded form as a way to niceify our URLs without having to change how the IDs (currently v4 uuids) are stored
The CLI tool will support encoding/decoding any valid UUID, whether v1, v4, or v7. We picked v7 as the definition of the spec, because we need to choose one of them when generating a new random ID, and our opinion is that by default, that should be v7.
We might add a warning in the future if you decode/encode something that is not v7, but if it suits your use-case to encode UUIDv4 in this way, go for it. Just keep in mind that you'll lose the locality property.
235 comments
[ 2.7 ms ] story [ 249 ms ] threadIDs generation is usually private to a company scope and rarely need to be "universally unique".
eg: google "allinurl:fag site:youtube.com"
[1] https://newsfeed.time.com/2013/12/17/delta-airlines-is-very-...
Oh sweet summer child (meaning Jeff White, not OP/GP). As someone who has implemented a censorship/filtering list, this is a UX problem on the same level of decideability as the halting problem. You can spend boundless time curating a list to flag/grawlix every possible string that would offend even the most prudish of prudes, and some would still get through. Such as the superficially benign "EATTHE"
https://www.dailymail.co.uk/news/article-2039662/Virginia-dr...
Even programming language have them. For instance, Basic has GOTO.
/j
https://en.m.wikipedia.org/wiki/Scunthorpe_problem
In the end I think we had a couple of characters to spare, and so, sitting by ourselves because everyone else had gone home for the day, we ranked swear words by how offensive they were to prioritize removal of a few extra letters. Then I convinced him that slurs were a bigger problem so we focused on that, which got rid of the letter n, instead of u
tggr is just cute, n**r is an uncomfortable conversation with multiple HR teams (we were B2B)
I'm a bit fuzzy now on what our ultimate character set was, because typically you're talking [a-z][0-9], an there are a lot of symbols you can't use in urls and some that are difficult to dictate. My recollection is that we eliminated both 0, l, and 1, but I think we relied on transcription happening either from all caps or all lowercase. 0o are not a problem. Nor are 1L.
Y is pretty versatile for pissing people off.
Guess that's a credit to the general civility of the community.
EDIT: It appears that other people in this thread are freely using profanity, so either your comment was targeted by automation due to the unusual density of banned words, or it's a joke that went over my head :)
http://www.bash.org/?244321
Crockford is being cheeky. To make a nice base32 alphabet out of non-confusable alphanumeric characters you only need to exclude O, I, and L. This leaves you with 33 characters still, so you need to remove one more, and it doesn't matter which one you remove, so you might as well pick an arbitrary reason for the last character that gets removed (and it's not the worst reason, if your goal is to use these as user-readable IDs, although obviously it's not even remotely bulletproof).
It is why PH is F, for instance.
See more from jan Misali: https://www.youtube.com/watch?v=sg2j7mZ9-2Y
- base 58 - Satoshi's/Bitcoin's https://en.wikipedia.org/wiki/Binary-to-text_encoding#Base58
- "base62" - Keybase's saltpack https://github.com/keybase/saltpack
- The famous "Adobe 85" - https://en.wikipedia.org/wiki/Ascii85
- basE91 - https://base91.sourceforge.net
At work we defined several new "bases" for QR code. IMHO, it is an under applied area of computer science.
Because he’s an American?
ksuid is the best general purpose id generator with sort-able timestamps I've found and has libraries in most languages. UUID v1-7 are wasteful.
1: https://github.com/svix/rust-ksuid 2: https://github.com/svix/python-ksuid
The spec has a really weird choice in it - it attempts to guarantee monotonicity. There's a few problems with that, namely that it's almost entirely pointless, it's impossible to actually guarantee it, and the spec mandates it be done in a bad way. Breaking those down:
* There's no particular reason why you'd expect UIDs to give you monotonic ordering, and no particular use case for it either. Being roughly k-sortable is very useful (eg, to allow efficient DB indexes), but strict monotonicity? There's just very few cases where that's needed, and when it is, you'd probably want a dedicated system to coordinate that. Even worse, if you do need it, ULIDs don't actually guarantee it. Which brings us to:
* UIDs are generally most useful in distributed systems, and the more you scale the more that will become required. The second you have a second system generating UIDs, your monotonicity guarantees go out the window, and without work that the various ULID libraries have not done, that's even true the moment you have a second process generating them. And the ULID spec doesn't even try and work around this (nor do all ULID libraries try to guarantee monoticity even when used in a single threaded manner), which in turn means you have no idea if any given ULID was generated in a way where monoticity is being attempted.
* The actual ULID spec says the UID is broken up into a timestamp and a random component, and if you ever generate a second ULID in the same millisecond, you must increment the random component, and if you can't due to overflow, generation must fail. Which is wild; it means you can only generate a random number of ULIDs per millisecond, and there's a chance you can only generate one. Even worse, if you can ever manage to cause a system to generate a ULID for you in the same millisecond as it generates one for your target, you can trivially guess the other ULID! Many use cases for UIDs assume they're effectively unguessable, but this is not true for compliant ULIDs.
The ULID spec is, a best, a bit underbaked. (And as others have noted, I find that Crockford's base32 encoding is a suboptimal choice.)
[1] https://github.com/sophiabits/resource-id
For example, the PostgresSQL implementation of TypeID, would let you use a "domain type" to define a typeid subtype. Thus ensuring that the database itself always checks the validity of the type prefix. An example is here: https://github.com/jetpack-io/typeid-sql/blob/main/example/e...
In go, we're considering it making it easy to define a new Go type, that enforces a particular type prefix. If you can do that, then the Go type system would enforce you are passing the correct type of id.
Example:
I have userId=4 and userId=2. Suppose a user can have multiple bank accounts and userId=4 has accountId=5 and accountId=6 and a defaultAccound accountId=5. userId=2 has an account, accountId=7; I want to send userId=4 some money so I use the function `sendUserMoneyFromAccount(to: int, from: int)`. This is a bad interface but these things exist in the wild a lot. I could accidentally assume that because I want to send userId=4 the money to their default account that I would call it using `sendUserMoneyFromAccount(4, 7)` and that would work, but if under the hood it wants 2 accountIds, I've just sent accountId=4 money rather than userId=4's defaultAccount, accountId=5.
With prefixed ids that indicate type, a function that assumes type differently from the one supplied will not accidentally succeed.
In addition, humans who copy ids will be less likely to mistake them. This is just an ergonomic/human centric typing.
And in my experience most people somehow think a UUID must be stored into the human friendly hex representation, dashes included. Wasting so much space in database, network, memory.
You can't guarantee that this will be globally unique.
Per Wikipedia, the probability to find a duplicate within 103 trillion version-4 UUIDs is one in a billion.
so-youre-saying-theres-a-chance.gif
A billion isn't that big a number, but 103 trillion is.
The probability of 1 trillion UUIDs having a collision is,
That number is roughly the approximation given in Wikipedia.I.e., at 1T UUIDs, it hasn't happened. For comparison, the odds of being struck by lighting (over a lifetime) is many orders of magnitude greater:
That aside, UUIDv4 is banned in many orgs because there have been several instances in the wild where the “random” number wasn’t nearly as random as advertised from some sources for a variety of reasons, leading to collisions. It is relatively easy to screw this up so many orgs don’t risk it.
The reality is that it is just like any other engineering situation. Sit down, write down your requirements, and see what, if anything, solves it.
Reading about the advantages of various formats is very helpful in helping you skip learning about certain things the hard way and use somebody else's experience of learning them the hard way instead. From that point of view I recommend at least glancing through them all. Sortability and time-based locality is one that you may not naturally think about, and if you need it, you will appreciate not learning that the hard way four years into a project after you threw that data away and then realizing you needed it. And some UUID formats actually managed to introduce small security issues into themselves (thinking MAC address leak from UUID v1 here), nice to avoid those too.
If you have a use case where there's an existing solution then, hey, great, go ahead and use it. Maybe if anyone ever needs that but in another language they can pull a library there too.
But if not, don't sweat it. The biggest use of UUIDs I personally have I specified as "just send me a unique string, use a UUID library of your choice if it makes you feel better". I think I've got a unique format per source of data in this system and it's fine. I don't have volume problems, it's tens of thousands of things per day. I don't have any need to sort on the UUID, they're not really the "identifier", they're just a unique token generated for a particular message by the originator of the message so we can detect duplicate arrivals downstream in a heterogenous system where I can't just defer that task to the queue itself since we have multiple. I don't even need them to be globally unique, I just need them unique within a rather small shard, and in principle I wouldn't even mind if they get repeated after a certain amount of time (though I left the system enforcing across all time anyhow for simplicity). In this particular case, I do indeed generate my own UUIDs for the stuff I'm originating by just grabbing some stuff from /dev/urandom and encoding it base64, with a size selected such that base64 doesn't end the encoding with ==. Even that's just for aesthetic's sake rather than any actual problem it would cause.
So it's got all of the above perks, but it also an actual UUID and fits in a Postgres UUID column.
It's very cool to be able to resolve a UUID to a particular database table and record with almost zero performance overhead (cached table lookup + indexed record select).
The goals are smallness, uniqueness, monotonicity, resistance to enumeration attacks, etc. Not randomness for randomness sake.
My UUIDv7+ can be consumed as a standard UUIDv7. It is not intended to be v8. A program can treat the last 16 bits as random noise if it wants.
It can have extra monotonicity data instead, per section 6.2 but ideally its random. Again, Not saying you can't do what you are doing, I just know per the conversations while the draft was gathering feedback, your type of change was intended to be done as uuidv8
> It can have extra monotonicity data instead
Well, which is it? These are incompatible requirements.
If I give you a standard UUIDv7 sample, it is impossible for you to interpret the last 62 bits. You cannot determine how they were generated. If I give you two samples with the same timestamp, you cannot say which was generated first. These bits are de facto uninterpretable, unlike e.g. the 48 MSB, which have clearly defined semantics.
So if we look at https://www.ietf.org/archive/id/draft-ietf-uuidrev-rfc4122bi...
For list item #3 it says "Random data for each new UUIDv7 generated for any remaining space." without the word "optional" and the bit layout diagram says `rand_b`
But when you read the description for `rand_b` it says: "The final 62 bits of pseudo-random data to provide uniqueness as per Section 6.8 and/or an optional counter to guarantee additional monotonicity as per Section 6.2."
Reading section 6.2 https://www.ietf.org/archive/id/draft-ietf-uuidrev-rfc4122bi..., it all involves incrementing counters, or other monotonic random data.
If you can guarantee that you custom uuidv7 is globally unique for 10000 values per second or more, I don't see why you can't do what you do and treat your custom data as random outside of your implementation.
I think part of this is my mistake, because I assumed you replaced most of the random data with information, but reading it now, I read that you replaced just the last 16 bits. Also since most people used random data for UUIDv1's remaining 48bits of `node` then your variation is no worse than UUIDv1 (or 6) while also being compatible with v7.
I think I just got too caught up on the the bit layout calling it `random` and misread your information. Sorry for the misunderstanding, and thanks for discussing it.
It says they could be pseudorandom and non-monotonic. Or it could be monotonic and non-random. These are completely disjoint cases! "X or not X" is tautological. And there is no way to determine which (e.g. there could be a flag that indicates this mode, but there is not).
To be clear, the standard should be amended to resolve this ambiguity. Say the last bits MAY be monotonic or MAY be pseudorandom. Or add a flag that indicates which.
As there is currently no standard way to interpret these bits, I feel perfectly justified in using the a few of the least significant ones to encode additional information.
But even if you follow the standard to a tee, you cannot infer anything about how the last 62 bits were assigned. That is my point!
There is already a UUIDv8. It's defined as vendor-specific UUID. https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u...
> Some example situations in which UUIDv8 usage could occur:
> An implementation would like to embed extra information within the UUID other than what is defined in this document.
Isn't that exactly what you are doing?
Compare that with otherwise nice ISO 8601 datetime format (e.g. 2023-06-28T21:47:59+00:00): it requires conversion for file systems that don't allow colons and plus signs.
Example:
I like how it folds in a time component but that it also doesn't reveal the time it was generated.Here's the snippet: https://gist.github.com/jszym/d3c7907b7b6e916f68205c99e5e489...
[1] - https://www.peakscale.com/strongly-typed-ids/
Details matter.
Personally, I rarely find I need ids to be sortable, so I just go with pure randomness.
I also like to split out a part of the random section into a tag that is easier for me to visually scan and match up ids in logs etc.
I call my ID format afids [0]
[0] https://github.com/aJanuary/afid
This property is useful for RDBMS writes, when the UUID is used as a primary key and this locality ensures that fewer slotted pages need to be modified to write the same amount of data.
Is there documentation covering the scenarios on how the order can become out of sync and what the odds are? There's a big difference between "almost" and "always" if we're talking about using this as a database PK.
Not in the context of an RDBMS, which use b+/b*-tree variants (or LSM sstables). Sequentially generated UUID's will end up near each other when sorted lexicographically, regardless of the fact that the sort order doesn't perfectly match the timestamp order.
So the order can become out of sync if multiple events happen in the same millisecond; or if your servers' clock error is greater than a millisecond (i.e. if you're an NTP user)
More than sufficient for things like ordering tweets. If you're ordering bank account transactions, well, you'd probably be using transactions in an ACID-compliant relational database.
https://joist-orm.io/docs/advanced/tagged-ids
We'd used `:` as our delimiter, but kinda regretting not using `_` because of the "double-click to copy/paste" aspect...
In theory it'd be really easy to get Joist to take "uuid columns in the db" and turn them into "typeids in the domain model", but probably not something that could be configured/done via userland atm...that'd be a good idea though.
The `t<X>` makes sense; we currently guess a tag name of "FooBarZaz" --> "fbz", but allow the user to override it, so you could hand-assign "t1", "t2", etc. as you added entities to the system.
Abbreviating/base36-ing even the auto-incremented numeric primary key to optimize lengths is neat; we haven't gotten to the size of ids where that is a concern, but it sounds like a luxurious problem to have! :-)
https://github.com/swyxio/brain/blob/master/R%20-%20Dev%20No...
I have one idea which is perhaps nerdy enough to make the list but I've never fully fleshed it out, it's that one can encode the nonnegative integers {0, 1, 2, ...} into the finite bitstrings {0, 1}* in a way which preserves ordering.
So if we use hexits for the encoding the idea would be that 0=0, 1=1, ... E=14, then
so the format is F, which is the overflow sigil, followed by a recursive representation of the length of the coming string, followed by a string of hexits that long.What if you need 16 hexits? That's where the recursion comes in,
Kind of goofy but would allow a bunch of things like "timestamp * 1024 + 10-bit machine ID" etc without worrying about the size of the numbers involvedNote that this RFC also supports lexicographic sorting for negative numbers using the 10k complement notation.
Let's say I have structs:
type User struct { ID TypeID }
type Post struct { ID TypeID }
How can I ensure the correct type is used in each of the structs?
[0] https://pkg.go.dev/encoding/json#Marshaler
[1] https://pkg.go.dev/encoding/json#Unmarshaler
If you don't need either of those, then UUIDv7 is the right choice.
This is more optimal for Postgres while making it slightly more difficult to interop between the db and the language (db driver needs to handle custom types, and you need to inject a custom type converter).
And while there are hacks you can do to make storing uuid-alikes as strings less terrible for db engines, if you want the best performance and smallest space consumption (compressed or not) make sure to use native ID types or convert to BINARY/numeric types.
1. I don't believe people actually hand type-in these values, so I'm not really concerned about the 'l' vs '1' issue. I do base 32 without `eiou` (vowels) to reduce the likelihood of words (profanity) sneaking in.
2. I add two base-32 characters as a checksum (salted of course). This is prevents having to go look at the datastore when the value is bogus either by accident or malice. I'm unsure why other implementations don't do this.
We had “analrita” as an autogenerated password that resulted in a complaint many years ago. Might consider adding ‘a’ as an excluded letter.
So adding an excluded letter is not easy.
For one application I used a base 58 encoded value. Part of it was a truncated hmac, which I used like check digits. This meant I could validate IDs before hitting the DB. As an attacker or script kiddie could otherwise try a resource exhaustion attack.
So in the age of public internet faceing APIs and app urls, I think built in optional check digit support is a good idea.
> either by accident or malice
1. if you don’t believe people hand type these then how else will they accidentally enter an invalid? I suppose copy/paste errors, or if a page renders it as uppercase, though you should just normalize the case if it’s base 32.
2. How does a 2 byte (non-cryptographically secure) checksum help in the case of malice?
We might add a warning in the future if you decode/encode something that is not v7, but if it suits your use-case to encode UUIDv4 in this way, go for it. Just keep in mind that you'll lose the locality property.