[jboss-dev-forums] [Design of JBossCache] - Re: memcached client/server

[genman]

ConsistentHashing allows you to replicate to as many servers as you want. Imagine a circle with dots representing "hashed server addresses". Then, pick a point, go clockwise/counterclockwise on the circle and find two or more unique instances.


  | package org.jboss.cache.util;
  | 
  | import java.util.Collection;
  | import java.util.Collections;
  | import java.util.HashSet;
  | import java.util.Set;
  | import java.util.SortedMap;
  | import java.util.TreeMap;
  | 
  | import org.jgroups.Address;
  | 
  | /**
  |  * Consistent hashing algorithm; see http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html
  |  * 
  |  * @param <T> type of nodes to use; consider {@link Address}
  |  */
  | public class ConsistentHash<T> {
  | 
  |     /**
  |      * Default (but overrideable) hash function.
  |      */
  |     public static class HashFunction {
  | 
  |         /**
  |          * Implementation from ConcurrentHashMap.
  |          * @param o object to cache
  |          * @return hopefully a well distributed hash code result
  |          */
  |         public int hash(Object o) {
  |             int i = o.hashCode();
  |             i += ~(i << 9);
  |             i ^= i >>> 14;
  |             i += i << 4;
  |             i ^= i >>> 10;
  |             return i;
  |         }
  | 
  |     }
  | 
  |     private final HashFunction hashFunction;
  |     private final int numberOfReplicas;
  |     private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
  | 
  |     public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
  |             Collection<T> nodes) {
  |         this.hashFunction = hashFunction;
  |         this.numberOfReplicas = numberOfReplicas;
  | 
  |         for (T node : nodes) {
  |             add(node);
  |         }
  |     }
  |     
  |     /**
  |      * Constructs a new ConsistentHash with default options.
  |      */
  |     public ConsistentHash() {
  |         this(new HashFunction(), 5, Collections.<T>emptyList());
  |     }
  | 
  |     /**
  |      * Adds a node.
  |      */
  |     public void add(T node) {
  |         for (int i = 0; i < numberOfReplicas; i++) {
  |             circle.put(hashFunction.hash(node.toString() + i), node);
  |         }
  |     }
  | 
  |     /**
  |      * Removes a node.
  |      */
  |     public void remove(T node) {
  |         for (int i = 0; i < numberOfReplicas; i++) {
  |             circle.remove(hashFunction.hash(node.toString() + i));
  |         }
  |     }
  | 
  |     /**
  |      * Returns N nodes for a key.
  |      */
  |     public Set<T> get(Object key, int count) {
  |         if (count <= 0)
  |             throw new IllegalArgumentException("count");
  |         if (key == null)
  |             throw new NullPointerException("key");
  |         if (circle.isEmpty()) {
  |             return Collections.emptySet();
  |         }
  |   // TODO bound the "count" to the number of instances
  |         Set<T> nodes = new HashSet<T>(count);
  |         int hash = hashFunction.hash(key);
  |         for (T node : circle.tailMap(hash).values()) {
  |             nodes.add(node);
  |             if (nodes.size() == count)
  |                 return nodes;
  |         }
  |         for (T node : circle.values()) {
  |             nodes.add(node);
  |             if (nodes.size() == count)
  |                 return nodes;
  |         }
  |         return nodes;
  |     }
  | 
  |     /**
  |      * Returns a debug <code>String</code>.
  |      */
  |     @Override
  |     public String toString()
  |     {
  |         return super.toString() +
  |             " numberOfReplicas=" + this.numberOfReplicas +
  |             " circle=" + this.circle +
  |             "";
  |     }
  | 
  | }
  | 

View the original post : http://www.jboss.com/index.html?module=bb&op=viewtopic&p=4177513#4177513

Reply to the post : http://www.jboss.com/index.html?module=bb&op=posting&mode=reply&p=4177513