naotang的测试成长空间，记录工作中的问题，学习中的心得。个人网站：www.naotang.com

Memcached了解

上一篇 / 下一篇 2007-11-16 12:44:50 / 个人分类：Web测试

51Testing软件测试网*y3wN;Y!mpo`

Memcached是danga.com（运营LiveJournal的技术团队）开发的一套分布式内存对象缓存系统，用于在动态系统中减少数据库负载，提升性能

a] B`xc zuO2m01、 Memcached是什么

很多人把它当作和SharedMemory那种形式的存储载体来使用，虽然memcached使用了同样的“Key=>Value”方式组织数据，但是它和共享内存、APC（Alternative PHP Cache）等本地缓存有非常大的区别。Memcached是分布式的，也就是说它不是本地的。它基于网络连接（当然它也可以使用localhost）方式完成服务，本身它是一个独立于应用的程序或守护进程（Daemon方式）。

Memcached使用libevent库实现网络连接服务，理论上可以处理无限多的连接，但是它和Apache不同，它更多的时候是面向稳定的持续连接的，所以它实际的并发能力是有限制的。在保守情况下memcached的最大同时连接数为200，这和Linux线程能力有关系，这个数值是可以调整的。Memcached内存使用方式也和APC不同。APC是基于共享内存和MMAP的，memcachd有自己的内存分配算法和管理方式，它和共享内存没有关系，也没有共享内存的限制，通常情况下，每个memcached进程可以管理2GB的内存空间，如果需要更多的空间，可以增加进程数。

4t ]FrT};M Ia0

2、 Memcached适合什么场合

$z]'n TxT'q3\#o0

memcached不是万能的，它也不是适用在所有场合。

Memcached是“分布式”的内存对象缓存系统，那么就是说，那些不需要“分布”的，不需要共享的，或者干脆规模小到只有一台服务器的应用，memcached不会带来任何好处，相反还会拖慢系统效率，因为网络连接同样需要资源，即使是UNIX本地连接也一样。在我之前的测试数据中显示，memcached本地读写速度要比直接PHP内存数组慢几十倍，而APC、共享内存方式都和直接数组差不多。可见，如果只是本地级缓存，使用memcached是非常不划算的。

Memcached在很多时候都是作为数据库前端cache使用的。因为它比数据库少了很多SQL解析、磁盘操作等开销，而且它是使用内存来管理数据的，所以它可以提供比直接读取数据库更好的性能，在大型系统中，访问同样的数据是很频繁的，memcached可以大大降低数据库压力，使系统执行效率提升。另外，memcached也经常作为服务器之间数据共享的存储媒介，例如在SSO系统中保存系统单点登陆状态的数据就可以保存在memcached中，被多个应用共享。

需要注意的是，memcached使用内存管理数据，所以它是易失的，当服务器重启，或者memcached进程中止，数据便会丢失，所以memcached不能用来持久保存数据。很多人的错误理解，memcached的性能非常好，好到了内存和硬盘的对比程度，其实memcached使用内存并不会得到成百上千的读写速度提高，它的实际瓶颈在于网络连接，它和使用磁盘的数据库系统相比，好处在于它本身非常“轻”，因为没有过多的开销和直接的读写方式，它可以轻松应付非常大的数据交换量，所以经常会出现两条千兆网络带宽都满负荷了，memcached进程本身并不占用多少CPU资源的情况。

3、 Memcached的工作机制

o2aa7z.HYwRFs0通过在内存中开辟一块区域来维持一个大的hash表来加快页面访问速度，和数据库是独立的。允许多个server通过网络形成一个大的hash，用户不必关心数据存放在哪，只调用相关接口就可以了。存放在内存的数据通过LRU算法进行淘汰出内存。同时可以通过删除和设置失效时间来淘汰存放在内存的数据。【注：LRU(Least recently used最近最少算法)：当内存的剩余的可用空间不够时，缓冲区尽可能的先保留使用者最常使用的数据，换句话说就是优先清除较不常使用的数据，并释放其空间】

4、 Memcached的工作方式51Testing软件测试网j3XFe.{0k|

首先，memcached是以守护程序方式运行于一个或多个服务器中，随时接受客户端的连接操作，客户端可以由各种语言编写，目前已知的客户端API包括Perl/PHP/Python/Ruby/Java/C#/C等等。PHP等客户端在与memcached服务建立连接之后，开始存取对象（如图Fig 2），每个被存取的对象都有一个唯一的标志符key，存取操作均通过这个key进行，保存到memcached中的对象实际上是放置在内存中的，并不是保存在cache文件中的，这也是为什么memcached能够如此高效快捷的原因。注意，memcached使用内存管理数据，所以它是易失的，当服务器重启，或者memcached进程中止，数据便会消失，所以memcached不能用来长久保存数据。

用户访问网页时，查看memcached中是否有当前用户的session数据，使用session_id（）做为唯一标识符；如果数据存在，则直接返回，如果不存在，再进行数据库连接，获取session数据，并将此数据保存到memcached中，供下次使用。

-v3@ z$]dI;u(f0

以下的部分中，读者最好能准备一份memcached的源代码。
]!lqD&U;Hj#c0Memcached是传统的网络服务程序，如果启动的时候使用了-d参数，它会以守护进程的方式执行。创建守护进程由daemon.c完成，这个程序只有一个daemon函数，这个函数很简单（如无特殊说明，代码以1.2.1为准）：51Testing软件测试网2@qcB/}}3d

51Testing软件测试网)C]?4g7e6YG

CODE:
#include
#include
#include

int
daemon(nochdir, noclose)
int nochdir, noclose;
{
int fd;
switch (fork()) {
case -1:
      return (-1);
case 0:
      break;
default:
      _exit(0);
}
if (setsid() == -1)
      return (-1);
if (!nochdir)
      (void)chdir("/");
if (!noclose && (fd = open("/dev/null", O_RDWR, 0)) != -1) {
      (void)dup2(fd, STDIN_FILENO);
      (void)dup2(fd, STDOUT_FILENO);
      (void)dup2(fd, STDERR_FILENO);
      if (fd > STDERR_FILENO)
         (void)close(fd);
}
return (0);
}

这个函数 fork 了整个进程之后，父进程就退出，接着重新定位 STDIN 、 STDOUT 、 STDERR 到空设备， daemon 就建立成功了。
Memcached 本身的启动过程，在 memcached.c 的 main 函数中顺序如下：
1 、调用 settings_init() 设定初始化参数
2 、从启动命令中读取参数来设置 setting 值
3 、设定 LIMIT 参数
4 、开始网络 socket 监听（如果非 socketpath 存在）（ 1.2 之后支持 UDP 方式）
5 、检查用户身份（ Memcached 不允许 root 身份启动）
6 、如果有 socketpath 存在，开启 UNIX 本地连接（Sock 管道）
7 、如果以 -d 方式启动，创建守护进程（如上调用 daemon 函数）
8 、初始化 item 、 event 、状态信息、 hash 、连接、 slab
9 、如设置中 managed 生效，创建 bucket 数组
10 、检查是否需要锁定内存页
11 、初始化信号、连接、删除队列
12 、如果 daemon 方式，处理进程 ID
13 、event 开始，启动过程结束， main 函数进入循环。
在 daemon 方式中，因为 stderr 已经被定向到黑洞，所以不会反馈执行中的可见错误信息。

memcached.c 的主循环函数是 drive_machine ，传入参数是指向当前的连接的结构指针，根据 state 成员的状态来决定动作。
Memcached 使用一套自定义的协议完成数据交换，它的 protocol 文档可以参考： http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt
在API中，换行符号统一为\r\n

)\_pLT}-}P;b0

5、 Memcached的内存管理方式

Memcached有一个很有特色的内存管理方式，为了提高效率，它使用预申请和分组的方式管理内存空间，而并不是每次需要写入数据的时候去malloc，删除数据的时候free一个指针。Memcached使用slab->chunk的组织方式管理内存。

1.1和1.2的slabs.c中的slab空间划分算法有一些不同，后面会分别介绍。

2^D6A?'[w@A@|i$A0

Slab可以理解为一个内存块，一个slab是memcached一次申请内存的最小单位，在memcached中，一个slab的大小默认为1048576字节（1MB），所以memcached都是整MB的使用内存。每一个slab被划分为若干个chunk，每个chunk里保存一个item，每个item同时包含了item结构体、key和value（注意在memcached中的value是只有字符串的）。slab按照自己的id分别组成链表，这些链表又按id挂在一个slabclass数组上，整个结构看起来有点像二维数组。slabclass的长度在1.1中是21，在1.2中是200。

51Testing软件测试网2CI\r6}Bn

slab有一个初始chunk大小，1.1中是1字节，1.2中是80字节，1.2中有一个factor值，默认为1.25

在1.1中，chunk大小表示为初始大小*2^n，n为classid，即：id为0的slab，每chunk大小1字节，id为1的slab，每chunk大小2字节，id为2的slab，每chunk大小4字节……id为20的slab，每chunk大小为1MB，就是说id为20的slab里只有一个chunk：

CODE:

#VDh@F.K:@:Tz051Testing软件测试网$?'n`3lAn

void slabs_init(size_t limit) {
int i;
int size=1;

Z I!`8|.c0

mem_limit = limit;
for(i=0; i<=POWER_LARGEST; i++, size*=2) {
      slabclass[i].size = size;
      slabclass[i].perslab = POWER_BLOCK / size;
      slabclass[i].slots = 0;
      slabclass[i].sl_curr = slabclass[i].sl_total = slabclass[i].slabs = 0;
      slabclass[i].end_page_ptr = 0;
      slabclass[i].end_page_free = 0;
      slabclass[i].slab_list = 0;
      slabclass[i].list_size = 0;
      slabclass[i].killing = 0;
}
/* for the test suite:  faking of how much we've already malloc'd */
{
      char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
      if (t_initial_malloc) {
         mem_malloced = atol(getenv("T_MEMD_INITIAL_MALLOC"));
      }
}
/* pre-allocate slabs by default, unless the environment variable
   for testing is set to something non-zero */
{
      char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
      if (!pre_alloc || atoi(pre_alloc)) {
         slabs_preallocate(limit / POWER_BLOCK);
      }
}
}

在1.2中，chunk大小表示为初始大小*f^n，f为factor，在memcached.c中定义，n为classid，同时，201个头不是全部都要初始化的，因为factor可变，初始化只循环到计算出的大小达到slab大小的一半为止，而且它是从id1开始的，即：id为1的slab，每chunk大小80字节，id为2的slab，每chunk大小80*f，id为3的slab，每chunk大小80*f^2，初始化大小有一个修正值CHUNK_ALIGN_BYTES，用来保证n-byte排列（保证结果是CHUNK_ALIGN_BYTES的整倍数）。这样，在标准情况下，memcached1.2会初始化到id40，这个slab中每个chunk大小为504692，每个slab中有两个chunk。最后，slab_init函数会在最后补足一个id41，它是整块的，也就是这个slab中只有一个1MB大的chunk：

51Testing软件测试网9M D2@6M[(F

CODE:

void slabs_init(size_t limit, double factor) {
int i = POWER_SMALLEST - 1;
unsigned int size = sizeof(item) + settings.chunk_size;
/* Factor of 2.0 means use the default memcached behavīor */
if (factor == 2.0 && size < 128)
      size = 128;
mem_limit = limit;
memset(slabclass, 0, sizeof(slabclass));
while (++i < POWER_LARGEST && size <= POWER_BLOCK / 2) {
      /* Make sure items are always n-byte aligned */
      if (size % CHUNK_ALIGN_BYTES)
         size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
      slabclass[i].size = size;
      slabclass[i].perslab = POWER_BLOCK / slabclass[i].size;
      size *= factor;
      if (settings.verbose > 1) {
         fprintf(stderr, "slab class %3d: chunk size %6d perslab %5d\n",
                  i, slabclass[i].size, slabclass[i].perslab);
      }
}
power_largest = i;
slabclass[power_largest].size = POWER_BLOCK;
slabclass[power_largest].perslab = 1;

/* for the test suite:  faking of how much we've already malloc'd */
{
      char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
      if (t_initial_malloc) {
         mem_malloced = atol(getenv("T_MEMD_INITIAL_MALLOC"));
      }
}
#ifndef DONT_PREALLOC_SLABS
{
      char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
      if (!pre_alloc || atoi(pre_alloc)) {
         slabs_preallocate(limit / POWER_BLOCK);
      }
}
#endif
}

Xr v'cH,MElM1V0

由上可以看出，memcached的内存分配是有冗余的，当一个slab不能被它所拥有的chunk大小整除时，slab尾部剩余的空间就被丢弃了，如id40中，两个chunk占用了1009384字节，这个slab一共有1MB，那么就有39192字节被浪费了。

Memcached使用这种方式来分配内存，是为了可以快速的通过item长度定位出slab的classid，有一点类似hash，因为item的长度是可以计算的，比如一个item的长度是300字节，在1.2中就可以得到它应该保存在id7的slab中，因为按照上面的计算方法，id6的chunk大小是252字节，id7的chunk大小是316字节，id8的chunk大小是396字节，表示所有252到316字节的item都应该保存在id7中。同理，在1.1中，也可以计算得到它出于256和512之间，应该放在chunk_size为512的id9中(32位系统）。

Memcached初始化的时候，会初始化slab（前面可以看到，在main函数中调用了slabs_init()）。它会在slabs_init()中检查一个常量DONT_PREALLOC_SLABS，如果这个没有被定义，说明使用预分配内存方式初始化slab，这样在所有已经定义过的slabclass中，每一个id创建一个slab。这样就表示，1.2在默认的环境中启动进程后要分配41MB的slab空间，在这个过程里，memcached的第二个内存冗余发生了，因为有可能一个id根本没有被使用过，但是它也默认申请了一个slab，每个slab会用掉1MB内存

,G:_gO9ore0

当一个slab用光后，又有新的item要插入这个id，那么它就会重新申请新的slab，申请新的slab时，对应id的slab链表就要增长，这个链表是成倍增长的，在函数grow_slab_list函数中，这个链的长度从1变成2，从2变成4，从4变成8……：

CODE:

!d \+k/]M9Rg0

static int grow_slab_list (unsigned int id) {
slabclass_t *p = &slabclass[id];
if (p->slabs == p->list_size) {
      size_t new_size =  p->list_size ? p->list_size * 2 : 16;
      void *new_list = realloc(p->slab_list, new_size*sizeof(void*));
      if (new_list == 0) return 0;
      p->list_size = new_size;
      p->slab_list = new_list;
}
return 1;
}

rm-Zbvw051Testing软件测试网*o4v9}(CmMG

在定位item时，都是使用slabs_clsid函数，传入参数为item大小，返回值为classid，由这个过程可以看出，memcached的第三个内存冗余发生在保存item的过程中，item总是小于或等于chunk大小的，当item小于chunk大小时，就又发生了空间浪费。51Testing软件测试网|KDg/ERL-J

pG${r2M4i)e1G06、 Memcached的NewHash算法

Memcached的item保存基于一个大的hash表，它的实际地址就是slab中的chunk偏移，但是它的定位是依靠对key做hash的结果，在primary_hashtable中找到的。在assoc.c和items.c中定义了所有的hash和item操作。

5X;o Ec7i3bfV0

Memcached使用了一个叫做NewHash的算法，它的效果很好，效率也很高。1.1和1.2的NewHash有一些不同，主要的实现方式还是一样的，1.2的hash函数是经过整理优化的，适应性更好一些。

0b-g,Y yk7e_051Testing软件测试网;p5ssaw+e

NewHash的原型参考：http://burtleburtle.net/bob/hash/evahash.html。

为了变换方便，定义了u4和u1两种数据类型，u4就是无符号的长整形，u1就是无符号char(0-255)。具体代码可以参考1.1和1.2源码包。

+]D#e!G7_-E\N051Testing软件测试网(KR#@pj5J

注意这里的hashtable长度，1.1和1.2也是有区别的，1.1中定义了HASHPOWER常量为20，hashtable表长为hashsize(HASHPOWER)，就是4MB（hashsize是一个宏，表示1右移n位），1.2中是变量16，即hashtable表长65536：

lS'Tr~^4Y0

CODE:

9M#lr1e)E6D+q)epG0

typedef unsigned long int ub4; /* unsigned 4-byte quantities */
typedef unsigned char ub1; /* unsigned 1-byte quantities */
#define hashsize(n) ((ub4)1<<(n))
#define hashmask(n) (hashsize(n)-1)

在assoc_init()中，会对primary_hashtable做初始化，对应的hash操作包括：assoc_find()、assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete()，对应于item的读写操作。其中assoc_find()是根据key和key长寻找对应的item地址的函数（注意在C中，很多时候都是同时直接传入字符串和字符串长度，而不是在函数内部做strlen），返回的是item结构指针，它的数据地址在slab中的某个chunk上。

a*H ];VX*?&kO0

items.c是数据项的操作程序，每一个完整的item包括几个部分，在item_make_header()中定义为：

51Testing软件测试网 HqV1j&P&|

key：键
nkey：键长
flags：用户定义的flag（其实这个flag在memcached中没有启用）
nbytes：值长（包括换行符号\r\n）
suffix：后缀Buffer
nsuffix：后缀长

QXg6?Mp!~Me,P;^051Testing软件测试网}.[(H-n#gG;f

一个完整的item长度是键长＋值长＋后缀长＋item结构大小（32字节），item操作就是根据这个长度来计算slab的classid的。

+E/p`P3XNCE+R0

hashtable中的每一个桶上挂着一个双链表，item_init()的时候已经初始化了heads、tails、sizes三个数组为0，这三个数组的大小都为常量LARGEST_ID（默认为255，这个值需要配合factor来修改），在每次item_assoc()的时候，它会首先尝试从slab中获取一块空闲的chunk，如果没有可用的chunk，会在链表中扫描50次，以得到一个被LRU踢掉的item，将它unlink，然后将需要插入的item插入链表中。

ql$J6m6nl+O ul051Testing软件测试网a9k%?(I e;t,id

注意item的refcount成员。item被unlink之后只是从链表上摘掉，不是立刻就被free的，只是将它放到删除队列中（item_unlink_q()函数）。

item对应一些读写操作，包括remove、update、replace，当然最重要的就是alloc操作。

51Testing软件测试网8X/@(L9L4AA

item还有一个特性就是它有过期时间，这是memcached的一个很有用的特性，很多应用都是依赖于memcached的item过期，比如session存储、操作锁等。item_flush_expired()函数就是扫描表中的item，对过期的item执行unlink操作，当然这只是一个回收动作，实际上在get的时候还要进行时间判断：

'iI2J Ki*x^/?-]w0

CODE:

51Testing软件测试网0v2L#d-n.@9Z v

/* expires items that are more recent than the oldest_live setting. */
void item_flush_expired() {
int i;
item *iter, *next;
if (! settings.oldest_live)
      return;
for (i = 0; i < LARGEST_ID; i++) {
      /* The LRU is sorted in decreasing time order, and an item's timestamp
      * is never newer than its last access time, so we only need to walk
      * back until we hit an item older than the oldest_live time.
      * The oldest_live checking will auto-expire the remaining items.
      */
      for (iter = heads[i]; iter != NULL; iter = next) {
         if (iter->time >= settings.oldest_live) {
            next = iter->next;
            if ((iter->it_flags & ITEM_SLABBED) == 0) {
                  item_unlink(iter);
            }
         } else {
            /* We've hit the first old item. Continue to the next queue. */
            break;
         }
      }
}
}

!ok]"Fgl5N:]0

CODE:

? K}qD0

/* wrapper around assoc_find which does the lazy expiration/deletion logic */
item *get_item_notedeleted(char *key, size_t nkey, int *delete_locked) {
item *it = assoc_find(key, nkey);
if (delete_locked) *delete_locked = 0;
if (it && (it->it_flags & ITEM_DELETED)) {
      /* it's flagged as delete-locked.  let's see if that condition
         is past due, and the 5-second delete_timer just hasn't
         gotten to it yet... */
      if (! item_delete_lock_over(it)) {
         if (delete_locked) *delete_locked = 1;
         it = 0;
      }
}
if (it && settings.oldest_live && settings.oldest_live <= current_time &&
      it->time <= settings.oldest_live) {
      item_unlink(it);
      it = 0;
}
if (it && it->exptime && it->exptime <= current_time) {
      item_unlink(it);
      it = 0;
}
return it;
}

51Testing软件测试网7i^Zj!@J

Memcached的内存管理方式是非常精巧和高效的，它很大程度上减少了直接alloc系统内存的次数，降低函数开销和内存碎片产生几率，虽然这种方式会造成一些冗余浪费，但是这种浪费在大型系统应用中是微不足道的。

Y%F#u(@|aXU&D051Testing软件测试网"y!J[ra QkK

~&[_$\8\r,`,J\)^*o07、 Memcached的理论参数计算方式

影响 memcached 工作的几个参数有：
aQ#BEu"DG0
"b"wY6r8{0常量REALTIME_MAXDELTA 60*60*24*30
;V w e5d a0`h0v0最大30天的过期时间
51Testing软件测试网1J7MD6e+p
conn_init()中的freetotal（=200）
zRSyX)W*DWSrR0最大同时连接数51Testing软件测试网W4}'V}(F

常量KEY_MAX_LENGTH 250
~pWF(HbU)~x0最大键长

settings.factor（=1.25）
6md,e4at4Tv4vm.S0factor将影响chunk的步进大小
$B\r Gl5D&Di0
s0s;s+QH2dhk0settings.maxconns（=1024）
I+k&|u:H4fX&o0最大软连接51Testing软件测试网ZK/B \)T\:g
51Testing软件测试网/HA6yx0I @d
settings.chunk_size（=48）
一个保守估计的key+value长度，用来生成id1中的chunk长度（1.2）。id1的chunk长度等于这个数值加上item结构体的长度（32），即默认的80字节。

常量POWER_SMALLEST 1
x S7N'kb#}'v0^r*Y:m0最小classid（1.2）
]0Y'b yhq K0
常量POWER_LARGEST 20051Testing软件测试网r'u9{n&|/| c
最大classid（1.2）
(u OS)e#^6Z051Testing软件测试网 Q y]r$?FV?
常量POWER_BLOCK 1048576
fs!v/l+ybO4Z0默认slab大小
51Testing软件测试网4s6gh`3P
常量CHUNK_ALIGN_BYTES (sizeof(void *))
;ttN%b i.k*QHOy0保证chunk大小是这个数值的整数倍，防止越界（void *的长度在不同系统上不一样，在标准32位系统上是4）
7s,J(l{&P|O5Bo0
$ki-t W1LUt0常量ITEM_UPDATE_INTERVAL 60
{:["sc9G^0队列刷新间隔51Testing软件测试网aq fS|9}c

xcl.{]d0常量LARGEST_ID 255
最大item链表数（这个值不能比最大的classid小）
7kF"azC2p051Testing软件测试网PJa%v$R7F]
变量hashpower（在1.1中是常量HASHPOWER）
i.ddan0决定hashtable的大小
`(Uml5l;{'Mc{0c0
根据上面介绍的内容及参数设定，可以计算出的一些结果：51Testing软件测试网6w9|P ]E }

N0_9e;R?URz01、在memcached中可以保存的item个数是没有软件上限的，之前我的100万的说法是错误的。
vLTzBb J{d"m02、假设NewHash算法碰撞均匀，查找item的循环次数是item总数除以hashtable大小（由hashpower决定），是线性的。
3、Memcached限制了可以接受的最大item是1MB，大于1MB的数据不予理会。
aO3dg | i E04、Memcached的空间利用率和数据特性有很大的关系，又与DONT_PREALLOC_SLABS常量有关。在最差情况下，有198个slab会被浪费（所有item都集中在一个slab中，199个id全部分配满）。51Testing软件测试网R r z$E~,Mt