搜索
首页数据库mysql教程400行代码实现本地Key-Value缓存_MySQL

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

 

bitsCN.com
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
与其他RDBM相比,MySQL如何处理并发?与其他RDBM相比,MySQL如何处理并发?Apr 29, 2025 am 12:44 AM

MySQLhandlesconcurrencyusingamixofrow-levelandtable-levellocking,primarilythroughInnoDB'srow-levellocking.ComparedtootherRDBMS,MySQL'sapproachisefficientformanyusecasesbutmayfacechallengeswithdeadlocksandlacksadvancedfeatureslikePostgreSQL'sSerializa

MySQL与其他关系数据库相比如何处理交易?MySQL与其他关系数据库相比如何处理交易?Apr 29, 2025 am 12:37 AM

mysqlHandLestActionSefectefectionalytheinnodbengine,supportingAcidPropertiessimilartopostgresqlesqlandoracle.1)mySqluessRepeTableReadAbleDasthEdefaultIsolationLelealevel,该canbeadjustEdToreDtoreDtoreadCommententCommententCommententCommententCommittedForHigh-TrafficsCenarios.2)

MySQL中有哪些数据类型?MySQL中有哪些数据类型?Apr 29, 2025 am 12:28 AM

MySQL的数据类型分为数值、日期和时间、字符串、二进制和空间类型。选择正确的类型可以优化数据库性能和数据存储。

在MySQL中编写有效的SQL查询的最佳实践是什么?在MySQL中编写有效的SQL查询的最佳实践是什么?Apr 29, 2025 am 12:24 AM

最佳实践包括:1)理解数据结构和MySQL处理方式,2)适当索引,3)避免SELECT*,4)使用合适的JOIN类型,5)谨慎使用子查询,6)使用EXPLAIN分析查询,7)考虑查询对服务器资源的影响,8)定期维护数据库。这些做法能使MySQL查询不仅快速,还具备可维护性、可扩展性和资源效率。

MySQL与PostgreSQL有何不同?MySQL与PostgreSQL有何不同?Apr 29, 2025 am 12:23 AM

MySQLisbetterforspeedandsimplicity,suitableforwebapplications;PostgreSQLexcelsincomplexdatascenarioswithrobustfeatures.MySQLisidealforquickprojectsandread-heavytasks,whilePostgreSQLispreferredforapplicationsrequiringstrictdataintegrityandadvancedSQLf

MySQL如何处理数据复制?MySQL如何处理数据复制?Apr 28, 2025 am 12:25 AM

MySQL通过异步、半同步和组复制三种模式处理数据复制。1)异步复制性能高但可能丢失数据。2)半同步复制提高数据安全性但增加延迟。3)组复制支持多主复制和故障转移,适用于高可用性需求。

您如何使用解释性语句分析查询性能?您如何使用解释性语句分析查询性能?Apr 28, 2025 am 12:24 AM

EXPLAIN语句可用于分析和提升SQL查询性能。1.执行EXPLAIN语句查看查询计划。2.分析输出结果,关注访问类型、索引使用情况和JOIN顺序。3.根据分析结果,创建或调整索引,优化JOIN操作,避免全表扫描,以提升查询效率。

您如何备份并还原MySQL数据库?您如何备份并还原MySQL数据库?Apr 28, 2025 am 12:23 AM

使用mysqldump进行逻辑备份和MySQLEnterpriseBackup进行热备份是备份MySQL数据库的有效方法。1.使用mysqldump备份数据库:mysqldump-uroot-pmydatabase>mydatabase_backup.sql。2.使用MySQLEnterpriseBackup进行热备份:mysqlbackup--user=root--password=password--backup-dir=/path/to/backupbackup。恢复时,使用相应的命

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器