18 ms·
UUIDs are popular, but bad for performance (2019)
- ebingdom 5y ago> Let’s begin by the base64 notation. The cardinality of each byte is 64 so it takes 3 bytes in base64 to represent 2 bytes of actual value. Wait, what? I thought it takes 4 base-64 digits to represent 3 bytes of data. Not 3 base-64 digits to represent 2 bytes of data.
- rawling 5y agoMaybe they're using a 9-bit byte? :)
- brabel 5y agobase64 means the "vocabulary" used has 6 bits (2^6 = 64). Hence, to complete a full number of bytes (without using any padding), you need 4 b64-letters: 4 * 6 = 24 = 8 * 3 So, you're correct... the exact amount of bytes that it takes to represent "actual" bytes goes like this: Actual bytes | b64 bytes required | overhead 1 | 2 | 2x 2 | 3 | 1.5x 3 | 4 | 1.33x 4 | 6 | 1.5x 5 | 7 | 1.4x 6 | 8 | 1.33x 7 | 10 | 1.43x 8 | 11 | 1.37x 9 | 12 | 1.33x EDIT: As you can see, this averages with an overhead of between 33% (best case scenario where the encoding requires no padding, happens every 3 rows above) and something like 37%, decreasing with the number of bytes being encoded and approaching the minimum, 33% (e.g. to encode 1024 bytes, you need 1366 b64 digits, an overhead of 1.333984375x).
- drenei 5y agoBad for performance as primary keys. But, still provide strong value as a unique identifier which is what makes them popular. I’ve used integers as primary keys, with UUIDs as alternate keys for external-to-the-data-store queries.
- KingOfCoders 5y agoDone the same :-)
- isoos 5y agoRather: bad for performance (as primary keys) when read/write in sequential order. Great for (primary keys or anything) in a distributed/sharded database (e.g. CockroachDB), when data access is mostly by keys.
- globular-toast 5y agoYeah. The main problem is people using them as primary keys in naïve systems like relational databases. You can't just expect a relational database to magically become a distributed system just by using UUIDs. There is a bit more work to do than that.
- globular-toast 5y agoIs it too much to ask people to explain what's wrong with this well-written and on-topic comment instead of downvoting it?
- jitl 5y agoCalling relational databases (HN’s preferred storage system) naive probably sounds like trolling to most people. There are also plenty of distributed relational databases. People downvote comments that sounds like trolling or flamebait. I use UUIDs but I don’t know why they would magically make my Postgres a distributed system. I like them because the client can generate them offline.
- globular-toast 5y agoWhat? Really? Naïve in this context means a general purpose solution that doesn't "know" about your use case. Have people never heard of a naïve algorithm or solution? Distributed relational databases aren't naïve in this context. MySQL is.
- busymom0 5y agoIs this specific to MySQL or does it apply to Postgres too?
- Svip 5y agoAs far as I can gather from this post and looking at the data type documentation, MySQL does not have a specific UUID type, but Postgres does.[0] I'll assume that Postgres has some internal optimisations to UUID that MySQL thus lacks. Addendum: I also realise this is anecdotal, but someone on Stackoverflow mentions a significant speed up from changing `text` to `uuid` in Postgres.[1] But this also fits with what I've been told on #postgresql on libera.chat. That being said, integers would still outperform uuid. [0] https://www.postgresql.org/docs/14/datatype-uuid.html https://www.postgresql.org/docs/14/datatype-uuid.html [1] https://stackoverflow.com/questions/29880083/postgresql-uuid-type-performance/56453329#56453329 https://stackoverflow.com/questions/29880083/postgresql-uuid...
- Rafert 5y agoThe UUID type index in Postgres is optimized: https://brandur.org/sortsupport https://brandur.org/sortsupport
- hobs 5y agoA lot of the problems listed in the post are physical issues with larger data types that are somewhat random - eg the size, how clustered indexes work, and you will have the same problems with them in SQL Server.
- radicalbyte 5y agoIf you order the data based on the uuid and your uuid is randomly distributed, then you will almost always be writing the data in the middle of your table, physically. You can cut the impact somewhat by using spare tables (leaving lots of empty space) but eventually you'll be re-writing the data. SQL Server has a sequential uuid type which avoids exactly this problem.
- yeldarb 5y agoInterestingly, for other systems you sometimes want the exact opposite: for your key space to be distributed across indexes to balance the load (vs wanting them all to hit the same “hot” index for MySQL). For example, Google’s Cloud Firestore is bottlenecked to 500 writes/second if your key is monotonically increasing (like a timestamp or these timestamp-based UUIDs) causing you to “hotspot” the index: https://cloud.google.com/datastore/docs/best-practices#high_readwrite_rates_to_a_narrow_key_range https://cloud.google.com/datastore/docs/best-practices#high_...
- ummonk 5y agoYeah S3 has similar performance issues where accessing objects with the same prefixes has lower throughput because they get sharded onto the same server. It's very counterintuitive when you're used to how performance works on single computers where you want to optimize for cache-locality.
- nielsole 5y agoUgh really? Why would they not hash the whole filename for shard assignment?
- bowmessage 5y agoBecause the file name includes the "directory" prefix, i.e. each file's name stores the `/entire/bucket/dir/tree`, which can get large.
- manigandham 5y agoThe size of the input doesn't affect the hashing.
- bowmessage 5y agoIt affects the runtime of the hashing.
- 5y ago
- NicoJuicy 5y agoI think the author is missing an overall picture, eg. Event driven scenario's. Where you don't have to check collisions with a db. He mentioned generating the pk's on remote client, but that doesn't capture the interesting bits. You generate the newly created object with the guid. You send it to the API/Microservices and it's generated, fire-and-forget style. And the remote client has an Id of the newly created object to do something with.
- VWWHFSfQ 5y agoBut now the remote client has an ID of something that may or may not exist the next time they try to use it depending on whether or not it actually made its way into the database. I've seen this kind of architecture before. It sounds nice but is loaded with consistency problems.
- roenxi 5y ago> and purely random (version 3) This is a typo, v3 isn't random. It is generated deterministically from inputs. > The only “repeated” value is the version, “4”, at the beginning of the 3rd field. All the other 124 bits are random. And this is close but not quite correct. UUID v4 has a couple of other fixed bits, there are only 121-122 random ones. There are patterns in the text representation other than constant numbers. :)
- gkop 5y agoThis blog post is over two years old, that 3 vs 4 error is inexcusable.
- gls2ro 5y agoA lot of things that we do for security or privacy are bad for performance, but I think they are still good tradeoffs.
- manuelabeledo 5y agoAnd for data safety as well. In an environment where millions of events are processed every second, being able to uniquely identify them is a must, and temporal keys are not always an option.
- eerikkivistik 5y agoAgreed. Using UUID-s for keys is useful to exclude entire classes of security issues. Most notable are many kinds of enumeration attacks.
- piaste 5y agoAlso entire classes of bugs. You screwed up a JOIN, or an application-level lookup for that matter? With UUIDs you'll get no results, with sequential ints you'll get a valid but wrong result. Or worse, the right result for the wrong reason. I've actually seen a case where creating a new entity in the application populated X records in X child tables, each with a sequential ID, and as a result all of them had the same surrogate PK. They were 1:N relationships in principle, but the software wasn't feature complete yet so the actual records were all 1:1. Years later one of those tables finally received some extra records, and it caused a really weird bug because a query had accidentally used the PK instead of the FK as a join key, but for years it had happily chugged along because the two columns were in sync.
- datavirtue 5y agoQuit exposing your keys.
- tluyben2 5y agoYep, so we need solutions for using these practices in a performant way rather than hearing they are not 'good' and then having to explain over and over again why they are there. Our datasets that use UUIDs have not had issues with performance but of course we keep looking for ways to keep using UUIDs while improving performance. It would be better to provide solutions on how to do that and spend time to get performance on par with int keys. Like someone else said; 32 bit int keys are no good anyway for many cases, so let's go to 128 bit, optimize for that and everyone is happy. Edit: like https://news.ycombinator.com/item?id=29851653 https://news.ycombinator.com/item?id=29851653
- Aardwolf 5y ago> The missing 4 bits is the version number used as a prefix to the time-hi field. Why would you use 4 bits for a version number in something that's supposed to be unique? What is the benefit of following this specification despite such cost, versus creating 128 unique bits based on time / random generators / machine IDs yourself?
- Borealid 5y agoThe ability to mix different types of ID in one column or one business data store. When you start with random UUIDs, and then decide you actually wanted per-host-namespaced ones halfway through, if you have allocated zero bits for the version ID you're up the creek. You're trading off present-day efficiency for future-day flexibility. Whether that's wise for a particular case depends on that case.
- MauranKilom 5y agoBecause 124 random bits are still way enough to make collisions extremely unlikely (needs on the order of 2^62 UUIDs even with birthday paradox - good luck storing them all), yet they are still recognizable as being of that specific format.
- olliej 5y agoI am very much not a database person, so forgive me if this is a dumb question. I'm reading this article and it says that UUID are compared byte by byte, and seems to be indicating they're stored as string. Is that actually the case? I would have assumed that SQL supported 128 bit ints, but this seems to imply it does not. Another question: if a column is set to char(fixed size) do the various sequel engines really not optimise to do multi word comparisons? (e.g. 8byte at a time, then 4, 2, 1, as size requires)
- NavinF 5y agoIt often doesn't matter if you use a 128bit int or a string since either way you're loading 4K/8K/16K from ssd/hdd. Database people do all sorts of silly things like storing datetimes as normalized ISO strings (2022-01-08T08:18:20) instead of using 64bit unix time. They get away with it because both the backend (durable storage) and the clients (webapps responding to a user 10ms away) are incredibly slow compared to CPUs. That aside, Postgres stores UUIDs as a 128bit int, not as a string, so it almost certainly uses multi-word comparisons via memcmp: https://stackoverflow.com/a/29882952/703382 https://stackoverflow.com/a/29882952/703382
- piaste 5y ago> Database people do all sorts of silly things like storing datetimes as normalized ISO strings (2022-01-08T08:18:20) instead of using 64bit unix time That's super weird. I can't think of a major RDBS that doesn't have a native date/time data type, unless you count SQLite.
- pkolaczk 5y agoYou can fit many more uuids encoded as 128 bit numbers than as strings in a 4K page. Hence you'll need fewer pages to store your data and that might make a difference between fetching from cache vs fetching from disk.
- jrochkind1 5y agoNot a dumb question, I think you've hit on a key oddity here. This article is about MySQL, apparently it's really the case in MySQL? It's not the case in every rdbms universally. Postgres has a uuid type that stores them how you would (rightfully) expect. I have no idea why MySQL does it this way, it does seem odd.
- deleted 5y ago[deleted]
- kgeist 5y agoJust a month ago we migrated many of the columns from integers to UUIDs (encoded as binary(16)) in several critical tables which are pretty large (Percona server, too), and so far I haven't heard about any serious performance degradation after the release.
- jcelerier 5y agowhat's pretty large for you though ? There are fields where 100k entries is a pretty large dataset and others where "large" starts at petabyte
- kgeist 5y agoI didn't mention that our DB setup uses sharding, and every tenant has their own DB shard (there are tens of thousands of shards). I just checked that one of the largest tenants has 2.2 mln rows in one of the affected tables, which is usually joined with 2-4 more related tables using UUIDs (another such table is 1.1 mln rows, for example), and they're on the hot code path because it's the core of the system. Maybe with sharding the difference is negligible? During code review I raised the concern that inserts and joins can become much slower after we migrate it to UUIDs, but so far my fears haven't materialized. Usually with these tables we have performance problems on the application side, not in the DB, such as ORM fetching data in a very inefficient way, or using too much RAM. Maybe it'll bite us in the long term as the tenants' shards grow in size, who knows.
- jandrewrogers 5y agoA few million rows is tiny for a database, so it shouldn't be an issue in most cases. That much data will trivially fit into cache (these days, possibly even CPU cache). It probably won't become noticeable until your tables are much larger than cache memory.
- qalmakka 5y agoIsn'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 ago
- busymom0 5y agoSlightly related question- does anyone know what data type Reddit uses for their post/comment id? It seems like a short alphanumeric yet unique identifier and much shorter than a uuid. Also what does twitter use for their post/comment id? Seems like some sort of big int?
- Dachande663 5y agoTwitter created Snowflake many years ago to generate IDs. Unsure whether it’s still in use. https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake https://blog.twitter.com/engineering/en_us/a/2010/announcing...
- erwincoumans 5y agoThat sounds nice and simple, and fits in 64 bits (vs 128): "we settled on a composition of: timestamp, worker number and sequence number. Sequence numbers are per-thread and worker numbers are chosen at startup via zookeeper"
- erwincoumans 5y agoTwitter uses strings instead of ints to represent the 64 bit UID, because Javascript only supports 53bit ints instead of 64bit... https://developer.twitter.com/en/docs/twitter-ids https://developer.twitter.com/en/docs/twitter-ids
- damagednoob 5y ago> The remaining of the UUID value comes from the MD5 of a random value and the current time at a precision of 1us. I might be misunderstanding something here but if your random seed is based on time, under high-concurrency, doesn't this risk collisions? I can't see any thread-safety guarantees in the documentation.[1] [1] https://dev.mysql.com/doc/refman/8.0/en/mathematical-functions.html#function_rand https://dev.mysql.com/doc/refman/8.0/en/mathematical-functio...
- hashimotonomora 5y agoIf the column is UNIQUE there’s no collisions it will just fail to INSERT.
- damagednoob 5y agoThen it doesn't have the same quality as a UUID which is supposedly guaranteed to be unique across space _and_ time[1]. [1] https://datatracker.ietf.org/doc/html/rfc4122 https://datatracker.ietf.org/doc/html/rfc4122
- hashimotonomora 5y agoIt’s not guaranteed, it’s just extremely probable that it’s unique given that its generation follows a uniformly random distribution.
- foxhop 5y ago
- andix 5y agoPerformance is really bad, if you save them as strings and use those strings as keys. If you take them as 128 bit integers, it’s kind of fine. Often 32 bit integers are anyway not long enough as a primary key, so you need at least 64 bit keys. UUID is just double the size then.
- hn_throwaway_99 5y agoNote some of the newly proposed UUID formats would take care of some of these issues [1]. They are time-ordered but still have a good bit of random entropy. 1. https://news.ycombinator.com/item?id=28088213 https://news.ycombinator.com/item?id=28088213
- sudhirj 5y agoI recently wrote about how encoding ULIDs in the UUID format could help with some of these problems https://news.ycombinator.com/item?id=29794186 https://news.ycombinator.com/item?id=29794186 https://sudhir.io/uuids-ulids https://sudhir.io/uuids-ulids
- sandman008 5y agoHi Sudhir, Love your blog posts. Keep them coming.
- deleted 5y ago[deleted]
- lepetitchef 5y agoFun improvement from my project a long time ago, uuid has 36 char and to save space, we created a shorten version by removing all the dash character in uuid. The result is 4 char could be removed, the field in MySQL table only needs 32 char.
- isoprophlex 5y agoThe point is, a uuid contains 128 bits of data, so a varchar(32) is still somewhat excessive
- Too 5y agoWhy varchar over char? The length is always the same.
- isoprophlex 5y agoYeah, true. My bad. I'm used to calling everything TEXT.
- dorongrinstein 5y agoThat's the reason I've chosen postgres over mysql years ago and I don't use clustered indexes.
- peheje 5y agoWhat does postgres do differently here to still have good performance?
- immutology 5y agoMicrosoft SQL Server / Azure SQL support sequential UUIDs to solve the index distribution problem: https://docs.microsoft.com/en-us/sql/t-sql/functions/newsequentialid-transact-sql?view=sql-server-ver15 https://docs.microsoft.com/en-us/sql/t-sql/functions/newsequ... It's better than nothing, but one of the values of UUIDs for identifiers is that you can create new ones client-side while offline. These "sequential" UUIDs will fail standard UUID validation because of the byte swapping and, in my experience, when used offline-capable apps, will result in sparse clusters of sequential UUIDs that yield an unpredictable improvement over truly random UUIDs.
- joshstrange 5y agoI'm sure I take bigger penalty hits for less, sorry but UUID's "click" in my head and they prevent a whole slew of foot-guns. It would be one thing if auto-inc was the same as UUID but there are really annoying things with auto-inc (not knowing the id until after insert being top of mind) and also you can generate UUID's client-side/offline if needed. Yes, I know some people argue for auto-inc as primary and still use UUID for client-facing but I don't understand what that really gets you and it seems way more complicated.
- deleted 5y ago[deleted]
- postalrat 5y agoTypically, it gets your performance. And if performance is what you need it may be one of the simpler things you can do.
- mhoad 5y agoI recently read a book by Google’s head guy on API design that was specifically about designing APIs and it had a big section on what makes a good identifier and why people reach for UUIDs and why specifically it is a problem on multiple levels. The thing that he ended up recommending however was super interesting in that I had never seen it mentioned before but it was basically to use this instead http://www.crockford.com/base32.html http://www.crockford.com/base32.html
- nostrebored 5y agoWhat was the book?
- mhoad 5y agohttps://www.bookdepository.com/API-Design-Patterns-JJ-Geewax/9781617295850 https://www.bookdepository.com/API-Design-Patterns-JJ-Geewax... I loved it, think it all made a ton of sense. Lots of code samples, no weird technology choices (normally they would do it all via protobufs and gRPC but they keep the same principles and just use HTTP instead and Typescript for code samples)
- jgeewax 5y agoGlad to hear ! :-)
- afhammad 5y agohttps://livebook.manning.com/book/api-design-patterns/chapte https://livebook.manning.com/book/api-design-patterns/chapte... Section 6.3.3 gets to the point about base32
- afhammad 5y ago
- Nav_Panel 5y agoI see this around the crypto world a lot lately (notably for Substrate/Polkadot addresses): base58 https://tools.ietf.org/id/draft-msporny-base58-01.html https://tools.ietf.org/id/draft-msporny-base58-01.html Seems to have the same idea of "human-read-write without visually identical characters" but with an expanded set for shorter string length.
- pachico 5y agoThis topic has been raised more than once at my work and it scared a lot of people. It's important to understand your use case before you embrace any other solution. This will affect you only when you are frequently creating and storing new IDs, which leads to reshaping btrees. If you have IDs and its number is under control and doesn't change a lot you're just fine.
- Zigurd 5y agoOnly if you are creating persistent objects in multiple places that may not be in communication with one another, and that at some point need to be distinguished from each other, do you need UUIDs. Even in mobile apps, which seem like the most common use case for needing them: Unless your app creates these objects while not connected, you don't need UUIDs. If your backend database is where objects get created, you don't need UUIDs.
- tehlike 5y agoSequential UUIDs fix this problem.
- jetzzz 5y agoWhat's the purpose of using non-random data such as time and MAC address in UUID? It increases probability of collision compared to purely random bits and if you need time or MAC it seems better to store them as separate fields - easier to perform selects, groupings, etc.
- abujazar 5y agoThe author seems to have forgotten the obvious alternative of using ints for database primary keys and uuids externally.
- web007 5y agoThis article talks about random IDs leading to page thrashing, and MySQL b-tree indexes not handling them well. They are bad for _MySQL performance_. It doesn't talk about NoSQL or sharding, where random IDs usually perform much better than sequential due to a lack of hot shards. If you distribute your reads and writes at random across N machines you can get ~Nx performance vs one machine. If you make your writes sequential, you'll usually get ~1x performance because every insert goes to the same machine for this second/minute/day, then rolls to a new one for the next period. There are sharding schemes that can counter this, but they require insight into your data design before implementation.
- kazinator 5y ago> Even if you use pseudo-ordered UUID values stored using binary(16), it is still a very large data type which will inflate the size of the dataset Every IPv6 datagram has a pair of source and destination UUIDs. :)
- deleted 5y ago[deleted]
- yalogin 5y agoWhy would anyone use a random value as a primary key? I haven’t done databases in a long time but isn’t it standard practice to use a sequential incrementing value for the primary key?
- tapas73 5y agoreasons are: 1. no need for coordination in distributed system, no need to check what is the next available id. 2. if userid is visible to users, sequential userid gives away information about the amount of users and allows guessing other valid userids.
- yalogin 5y agoThis is exactly over engineering and solving for the wrong problem. It can be solved easily d efficiently in other ways.
- kune 5y agoPeople should have a look as k-sortable unique identifiers (KSUID). Binary they are represented by 20 bytes and their string representation has 27 characters, which is shorter than UUIDs since the use a base62 encoding. They are sortable since the 20 bytes start with a 32 bit UNIX timestamp followed by random 128 bits. They should be very efficient for clustered indexes / B+-Trees. Note also that as long as you have a single central database you don't need UUIDs. They are only needed if you have several processes creating objects without coordination.
- itsdrewmiller 5y agoSounds like a ULID that doesn't fit in a UUID column - https://github.com/ulid/spec https://github.com/ulid/spec
- jimmaswell 5y agoThis seems to be just about using UUIDs as indexes in a DB, not using UUIDs in general as an ID for things which I'm not seeing any reason not to continue doing.
- nightpool 5y agoSure, as long as you never want to look things up or reference them by ID, then there's no reason to worry. Otherwise, yes, you'll have the exact same problems laid out in the article