1.關于本文檔
本文檔所有的分析都是在1.2版本之上,偶爾會提到比較1.1版本.其他版本沒有閱讀.
一個星期時間的工作,不可能對memcache有很深刻的分析.文檔本身的目的在于為以后的研究準備一個總結資料.剛接觸memcache時,對其設計分
布式的思路感到十分欣喜,因為在中間層以極小的代價實現簡單分布式無疑成為一些要求不是很高的分布式應用的一個很好的設計思路,這個特性決定
memcache本身在分布式應用中,單個結點之間是Server相互獨立,不會存在同級之間的通信.一個結點拒絕訪問,如果沒有相應的冗余策略,將導致
該結點的數據丟失.同時,memcache的Server結點對數據的存儲操作都是在內存中完成,而memcache對內存分配和回收采用了曾在
SunOS實現的分頁機制,預分配一個大內存(默認是 <=
200M),然后分頁切塊,對每個數據對象的存儲便在所切的塊中進行操作.這個特點決定memcache沒有設計到任何磁盤IO操作,那么所有的關于
memcache的性能瓶頸都在網絡通信部分,而memcache正是將這一部分拋給了一個中間層完成.可以說真正的memcache是一個單進程,單線
程,監聽某個網絡端口的daemon(或非daemon),是一個輕量級的應用服務進程.這些特性決定了memcache的應用范圍,性能瓶頸和優化策
略.
本文檔的目的也就詣在探討查看memcache源碼后的一些觀點.
文檔分為六個部分:
1. 文檔介紹.主要介紹文檔組織和文檔目的.
2. memcache的代碼分析.分析memcache的源代碼,指出核心的數據結構和算法.
3. memcache的使用優化.分析memcache的特點,結合實際應用給出一些優化memcache的策略.
4. memcache的測試分析.初略測試了memcache,給出優化方案的例證.
5. memcache的中間層客戶端編寫.分析memcache的通信協議,模擬編寫了一個簡單的memcache中間層客戶端.
6. libevent簡介.memcache采用的是libevent進行網絡IO處理,libevent作為一種新的網絡IO方式以高效的方法(epoll/kqueue)組織IO.
其中第六章可以不看.對于系統管理員,需要查看第一,三,四部分;進行二次開發的程序員可以查看第一,二,四,五,六部分.
2.memcache代碼分析
1. memcache main流程
圖2.1 memcache main流程
libevent的事件處理機制在main進程里體現在處理網絡IO上.在TCP memcache的服務流程里,也是利用event處理事件的.
2. memcache服務流程(TCP)
圖2.2 memcache服務流程圖(TCP)
3. memcache狀態轉換和通信協議處理
圖2.3 memcache狀態轉換和通信協議處理
需要說明的是,這里需要排除所有出錯處理.很顯然,不管是哪種操作下,一旦出錯,信息需要通過conn_write狀態往client寫入出錯信息的,那么在string_out時,必定轉入conn_write狀態.
而且,很多細節也沒有在流程圖中給出,如統計信息的處理,超時后get操作時刪除等等.對于在memcache協議中定義的其他操作,如
stats,version,quit,flush_all,own,disown等等由于使用很少,在流程中沒有詳細給出,可以查看源代碼.
4. memcache核心數據結構
1. item結構
item是存儲在memcache的key-value對的抽象.由于組織item存放是按照LRU算法組織的.那么在其中有幾個成員在修改源代碼時必
須注意,time是最近訪問時間.exptime是item消亡時間.item是一個雙向列表.同時還掛在一個Hash table上.
2. conn結構
conn結構是聯系上下文的關鍵對象.對于每個連接的到來,都有一個conn結構與其對應,并且對應到某個連接狀態,進入狀態轉換而完成操作.
conn在程序開始也進行了一次預分配,分配200個連接空間.當200個使用完之后便是按需分配,到達一個分配一個.
conn和item,iovec(內核級別緩沖結構)關聯.
3. slabclass_t結構
slabclass_t保存了分級大小的空間槽,以分別適用于不同大小的item存放.取決于兩個命令行參數,-f和-n.在應用
slabclass_t時,定義的是一個數組,該數組長度取決于增長的指數級別和初始值大小(32+chunk_size),每個空間槽是不允許大于1M
的,也就是1048576.
4. settings結構
系統獲取的命令行參數保存的地方.
5. stats結構:
統計信息保存地方,可以考慮對其進行操作以適應不同的統計信息處理,如獲取某個時間段的get命中率等等操作.
5. memcache核心算法
事件觸發處理連接,LRU算法掛載item,加鎖并事后處理刪除操作,預分配空間和按需請求不夠空間策略獲取存儲空間,freelist方式管理空閑空間.名為new_hash的hash算法計算key的hash值(
http://burtleburtle.net/bo...
3.memcache使用優化
在優化memcache的工作之前,需要了解memcache體系的工作流程.一個分布式的memcache的運作是需要三個部分的,多臺提供
memcache服務的servers(簡稱S),一個進行分布式映射的中間層lib(其實這個也可以當作客戶端的一部分,簡稱L),和進行
memcache請求的客戶端(簡稱C).
在memcache工作時,有以下四個步驟:
1. C通過帶有特性化的Key值的命令串,向L請求memcache服務,L將命令串進行分解,并通過對key的某種Hash算法決定S的地址
2. L將分解的(Comm Key-Value)或者(Comm Key)向相關的S請求memcache服務.
3. 相關的S根據memcache協議向L返回服務結果.
4. L將結果進行聚集包裝后返回給C一個人性化的響應.
這個流程可以用圖3.1進行描述.
圖3.1 memcache工作步驟
在每個S端,請求處理的Key-Value對當作一個對象(不過這個對象的結構是單一的),再進行另一步hash之后,存儲在內存里.存儲算法在第二部分有詳細的描述.這種通過雙層hash來分開處理分布式和緩存兩個功能的方法值得學習.
從上面的分析可以看出,分布式的memcache服務是需要很大的網絡開銷的.對于一般的應用而言,是否都要進行memcache的優化,甚至是否需要
用到memcache,都需要進行權衡分析.如果只是本地小規模的應用,在數據庫可承受的范圍內,是寧愿采用數據庫+文件緩存的方式.1.1版本的
memcache走TCP模式在本地應用的處理速度甚至比不上Mysql數據的Unix域套接口的處理速度的一半,當然會更加比不上在程序內部直接操作內
存了.雖然1.2版本的memcache已經提供了-s參數指定Unix域套口和-u指定udp模式.而且如果不需要用到分布式的話,不推薦使用
memcache,除非你的內存足夠大到浪費的程度.
因此,在進行優化之前,需要看看是否真的需要優化memcache,是否真正需要用到memcache.
優化可以從以下幾個方面進行：
1. 命中率.
對于緩存服務而言,命中率是至關重要的.命中率的提升可以通過多種方案實現.其一,提高服務獲取的內存總量.這無疑是增加命中的最直接的辦法,將緩存數
據完全放入數據池中.只要連接不失效,就一定命中.其二,提高空間利用率,這實際上也是另一種方式的增加內存總量.具體實現在下一個方面給出.其三,對于
一些很特別的memcache應用,可以采用多個memcache服務進行偵聽,分開處理,針對服務提供的頻繁度劃分服務內存,相當于在應用一級別上再來
一次LRU.其四,對于整體命中率,可以采取有效的冗余策略,減少分布式服務時某個server發生服務抖動的情況.如,14臺機器實現分布式
memcache,劃分兩組服務,其中一組13臺做一個分布式的memcache,一組1臺做整個的memcache備份.對于update操作,需要進
行兩邊,get操作只需要一遍,一旦訪問失效,則訪問備份服務器.這樣,對于備份服務器需要內存比較大,而且只適應于讀操作大于寫操作的應用中.這可以認
為是RAID3,當然,也可以采用RAID1完全鏡像.
2. 空間利用率.
對于使用memcache做定長數據緩存服務而言,是可以在空間利用率上進行優化.甚至最簡單的辦法可以不用更改memcache的源碼遍可以完成由
-f和-n參數的配合可以做到定長優化,不過極可能需要浪費掉預分配的199M內存空間.當然前提是memcache的版本是1.2,同時如果使用的是
1.2.0和1.2.1的話,需要更改掉一個BUG,那就是getopt時將opt串中最后一個”s”改成”n”,希望memcache能在以后的版本發
現這個BUG.例如,如果key是一個定長id(如一個8位的流水號00000001),value是一個定長的串(如16位的任意字符串),對應于一個
chunk_size可以這么計算:chunk_size = sizeof(item) + nkey + *nsuffix + nbytes =
32 + 9 + (flag的數位長度 )2+ (16)的數位長度) 2+(兩換行的長度)4 + 17 = 40 + 10 + 16 =
66,那么可以通過 -f 1.000001 -n `expr 66 - 32`,即 -f 1.000001 -n 34
來啟動memcache.這種情況下,會浪費掉memcache預先分配的200M空間中的199M.從第2個預分配等級到第200個預分配等級將不會用
到.然而,存在解決辦法,那就是在編譯memcache是加入編譯參數-DDONT_PREALLOC_SLABS,或者在源代碼中加入#define
DONT_PREALLOC_SLABS即可,只是會去除memcache的預分配內存機制.
如果需要memcache的預分配內存機制,那么需要對其源代碼進行修改.修改如下:
引用
1. 在slabs.c中,將函數slabs_clsid改成:
unsigned int slabs_clsid(size_t size)
{ unsigned int res = POWER_SMALLEST;
if(size==0)
return 0;
res = (size)%power_largest;
return res;
}
2. 在item.c中,將函數 item_make_header改為:
int item_make_header(char *key, uint8_t nkey, int flags, int nbytes,
char *suffix, int *nsuffix)
{
*nsuffix = sprintf(suffix, " %u %u"r"n", flags, nbytes - 2);
return sizeof(item)+ nkey + *nsuffix + nbytes + hash(key,nkey,0);
}
3. 在item.c中,將函數 item_free改為:
void item_free(item *it)
{ unsigned int ntotal = it->slabs_clsid;
assert((it->it_flags & ITEM_LINKED) == 0);
assert(it != heads[it->slabs_clsid]);
assert(it != tails[it->slabs_clsid]);
assert(it->refcount == 0);
it->slabs_clsid = 0;
it->it_flags |= ITEM_SLABBED;
slabs_free(it, ntotal);
}
做一個輪流存儲的機制使用預分配的內存,這樣的好處是其他地方不需要做任何修改就可以了,當然你可以在源代碼中加入上面的代碼,并將它們放在一個自定義的宏后面.
3. 加速比.
加速比,也即事件的處理效率.是否可以修改libevent的事件處理效率,需要研究.如果內存空間很大,可以將freeconn的數值調大,增加預分配的conn內存大小.
是否可以將memcache做成多線程處理,但在處理多線程數據同步是個問題.
如果有時間,愿意來試試這個策略.
4. 安全性能.
memcache還存在一個比較顯著的問題,那就是其安全性能.只要了解memcache監聽的端口,對于能夠使用分布式memcache進行數據通信
的網絡環境的機器,都可以通過memcache協議于memcache服務器進行通信,獲取或種植數據.不能保證種植進內存里的數據不會被別有心意的人再
利用.也不能保證服務器的內存不被漫天遍地的垃圾數據所堆積,造成命中極低.
memcache的設計理念在一個輕字,如果對每次Client的通訊需要校驗身份,那么恐怕memcache也就達不到其想要的效果了.存在解決辦法
緩解這個問題,一般而言,需要使用memcache服務的機器,可以在Server維持一張紅色列表.這張表上的機器便可以獲取服務.很顯
然,memcache并非任意Client都能訪問,只有信任的機器訪問,那么為什么不將這些信任的機器放在一個/etc/mem_passwd下呢.
還有,memcached走udp時,很大幾率接受到upd時,都會使服務死掉,特別是set,add,replace時,這個問題需要去考究一下.不過沒有時間了.
4.memcache測試分析
服務器端memcache在命令行運行的參數:
引用
# memcached –d –m 512 –l *.*.*.* -u ** -f 1.00001 –n 16 –c 10000 -vv
1. 讀寫memcache指令測試
在利用了memcache官方推薦的c客戶端libmemcache和自己編寫的一個簡單客戶端測試之后,在set/get/add/del指令的運行速度如表4.1和圖4.1所示:
表4.1 memcache的指令運行速度
圖4.1 memcache的指令運行速度
2. 并發連接
由于在memcache服務器端,一個結點運行的是單進程單線程的daemon(或非daemon)服務,同時對于采用了libevent處理網絡IO
而言,其并發連接的數目是和libevent采用的機制相關連的.很顯然,accept函數在接收到connection后將Client的socket
放進event庫中,等待處理.而libevent庫在LINUX中使用的是epoll,監聽EPOLLIT水平觸發.因此從理論上講,memcache
的并發連接可以達到infinite,前提是event池和內存空間足夠大.而沒有和linux的線程處理有關系.事實上,在后面的測試中便可發現,在單
結點連接壓力測試時,瞬時并發連接可以達到5000多個.只是等待觸發時間上的長短和有效無效的區別.
在表4.2中可以清晰的看到并發連接的一些數據.
3. 服務端系統負載
通過自己編寫的服務器端,對單結點的memcache進行了連接壓力測試.其中測試用例的編寫是這樣的:啟用七個客戶端,每個客戶端串行運行1000個
進程,每個進程開3000線程,每個線程執行10次memcache的讀操作或者寫操作(操作相同).客戶端并發連接.
1. 客戶端(7)的環境:Intel(R) Xeon(R) CPU 5120 @ 1.86GHz,4G memory.
2. 服務器端(1)的環境:Intel(R) Xeon(R) CPU 5120 @ 1.86GHz,4G memory.
3. 網絡環境:100M網卡,Cisco交換機.
4. 數據記錄:見表4.2和圖4.2.
表4.2 memcache連接和系統負載
圖4.2 memcache連接和系統負載
很顯然,memcache的運行在系統cpu的消耗上占十分少的比重,即便是很恐怖的并發連接也不會給系統帶來多大的負載,因為其磁盤IO
free(所有操作都在內存中)和相應的內存分配機制決定其占用cpu的極少,而相反,在網絡IO上卻花費很大的時間.
4. 空間分配,命中率
由于本地測試式的get數據非常固定,因此命中率基本為100%.在10.68.1.31上運行了一個有前端應用的memcachce服務器,運行時間已經有364個多小時了.
因此通過10.68.1.31上的數據說明(版本為1.1.13).通過memcache的統計協議可以清楚的看到其命中率高達95.9%,如表4.3所示:
表4.3 memcache空間分配和命中
5.memcache客戶端編寫
1.
memcache協議
在memcache協議中規定了Client和Server的通信規則.
在源碼分析中,主要分析了update/get/del/incr/decr幾類的處理過程.其具體的規則可以在官方文檔中有說明(),這里做簡單的解釋.
引用
1． Update(set/add/replace):
Client請求規則：
"r"n
"r"n
Server響應規則：
STORED"r"n 或者 NOT_STORED"r"n
其中，是set,add,replace三種中的一種;
是client請求存儲的鍵值;
是任意16bit長的unsigned int值,在get操作時,也將伴隨data一起返回,可以用來存儲某些認證信息或者描述信息;
是key－value對象的消亡時間,如果為0,則代表永不消亡;
是數據的長度,千萬小心,這個很重要,在memcache源代碼里,直接讀取這個數值來當作數據的長度,而不是用strlen計算的.這個顯而易見,因為數據中有可能存在/r/n符號,也就是協議中規定的分隔符.如果出現,則嚴格按長度取數據;
也就是value值,可以包含"r"n值.
STORED代表update操作成功，NOT_STORED代表update操作失敗.
2． Get(get/bget)
Client請求規則：
*"r"n
Server響應規則：
VALUE "r"n
"r"n
END"r"n
Get/bget操作可以一次操作多個key值,server的響應格式中的關鍵字可以參看上面的解釋,END代表數據顯示結束.如果沒有數據,則只有一個END"r"n.
3． Delete(delete)
Client請求規則：
delete
2. 針對協議的一個簡單實現
在這個例子中簡單實現了一個能進行update/get/delete操作測試用例,只是簡單socket的應用而已.如果可以,模仿這個寫一個簡單的客戶端應該難度不大.
引用
/****************************************"
* mem_benchmark_conn2.c
*
* Mon Mar 7 10:52:30 2007
* Copyright 2007 Spark Zheng
* Mail
* v0.1 Mar 5 2007 file:mem_benchmark_conn.c
"****************************************/
#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < ctype.h>
#include < unistd.h>
#include < pthread.h>
#include < time.h>
#include < sys/types.h>
#include < sys/time.h>
#include < sys/resource.h>
//#include < sys/socket.h>
//#include < netdb.h>
//#include < arpa/inet.h>
#ifndef MEM_SERVER
#define MEM_SERVER "10.210.71.25"
#endif
#ifndef MEM_PORT
#define MEM_PORT 11211
#endif
void p_usage(void);
void *conn_mem(void);
int NonbSocket(const char *server, int port);
int mem_set(int sock,const char *key,const char *value);
int mem_add(int sock,const char *key,const char *value);
int mem_get(int sock,const char *key,char *value);
int mem_del(int sock,const char *key);
int main(int argc,char **argv)
{
int conn=0;
int i=0;
pthread_t ptid[10000];
struct rlimit rlim;
struct timeval tv1,tv2;
if(argc < 2)
{
p_usage();
exit(255);
}
conn = atoi(argv[1]);
if(getrlimit(RLIMIT_NOFILE,&rlim) != 0)
{
fprintf(stderr,"getrlimit error in line %d"n",__LINE__);
exit(254);
}
if((conn > rlim.rlim_cur) && (2*conn > 1024))
{
rlim.rlim_cur = 2*conn;
}
if(rlim.rlim_cur > rlim.rlim_max)
{
rlim.rlim_max = rlim.rlim_cur;
}
if(setrlimit(RLIMIT_NOFILE,&rlim) != 0)
{
fprintf(stderr,"setrlimit error in line %d"n",__LINE__);
exit(254);
}
gettimeofday(&tv1,NULL);
while(i++ < conn)
{
if(pthread_create(&ptid[i],NULL,(void *)conn_mem,NULL) != 0)
{
perror("pthread_create error"n");
exit(253);
}
}
i=0;
while(i++ < conn)
{
if(pthread_join(ptid[i],NULL) != 0)
{
perror("pthread_join error"n");
exit(253);
}
}
gettimeofday(&tv2,NULL);
printf("time is %f,conn is %f persecond"n",((tv2.tv_sec-tv1.tv_sec)+(tv2.tv_usec-tv1.tv_usec)/1000000.0),conn/((tv2.tv_sec-tv1.tv_sec)+(tv2.tv_usec-tv1.tv_usec)/1000000.0));
return 0;
}
void p_usage(void)
{
printf("Usage:./mem_benchmark_conn < conn_num >"n");
printf("Notice: the conn_num must <= 10000"n");
return;
}
void *conn_mem(void)
{
int sock;
char *key = "test_a";
char *value = "this is a";
if((sock=NonbSocket(MEM_SERVER,MEM_PORT)) < 0)
{
fprintf(stderr,"socket error in line %d"n",__LINE__);
return NULL;
}
int i=0;
while(i++ < 10)
{
///*
mem_set(sock,key,value);
//*/
/*
char *key2="test_b";
char *value2="this is b";
mem_add(sock,key2,value2);
*/
/*
char buf[101];
mem_get(sock,key,buf);
printf("get value for %s is %s"n",key,buf);
*/
/*
char *key3="test_c";
mem_del(sock,key);
*/
}
close(sock);
return NULL;
}
int mem_set(int sock,const char *key,const char *value)
{
char set[101];
char recv_buf[101];
sprintf(set,"set %s 0 0 %d"r"n%s"r"n",key,strlen(value),value);
if(write(sock,set,strlen(set)) < 0)
{
fprintf(stderr,"write error in line %d"n",__LINE__);
return -1;
}
if(read(sock,recv_buf,100) < 0)
{
fprintf(stderr,"read error in line %d"n",__LINE__);
return -2;
}
printf("in set %s"n",recv_buf);
return 0;
}
int mem_add(int sock,const char *key,const char *value)
{
char add[101];
char recv_buf[101];
sprintf(add,"add %s 0 0 %d"r"n%s"r"n",key,strlen(value),value);
if(write(sock,add,strlen(add)) < 0)
{
fprintf(stderr,"write error in line %d"n",__LINE__);
return -1;
}
if(read(sock,recv_buf,100) < 0)
{
fprintf(stderr,"read error in line %d"n",__LINE__);
return -2;
}
printf("in add %s"n",recv_buf);
return 0;
}
int mem_get(int sock,const char *key,char *value)
{
char get[101];
char recv_buf[101];
sprintf(get,"get %s"r"n",key);
if(write(sock,get,strlen(get)) < 0)
{
fprintf(stderr,"write error in line %d"n",__LINE__);
return -1;
}
if(read(sock,recv_buf,100) < 0)
{
fprintf(stderr,"read error in line %d"n",__LINE__);
return -2;
}
strncpy(value,recv_buf,strlen(recv_buf));
printf("in get %s"n",recv_buf);
return 0;
}
int mem_del(int sock,const char *key)
{
char del[101];
char recv_buf[101];
sprintf(del,"delete %s 0"r"n",key);
if(write(sock,del,strlen(del)) < 0)
{
fprintf(stderr,"write error in line %d"n",__LINE__);
return -1;
}
if(read(sock,recv_buf,100) < 0)
{
fprintf(stderr,"read error in line %d"n",__LINE__);
return -2;
}
printf("in del %s"n",recv_buf);
return 0;
}
3. 分布式的實現
分布式的實現可以這么完成,構建一個struct用于存放server信息.對于每個請求的key值,用很簡單的hash算法(如
libmemcache用的是crc32)映射到server數組中的某個數組,然后對其進行通信.獲取處理結果之后,將結果美化返回client.
6.
libevent簡介
1. libevent
libevent是一個事件觸發的網絡庫,適用于windows,linux,bsd等多種平臺,內部使用iopc/epoll/kqueue等系統調用管理事件機制,而且根據libevent官方網站上公布的數據統計,似乎也有著非凡的性能.
從代碼中看,libevent支持用戶使用三種類型的事件,分別是網絡IO,定時器,信號三種,在定時器的實現上使用了紅黑樹(RB
tree)的數據結構,以達到高效查找,排序,刪除定時器的目的,網絡IO上,libevent的epoll居然用的EPOLLLT水平觸發的方式,不容
易出錯,但是在效率上可能比EPOLLET要低一些.跟網絡無關的,libevent也有一些緩沖區管理的函數,libevent沒有提供緩存的函數.而
且libevent的接口形式非常值得參考.
2. epoll
在linux中,libevent用的是epoll.如果有興趣的話,可以查看man epoll頁面.或者看前面blog上引用的libevent的資源.
文章學習了
黑夜路人相關文章,
奶瓶博士的memcache深度分析文章和一些
memcache作者的文章,在此向他們致敬.