POCO C++庫學習和分析 -- Cache
1. Cache概述
在STL::map或者STL::set中，容器的尺寸是沒有上限的，數目可以不斷的擴充。並且在STL的容器中，元素是不會自動過期的，除非顯式的被刪除。Poco的Cache可以被看成是STL中容器的一個擴充，容器中的元素會自動過期(即失效)。在Poco實現的Cache框架中，基礎的過期策略有兩種。一種是LRU(Last Recent Used)，另外一種是基於時間的過期(Time based expiration)。在上述兩種過期策略之上，還提供了兩者之間的混合。
下面是相關的類：
1. LRUCache: 最近使用Cache。在內部維護一個Cache的最大容量M，始終只保存M個元素於Cache內部，當第M+1元素插入Cache中時，最先被放入Cache中的元素將失效。
2. ExpireCache: 時間過期Cache。在內部統一管理失效時間T，當元素插入Cache後，超過時間T，則刪除。
3. AccessExpireCache: 時間過期Cache。同ExpireCache不同的是，當元素被訪問後，重新開始計算該元素的超時時間，而不是只從元素插入時開始計時。
4. UniqueExpireCache: 時間過期Cache。同ExpireCache不同的是，每一個元素都有自己單獨的失效時間。
5. UniqueAccessExpireCache：時間過期Cache。同AccessExpireCache不同的是，每一個元素都有自己單獨的失效時間。
6. ExpireLRUCache：時間過期和LRU策略的混合體。當時間過期和LRU任一過期條件被觸發時，容器中的元素失效。
7. AccessExpireLRUCache：時間過期和LRU策略的混合體。同ExpireLRUCache相比，當元素被訪問後，重新開始計算該元素的超時時間，而不是只從元素插入時開始計時。
8. UniqueExpireLRUCache：時間過期和LRU策略的混合體。同ExpireLRUCache相比，每一個元素都有自己單獨的失效時間。
9. UniqueAccessExpireLRUCache：時間過期和LRU策略的混合體。同UniqueExpireLRUCache相比，當元素被訪問後，重新開始計算該元素的超時時間，而不是只從元素插入時開始計時。
2. Cache的內部結構
2.1 Cache類
下面是Poco中Cache的類圖：
從類圖中我們可以看到所有的Cache都有一個對應的strategy類。事實上strategy類負責快速搜索Cache中的過期元素。Cache和strategy采用了Poco中的同步事件機制(POCO C++庫學習和分析 -- 通知和事件 （四） )。
讓我們來看AbstractCache的定義：
[cpp]
template <class TKey, class TValue, class TStrategy, class TMutex = FastMutex, class TEventMutex = FastMutex>
class AbstractCache
/// An AbstractCache is the interface of all caches.
{
public:
FIFOEvent<const KeyValueArgs<TKey, TValue >, TEventMutex > Add;
FIFOEvent<const KeyValueArgs<TKey, TValue >, TEventMutex > Update;
FIFOEvent<const TKey, TEventMutex> Remove;
FIFOEvent<const TKey, TEventMutex> Get;
FIFOEvent<const EventArgs, TEventMutex> Clear;
typedef std::map<TKey, SharedPtr<TValue > > DataHolder;
typedef typename DataHolder::iterator Iterator;
typedef typename DataHolder::const_iterator ConstIterator;
typedef std::set<TKey> KeySet;
AbstractCache()
{
initialize();
}
AbstractCache(const TStrategy& strat): _strategy(strat)
{
initialize();
}
virtual ~AbstractCache()
{
uninitialize();
}
// ...........
protected:
mutable FIFOEvent<ValidArgs<TKey> > IsValid;
mutable FIFOEvent<KeySet> Replace;
void initialize()
/// Sets up event registration.
{
Add += Delegate<TStrategy, const KeyValueArgs<TKey, TValue> >(&_strategy, &TStrategy::onAdd);
Update += Delegate<TStrategy, const KeyValueArgs<TKey, TValue> >(&_strategy, &TStrategy::onUpdate);
Remove += Delegate<TStrategy, const TKey>(&_strategy, &TStrategy::onRemove);
Get += Delegate<TStrategy, const TKey>(&_strategy, &TStrategy::onGet);
Clear += Delegate<TStrategy, const EventArgs>(&_strategy, &TStrategy::onClear);
IsValid += Delegate<TStrategy, ValidArgs<TKey> >(&_strategy, &TStrategy::onIsValid);
Replace += Delegate<TStrategy, KeySet>(&_strategy, &TStrategy::onReplace);
}
void uninitialize()
/// Reverts event registration.
{
Add -= Delegate<TStrategy, const KeyValueArgs<TKey, TValue> >(&_strategy, &TStrategy::onAdd );
Update -= Delegate<TStrategy, const KeyValueArgs<TKey, TValue> >(&_strategy, &TStrategy::onUpdate);
Remove -= Delegate<TStrategy, const TKey>(&_strategy, &TStrategy::onRemove);
Get -= Delegate<TStrategy, const TKey>(&_strategy, &TStrategy::onGet);
Clear -= Delegate<TStrategy, const EventArgs>(&_strategy, &TStrategy::onClear);
IsValid -= Delegate<TStrategy, ValidArgs<TKey> >(&_strategy, &TStrategy::onIsValid);
Replace -= Delegate<TStrategy, KeySet>(&_strategy, &TStrategy::onReplace);
}
void doAdd(const TKey& key, const TValue& val)
/// Adds the key value pair to the cache.
/// If for the key already an entry exists, it will be overwritten.
{
Iterator it = _data.find(key);
doRemove(it);
KeyValueArgs<TKey, TValue> args(key, val);
Add.notify(this, args);
_data.insert(std::make_pair(key, SharedPtr<TValue>(new TValue(val))));
doReplace();
}
void doAdd(const TKey& key, SharedPtr<TValue>& val)
/// Adds the key value pair to the cache.
/// If for the key already an entry exists, it will be overwritten.
{
Iterator it = _data.find(key);
doRemove(it);
KeyValueArgs<TKey, TValue> args(key, *val);
Add.notify(this, args);
_data.insert(std::make_pair(key, val));
doReplace();
}
void doUpdate(const TKey& key, const TValue& val)
/// Adds the key value pair to the cache.
/// If for the key already an entry exists, it will be overwritten.
{
KeyValueArgs<TKey, TValue> args(key, val);
Iterator it = _data.find(key);
if (it == _data.end())
{
Add.notify(this, args);
_data.insert(std::make_pair(key, SharedPtr<TValue>(new TValue(val))));
}
else
{
Update.notify(this, args);
it->second = SharedPtr<TValue>(new TValue(val));
}
doReplace();
}
void doUpdate(const TKey& key, SharedPtr<TValue>& val)
/// Adds the key value pair to the cache.
/// If for the key already an entry exists, it will be overwritten.
{
KeyValueArgs<TKey, TValue> args(key, *val);
Iterator it = _data.find(key);
if (it == _data.end())
{
Add.notify(this, args);
_data.insert(std::make_pair(key, val));
}
else
{
Update.notify(this, args);
it->second = val;
}
doReplace();
}
void doRemove(Iterator it)
/// Removes an entry from the cache. If the entry is not found
/// the remove is ignored.
{
if (it != _data.end())
{
Remove.notify(this, it->first);
_data.erase(it);
}
}
bool doHas(const TKey& key) const
/// Returns true if the cache contains a value for the key
{
// ask the strategy if the key is valid
ConstIterator it = _data.find(key);
bool result = false;
if (it != _data.end())
{
ValidArgs<TKey> args(key);
IsValid.notify(this, args);
result = args.isValid();
}
return result;
}
SharedPtr<TValue> doGet(const TKey& key)
/// Returns a SharedPtr of the cache entry, returns 0 if for
/// the key no value was found
{
Iterator it = _data.find(key);
SharedPtr<TValue> result;
if (it != _data.end())
{
// inform all strategies that a read-access to an element happens
Get.notify(this, key);
// ask all strategies if the key is valid
ValidArgs<TKey> args(key);
IsValid.notify(this, args);
if (!args.isValid())
{
doRemove(it);
}
else
{
result = it->second;
}
}
return result;
}
void doClear()
{
static EventArgs _emptyArgs;
Clear.notify(this, _emptyArgs);
_data.clear();
}
void doReplace()
{
std::set<TKey> delMe;
Replace.notify(this, delMe);
// delMe contains the to be removed elements
typename std::set<TKey>::const_iterator it = delMe.begin();
typename std::set<TKey>::const_iterator endIt = delMe.end();
for (; it != endIt; ++it)
{
Iterator itH = _data.find(*it);
doRemove(itH);
}
}
TStrategy _strategy;
mutable DataHolder _data;
mutable TMutex _mutex;
private:
// ....
};
從上面的定義中，可以看到AbstractCache是一個value的容器，采用map保存數據，
[cpp]
mutable std::map<TKey, SharedPtr<TValue > > _data;
另外AbstractCache中還定義了一個TStrategy對象，
[cpp]
TStrategy _strategy;
並且在AbstractCache的initialize()函數中，把Cache的一些函數操作委托給TStrategy對象。其函數操作接口為：
1. Add : 向容器中添加元素
2. Update : 更新容器中元素
3. Remove : 刪除容器中元素
4. Get : 獲取容器中元素
5. Clear : 清除容器中所有元素
6. IsValid: 容器中是否某元素
7. Replace: 按照策略從strategy中獲取過期元素，並從Cache和Strategy中同時刪除。將觸發一系列的Remove函數。
這幾個操作中最復雜的是Add操作，其中包括了Remove、Insert和Replace操作。
[cpp]
void doAdd(const TKey& key, SharedPtr<TValue>& val)
/// Adds the key value pair to the cache.
/// If for the key already an entry exists, it will be overwritten.
{
Iterator it = _data.find(key);
doRemove(it);
KeyValueArgs<TKey, TValue> args(key, *val);
Add.notify(this, args);
_data.insert(std::make_pair(key, val));
doReplace();
}
而Replace操作可被Add、Update、Get操作觸發。這是因為Cache並不是一個主動對象(POCO C++庫學習和分析 -- 線程 （四）)，不會自動的把元素標志為失效，需要外界也就是調用方觸發進行。
在Cache類中另外一個值得注意的地方是，保存的是TValue的SharedPtr。之所以這麼設計，是為了線程安全，由於replace操作可能被多個線程調用，所以解決的方法，要麼是返回TValue的SharedPtr，要麼是返回TValue的拷貝。同拷貝方法相比，SharedPtr的方法要更加廉價。
2.2 Strategy類
Strategy類完成了對_data中保存的<key-value>pair中key的排序工作。每個Strategy中都存在一個key的容器，其中LRUStrategy中是std::list<TKey>，ExpireStrategy、UniqueAccessExpireStrategy、UniqueExpireStrategy中是std::multimap<Timestamp, TKey>。這說明在std::list和multimap中存儲了key的信息，以及不同策略下的key的權重信息。對於LRU策略，每次訪問都會使key被重置於list的最前端，key的權重相當於位置信息。而在Time Expire策略下，權重的額外信息為Timestamp，所以采用了multimap。在multimap和lis容器中，key的權重信息是pair的key，而key是value。因此為了實現對multimap和list快速訪問，所有的strategy類中配套了multimap和list的pair的索引，在pair被插入multimap和lis容器時，保存pair在容器的iterator。保存索引的類在strategy中被稱為Index，實際上它是一個std::map<TKey, Iterator>。
讓我們來看一下Strategy類中的replace操作。
[cpp]
ExpireStrategy類的Replace操作定義如下：
void onReplace(const void*, std::set<TKey>& elemsToRemove)
{
// Note: replace only informs the cache which elements
// it would like to remove!
// it does not remove them on its own!
IndexIterator it = _keyIndex.begin();
while (it != _keyIndex.end() && it->first.isElapsed(_expireTime))
{
elemsToRemove.insert(it->second);
++it;
}
}
可以看出ExpireStrategy的replace操作對Index容器做了遍歷，來找出失效元素。效率是不高的。
LRUStrategy類的Replace操作定義如下：
[cpp]
void onReplace(const void*, std::set<TKey>& elemsToRemove)
{
// Note: replace only informs the cache which elements
// it would like to remove!
// it does not remove them on its own!
std::size_t curSize = _keyIndex.size();
if (curSize < _size)
{
return;
}
std::size_t diff = curSize - _size;
Iterator it = --_keys.end(); //--keys can never be invoked on an empty list due to the minSize==1 requirement of LRU
std::size_t i = 0;
while (i++ < diff)
{
elemsToRemove.insert(*it);
if (it != _keys.begin())
{
--it;
}
}
}
LRUStrategy的replace操作是，只在curSize超過設定的訪問上限_size時觸發，把list容器中排在末尾的(curSize-_size)個元素標志為失效。
3. 開銷
Poco中的Cache類比std::map要慢，其中開銷最大的操作為add操作。采用Time Expire策略的Cache要比采用LRU策略的Cache更慢。並且由於Cache類引入了SharePtr和Strategy，其空間花費也要大於std::map。所以在沒有必要使用Cache的情況下，還是使用map較好。
4. 例子
下面是Cache的一個示例：
[cpp]
#include "Poco/LRUCache.h"
int main()
{
Poco::LRUCache<int, std::string> myCache(3);
myCache.add(1, "Lousy"); // |-1-| -> first elem is the most popular one
Poco::SharedPtr<std::string> ptrElem = myCache.get(1); // |-1-|
myCache.add(2, "Morning"); // |-2-1-|
myCache.add(3, "USA"); // |-3-2-1-|
// now get rid of the most unpopular entry: "Lousy"
myCache.add(4, "Good"); // |-4-3-2-|
poco_assert (*ptrElem == "Lousy"); // content of ptrElem is still valid
ptrElem = myCache.get(2); // |-2-4-3-|
// replace the morning entry with evening
myCache.add(2, "Evening"); // 2 Events: Remove followed by Add
}
