FIFO queues are all you need for cache eviction (SOSP'23) 의 연장선 같은 느낌의 논문이다. 저자도 같다.
대충 요약하자면 굉장히 심플한 알고리즘인 SIEVE의 성능이 기타 복잡한 Cache Eviction Policy들보다 비슷하거나 낫다는 이야기이다.
이런 식으로 지금까지 많은 알고리즘이 등장했다. GL-Cache 같은 경우 같은 저자가 쓴 논문.
근데 당연히도 복잡한 알고리즘은 안 좋다. 유지하기도 어렵고 파라미터 튜닝하기도 어렵고.
그래서 Lazy promotion과 Quick demotion이 특징인 SIEVE를 만들었다. SIEVE는 앞서 말한 FIFO queues are all you need for cache eviction 의 디자인을 좀 더 간단하게 만든 거 같은 구조이다.
FIFO도 그렇고 이 두 논문의 핵심은 "한번만 읽은 데이터는 보통 다시 읽지 않지만, 두 번 이상 본 데이터는 다시 읽더라" 이다. 즉 한번만 액세스 된 친구들, 즉 Cold region과 두 번 이상 본 데이터들, Hot region을 구분하는 것이다.
SIEVE는 다음과 같이 작동된다. (Linked List를 이용해 구현했다 가정하자)
- 처음 액세스 한 object라면 공간이 허락할 때까지 Queue앞에 넣는다.
- 이미 cache에 있는 object라면 visited를 1로 만든다.
- 이제 Evict를 해야 할 때가 왔다.
- SIEVE는 현재의 커서를 유지하는데, 그 커서는 한 방향으로 sweep하는 방식이다.
- visited가 1인 object를 만나면 visited를 0으로 만들고 진행한다.
- 0인 object를 만나면 evict하고 큐 맨 앞에 object를 추가한다.
- 큐 시작에 도달하면 커서를 다시 큐 끝으로 보낸다.
- 이렇게 계속 반복하면 커서 앞은 cold region, 뒤는 hot region이 된다.
이 논문을 읽고 가장 먼저 든 생각은 "이렇게 간단한 알고리즘을 왜 지금까지 못 찾았지?"이다... 사실 잘 모르겠다. 왤까??