400行代码实现本地Key-Value缓存 - mysql数据库栏目_MariaDB_青云站长教程网
欢迎来到站长教程网!
  • 秒到短信接口 免费试用
  • 微信支付宝接口 秒结算
  • 中文网站排名|申请加入
  • 搜索引擎全站查询
  • 查询移动网站权重数据
  • 海外主机 台湾公司直销
  • MariaDB

    当前位置:主页 > 数据库 > MariaDB >

    400行代码实现本地Key-Value缓存 - mysql数据库栏目

    时间:2019-08-12|栏目:MariaDB|点击:
  • 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<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; }

    上一篇:浅谈MySQL数据库性能优化 - mysql数据库栏目 - 自学

    栏    目:MariaDB

    下一篇:mysql实现两表关联更新 - mysql数据库栏目 - 自学

    本文标题:400行代码实现本地Key-Value缓存 - mysql数据库栏目

    本文地址:http://www.jh-floor.com/shujuku/Mariadb/19778.html

    广告投放 | 联系我们 | 版权申明

    重要申明:本站所有的文章、图片、评论等,均由网友发表或上传并维护或收集自网络,属个人行为,与本站立场无关。

    如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

    联系QQ:888888 | 邮箱:888888#qq.com(#换成@)

    Copyright © 2002-2017 青云站长教程网 版权所有 琼ICP备xxxxxxxx号