memcached:Memcached深度分析

　　Memcached是danga.com(运营LiveJournal技术团队(Team))开发套分布式内存对象缓存Cache系统用于在动态系统中减少数据库负载提升性能有关这个东西相信很多人都用过本文意在通过对memcached实现及代码分析获得对这个出色开源软件Software更深入了解并可以根据我们需要对其进行更进步优化末了将通过对BSM_Memcache扩展分析加深对memcached使用方式理解

　　本文部分内容可能需要比较好数学基础作为辅助

　　◎Memcached是什么

　　在阐述这个问题的前我们首先要清楚它“不是什么”很多人把它当作和SharedMemory那种形式存储载体来使用虽然memcached使用了同样“Key=>Value”方式组织数据但是它和共享内存、APC等本地缓存Cache有非常大区别Memcached是分布式也就是说它不是本地它基于网络连接(当然它也可以使用localhost)方式完成服务本身它是个独立于应用或守护进程(Daemon方式)

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

　　◎Memcached适合什么场合

　　在很多时候memcached都被滥用了这当然少不了对它抱怨我经常在论坛上看见有人发贴类似于“如何提高效率”回复是“用memcached”至于如何用用在哪里用来干什么句没有memcached不是万能它也不是适用在所有场合

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

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

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

　　◎Memcached工作方式

　　以下部分中读者最好能准备份memcached源代码

　　Memcached是传统网络服务如果启动时候使用了-d参数它会以守护进程方式执行创建守护进程由daemon.c完成这个只有个daemon这个很简单(如无特殊介绍说明代码以1.2.1为准):

　　CODE:

# <fcntl.h>
# <stdlib.h>
# <unistd.h>

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

　　这个 fork 了整个进程的后父进程就退出接着重新定位 STDIN 、 STDOUT 、 STDERR 到空设备 daemon 就建立成功了

　　Memcached 本身启动过程在 memcached.c 中顺序如下:

　　1 、 tings_init 设定化参数

　　2 、从启动命令中读取参数来设置 ting 值

　　3 、设定 LIMIT 参数

　　4 、开始网络 监听(如果非 path 存在)( 1.2 的后支持 UDP 方式)

　　5 、检查用户身份( Memcached 不允许 root 身份启动)

　　6 、如果有 path 存在开启 UNIX 本地连接(Sock 管道)

　　7 、如果以 -d 方式启动创建守护进程(如上 daemon )

　　8 、化 item 、 event 、状态信息、 hash 、连接、 slab

　　9 、如设置中 managed 生效创建 bucket

　　10 、检查是否需要锁定内存页

　　11 、化信号、连接、删除队列

　　12 、如果 daemon 方式处理进程 ID

　　13 、event 开始启动过程结束 进入循环

　　在 daemon 方式中 stderr 已经被定向到黑洞所以不会反馈执行中可见信息

　　memcached.c 主循环是 drive_machine 传入参数是指向当前连接结构指针根据 state 成员状态来决定动作

　　Memcached 使用套自定义协议完成数据交换它 protocol 文档可以参考: http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt

　　在API中换行符号统为rn

　　◎Memcached内存管理方式

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

　　1.1和1.2slabs.c中slab空间划分算法有些区别后面会分别介绍

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

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

　　在 1.1中chunk大小表示为大小*2^nn为id即:id为0slab每chunk大小1字节id为1slab每 chunk大小2字节id为2slab每chunk大小4字节……id为20slab每chunk大小为1MB就是说id为20slab里只有个chunk:

　　CODE:

void slabs_init(size_t limit) {
　　 i;
　　 size=1;
　　mem_limit = limit;
　　for(i=0; i<=POWER_LARGEST; i, size*=2) {
　　 　slab[i].size = size;
　　 　slab[i].perslab = POWER_BLOCK / size;
　　 　slab[i].slots = 0;
　　 　slab[i].sl_curr = slab[i].sl_total = slab[i].slabs = 0;
　　 　slab[i].end_page_ptr = 0;
　　 　slab[i].end_page_free = 0;
　　 　slab[i].slab_list = 0;
　　 　slab[i].list_size = 0;
　　 　slab[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");
　　 　 (t_initial_malloc) {
　　 　 　 mem_malloced = atol(getenv("T_MEMD_INITIAL_MALLOC"));
　　 　}
　　}
　　/* pre-allocate slabs by default, unless the environment variable
　　 　for testing is to something non-zero */
　　{
　　 　char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
　　 　 (!pre_alloc || atoi(pre_alloc)) {
　　 　 　 slabs_preallocate(limit / POWER_BLOCK);
　　 　}
　　}
}

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

　　CODE:

void slabs_init(size_t limit, double factor) {
　　 i = POWER_SMALLEST - 1;
　　unsigned size = (item) + tings.chunk_size;
　　/* Factor of 2.0 means use the default memcached behavior */
　　 (factor 2.0 && size < 128)
　　 　size = 128;
　　mem_limit = limit;
　　mem(slab, 0, (slab));
　　while (i < POWER_LARGEST && size <= POWER_BLOCK / 2) {
　　 　/* Make sure items are always n- aligned */
　　 　 (size % CHUNK_ALIGN_BYTES)
　　 　 　 size CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
　　 　slab[i].size = size;
　　 　slab[i].perslab = POWER_BLOCK / slab[i].size;
　　 　size *= factor;
　　 　 (tings.verbose > 1) {
　　 　 　 fprf(stderr, "slab %3d: chunk size %6d perslab %5dn",
　　 　 　 　 　 　i, slab[i].size, slab[i].perslab);
　　 　}　　 　
　　}
　　power_largest = i;
　　slab[power_largest].size = POWER_BLOCK;
　　slab[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");
　　 　 (t_initial_malloc) {
　　 　 　 mem_malloced = atol(getenv("T_MEMD_INITIAL_MALLOC"));
　　 　}　　 　
　　}
#ndef DONT_PREALLOC_SLABS
　　{
　　 　char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
　　 　 (!pre_alloc || atoi(pre_alloc)) {
　　 　 　 slabs_preallocate(limit / POWER_BLOCK);
　　 　}
　　}
#end
}

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

　　Memcached 使用这种方式来分配内存是为了可以快速通过item长度定位出slabid有点类似hashitem长度是可以计算比如个item长度是300字节在1.2中就可以得到它应该保存在id7slab中按照上面计算思路方法id6chunk大小是252字节id7chunk大小是316字节id8chunk大小是396字节表示所有252到316字节item都应该保存在id7中同理在 1.1中也可以计算得到它出于256和512的间应该放在chunk_size为512id9中(32位系统)

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

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

　　CODE:

grow_slab_list (unsigned id) {
　　slab_t *p = &slab[id];
　　 (p->slabs p->list_size) {
　　 　size_t _size =　p->list_size ? p->list_size * 2 : 16;
　　 　void *_list = realloc(p->slab_list, _size*(void*));
　　 　 (_list 0) 0;
　　 　p->list_size = _size;
　　 　p->slab_list = _list;
　　}
　　 1;
}

　　在定位item时都是使用slabs_clsid传入参数为item大小返回值为id由这个过程可以看出memcached第 3个内存冗余发生在保存item过程中item总是小于或等于chunk大小当item小于chunk大小时就又发生了空间浪费

　　◎MemcachedNewHash算法

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

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

　　NewHash原型参考:http://burtleburtle.net/bob/hash/evahash.html数学家总是有点奇怪呵呵～

　　为了变换方便定义了u4和u1两种数据类型u4就是无符号长整形u1就是无符号char(0-255)

　　具体代码可以参考1.1和1.2源码包

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

　　CODE:

typedef　unsigned long　　ub4;　/* unsigned 4- quantities */
typedef　unsigned　　 　char ub1;　/* unsigned 1- quantities */
# hashsize(n) ((ub4)1<<(n))
# 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上

　　items.c是数据项操作每个完整item包括几个部分在item_make_header中定义为:

　　key:键

　　nkey:键长

　　flags:用户定义flag(其实这个flag在memcached中没有启用)

　　ns:值长(包括换行符号rn)

　　suffix:后缀Buffer

　　nsuffix:后缀长

　　个完整item长度是键长＋值长＋后缀长＋item结构大小(32字节)item操作就是根据这个长度来计算slabid

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

　　注意itemrefcount成员item被unlink的后只是从链表上摘掉不是立刻就被free只是将它放到删除队列中(item_unlink_q)

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

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

　　CODE:

/* expires items that are more recent than the oldest_live ting. */
void item_flush_expired {
　　 i;　
　　item *iter, *next;
　　 (! tings.oldest_live)
　　 　;
　　for (i = 0; i < LARGEST_ID; i) {
　　 　/* The LRU is sorted in decreasing time order, and an item's timestamp
　　 　 * is never er than its last access time, so we _disibledevent= 0;
　　}
　　 it;
}

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

　　◎Memcached理论参数计算方式

　　影响 memcached 工作几个参数有:

　　常量REALTIME_MAXDELTA 60*60*24*30

延伸阅读

• 2009-1-15-- memcached:memcached全面剖析–5. memcached的应用和兼容程序
• 2009-1-15-- memcached:memcached全面剖析–3.memcached的删除机制和发展方向
• 2009-1-12-- memcached:启用MEMCACHE_COMPRESSED压缩 扩容 MemCached
• 2009-1-15-- memcached:memcached 1. 基本操作
• 2009-1-15-- memcached:memcached全面剖析–4. memcached的分布式算法
• 2009-1-4-- memcached:memcached完全剖析–1. memcached的基础
• 2009-9-2-- memcached:memcached完全剖析–1. memcached的基础
• 2009-1-15-- memcached:Memcached 的使用和协议分析详解
• 2009-1-15-- memcached:memcached全面剖析–2.理解memcached的内存存储
• 2009-9-2-- facebook:Facebook 的 Memcached 扩展经验