Patch delays and the Birthday Paradox | EVE Online

Patch delays and the Birthday Paradox

2006-08-31 - By CCP CAPSLOCK

Some of you may have heard of the Birthday Paradox. In short, it's something like this: If you have 23 people in a room, the chance that two of them will share the same birthday exceeds 50%. That is a surprisingly large probability, given that there are 365 days in a year.

Well, today the birthday paradox bit us in the arse. After running EVE for three years, we finally encountered a crippling hash collision in our game resource manager. Until the Dragon deployment, we have been using 32 bit hashes to locate resource files, happy in the knowledge that 32 bits can have more than four billion different values.

We should have known better, though. One of the offshoots of the aforementioned "paradox" is that we only need about 65000 files, each with their own 32 bit hash, before we have a duplicate hash. I'll spare you the exact mathematical details, you can look it up in any book on cryptograpy, or on the venerable Wikipedia.

Anyway, this issue was in a long forgotten piece of code, from those blissful days before we had localization, and less resource files. No one had really given it much thought of late.

So, when a player selected the German client and the client suddenly started to throw tantrums when the skills view was displayed, we were quite flabergasted. The error was very strange to say the least, and everything pointed to some sinister internal memory corruption.

Frantic debugging revealed it to be somehow related to resource loading and it finally emerged that as we were trying to load a particular resource, the presence of the German language pack caused a devious hash collision to occur, which in turn caused us to load a completely different resource. This was then passed on, masquerading as a different issue, and caused havoc later on.

What all this revealed is this particular code in the resource manager needs to be updated. No longer can we blindly rely on the laws of probability to keep us from harm. Code has to be written, tests have to be made, and a new and sturdy patch has to be built. A patch to take on the world.