{"id":92851,"date":"2016-01-14T07:00:00","date_gmt":"2016-01-14T22:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/?p=92851"},"modified":"2019-03-13T12:10:21","modified_gmt":"2019-03-13T19:10:21","slug":"20160114-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20160114-00\/?p=92851","title":{"rendered":"When you start talking about numbers as small as 2\u207b\u00b9\u00b2\u00b2, you have to start looking more closely at the things you thought were zero"},"content":{"rendered":"

GUID generation algorithm 4 fills the GUID with 122 random bits. The odds of two GUIDs colliding are therefore one in 2¹²², which is a phenomenally small number. When you are dealing with rates this low, you have to adjust your frame of reference. <\/p>\n

Some people don’t like algorithm 4 because the algorithm is not designed to ensure uniqueness. There is a chance, admittedly small, that a collision will occur. On the other hand, algorithm 1, for example, uses time-space coordinates to ensure zero chance of duplication, unless someone screws up the generation process<\/a>. <\/p>\n

Hang on a second. “Unless someone screws up the generation process.” Ah, so it’s not zero after all, because there is of course a tiny chance that something will get screwed up in the generation process. <\/p>\n

According to this research paper (pdf)<\/a>, memory chips suffer 25,000 to 70,000 errors per billion hours per megabit. Let’s do some back-of-the-envelope calculations. <\/p>\n\n\n
25,000 to 70,000 errors <\/p>\n
10⁹ hours × 2²⁰ bits <\/td>\n		  ≈  <\/td>\n 2¹⁵ errors <\/p>\n
2³⁰ hours × 2²⁰ bits <\/td>\n		  =  <\/td>\n 1 error <\/p>\n
2³⁵ hours × bits <\/td>\n<\/table>\n

Now let’s see how this error rate converts to “corrupted GUIDs”. <\/p>\n\n\n
1 error <\/p>\n
2³⁵ hours × bits <\/td>\n		  ×  <\/td>\n 2⁷ bits <\/p>\n
1 GUID <\/td>\n		  ×  <\/td>\n 1 hour <\/p>\n
60 × 60 × 10⁹ nanoseconds <\/td>\n<\/table>\n

Now, 60 × 60 = 3600 is approximately 4096 = 2¹², and 10⁹ is approximately 2³⁰. <\/p>\n\n
≈  <\/td>\n 2⁷ errors <\/p>\n
2³⁵ × 2¹² × 2³⁰ GUID × nanosecond <\/td>\n		  =  <\/td>\n 1 errors <\/p>\n
2⁷⁰ GUID × nanosecond <\/td>\n<\/table>\n

The odds that a GUID will be corrupted in memory in the one nanosecond between the time it is created and the time the value is copied somewhere safe is therefore around one in 2⁷⁰. <\/p>\n

This is 2⁵² ≈ 10¹⁵ = a quadrillion* times more likely than a collision between two GUIDs generated by algorithm 4. <\/p>\n

And that’s just mechanical failures in the RAM chips. There are other ways that the generation process can get screwed up. For example, there could be a failure in the CPU itself, maybe due to overheating or overclocking<\/a>. Or a bit error on the hard drive. Or a programming error<\/a>. <\/p>\n

When you start talking about numbers as small as 2⁻¹²², you have to start looking more closely at all the things that you thought were zero. <\/p>\n

* Or “a thousand billion” if you use the European scale. <\/p>\n

Bonus chatter<\/b>: Note that I’m not saying that a collision caused by a random bit flip is more likely than a collision caused by a v4 GUID happening to match some other v4 GUID. I’m saying that it’s wrong to say that the v1 GUID generator will never generate a collision, because there’s a nonzero probability that the v1 GUID generator will deviate from the algorithm. Sure, that probably may be minuscule, but when you’re dealing with numbers like 2⁻¹²², these minuscule probabilities become significant. <\/p>\n","protected":false},"excerpt":{"rendered":"

Do the math.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[26],"class_list":["post-92851","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"

Do the math.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/92851","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=92851"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/92851\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=92851"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=92851"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=92851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}