5 ms·
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 a
by willvarfar 2y ago
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-rfc4122bis/ 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.
- dagss 2y agoBut 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..
- cbsmith 2y agoWhat 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.
- Kwpolska 2y agoHex 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.
- zarzavat 2y agoThere’s no reason to use hex though. Base32/36/62/64 should be considered.
- willvarfar 2y agothere'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.
- cbsmith 2y ago> 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.
- cbsmith 2y agoStuff 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.
- Kwpolska 2y ago> 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.
- willvarfar 2y agoAnd the answer is "depends on the database tech". Here are some nice benchmarks: https://www.toomanyafterthoughts.com/uuids-are-bad-for-database-index-performance-uuid7/ 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.
- erik_seaberg 2y agoYou should definitely bench your storage to confirm that it likes hotspots (some don't!)
- kreetx 2y agoYou 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.
- erik_seaberg 2y agoYou often can't bottleneck the entire workload on the capacity of one cluster node and one storage device.
- kreetx 2y agoI can't really understand what you said, could you elaborate? :)
- j-pb 2y agoYou 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).
- s4i 2y agoDepending 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 https://news.ycombinator.com/item?id=40272446
- j-pb 2y agoGreat 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.
- j-pb 2y agoA 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.
- jitl 2y agoIt 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.
- deleted 2y ago[deleted]