간단 한 자바 캐 시 구현

캐 시 를 언급 할 때 캐 시 알고리즘 (도태 알고리즘) 을 언급 하지 않 을 수 없다. 흔히 볼 수 있 는 알고리즘 은 LRU, LFU 와 FIFO 등 알고리즘 이 있 고 각 알고리즘 은 각각 장점 과 단점 과 적응 환경 이 있다.
1. LRU (Least Recently Used, 최근 최소 사용) 알고리즘 은 데이터 의 최근 방문 기록 에 따라 데 이 터 를 도태 시 킵 니 다. 만약 에 데이터 가 최근 에 방문 한 적 이 있 으 면 앞으로 방문 할 확률 이 상대 적 으로 높 습 니 다. 가장 흔히 볼 수 있 는 실현 은 하나의 링크 를 사용 하여 캐 시 수 거 리 를 저장 하 는 것 입 니 다. 상세 한 구체 적 인 알고리즘 은 다음 과 같 습 니 다. 1. 새로운 데 이 터 를 링크 머리 에 삽입 하 는 것 입 니 다.2. 캐 시 데이터 가 명중 할 때마다 데 이 터 를 링크 머리 로 이동 합 니 다.3. 링크 가 가득 찼 을 때 링크 끝의 데 이 터 를 버 립 니 다.2. LFU (Least Frequently Used, 가장 자주 사용 하지 않 음) 알고리즘 은 데이터 의 역사적 방문 빈도 에 따라 데 이 터 를 도태 시 키 는데 그 원 리 는 데이터 가 과거 에 방문 횟수 가 많 을 수록 앞으로 방문 할 확률 이 상대 적 으로 높다 는 것 이다.LFU 의 모든 데이터 블록 은 인용 계수 가 있 고 모든 데이터 블록 은 인용 계수 에 따라 정렬 되 며 같은 인용 계수 가 있 는 데이터 블록 은 시간 에 따라 정렬 됩 니 다.구체 적 인 알고리즘 은 다음 과 같다. 1. 데 이 터 를 대기 열 끝 에 새로 삽입 합 니 다 (인용 계수 가 1 이기 때 문).2. 대기 열 에 있 는 데이터 가 접근 한 후 인용 계수 가 증가 하고 대기 열 을 다시 정렬 합 니 다.3. 데 이 터 를 도태 시 키 려 면 정렬 된 목록 의 마지막 데이터 블록 을 삭제 합 니 다.3. FIFO (First In First Out, 선진 선 출) 알고리즘 은 선진 선 출 원리 에 따라 데 이 터 를 도태 시 키 는 것 으로 실현 에 있어 가장 간단 한 것 입 니 다. 구체 적 인 알고리즘 은 다음 과 같 습 니 다. 1. 새로 방문 한 데 이 터 는 FIFO 대기 열 끝 에 삽입 되 고 데 이 터 는 FIFO 대기 열 에서 순서대로 이동 합 니 다.2. FIFO 대기 열의 머리 에 있 는 데 이 터 를 삭제 합 니 다.캐 시 알고리즘 의 좋 고 나 쁨 을 평가 하 는 기준 은 주로 두 가지 가 있 는데 하 나 는 명중률 이 높 아야 하고, 다른 하 나 는 알고리즘 이 쉽게 이 루어 져 야 한다.핫 이 슈 데이터 가 존재 할 때 LRU 의 효율 성 은 좋 지만 우발 적 이 고 주기 적 인 대량 작업 은 LRU 명중률 을 급 격 히 떨 어 뜨리 고 캐 시 오염 상황 이 심각 하 다.LFU 는 LRU 보다 효율 적 이 고 주기 적 이거 나 우발 적 인 조작 으로 캐 시 명중률 이 떨 어 지 는 문 제 를 피 할 수 있다.그러나 LFU 는 데이터 의 과거 기록 을 기록 해 야 한다. 데이터 액세스 모드 가 바 뀌 면 LFU 는 미래 데이터 에 영향 을 미 칠 과거 기록 데이터 의 '캐 시 오염' 효용 을 적용 하 는 데 더 많은 시간 이 필요 하 다.FIFO 는 실현 은 간단 하지만 명중률 이 낮 아 실제로 도 이런 알고리즘 을 거의 사용 하지 않 는 다.
기 존의 jdk 라 이브 러 리 를 기반 으로 위의 캐 시 알고리즘 을 쉽게 실현 할 수 있 습 니 다.
우선 캐 시 인터페이스 클래스 정의
/**
 *     
 * @author Wen
 *
 */
public interface Cache<K,V> {
	/**
	 *          
	 * 
	 * @return  
	 */
	int size();
	
	/**
	 *         
	 * 
	 * @return
	 */
	long getDefaultExpire();
	
	/**
	 *      value  ,             
	 * 
	 * @param key
	 * @param value
	 */
	void put(K key ,V value) ;
	
	/**
	 *      value  ,       
	 * @param key
	 * @param value
	 * @param expire      
	 */
	void put(K key ,V value , long expire ) ;
	
	/**
	 *       
	 * @param key
	 * @return
	 */
	V get(K key);
	
	/**
	 *     
	 * 
	 * @return         
	 */
	int eliminate();
	
	/**
	 *        
	 * @return
	 */
	boolean isFull();

	/**
	 *       
	 * 
	 * @param key
	 */
	void remove(K key);

	/**
	 *         
	 */
	void clear();

	/**
	 *       
	 * 
	 * @return  
	 */
	int getCacheSize();

	/**
	 *        
	 */
	boolean isEmpty();

}

기본 실현 추상 류
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 *     
 */
public abstract class AbstractCacheMap<K,V> implements Cache<K,V> {

	class CacheObject<K2,V2> {
		CacheObject(K2 key, V2 value, long ttl) {
			this.key = key;
			this.cachedObject = value;
			this.ttl = ttl;
			this.lastAccess = System.currentTimeMillis();
		}

		final K2 key;
		final V2 cachedObject;
		long lastAccess;		//       
		long accessCount;		//     
		long ttl;				//       (time-to-live)

		boolean isExpired() {
			if (ttl == 0) {
				return false;
			}
			return lastAccess + ttl < System.currentTimeMillis();
		}
		V2 getObject() {
			lastAccess = System.currentTimeMillis();
			accessCount++;
			return cachedObject;
		}
    }

	protected Map<K,CacheObject<K,V>> cacheMap;

	private final ReentrantReadWriteLock cacheLock = new ReentrantReadWriteLock();
	private final Lock readLock = cacheLock.readLock();
	private final Lock writeLock = cacheLock.writeLock();



	protected int cacheSize;      //      , 0 ->    
	
	protected  boolean existCustomExpire ; //          
	
	public int getCacheSize() {
		return cacheSize;
	}

	protected long defaultExpire;     //       , 0 ->     
	
	public AbstractCacheMap(int cacheSize ,long defaultExpire){
		this.cacheSize  = cacheSize ;
		this.defaultExpire  = defaultExpire ;
	}

	
	public long getDefaultExpire() {
		return defaultExpire;
	}


	protected boolean isNeedClearExpiredObject(){
		return defaultExpire > 0 || existCustomExpire ;
	}

	
	public void put(K key, V value) {
		put(key, value, defaultExpire );
	}


	public void put(K key, V value, long expire) {
		writeLock.lock();

		try {
			CacheObject<K,V> co = new CacheObject<K,V>(key, value, expire);
			if (expire != 0) {
				existCustomExpire = true;
			}
			if (isFull()) {
				eliminate() ;
			}
			cacheMap.put(key, co);
		}
		finally {
			writeLock.unlock();
		}
	}



	/**
	 * {@inheritDoc}
	 */
	public V get(K key) {
		readLock.lock();

		try {
			CacheObject<K,V> co = cacheMap.get(key);
			if (co == null) {
				return null;
			}
			if (co.isExpired() == true) {
				cacheMap.remove(key);
				return null;
			}

			return co.getObject();
		}
		finally {
			readLock.unlock();
		}
	}
	
	public final int eliminate() {
		writeLock.lock();
		try {
			return eliminateCache();
		}
		finally {
			writeLock.unlock();
		}
	}
	
	/**
	 *         
	 * 
	 * @return
	 */
	protected abstract int eliminateCache(); 


	
	public boolean isFull() {
		if (cacheSize == 0) {//o ->    
			return false;
		}
		return cacheMap.size() >= cacheSize;
	}

	
	public void remove(K key) {
		writeLock.lock();
		try {
			cacheMap.remove(key);
		}
		finally {
			writeLock.unlock();
		}
	}

	
	public void clear() {
		writeLock.lock();
		try {
			cacheMap.clear();
		}
		finally {
			writeLock.unlock();
		}
	}

	public int size() {
		return cacheMap.size();
	}

	
	public boolean isEmpty() {
		return size() == 0;
	}
}

LRU 캐 시 구현 클래스
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * LRU    
 * @author Wen
 *
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> extends AbstractCacheMap<K, V> {

	public LRUCache(int cacheSize, long defaultExpire) {
		
		super(cacheSize , defaultExpire) ;

		//linkedHash    LRU             ,        ,                   ,             ,    ,               ,     ,                  
		this.cacheMap = new LinkedHashMap<K, CacheObject<K, V>>( cacheSize +1 , 1f,true ) {

			@Override
			protected boolean removeEldestEntry(
					Map.Entry<K, CacheObject<K, V>> eldest) {

				return LRUCache.this.removeEldestEntry(eldest);
			}

		};
	}

	private boolean removeEldestEntry(Map.Entry<K, CacheObject<K, V>> eldest) {

		if (cacheSize == 0)
			return false;

		return size() > cacheSize;
	}

	/**
	 *                ,linkedHashMap    LRU
	 */
	@Override
	protected int eliminateCache() {

		if(!isNeedClearExpiredObject()){ return 0 ;}
		
		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		int count  = 0 ;
		while(iterator.hasNext()){
			CacheObject<K, V> cacheObject = iterator.next();
			
			if(cacheObject.isExpired() ){
				iterator.remove(); 
				count++ ;
			}
		}
		
		return count;
	}

}

LFU 구현 클래스
import java.util.HashMap;
import java.util.Iterator;

//LFU  
public class LFUCache<K,V> extends AbstractCacheMap<K, V> {
	

	public LFUCache(int cacheSize, long defaultExpire) {
		super(cacheSize, defaultExpire);
		cacheMap = new HashMap<K, CacheObject<K,V>>(cacheSize+1) ;
	}

	/**
	 *                        
	 * 
	 */
	@Override
	protected int eliminateCache() {
		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		int count  = 0 ;
		long minAccessCount = Long.MAX_VALUE  ;
		while(iterator.hasNext()){
			CacheObject<K, V> cacheObject = iterator.next();
			
			if(cacheObject.isExpired() ){
				iterator.remove(); 
				count++ ;
				continue ;
			}else{
				minAccessCount  = Math.min(cacheObject.accessCount , minAccessCount)  ;
			}
		}
		
		if(count > 0 ) return count ;
		
		if(minAccessCount != Long.MAX_VALUE ){
			
			iterator = cacheMap.values().iterator();
			
			while(iterator.hasNext()){
				CacheObject<K, V> cacheObject = iterator.next();
				
				cacheObject.accessCount  -=  minAccessCount ;
				
				if(cacheObject.accessCount <= 0 ){
					iterator.remove();
					count++ ;
				}
				
			}
			
		}
		
		return count;
	}

}

FIFO 실현 클래스
import java.util.Iterator;
import java.util.LinkedHashMap;
/**
 * FIFO  
 * @author Wen
 *
 * @param <K>
 * @param <V>
 */
public class FIFOCache<K, V> extends AbstractCacheMap<K, V> {

	public FIFOCache(int cacheSize, long defaultExpire) {
		super(cacheSize, defaultExpire);
		cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1);
	}

	@Override
	protected int eliminateCache() {

		int count = 0;
		K firstKey = null;

		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		while (iterator.hasNext()) {
			CacheObject<K, V> cacheObject = iterator.next();

			if (cacheObject.isExpired()) {
				iterator.remove();
				count++;
			} else {
				if (firstKey == null)
					firstKey = cacheObject.key;
			}
		}

		if (firstKey != null && isFull()) {//         ,         
			cacheMap.remove(firstKey);
		}

		return count;
	}

}

좋은 웹페이지 즐겨찾기