`
kakaluyi
  • 浏览: 444988 次
  • 性别: Icon_minigender_1
  • 来自: 苏州
社区版块
存档分类
最新评论

缓存服务器开发(1)---缓存服务器之数据结构LRUMap

阅读更多

   大家知道缓存服务器是怎么实现的吗,缓存服务器的数据结构是用LRUMap实现的,所谓LRUMap是每次put的时候,假如超过Map的长度,那么内部有一个算法实现移除最早放在里面的entry,这样就可以保证缓存是固定长度,而且每次更新总是把最老的缓存移除出去。为什么不用apchecommon提供的LRUMap呢,因为org.apache.commons.collections.map包中的LRUMap是非线程安全的,这个对缓存服务器的实现是不利的,所以需要concurrentmap来实现一些原子的同步功能.

下面看看LRUMap的代码实现:

 

感谢liuaike提供了代码,

 

public class LRUMap {

    /*
     *  最大空间
     */
    private int maxSize;

    /*
     *  缓存用到了ConcurrentHashMap这样可以避免自己去同步cache的put和delete     */
    private ConcurrentHashMap cache;

    /*
     *  这个数据结构就是缓存中entry的wraper类,因为他还要记录上一个元素和下一个元素
    *来区分到底他是否是该LRU中最老的那个元素       */
    private class Node {
        Node prev, next;
        Object key;
        Object item;
        int size;
    }

    /*
     *  最新元素和最老元素
     */
    private Node head, tail;

    public LRUMap(int maxSize) {
        this.maxSize = maxSize;
        clear();
    }

    public int getSize() {
        return cache.size();
    }

    /**
     *   
     *
     * @return
     *  得到缓存的大小
     */
    public int getMaxSize() {
        return maxSize;
    }
    
    /**
     * 用于遍历
     * @return
     */
    public Set keySet()
    {
    	return cache.keySet();
    }

    /**
     *   增加一个缓存entry,默认大小为1
     *   如果map满了的话,最老的那个缓存entry将会被删除
    *   本entry将会成为最年轻的entry,当前最后被删除       */ 
    public void put(Object key, Object item) {
        put(key, item , 1);
    }

    /**
     *   增加一个实体到缓存中
     *   假如缓存满了,将会从最老的缓存实体(或者最不经常用的)那个开始删除 
     *   这个新的实体将会成为最新的那个缓存 
     * 
     * @param key
     *   The key used to refer to the object when calling <CODE>get()</CODE>.
     * @param item
     *   The item to add to the cache.
     * @param size   */ 
    private void put(Object key, Object item, int size) {
        // 假如已经有这个key的缓存,删除原先的那个
        if (cache.containsKey(key))
            remove(key);
        // 从最老的entry开始删除,直到有空余空间位置
        while (cache.size() + size > maxSize) {
            if (!deleteLRU())
                break;
        }
        if (cache.size() + size > maxSize)
            // 如果此时正好被别的线程又保存新的entry进来,那么空间还是不够,那么就缓存失败
            return;
//创建一个新的实体保存到LRUMap中,并保存实体之间的联系为一个链表
        Node node = new Node();
        node.key = key; 
        node.item = item; 
        node.size = size;
        cache.put(key, node);
        insertNode(node);
    }


    /**
     *   从缓存中查找实体,返回null假如没有找到
     *   因为经常被查找的缓存要延迟被清空的时间,所以要把被查找的缓存从列表中删除更新为最新的entry
     * 
     * @param key
     *   The key used to refer to the object when <CODE>add()</CODE>
     *   was called.
     * @return
     *   The item, or null if not found.
     */
    public Object get(Object key) {
        Node node = (Node)cache.get(key);
        if (node == null)
            return null;
        deleteNode(node);
        insertNode(node); // 移动到链表的最前面(更新为最新的实体).
        return node.item;
    } 
  
   
    /**
     *   从缓存中删除      
     * @param key
     *   The key used to refer to the object when <CODE>add()</CODE>
     *   was called.
     * @return
     *   The item that was removed, or null if not found.
     */ 
    public Object remove(Object key) {
        Node node = (Node)cache.remove(key);
        if (node == null)
            return null;
        deleteNode(node);
        return node.item;
    }


    public boolean containsKey(Object key) {
        return cache.containsKey(key);
    }


    /**
     *   清空所有缓存,慎用
     */
    public void clear() {
        cache = new ConcurrentHashMap();
        head = tail = null;
    }


    /*
     *  把实体插入到链表的第一个位置
     *  
     */ 
    private void insertNode(Node node) {
        node.next = head;
        node.prev = null;
        if (head != null)
            head.prev = node;
        head = node;
        if (tail == null)
            tail = node;
    }


    /*
     *  从链表中删除这个实体
     *  This only does linked list management.
     */
    private void deleteNode(Node node) {
        if (node.prev != null)
            node.prev.next = node.next;
        else
            head = node.next;
        if (node.next != null)
            node.next.prev = node.prev;
        else
            tail = node.prev;
    } 

    
    /*
     *  删除列表最后一个缓存
     *  如果删除成功返回正确,如果缓存为空则返回失败 
     */
    private boolean deleteLRU() {
        if (tail == null)
            return false;
        cache.remove(tail.key);
        deleteNode(tail);
        return true;
    }

    /**
     *  得到这个缓存的描述字串,以key连接
     */
    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append("LRU ");
        buf.append("/");
        buf.append(maxSize);
        buf.append(" Order: ");
        Node n = head;
        while (n != null) {
            buf.append(n.key);
            if (n.next != null)
                buf.append(", ");
            n = n.next;
        }
        return buf.toString();
    }

 

分享到:
评论

相关推荐

    热-map是一个key-value的数据结构

    "热-Map"这个概念,从标题来看,似乎是指一个特定类型的key-value数据结构,可能与高性能计算或数据缓存相关,因为"热"通常用于描述高访问频率或活跃的数据。在传统的Map数据结构中,它允许我们通过键(key)来快速...

    redis-缓存文档

    缓存服务器通过存储频繁访问的内容,当再次请求相同内容时,可以直接从缓存服务器中读取,从而减少了延迟时间并减轻了源服务器的压力。 #### 二、Redis缓存特性与优势 - **读写速度快**:由于Redis将数据存储在...

    缓存组件的实现(go语言实现)

    但有时候,对于一些特定需求,我们可能需要设计一个与应用程序紧密集成的缓存系统,而不是依赖于一个独立的缓存服务器,这样可以减少系统的复杂度。 设计缓存系统时,需要考虑的关键特性包括: 1. 缓存数据的存储...

    缓存面试题大全 pdf版

    - **Redis**:目前最主流的分布式缓存方案之一,支持多种数据结构,如字符串、列表、哈希表等,并且提供了丰富的客户端库。 - **Memcached**:简单高效的键值存储系统,适用于需要快速存取数据的场景。 - **Tair*...

    分布式缓存.docx

    例如,SpringBoot中的简单MapCache实现就展示了如何通过这个数据结构实现存取删除操作,并通过定时任务检查并清理过期的缓存条目。 接着,我们来看看Ehcache。Ehcache是一个流行的Java缓存框架,它支持内存和磁盘...

    lru-cache:C ++中功能完整的LRU缓存实现

    在C++中实现LRU缓存,需要理解数据结构和算法的基础知识,特别是哈希表和双向链表的应用。 在C++中,LRU缓存通常通过结合哈希表(如`std::unordered_map`)和双向链表(如`std::list`或自定义实现)来实现。哈希表...

    android本地缓存

    在Android应用开发中,本地缓存是一种常见且重要的技术,用于存储用户数据或网络资源,以减少不必要的网络请求,提高用户体验。本篇文章将深入探讨如何在Android中实现本地缓存功能,满足以下需求: 1. 数据缓存:...

    Java缓存讨论.pdf

    Jofti为缓存层中的对象(支持EHCache、JBossCache和OSCache)以及实现了Map接口的存储结构中的对象提供索引和搜索功能。它提供了透明的索引管理及易于使用的查询接口。 最后,cache4j提供了一个简单API的快速Java...

    redis缓存demo

    Redis支持的数据类型包括字符串(Strings)、哈希(Hashes)、列表(Lists)、集合(Sets)和有序集合(Sorted Sets)等,这些丰富的数据结构使得Redis在多种场景下都能发挥作用。 1. 字符串(Strings):最基础的数据类型,...

    ehcache 2 8 包括文档

    - **LRU(Least Recently Used)**:最常用的淘汰策略,最近最少使用的条目会被移出缓存。 - **LFU(Least Frequently Used)**:最少使用的条目优先被淘汰。 - **定时过期**:设置每个缓存项的生存时间,到达...

    LRU算法 C++实现

    LRU算法的实现通常依赖于数据结构,如哈希表和双向链表。在C++中,我们可以使用`std::unordered_map`来存储页面及其访问时间,同时使用`std::list`来维护页面的顺序。以下是一个简单的C++实现概述: ```cpp #...

    ehcache 缓存

    1. **Terracotta服务器**: Ehcache通过集成Terracotta服务器,可以实现跨JVM的分布式缓存,提高多节点间的缓存共享和一致性。 2. **复制策略**: 分布式缓存中,当在一个节点上添加、更新或移除元素时,这些操作可以...

    论文研究-LDAP数据访问优化的研究 .pdf

    内存缓存结构通常基于hash的Map数据结构,以key-value对的形式存储数据。通过key,可以迅速定位并访问到缓存中的对象。MemoryStore接口的定义则为内存缓存提供了必要的方法实现,增强了系统的灵活性和可修改性。 ...

    Java实现LRU算法.zip

    在实际应用中,LRU算法不仅可以用于操作系统中的页面替换,还可以应用于数据库查询缓存、编程语言的内存管理(如Java的SoftReference和WeakReference)以及Web服务器的静态资源缓存等场景。 总的来说,Java实现LRU...

    一步步构建大型网站架构

    - 缓存数据结构的选择,如Map等。 - 缓存算法的研究,比如LRU(Least Recently Used)算法。 - 分布式缓存框架的使用,如Redis或Memcached。 #### 架构演变第五步:增加WebServer 当单台WebServer无法应对高峰...

    nodejs cache

    3. **用户自定义缓存**:开发者可以根据需求自行实现缓存策略,比如使用 Map 或者 LRU(Least Recently Used)数据结构来存储和管理数据。这在处理大量数据或者频繁读取的情况时非常有用。 4. **第三方库**:在描述...

    LRU页面置换算法(Java)

    在Java中实现LRU页面置换算法,通常会用到数据结构如HashMap或LinkedHashMap,因为它们能够提供快速的查找和按照访问顺序排序的功能。HashMap提供了O(1)的时间复杂度进行查找,而LinkedHashMap则在HashMap的基础上...

    my-distributed-cache.7z

    在Go中,可以通过数据结构和算法实现这些策略。 4. **分布式锁**:在多节点环境中,确保同一数据在同一时刻只有一个节点进行操作,防止数据不一致。Go的sync包提供了Mutex和RWMutex等互斥锁机制。 5. **网络通信**...

Global site tag (gtag.js) - Google Analytics