Skip links

A Tale of Two HashMaps, or the importance of reading developer docs

In this article we’ll show an example of the importance of knowing about Data Structures (HashMaps or Dictionaries in this case) and paying attention to contracts and documentation, with a real story.

Media Google Ads
Image by Megan Rexazin from Pixabay

We had an ads system (picture something like Google Ads) in an e-commerce site. And to make it simple, let’s say that we had 3 key endpoints:

  • One to retrieve ads
  • Other to count impressions (a pixel request placed by the retrieved ad)
  • The last one to count clicks and do the proper redirect

To count impressions, that endpoint should get an encrypted parameter, decrypt it, verify the (internal, decrypted) parameters with a signature, and then use those values impressions counting.

While the code that generated those links was deployed in servers that were readily updatable, the code that read those links (impressions counter) was deployed in an old monolithic system. Those servers were only deployable every 2 weeks.

  • Link generator –> in servers that could update
  • Link/impression reader –> in servers that couldn’t update
Servers Clusters
Photo by Manuel Geissinger from Pexels

When this code was released, both servers (clusters indeed, but let’s call them servers for simplification) were running JDK 1.5.

In a given moment the server which was part of the readily updatable ones, got updated to JDK 1.6, and at that point.. we lost something…

In the morning we were alerted by the abnormality of having 0 (zero) impressions. Fall that could not be attributed to anything organic, but a code issue.

So, what was happening?

HashMap implementation changes

Remember that I said we were creating those links with a big encrypted parameter? That had a signature mechanism that was analyzed by the impression reader server code, and if the signature (simply done by hashing) wasn’t correct, the impression was discarded.
So the code for the impression counter link was something like:

for (String key: parametersMap.keySet()) {
    appendParameter(key, parametersMap.get(key),paramsBuilder); // Appends parameter
    stringToHash += parametersMap.get(key); // append value for the string to hash to get a signature

// calculate the hash and add some salt
stringToHash += secret;

signature = calulateHash(stringToHash);

appendParameter("signature", signature, paramsBuilder); // Appends parameter

On the reader/impression counter side:

for (String key: parametersMap.keySet()) { // before this, this code put the parameters into a Map
    stringToHash += parametersMap.get(key);

// calculate the hash and add some salt
stringToHash += secret;

signatureToVerify = calulateHash(stringToHash);

Can you spot the error there? It happens that in JDK 1.6, there was a slight change in the hashing code in HashMap, which made another slight change in the order elements were placed in the internal hashtable (an array).

So at the point where the impression counter server did .keySet, it provided those keys/values in an original order (by JDK 1.5) while the new code that generated that, was delivering those values in a different order (by JDK 1.6).

Hash function comparison
How the HashMap#hash() function changed. (But this isn’t the exact change of this story, we just couldn’t find it)

Obviously the bug is that relying on that order from the HashMap to append and retrieve values was a violation of the HashMap contract (and Set for instance), where it is expressed that you shouldn’t rely on the HashMap keys order.

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Extracted from the HashMap class Javadoc

Developer’s quick solution to save the day

As the server that counted those impressions wasn’t available for an update (next code upload was scheduled for the next 2 weeks!), we had to do something on the ‘pixel generator’ with that link.

As the counter was expecting those parameters in a given order, we decided to use the old HashMap code, so we could get the same order to verify the signature.

The parametersMap object ended up being an instance of the HashMap15 class, for the sake of letting it sort those elements as the impression counter endpoint expected them to be.

Cleanup and conclusion

In a next release we did sort those keys before relying on the order and ditched that temporary class. (It wasn’t an elegant solution to keep).

So that’s the story of why we should know about data structures, contracts and reading docs… or maybe about minor bugs that could go unnoticed until big consequences happen. Have you ever had to resort to this kind of tricks to save the day and continue operations?

A Tale of Two Cities Book Cover Photo by Lisa from Pexels

Leave a comment