分布式设计《初尝memcached》

浏览数：41 / 时间：2015年06月20日

之前听说过高性能的分布式缓存开源工具，但一直没有真正接触过，现在接触的产品中有用到过分布式缓存，所以决定一探究竟。memcached是一个优秀的开源的分布式缓存工具，也是目前比较火热的分布式缓存的解决方案雏形。memcached的服务端产品本身功能简洁，简单易用，但是玩法多种多样。但是事实上它是一个“伪分布式”解决方案，它本身并没有实现服务端分布式(服务端的memcached server之间是不能通信的)，所谓的分布式都是依靠客户端来实现，而目前市面上提供了客户端分布式实现的开源工具很多，在这里我主要以Spymemcached这个客户端实现为基础讲述一些memcached的原理和应用。

【原理说明】

之前提到了，memcached产品本身并未实现分布式，所以借助下列两幅网上流行的图片便可以直观的了解memcached的原理以及怎么玩分布式的。

1、存储(set)

假设memcached server有node1/node2/node3三个节点，现在应用程序需要存储"tokyo"/"test"这样一对键值对。memcached客户端接收应用程序传来的键值对"tokyo"/"test"，通过算法(文章尾部会介绍具体的算法细节)从服务器列表中选中了node1作为目标存储服务器，接着发送set指令命令node1执行存储任务。

图1 存储数据

2、获取(get)

假设应用程序现在需要获取键"tokyo"对应的值数据"test"，memcached客户端程序接收参数"tokyo"，通过同样的算法从服务器列表中选中node1，接着发送get指令命令node1获取键"tokyo"对应的值数据。

图2 获取数据

【使用场景】

在网上也看过一些前辈描述过一些关于使用场景的描述，我简单总结下大致就以下两点

1、从memcached设计初衷的角度来看，memcached可以减少网站数据库的开销。对于经常需要读取，而又不经常改变的数据完全可以放到memcached中。

2、分布式应用之间共享数据。举个例子，登陆系统和商品查询系统是独立部署，并且是集群的。用户登陆了登陆系统之后如何将登录信息与其他的业务系统(商品查询系统)共享信息，这时就可以使用memcached缓存登录信息，商品查询系统便可以从memcached中获取用户的登陆信息。

【客户端源码分析】

1、客户端调用

以Spymemcached客户端实现为例，下面贴一段客户端的简单应用代码。下载链接memcached client

package com.lvmama.memcached;
import java.net.InetSocketAddress;
import net.spy.memcached.MemcachedClient;
public class TestSpymemcached {
 public static void main(String[] args) throws Exception{
  MemcachedClient client = new MemcachedClient(new InetSocketAddress("127.0.0.1", 11211)); //创建连接
  client.set("name", 10, "tony"); //set数据
  Object name = client.get("name"); //get数据
  System.out.println("name:" + name);
 }
}

2、余数hash算法

实现类为ArrayModNodeLocator，将传入的参数k(键)，通过hash算法得出一个整数值，计算下memcached server的个数。拿着参数k的hash值对服务器节点的个数求余数。余数便是选中的服务器节点。

  public MemcachedNode getPrimary(String k) {
    return nodes[getServerForKey(k)]; 
  }

  private int getServerForKey(String key) {
    int rv = (int) (hashAlg.hash(key) % nodes.length);
    assert rv >= 0 : "Returned negative key for key " + key;
    assert rv < nodes.length : "Invalid server number " + rv + " for key "
        + key;
    return rv;
  }

3、consistent hash算法

算法原理见下图

第一步：将memcached服务器节点的hash值映射到一个0~2的32次方的环形数据结构上，存储方式为k(hash值)，v(服务器节点)；

第二步：将要保存的参数k计算hash值，并映射到环形数据结构中；

第三步：从参数k的hash值顺时针查找已映射的hash值，第一个hash值对应的服务器节点便是选中的目标存储服务器。

图 3 consistent hash算法

实现类为KetamaNodeLocator，代码结构比较简单：将要保存的k计算hash值作为参数传入getNodeForKey()方法，从hash值顺时针查找到剩余的环形数据结构tailMap，如果tailMap不为空则取tailMap中第一个已经映射hash值，如果tailMap为空则取整个环形数据结构ketamaNodes的第一个已经映射的hash值(从0开始)，取得hash值便可以找到对应的memcached服务器节点。

  public MemcachedNode getPrimary(final String k) {
    MemcachedNode rv = getNodeForKey(hashAlg.hash(k));
    assert rv != null : "Found no node for key " + k;
    return rv;
  }

  MemcachedNode getNodeForKey(long hash) {
    final MemcachedNode rv;
    if (!ketamaNodes.containsKey(hash)) {
      // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
      // in a lot of places, so I'm doing this myself.
      SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);
      if (tailMap.isEmpty()) {
        hash = getKetamaNodes().firstKey();
      } else {
        hash = tailMap.firstKey();
      }
    }
    rv = getKetamaNodes().get(hash);
    return rv;
  }

4、算法优劣比较

余数hash算法：当服务器节点存在增加或者减少时，get数据时求得的余数同set数据时求得的余数很可能就不是同一个值，这时便大大降低了缓存读取的命中率。

consistent hash算法：当服务器节点存在增加或者减少时，如图3增加了node5,只有node2~node5之间的hash值会受到影响，由原来存储时命中的node4变成获取数据时命中的node5，其余hash值都不会受到影响。所以命中率较高。

而且有些consistent hash算法的实现采用了虚拟节点的思想，使用一般的hash函数会使得服务器节点的映射分布的不均匀，因此可以为每个物理服务器节点分配100~200虚拟映射点，这样便可最大限度的减少节点分布不均的情况发生。

初尝memcached,如有描述有误，欢迎拍砖哈！后续会写memcached服务端的内存模型，内存管理，源码分析等文档，欢迎大家一起探讨！