Chinaunix

标题: 发布我的开源cache库ccache [打印本页]
作者: converse    时间: 2008-03-24 11:18
标题: 发布我的开源cache库ccache
ccache(common cache)是一个使用共享内存实现的cache静态库,在节点数据不足时采用LRU算法进行节点的淘汰.
与memcache的区别在于,首先memcache是一个完整的server程序,不仅有cache的处理操作,还需要监听及处理客户端的操作请求,而ccache只是一个静态库,只关心cache的处理操作;其次,memcache采用了内存去管理数据,程序一旦停止,其中的数据全部丢失,而ccache采用了mmap的方式去管理数据,也就是每个cache都用一个与之对应的文件,一定程度上保证了数据不至于在程序停止的时候丢失;第三,memcache实现了对不定长key和data的支持,而cache目前(version 0.1)只支持定长的key和data,也就是同一个cache只能管理一个类型的key和data.

当前的版本(version0.1)采用hash-list的形式管理数据,LRU算法在节点数据不足时进行淘汰数据.
今后的版本需要完成的主要功能:
1)实现对不定长key和data的处理支持.
2)降低锁粒度,目前ccache在对数据进行操作时,都是对cache全局加锁,以后希望能做到降低这个加锁的粒度,使效率更高.
3)加入hash-rbtree的形式管理数据.

test/testcache.c是一个演示如何使用ccache的程序,目前仅在多进程的情况下进行测试,由于我本人对多线程不太熟悉,所以没有做多线程情况下的测试.
另外,由于使用了线程锁,所以在编译的时候需要链接pthread库.

项目地址:http://code.google.com/p/commoncache/
(注:请下载其中的ccache0.1.rar文件包,原先的cache.rar有一些问题)

2008.08.07发布0.3版本:
changelog:
加入对可变长key/value的支持.
shm.h/.c文件更名为memory.h/.c文件 create_shm/destroy_shm 更名为create_mmap/destroy_mmap
加入头文件config.h, 可用于配置一些参数
加入error.h/error.c 可以保存一些出错的信息

在使用时, 采用create_ccache函数创建ccache_t对象指针,其中的参数min_size和max_size分别指定cache中保存数据的最小和最大尺寸, min_size<=max_size, 当min_size = max_size时, 则是特殊情况, 可用于固定key/value的cache来使用, 节省了不少空间.(当然, 如果你想使用min_size和max_size不相同的cache来存放固定key/value的数据,也是可以的,只不过会浪费一些空间).

在插入/查询/删除数据等操作时,需要将数据封装到一个数据结构中:
typedef struct data_t
{
    int     datasize;               /* the size of the data */
    int     keysize;                /* the size of the key */
    char*   data;                   /* the pointer of the data */
    char*   key;                    /* the pointer of the key */
}data_t;

注释中对每个字段的含义解释的很清楚.

具体如何使用ccache来操作可变或者固定key/value的数据,请参看test文件夹下面用于压力测试的两个示例文件.

0.4版本(2008-10-31)
1)将原先的线程锁改成了线程读写锁,这个变化会让操作更快些,在查找,遍历操作的时候使用的是读锁,插入,删除,更新,替换等
会改变cache中元素的操作使用的是写锁.
2)将原先的API命名方式做了改变,变为ccache_***方式的命名, 这也是很多项目的命名方式, 但是其他未向外公开的API没有改变
命名方式,我在想是不是要把所有的函数都改成ccache_***的命名方式, 似乎这样更加统一一些.
3)另外, 原来的一个API, update_or_insert_data,命名方式太丑陋了, 改成了replace, 按照现在的命名方式, 这个API的名字
就是ccache_replace.
4)原先的operator.h/.c文件被删除, 取而代之的是functor.h/.c文件, 同时将插入,替换,更新,查找,删除,访问等操作作为函数指针封装到functor_t结构体
中, 这样以后采用其他的数据结构只要初始化不同的函数指针就可以了.

0.5版本(2008-11-14)
1) 加入对红黑树的支持, 可以在编译的时候决定使用的是hash-list还是hash-rbtree结构体进行数据的存储,具体请见makefile
2) 加入了一个数据结构对insert,find,erase,update,replace等操作进行统计, 参见ccache.h中的ccache_stat_t的结构体,另外在
测试程序中也加入了演示打印这些数据的函数,参见test中的测试代码.
3) 对hash-list算法进行了改进, 在访问到某一个节点的时候, 会让这个节点所在的链表位置向前走一步, 这样访问越频繁的节点就越靠近
链表头部,参见ccache_lis.c中的ccache_list_advance函数, 每次访问了某个节点就会去调用该函数.
4) 同样的,LRU链表算法也进行了改善,之前是访问的节点马上就更新到该LRU链表的头部, 现在也更改为每次向前走一步,
参见ccache_lrulist.c中的ccache_lrulist_advance函数.
5) 代码风格的调整, 所有的文件名,函数名, 宏名, 自定义类型名称都加上了"ccache_"前缀.

点击这里下载.

发布了这个版本之后,貌似我想不到其他比较大的feature, 最近的一段时间内除非有bug的改正, 否则不会发布新的版本了,我将抽时间整理出一份文档讲解ccache的实现.


ccache库项目地址:
http://code.google.com/p/commoncache/

[ 本帖最后由 converse 于 2008-11-14 16:56 编辑 ]
作者: net_robber    时间: 2008-03-24 14:31
标记一下，下个星期学习代码
作者: cofish    时间: 2008-03-24 14:59
贊一個
作者: pengjay    时间: 2008-03-24 15:26
up
作者: LinuxKen    时间: 2008-03-24 15:35
友情帮顶。
楼上的个性签名
作者: Coolriver    时间: 2008-03-27 13:08
学习一下。
作者: weedeater    时间: 2008-03-27 13:20
看标题还以为是这个 ccache.samba.org
重名了
作者: gunsand    时间: 2008-04-01 09:27
标题: XXXX
你要是加上SQL语句的支持就牛了。。 嘿嘿。
作者: iunknown    时间: 2008-04-01 09:53
标题: 一点小建议
建议用 zip 格式来发布。记得以前看过 zip 和 rar 格式的一些八卦，提到 rar 是有版权的，目前免费的 rar 软件也不多。
作者: kakasi    时间: 2008-04-01 10:00
支持，有空学习~~
PS：又是google code。。
作者: converse    时间: 2008-04-01 10:04
标题: 回复 #9 iunknown 的帖子
是的 我的blog上也有人是这么建议的 今后的版本决定这么做了 以前没有这方面的经验.
作者: yangsf5    时间: 2008-04-01 11:04
下不动啊。。资源是 0/1。。

版主的博客在哪啊，想拜读。

另外能把你的cache发给我一份么？感激

[ 本帖最后由 yangsf5 于 2009-1-5 13:03 编辑 ]
作者: yangsf5    时间: 2008-04-01 11:19
挂迅雷挂了20分钟。。。终于下来了。。。
作者: blueboy83    时间: 2008-04-01 11:26
mark一个
感觉做web应用比较适合
作者: pilgrim_kevin    时间: 2008-04-01 12:33
学习下。
作者: albcamus    时间: 2008-04-01 12:52
能改个名字吗？ 冲突了：

rpm -qi ccache
Name        : ccache                       Relocations: (not relocatable)
Version     : 2.4                               Vendor: Fedora Project
Release     : 11.fc8                        Build Date: 2007年10月03日 星期三 00时53分56秒
Install Date: 2008年04月01日 星期二 12时48分33秒      Build Host: xenbuilder2.fedora.redhat.com
Group       : Development/Tools             Source RPM: ccache-2.4-11.fc8.src.rpm
Size        : 86820                            License: GPLv2+
Signature   : DSA/SHA1, 2007年10月25日 星期四 08时41分28秒, Key ID b44269d04f2a6fd2
Packager    : Fedora Project
URL         : http://ccache.samba.org/
Summary     : C/C++ compiler cache
Description :
ccache is a compiler cache.  It acts as a caching pre-processor to
C/C++ compilers, using the -E compiler switch and a hash to detect
when a compilation can be satisfied from cache.  This often results in
a 5 to 10 times speedup in common compilations.
作者: flw    时间: 2008-04-01 12:53
lcache
作者: converse    时间: 2008-04-02 11:51
发布0.2版本,主要改动:

0.2版本:
cmpfun函数指针去掉了size参数, 因为我认为这个参数应该由使用该cache的用户去关心,见test/testcache.c中的示例代码
加入两个api:update_or_insert_data和visit_cache
同时还有unlock_cache api,因为某些使用C++的用户如果使用了C++的异常处理,在调用ccache中的API时抛出异常将导致ccache没有解锁
, 以后就不能再使用了, 提供这个API是为了在抛出异常的时候用户自己释放锁

另外,这个版本还修正了原来的两个低级错误:第一个是在ccache.h中加入了对__cplusplus宏的处理,如果不加入这个宏的处理,那么如果用gcc编译了
ccache,而用g++编译链接生成的静态库将导致链接错误;第二个将makefile中的
testcache:test/testcache.c $(OBJS)
        $(CC) -o $(TESTCACHE) $(OBJS) $(TESTDIR)/*.c -L$(LIB_DIR) -l$(LIBNAME) $(CFLAGS) $(INCLUDE) -lpthread
改成了:
testcache:test/testcache.c $(LIB)
    $(CC) -o $(TESTCACHE) $(TESTDIR)/*.c -L$(LIB_DIR) -l$(LIBNAME) $(CFLAGS) $(INCLUDE) -lpthread
作者: yangsf5    时间: 2008-04-02 20:19
  1.     while (0 <= index)

  3.     {

  5.         node = NODE(cache, index);

  7.         nodekey = NODE_KEY(node);



  11.         if (!cmp(key, nodekey))

  13.         {

  15.             break;

  17.         }



  21.         index = node->next;

  23.     }
复制代码

版主的这个找节点是用遍历链表的阿？
我要维护一个1.5w节点的cache，这样会降低效率么？

如果设计成哈希表那样的，可以直接由数据的key找到对应节点的。。。但又会解决哈希冲突的开销和映射。。。

两种效率怎么取舍阿？
作者: converse    时间: 2008-04-02 21:59
标题: 回复 #19 yangsf5 的帖子
你没有看完这个代码,是采用HASH-LIST的复合数据结构.
作者: yangsf5    时间: 2008-04-03 09:06
  1. unsigned int hash(const void* key, ccache_t* cache)

  3. {

  5. #define mix(a,b,c) \

  7.     { \

  9.         a -= b; a -= c; a ^= (c >> 13); \

  11.         b -= c; b -= a; b ^= (a << 8); \

  13.         c -= a; c -= b; c ^= (b >> 13); \

  15.         a -= b; a -= c; a ^= (c >> 12);  \

  17.         b -= c; b -= a; b ^= (a << 16); \

  19.         c -= a; c -= b; c ^= (b >> 5); \

  21.         a -= b; a -= c; a ^= (c >> 3);  \

  23.         b -= c; b -= a; b ^= (a << 10); \

  25.         c -= a; c -= b; c ^= (b >> 15); \

  27.     }



  31.     char *k = (char *)key;

  33.     unsigned int a, b, c, i, len;

  35.     unsigned int length = cache->keysize;



  39.     for (i = 0; i < length; i++)

  41.         k[i] = tolower(k[i]);



  45.     len = length;

  47.     a = b = c = 0x9e3779b9;  /* the golden ratio; an arbitrary value */



  51.     while (12 <= len)

  53.     {

  55.         a += (k[0] +((unsigned int)k[1] << 8) +((unsigned int)k[2] << 16) +((unsigned int)k[3] << 24));

  57.         b += (k[4] +((unsigned int)k[5] << 8) +((unsigned int)k[6] << 16) +((unsigned int)k[7] << 24));

  59.         c += (k[8] +((unsigned int)k[9] << 8) +((unsigned int)k[10]<< 16)+((unsigned int)k[11] << 24));

  61.         mix(a,b,c);

  63.         k += 12;

  65.         len -= 12;

  67.     }



  71.     c += length;

  73.     switch(len)

  75.     {

  77.         case 11: c+=((unsigned int)k[10] << 24);

  79.         case 10: c+=((unsigned int)k[9]  << 16);

  81.         case 9 : c+=((unsigned int)k[8]  << 8);

  83.         case 8 : b+=((unsigned int)k[7] << 24);

  85.         case 7 : b+=((unsigned int)k[6] << 16);

  87.         case 6 : b+=((unsigned int)k[5] << 8);

  89.         case 5 : b+=k[4];

  91.         case 4 : a+=((unsigned int)k[3] << 24);

  93.         case 3 : a+=((unsigned int)k[2] << 16);

  95.         case 2 : a+=((unsigned int)k[1] << 8);

  97.         case 1 : a+=k[0];

  99.     }

  101.     mix(a,b,c);



  105.     return c % cache->hashitemnum;

  107. }
复制代码

这段代码看不懂啊。。版主能粗略的讲解一下么？
是寻找节点所在的hash表的索引吗？
作者: converse    时间: 2008-04-03 09:30
标题: 回复 #21 yangsf5 的帖子
你的理解是对的.
作者: yangsf5    时间: 2008-04-03 09:59
哈哈，关于本函数用途的理解是因为你代码里有上下逻辑。。。

但是，你的这个算法我看不懂阿，晕糊糊的。。

我是个unix编程初学者，要是版主能有时间详讲一下这段代码，那该多好阿。。


晕的我都不知道为啥要建多个哈希表了。。
作者: converse    时间: 2008-04-03 10:51
标题: 回复 #23 yangsf5 的帖子
这个hash算法我也不懂,抄的,能用就是.
一个好的hash算法有一个标准,就是要求hash出来的index能够尽可能的平均分布.
作者: yangsf5    时间: 2008-04-03 11:16
还没明白的地方：
这个cache里，可以有多张哈希表。。
建多张表的用意是：可以多张表并行的处理同时要求处理的太多的结点吗？

如果是这样，那个算法是否处理了同个结点的位置唯一性？
作者: hantangwang    时间: 2008-04-03 15:35
提示: 作者被禁止或删除 内容自动屏蔽
作者: 鸡鸡歪歪    时间: 2008-04-03 17:13
*** 作者被禁止或删除 内容自动屏蔽 ***
作者: xulei_ice    时间: 2008-04-03 21:00
标题: 楼主的精神可佳， 支持。
建议参考一下开源的数据库berkeley db.  感觉你的思路跟berkeley db很像， 从中可以参考和借鉴一下。

预祝你的数据库越来越完善！
作者: mantiser    时间: 2008-04-04 03:54
不错。哈哈。。谁共享下。。块内存管理，链接管理的代码出来。。谢谢。
作者: mantiser    时间: 2008-04-04 04:01
看了下代码。哈。。

发现你也喜欢用自动生成API参考。。是doxgen吗。。。

到此下载：http://webscripts.softpedia.com/ ... /Doxygen-15198.html

[ 本帖最后由 mantiser 于 2008-4-4 04:11 编辑 ]
作者: yangsf5    时间: 2008-04-04 13:10
原帖由 yangsf5 于 2008-4-3 11:16 发表
还没明白的地方：
这个cache里，可以有多张哈希表。。
建多张表的用意是：可以多张表并行的处理同时要求处理的太多的结点吗？

如果是这样，那个算法是否处理了同个结点的位置唯一性？



都那么强，就没人回答我的问题吗？
作者: converse    时间: 2008-04-04 16:37
插入节点的时候,首先会在所在HASH表中查找节点是否已经存在,如果存在报错退出,否则进行插入操作,在函数insert_data中.

有问题,Read The Fu**ing Source, pls.
作者: jamesr    时间: 2008-04-04 16:58
提示: 作者被禁止或删除 内容自动屏蔽
作者: converse    时间: 2008-04-05 00:46
标题: 回复 #33 jamesr 的帖子
关于这个问题,我决定以后的版本注释一律采用英文注释.
作者: SupervisedBoy    时间: 2008-04-05 12:33
楼主用mmap文件存储数据，应该用的是文件锁吧。文件锁支持按偏移和大小加锁的，不用每次锁住全部。
作者: converse    时间: 2008-04-05 16:39
之所以要采用全局锁,是因为一直没有解决这样的问题:

进程A要对hash表a进行插入操作,此时锁住hash表a,但是发现当前已经没有空闲节点,要采用淘汰算法进行淘汰,假设需要淘汰hash表b上的一个节点,此时hash表b已经被另一个进程B锁住,而进程B要进行淘汰的节点又在hash表a上,如此情况,造成死锁.

因此,现在的折中策略是对全局进行加锁,减少锁粒度属于今后的优化,暂缓.
作者: iunknown    时间: 2008-04-05 20:20
原帖由 converse 于 2008-4-2 11:51 发表
同时还有unlock_cache api,因为某些使用C++的用户如果使用了C++的异常处理,在调用ccache中的API时抛出异常将导致ccache没有解锁
, 以后就不能再使用了, 提供这个API是为了在抛出异常的时候用户自己释放锁


对于这个问题，在 c++ 中倒是可以通过 RAII 来处理。
RAII英文意思：Resource acquisition is initialization，资源获取即初始化。该原则或技术用于对资源的管理。其核心思想，就是在对象的生命周期中，资源总是有效。而对象结束时，资源会自动释放。

典型的实现

  2. class MutexGuard {
  3. public:
  4.     MutexGuard( Lock_t * lock ) {
  5.         mLock = lock;
  6.         lock->lock();
  7.     }

  9.     ~MutexGuard() {
  10.         mLock->unlock();
  11.     }

  13. private:
  14.     Lock_t * mLock;
  15. };

  17. void Cache :: put( ... )
  18. {
  19.     MutexGuard guard( mLock );

  21.     ..........
  22. }
复制代码

[ 本帖最后由 iunknown 于 2008-4-5 20:23 编辑 ]
作者: lysde    时间: 2008-04-07 13:43
支持,有时间学学...
作者: yangsf5    时间: 2008-04-11 21:51

  2. int find_data(const void* key, void* data, ccache_t* cache, cmpfun cmp)
  3. {
  4.     int hashindex = hash(key, cache), ret;
  5.     void *nodedata;
  6.     node_t *node;

  8.     if (0 > lock(&(cache->mutex)))
  9.     {
  10.         return -1;
  11.     }

  13.     ret = FIND_NODE(hashindex, key, cache, cmp);

  15.     if (0 <= ret)
  16.     {
  17.         if (NULL != data)
  18.         {
  19.             node = NODE(cache, ret);
  20.             nodedata = NODE_DATA(node);
  21.             memcpy(data, nodedata, node->datasize);
  22.         }
  23.         linktolrulisthead(ret, cache);
  24.     }

  26.     if (0 > unlock(&(cache->mutex)) || 0 > ret)
  27.     {
  28.         return -1;
  29.     }
  30.     return ret;
  31. }
复制代码

搂住这个函数有问题。。。
在调用这个函数时，对返回值进行判断。
>=0...说明节点存在。。
但是对于－1，就不能确定了：
可以是还没判断就因为锁出错返回－1；也可以是没有这个节点返回－1(因为链表里的最后一个节点的next是－1)。
（算了，不愿回答就算了。。。）

  2. int list_findnode(int hashindex, const void* key, ccache_t* cache, cmpfun cmp)
  3. {
  4.     hashitem_t *hashitem = HASH_ITEM(cache, hashindex);
  5.     int index = hashitem->first;
  6.     node_t *node;
  7.     void* nodekey;

  9.     while (0 <= index)
  10.     {
  11.         node = NODE(cache, index);
  12.         nodekey = NODE_KEY(node);
  13.         if (!cmp(key, nodekey))
  14.         {
  15.             break;
  16.         }

  18.         index = node->next;
  19.     }

  21.     return index;
  22. }
复制代码

[ 本帖最后由 yangsf5 于 2009-1-5 13:06 编辑 ]
作者: converse    时间: 2008-08-07 17:29
新版本发布,这次最大的feature就是支持可变长key/value了,请见首页更新说明.
作者: e_sharp    时间: 2008-08-12 16:01
好人

学习
作者: qliu00    时间: 2008-08-12 16:03
学习一下cache库ccache ，楼主好强
作者: chenyajun5    时间: 2008-08-13 11:11
有人把memcached和Berkeley db结合成memcachedb，这样既兼容memcached的协议，又能保证持久性。。。
作者: newIT666    时间: 2008-08-13 11:14
原帖由 chenyajun5 于 2008-8-13 11:11 发表
有人把memcached和Berkeley db结合成memcachedb，这样既兼容memcached的协议，又能保证持久性。。。


学习了.
作者: gawk    时间: 2008-08-20 14:25
关注
作者: epegasus    时间: 2008-08-21 10:05
这个在嵌入式的板子上不可用啊
作者: zhhsboy    时间: 2008-08-29 17:49
作者: hb12112    时间: 2008-08-29 18:02
作者: converse    时间: 2008-11-01 00:08
2008-10-31发布0.4版本:

0.4版本(2008-10-31)
1)将原先的线程锁改成了线程读写锁,这个变化会让操作更快些,在查找,遍历操作的时候使用的是读锁,插入,删除,更新,替换等
会改变cache中元素的操作使用的是写锁.
2)将原先的API命名方式做了改变,变为ccache_***方式的命名, 这也是很多项目的命名方式, 但是其他未向外公开的API没有改变
命名方式,我在想是不是要把所有的函数都改成ccache_***的命名方式, 似乎这样更加统一一些.
3)另外, 原来的一个API, update_or_insert_data,命名方式太丑陋了, 改成了replace, 按照现在的命名方式, 这个API的名字
就是ccache_replace.
4)原先的operator.h/.c文件被删除, 取而代之的是functor.h/.c文件, 同时将插入,替换,更新,查找,删除,访问等操作作为函数指针封装到functor_t结构体
中, 这样以后采用其他的数据结构只要初始化不同的函数指针就可以了.


点击这里下载新版.

[ 本帖最后由 converse 于 2008-11-1 09:38 编辑 ]
作者: heixiake    时间: 2008-11-03 16:02
不明白
作者: cxjnet    时间: 2008-11-14 10:19
不错，学习一下
作者: chary8088    时间: 2008-11-14 10:43
mark
作者: carl_lau    时间: 2008-11-14 14:10
拜牛人来的
作者: converse    时间: 2008-11-14 17:00
0.5版本(2008-11-14)
1) 加入对红黑树的支持, 可以在编译的时候决定使用的是hash-list还是hash-rbtree结构体进行数据的存储,具体请见makefile
2) 加入了一个数据结构对insert,find,erase,update,replace等操作进行统计, 参见ccache.h中的ccache_stat_t的结构体,另外在
测试程序中也加入了演示打印这些数据的函数,参见test中的测试代码.
3) 对hash-list算法进行了改进, 在访问到某一个节点的时候, 会让这个节点所在的链表位置向前走一步, 这样访问越频繁的节点就越靠近
链表头部,参见ccache_lis.c中的ccache_list_advance函数, 每次访问了某个节点就会去调用该函数.
4) 同样的,LRU链表算法也进行了改善,之前是访问的节点马上就更新到该LRU链表的头部, 现在也更改为每次向前走一步,
参见ccache_lrulist.c中的ccache_lrulist_advance函数.
5) 代码风格的调整, 所有的文件名,函数名, 宏名, 自定义类型名称都加上了"ccache_"前缀.

点击这里下载.

发布了这个版本之后,貌似我想不到其他比较大的feature, 最近的一段时间内除非有bug的改正, 否则不会发布新的版本了,我将抽时间整理出一份文档讲解ccache的实现.
作者: wjian10    时间: 2013-08-08 21:55
mark
有时间学习
作者: csumck    时间: 2013-08-09 09:34
mark 学习一下
作者: djsxut    时间: 2013-08-09 11:01
支持， 回复收藏下。。。
作者: fgkenshin    时间: 2013-08-20 13:52
标记下，有空下下来试试



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2