Comment by willvarfar | Hacker News Reader

Comment by willvarfar | Hacker News Reader

Parent Full thread

The main driver behind lexically sortable identifiers is that you generally insert into databases in time order so if your ids are sorted by time then you are appending to the end of the table. If, on the other hand, your ids are random (e.g. the prevalent UUIDv4) then your database is spending all it's time shuffling everything around to insert your new rows in the middle of everything.

Once you have time-based identifiers as primary keys you can do fancy things like using some id you know was generated at time x as a where clause on some other table to dramatically cut down the search space. This kind of dirty trick can really improve performance sometimes when it really matters.

However, the main contender for lexically sorted IDs is ... UUIDs! The new UUID specs have ULID versions of UUIDs.

The new UUID spec includes lexically sortable variants, of which UUIDv7 is gaining widespread support. https://datatracker.ietf.org/doc/draft-ietf-uuidrev-rfc4122b...

That spec lists 16 prior lexically-sortable identifiers, and has good motivation for adding time sorting to the UUID standard.

Two things I particularly like about the UUIDv7 standard is that it is easy to swap into existing codebases that are using UUIDv4, and that it is easy to extract the timestamp part in systems that don't know about it and are treating it as a string e.g. in lots of databases you can do some sql like TIMESTAMP_MILLIS(CAST(CONCAT("0x", LEFT(REPLACE(id, '-', ''), 12)) AS INT64)). This is a massive advantage over systems that use non-hex encodings.

So these days, use UUIDv7 if you want to generate your ID outside of a database and the time the id was created is not a secret; else use UUIDv4. Your database will thank you.

> your database is spending all it's time shuffling everything around to insert your new rows in the middle of everything

Is it? The order of data on disk tends to be the insertion order. What might get shuffled around is the index for the primary key, but indexes can handle that quite well.

And the answer is "depends on the database tech".

Here are some nice benchmarks: https://www.toomanyafterthoughts.com/uuids-are-bad-for-datab...

I learned the lexically-sortable-id trick from wizened DBAs in the 90s. It's an old trick. I've applied it myself to speed things up and have used both the ULID types described in the article and UUIDv7 etc.

I even advocate using UUID7 on BigQuery where there are no indexes. Having sortable keys is nice even if it doesn't add speed.

You should definitely bench your storage to confirm that it likes hotspots (some don't!)

You should, but B-tree is the most common data structure used for database indexes, and sequential order performs better than random order for index keys.

You often can't bottleneck the entire workload on the capacity of one cluster node and one storage device.

I can't really understand what you said, could you elaborate? :)

If one machine can only handle a hundred transactions per second, and you might ever receive more than that, you have to spread the work across several machines, probably by assigning primary keys that aren't (mostly) sequential.

usually in sharding schemes its a few bits of a hash of the id that are used to determine shard; the system or library you are using will take care of this transparently for you.

You don't need a total order for the locality properties. E.g. a 32bit ms timestamp that overflows every ~50 days + 96bit of entropy will give you the same locality with a much lower collision probability.

That being said, a lot of index types don't care about this kind of locality and might even benefit from higher entropy (randomized algorithms).

Depending on your read and write patterns, overflowing even every few days might be appropriate, and also obfuscate the creation time [1] more.

[1] https://news.ycombinator.com/item?id=40272446

Great point, using a u16 is probably the best choice then. As it give locality within 65.53600 seconds (roughly a minute) without exposing sensitive timing information, and should cover most real world write scenarios.

A small additional improvement might be to also create a random 16bit salt at startup and then xor the timestamp with that, to leak even less information. That way entries will still have locality without leaking ms timestamp info.

at this point, why not use the creation date (with all that you describe on top) as the primary component of the primary key?

you only got 128bit, you want most of that to be randomnes, otherwise collisions are much more likely

But if you for instance use MS SQL and the uniqueidentifier type, sorted UUIDv7 is not sorted im the database because MS SQL swapsnthe bytes around. So ULID (stored as binary(16)) is an advantage in that case to avoid making that mistake.

I really like that ULID looks differentt from UUIDv4. UUIDv7 is something sorted that on the surface looks like it will be random and is mixed with random IDs etc..

It depends per storage system. I think we evaluated this on Postgres b-tree and weren’t super jazzed about it. Some storage systems don’t like hotspots. They can write two far-apart keys in parallel, but adjacent keys need to be serialized. Sometimes this happens with sharding systems.

What drives me nuts is people storing uuids in databases as hex strings. They're bytes, and if you do it right, even the type 1's are lexigraphically sortable.

Hex strings may require more storage, but they remove the need to convert back and forth and make it easier to manually query the database when debugging. The best type is your database's uuid type if it has one.

There’s no reason to use hex though. Base32/36/62/64 should be considered.

there's no reason to not use hex, though.

In my post this is replying to, I mentioned "in lots of databases you can do some sql like TIMESTAMP_MILLIS(CAST(CONCAT("0x", LEFT(REPLACE(id, '-', ''), 12)) AS INT64)). This is a massive advantage over systems that use non-hex encodings."

I've had struggles with binary and base62 encodings and things and just want everyone to use hex.

Typical databases compress rows or columns anyway these days; or if they don't, then the storage does. So often the question is entropy not character count. For example storage I work with these days takes as an identical number of bytes to store a hex string as to store the same id as a byte array.

> Typical databases compress rows or columns anyway these days; or if they don't, then the storage does. So often the question is entropy not character count. For example storage I work with these days takes as an identical number of bytes to store a hex string as to store the same id as a byte array.mo

Storage tends to be cheap, so it's less about that, and more about memory consumption and index efficiency. The cost of transforming back to and from binary is also pretty trivial on modern systems.

Stuff gets "converted" between you and the database anyway. If you really want to see it as though they were strings all the time, you can always make a view.

Reply on news.ycombinator.com