Most distributed caching frameworks are based on some form of mapping of an object to a cache node. Such mappings are performed by a hash function. To understanding how to implement efficient caching, it is important to grasp the benefits of consistent hashing, argues Tom White in a recent article, Consistent Hashing.

While such hashing algorithms are likely implemented as part of a client of a caching library, such as memcached, developers need to still understanding how to write consistent hashing for their objects, writes White:

Consistent hashing is needed to avoid swamping your servers... The need for consistent hashing arose from limitations experienced while running collections of caching machines—web caches, for example. If you have a collection of n cache machines then a common way of load balancing across them is to put object o in cache machine number hash(o) mod n.

This works well until you add or remove cache machines (for whatever reason), for then n changes and every object is hashed to a new location. This can be catastrophic since the originating content servers are swamped with requests from the cache machines. It's as if the cache suddenly disappeared. Which it has, in a sense.

Consistent hashing is used to avoid that sort of situation, and to aid in the efficient distribution of objects to caches:

Consistently maps objects to the same cache machine, as far as is possible, at least... The hash function actually maps objects and caches to a number range. This should be familiar to every Java programmer - the hashCode method on Object returns an int, in order for consistent hashing to be effective it is important to have a hash function that mixes well. Most implementations of Object's hashCode do not mix well - for example, they typically produce a restricted number of small integer values... MD5 hashes are recommended here.

In the article, White discusses a popular algorithm and its Java implementation to provide consistent hashing for objects.

What sort of guidelines do you follow when defining the hashCode() methods of your classes?

class Point
{
   int x;
   int y;
 
   public int hashCode()
   {
      return x + (57 * y);
   }
}