6 ms·
Many years ago now we built something that used a 60-bit truncated hash of URIs. So that's far too small to be comfortable that you won't run into collisions,
by tialaramex 6y ago
Many years ago now we built something that used a 60-bit
truncated hash of URIs. So that's far too small to be comfortable that you won't run into collisions, but it's big enough that for modest sizes (hundreds of millions up to billions) a collision is unlikely. So you can have a slow path for the collision case, so long as that slow path is correct. For unit testing we needed at least one collision so we could see that everything behaves as designed before some real user hits one. We had test data sets with over a billion URIs in them, but none that (as far as we could tell) had a collision.
So I just wrote code to mint nonsense URIs for our system based on a small integer seed (like https://foo.example/123456789 https://foo.example/123456789), then span up a system with a bunch of RAM (maybe 8-12GB) to iterate through each seed, storing the hash and seed it was generated from, until it hit a collision after a few gigabytes of RAM, then it spat out the two URIs from the colliding seeds. Bingo, now we had data for unit testing to show that stuff works even in the unlikely case that two distinct URIs have the same hash.
Probably a day's work to build that, and then I'd guess several hours every month saved debugging weird collision bugs because our unit tests would now tell us if we'd screwed up and collisions were slipping past.
- seanmcdirmid 6y agoCouldn’t you also test the recovery logic with a hasher that yielded collision more often? It’s like take your system, make it worse (use very dumb hashing), and see how it degrades and/or breaks?
- xxxtentachyon 6y agoOr, even simpler, just stub out your hash function and to something that always generates the same value and test with that.
- rocqua 6y agoSeems like that would make it less of an integration test
- jmholla 6y agoThey said it was for unit tests.
- Heliosmaster 6y agothey mention this was a unit test, for which stubbing the hashing function would have been totally fine
- treeman79 6y agoThis! Take over a project with thousands of integration tests. I trust none of them. Why? Because anything hard to test has been mocked to oblivion. I have api endpoints that have massive complicated integration tests. I eventually just got source for every project in company and checked to see what they actually did with API.
- thaumasiotes 6y agoIn this case, I think mocking is the right thing to do. You want to know that you can handle the case where two hashes collide. But for this purpose, you don't care at all how the hashes were generated. If the website changes its URI hash algorithm, the "honest" test that just supplies two URIs that happened to collide under the earlier algorithm will suddenly become worthless. The mocked test will continue doing exactly what you always wanted it to do -- exercise the "what if the hashes collide?" case in your code.
- cle 6y agoYou still have to reason through “what if it collides with the real hash function?” How do you know it will behave the same if you don’t test it? (I can sympathize with both approaches and don’t think either one is better.)
- jskdvsksnb 6y agoI have the inverse - I started at a place that has hundreds integration tests that require a database, k8s, the whole shebang. No mocking anywhere. Tests take an hour to run, are extremely fragile and flakey. Getting your local dev machine set up to run even a subset of the tests is a half day ordeal, and it can change periodically. If you have external dependencies that don't version their APIs well it may be inevitable that you need to run tests against them. But for developer productivity you should have a fast/non-flakey path to run local unit tests with no network dependencies. It's also great for working on a plane.
- tialaramex 6y agoMy preference is always to actually test parts in as close as possible to the real state, avoiding mocks unless they're necessary. The more "fake" the system is, the less it tells you about how your software actually works. So since I could generate collisions for the real hash, that's what I did. If it had been infeasible, I would of course have found a different way to test. This particular software was written mostly in C (today I would not write it in C) which makes it even more likely that introducing never-used-in-production behaviour unexpectedly perturbs the system. This same system for example ran into an obscure (and since fixed) libc allocator bug, and a defect in the Linux kernel, because we were really kicking the shit out of the memory mapped file I/O with what we were doing.
- seanmcdirmid 6y agoThe only high fidelity mantra in testing is a bit misguided. If you only test your system in as close to production state as possible, you are never going to encounter stress states that would only very rarely appear in production. Seeing how your components independently deal with less ideal components in the system can tell you a lot about how they might handle rare but bad cases in production, and allow you to over engineer them a bit more to avoid that. > which makes it even more likely that introducing never-used-in-production behaviour unexpectedly perturbs the system. Isn’t that a good thing? Isn’t the goal to deal with the unexpected in the first case?
- jniedrauer 6y agoTests come with a non-zero cost. They're code that needs to be maintained. Often complex code, with poor documentation. I don't think the value provided by testing states that you will never actually encounter in production outweighs the cost of maintaining the tests.
- seanmcdirmid 6y agoTo achieve “defense in depth,” testing components in degenerate non-production situations (and then over engineering them to gracefully deal with those situations) is the only way to get there. Of course, we aren’t building bridges, so maybe it’s less important.
- harpiaharpyja 6y agoI was wondering why GP couldn't have swapped out the hash function for one that just returns a fixed value, making everything a collision. Then it would just be a matter of verifying the system still works under that condition (ignoring the performance hit). You could even measure the performance hit from that degraded condition and create a heuristic to warn you if something is wrong with the fast path.
- AtlasBarfed 6y agoDid you truncate the hash for dataset size considerations? If you associate data with the hash, I would guess the test data would dwarf the hash size, so why not do 128 or 256 hashes?
- tialaramex 6y agoThe hash is for content-based addressing. We're going to fasten those 60 truncated bits to a 4 bit tag that says this is a URI in the content-based storage. And then we can use this 8 byte value to refer to that URI twice, or fifty thousand times in our system even if the URI is a hundred bytes long - the only problem is collisions, so we need to be sure we notice if there is a collision and handle that correctly everywhere.
- nulptr 6y agoI have a question about how you generated collisions. If each seed is a 32-bit int, and each hash is 60 bits, then you'll have to store 92 bits for each (seed, hash) pair. With 2^32 (~4.3 billion) (seed, hash) pairs, you'd need 2^32 * 92 bits ~= 50 gigabytes. But you mention only needing 8-12GB. Is my calculation wrong, or have I missed something?
- manulp 6y agoYou’re looking for a collision, any of them will do, so your computation doesn’t actually need to go through all the elements. https://en.m.wikipedia.org/wiki/Birthday_attack https://en.m.wikipedia.org/wiki/Birthday_attack
- Thorrez 6y agoSince the hash is 60 bits, a collision is expected after 2^30 tries due to the birthday paradox. So by your math this would be 12.3GB. Although this is ignoring hash table overhead, which I expect to be at least 2x. Maybe they just got lucky.
- nulptr 6y agoI think I found a way to do it with ~8GB. As you mentioned you only need 2^30 tries due to birthday paradox. But, instead of using a hash table to store (seed, hash) pairs, we can just use a list of only hashes. To generate the next hash we use current hash. i.e. next_hash = hash("example.com/" + string(int64(cur_hash))). So now, we just store 60-bit hash values which takes up 2^30 * 60 bits = 8gigs. The only other problem is detecting if a hash already exists, which I think can be done using a space efficient probabilistic hashset like a bloom filter (and when the bloom filter says the hash already exists, we do a linear scan to find where it exists and we have a possible collision).
- penteract 6y agoActually, using that method, you'd need much less than 8GB, since a collision would mean you'd hit a cycle, so you could store something like 1 value for every 2^10 iterations. When you found a collision with one of those, you could examine the interval more carefully to find exactly where the collision was.
- jcims 6y agoI embarrassed myself as a Noogler trying to explain what in my head seemed like a good tradeoff between hash size (also of URIs) and collision handling. The process had fixed storage for a table of known hashes, and every collision was tested for validity before taking action. If you could use a truncated hash, you’d obviously increase your collisions, but if you’re going to validate all collisions anyway, it seemed like you could increase your coverage substantially (in the 60-bit case it would have been 4x) while only marginally increasing your overhead of collision handling. There's some kind of sparsity/entropy function involved with optimizing these two but I'm too clueless to sort it out. Without the vocabulary to make my case I just got weirded out by a bunch of smart people staring at me quizzically. Sooo..
- deleted 6y ago[deleted]
- Arcuru 6y agoThat kind of thing happens to me all the time. I'm very often unable to think of or explain things in the moment. Sometimes it helps to write a doc afterwards to get my thoughts in order and decide if it's worth sharing.
- btrask 6y agoIt's known as the birthday paradox. There is a probability table here: https://en.wikipedia.org/wiki/Birthday_paradox#Probability_table https://en.wikipedia.org/wiki/Birthday_paradox#Probability_t...
- jcims 6y agoYes! That’s the part that I was having trouble getting my head around. Looks like 96 bits would have been fine and 128 more than adequate. A small bit of vindication :)
- stouset 6y agoWhy not just run the test-cases using a 16-bit hash function?
- kortilla 6y agoLikely a C programmer with little experience doing testing with fakes. Most C projects I’ve worked on are horrible at structuring the code in a way that makes it sane to do dependency injection or mocking.
- kortilla 6y agoThis is one of those cases where it would have been easier to fake the hashing function in the unit tests with something that collides when you want. What happens if you want a test case where 3+ URLs hash to the same bucket?
- wbsun 6y agoAny reason the hash function and the collision handling can’t be separated and mocked for unit tests? What if you decide to increase the bits of hash values or change the hash algorithm?
- csense 6y agoFigure you need at least 12 bytes per entry to store the ID and hash. Then you can only handle 1/12 of your memory size in bytes (so 1 billion entries if you have 12 billion bytes of RAM). Much more memory efficient to use a Bloom filter. Build n different ways of hashing the hash (this can be as simple as having some standard hash function H() making the ith different way H(h, i)). Then when you add an entry you write a bit at each of these locations. Instead of writing right away, you check to see if all the bits were already set. If they were, the entry being added is a candidate for a possible collision with some earlier entry, so stream it out to a file or something. Once you have the (much smaller) list of a few million collision candidates, you do another iteration over the whole data set, checking each one against only the collision candidates. The most memory-intensive part is the Bloom filter. You could probably get away with a Bloom filter size of 10 bits per entry or less. (If you want specific numbers, there are lots of online calculators to help you calibrate the size of a Bloom filter.) But given this is a one-off search, and you had a machine with enough RAM to find a collision, an ordinary hash-based set implementation is good enough and saves the most precious resource of all, developer time :)
- tialaramex 6y agoThis is clever. At the time we needed this machine anyway (this is way before "Cloud computing" was really a thing) but a few years earlier it would have been a good choice. We actually had most of the bloom filter code you'd need because we used a lot of Bloom Filters in that project. One of the very common queries that system had was "Hey do we know about random thing X?" for which the answer would often (but not always) be "No". So Bloom Filters enabled the system to be able to say definitively "Nope, I know nothing about X" a good fraction of the time without any further work. This actually hurt us in some third party benchmarks we ran for boasting, but helped in our real use case.