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;