LinkedHashMap은 Java 1.4에서 도입된 하이브리드 데이터 구조로, HashMap의 O(1) 평균 조회와 이중 연결 리스트를 결합하여 결정적인 반복 순서, 즉 삽입 순서 또는 접근 순서를 제공합니다. 이 디자인은 removeEldestEntry 템플릿 메서드를 도입하여 서브클래스가 원하는 크기를 초과할 때 true를 반환함으로써 LRU(Least Recently Used) 퇴출 정책을 구현할 수 있도록 합니다. 그러나 구현은 동시 사용을 위한 것이 아니며, HashMap의 비 스레드 안전한 특성을 상속받고 모든 항목을 가로지르는 양방향 before 및 after 포인터를 유지하는 복잡성을 추가합니다.
동시 구조 수정 중—예를 들어, 한 스레드가 삽입하는 동안 다른 스레드가 삭제하거나 크기를 조정하는 경우—연결 리스트 포인터는 원자적으로 업데이트되지 않을 수 있으며, 이는 항목들이 순환 참조를 형성하거나 주 체인에서 고아가 되는 손상된 그래프 구조로 이어질 수 있습니다. 예를 들어, 스레드 A가 항목의 after 포인터를 항목 B를 가리키도록 업데이트하는 동안, 스레드 B가 병행하여 항목 B를 제거하고 before 포인터를 업데이트하면, 리스트는 A가 B를 가리키고 B가 C를 가리키는 상태가 되어 A를 건너뛰거나 사이클을 생성할 수 있습니다. 이러한 손상으로 인해 이터레이터는 무한 루프에 빠져(100% CPU를 소모)거나 유효한 항목을 조용히 건너뛰게 되어, removeEldestEntry 정책이 신뢰할 수 없게 됩니다. 왜냐하면 "가장 오래된" 포인터가 더 이상 리스트의 실제 헤드를 반영하지 않기 때문입니다.
멀티 스레드 환경에서 LinkedHashMap을 안전하게 사용하려면 모든 작업을 외부에서 동기화해야 합니다. accessOrder=true 캐시의 경우, get() 또한 구조적 수정으로 간주됩니다(이는 연결 리스트의 순서를 재정렬하기 때문) 그래서 표준 ReadWriteLock 최적화는 무효입니다; 모든 작업을 쓰기로 취급해야 하거나 전역 뮤텍스를 사용해야 합니다. 가장 안전한 접근 방식은 Collections.synchronizedMap이지만, 이터레이션 중에 맵에 대해 수동으로 동기화해야 합니다. 그러나 프로덕션 시스템에서는 LinkedHashMap을 Caffeine 또는 Guava의 CacheBuilder로 대체해야 하며, 이들은 전역 경쟁 없이 락 스트라이프 알고리즘이나 전적으로 동시적인 퇴출 알고리즘을 제공합니다.
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMap은 스레드 안전하지 않으며, 외부에서 동기화해야 함 this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // 모든 메서드는 맵에 대해 동기화해야 함 public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // 반복은 명시적인 동기화를 요구함 public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
전자상거래 플랫폼의 백엔드 서비스는 데이터베이스 부하를 줄이기 위해 제품 가격 데이터를 위한 인 메모리 캐시가 필요했습니다. 초기 구현은 accessOrder=true를 가진 LinkedHashMap을 사용하며 removeEldestEntry를 재정의하여 1,000 항목 한도를 적용했으며, 맵이 자동으로 오래된 항목을 제거할 것이라고 가정했습니다. 낮은 부하 테스트 중에는 이 기능이 정확히 작동했지만, 프로덕션 트래픽 아래에서 40개의 동시 스레드가 플래시 세일을 처리하면서 서비스는 간헐적인 CPU 스파이크를 100% 경험하고 결국 스레드 기아에 시달렸습니다.
스레드 덤프는 여러 스레드가 LinkedHashMap 이터레이터 안에서 순환 참조를 탐색하고 있는 것을 보여주었습니다. 특히 한 스레드가 내부 테이블을 조정하는 동안 다른 스레드가 항목의 접근 순서를 업데이트하여 Entry 노드의 after 포인터가 자신을 참조하게 되어 반복 중 무한 루프가 발생했습니다. 또한, removeEldestEntry 콜백이 때때로 잘못된 항목을 제거했습니다. 왜냐하면 "가장 오래된" 포인터가 동시 재정렬로 인해 손상되었기 때문에 최근에 접근한 항목이 아니라 오래된 항목이 퇴출되었습니다.
팀은 처음에 맵을 Collections.synchronizedMap으로 래핑하는 것을 고려했습니다. 장점: 최소한의 코드 변경으로 개별 작업의 원자성을 보장합니다. 단점: 전역 모니터를 도입하여 모든 읽기 및 쓰기를 직렬화하므로 예상된 초당 20,000 작업의 처리량이 경쟁 아래 3,000 미만으로 줄어들었습니다. 게다가 이터레이터는 여전히 명시적인 synchronized(map) 블록을 요구하므로 개발자들이 가끔 잊어버려 ConcurrentModificationException이 발생했습니다.
그 다음 ConcurrentHashMap과 ConcurrentLinkedQueue를 사용하여 최근성을 추적하고 백그라운드 정리 스레드를 사용하는 방안을 평가했습니다. 장점: 읽기 및 쓰기에 대한 높은 동시성을 제공합니다. 단점: LRU를 올바르게 구현하는 것은 오류가 발생하기 쉽습니다. 가장 오래된 항목을 제거하는 것은 삽입과 원자적이지 않으므로 캐시가 높은 부하 하에서 일시적으로 크기 제한을 초과할 수 있습니다. 또한 get()마다 큐를 업데이트하면 쓰기 작업이 필요하므로 유사한 경쟁 포인트와 큐와 맵 간의 일관성을 유지하는 복잡성이 발생합니다.
마지막으로, 팀은 Caffeine, 고성능 캐싱 라이브러리를 벤치마킹했습니다. 장점: 락 스트라이핑과 퇴출을 위한 쓰기 버퍼를 가진 BoundedLocalCache를 사용하여 잠금 없이 동시 읽기를 가능하게 하고 높은 처리량의 쓰기를 지원합니다. 이는 명시적 동기화 없이 LRU/W-TinyLFU 퇴출을 원자적으로 처리합니다. 단점: 외부 의존성을 추가하며 새로운 API(예: CacheLoader)를 배워야 합니다.
부하 테스트에서 Caffeine이 80,000 이상 작업을 지속하고 p99 대기 시간이 1ms 미만인 반면, 동기화된 LinkedHashMap이 5k ops/sec에서 병목을 겪고 p99는 500ms에 달하는 결과를 보여주자 팀은 Caffeine을 선택했습니다. 마이그레이션에는 맵을 Caffeine.newBuilder().maximumSize(1000).build()로 대체하고 정리 로직을 위한 제거 리스너를 등록하는 것이 포함되었습니다.
배포 후 모니터링 결과 CPU 사용량은 안정적이고 스레드 정지는 없었습니다. 캐시 적중률은 85%에서 94%로 개선되었습니다. 왜냐하면 퇴출이 결정론적이고 경쟁이 없는 형태가 되었기 때문입니다. 이 사건은 LinkedHashMap이 편리한 API에도 불구하고 동시 LRU 캐시에는 부적합한 단일 스레드 데이터 구조라는 점을 강조했습니다.