4 ms·

> 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) t

by kiitos 3y ago

> 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.

jahewson 3y ago
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.
- kiitos 3y ago
  Usually you use UUIDs when you don't want your IDs to be guessable.
  - insanitybit 3y ago
    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.
    - kiitos 3y ago
      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.
      - insanitybit 3y ago
        > 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.
gipp 3y ago
> 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
deleted 3y ago
[deleted]

by kiitos 3y ago

jahewson 3y ago

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.

kiitos 3y ago
Usually you use UUIDs when you don't want your IDs to be guessable.
- insanitybit 3y ago
  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.
  - kiitos 3y ago
    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.
    - insanitybit 3y ago
      > 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.

gipp 3y ago

> 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

deleted 3y ago

[deleted]