Shahzad Bhatti

September 22, 2010

An implementation of Virtual Node Router with Consistent Hash algorithm

Filed under: Java — admin @ 1:02 pm

Since the Dynamo paper, published a few years ago, DHTs and consistent hash have become mainstream. Here is my implementation of a virtual node router that uses consistent hash algorithm for splitting requests to the virtual nodes:

 import java.nio.ByteBuffer;
 import java.security.MessageDigest;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.SortedMap;
 import java.util.TreeMap;
 
 public class VirtualNodeRouter {
     interface HashCalculator {
         long calculateHash(String key);
     }
 
     private static class VirtualNode {
         final String nodeName;
         final int replicaNumber;
 
         VirtualNode(final String nodeName, final int replicaNumber) {
             this.nodeName = nodeName.toLowerCase();
             this.replicaNumber = replicaNumber;
         }
 
         boolean matches(String host) {
             return nodeName.equalsIgnoreCase(host);
         }
 
         @Override
         public String toString() {
             return nodeName + ":" + replicaNumber;
         }
     }
 
     private final HashCalculator hashFunction;
     private final SortedMap<Long, VirtualNode> virtualNodePoolByHash = new TreeMap<Long, VirtualNode>(
             new Comparator<Long>() {
                 public int compare(Long i, Long j) {
                     if (i > j) {
                         return 1;
                     } else if (i < j) {
                         return -1;
                     } else {
                         return 0;
                     }
                 }
             });
 
     public VirtualNodeRouter() {
         this(new HashCalculator() {
             public long calculateHash(String key) {
                 try {
                     MessageDigest sha1 = MessageDigest.getInstance("SHA1");
                     sha1.update(key.getBytes());
                     byte[] digest = sha1.digest();
                     return bytesToLong(digest);
                 } catch (Exception e) {
                     throw new RuntimeException(e);
                 }
             }
         });
     }
 
     public VirtualNodeRouter(final HashCalculator f) {
         this.hashFunction = f;
     }
 
     /**
      * Adds a node with one replica
      * 
      * @param node
      *            - node name
      */
     public void add(String node) {
         add(node, 1);
     }
 
     /**
      * Adds a node to the available pool
      * 
      * @param node
      *            - node name
      * @param replicas
      *            - # of replicas - increase # of replicas based on the
      *            computing power of the machine
      */
     public void add(String node, int replicas) {
         // Note: You can call this method incrementally by adding more replicas,
         // so that you don't cause DOS on
         // your own services
         int existingReplicas = getReplicas(node);
 
         for (int i = 0; i < replicas; i++) {
             VirtualNode virtualNode = new VirtualNode(node, i
                     + existingReplicas);
             virtualNodePoolByHash.put(hashFunction.calculateHash(virtualNode
                     .toString()), virtualNode);
         }
     }
 
     /**
      * remove the node from available pool
      * 
      * @param node
      */
     public void remove(String node) {
         Iterator<Long> it = virtualNodePoolByHash.keySet().iterator();
         while (it.hasNext()) {
             Long key = it.next();
             VirtualNode virtualNode = virtualNodePoolByHash.get(key);
             if (virtualNode.matches(node)) {
                 it.remove();
             }
         }
     }
 
     public String getNode(String key) {
         if (virtualNodePoolByHash.isEmpty()) {
             return null;
         }
         long hash = hashFunction.calculateHash(key);
         for (Map.Entry<Long, VirtualNode> e : virtualNodePoolByHash.entrySet()) {
             if (hash < e.getKey()) {
                 return e.getValue().nodeName;
             }
         }
         SortedMap<Long, VirtualNode> tailMap = virtualNodePoolByHash
                 .tailMap(hash);
         hash = tailMap.isEmpty() ? virtualNodePoolByHash.firstKey() : tailMap
                 .firstKey();
         return virtualNodePoolByHash.get(hash).nodeName;
     }
 
     public void dump() {
         for (Map.Entry<Long, VirtualNode> e : virtualNodePoolByHash.entrySet()) {
             System.out.println("  " + e.getKey() + " => " + e.getValue());
         }
     }
 
     public int getReplicas(String nodeName) {
         int replicas = 0;
         for (VirtualNode node : virtualNodePoolByHash.values()) {
             if (node.matches(nodeName)) {
                 replicas++;
             }
         }
         return replicas;
     }
 
     private static long bytesToLong(byte[] b) {
         ByteBuffer bb = ByteBuffer.wrap(b);
         return bb.getLong();
     }
 }
 

The virtual nodes are added by specifying the node name and the number of replicas. You can add more virtual nodes for the more powerful machines than the low-end machines. You can call remove method when the node goes down or is unavailable. The getNode is called when a request needs to be routed. For example, if you are caching results of a service, you can use the key of cache to find the virtual node and then store the cache value at that node. You can read following resources to learn more about the consistent hash algorithm:



September 16, 2010

My impression of Diaspora codebase

Filed under: Computing — admin @ 5:07 pm

I briefly reviewed the Diaspora source code, which is all written in Ruby on Rails 3.0. Here are my initial thoughts on the codebase:

What I liked:

  • It’s all open source — YES!
  • Diaspora uses latest Rails 3.0 APIs such as global respond_to in controllers, thin controllers, and fat models with new query APIs. The code uses RSpec for tests and Factory-Girl for creating test objects instead of fixtures, which are much easily managed. There are a few Selenium tests, but most of the tests are in RSpec.
  • Diaspora is built using latest technologies and standards such as PKI (OpenSSL), HTML5, VCard, Websockets, Microformat, XRDS, PubSubHubbub along with popular libraries such as EventMachine, HAML, jQuery, Fancybox, Sprinkle, Bundler, Blueprint, etc.
  • Deployment scripts and documentation – Though, there isn’t any documentation on overall architecture or comments in the code, but I found installation documentation very helpful. Also, the deployment rake tasks and configurations are all included in the source code.

What I disliked:

Though, I found the code to be fairly easy to read and consistent in style I found following problems related to the performance, scalability and modularity.

  • Service API – Diaspora uses Rails controller for serving HTML as well as JSON, XML and XRDS requests but I would have preferred separate services for the API with much more defined contract.
  • Pagination – I found sporadic use of pagination in the code but a number of classes use Rails’ builtin relationships without any pagination. It’s like when you ask for banana you get the gorilla holding the banana. In my experience, this has been problem with all O/R mapping tools, which give you nice syntax for fetching related objects until your server runs out of memory or your database dies on you.
  • Before/after filters – I found a number of such filters in the code, which I have found to be another common issue with the scalability when before/after filters require a lot of overhead.
  • Asynchronous Messaging – I didn’t see any use of asynchronous messaging as a lot of requests such as adding/removing a friend can be done asynchronous.
  • Modularity – Diaspora code uses modules and models for the business logic, but I found a couple of models such as user to be too big, which can be divided into suitable modules.
  • MongoDB – I have nothing against MongoDB but I found a lot of code depends on MongoDB. I would have preferred using data access service instead, which completely encapsulates underlying storage technology and allows you to replace it without modifying all the code.

Conclusion

Despite the Knuth’s advice: “Forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil,” you need the architecture for scalability and performance when you are building the platform to replace Facebook. As social networking tools depend much more on Network effects or Metcalfe’s law instead of best technology, I hope early release of the software allows it to capture more users who use it. I was somewhat disappointed that identi.ca has not caught much attraction as open source alternative to Twitter. And I hope that Diaspora succeeds in becoming a good alternative to Facebook.

Powered by WordPress