동시 LRU 캐시 구현

Question

스레드 안전하고 효율적인 LRU 캐시 구현 코드가 필요합니다. 아래 코드 은 스레드로부터 안전하지 않습니다. 이 코드는 ConcurrentHashMap을 사용하여 향상시킬 수 있습니까? 미리 감사드립니다.

private class LruCache<A, B> extends LinkedHashMap<A, B> { 
    private final int maxEntries; 

    public LruCache(final int maxEntries) { 
     super(maxEntries + 1, 1.0f, true); 
     this.maxEntries = maxEntries; 
    } 

    @Override 
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) { 
     return super.size() > maxEntries; 
    } 
} 

Answer 1

당신이 할 수있는 최선은 스레드 안전 확인하는 것입니다은 javadoc에 설명 Collections.synchronizedMap(map) 함께 래핑하는 것입니다 :이 구현은를 동기화되지

하는 것으로. 복수 스레드 이 링크 된 해시 맵에 동시에 액세스하고 적어도 하나의 스레드 이 맵을 구조적으로 수정하면 외부에서 동기화되어야합니다. 이것은 보통 이 맵을 자연스럽게 캡슐화하는 일부 오브젝트에서 동기화하여 수행됩니다. 그러한 객체가 존재하지 않는 경우, Collections.synchronizedMap 메소드를 사용하여 맵을 "랩핑"해야합니다. 이 맵에의 우발적 인 비동기 액세스를 막기 위해서 (때문에), 작성시에 실시하는 것이 최적입니다

이 충분하지 않습니다 그러나

Map m = Collections.synchronizedMap(new LinkedHashMap(...)); 

은 스레드에 안전하게 할 내용을 통해 모든 반복을 보호하기 위해 문턱 필요 객체의 모니터로 포장 맵의 인스턴스를 사용하여지도의 :

Map m = Collections.synchronizedMap(map); 
... 
Set s = m.keySet(); // Needn't be in synchronized block 
... 
synchronized (m) { // Synchronizing on m, not s! 
    Iterator i = s.iterator(); // Must be in synchronized block 
    while (i.hasNext()) 
     foo(i.next()); 
} 

---

이는 거의 모두 수행 할 수 있습니다 쉽게은 JDK 상자에있는 것을 그대로 사용하고 스레드 안전성과 효율성을 높이려면 Cache을 Google Guava에서 찾아야합니다. 여기

는 guava 빌드 2의 최대 크기와 LRU 캐시의 예이다 :

ConcurrentMap<String, String> cache = 
    CacheBuilder.newBuilder() 
     .maximumSize(2L) 
     .<String, String>build().asMap(); 
cache.put("a", "b"); 
cache.put("b", "c"); 
System.out.println(cache); 
cache.put("a", "d"); 
System.out.println(cache); 
cache.put("c", "d"); 
System.out.println(cache); 

출력 : 래퍼 Collections.synchronozedMap()를 사용하는 것에 비해

{b=c, a=b} 
{b=c, a=d} 
{c=d, a=d} 

Answer 2

, I ConcurrentHashMap과 ConcurrentLinkedList을 함께 사용하고 012를 구현하는 것이 더 바람직하다고 생각합니다.인터페이스가 필요하며 가능하면 List 인터페이스가 필요합니다. 그러나 동시성이 유지되도록 내부 맵과 목록의 작업 사이에 사용자 지정 논리가 필요합니다. 그래도 성능은 완전히 synchronized지도보다 좋을 수 있습니다.

Answer 3

발견 구아바의 Cache. 나 혼자 사용하지 않았어.

캐시는 ConcurrentMap과 유사하지만 완전히 동일하지는 않습니다.

출처 : https://github.com/google/guava/wiki/CachesExplained

예 :

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder() 
     .expireAfterAccess(10, TimeUnit.MINUTES) 
     .maximumSize(1000) 
     .build(
      new CacheLoader<Key, Graph>() { 
      public Graph load(Key key) { // no checked exception 
       return createExpensiveGraph(key); 
      } 
      }); 

... 
return graphs.getUnchecked(key);