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

400行代码实现本地Key-Value缓存_MySQL

Jun 01, 2016 pm 01:26 PM

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

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

减少在Docker中使用MySQL内存的使用 减少在Docker中使用MySQL内存的使用 Mar 04, 2025 pm 03:52 PM

本文探讨了Docker中的优化MySQL内存使用量。 它讨论了监视技术(Docker统计,性能架构,外部工具)和配置策略。 其中包括Docker内存限制,交换和cgroups

mysql无法打开共享库怎么解决 mysql无法打开共享库怎么解决 Mar 04, 2025 pm 04:01 PM

本文介绍了MySQL的“无法打开共享库”错误。 该问题源于MySQL无法找到必要的共享库(.SO/.DLL文件)。解决方案涉及通过系统软件包M验证库安装

如何使用Alter Table语句在MySQL中更改表? 如何使用Alter Table语句在MySQL中更改表? Mar 19, 2025 pm 03:51 PM

本文讨论了使用MySQL的Alter Table语句修改表,包括添加/删除列,重命名表/列以及更改列数据类型。

在 Linux 中运行 MySQl(有/没有带有 phpmyadmin 的 podman 容器) 在 Linux 中运行 MySQl(有/没有带有 phpmyadmin 的 podman 容器) Mar 04, 2025 pm 03:54 PM

本文比较使用/不使用PhpMyAdmin的Podman容器直接在Linux上安装MySQL。 它详细介绍了每种方法的安装步骤,强调了Podman在孤立,可移植性和可重复性方面的优势,还

什么是 SQLite?全面概述 什么是 SQLite?全面概述 Mar 04, 2025 pm 03:55 PM

本文提供了SQLite的全面概述,SQLite是一个独立的,无服务器的关系数据库。 它详细介绍了SQLite的优势(简单,可移植性,易用性)和缺点(并发限制,可伸缩性挑战)。 c

在MacOS上运行多个MySQL版本:逐步指南 在MacOS上运行多个MySQL版本:逐步指南 Mar 04, 2025 pm 03:49 PM

本指南展示了使用自制在MacOS上安装和管理多个MySQL版本。 它强调使用自制装置隔离安装,以防止冲突。 本文详细详细介绍了安装,起始/停止服务和最佳PRA

如何为MySQL连接配置SSL/TLS加密? 如何为MySQL连接配置SSL/TLS加密? Mar 18, 2025 pm 12:01 PM

文章讨论了为MySQL配置SSL/TLS加密,包括证书生成和验证。主要问题是使用自签名证书的安全含义。[角色计数:159]

哪些流行的MySQL GUI工具(例如MySQL Workbench,PhpMyAdmin)是什么? 哪些流行的MySQL GUI工具(例如MySQL Workbench,PhpMyAdmin)是什么? Mar 21, 2025 pm 06:28 PM

文章讨论了流行的MySQL GUI工具,例如MySQL Workbench和PhpMyAdmin,比较了它们对初学者和高级用户的功能和适合性。[159个字符]

See all articles