Hacker News Reader

Comment by rockwotj | Hacker News Reader

I find it interesting that it’s quoted random IDs are bad for performance, because it’s actually better for distributed storage systems because you don’t hotspot on a single node. For example see: https://stackoverflow.com/a/53901549 and https://medium.com/google-cloud/cloud-spanner-choosing-the-r...

View on HN

They can be bad for performance. It all depends on your access patterns. A common caching pattern is called "temporal locality" which means that theres a high likelihood that data created at the same time will be accessed at the same time. Therefore, if these pieces of information are on the same machine, they can be queried / returned much faster than if they were both on separate machines. This is doubly true if theres a data dependency between them. E.g. SELECT x + y or SELECT x WHERE y = 'foo'.

Yes but if that machine with sequential data receives 100x the traffic of other machines, it can be worse than splitting this traffic evenly across all available machines.

If your database simply shards keys sequentially, it's going to get hotspots in a lot of use cases, like plain old integer keys and timestamps, not just UUIDv7. In that case it would be fair to say that your database is doing it wrong.

Fortunately, there's no rule that says you should shard your keys using the sequential part up front.

One of the rules for generating randomness from environmental sources is to throw away the high bits and only use the low bits. Distributed databases should do the same if they want a good distribution.

As I understood it, a big part of the premise of the post was that they see sequential storage (either in db or cache layer) as desirable

What distributed databases shard on the low bits? How do they do something like a range query?

The closest I’ve ever heard of is sharding based on a hash (e.g. CockroachDB can do this on request[1]) but most distributed databases with strong consistency (Spanner descendants in particular) default to “doing it wrong”.

[1]: https://www.cockroachlabs.com/docs/stable/hash-sharded-index...

It depends if you have a request covers a lot of sequential data, or if you have a lot of requests of sequential data.

Correct, it speeds up latency in best case scenario, and falls over in worst case scenario. Randomly sharded keys give a more consistent performance.

You're painting with way too broad of a brush. It is not always better and not always worse. E.g. "give me a list of users who made two posts where both posts were created within 1 second of each other" This query would likely blow up on a system which has all the data completely randomly sharded (because you'd have to aggregate all the data centrally, unless you had a complicated shuffle setup (which most dbs dont)) whereas would work fine on a system which has posts sharded by time.

If you're working on a multi-user system, particularly one with hundreds of requests per second, there is no locality of ids. Two of my actions are separated by a sea of actions by other users.

We solved that with UUIDS and updated_at and created_at columns. The latter the default sort in all views and queries. So the btree/indexing issues were hardly an issue. Whenever you fetch a set of rows, they will be bounded by these timestamps.

We even sharded on these columns, because of this (our business case made it so that hardly ever did people need data over multiple months)

But we never encountered distribution issues. I don't think the locality issue will be solved, as postgres doesn't consider other columns when distributing data, only the primary key IIRC. I don't know why we never saw this, though.

UUIDv7: Timestamp up front, random in the back.

Truly, the mullet of unique identifiers.

I know HN doesn't like jokes, but this is really funny. And the subcomment about mullets too.

(for folks who don't get it, mullets are a 1980s haircut (think MacGyver) with a short front but a long tail in the back. A funny description of them is "business in the front, party in the back")

Sitting on a tram in Sheffield, early noughties, a chap with a magnificent unreconstructed ROCK mullet gets off. I see two women chatting on the street, they are stunned into slack-jawed amazement as he struts past -- one of the women makes a scissor-snipping hand gesture behind him as he passes, the whole tram erupts in laughter.

It Depends(tm).

If you're using a system which is built for distribution, random is great.

When you're leaning on a Postgres database which has powered your startup through scaling but expects right-leaning btree indexes, it's a bad time.

Rearchitecting to use a new data store is ideal, but often impractical as an immediate step. UUIDv7 is a great increment walking that road via sharding etc.

In all the distributed systems I’ve built I hashed the keys to ensure good distribution. A nice thing of ordered keys is you can use part of the ordering to distribute keys with a tunable amount of key locality in each node for efficiency.

Depends how you query it. In a lot of systems, recently added data is also the most queried data or data typically gets pulled out sorted by time. Having that data on disk in more or less the order it is going to be queried makes sorting it a bit easier. Even in a sharded system, each of the shards would have less work to do for sorting. Of course a lot of these systems would have an append only write model which would effectively sort things by time anyway, even with completely random ids.

Somebody posted an interesting article for the instagram ids, which do something similar. They use 41 bits for a time from a custom epoch followed two more groups of bits for a shard id and a sequential number. Each shard has an incrementing sequence for the sequential bit, which guarantees that things on a shard are sorted by time.

This UUIDv7 is slightly weaker than that but sorting things published in the same millisecond is mostly going to be very light work. The lack of a dedicated sharding group of bits is not that important as you could just take the n least significant bits at the end for that without too much effort. Those are random so you end up with nice consistent hashing. Having 48 instead of 41 bits for the time means we won't run out of time any time soon (nearly 9K years vs. 70 years).

An explicit shard id can ensure all related data across all tables can be on the same shard. Helpful for SQL JOIN operations.

Picking the N least significant bits only a single table has good distribution and sort qualities, no cross-table properties.

Depends on the use case. If, for example, you store things on disk ordered by these IDs, and access patterns to your dataset are related to time (e.g. more recently created data is accessed more frequently), it will help a lot to have this data ordered by time.

This is especially useful when your underlying database stores data in large "chunks", such as LSM-trees you find with e.g. rocksdb.

It's great for performance, up until you reach the point where a single device becomes a bottleneck, at which point it's terrible for performance.

As a sibling comment says, you ideally want to shard on some other key to get "just enough" distribution that all your machines/disks have work to do, but you are still only hitting a limited number of hot sectors on each disk that can be effectively cached. But that requires active monitoring and rebalancing of your data as it grows. Totally random keys are a safe default that will scale with any kind of data distribution and access patterns.

It can be bad for performance due to how b-trees work in databases, and more pronounced when you have a clustered index.

It's bad for performance if you frequently access large consecutive sets of records.

UUIDs are good for data where I want either lots of different users being able to insert without collision, or lots of users who I want to keep their peepers off of other user's metadata (eg, how many X they add to the system per day).

In both cases I'm melding highly disjointed data into a single schema. There are no large consecutive sets of records.

If you're using UUIDs, there's probably a reason. And that reason invalidates the justifications for not using them.

> If you're using UUIDs, there's probably a reason.

Not really; think of how many architectural decisions are made purely based on imaginary scaling problems, or what the latest blog said.

I would wager that if you polled 100 backend devs, very few of them could correctly articulate the pros and cons of a randomized primary key.

Agree, but the solution is easy peasy with a simple hash function.

(Or just reverse the bits, take the last n, etc)

As far as I understand, you want to have a random shard position, but once you have found a shard you want that index operation to be cache friendly. When choosing a shard, you can always use the last N bits or use some consistent hashing strategy[1]

[1]: https://en.m.wikipedia.org/wiki/Consistent_hashing

There are many other options that usually scale better than random distribution. For example distribution by user or tenant id.

They likely mean it’s good for latency and not necessarily for throughput.

I still think that graph databases are way better for this sort of thing.

They later note most of this traffic is going to a single postgres instance. Having all the keys go to the same range probably helps throughput because they can do a better job of grouping fsync. But that probably depends on the type of drives they are using (even fast NVMe benefit from locality).

Reply on news.ycombinator.com