7 ms·
Isn't this easily solved by supporting 128 bit keys and using UUIDs as intended, i.e. as integers and not in their string serialization? This is as nonsensical
by qalmakka 5y ago
Isn't this easily solved by supporting 128 bit keys and using UUIDs as intended, i.e. as integers and not in their string serialization? This is as nonsensical as storing IPv4 as strings instead of 32 bit integers.
- fivea 5y agoIt should be noted that some database providers already provide a UUID data type which is a 128bit integer. https://www.postgresql.org/docs/14/datatype-uuid.html https://www.postgresql.org/docs/14/datatype-uuid.html
- deleted 5y ago[deleted]
- nly 5y agoNot to mention the string serialization is also ugly...
- dexterdog 5y agoIf it's ever being turned into a string and stored or transmitted it's always better to use a standard base64 encode to keep the string to 22 chars instead of the standard 36/38 chars. You can also use base85 and go to 20, but you get into some funky chars there.
- jrochkind1 5y agoI'm kind of shocked MySQL doesn't do this?
- da_chicken 5y agoExperience has taught me to never be surprised when you learn that MySQL does something incorrectly. Having used it since v3.3 it's not unusual.
- yellowbeard 5y agoThat helps with storage, but still is larger than a bigint, and doesn't help with the random distribution of data. I believe newer versions of MySQL have a data type for this.
- da_chicken 5y agoWell, you probably shouldn't cluster on a UUID, but it's not really a great idea to blindly cluster on a sequential id, either. You should cluster based on how you query the data to minimize I/O.
- cbsmith 5y agoIf you use a type1 UUID, you shouldn't have quite so random distribution, particularly if there's only a single machine generating the UUIDs (which admittedly, kind of misses the point, but alas is done all the time).
- evanelias 5y agoMySQL doesn't have a UUID type, nor 128-bit int type. But MySQL 8 does provide functions UUID_TO_BIN and BIN_TO_UUID, which make it trivial to convert between the human-readable string representation of a UUID and the more efficient BINARY(16) representation. MariaDB now has a native UUID column type as of MariaDB 10.7. This is brand new -- 10.7 had its RC release in Nov, not GA yet but very soon I'd imagine.
- mdasen 5y agoThey do test a binary(16) field which is basically what you're talking about (and you could use a binary(32) for a 128-bit UUID).
- ectopod 5y ago16 bytes is 128 bits. Why would you use 32?
- colanderman 5y agoLength 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!).
- stickfigure 5y agoFirestore 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.
- bhawks 5y agoIndeed, 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.
- luhn 5y agoDynamoDB runs the partition key through a hash function, so sequential values end up being evenly distributed across partitions.
- stickfigure 5y agoIf 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.
- stillicidious 5y agoThat's only part of it, the major problem with classic UUIDs are that writes occur randomly across the entire keyspace. Whether it's represented as a string or in binary, ordering does not change, and so the underlying indexing method must cope with these random orderings at insertion time. At least btrees perform much worse with random insertions. I don't know how much impact it has on LSM
- colanderman 5y agoLSMs and fractal trees handle random inserts much better. But you still lose locality of lookups: items generated near each other time-wise are not correlated on disk.
- SloopJon 5y agoIn terms of space usage and its impact on the buffer pool, storing as 128-bit integers (if your DBMS supports it, which MySQL does not) is essentially equivalent to the bin16 case in the first "UUID insertion rates" graph. Performance still falls off a cliff, just a little bit later. As the author says, "The use of a smaller representation for the UUID values just allows more rows to fit in the buffer pool but in the long run, it doesn't really help the performance, as the random insertion order dominates." If you look at the fastest approach the author tried in the second "UUID insertion rate" graph, it actually stores a modified UUID in a 36-character string. There is a missed optimization to store the modified UUID as 16 bytes, rather than 36, but imposing some order on the keys is the dominant improvement.
- stjohnswarts 5y agoYou know what's nonsensical? Assuming one rule of thumb applies everywhere. I will stand by that rule of thumb until I'm cold and in the ground.