5 ms·

One of the post's points is that UUIDs will scatter your writes across the database, and that for this reason you want a (more or less) sequential key as your p

One of the post's points is that UUIDs will scatter your writes across the database, and that for this reason you want a (more or less) sequential key as your primary key. This crucially depends on both your database technology and your query patterns. In a single-node database or even a manually-sharded one, this post's advice is good (For Friendfeed, we used a variation of the "Integers Internal, UUIDs External" strategy on sharded mysql: https://backchannel.org/blog/friendfeed-schemaless-mysql https://backchannel.org/blog/friendfeed-schemaless-mysql). But in a distributed database like CockroachDB (Disclosure: I'm the co-founder and CTO of Cockroach Labs) or Google Cloud Spanner, it's usually better to get the random scattering of a UUID primary key, because that spreads the workload across all the nodes in the cluster. Sometimes query patterns benefit enough from an ordered PK to overcome this advantage, but usually it's better to use randomly-distributed PKs by default. For CockroachDB, my general recommendation for schema design would be to use UUIDs as the primary keys of tables that make up the top level of an interleaved table hierarchy, and SERIAL keys for tables that are interleaved into another. (Google's recommendations for Spanner are similar: https://cloud.google.com/spanner/docs/schema-design#choosing_a_primary_key https://cloud.google.com/spanner/docs/schema-design#choosing...)

Twirrim 9y ago
With DynamoDB you also want to be scattering your reads. As you scale up the table (either data or read/writes) it will be partitioned and your total read/write capacity is split evenly amongst the partitions. If you don't have even distribution of requests across the table, you're going to keep running in to throttle limits.
- manigandham 9y ago
  dynamo and cassandra use consistent hashing of the primary key, ordered numbers are already hashed randomly.
jrs235 9y ago
>One of the post's points is that UUIDs will scatter your writes across the database And will wreak havoc on any indexes it is included in [if you do a lot of writes and don't have sufficient padding]... page split city!
- UK-AL 9y ago
  Some UUID and Guids can be made sequential.
  - braveo 9y ago
    I can't speak for other databases, but SQL Server's NEWSEQUENTIALID is only guaranteed until the server reboots. At which point the next UUID integer value can be less than the previous, at which point you're back to splitting pages.
    - UK-AL 9y ago
      Normally your application would generate them not the dB
      - braveo 9y ago
        I didn't provide enough context. There's nothing wrong with using UUID's, but I would avoid them for clustered indexes. And I would say typically you wouldn't care about whether or not UUID's were sequential unless you WERE putting them into a clustered index. I'm sure there are use cases where you would worry about the sequential nature for reasons not related to clustered indexes, but in general what I said is true.
        UK-AL 9y ago
        You application generates sequential guids before placing in a database with a clustered index. Thus solving the issue with NEWSEQUENTIALID and clustered index issue.
        lazulicurio 9y ago
        Just for other people reading this thread, as I've posted before[1], a word of caution if you're trying to generate sequential UUIDs client-side for SQL server: SQL server does not sort UUIDs in the order you'd expect. The bytes are ordered 10-11-12-13-14-15-8-9-7-6-5-4-3-2-1-0. [1] https://news.ycombinator.com/item?id=13120522 https://news.ycombinator.com/item?id=13120522
tkahnoski 9y ago
I've been on the wrong-side of this unfortunately. Rather than implementing a sane archive delete strategy, data was left there to collect so there was pretty much no hope for a particular join not to generate page miss. Eventually we settled on a NoSQL DB with denormalized data in partitions. A few years later we realized we made a poor choice in having too few and too big of partitions, and basically just repeated the mistake with a different database technology (made even worse because now the things on disk were even bigger that we needed to fetch!)
malkia 9y ago
Also Cloud Bigtable - https://cloud.google.com/bigtable/docs/schema-design#types_of_row_keys https://cloud.google.com/bigtable/docs/schema-design#types_o...
sroussey 9y ago
Sometimes, you don't want a workload spread across all the nodes of a cluster.
braveo 9y ago
The one point I went looking for and didn't see is that UUID's make for very poor clustered indexes. SQL Server tried to mitigate this with the 'NEWSEQUENTIALID', but it essentially 'resets' when the server is rebooted. If your data is small enough that it doesn't matter then fine, but in general UUID's are better as a surrogate key than as a primary key.
- jrochkind1 9y ago
  Yes, that's in the OP, exactly what you said.
  - braveo 9y ago
    It was, I meant I went looking for it in the article and didn't see it :)
- UK-AL 9y ago
  Very few people generate the guids database side. They normally generate them before they even insert it into the database.
lugg 9y ago
Thanks for this reclarification, lead me to do a little searching. https://mariadb.com/kb/en/mariadb/guiduuid-performance/ https://mariadb.com/kb/en/mariadb/guiduuid-performance/ Has some helpful tidbits, like how pks get implicit copies to all other indexes making uuids quite expensive memory wise if you have a lot of referencing tables and a lot of indexes. One of the recommendations I'm not sure on is to compress and reorder the uuid for time sequence. I get the compression part (remove dashes, convert to bin with unhex), but I'm concerned reordering the uuid so the time sections are together (to order your writes better) might actually decrease entropy? and make collisions likely. Does anyone here know much about uuid generation and whether the time sections reordered would make a difference across a table of around 100m~? I think I might just go with internal incremental and external uuid. Solves the knowing key before insert problem with little downsides. The time swap thing is now implemented in mysql8 (broken link in the mariadb post) https://dev.mysql.com/doc/refman/8.0/en/miscellaneous-functions.html#function_uuid-to-bin https://dev.mysql.com/doc/refman/8.0/en/miscellaneous-functi...
- meritt 9y ago
  > might actually decrease entropy? and make collisions likely. It's rearranging in a deterministic manner, there's no loss of information, it's just a permutation. There is no impact to entropy nor the likelihood of a collision.
- hodgesrm 9y ago
  The UUID time-swapping trick seems like a bad idea outside of special cases. Overloading the UUID in this way makes you dependent on generating UUIDs correctly so that the ordering works. You can get insertion ordering by using an auto-increment integer primary key which also results in a relatively short key for secondary indexes. This is much easier to understand and cannot be messed up by application errors.
- caleblloyd 9y ago
  The probability of a collision can be estimated using the "Birthday Paradox" equation: http://planetmath.org/approximatingthebirthdayproblem http://planetmath.org/approximatingthebirthdayproblem Say you can tolerate a 1 in 1 Billion probability of collision: With completely random 128-bit UUIDs, you would need slightly over 800 Trillion Rows to have a 1 in 1 Billion chance of a collision. Equation: sqrt(2(2^128)ln(1/(1-1/1000000000))) Adapting the UUID to contain the first 8 bytes as the number of milliseconds since the 1970 epoch would mean 64 bits of random data. You would need to insert over 192,000 rows IN A GIVEN MILLISECOND to have a 1 in 1 Billion chance of collision. Equation: sqrt(2(2^64)ln(1/(1-1/1000000000)))
emmelaich 9y ago
Could you retain simple ints as the primary key and use a hash of it for sharding instead? Then you'd get the best of both worlds.
hodgesrm 9y ago
You make a good point about knowing your database technology. For me the takeaway from the article is "know your database technology and your data" especially if you plan to get big. The original post refers to RDBMS and seems to be largely based on MySQL/InnoDB experience. InnoDB clusters on the primary key and copies primary key values into secondary indexes, so scattered writes and exploding secondary indexes are as well-known problem if you use UUIDs as the primary key on MySQL. Another well-known issue is that UUIDs can lead to random scattering of reads which chew up space in the buffer pool. That said, other RDBMS types don't necessary have the same problems. SQL server can cluster on non-primary key columns or not cluster at all (heap organization). In the latter case secondary indexes on the table use row IDs (RIDs) to refer to rows from the index. Using UUID as a primary key does not inexorably entail performance problems though it might if you made bad choices about indexing. It seems to me people sometimes make a bigger deal of UUIDs and DBMS than is really called for. Badly chosen surrogate keys or time-series clustering can lead to performance problems that are just as severe depending on your access patterns. There are perfectly reasonable workarounds for UUID issues like using integer surrogate keys, which RDBMS support quite well. To use them effectively though you need to spend time to understand your DBMS technology and implementation choices thoroughly. A lot of people skip this step.

Twirrim 9y ago

With DynamoDB you also want to be scattering your reads. As you scale up the table (either data or read/writes) it will be partitioned and your total read/write capacity is split evenly amongst the partitions. If you don't have even distribution of requests across the table, you're going to keep running in to throttle limits.

manigandham 9y ago
dynamo and cassandra use consistent hashing of the primary key, ordered numbers are already hashed randomly.

jrs235 9y ago

>One of the post's points is that UUIDs will scatter your writes across the database And will wreak havoc on any indexes it is included in [if you do a lot of writes and don't have sufficient padding]... page split city!

UK-AL 9y ago
Some UUID and Guids can be made sequential.
- braveo 9y ago
  I can't speak for other databases, but SQL Server's NEWSEQUENTIALID is only guaranteed until the server reboots. At which point the next UUID integer value can be less than the previous, at which point you're back to splitting pages.
  - UK-AL 9y ago
    Normally your application would generate them not the dB
    - braveo 9y ago
      I didn't provide enough context. There's nothing wrong with using UUID's, but I would avoid them for clustered indexes. And I would say typically you wouldn't care about whether or not UUID's were sequential unless you WERE putting them into a clustered index. I'm sure there are use cases where you would worry about the sequential nature for reasons not related to clustered indexes, but in general what I said is true.
      - UK-AL 9y ago
        You application generates sequential guids before placing in a database with a clustered index. Thus solving the issue with NEWSEQUENTIALID and clustered index issue.
        lazulicurio 9y ago
        Just for other people reading this thread, as I've posted before[1], a word of caution if you're trying to generate sequential UUIDs client-side for SQL server: SQL server does not sort UUIDs in the order you'd expect. The bytes are ordered 10-11-12-13-14-15-8-9-7-6-5-4-3-2-1-0. [1] https://news.ycombinator.com/item?id=13120522 https://news.ycombinator.com/item?id=13120522

tkahnoski 9y ago

I've been on the wrong-side of this unfortunately. Rather than implementing a sane archive delete strategy, data was left there to collect so there was pretty much no hope for a particular join not to generate page miss. Eventually we settled on a NoSQL DB with denormalized data in partitions. A few years later we realized we made a poor choice in having too few and too big of partitions, and basically just repeated the mistake with a different database technology (made even worse because now the things on disk were even bigger that we needed to fetch!)

malkia 9y ago

Also Cloud Bigtable - https://cloud.google.com/bigtable/docs/schema-design#types_of_row_keys https://cloud.google.com/bigtable/docs/schema-design#types_o...

sroussey 9y ago

Sometimes, you don't want a workload spread across all the nodes of a cluster.

braveo 9y ago

The one point I went looking for and didn't see is that UUID's make for very poor clustered indexes. SQL Server tried to mitigate this with the 'NEWSEQUENTIALID', but it essentially 'resets' when the server is rebooted. If your data is small enough that it doesn't matter then fine, but in general UUID's are better as a surrogate key than as a primary key.

jrochkind1 9y ago
Yes, that's in the OP, exactly what you said.
- braveo 9y ago
  It was, I meant I went looking for it in the article and didn't see it :)
UK-AL 9y ago
Very few people generate the guids database side. They normally generate them before they even insert it into the database.

lugg 9y ago

Thanks for this reclarification, lead me to do a little searching. https://mariadb.com/kb/en/mariadb/guiduuid-performance/ https://mariadb.com/kb/en/mariadb/guiduuid-performance/ Has some helpful tidbits, like how pks get implicit copies to all other indexes making uuids quite expensive memory wise if you have a lot of referencing tables and a lot of indexes. One of the recommendations I'm not sure on is to compress and reorder the uuid for time sequence. I get the compression part (remove dashes, convert to bin with unhex), but I'm concerned reordering the uuid so the time sections are together (to order your writes better) might actually decrease entropy? and make collisions likely. Does anyone here know much about uuid generation and whether the time sections reordered would make a difference across a table of around 100m~? I think I might just go with internal incremental and external uuid. Solves the knowing key before insert problem with little downsides. The time swap thing is now implemented in mysql8 (broken link in the mariadb post) https://dev.mysql.com/doc/refman/8.0/en/miscellaneous-functions.html#function_uuid-to-bin https://dev.mysql.com/doc/refman/8.0/en/miscellaneous-functi...

meritt 9y ago
> might actually decrease entropy? and make collisions likely. It's rearranging in a deterministic manner, there's no loss of information, it's just a permutation. There is no impact to entropy nor the likelihood of a collision.
hodgesrm 9y ago
The UUID time-swapping trick seems like a bad idea outside of special cases. Overloading the UUID in this way makes you dependent on generating UUIDs correctly so that the ordering works. You can get insertion ordering by using an auto-increment integer primary key which also results in a relatively short key for secondary indexes. This is much easier to understand and cannot be messed up by application errors.
caleblloyd 9y ago
The probability of a collision can be estimated using the "Birthday Paradox" equation: http://planetmath.org/approximatingthebirthdayproblem http://planetmath.org/approximatingthebirthdayproblem Say you can tolerate a 1 in 1 Billion probability of collision: With completely random 128-bit UUIDs, you would need slightly over 800 Trillion Rows to have a 1 in 1 Billion chance of a collision. Equation: sqrt(2(2^128)ln(1/(1-1/1000000000))) Adapting the UUID to contain the first 8 bytes as the number of milliseconds since the 1970 epoch would mean 64 bits of random data. You would need to insert over 192,000 rows IN A GIVEN MILLISECOND to have a 1 in 1 Billion chance of collision. Equation: sqrt(2(2^64)ln(1/(1-1/1000000000)))

emmelaich 9y ago

Could you retain simple ints as the primary key and use a hash of it for sharding instead? Then you'd get the best of both worlds.

hodgesrm 9y ago

You make a good point about knowing your database technology. For me the takeaway from the article is "know your database technology and your data" especially if you plan to get big. The original post refers to RDBMS and seems to be largely based on MySQL/InnoDB experience. InnoDB clusters on the primary key and copies primary key values into secondary indexes, so scattered writes and exploding secondary indexes are as well-known problem if you use UUIDs as the primary key on MySQL. Another well-known issue is that UUIDs can lead to random scattering of reads which chew up space in the buffer pool. That said, other RDBMS types don't necessary have the same problems. SQL server can cluster on non-primary key columns or not cluster at all (heap organization). In the latter case secondary indexes on the table use row IDs (RIDs) to refer to rows from the index. Using UUID as a primary key does not inexorably entail performance problems though it might if you made bad choices about indexing. It seems to me people sometimes make a bigger deal of UUIDs and DBMS than is really called for. Badly chosen surrogate keys or time-series clustering can lead to performance problems that are just as severe depending on your access patterns. There are perfectly reasonable workarounds for UUID issues like using integer surrogate keys, which RDBMS support quite well. To use them effectively though you need to spend time to understand your DBMS technology and implementation choices thoroughly. A lot of people skip this step.