5 Replies Latest reply on Sep 18, 2008 2:15 PM by genman

    memcached client/server

    genman

      JGroups came out with a demo memcached implementation in Java.

      So I was wondering why this wasn't ported or done in JBoss Cache yet.

      I'm thinking it'd be fairly trivial to write a cache loader for JBossCache to talk to memcached, using possibly http://code.google.com/p/spymemcached/ ... No need to reinvent this guy. It needs to be hosted in somebody's Maven repository I guess.

      The server -- couldn't that just be ported from Bela Ban's code?

        • 1. Re: memcached client/server
          belaban

          Not sure I'd use a cache loader for a memcached implementation in JBossCache. I would do it as follows:
          - Goal (like in JGroups' impl) is to have Java clients sit in the address space of the server, so no memcached protocol is required
          - The memcached protocol is implemented (for remote clients, or clients written in different languages) in a JBC-memcached server. Here, we can copy JGroups' implementation, or any server side impl (there aren't many though)
          - The server implementation consists of a configuration which replaces the ReplicationInterceptor with a different interceptor (maybe a subclass ?). That interceptor forwards calls to certain FQN to different servers, using consisten hashing over the FQN to always map the same FQN to the same JBC-memcached instance
          - L1 cache: the results could be stored in the JBC instance, so it would act as an L1 cache

          Hmm, maybe your CacheLoader thought is not such a bad idea ! The CacheLoader acts as L2 cache and uses consistent hashing to fetch items from given hosts, and JBC itself (in conjunction with evciction) acts as L1 cache...

          Whichever implementation we pick, it should fit into the architecture of Data Partitioning

          • 2. Re: memcached client/server
            genman

            There's probably some value in having a Memcached-talking CacheLoader as well, and fairly trivial to write. It might be good for testing the server, at least.

            One interesting thing that memcached does is allow for the specification of an eviction time per key. As a emulating server, I suppose that my ExpirationPolicy might come into play.

            Not sure consistent hashing really fits in with the Data Partitioning design since it seems to concern itself with load/data balancing and reliability.

            But I sense that data balancing is possible with consistent hashing. For instance, when a node joins or leaves, each existing instance would examine their tree and "move" any data rehashed for the new/existing member to that instance. And some measure of reliability certainly is possible with consistent hashing: Hash an Fqn to two nodes and store two copies.

            • 3. Re: memcached client/server
              belaban

              Yes, ExpirationPolicy would certainly be needed, compared to defining a policy for an entire region.

              Regarding consisten hashing: the Data Partitioning feature calls for metadata, replicated to all JBC instances, which keeps track of allocation of stripes to instances.
              However, as an alternative, as you mentioned, we could use consistent hashing, to define where data is placed in the cluster. This could also be used to derive the primary node and backup nodes for a given stripe, instead of using metadata.
              Interesting comparison: Google File System (GFS) uses metedata, but it is maintained by a single central server. However, this is not an issue as it can be reconstructed by consulting the cluster nodes.
              We have to think a bit more about whether to use consistent hashing, or metadata, to place data across a cluster. I suspect metadata gives us more flexibility in supporting more exotic setups. If we store local metadata in every node, then we don't have to replicate metadata across the cluster, but the (JGroups) coordinator could maintain it. When it goes down, the next-in-line takes over, soliciting metadata from all nodes...

              • 4. Re: memcached client/server
                manik

                My issue with the metadata approach is that it can lead to unnecessary traffic, and while this traffic is small, could be a scalability problem.

                I very much prefer the consistent hashing approach if we can make it work for us. Using two hash functions to map an Fqn to two different servers is one approach, but this is hard when you want > 1 backup copy.

                Regarding memcached in relation to JBC, I actually see JBC as a memcached server rather than a client. E.g., Bela's memcached server code could act as a "front end" to JBC, and instead of putting stuff in a CHM, it could put stuff into a JBC instance. This buys us:

                1. The ability to use different types of clients talking to JBC (any memcached client library should work)
                2. The ability to be colocated in-VM as well, for a more p2p-like setup

                To make this work we would need clients to be aware of the consistent hashing algo, so it could direct requests to the relevant server (as an optimisation), and for clients that don't do this (as well as colocated clients) the JBC instance would need a subclass of the ClusteredCacheLoader that has the consistent hashing algo. We then automatically have cache instances acting as L1 caches if they aren't the "host" cache for a particular fqn, and automatically would have L1 cache invalidation (assuming the cache uses INVALIDATION. REPLICATION would be pointless anyway in such a setup).


                • 5. 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 +
                   "";
                   }
                  
                  }