mysql implements the local keyvalue database cache example
- 2020-06-07 05:24:16
- OfStack
There are many Key-ES2en caches, most of which are memcache and redis. They are all run as independent services. Sometimes in the work, a local ES5en-ES6en cache needs to be embedded.
This paper implements a super lightweight cache,
1. The implementation code only needs 400 lines;
2. High performance. When the length of value is 1K, the test speed is around 2 million per second
3. The cache is mapped to the file, so there is no overhead of malloc and free, as well as memory leakage and memory fragmentation.
4. If the service is suspended, the cache contents will continue to exist after restarting;
5, if the cache mapping to disk files even if the machine hangs, the contents of the cache will still exist, of course, there may be data corruption;
6, 1 to a certain extent to achieve LRU elimination algorithm, LRU is not global only on a chain, so can only be said to be implemented in a definite program;
7. Stable. It has been used in several projects.
8. Ordinary cache key and value are both in the form of strings, and key and value of this cache can be class and struct object structure, which is more convenient to use.
Old rules directly on the code:
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;
}