Hacker News Reader

Comment by qalmakka | Hacker News Reader

Isn't this easily solved by supporting 128 bit keys and using UUIDs as intended, i.e. as integers and not in their string serialization? This is as nonsensical as storing IPv4 as strings instead of 32 bit integers.

View on HN

It should be noted that some database providers already provide a UUID data type which is a 128bit integer.

https://www.postgresql.org/docs/14/datatype-uuid.html

Length isn't the primary issue. Locality is.

UUIDs are generally generated randomly. This results in terrible insert performance into B+tree-based indexes, and terrible (= no) lookup locality with basically any database. In a large table, successive entries ends up in separate disk pages.

Even with time-based UUIDs, the time fields are ordered backward, which produces the same issue.

One way to fix this (beside the methods outlined in the article) is to create time-based UUIDs with fields sorted the other way around. Or reverse the time fields during indexing (slower, but still not as slow as an unnecessary disk read!).

Firestore has exactly the opposite problem - indexed sequential values put pressure on the "last tablet" and require the same tablet to repeatedly split. This becomes the limiting factor on insert volume. Random generated keys are better, because they spread inserts across multiple tablets (ie servers).

I don't know for certain, but I suspect DynamoDB and most other databases that can trace their origins to the bigtable whitepaper have similar behavior.

Indeed, traditional rdbms are generally optimized for patterns with high locality. High locality patterns with NoSQL and NewSQL style dbs often end up causing one node in the system to receive disproportionately high load that defeats attempts to spread operations across the cluster.

DynamoDB runs the partition key through a hash function, so sequential values end up being evenly distributed across partitions.

If so, how does it iterate in key order?

I should clarify - the problem with Firestore is the index tablets. The indexes inherently need to be inorder or you can't perform ordered queries.

It can't. You can only perform range queries and the like on "sort keys." All sort keys are on the same partition, so has limits on storage size and throughput.

Partitioning is very explicit in DynamoDB, for better or for worse. Harder to shoot yourself in the foot, but also limits what you can do.

I can't say I've had much issue with this in postgres, but even still, this is easily worked around by having a pkey/cluster key of a monotomically increasing int--which is useful for other things such as data migrations, as you can pick defined start and end targets without worrying about new things being inserted in between.

Pg does not cluster, so the only impact of a uuid is that you’re inserting in a random location location of the index, which is not great but not the end of the world (probably).

InnoDB clusters on the PK by default, so when you're inserting a UUID you're not only inserting in the middle of the index (on average) you're also inserting in the middle of the table.

And I don't know how much the on-disk storage has been optimised for this sort of things, but if the answer is "not" and sparse pages are not really a thing, you might need to rewrite half the table in order to do so.

It's going to depend on the database. This article is primarily focused on InnoDB and goes over the read/write locality issues with a uuid.

That isn't always going to matter (or can be a very good thing). For a KV store like dynamodb a uuid is a great key because it'll distribute nicely across your shards.

It also depends a lot on your query patterns. If you have a uuid primary key but you're partitioning by some other value you may end up significantly reducing the number of pages you have to look through.

> Or reverse the time fields during indexing (slower, but still not as slow as an unnecessary disk read!).

When you're IO bound, I'm not sure it actually is slower in practice.

Depending on caching strategy, using random UUIDs also decreases the maximum working set size before you become I/O bound by a huge factor. Postgres e.g. relies heavily on the O/S block cache and is subject to this.

> using random UUIDs

I wasn't discussing using random UUIDs.

there is new uuid versions (draft) that solves the locality problem: https://datatracker.ietf.org/doc/html/draft-peabody-dispatch... (one of the new ones, cant remember which exactly)

That helps with storage, but still is larger than a bigint, and doesn't help with the random distribution of data. I believe newer versions of MySQL have a data type for this.

Well, you probably shouldn't cluster on a UUID, but it's not really a great idea to blindly cluster on a sequential id, either. You should cluster based on how you query the data to minimize I/O.

If you use a type1 UUID, you shouldn't have quite so random distribution, particularly if there's only a single machine generating the UUIDs (which admittedly, kind of misses the point, but alas is done all the time).

MySQL doesn't have a UUID type, nor 128-bit int type. But MySQL 8 does provide functions UUID_TO_BIN and BIN_TO_UUID, which make it trivial to convert between the human-readable string representation of a UUID and the more efficient BINARY(16) representation.

MariaDB now has a native UUID column type as of MariaDB 10.7. This is brand new -- 10.7 had its RC release in Nov, not GA yet but very soon I'd imagine.

That's only part of it, the major problem with classic UUIDs are that writes occur randomly across the entire keyspace. Whether it's represented as a string or in binary, ordering does not change, and so the underlying indexing method must cope with these random orderings at insertion time.

At least btrees perform much worse with random insertions. I don't know how much impact it has on LSM

LSMs and fractal trees handle random inserts much better. But you still lose locality of lookups: items generated near each other time-wise are not correlated on disk.

I'm kind of shocked MySQL doesn't do this?

Experience has taught me to never be surprised when you learn that MySQL does something incorrectly. Having used it since v3.3 it's not unusual.

They do test a binary(16) field which is basically what you're talking about (and you could use a binary(32) for a 128-bit UUID).

16 bytes is 128 bits. Why would you use 32?

In terms of space usage and its impact on the buffer pool, storing as 128-bit integers (if your DBMS supports it, which MySQL does not) is essentially equivalent to the bin16 case in the first "UUID insertion rates" graph. Performance still falls off a cliff, just a little bit later. As the author says, "The use of a smaller representation for the UUID values just allows more rows to fit in the buffer pool but in the long run, it doesn't really help the performance, as the random insertion order dominates."

If you look at the fastest approach the author tried in the second "UUID insertion rate" graph, it actually stores a modified UUID in a 36-character string. There is a missed optimization to store the modified UUID as 16 bytes, rather than 36, but imposing some order on the keys is the dominant improvement.

You know what's nonsensical? Assuming one rule of thumb applies everywhere. I will stand by that rule of thumb until I'm cold and in the ground.

Not to mention the string serialization is also ugly...

If it's ever being turned into a string and stored or transmitted it's always better to use a standard base64 encode to keep the string to 22 chars instead of the standard 36/38 chars.

You can also use base85 and go to 20, but you get into some funky chars there.

Reply on news.ycombinator.com