《Mysql入門mysql實(shí)現(xiàn)本地keyvalue數(shù)據(jù)庫(kù)緩存示例》要點(diǎn)：
本文介紹了Mysql入門mysql實(shí)現(xiàn)本地keyvalue數(shù)據(jù)庫(kù)緩存示例，希望對(duì)您有用。如果有疑問(wèn)，可以聯(lián)系我們。
MYSQL入門Key-Value緩存有很多,用的較多的是memcache、redis,他們都是以獨(dú)立服務(wù)的形式運(yùn)行,在工作中有時(shí)需要嵌入一個(gè)本地的key-value緩存,當(dāng)然已經(jīng)有LevelDb等,但感覺(jué)還是太重量級(jí)了.
MYSQL入門本文實(shí)現(xiàn)了一種超級(jí)輕量的緩存,
MYSQL入門1、實(shí)現(xiàn)代碼僅僅需要400行；
MYSQL入門2、性能高效,value長(zhǎng)度在1K時(shí)測(cè)試速度在每秒200萬(wàn)左右
MYSQL入門3、緩存是映射到文件中的,所以沒(méi)有malloc、free的開銷,以及帶來(lái)的內(nèi)存泄露、內(nèi)存碎片等；
MYSQL入門4、如果服務(wù)掛掉了,重啟后緩存內(nèi)容繼續(xù)存在；
MYSQL入門5、如果把緩存映射到磁盤文件就算機(jī)器掛了,緩存中內(nèi)容還是會(huì)存在,當(dāng)然有可能會(huì)出現(xiàn)數(shù)據(jù)損壞的情況；
MYSQL入門6、一定程度上實(shí)現(xiàn)了LRU淘汰算法,實(shí)現(xiàn)的LRU不是全局的只是一條鏈上的,所以只能說(shuō)在一定程序上實(shí)現(xiàn)了；
MYSQL入門7、穩(wěn)定,已經(jīng)在多個(gè)項(xiàng)目中運(yùn)用,線上部署的機(jī)器有幾十臺(tái),運(yùn)行了大半年了沒(méi)出過(guò)問(wèn)題；
MYSQL入門8、普通的緩存key、value都是字符串的形式,此緩存的key、value都可以是class、struct對(duì)象結(jié)構(gòu)使用更方便；
MYSQL入門?老規(guī)矩直接上代碼：
MYSQL入門?
代碼如下:
?template<typename K, typename V>
class 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<K> &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);
};
template<typename K, typename V>
HashTable<K, V>::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;
??? }
}
template<typename K, typename V>
HashTable<K, V>::~HashTable()
{
??? MemFile::Release(m_MemAddr, m_MemSize);
}
template<typename K, typename V>
bool HashTable<K, V>::MoveToHead(K &key)
{
??? uint32_t nodeId = GetIdByKey(key);
??? uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;
??? return MoveNodeToHead(index, nodeId);
}
template<typename K, typename V>
uint32_t HashTable<K, V>::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;
}
template<typename K, typename V>
void HashTable<K, V>::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;
??? }
}
template<typename K, typename V>
bool HashTable<K, V>::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;
}
template<typename K, typename V>
bool HashTable<K, V>::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;
}
template<typename K, typename V>
uint32_t HashTable<K, V>::GetTailNodeId(uint32_t index)
{
??? if(index >= m_HeadAddr->m_TableLen) return m_InvalidId;
??? Array *tmpArray = m_ArrayAddr + index;
??? return tmpArray->m_Tail;
}
template<typename K, typename V>
uint32_t HashTable<K, V>::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;
}
?
轉(zhuǎn)載請(qǐng)注明本頁(yè)網(wǎng)址：
http://www.snjht.com/jiaocheng/3430.html
