Hacker News Reader

If you care about compressability, you can simply use a different way of generating UUIDs, instead of switching to another type. For example initializing a 128-bit counter when starting the process and incrementing it for each number generated. This should compress almost as well as sequential integers, while still being collision resistant without coordination or persistent state.

Yep. Different UUIDs will have different characteristics when compressed. Still, if you can afford to just have '1, 2, 3, ..' as IDs that's hard to beat.

I have never seen this strategy described. Is there any literature on it? Cause it does seem to be that this would be as good as the other algorithms for generating UUIDs, but faster and with the benefit of compression. It would make resulting UUIDs easier to guess, but that has never been a design goal of UUIDs anyway.

This method doesn’t scale in a distributed system. Two machines running this algorithm will generate conflicts which violates the “universal” part of UUID which means you can run the same algorithm anywhere and you won’t get a conflict. So if you want to make this unique, you have to make a remote query to generate the UID uniquely. Examples of this are Snowflake. Also Sled (the database written in Rust) does a variant of this but it’s not a distributed system per se (ie generates unique identifiers globally on a single machine across process restarts which is useful for transaction IDs).

The current SOTA as I understand it is to have the timestamp be the most significant digits and a random value in the least (ULID, UUIDv7 etc). That way you get temporal locality for the UUID which is typically an indexed column where that helps for storage a bit (not so much for lookups because it’s still a random value relative to other concurrently accessed UIDs being input into the system)

Although CodesInChaos didn't specify the initialization, I assume the intent is that each machine would randomly initialize their counter, in order to prevent collisions. While collisions are possible in any scheme without coordination, I suspect that 128 bits is enough entropy for this to be extremely improbable.

Yup, and I am curious about the math on collisions with this scheme. Cause 128 bits is a lot of entropy, and I would expect this scheme to have similar collision resistance of "it never happens with good RNG" as regular uuids, but a proof would be nice.

Yeah, intuitively I assume that the gaps between any two UUID guesses will be sufficiently large such that you can increment a lot without overlap but... until someone shows me the math, I don't love the idea.

I meant using a random initial value. This will make collisions less likely than v4 UUIDs (because the quadratic scaling of the birthday problem only applies to counter initialization), however once you get one collision you get many.

That’s an interesting approach, but what’s the use case you’re thinking of? There’s no correlation of UUIDs across nodes like there is with something like UUIDv7 or ULIDs.

I guess you’ll still have batches of locality depending on the uptime of the server which might be useful and generation would of course be significantly faster although I doubt many applications are really bottlenecks by UUID generation speed.

Within a node it would improve compression, so in theory your overall system would benefit. This diminishes as you increase the number of nodes. TBH if you have a very small number of nodes I think just having a synchronized counter is fine. You can make extremely fast counters if you allow for gaps.

One idea is just to use fewer random bits in peerIDs. Yjs (https://docs.yjs.dev/) gets away with just 32 random bits. If you compromise and use 64 random bits, then even a very popular doc with 1 million lifetime peerIDs will have a < 10^-7 lifetime probability of collision.

> how expensive UUIDs are

I don't quite get it. The normal string encoding of a UUID (d92b13b6-6780-4b98-82cc-d469dcdd42ab) clearly requires more bytes (36B) than the actual UUID itself (16B). The string encoding is for showing to users, it's not what you store in your DB, or your CRDT -- for that, you use the actual 16-byte value.

> Not only will your UUIDs take up 2x the space of a 64bit integer, they'll compress horribly by comparison. Integer compression is so good these days you can compress integers such that they basically end up taking up ~1/2 a byte instead of 8. Doing that with UUID v4s is fundamentally not going to work.

Yes, UUIDs are 128 bits, and 64 bit integers are 64 bits, but in both cases you're storing them as raw bytes -- or, maybe, integers, sure. Whatever compression works on your int64s will work just as well on your UUID int128s.

I assume they are referring specifically to a monotonic integer sequence. This will compress and index very nicely (low entropy) whereas v4 UUIDs are random and will not (high entropy). This is the same principle that explains why gzip works well on text but not photos.

Usually you use UUIDs when you don't want your IDs to be guessable.

That is definitely not why the vast, vast majority of people choose UUIDs, though it is a nice property of them. The reason people choose them is because you can generate them without any synchronization in a distributed system.

To reply to your initial point:

> Whatever compression works on your int64s will work just as well on your UUID int128s.

This is not the case. Compressing non-random 64bit values (such as the ones in the article - they are sequential) is going to be way more effective than compressing UUIDs. UUIDs do not compress, you'll likely end up with a larger output than the input.

What the article does, essentially, is a dictionary encoding pass. The duplicate, expensive UUIDs are mapped to small, sequential integers.

I explained elsewhere that you can turn nearly arbitrary numbers of sequential integers into a few bits each.

This assumes that you're compressing IDs in batches. I'm sure that's a common situation, but I'm not sure why it's assumed to be the _default_ situation, nor am I sure why this is assumed to be the primary metric for IDs.

> I'm sure that's a common situation

It's the situation we're presented with in the blog post. It's not an uncommon situation given that UUIDs are used in databases and, for many databases, compression is done at a block level.

> nor am I sure why this is assumed to be the primary metric for IDs.

It isn't.

> Whatever compression works on your int64s will work just as well on your UUID int128s.

That's not true in general; it depends on how the ints are distributed. UUIDs are, by design, distributed in a way that's pretty much maximally unfriendly to compression

Thank you so much! I spent a long time on these diagrams haha.

> Integer compression is so good these days you can compress integers such that they basically end up taking up ~1/2 a byte instead of 8

This needs an explanation.

Well if your integers are sequential you can encode huge numbers of them using diff + RLE in just a few bytes, likely far fewer than 1/2 a byte on average, for the right dataset (in theory you can store 1,2,3,4,5...10_000 in 2 bytes).

But for other integer datasets there's FastPFOR

https://github.com/lemire/FastPFor

The linked papers there will talk about techniques that can be used to store multiple 32bit integers into a single byte, etc. Integer compression is pretty powerful if your data isn't random. The thing with UUIDs is that your data is pretty random - even a UUIDv7 contains a significant amount of random data.

Also had great success with Roaring Bitmaps, a bit further on the compression/ease of manipulation axis.

Edit: I see you're already linking to Daniel Lemire's github, so I guess you're familiar with them, just mentioning them, since it's in a comment thread like this one that I discovered them.