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

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