memcache proxy之memagent介绍分析

1、和每个memcache server保持多个长连接，效果是减少memcache server保持的连接数量及创建销毁连接的开销。不过，memcache本身就支持大并发连接，这个功能也就没什么特别的说道。

2、支持memcache的binary协议命令，实现请求的转发。

3、和memcache一样，基于libevent的事件驱动来处理IO。

4、支持ketama 的一致性hash算法。

5、支持memcache backup集群，当memcache集群有机器挂了，memagent会将get请求转向memcache backup集群。这个功能对于cache的稳定性要求高的场景下会有用武之地。

就提供的功能而言，memagent是个很简单的东西。对于较大的memcache集群，可以考虑搭一套memagent作为proxy使用。

实现分析
1、我得到memagent版本是0.5。除去一致性hash算法ketama的代码，memagent的代码都在magent.c文件中，代码总行数2000多行。稍微拿出半个晚上，就能把这份代码分析得差不多了。

2、memagent像memcache一样，使用了libevent来驱动状态及处理。Libevent是个很适合于事件驱动（最典型的就是网络 IO事件）的场景。像memagent，对于client端的一个请求，它既要处理client端的网络IO，又要处理server端的网络IO，还有可 能处理back server的网络IO，一个流程下来就触发了多达6、7次的网络IO事件。

3、memagent是单进程单线程程序，因为它的工作主要就是接受请求、对请求稍作解析后转发请求，所以逻辑上较为简单，最多的也就是内存拷贝工作，采用单进程单线程也就足够了。

4、memagent的事件回调函数分别是server_accept、drive_client、 drive_memcached_server、drive_backup_server。这4个回调函数的功能也很明显，在drive_client、 drive_memcached_server和drive_backup_server也分别涉及到读写处理的状态机机制，这部分代码涉及到协议解析及 IO处理，代码细节也是琐碎繁杂的很。 基本的过程是：

1）memagent解析出client端的数据（主要是命令类型和key），向映射到的memcache server发送数据，如果memcache server连接不上，memagent会向backup集群（如果设置的话）发送数据。

2）在得到memcache server返回的数据后，memagent还是需要解析，如果这段时间memcache server返回失败，memagent还会再向backup集群请求数据。

3）最后，memagent将数据返回给client。

5、对于backup集群，如果配置了，memagent每次提交操作都会发给backup集群。在get某个memcache server失败时会将向backup集群再请求一遍。

6、对于gets命令，memagent对批量的每个key是单独和memcache server交互的。这块我觉得还可优化，可以合并映射到同一个memcache server的key在发往server的一个请求中批量处理。

7、无论是读client数据还是读server端数据，memagent都是不知道这个请求中到底有多少字节的数据，所以读时首先调用 ioctl(fd, FIONREAD, &toread)函数计算出IO buffer中已经收到的网络字节数据，再对收到的数据做分析确定是否需要继续read。这个技巧在不知道数据包头大小的情况下采用的手段。

8、再说一个实现的小细节。对于event_set的回调函数原型，对于不使用的参数可以通过调用宏#define UNUSED(x) ( (void)(x) )来解决gcc在开-Wall时的报错，我之前看到有文章说是用#pragma也行，不过我没试成功

一致性hash算法
对于memcache客户端就Cache key映射到哪个memcache server的选择算法，最简单的莫过于根据key计算出的hash值取count(memcache server)的余数。对于小的memcache集群或者cache集群整体挂掉不会对服务产生严重影响的情况，这种映射方法就简单实用。

当然，更好的选择是一致性hash算法。该算法的效果是减少或增加一个memcache节点，只会影响到整个集群的1/n的数据。在实现方法上，主要有两种：

1、将memcache物理节点均匀地分布在整数范围构成的hash环。当增加一个节点时，可以将该节点插入环上的两个节点之间，这样只会失效 1/2n的数据，但会使hash环变得不均衡；另一种方法是，重新分布memcache节点在hash环的位置，这样每个节点的数据都会有些缺失，但缺失 的总和是一个节点的数据范围。

2、引入虚拟节点的思想，将一个memcache物理节点散落在hash环上的多个虚拟节点，这在均衡性方法效果会更好些。当然，查找的算法复杂度也由O(1)提高到log(N)。Ketama 算法是实现这个思想的第一个也是用得很多的实现，可以从
[url]http://www.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients [/url]
得到这个算法的多语言版本实现。

Memagent使用的一致性hash算法实现就是Ketama，但Memagent在代码方面做了简化修改。Ketama的两个核心数据结构是：

struct dot {   
    
   unsigned int point;// unsigned int范围内的某个点   
    
   int srvid;//memcache server id   
    
};   
    
struct ketama {   
    
   unsigned int numpoints;// 一致性hash的虚拟节点数   
    
   struct dot *dot;//一致性hash的虚拟节点列表   
    
   int count;//memcache server个数   
    
   char **name;// 各memcache server名称数组   
    
   int *weight;// 各memcache server权重，实际都是一样的   
    
   int totalweight;//权重总和   
    
};  

struct dot结构表示hash环上一个虚拟节点，struct ketama是算法的全局性数据结构。Ketama 算法涉及到两个函数是：

int create_ketama(struct ketama *ring, int step) 

Ring由Memagent之前根据memcache server集群信息构造而来，step取值为500，函数内部再乘以4，表示一个memcache server在hash环上有2000个虚拟节点。
计算虚拟节点的取值及对应的server id的方法如下：

for (i = 0; i < ring->count; i ++) {   
    pct = (float) ring->weight[i] / (float) ring->totalweight;   
    ks = (int) floorf(pct * step *(float) ring->count); /* divide by 4 for 4 part */  
    for (k = 0; k < ks; k ++) {   
        snprintf(temp, 255, "%s-%d", ring->name[i], k);   
        ketama_md5_digest(temp, digest);   
        for (h = 0; h < 4; h ++) {   
                dot[cont].point = ( digest[3+h*4] << 24 ) | ( digest[2+h*4] << 16 )   
                        | ( digest[1+h*4] <<  8 ) | digest[h*4];   
                dot[cont].srvid = i;   
                cont ++;   
        }   
    }   
}  

最后会对得到的dot列表针对point大小做排序处理，以便get_server时的二分查找。

源码copy to clipboard打印？
int get_server(struct ketama *, const char *); 

int get_server(struct ketama *, const char *);这个函数就是根据key从struct ketama结构中找到对应的memcache server index。Cache key的hash值计算使用的是16位的md5算法。根据key的hash值查找对应在hash环上的位置，采用的是二分查找。
小结
如果你只想要个简单实用的memcache proxy，memagent是个不错的选择。当然，memcache proxy可以做的工作也可以更多，就像另一个memcache proxy实现moxi（http://labs.northscale.com/moxi/）提供了更为丰富的功能，我会在接下来的文章中继续介绍moxi。

转帖自：
http://www.kafka0102.com/2010/01/9.html