4 ms·

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 hotspo

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 https://stackoverflow.com/a/53901549 and https://medium.com/google-cloud/cloud-spanner-choosing-the-right-primary-keys-cd2a47c7b52d https://medium.com/google-cloud/cloud-spanner-choosing-the-r...

EGreg 3y ago
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.
- rockwotj 3y ago
  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).
fnordpiglet 3y ago
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.
akira2501 3y ago
UUIDv7: Timestamp up front, random in the back.
- labster 3y ago
  Truly, the mullet of unique identifiers.
- wenc 3y ago
  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")
  - jjgreen 3y ago
    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.
chacham15 3y ago
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'.
- stepanhruda 3y ago
  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.
  - kijin 3y ago
    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.
    - johncolanduoni 3y ago
      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-indexes https://www.cockroachlabs.com/docs/stable/hash-sharded-index...
    - stepanhruda 3y ago
      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
moralestapia 3y ago
Agree, but the solution is easy peasy with a simple hash function. (Or just reverse the bits, take the last n, etc)
dheera 3y ago
It's bad for performance if you frequently access large consecutive sets of records.
- hinkley 3y ago
  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.
  - sgarland 3y ago
    > 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.
stingraycharles 3y ago
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.
sroussey 3y ago
It can be bad for performance due to how b-trees work in databases, and more pronounced when you have a clustered index.
sj26 3y ago
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.
jillesvangurp 3y ago
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).
- gregw2 3y ago
  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.
conradludgate 3y ago
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 https://en.m.wikipedia.org/wiki/Consistent_hashing
andix 3y ago
There are many other options that usually scale better than random distribution. For example distribution by user or tenant id.
tveita 3y ago
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.

EGreg 3y ago

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.

rockwotj 3y ago
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).

fnordpiglet 3y ago

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.

akira2501 3y ago

UUIDv7: Timestamp up front, random in the back.

labster 3y ago
Truly, the mullet of unique identifiers.
wenc 3y ago
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")
- jjgreen 3y ago
  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.

chacham15 3y ago

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'.

stepanhruda 3y ago
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.
- kijin 3y ago
  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.
  - johncolanduoni 3y ago
    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-indexes https://www.cockroachlabs.com/docs/stable/hash-sharded-index...
  - stepanhruda 3y ago
    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

moralestapia 3y ago

Agree, but the solution is easy peasy with a simple hash function. (Or just reverse the bits, take the last n, etc)

dheera 3y ago

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

hinkley 3y ago
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.
- sgarland 3y ago
  > 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.

stingraycharles 3y ago

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.

sroussey 3y ago

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

sj26 3y ago

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.

jillesvangurp 3y ago

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

gregw2 3y ago
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.

conradludgate 3y ago

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 https://en.m.wikipedia.org/wiki/Consistent_hashing

andix 3y ago

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

tveita 3y ago

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.