Making CRDTs 98% More Efficient

Re:Making CRDTs 98% More Efficient by jahewson on Tuesday October 17, 2023 @03:04PM (#37920012)

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.

[ Parent | on HN ]

Re:Making CRDTs 98% More Efficient by kiitos on Tuesday October 17, 2023 @03:31PM (#37920391)

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

[ Parent | on HN ]

Re:Making CRDTs 98% More Efficient by insanitybit on Tuesday October 17, 2023 @08:01PM (#37923209)

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.

[ Parent | on HN ]

Re:Making CRDTs 98% More Efficient by kiitos on Wednesday October 18, 2023 @08:44PM (#37936812)

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.

[ Parent | on HN ]

Re:Making CRDTs 98% More Efficient by insanitybit on Thursday October 19, 2023 @12:31AM (#37938427)

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

[ Parent | on HN ]