bitsCN.com
Key-Value缓存有很多，用的较多的是memcache、redis，他们都是以独立服务的形式运行，在工作中有时需要嵌入一个本地的key-value缓存，当然已经有LevelDb等，但感觉还是太重量级了。
本文实现了一种超级轻量的缓存，
1、实现代码仅仅需要400行；
2、性能高效，value长度在1K时测试速度在每秒200万左右
3、缓存是映射到文件中的，所以没有malloc、free的开销，以及带来的内存泄露、内存碎片等；
4、如果服务挂掉了，重启后缓存内容继续存在；
5、如果把缓存映射到磁盘文件就算机器挂了，缓存中内容还是会存在，当然有可能会出现数据损坏的情况；
6、一定程度上实现了LRU淘汰算法，实现的LRU不是全局的只是一条链上的，所以只能说在一定程序上实现了；
7、稳定，已经在多个项目中运用，线上部署的机器有几十台，运行了大半年了没出过问题；
8、普通的缓存key、value都是字符串的形式，此缓存的key、value都可以是class、struct对象结构使用更方便；
老规矩直接上代码：
templateclass HashTable{public: HashTable(const char *tablename, uint32_t tableLen, uint32_t nodeTotal); virtual ~HashTable(); bool Add(K &key, V &value) { AutoLock autoLock(m_MutexLock); //check is exist uint32_t nodeId = GetIdByKey(key); if(nodeId != m_InvalidId) return false; nodeId = GetFreeNode(); if(nodeId == m_InvalidId) return false; uint32_t hashCode = key.HashCode(); Entry *tmpNode = m_EntryAddr + nodeId; tmpNode->m_Key = key; tmpNode->m_Code = hashCode; tmpNode->m_Value = value; uint32_t index = hashCode % m_HeadAddr->m_TableLen; AddNodeToHead(index, nodeId); return true; } bool Del(K &key) { AutoLock autoLock(m_MutexLock); uint32_t nodeId = GetIdByKey(key); if(nodeId == m_InvalidId) return false; uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen; return RecycleNode(index, nodeId); } bool Set(K &key, V &value) { AutoLock autoLock(m_MutexLock); uint32_t nodeId = GetIdByKey(key); if(nodeId == m_InvalidId) return false; (m_EntryAddr + nodeId)->m_Value = value; return true; } bool Get(K &key, V &value) { AutoLock autoLock(m_MutexLock); uint32_t nodeId = GetIdByKey(key); if(nodeId == m_InvalidId) return false; value = (m_EntryAddr + nodeId)->m_Value; return true; } bool Exist(K &key) { AutoLock autoLock(m_MutexLock); uint32_t nodeId = GetIdByKey(key); if(nodeId == m_InvalidId) return false; return true; } uint32_t Count() { AutoLock autoLock(m_MutexLock); return m_HeadAddr->m_UsedCount; } //if exist set else add bool Replace(K &key, V &value) { AutoLock autoLock(m_MutexLock); if(Exist(key)) return Set(key, value); else return Add(key, value); } /*********************************************** ****LRU: when visit a node, move it to head **** ************************************************/ //if no empty place,recycle tail bool LruAdd(K &key, V &value, K &recyKey, V &recyValue, bool &recycled) { AutoLock autoLock(m_MutexLock); if(Exist(key)) return false; if(Add(key, value)) return true; uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen; uint32_t tailId = GetTailNodeId(index); if(tailId == m_InvalidId) return false; Entry *tmpNode = m_EntryAddr + tailId; recyKey = tmpNode->m_Key; recyValue = tmpNode->m_Value; recycled = true; RecycleNode(index, tailId); return Add(key, value); } bool LruSet(K &key, V &value) { AutoLock autoLock(m_MutexLock); if(Set(key, value)) return MoveToHead(key); else return false; } bool LruGet(K &key, V &value) { AutoLock autoLock(m_MutexLock); if(Get(key, value)) return MoveToHead(key); else return false; } //if exist set else add; if add failed recycle tail than add bool LruReplace(K &key, V &value, K &recyKey, V &recyValue, bool &recycled) { AutoLock autoLock(m_MutexLock); recycled = false; if(Exist(key)) return LruSet(key, value); else return LruAdd(key, value, recyKey, recyValue, recycled); } void Clear() { AutoLock autoLock(m_MutexLock); m_HeadAddr->m_FreeBase = 0; m_HeadAddr->m_RecycleHead = 0; m_HeadAddr->m_UsedCount = 0; for(uint32_t i = 0; i < m_HeadAddr->m_TableLen; ++i) { (m_ArrayAddr+i)->m_Head = m_InvalidId; (m_ArrayAddr+i)->m_Tail = m_InvalidId; } } int GetRowKeys(vector &keys, uint32_t index) { AutoLock autoLock(m_MutexLock); if(index >= m_HeadAddr->m_TableLen) return -1; keys.clear(); keys.reserve(16); int count = 0; Array *tmpArray = m_ArrayAddr + index; uint32_t nodeId = tmpArray->m_Head; while(nodeId != m_InvalidId) { Entry *tmpNode = m_EntryAddr + nodeId; keys.push_back(tmpNode->m_Key); nodeId = tmpNode->m_Next; ++count; } return count; } void *Padding(uint32_t size) { AutoLock autoLock(m_MutexLock); if(size > m_HeadSize - sizeof(TableHead)) return NULL; else return m_HeadAddr->m_Padding; }private: static const uint32_t m_InvalidId = 0xffffffff; static const uint32_t m_HeadSize = 1024; struct TableHead { uint32_t m_TableLen; uint32_t m_NodeTotal; uint32_t m_FreeBase; uint32_t m_RecycleHead; uint32_t m_UsedCount; char m_TableName[256]; uint32_t m_Padding[0]; }; struct Array { uint32_t m_Head; uint32_t m_Tail; }; struct Entry { V m_Value; K m_Key; uint32_t m_Code; uint32_t m_Next; uint32_t m_Prev; }; size_t m_MemSize; uint8_t *m_MemAddr; TableHead *m_HeadAddr; Array *m_ArrayAddr; Entry *m_EntryAddr; ThreadMutex m_MutexLock; bool MoveToHead(K &key); uint32_t GetIdByKey(K &key); void AddNodeToHead(uint32_t index, uint32_t nodeId); bool MoveNodeToHead(uint32_t index, uint32_t nodeId); bool RecycleNode(uint32_t index, uint32_t nodeId); uint32_t GetTailNodeId(uint32_t index); uint32_t GetFreeNode(); DISABLE_COPY_AND_ASSIGN(HashTable);};templateHashTable::HashTable(const char *tablename, uint32_t tableLen, uint32_t nodeTotal){ AbortAssert(tablename != NULL); m_MemSize = m_HeadSize + tableLen*sizeof(Array) + nodeTotal*sizeof(Entry); m_MemAddr = (uint8_t*)MemFile::Realloc(tablename, m_MemSize); AbortAssert(m_MemAddr != NULL); m_HeadAddr = (TableHead*)(m_MemAddr); m_ArrayAddr = (Array*)(m_MemAddr + m_HeadSize); m_EntryAddr = (Entry*)(m_MemAddr + m_HeadSize + tableLen*sizeof(Array)); m_HeadAddr->m_TableLen = tableLen; m_HeadAddr->m_NodeTotal = nodeTotal; strncpy(m_HeadAddr->m_TableName, tablename, sizeof(m_HeadAddr->m_TableName)); if(m_HeadAddr->m_UsedCount == 0)//if first use init array to invalid id { for(uint32_t i = 0; i < tableLen; ++i) { (m_ArrayAddr+i)->m_Head = m_InvalidId; (m_ArrayAddr+i)->m_Tail = m_InvalidId; } m_HeadAddr->m_FreeBase = 0; m_HeadAddr->m_RecycleHead = 0; }}templateHashTable::~HashTable(){ MemFile::Release(m_MemAddr, m_MemSize);}templatebool HashTable::MoveToHead(K &key){ uint32_t nodeId = GetIdByKey(key); uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen; return MoveNodeToHead(index, nodeId);}templateuint32_t HashTable::GetIdByKey(K &key){ uint32_t hashCode = key.HashCode(); uint32_t index = hashCode % m_HeadAddr->m_TableLen; Array *tmpArray = m_ArrayAddr + index; uint32_t nodeId = tmpArray->m_Head; while(nodeId != m_InvalidId) { Entry *tmpNode = m_EntryAddr + nodeId; if(tmpNode->m_Code == hashCode && key.Equals(tmpNode->m_Key)) break; nodeId = tmpNode->m_Next; } return nodeId;}templatevoid HashTable::AddNodeToHead(uint32_t index, uint32_t nodeId){ if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return; Array *tmpArray = m_ArrayAddr + index; Entry *tmpNode = m_EntryAddr + nodeId; if(m_InvalidId == tmpArray->m_Head) { tmpArray->m_Head = nodeId; tmpArray->m_Tail = nodeId; } else { tmpNode->m_Next = tmpArray->m_Head; (m_EntryAddr + tmpArray->m_Head)->m_Prev = nodeId; tmpArray->m_Head = nodeId; }}templatebool HashTable::MoveNodeToHead(uint32_t index, uint32_t nodeId){ if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return false; Array *tmpArray = m_ArrayAddr + index; Entry *tmpNode = m_EntryAddr + nodeId; //already head if(tmpArray->m_Head == nodeId) { return true; } uint32_t nodePrev = tmpNode->m_Prev; uint32_t nodeNext = tmpNode->m_Next; (m_EntryAddr+nodePrev)->m_Next = nodeNext; if(nodeNext != m_InvalidId) { (m_EntryAddr+nodeNext)->m_Prev = nodePrev; } else { tmpArray->m_Tail = nodePrev; } tmpNode->m_Prev = m_InvalidId; tmpNode->m_Next = tmpArray->m_Head; (m_EntryAddr + tmpArray->m_Head)->m_Prev = nodeId; tmpArray->m_Head = nodeId; return true;}templatebool HashTable::RecycleNode(uint32_t index, uint32_t nodeId){ if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return false; Array *tmpArray = m_ArrayAddr + index; Entry *tmpNode = m_EntryAddr + nodeId; uint32_t nodePrev = tmpNode->m_Prev; uint32_t nodeNext = tmpNode->m_Next; if(nodePrev != m_InvalidId) { (m_EntryAddr + nodePrev)->m_Next = nodeNext; } else { tmpArray->m_Head = nodeNext; } if(nodeNext != m_InvalidId) { (m_EntryAddr + nodeNext)->m_Prev = nodePrev; } else { tmpArray->m_Tail = nodePrev; } (m_EntryAddr+nodeId)->m_Next = m_HeadAddr->m_RecycleHead; m_HeadAddr->m_RecycleHead = nodeId; --(m_HeadAddr->m_UsedCount); return true;}templateuint32_t HashTable::GetTailNodeId(uint32_t index){ if(index >= m_HeadAddr->m_TableLen) return m_InvalidId; Array *tmpArray = m_ArrayAddr + index; return tmpArray->m_Tail;}templateuint32_t HashTable::GetFreeNode(){ uint32_t nodeId = m_InvalidId; if(m_HeadAddr->m_UsedCount < m_HeadAddr->m_FreeBase)//get from recycle list { nodeId = m_HeadAddr->m_RecycleHead; m_HeadAddr->m_RecycleHead = (m_EntryAddr+nodeId)->m_Next; ++(m_HeadAddr->m_UsedCount); } else if(m_HeadAddr->m_UsedCount < m_HeadAddr->m_NodeTotal)//get from free mem { nodeId = m_HeadAddr->m_FreeBase; ++(m_HeadAddr->m_FreeBase); ++(m_HeadAddr->m_UsedCount); } else { nodeId = m_InvalidId; } //init node if(nodeId < m_HeadAddr->m_NodeTotal) { Entry *tmpNode = m_EntryAddr + nodeId; memset(tmpNode, 0, sizeof(Entry)); tmpNode->m_Next = m_InvalidId; tmpNode->m_Prev = m_InvalidId; } return nodeId;}
bitsCN.com
