欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

mysql实现本地keyvalue数据库缓存示例_MySQL

程序员文章站 2022-06-12 16:16:55
...
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对象结构使用更方便;

老规矩直接上代码:


template
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_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);
};

template
HashTable::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 {
(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
HashTable::~HashTable()
{
MemFile::Release(m_MemAddr, m_MemSize);
}

template
bool HashTable::MoveToHead(K &key)
{
uint32_t nodeId = GetIdByKey(key);
uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;

return MoveNodeToHead(index, nodeId);
}

template
uint32_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;
}

template
void 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;
}
}

template
bool 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;
}

template
bool 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;
}

template
uint32_t HashTable::GetTailNodeId(uint32_t index)
{
if(index >= m_HeadAddr->m_TableLen) return m_InvalidId;

Array *tmpArray = m_ArrayAddr + index;

return tmpArray->m_Tail;
}

template
uint32_t HashTable::GetFreeNode()
{
uint32_t nodeId = m_InvalidId;
if(m_HeadAddr->m_UsedCount 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_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_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
相关标签: 数据库 mysql