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 :)
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.
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..
Sometimes it helps to write a doc afterwards to get my thoughts in order and decide if it's worth sharing.
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.
Of course, sometimes getting verisimilar test cases is difficult enough that you judge it not worth the effort over mocking it up and dealing with any issues with the mockup, foreseen and unforeseen.
A test handing a hash collision is not a test of the hashing algorithm so you should be able to switch out the algorithm to something super predictable. This isn’t a discussion about mocking frameworks - you should be able to do with by just plugging in a different hash implementation when you construct the test.
Also I can employ a $75k - $100k/year engineer and say follow this protocol for testing. If I want someone who can optimize test case 100% of the time with zero mistakes ever then I might have to pay $150k - $200k / year.
Anyone who demanded the real hashing algorithm in this case doesn’t understand how hash collisions work and what problems you need to solve when using hashing. Your “100% accurate test case” serves very little value.
It’s the same as requiring a real person perform the checkout workflow in your shopping cart integration tests. It’s “100% accurate” but it’s a massive waste of resources and provides terrible coverage of the many other edge cases.
If we wanted to change how the hash is calculated all extant instances of the system need to dump to backups, then be painstakingly restored after updating. Possible, but certainly not something you'd be doing for giggles.
> 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?
Personally, I see tests as not just a way to prevent bugs, but as a way to learn about the system being tested—both how it behaves now and, continually, how it behaves in future iterations. In this specific case, understanding what happens if two URIs hash to the same value even if they don't "really" do that is an important bit of information: it tells us not only what would happen with a real hash collision but also how our system would behave if there were a bug either in the hashing algorithm itself or in the code that connects the hashing algorithm to the component that uses the hashes.
What happens if we introduce a caching layer between where the hash is generated and where it's used, and there's a cache invalidation bug? I don't know how realistic that is in this specific hypothetical, but I'm sure there are other performance optimizations with the same bug potential that I'm not even thinking of. Changes like that can lead to absolute debugging nightmares! Testing even "impossible" edge cases helps catch this in a systematic way, without needing full knowledge of which conditions might matter.
Of course, none of this talks to the trade-off you pointed out: test code does have a real cost. That is absolutely something to consider. I just don't think the answer is to draw a hard line at "don't test situations that can't come up in production"—and, perhaps naively, I think the "real" solution is less about deciding what is and isn't worth testing and more about reducing the costs of testing more. Write application code in a way that's easy to test and treat your test code as code—keep it clean, include comments, and invest time in setup and tooling to make your tests as easy to write and maintain as possible.
Defense in depth is regarding layering different types of security, not targeted testing.
That’s understating it. It’s incompetence because it’s an excuse to not test a huge surface area of edge cases.
I've heard this before, but never actually had that problem with fakes in practise. Where can I read more about it?
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.
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.
(I can sympathize with both approaches and don’t think either one is better.)
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.
Agree. Not an integration test. If it has mocks in it, it is not testing the INTEGRATION of/between components.
Mocks are for Unit tests. Where you want to isolate testing one single UNIT from all the other crap it integrates with (which have their own unit tests) After all these unit tests run, you test the whole shebang together with integration tests.
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.
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?
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).
Oechslin improved on Hellman's idea to make "Rainbow Tables" by sightly perturbing the reduction function with the depth, so that collisions are fleeting unless they also coincidentally happen in the same position on a hash chain, this makes his Rainbow Table far more efficient/ reliable for the same pre-computation effort and it produces the "rainbow" picture in his slide deck.
For my purpose Oechslin's improvement was irrelevant of course because I actually wanted collisions.
But memory fades, it is possible either that I got lucky, that I actually had 16GB of RAM, or that I made some minor efficiency improvements that were enough to make it work.
So I just wrote code to mint nonsense URIs for our system based on a small integer seed (like 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.