Hacker News Reader

Comment by colanderman | Hacker News Reader

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

View on HN

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)

Reply on news.ycombinator.com