Be Careful with UUID or GUID as Primary Keys
tomharrisonjr.com
tomharrisonjr.com
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).
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...)
If you don't have even distribution of requests across the table, you're going to keep running in to throttle limits.
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!
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.
Thus solving the issue with NEWSEQUENTIALID and clustered index issue.
Fairly common when building a distributed application.
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.
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.
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.
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.
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!)
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.
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...
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.
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 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.
This is called a "candidate key" in existing literature. much has been written about such things.
Both UUID's and auto ID's are "surrogate keys" because they are arbitrary with respect to the data.
lastly, "natural keys" are combinations of columns that consist of the business data.
Is there a book or any other reading you would recommend to be more familiar with these sorts of details? The longest text I could find about this was the c2 wiki. I'd like to know what else I don't know.
I think I've found the #dbclass series on YouTube, is it the one from Stanford? And thanks for the help.
Links below:
https://lagunita.stanford.edu/courses/Engineering/db/2014_1/...
https://lagunita.stanford.edu/courses/DB/2014/SelfPaced/abou...
https://www.amazon.com/Data-Warehouse-Toolkit-Complete-Dimen...
Edit: no instances of candidate key when I ctrl+f though, still looks pretty good.
As to your question, any introduction to RDBMSs book will teach all these concepts.
Thankfully mine are legally enforced, so it works well :)
Ironically, many illegal immigrants actually do report taxes. In which case they use ITIN, which is compatible to SSN format-wise (###-##-####)... but it is not unique over time.
Except for the fact they are not unique, and there have been cases where people from different states have the same number because each state generated this "random" number, but didn't actually check with each other if it's really unique. It is legally enforced, no two people should ever have the same, but they do.
The only way to have uniqueness is if you know the algorithm AND can control that it behaves as expected. Anything else is just kidding yourself.
--
[0] - as opposed to the way US handles the SSN, where the number was explicitly forbidden from being used for identification, but people use it for it anyway.
What, you think laws never change?
This is what, given (excuse the Java):
MyObject a = new String("choo choo");
MyObject b = a;
MyObject c = new String("choo choo");
a == b;
a != c;
b != c;
a.equals(b);
a.equals(c);
b.equals(c);
This is exactly like surrogate keys. An implementation detail that's crucial to the meaning of the whole thing.
And furthermore, objects in real world also have identities, which are distinct from their attributes. You aren't you because you have a certain name and date of birth, or a certain SSN. You're you because you're you. And we all intuitively know and understand this concept of identity. So any software that deals with real world entities has to reflect that concept, which is exactly what synthetic primary keys do.
And it might not be purely relational; but if purely relational model cannot handle this, then it's simply not a particularly useful model for most practical scenarios.
BTW, a pedantic argument could be made here that, ultimately, identity of physical objects is also data - you just need to go low-level enough (ultimately, the identity of any entity is its wavefunction) to see that. Of course, that ignores the practical aspects.
Are you sure that 'you' today is the same as 'you' yesterday? The notion of identity, however intuitive it may seem to some, is far from being universally obvious.
Let's say you are building a cloud-based HR software of some type. You have an employees table, and store employees.
If someone gets married and changes their name, or gets a promotion and changes title, they're still the same person (and the same database entry).
However, if that someone leaves that job, and then gets a new job at a totally separate company -- that also happens to use your service -- they are a new database entry.
Or are you saying that by using a surrogate key, we only ever have to create one record for an employee, and just update their company details etc. when they change jobs?
I'd argue for a surrogate key in this case because I wouldn't want someone to be parsing my id, and having to worry about changes and backwards compatibility.
E.g., the key might be 2360108 where 236 is company number. Then as we grow eventually you get an id like 10910249, which is ambiguous (company 109 grew to over 10,000 or company 1091?)
I deliberately choose a short prefix for illustration, but this could be an issue with any scheme (you'll never perfectly predict all the future requirements), which using surrogate keys completely avoids.
Of course, you may still want to use a surrogate key for performance or security or other technical reasons, as the article describes.
I just wasn't clear on how the specific scenario you laid out made any additional case for their use.
But there is an intuitive concept of identity that every human after some age has. A lot of philosophy goes to point out that this concept of identity doesn't really work well if you stress it enough - as evidenced e.g. by this identity being constant under ship of Theseus transformation. But under this level of scrutiny, a lot of other things break too, including the meaning of words themselves ("what do you mean by 'is'?").
As it is, this concept of identity is natural to us, it's the way we see the world and organize our societies, and it works fine for all practical purposes.
And it may well be fuzzy, but it's rather telling that this fuzziness nevertheless remains confined to philosophy and metaphysics. Asharites, for example, believed that the world is recreated by God "at every moment" (and that this is what makes the notions of time, motion etc possible), so in that sense, every person is also re-created. But their societies did not derive any peculiar social customs from that belief - they still treated any person at any given moment as if they possessed stable identity over time in practice.
1. We have some EQ function such that if EQ(X, Y) reports true, then X and Y are the same object; and
2. There doesn't exist any function which is more discerning than EQ; if EQ concludes that X and Y are the same, then no other function can find a difference.
In programming, the currrent object may be different from that object moments ago because of mutations. However, inside the virtual machine, we are forced conclude it's the same object. The reason is that within the machine, we do not have a function which can distinguish the two objects. And the reason for that is that under mutation, we we do not simultaneously have the previous object and the new object. Therefore, we cannot apply both of them to a function.
We can discuss differences between yesterday's you and today's you, and find differences. But the discussions of you are not you; they are ideas of you.
Likewise in the machine, we can snapshot the state of an object into some serialized format or whatever, and then two snapshots at different times are different, informing us how the object changed. The two snapshots are not EQ, but they are not the object.
Well, never say never... In a world of immutable objects, an object's identity (reference) can be derived from its content. Look, for example, at how objects are stored in Git.
EDIT: important detail I'd forgotten: hash functions take arbitrary-length data in and spit out fixed-length hashes. I learned about https://en.wikipedia.org/wiki/Perfect_hash_function and https://crypto.stackexchange.com/questions/29264/why-cant-we... is relevant. Relevant quote: """ Mathematically speaking, there is no such thing as a collision-free hash. Practically speaking, there is. """
The practical aspect of making hash function "collision-free" is by using trickery and dark magic to reduce the probability of collision down to somewhere below "Earth just got hit by an asteroid, we all have other problems". You want to go really, really low because hashes are mostly used to quickly verify data, and malicious actors will be happy to throw compute at trying to generate collisions so they can alter the data.
As for how the trickery and dark magic is performed, I'm a wizard of too low level to explain these details to you; all that I recall is that you try and make the hash maximally sensitive to every bit of the input data, so that a random bitflip anywhere has a huge probability of greatly changing the hash.
--
> This is called a "candidate key" in existing literature. much has been written about such things.
To be picky, a "primary primary" key is also a candidate key. A superkey is any set of columns the values of which are guaranteed to be unique in any row in a given table; a candidate key is a minimal superkey (i.e., if you remove any column from the key, you destroy its uniqueness). (Relational purists will want to read "attribute" for "column", "tuple" for "row", and "relation" for "table".)
From a logical perspective, the designation of a candidate key as the primary key is more or less arbitrary; as per this article, that may well not be the case from a physical perspective.
Why does your security rely on primary key obscurity? This seems like you're doing something horribly wrong, put some authentication on that or something.
And no, no they won't. Hitting a collision is very hard if you're using cryptographic strength random UUIDs, you wouldn't even be able to bruteforce 64 bits over the internet in a reasonable timeframe.
Go ahead, try the math on that, the only reason small keys are vulnerable to local attack is because you can perform an enormous number of attempts per second, often in thousands of millions of attempts per second and they can keep at it for as long as they want. The database server won't let you query anywhere near that fast. You will never get anything like that for network based attacks as you're limited by bandwidth, latency and of course, the other side who will notice if you even try to do this for any significant period of time and likely block your attempts or limit them greatly.
You can't put authentication on everything. Some things are inherently vulnerable to guessing because you can't toss an access control on it (the thing is the access control), which what the high bit-lengths and rate-limiting are for. I wouldn't do this with a customer's UUID because it's static, but sooner or later you have to rely on security by obscurity somewhere (for example, password reset tokens).
As a theoretical matter a UUID shouldn't be the sole distinguishing data for authorized actions, but in practice it's probably best not to expose them in case you have an errant insecure direct object reference (which approximately all modern applications do, somewhere or other).
I'm just nitpicking your use of the phrase, "security by obscurity" here. That terminology is levied as a criticism against a lot of modern security design but it's really fine (and sometimes necessary) to use it for defense in depth (unlike, say, a cryptographic algorithm, which does not generally benefit from security by obscurity, though particulars of the peripheral infrastructure can).
It's unrealistic to brute-force one well designed token in the absence of authentication (if it's long enough you could go without any other security controls, including expiry or rate-limiting, but that's also a performance hit at scale). Adding one with an integrity check is effectively rate-limiting anyway.
Funny story though - I was once on an assessment in which a company used a scheme just like that. The UUID was HMAC'd for a password reset request, and UUIDs could be found by messaging another user. Unfortunately, they used the same secret key for password reset HMACs as the one embedded in their mobile app for HMAC signing requests. Worse still, password resets didn't need to be activated, so you could effectively takeover any account by retrieving the HMAC secret key from the app and running the victim's UUID through it.
[1] https://en.wikipedia.org/wiki/Computational_hardness_assumpt...
The other side of it is that safety from enumeration attempts is the sort of thing that gets added on well after the software's actually in use, unfortunately, and changing existing keys might not be practical.
A social network I use is in the position where they don't really want people enumerating their users by ID... but all their users are identified in the URL by sequential ID. An HMAC would help them, and isn't difficult to implement.
And yeah, bad implementations are bad, but I wouldn't trust someone who can't use an HMAC securely to generate and use unguessable IDs properly either.
The original issue with simple auto-incrementing values is that they are easily guessable as I noted above. Botnets will just keep guessing until they find one.
I'm tired of hearing "you don't have to say how to get the data, you have to tell the database what you want and it will get that in the most efficient manner" and then deal with an encyclopedia of byzantine rules to get it to do the aforementioned "efficient manner" with anything approaching decent performance. I can see the art, but the practicality mars it beyond recognition. It's like Venus de Milo sculpted out of duct-tape and bubble gum.
Sorry for the rant, I'm just getting frustrated with performance problems in small data sets. I've taken the courses, I've read Date and Darwen, and I'm just starting to get terribly disillusioned.
You trade complex retrieval of subgraphs for complex retrieval of aggregate measures. Sometimes it is worth it, but I usually find that if you need both (and that is a big if) it's easy to scale relational databases than it is to scale document stores.
This is for many reasons, but an underappreciated one is that it is easier to cache individual objects than it is to cache aggregate measures. So if you need a subgraph just store it as JSON in a table full of simple key value mappings with some tables that handle how to invalidate the cache. But because aggregate measures span so many business objects it it's harder to achieve this. Furthermore, it is more likely to be possible to enumerate subgraphs than it is to enumerate aggregations.
For example, imagine a tool that estimates the number of companies that meet certain criteria. "Count the companies by country that have at least one employee that earns at least $100k a year and who has had at least 2 previous positions." The number of permutations are endless, and while these types of queries aren't trivially fast on RDMSes, it is at least possible to handle them.
I'm not saying any of this is really easy, but humans don't live in an easy world. I used to be a structural engineer (EIT), and what amazed me was that despite the fact that we've built thousands of skyscrapers, each one was its own hell. Concrete trucks would go bad, water would gush out of places in the ground it wasn't supposed to, people would die. But we continue to push forward because we want to succeed.
Performance characteristics of different RDBMSs varies by orders of magnitude dependent on workloads.
Keys are also a flexible concept. They can be formalized to ensure referential integrity (domain), or you can join on whatever you want.
Recursive queries can handle some reasoning on graphs, but they quickly become impractical.
Even so: The flexibility SQL offers when you want to change which data you think should be related is tremendous - on HPC database machines :)
https://www.postgresql.org/message-id/20151222124018.bee10b6...
“There's no substance to these claims. Chasing the links around we finally find this article: http://www.sqlskills.com/blogs/kimberly/guids-as-primary-key... which makes the reasonable argument that random primary keys can cause performance robbing fragmentation on clustered indexes.
But Postgres doesn't _have_ clustered indexes, so that article doesn't apply at all. The other authors appear to have missed this important point.
One could make the argument that the index itself becomming fragmented could cause some performance degredation, but I've yet to see any convincing evidence that index fragmentation produces any measurable performance issues (my own experiments have been inconclusive).”
It can be a bigger issue if you proxy sql queries and shard to 1000 DB servers and you thus rely on part of the query to indicate which shard it is on. You can do this with a type of uuid that embeds the shard, or you have to include additional parts in the query beyond the PK to get the row (it could be a column that the sharing is based on, or a comment). And yes, careful with joins from an a root object's table that joins to other tables that use uuids unless you can guarantee that they are in the same node.
This shouldn't be right. UTF-8 encoding uses the same 8 bits for each valid UUID character that Latin-1 would. Unless someone put invalid characters in the UUID field, I would guess that the new encoding was actually UTF-16 or something.
All the bytes transmitted on the wire will be UTF-8 strings, but this is disconnected from the underlying storage engine.
I don't know if this is the case for other databases, but when I read this my first thought was "This must have been MySQL"
But even with that design, you'd expect VARCHAR(36) to have space for 36 ASCII characters, not 9.
Of course, that is the worst case, but for index size limits, MySQL has to assume the worst case, which means you quickly bump into the default index key limit of 767 bytes with large string keys.
And the parent comment says "In MySQL for example, using UTF-8 charset will cause it to use 3 or 4 bytes per character.", and if it's really using 3 or 4 bytes per character regardless of what that character is, then it's probably storing it internally as a sequence of unicode scalars instead of UTF-8.
Granted, upon re-reading this, neither source explicitly says that a CHAR(36) column won't actually be able to hold 36 characters, but if it can then I don't know why the indexes would stop working.
EDIT: It occurs to me that a CHAR(36) column would require 4 bytes per character to be allocated, since it's a fixed-width column, though it should still only actually use 1 byte for an ASCII character. But 144 bytes is still well under the 767 byte limit you mentioned.
The problem isn't so much the content itself, but the column and index definitions: keeping the same length in characters in the definition will use more bytes in utf8 or utf8mb4, at least against the storage engine index limits. I'm not sure whether this is because MySQL is just lazily/smartly computing the worst case, or if it's actually storing using multiple bytes per character regardless. I assume it's the former.
The documentation's example of the problem with InnoDB goes like this:
This definition is legal, a 255-character index at 3 bytes per char coming in under the 767-byte limit:
col1 VARCHAR(500) CHARACTER SET utf8, INDEX (col1(255))
col1 VARCHAR(500) CHARACTER SET utf8mb4, INDEX (col1(191))
In the case of the UUIDs in the article, I believe it mentioned it was a multiple-column index, so the increase of 3x (or 4x) from latin1 could easily push them over the limit if there's another big column or columns in the index.
I can confirm both these commands return 36 in my mysql installation:
SELECT LENGTH('15c915fc-4d50-11e7-9bc7-50b7c307c620' COLLATE utf8_general_ci);
SELECT LENGTH('15c915fc-4d50-11e7-9bc7-50b7c307c620' COLLATE utf8mb4_general_ci);
MySQL's storage has some space limits defined in terms of bytes, and to express that in terms of characters it has to allow for the worst case.
If it allowed 255-byte space to be used as VARCHAR(255) in UTF-8, then an insert of 255-character long string with emojis would fail.
UTF-8 is variable length anywhere, not just inside mysql. If you don't want this behavior, you can either use UCS-2 or UTF-32. UTF-16 and UTF-8 are variable length encodings, period.
Most databases that have use char length for unicode actually work with UCS-2, and use 2 bytes per char, like MS SQL Server.
The question was why UTF-8 in MySQL has weird limits. It wasn't about what MySQL should have done in an alternative universe.
More fun MySQL Unicode facts...utf-16 uses 32 bits per character to ensure it can handle supplementary characters. UTF-8 only handles characters up to 3 bytes; gotta use UTF-8mb4 if you expect to handle 4-byte values. You can create prefix indexes for Unicode string values that exceed the maximum index size.
Now that it does they can not change the names anymore.
It's the same as why windows is stuck with utf-16, because when they implemented it unicode was 2 bytes.
Incorrect. When UTF-8 was invented, it was actually variable up to 6 bytes in length, being capable of representing code points up to U+7FFFFFFF. It was only shortened to 4 bytes in 2003. There is no point in history where UTF-8 was only limited to 3 bytes.
The 1998 version of MySQL didn't support unicode at all yet.
Unicode 2.0 introduced UTF-16 in 1996, making the need for non-BMP characters very explicit.
And UTF-8 at the time supported 31-bit code points.
http://mysqlserverteam.com/mysql-8-0-when-to-use-utf8mb3-ove...
http://mysqlserverteam.com/sushi-beer-an-introduction-of-utf... (Problem #1)
(Author is the first link here.)
The whole point of UTF-8 is that it's identical to Latin-1 (edit: ASCII) except in cases where it can't be. In those cases, it uses a very efficient encoding.
I understand that people (for whatever reasons) don't want to store text in UTF-8, but that's incredible that such a popular piece of software would take that notion to the extreme. "Let's make UTF-8 almost equivalent to UTF-32 when the data is at rest! Yes!"
Are you sure that info is correct? And if it's correct, are there any valid engineering reasons for that decision? It's probably best to be charitable and assume there must be a reason.
https://mathiasbynens.be/notes/mysql-utf8mb4
You have to use utf8mb4 to have proper utf8 support. Yes its stupid, this is the main reason I prefer not using mysql for anything. Too many gotchas lurking about.
The hyphen has a handful of imposters and one of the more troublesome ones is in extended ASCII as "en dash" (there's another as "em dash"). These do not have a direct mapping to unicode as they are not "hyphens" but they sure do look like them to humans in a hurry. It will throw your meticulously thought out and implemented keys (or any other well-measured column) into a tailspin. Dealing with extended ASCII implementations has been the most hazardous area of characterset handling, at least for me.
Although probably unlikely the UUID is not a guaranteed direct ASCII to UNICODE conversion. I'd advise awareness and perhaps even some level of caution if you have a complex data flow (or, more apt, a seemingly ridiculously simple and bulletproof one).
Extended ASCII sucks so if you use it and don't have one or both feet nailed to the floor then get off of it, sooner.
It's only compatible with ASCII, not Latin-1. You are maybe confusing UTF-8 with the Unicode codepoint space, of which the first 256 codepoints are the same as Latin-1.
- 7-bit ASCII encodes 128 characters; latin-1 encodes 256 characters; UTF-8 encodes all unicode characters
- latin-1 and UTF-8 both extend 7-bit ASCII; the three encodings are equivalent for ordinals 0-127
- UUID characters are part of 7-bit ASCII, so they have the same encoding in ASCII, latin-1 and UTF-8
A CHAR column always allocates the maximum size, so a utf8 (MySQL's weird "UTF-8, but only for the BMP" encoding) CHAR(100) needs to reserve 300 bytes per row, and a utf8mb4 (MySQL's actual UTF-8 encoding) CHAR(100) needs to reserve 400 bytes per row.
But a VARCHAR is dynamically allocated, so, yes, a VARCHAR(100) that stores 100 lower-ASCII characters is only going to use 102 bytes of storage (using 2 bytes for the string length).
See, e.g., the "tip" section at the end of https://dev.mysql.com/doc/refman/5.5/en/charset-unicode-utf8...
A flock of Correctosaurs glide by overhead, scanning the muck with uncanny vision for the telltale motion of their Suttlebug prey. It is their rare, mid-air collisions that give the Suttlebug away, despite their otherwise excellent camouflage.
You might be thinking about the memory storage engine (and temp tables).
This happens even in InnoDB -- it's taking the maximum byte size of all the key fields. For a single VARCHAR(255) in MySQL utf8 that ends up being 3*255=765 for just that one field. If you add other fields, it's really easy to hit the max key length and have the create or alter fail.
The default row format changes in 5.7, so key size is max is now much larger.
In mysql 5.7+ the default row format allows 3000+ potential bytes (up from 767 bytes), so this becomes a non issue for most cases.
you'll never say this out loud : 7383929. you may be able to remember it, maybe. in a uuid you'll match the last few and first few letters just as fast in your head
uuids are fine. sorting is an issue but at scale (the entire point of this article) how often do you need to sort your entire space of objects by primary key? you'll have another column to sort on
hiding primary keys and having 2 keys seems like a great way to make all queries and debugging 2x as complicated
(edit: spelling)
Now, if the developer don't know when it makes sense to use a UUID, there are certainly more problems in the application to worry about. Which is 99% of the cases in most business applications.
https://github.com/alizain/ulid
You can see this visualized with the innodb_ruby project here:
https://www.percona.com/blog/2015/04/03/illustrating-primary...
https://blog.twitter.com/engineering/en_us/a/2010/announcing...
Definitely true, in fact I tend to prefer hex for this purpose. But one minor note - assuming the whole thing is cryptographic-strength random, there's no need to compare first and last, just do first only or last only (last is usually preferred for UUIDs due to them sometimes containing a timestamp at the start), the odds of an accidental match is the same and the visual processing time of switching from one end to the other is lower.
The moment any db starts to grow to these areas, UUIDs lead to far less issues than incrementing ids everytime.
Most RDBMS now have optimizations and native types (uniqueid) for UUIDs/GUIDs and this is really a moot point at this point, most UUIDs are no longer strings in DBs unless legacy from the time before native UUID types.
UUIDs are right for most projects but not all and as typical in any system, the environment and needs of your project will dictate whether it makes sense to use them.
UUIDs eliminating the round trip and negating dealing with autonumbering/sequencing is a massive benefit, the only real con of UUIDs is the extra 8 bytes but make up for it in less need to lookup during runtime when creating new or associating data with them.
(The problem with UUID is that the two first letters are a cruel joke. But hey: people need to make their own mistakes because some things you can't just tell people: some rakes they need to step on until they learn or are unable to reproduce)
Try syncing autonumbering across different database types where some use autonumbering and others use sequences. That is a nightmare scenario but there would be zero issues with UUID keys.
Primary keys as ints/longs will be constant rake stepping as you grow and maintain an app.
UUIDs emerged from a need that int keys weren't filling especially in a distributed/serviced world. I have used them in most DBs for over a decade and no rake steppage.
Side note off topic: If you were a piece of data would you want to be a universally unique piece of data or an int and merely a clone? All my data is a unique piece of data, I am a good Bender.
In many cases you have two problems: network partitions and/or high ID assignment rates. So statements "if there ever was a conflict you'd have an API stating as much" is simply passing the buck to some piece of magic and actively not knowing what goes on. It is a bullshit statement.
In my experience, this is the kind of problem where people tend to fail because they don't grasp that it is actually kinda hard. Especially if you have additional constraints (like the size of IDs). People tend to make all manner of assumptions and then not test those assumptions.
The arguments are familiar though. I hear a re-run of them about every 2 years, when someone has a system in production and the thing starts to generate duplicate IDs. Although both code and notes are available on previous solutions within the company, people tend to ignore that and just plow ahead.
One of our Ops guys did an experiment where they put a uniqueness constraint on the ID column and added an auto-incrementing primary key column that's never exposed to the code driving the thing. It apparently sped up our DB performance by orders of magnitude.
It also turns out that MySQL would perform faster just by leaving those values as strings instead of converting them to binary values. We've got some outside pressure to use Oracle instead of MySQL, and apparently it performs much better than MySQL with our current schema so we apparently aren't going to do anything to improve the MySQL performance or change any of this behaviour.
Let me know if you want ports in any other languages - the the algorithm is to really just treat the UUID as a hexadecimal number (that's actually what it is) and re-encode it into any other alphabet of choice.
That said, always use native UUID types in datastores - they'll convert to bytes / numbers internally and will always be the most efficient. For other situations, remember that they're just numbers, so you can write them in binary, ternary, octal, decimal, hexadecimal, vowels, baseXX or really any other alphabet you want. The bigger your alphabet (as long encoding remains efficient, like ASCII under UTF-8), the better your gains will be.
This may be practical from a storage standpoint but string-based indexes on an SSD are pretty damned efficient.
I've seen cases where it's possible for a business to track a competitor's growth by watching a public facing user id count increase.
Ask an invoice from a HN startup. See the reference number at the top "2017-0000438".
They had 438 potential customers this year :D
In what context would a primary key change, even when sharding? In my entire career I have yet to see it. Also any sane person would never sort random values. If you need sorting in your table, provide some kind of indexed timestamp.
The only time I've seen that happen is when a DBA evangelized for just using 'natural' keys, which in this case were slugs based on the item name. The problem came when users decided they wanted to rename things and then wondered why the IDs they were seeing in URLs didn't match the new names.
I'm not a believer in natural keys anymore.
> If you need sorting in your table, provide some kind of indexed timestamp.
A v4 UUID contains a timestamp. So it seems a bit wasteful to add the separate timestamp column. Why not just use the timestamp built into the ID? This is what MongoDB's internally-generated IDs do. (Though they're not quite UUIDs.)
There's a catch with v4 UUIDs though: the timestamp portion of the ID is not the most significant digits, so a simple ORDER BY doesn't do what you want.
I like the solution developed by Instagram, which Rob Conery discusses at the link below. It uses a pretty simple plpgsql function to generate a 64 bit integer based on the current time, a shard ID, and a per-shard sequence. This lets you generate 1024 IDs per second per shard. It also puts the timestamp portion of the ID first, so if all the shards' data ends up in Hadoop or something you can order consistently across the whole set.
http://rob.conery.io/2014/05/29/a-better-id-generator-for-po...
http://www.sciencemuseum.org.uk/whoami/findoutmore/yourgenes...
In theory, one could use 3D geoposition at time of birth, time of birth, and sibling order (for twins / triplets / etc delivered surgically), where said order is dictated by the parent(s) or ob/gyn present. Of course, the main problem with this in practice is that not everybody has this information.
I would have said you could do something via retinal imagery, but not everybody has eyes. If we had non-invasive neural imagery, would it maybe be possible to derive a key from a simplification of a person's physical brain topology?
IMO, this is one thing Mongo got right: keys, by default, are a timestamp + some random string. This way, they still sort nicely, but don't collide with their cousins in a different instance of the DB.
If you're using natural keys, and one of them is displayable text, and then the business says "We decided to rename the 8th sales district. Can you change it for us?"
Was this a good design? Maybe not. But legacy happens.
We're dealing with a vendor right now that has references to look-up tables based on display text. They should have used surrogate keys of some kind. Or at the least, code columns so that the database is mostly unaffected when values shown to the users get renamed. (Also useful for I18N work)
I think sorting by a arbitrary, unique value as the last sorting dimension is useful to ensure you always get the same ordering when first dimensions are equal. For instance sorting users by (last_name, first_name, user_id) ensures homonymous users don't move around in the list from request to request.
This is quite a sane thing to do, don't you think?
I can't imagine that a primary key migration would be easy even if you'd followed the author's suggestions around having an internal key and an external key, and I feel like if you're optimizing for a future primary key migration you might be focusing on the wrong part of your product.
Unfortunately, the author doesn't really get UUIDs -- the whole point of generating them and using them as a primary key is that you get a unique entry that can be used between systems. That is a magical thing that gives you superpowers.
In a past life, we would keep the customers basic data in the production database forever, but denormalize and export most historical records out of the transaction system to a data warehouse after 18 months of account activity. We also dumped login/audit data to a big flat file for compliance purposes.
The beauty of using the UUID as the key in that scenario is that the data became fungible between the systems. We didn't care about the audit logs, but had to keep them -- if we had to process them, we could do so with text tools (i.e. Perl/Awk) and do whatever querying we needed to do with a subset of data.
Relational databases are shitty and expensive when used as file systems. If you don't need the relational magic, you don't need the cost and operational overhead of a RDBMS. Literally billions of dollars are wasted keeping unused data in databases.
Best case scenario, things break cleanly and you have to fix up your auto-incrementing counters. Worse is when you start getting data corruption because some remote system has its information about "Customer 11492" (who registered yesterday) overwritten by details for "Customer 11492" who registered today.
Also consider that you commonly have systems that you cannot control. What's the internal representatation of s user or action in a SaaS app?
Don't know, don't care. I slurp in data, with UUID as an attribute!
When the model underlying the data is significantly incorrect, and needs to change. I.e., the relation you modeled does not map to the real-world concept like you thought it did. (Or, it did, but no longer does.)
I feel like this most often happens when two concepts end up being modeled by a singular table. You find out later that the table really represents separate, distinct things, and needs splitting. The split off things can — depending on how you do PKs / your migration — get new PKs.
Notice how the author assumes UUID v4[1] in the conversation. There are very few reasons to use the other versions but we are still paying for their price in code complexity all the time.
Look at this UUID parsing code: https://github.com/sporkmonger/uuidtools/blob/master/lib/uui...
What it really should be is `[uuid_string.gsub('-', '')].pack('H*')` (for non-rubyists: remove the dashes, decode the hex back to binary).
Their representation is also not that good since hex encoding is not very compact.
I guess what I'm trying to say is that UUIDs are often used as a default unique identifiers but they are actually not that good.
[1]: https://en.wikipedia.org/wiki/Universally_unique_identifier#...
On top of that you get IDs that are impractical to guess, which while wouldn't replace other security measures, would still give you some collision resistance and probably avoid some bugs because of the unlikeliness of accidentally picking the same key for two different entities.
I'm sure there are pathological cases for UUIDs as primary keys in certain scenarios, like perhaps a very high number of small records, but I've not come across them myself. You obviously have to know your own data and database if you have some very specific requirements.
One interesting thing we ran into when implementing is that C#'s binary format and string format must be different to be sequential. So we have to detect whether the GUID is stored as a string or binary and put the timestamp in the correct place to ensure it is actually sequential.
Here's the PR for the feature for anyone interested: https://github.com/PomeloFoundation/Pomelo.EntityFrameworkCo...
Many UUID generators produce data that is particularly
difficult to index, which can cause performance issues
creating indexes. To address this, Datomic includes a
semi-sequential UUID generator, Peer.squuid. Squuids are
valid UUIDs, but unlike purely random UUIDs, they
include both a random component and a time component.
[1] http://docs.datomic.com/identity.html#sec-6
edit: formatting
Why would you sort these to begin with; what ordering of essentially randomness (part of the point) makes sense?
For example, if your page size is N and you have N+1 things with the same timestamp, you need a backup sort key or your pagination breaks down
SELECT uuid FROM t where filterable_field > $whatever and uuid > $lastSeen limit $pageSize
That being said, the author does talk about not exposing the UUIDs either. I get the feeling it's slightly less bad if a UUID gets exposed accidentally than an increment sequence number.
The bottom line is UUIDs are not bad, you just need to be aware of couple of things when working with them.
Also, sequential ID may reveal some information you may not wan to share. If someone's user ID is 1234, that may be an indication the service has at least 1234 users.
[0]https://medium.com/swlh/watch-paint-dry-how-i-got-a-game-on-...
You'd just start at a million or so, +/- some random amount. That's not a new thing. You should be able to spin all of the auto-number types in all the databases to whatever you want it to start at.
Assume Bob uses one such not-entirely-random UUID variety and actually makes use of the embedded information. Charlie uses random UUID. Bob and Charlie merge their data.
If Charlie had filled the version bits with random garbage, the merge would poison Bob's use of the embedded information.
Basically, UUIDs are a discriminated union type.
It's purpose is to never collide with another UUID v4, not to be the most unique value ever.
Also if there's UUIDs in your system colliding with a 128 bit random numbers then the rng is broken or your UUID generator would be great to crack encryption keys.
Doesn't invalidate your point about being able to make them offline though. Another option I considered to create PKs offline was a userid/timestamp pair.
1. Store uuids in a uuid field. Why starting the article with such a trivial finding that a text field is not optimal.
2. Use sequential uuids.
3. Several benchmarks have shown that the performace hit is minimal.
4. The only way to communicate with ids is to copy and paste them. Never try to memorize, talk about them or type them.
What about the hi/lo algorithm as a middle ground?
https://vladmihalcea.com/2014/06/23/the-hilo-algorithm/
In short, and I hope I don't oversimplify, each "shard" or "cluster" in the database gets a "block" of ids it can then go and assign on their own, the sequential "atomic" increase happens only once per hi "block", lowering the contention.
This gives you nice integers, incremental-ish most of the time.
I like the notion of integers internally and UIID (as integers of course! I would have never saved one as a varchar, I swear! ok, I was a noob... I deserve to be shamed)
Great post all in all!
A GUID has much superior collision resistance than a bare random integer.
The GUID includes a part that is a random (like the int), a time component (prevents collision for hashes generate at different microsecond) and network information (prevent collision across host names).
If the IDs are UUID, then the easiest way to fix the values is to drop the index and re-create it, making all of the other data in the index unavailable as it's being recreated.
The less-easy way with UUIDs is to select just the broken events, create new patched events, delete the old events, and insert the new ones in the right index. But you'd have to branch off of your regular indexing logic to do this, probably writing a separate script. Of course if you make a mistake, you may end up with either duplicate documents or loss of data, compounding the original problem.
So I agree, have IDs that are deterministic (that they can be recreated using some known formula and source data, for example: documenttype_externalid_timestamp).
I'm dealing with that from several vendors atm.
> Think twice — in two cases of very large databases I have inherited at relatively large companies, this was exactly the implementation. Aside from the 9x cost in size, strings don’t sort as fast as numbers because they rely on collation rules.
Eh, I've done that before because it made some interaction with Entity Framework easier (don't recall what now). Hasn't really mattered. The space for storing GUIDs has never been a meaningful constraint for anything I've ever worked on (9x is also nuts and assumes that your database uses 4 bytes per character). Sorting UUIDs is also generally uninteresting since they aren't meaningful by themselves. Maybe if you're doing lots of joins you might care about this.
I had to google it up to know there is a data type for GUID called "uniqueidentifier" (MS SQL) or "uuid" (PostgreSQL). As for MySQL, there is no such equivalent and suggestion is to use CHAR(38) instead.
Does that mean MySQL will have to live with the 9x cost in size issue?
We have multiple components over different stacks and id could be generated anywhere in the components. We had to live with either building unique id per table separate infrastructure or UUID. UUID works perfectly and with POSTGreSQL, it's just awesome.
UUID-4, UUID-3 and UUID-5 are random (3 and 5 are hashes).
UUID-1 is time-based with the time leading, and you can often control the sequence (14 bits) and nodeid (48 bits) fields to be used as whatever you want to avoid collisions.
It even is different from how C# orders System.GUID instances. I think that could be something that can be put to good use if there ever is an underhanded C# contest mimicking the underhanded C contest (http://www.underhanded-c.org/)
Fun times...
If I follow my advice, the type of an ID is an implementation detail of the persistence layer and/or service endpoint.
This solves basically all the problems and we use it in production to number several tables with billions of events per day.
If you are building mobile apps that sync state, UUIDs make your life so much easier. Optimistically perform writes locally, then perform writes remotely and retry on exponential backoff in case of a network error.
Each of the clients reserve a chunk of Lo numbers, and increment the Hi number. Basically, they would pre-allocate a chunk of id ranges, and this allowed good distributed id allocation performance, while somewhat keeping local ordering.
Client generated ids are very useful to do.
This was my attempt to explain different ID generators in NHibernate. While it slowly got overtaken by MS frameworks, for most people, it had special place.
It was/is a very good ORM! And I used it extensively.
it's nicer than using UUIDs because the strings are much shorter.
Is that normal practice? Their DBA was insisting that its normal.
Also- wrt SQL Server ignore anything they say about GUID's as indexes. Just don't cluster them.
Also- enjoy the benefit of not having to ever ask the DB what the pk of those records you want to insert is going to be.
What do you think about such setup?
Database coder reinvents interned atoms.
Works fine.
(10 million new rows everyday)
Using an UUID is not performance optimal, but it is developer optimal and mitigates many other problems listed in this thread (offline sync scenarios, merging partitions or datasets, tracking across systems, opaque external representation perfect for APIs etc.) so unless you're really squeezing the last performance drops from a system I would simply use an UUID nowadays.
Often though, you need an automatic, user-friendly unique id for PK's to give users besides asking the user or generating a text slug.
Here's one construction:
friendly id = HMAC-SHA256(plaintext = "#{table-object-or-model}#{primary-key}", nonce = app-wide-unique-secret-token)
Then in the server app, keep a limited MRU cache (Hash table) of digests back to PKs.
Out-of-scope: authentication, authorization, CSRF/XSS and replay attacks.
I don't think this is a real problem. If you're relying on your ID's being "unguessable" (and introducing engineering complexity to that end) for security you've already failed.
This isn't very feasible with UUIDs because something like 99.9999999% of keys won't have a corresponding object.
This is why most link shortening products use long random strings, and the ones that don't are shamed into doing so [1].
[1] https://www.wired.com/2016/04/researchers-cracked-microsoft-...
That being said, I can still extract information. For example, I can create a user today, and then another user a week from today. From that information I can extract how many new users a service adds in a week.
To avoid that, I can increment by a value other than one, but that might make sharding harder unless I pick a number like 10, 1000, etc. (of course depending on sharding strategy), which is probably easy to figure out.
I guess my point is that it's harder to avoid leaking information with auto incrementing IDs. This may or may not matter depending on the use case.
Most of the drawbacks discussed don't exist if you're using a key value store.