Hacker News Reader

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.

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.

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

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

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

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.

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

Some UUID and Guids can be made sequential.

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.

Normally your application would generate them not the dB

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.

You application generates sequential guids before placing in a database with a clustered index.

Thus solving the issue with NEWSEQUENTIALID and clustered index issue.

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

I'm not sure what that buys you that you can't get by just using an identity column.

Places where the user request, is detached from the actual insert. For example if you are using a queing system for user requests, but you still need to return an Id to the user.

Fairly common when building a distributed application.

why do you need it to be sequential then?

Because it will eventually go into a clustered index once it's been processed.

I'm not trying to be hardheaded, and I understand I don't see all of the nuance because I'm not familiar with the problem you were solving.

But having said that, I have to go back to asking why you didn't just use an identity of some sort.

I cannot see any reason outside of convenience why you would insist on sequential UUID's for that, and I would argue against the convenience seeing as how UUID's are not naturally sequential and any work you did to guarantee them being sequential would also have been useful for generating sequential integers in the software as well (even 128 bit integers).

You could have literally created a 128-bit sequential integer, waved your hands, and then announced to the world that it's a UUID (you wouldn't even need to set the bit to determine which version of UUID unless you were using it outside of your environment for some reason).

Unless there is some other requirement that I'm not aware of, I don't really understand what it buys you.

Combed Guids are normally only partly sequential.

It means they go be generated on any machine, returned to the user, and the request placed on a queue.

Without completely messing up a clustered index.

I don't think you can guarantee the generation of anything sequential across multiple machines without some sort of authority. A single machine, sure as long as the resolution you're using is small enough and/or you have a single point of authority on that machine.

But across multiple machines?

Can you explain to me how you're doing that across multiple machines without any sort of authority? If there's a way to do that I'm genuinely curious.

Most simply use the system clock. Now if I would was building a machine critical distributed system I would advise against using the system clock and instead use some sort of logical clock. But in this case the clock doesn't need to be super accurate, it just needs accurate enough it get placed near the end of the table.

But the worst case in this instance is your insert is slow, and fragments your index. I trust infrastructure to make sure the clocks are accurate.

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

Thanks for this reclarification, lead me to do a little searching.

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

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

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.

The probability of a collision can be estimated using the "Birthday Paradox" equation: 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)))

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.

Yes, that's in the OP, exactly what you said.

It was, I meant I went looking for it in the article and didn't see it :)

Very few people generate the guids database side. They normally generate them before they even insert it into the database.