数据库专题（五） ——Memcached技术

数据库专题（五）——Memcached技术

（原创内容，转载请注明来源，谢谢）

一、Slab分配算法保存数据

Memcached默认只能用1MB的存储空间，其在分配存储采用Slab算法，把1MB的固定大小内存划分成n块，称为一个slab页，每次向系统申请一个slab，并把其分为若干小块，称为chunk，分配给用户使用。

memcache设置每个chunk的大小共有40种，第一个chunk是80B，第二个开始每个是前面一个的1.25倍。但是为了更好利用空间，当chunk大小不是8的倍数时，会采用size+8-size%8，即通过略微增加chunk的值，使其保持在8的倍数。

当用户调用memcache存储数据时，slab会自动查找当前的trunk中，空闲的trunk且最接近待存储数据大小的值。

如下图所示：（来自网络）

二、删除机制

1、延时删除

当存储在memcache的数据过期时，不会被马上删除，而是每次在调用到key进行查找时，会先判断其过期时间，如果比当前时间早，再进行删除。

这样做的好处是节省cpu使用率，不用实时的去扫描存储的所有数据来判断是否要删除。

2、LRU算法淘汰数据

每次申请数据存储在memcache，都需要malloc一个地址空间。当memcache数据满，地址空间申请失败，则会触发删除数据的代码。删除旧数据采用的是LRU算法，即删除队列中队尾数据中三小时内没有被访问的数据。（3小时是在memcache的源码中写的）

每次访问memcache的key，被访问的key会被移到队列的头部，这样就保证尾部的都是较久没有被访问的数据。

三、多线程

1、并发

memcache使用多路复用I/O模型，即非阻塞的方式进行连接，先准备好的连接先执行。避免I/O被未准备好的进程阻塞。

memcache支持多线程，开启memcache服务器时，通过-t参数指定线程数量。通常数量设定为cpu内核数量，这避免系统的线程调度，保证每个内核有一个线程。

2、进程职责

在memcache内部，线程分为主线程和工作线程。如下图所示（来自网络）

主线程（mainthread）负责接收客户端的连接，并把连接分配给工作线程进行处理。工作线程（worker thread）处理客户端的连接请求。

主线程主要负责侦听客户端的连接（通过调用accept函数），其分配连接时（通过调用dispatch_conn_new函数），采用的是轮询的方式，每次把一个连接放到某个worker的队列中。

工作线程接收到主线程的信号后，会把队列上的客户端连接注册到libevent进行侦听（因此安装memcache服务器的前置条件是安装libevent），其侦听到客户端的读写事件后，调用相关的回掉函数进行处理（调用thread_libevent_process函数）。thread_libevent_process主要是从管道读取一个字节的数据，然后从队列中取得一个连接，并调用conn_new函数把链接注册到libevent进行侦听。

四、分布式memcache方案

当一台memcache服务器不足以满足要求，则需要布置多太服务器。因此，需要确定把数据保存在哪一台服务器上。可以采用普通Hash分布或一致性Hash分布。

1、普通Hash

functionmHash($key){
$md5 = substr(md5($key), 0, 8);
$seed = 31;
$hash = 0;
for($i=0;$i<8;$i++){
$hash =$hash*$seed+ord($md5($i));
$i++;
}
return $hash*0x7FFFFFFF;
}

即通过md5把key处理成32位字符串，取前八位，再进过hash处理成整数并返回，然后映射到一台memcache服务器。当有n台服务器时，则mHash($key)%n，根据结果分配到相应的服务器。

取数据时采用同样的key，同样的mHash，则可以获取到相应的数据。

2、一致性Hash

当服务器的数量是变动的时候，采用上述普通哈希则无法解决问题。

一致性哈希如下图所示：（来自网络）

一致性哈希共4个步骤：

1）将32位整数（0~232-1）模拟成一个圆环，0是头，232-1是结尾。

2）通过普通哈希（上述的mHash）把key处理成整数，即可以在第一步骤的环中找到相应的位置。

3）把memcache群映射到环上，用mhash函数处理memcache服务器使用的ip地址，以便把服务器也映射到环上。

4）把第二步的数据映射到第三步的服务器上。方法是沿圆环顺时针方向的key出发，直到遇到映射在上面的第一个服务器为止。

一致性哈希当发生移除服务器和新增服务器时，会有以下操作：

1）移除服务器

移除服务器时，假设移除server2，其顺时针下一个服务器是server3，则只需要把映射到server2的数据，相应的映射到server3上。

2）新增服务器

新增服务器时，假设新增server3，插入到server1和server2（顺时针靠前）之间，则只需要把映射到server2的数据中，数据位置在server3逆时针位置且在server1顺时针之前的数据，保存到server3上即可。

——written by linhxx 2017.08.09