rackerlabs/repose — pull request #785 by dmnjohns (2013-11-08 17:41:46+00:00)
Title: D-16092 Eliminate Cache ID Collissions

I'd like to thank Richard for identifying this defect and proposing two implementations that would fix it! As for why I choose to stick with string concatenation over the exclusive or combination method, well... there were a few considerations.

The XOR method would have given us generally shorter cache IDs (since the cache ID would be formed from a single int value). There would, however, still be concerns about collisions. Granted we have the entire integer space to use, not only is it still technically limited, but it is possible to cause collisions since we are confining entropy to a single integer. That is, combining multiple hashes into a single integer means that we could have a pattern that resolves to the same cache ID as a different pattern XOR'd with multiple capture groups (although it would be unlikely).

Going the string concatenation route (with a delimiter between capture groups), we are only bounded by memory (since strings can be arbitrarily long? very long, at least). The delimiter allows us to avoid collisions that may be caused by variable length integers (again, unlikely) since the ':' character will never be returned from the call to String.valueOf(int). We have (relative) assurance that hashes are unique, and thus, our cache ID should be unique (formed by concatenating a unique pattern hash with unique capture group hashes).

Note that while using a non-hashed pattern should provide the same guarantees as a hashed one. In fact, hashing the pattern limits the pattern space to the integer space (as discussed above) but it also provides a generally shorter string that the pattern itself. I choose to hash the pattern for that reason, and for the sake of consistency in the method.