O(log n) 오버헤드 제거를 위한 Approximate LRU 및 Eviction Pool 설계

Context

전통적인 True LRU 구현 시 발생하는 모든 Read 요청에 대한 메타데이터 업데이트 비용 분석. 특히 수백만 건의 Request 처리 환경에서 Heap 유지나 Doubly-linked List 수정으로 인한 O(log n) 혹은 공유 자원 경합 발생 가능성 식별.

Technical Solution

• Read Path의 성능 극대화를 위해 매 요청마다 수행하는 LRU 순서 업데이트 로직을 완전히 제거한 설계
• 메모리 한계 도달 시에만 작동하는 Random Sampling 방식을 통한 Approximate LRU 알고리즘 도입
• 기본 5개의 Key를 무작위 추출하여 최신성이 가장 낮은 항목을 제거하는 통계적 접근 방식 적용
• 추출된 Candidate들을 16개 크기의 Eviction Pool에 유지하여 샘플링 효율을 높이는 최적화 구조 설계
• 드문 발생 이벤트인 Eviction 시점에만 연산 비용을 집중시켜 Hot Path의 응답 속도를 보존하는 전략 채택