開(kāi)發(fā)互聯(lián)網(wǎng)的server系統(tǒng)，難免會(huì)用一些cache機(jī)制，通常在Linux下多使用共享內(nèi)存機(jī)制，把分配的內(nèi)存組織成一個(gè)特定的數(shù)據(jù)結(jié)構(gòu)，用來(lái)緩存后端DB的數(shù)據(jù)，加速讀寫(xiě)。但是對(duì)一些新手而言，共享內(nèi)存的使用還是有一些門(mén)檻，與此同時(shí)STL的使用卻是相對(duì)容易上手，所以可以通過(guò)STL的容器組合出一個(gè)cache來(lái)。
上網(wǎng)搜了一下，看到已經(jīng)有人做了一些類似的事情，具體可以參看http://bytes.com/forum/thread640146.html，作者采用STL::map（當(dāng)然也可以是hash_map做數(shù)據(jù)緩存cache），采用一個(gè)list做lru鏈，每當(dāng)讀寫(xiě)cache中的數(shù)據(jù)時(shí)，都要在lru鏈中刪除該key值對(duì)應(yīng)的項(xiàng)，并把該數(shù)據(jù)的key值重新放到頭部，這里面有個(gè)相對(duì)較慢的地方就是從lru鏈中刪除key值對(duì)應(yīng)的項(xiàng)的操作，因?yàn)閯h除操作表面看也僅是erase，但是其中也是順序查找出來(lái)再刪，相對(duì)耗時(shí)。可以針對(duì)此對(duì)之進(jìn)行改進(jìn)。
采用STL::map做lru鏈，map::first是一個(gè)“虛時(shí)間”，表示訪問(wèn)某一個(gè)key的虛時(shí)間，map::second就是key值，同樣另外一個(gè)map做cache緩存數(shù)據(jù)，first為key，second為（value，virtual_time)對(duì)，這樣當(dāng)讀寫(xiě)一個(gè)key的數(shù)據(jù)時(shí)，可以快速定位到該數(shù)據(jù)，并且可以查找到它的上次訪問(wèn)時(shí)間，從而在lru鏈里面快速定位（樹(shù)上的查找終究要快）并刪除，再更新key的訪問(wèn)時(shí)間并插入到lru鏈中就可以了。
當(dāng)cache過(guò)大了，比如緩存最多100，那么就可以從lru鏈的頭部開(kāi)始淘汰了，（因?yàn)閘ru鏈first值越小，表示訪問(wèn)越久了）。代碼貼在下面，歡迎批評(píng)指證。與上面文章里的相比，代碼簡(jiǎn)化了給多，這樣比較方便閱讀，另外考慮到數(shù)據(jù)多是blob，所以cache中的value就采用stl::string了。
STL做cache的幾個(gè)缺點(diǎn)：
1 由于cache的數(shù)據(jù)在堆棧中，所以server一旦core掉就丟了；
2 鑒于上述原因，所以這種cache適合“讀多寫(xiě)少”的業(yè)務(wù)，一旦有“寫(xiě)入”操作，就和數(shù)據(jù)庫(kù)同步更新，這樣的話淘汰的時(shí)候也比較簡(jiǎn)單，直接丟掉就好了，不存在“臟數(shù)據(jù)”的概念。
當(dāng)然，對(duì)于海量用戶訪問(wèn)的業(yè)務(wù)，還是建議用共享內(nèi)存做cache機(jī)制，這樣讀寫(xiě)的效率都會(huì)提高，并且程序出問(wèn)題數(shù)據(jù)仍然在，但是壞處就是會(huì)帶來(lái)復(fù)雜性和好多其它的問(wèn)題，就不在這里說(shuō)了。
#ifndef _MAP_LRU_CACHE_H_
#define _MAP_LRU_CACHE_H_
#include <string.h>
#include <iostream>
#include <list>
#include <map>
using namespace std;
namespace lru_cache {
static const int DEF_CAPACITY = 100000;
typedef unsigned long long virtual_time;
typedef struct _HashKey
{// key的類型自定義，重要的是要overload <和==
｝HashKey;
typedef struct _HashValue
{
string value_;
virtual_time access_;
}HashValue;
class CLRUCache
{
public:
CLRUCache() : _lru_list(), _hash_table(), _now(0){}
virtual ~CLRUCache(){}
int set( const HashKey& key, const string &value );
HashValue* get( const HashKey& key );
unsigned get_lru_list_size(){ return (unsigned)_lru_list.size(); }
unsigned get_hash_table_size() { return (unsigned)_hash_table.size(); }
virtual_time get_now() { return _now; }
private:
virtual_time get_virtual_time()
{
return ++_now;
}
map<virtual_time, HashKey> _lru_list;
map<HashKey, HashValue> _hash_table;
virtual_time _now;
};
}
#endif
#include "map_lru_cache.h"
using namespace lru_cache;
int CLRUCache::set( const HashKey& key, const string &value )
{
HashValue hash_value;
hash_value.value_ = value;
hash_value.access_ = get_virtual_time();
pair< map<HashKey, HashValue>::iterator, bool > ret = _hash_table.insert(make_pair(key, hash_value));
if ( !ret.second )
{
// key already exist
virtual_time old_access = _hash_table[key].access_;
map<virtual_time, HashKey>::iterator iter = _lru_list.find(old_access);
if(iter != _lru_list.end())
{
_lru_list.erase(iter);
}
_lru_list.insert(make_pair(hash_value.access_, key));
_hash_table[key] = hash_value;
}
else
{
_lru_list.insert(make_pair(hash_value.access_, key));
if ( _hash_table.size() > DEF_CAPACITY ) //ÌÔÌ
{
// get the least recently used key
map<virtual_time, HashKey>::iterator iter = _lru_list.begin();
_hash_table.erase( iter->second );
// remove last key from list
_lru_list.erase(iter);
}
}
return 0;
}
HashValue* CLRUCache::get( const HashKey& key )
{
map<HashKey, HashValue>::iterator iter = _hash_table.find(key);
if ( iter != _hash_table.end() )
{
virtual_time old_access = iter->second.access_;
iter->second.access_ = get_virtual_time();
map<virtual_time, HashKey>::iterator it = _lru_list.find(old_access);
if(it != _lru_list.end())
{
_lru_list.erase(it);
}
_lru_list.insert(make_pair(iter->second.access_, key));
return &(iter->second);
}
else
return NULL;
}