Analysis of DefaultConsistentHash.java

infinispan.distribution.DefaultconsistentHash.java

This is a implement of consistent hashing algorithm. In DefaultConsistentHash class, setCaches(List<Address caches) set up a nodes circle in positions(TreeMap<Integer,Address>) according to given nodes address hash code.

In hash processing,position is computered according to object address. The following listed is main implements of construction for Consistent Hashing circle

addresses = new ArrayList<Address>(caches);

// this list won't grow.

addresses.trimToSize();

positions = new TreeMap<Integer, Address>();

addressToHashIds = new HashMap<Address, Integer>();

for (Address a : addresses) {

int positionIndex = Math.abs(hash(a)) % HASH_SPACE;

// this is deterministic since the address list is ordered and the order is consistent across the grid

while (positions.containsKey(positionIndex)) positionIndex = positionIndex + 1 % HASH_SPACE;

positions.put(positionIndex, a);

// If address appears several times, take the lowest value to guarantee that

// at least the initial value and subsequent +1 values would end up in the same node

// TODO: Remove this check since https://jira.jboss.org/jira/browse/ISPN-428 contains a proper fix for this

if (!addressToHashIds.containsKey(a))

addressToHashIds.put(a, positionIndex);

}

addresses.clear();

// reorder addresses as per the positions.

for (Address a : positions.values()) addresses.add(a);

Fist step, setCache(List<Address> caches) implements Consistent Hashing algorithm that construct hashing circle. According to exsiting caches, Consistent Hashing circle is constructed. Second, locate() method provides cache's addresses by given object Key and replication count.

I will post the sequence chart later when I have free time.