LRU 캐시에서 "대량 이탈"방지

Question

LRU 캐시를 구현했습니다. 새 항목을 삽입하는 과정은 다음과 같습니다.

1. haystack에 충분한 공간이 있는지 확인하십시오. 예인 경우 4로 이동하십시오.
2. 가장 최근에 사용한 적이없는 항목을 제거하십시오.
3. 충분한 공간이 있는지 확인하십시오. 그렇지 않다면 2를 반복하십시오.
4. 빈 공간에 항목을 삽입하십시오.

항목은 건초 더미에서 효과적으로 무작위로 정렬됩니다.

이전 항목보다 큰 항목을 삽입해야하는 경우 문제가 발생합니다. 그것은 "대량 퇴거 (mass eviction)"로 이어진다. 여기서 충분한 항목이 축출 될 때까지 계속되는 퇴화 과정을 거치면서 몇 개의 인접한 아이템이 퇴거되었다.

이 "대량 이탈"은 종종 수만 가지 항목을 퇴치하는 것을 포함합니다.

이 "대량 퇴거"를 피하거나 완화하기 위해 수행 할 수있는 조치는 무엇입니까?

Answer 1

모든 캐시 항목에 크기와 나이에 비례하는 가중치를 부여하는 것을 검토했습니다.

(정말 오래된 예. 정말 큰 항목은 큰 무게를 가지고있다. 크기가 매우 작 으면 정말 오래된 항목이 거의 너무 많은 무게가없는) 그런 다음 "에 따라 일을 퇴거

을 무게". 그것은 더 오래된 1 만개의 작은 아이템을 추방하는 것보다 크고 보통의 아이템을 퇴거시키는 것을 선호 할 것입니다.

Answer 2

아마도 Buddy 메모리 할당을 살펴볼 수 있습니다. 리눅스 커널 :

http://en.wikipedia.org/wiki/Buddy_memory_allocation

이 방법은, 내가 버디 방법은 분열을 피하고 효율적 아직 있기 때문에, 당신은 여전히 ​​엄격하게 필요한 것보다 더 많은 항목을 퇴거 거라고 생각, 난 당신이 큰을 찾을 거라고 생각 것 더 빨리 차단하십시오.