那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

The design and implementation of CommonCache Library(base on version 0.6)


1. Overview

a) the functions of a cache
cache the most frequently visited data in the memory, so:
1) if the the data get losed is not a big matter,it means that you should not store data
in cache only, offen, cache is between the DB server and application,hence reduce visiting DB times
 and speed up application.
2) since the memory is not quite big, so the eliminating algorithm such LRU must to be used.
3) must support key-value-like API such as find/erase/set and so forth.

b) ccache feature (version 0.6):
1) using mmap to cache data in file, so it can be used in multi-thead and multi-process application.
2) support unfix size key node
3) support hash-rbtree and hash-list structure
4) use LRU algorithm to eliminate nodes when it is running out of its memory size
5) fast, 100W/read operation on fix-size key node in no more than 0.5 second

c) what is the difference between ccache and memcached?
ccache is a static library, memcached is a cache sever, so users who use ccache must
design the protocols between clients and server, and write the server application themself.

2. implementation
a) the cache file structure


b) the hashitem array detail   
the hashitem array is used to find the node base on the node key.Every nodes in a
same hashitem has a same hash num.All the nodes in the same hashitem are strutured
in list or rbtree:


when compiling the ccache, define the macro CCACHE_USE_RBTREE to specily using rbtree,
else macro CCACHE_USE_LIST using list. The structrue ccache_node_t has following fields
about this:

typedef struct ccache_node_t
{
        
/* 
          
         
*/

#ifdef CCACHE_USE_LIST
    
struct ccache_node_t *next, *prev;
#elif defined CCACHE_USE_RBTREE    
    ccache_color_t color;
    
struct ccache_node_t *parent, *left, *right;
#endif

        
/* 
          
         
*/

}
ccache_node_t;

the hashitem array size is defined in the configure file when open the cache.

c) the freearea array detail   
ccache use slab-like algorithm to allocate node memory.In the configure file, there is an
item called "alignsize", this value specify the align size between different freearea,
assume the alignsize is 8 bytes:

all the nodes in the same freearea has the same size, when allocating a node(ccache_memory.c/ccache_allocate):
1) allign the node size with the alignsize value, then find the fit
freearea(ccache_memory.c/ccache_get_freeareaid) and return the freeareaid
2) if the data zone has enough memory for the node, change the cache->start_free and cache->freesize
and return the node pointer
3) else, erase the  cache->freearea[freeareaid]->lrulast node, use this node memory
for this allocation.
4) every time a node allocated, place it in the freearea's tail(freearea->lrulast = node),
when the node has been visited, it move on one step in the freearea list.So, the more a node has been
visited, the closer it moves to the freearea head(freearea->lrufirst).Hence, the freearea lrulast
node is the less frequently visited node in the freearea(although not so accurate:).

the ccache_node_t structure has following fields about LRU:

typedef struct ccache_node_t
{
    
/*
       .
    
*/
       
    
struct ccache_node_t *lrunext, *lruprev;

    
/*
       .
    
*/
       
}
ccache_node_t;

 

 

posted on 2009-10-22 21:11 那谁 阅读(4036) 评论(1)  编辑 收藏 引用 所属分类: ccache

评论

# re: The design and implementation of CommonCache Library(base on version 0.6)  回复  更多评论   

开源,大力支持啊!
中国缺少这样的东西
2010-03-10 19:37 | jesse

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理