XML | HTML | TXT
您当前位置:软件开发 >> 新闻动态 >> 软件开发行业资讯 >> 浏览文章

C++实现最基本的LRUCache服务器缓存

  后台开发必备知识,不过我不是搞这个的,只是因为很久以前就想写这些东西,事情多,拖到现在。写的过程里面发现很多问题,不会全部说,最后会顺带提一提。

  注意,本篇笔记只是对接口写法做了记录,并没有进行更严格的设计和限制,包括更严密的封装,这里只是学习它实现的原理。

  不过有些idea还是要知道的,系统定时对缓存进行清除并加入满足条件的新数据,是根据:访问时间,访问次数,可用缓存容量(分配到的内存)等因素决定的,实际设计其实很多东西需要考虑。

  一、介绍:

  LRU,Least Recently Used,最近最少使用,服务器缓存常用算法的一种。

  比如说一些系统登录的操作,不可能每次你访问系统都去调用数据库的东西,如果能划出一些空间来,比如说500M,用来缓存这些东西,这样用户访问的时候先在缓存里找,找不到,再去访问数据库,同时把被访问的内容放到缓存里面(我们可以假设这些东西还会经常被访问)。然而,我们分配用来做缓存(Cache)的空间肯定是有限的,总不可能从数据库读的东西全部放到缓存里,所以,当缓存里的内容达到上限值的时候,我们就要把最少使用的东西写回数据库,再将新的访问内容从数据库暂存到缓存里面。

  二、数据结构:

  最常用的数据结构实现方式是hash_map和Double-Linked List,hash_map只是为了实现键值key-value对应,这样就避免了每次寻找特定值都要在双线链表里面顺序查找,服务器是没办法负担这种低效率的查找方法的。

  我们可以为链表节点写一个结构体,用来定义节点的类型;然后专门写一个类用来组织缓存信息的存放——以双链表的形式。

  复制代码

  template<class K, class T>

  struct Node

  {

  K key;

  T data;

  Node *next;

  Node *prev;

  };

  复制代码

  复制代码

  template<class K,class T>

  class LRUCache

  {

  public:

  LRUCache(size_t size);         //typedef unsigned int size_t

  ~LRUCache();

  void Put(K key,T data);

  T Get(K key);

  private:

  void Attach(Node<K,T>* node);

  void Detach(Node<K,T>* node);

  private:

  hash_map<K,Node<K,T>*> hashmap;

  vector<Node<K,T>*> linkedList;

  Node<K,T>* head;

  Node<K,T>* tail;

  Node<K,T>* entries;          //temp nodes

  };

  复制代码

  看代码太枯燥,我画了个UML图:

  三、主要的两个函数接口Put()和Get():

  最基本的,不是存,就是取。那修改呢?合并到存里面去了,通过键值key查找一个hash_map对应的value,如果value不是NULL,那么更新value的内容即可。其实服务器缓存比较多作的是读多写少的东西。

  因为代码实在是太枯燥了,所以针对Put函数和Get函数画了两张流程图:

  其中,Detach(node)表示将这个节点从双链表中解出,成为一个独立的节点;Attach(node)表示将node插入到头节点head后面(表示它可能再次被用到),这样的话,如果自己再设计一个GetFirst()函数,就能直接获取上次的访问结果,这种访问连hash_map都不需要用到。

  流程讲解:

  在上述Put函数流程图中,注意第一个判断“node==NULL”,这个node地址是通过hashmap映射而来的:1、如果不是NULL,说明这个节点已经存在,那么将该节点的数据data重写以后加到链表头;

  2、如果是NULL,还要进行第二个判断“分配地址的linkedList是不是已经空了”:

  2.1、如果空了,说明全部可用地址已经分配完了,那么,将原链表的最后一个节点踢出链表(应写入数据库),然后将被踢出点的hashmap中对应的key-value擦除,然后再加入新节点,并在hashmap中对应好新节点的key-value;

  2.2、如果不空,那么从linkedList中分配个新地址给这个节点,同时linkedList要弹出分配完的地址,然后再将新节点加入链表中,对应好hashmap中的key-value。

  要注意,hashmap用来对应key-value,这里是方便查找;而vector变量linkedList也只是在初始化的时候存储了一块连续地址,用来分配地址,它们两者都不是用来直接构建链表的,链表是你自己建立的。

  Get()函数就比较简单了:

  四、C++代码实现:

  代码不是我原创的(后面给出原文地址),不过理清思路之后我自己实现了一遍,测试的过程实在是各种奇葩和辛苦(因为一个不注意的小地方)。

  代码实现里用到了hash_map,注意,这个不是C++标准的一部分,所以你要自己去库文件里找找,一般来说库文件都是在/usr/include下面的了,cd到这个文件夹,然后用grep找一下:

  cd /usr/include

  grep  -R "hash_map"

  最后你会发现是这个头文件:<ext/hash_map>,用文本文档打开来看一下,因为是限制了命名空间的,会发现有两个可用的命名空间,其中一个是__gnu_cxx。

  代码我一开始是用Qt写的,不过后来发现Qt没法调试(后面再说),于是最后使用Eclipse完成了调试和测试,下面先给出代码:

  LRUCache

  调试的时候我发现了一个问题:

  坑爹了,全部节点的next指针全部都指向自己,这样的话链表长得像什么样子呢?应该是这样:

  这个错误到底是怎么来的?

  我反复地看代码,节点的链入(Attach)和取出(Detach)都是没有问题的,而且,插入新节点的时候,已经插入过的节点为什么没有了?Attach方法既然是正确的,那为什么节点的next为什么会指向自己?

  综合上面两个问题,我突然意识到:那只能是分配地址的时候出现问题了!

  所以回到构造函数分配地址的部分,我发现在for循环里面,本应是:

  linkedList.push_back(entries+i);

  这样就能顺序存储分配好的地址。

  但我竟然把i写成了1,所以每个地址都成了同一个!吐血的经历。


手机:18678812288 E-Mail:1069706080@qq.com
地址:山东省济南市舜耕路泉城公园东门园内向北50米 鲁ICP备07011972号 版权所有2008-2013 山东赢德信息科技有限公司