[번역] An O(1) algorithm for implementing the LFU cache eviction scheme

An O(1) algorithm for implementing the LFU cache eviction scheme

 

Prof. Ketan Shah, Anirban Mitra, Dhruv Matani

August 16, 2010

원문

(참고): Go 구현

Abstract

캐시 제거 알고리즘은 애플리케이션에서 사용하는 데이터를 캐싱하여 실행 속도를 높이기 위해 캐시를 사용하는 운영 체제, 데이터베이스 및 기타 시스템에서 널리 사용됩니다. 다음과 같은 많은 정책이 있습니다.
MRU(가장 최근 사용), MFU(가장 자주 사용), LRU(가장 최근 사용), LFU(가장 적게 사용) 등 다양한 정책이 있으며, 각각 장단점이 있으므로 특정 시나리오에 따라 사용됩니다. 지금까지 가장 널리 사용되는 알고리즘은 O(1)의 작동 속도와 대부분의 애플리케이션에서 예상되는 동작 유형과 매우 유사하기 때문에 LRU입니다. LFU 알고리즘은 또한 많은 실제 워크로드에서 바람직한 동작을 수행합니다. 그러나 많은 경우, 런타임 복잡성이 O(1)로 O(log n)에 비해 낮기 때문에 LRU 알고리즘이 LFU 알고리즘보다 선호됩니다. 여기서는 모든 연산에 대해 런타임 복잡도가 O(1)인 LFU 캐시 제거 알고리즘을 소개합니다. 삽입, 액세스, 삭제(퇴거)를 포함한 모든 연산에 대해 런타임 복잡도가 O(1)입니다.

 

1. Introduction

이 문서는 다음과 같이 구성되어 있습니다.

• 다른 캐시 퇴출 알고리즘보다 우수함을 입증할 수 있는 LFU의 사용 사례에 대한 설명 다른 캐시 제거 알고리즘보다 우수함을 입증할 수 있는 사용 사례에 대한 설명
• LFU 캐시 구현에서 지원해야 하는 사전 연산. 전략의 런타임 복잡성을 결정하는 연산.
• 현재 가장 잘 알려진 LFU 알고리즘과 런타임 복잡성에 대한 설명.
• 제안된 LFU 알고리즘에 대한 설명으로, 모든 연산의 런타임 복잡도가 의 런타임 복잡도는 O(1)

2. Uses of LFU

HTTP 프로토콜을 위한 캐싱 네트워크 프록시 애플리케이션을 생각해 봅시다. 이 프록시는 일반적으로 인터넷과 사용자 또는 사용자 집합 사이에 위치합니다. 모든 사용자가 인터넷에 액세스할 수 있도록 보장하고 공유 가능한 모든 리소스를 공유하여 네트워크 활용도를 최적화하고 응답성을 개선합니다. 이러한 캐싱 프록시는 제한된 스토리지 또는 메모리에서 캐싱할 수 있는 데이터의 양을 최대화해야 합니다 [[4, 8, 7]]. 일반적으로 이미지, CSS 스타일시트, 자바스크립트 코드와 같은 많은 정적 리소스는 최신 버전으로 교체되기 전까지 상당히 오랜 시간 동안 매우 쉽게 캐싱될 수 있습니다. 이러한 정적 리소스 또는 프로그래머가 'assets'이라고 부르는 리소스는 거의 모든 페이지에 포함되어 있으므로 거의 모든 요청에 이러한 리소스가 필요하므로 캐싱하는 것이 가장 유리합니다. 또한 네트워크 프록시는 초당 수천 건의 요청을 처리해야 하므로 이에 필요한 오버헤드를 최소한으로 유지해야 합니다.
이를 위해 자주 사용되지 않는 리소스만 퇴출해야 합니다. 따라서 자주 사용되는 리소스는 오랜 기간 동안 유용하다는 것이 입증되었으므로 자주 사용되지 않는 리소스를 희생하여 유지해야 합니다. 물론 과거에 많이 사용되었던 리소스가 미래에는 필요하지 않을 수도 있다는 반론도 있지만, 대부분의 상황에서 그렇지 않은 것으로 나타났습니다. 예를 들어, 많이 사용되는 페이지의 정적 리소스는 항상 해당 페이지의 모든 사용자가 요청합니다. 따라서 LFU 캐시 교체 전략은 이러한 캐싱 프록시가 메모리가 부족할 때 캐시에서 가장 자주 사용되지 않는 항목을 제거하기 위해 사용할 수 있습니다. LRU도 여기에 적용 가능한 전략일 수 있지만 요청 패턴이 요청된 모든 항목이 캐시에 맞지 않고 라운드 로빈 방식으로 항목이 요청되는 경우 실패할 수 있습니다. LRU의 경우 사용자 요청이 캐시에 도달하지 않고 아이템이 계속 캐시에 들어오고 나가게 됩니다. 그러나 동일한 조건에서 LFU 알고리즘은 캐시된 항목의 대부분이 캐시 히트로 이어져 훨씬 더 나은 성능을 발휘합니다. 하지만 LFU 알고리즘의 병리적 동작이 불가능한 것은 아닙니다. 이 글에서는 LFU의 사례를 제시하려는 것이 아니라, LFU가 적용 가능한 전략이라면 이전에 발표된 것보다 더 나은 구현 방법이 구현하는 더 좋은 방법이 있다는 것을 보여드리고자 합니다.

3. Dictionary operations supported by an LFU cache

캐시 퇴출 알고리즘에 대해 이야기할 때는 주로 캐시된 데이터에 대한 세 가지 작업을 염두에 두어야 합니다.

• 캐시에 항목 설정(또는 삽입)
• 캐시에서 항목 검색(또는 조회), 동시에 사용 횟수 증가(LFU의 경우)
•  사용 빈도가 가장 낮은 항목을 퇴거(또는 삭제)합니다(또는 퇴거 알고리즘의 전략에 따라 퇴거 알고리즘의 전략에 따라) 캐시에서 항목을 퇴거(또는 삭제)합니다.

4. The currently best known complexity of the LFU algorithm

이 글을 쓰는 현재, 위에서 언급한 각 작업에 대해 가장 잘 알려진 런타임은 에 대해 가장 잘 알려진 런타임은 다음과 같습니다:

• 삽입: O(log n)
• 조회: O(log n)
• 삭제: O(log n)

이러한 복잡성 값은 이진 힙 구현의 복잡성과 표준 충돌 없는 해시 테이블의 복잡성에서 직접적으로 따라옵니다. LFU 캐싱 전략은 최소 힙 데이터 구조와 해시 맵을 사용하여 쉽고 효율적으로 구현할 수 있습니다. 최소 힙은 (항목의) 사용 횟수를 기반으로 생성되고 해시 테이블은 항목)을 기반으로 생성되며 해시 테이블은 요소의 키를 통해 인덱싱됩니다. 충돌 없는 해시 테이블의 모든 연산은 O(1)의 순서를 가지므로 LFU 캐시의 런타임은 최소 힙 [[5, 6, 9, 1, 2]]에서의 연산 런타임에 의해 결정됩니다. 요소가 캐시에 삽입되면 사용 횟수가 1로 들어가고 최소 힙에 삽입하는 데 O(log n)의 비용이 들기 때문에 LFU 캐시에 삽입하는 데 O(log n)의 시간이 걸립니다 [[3]]. 요소를 조회할 때는 실제 요소의 키를 해싱하는 해싱 함수를 통해 요소를 찾습니다. 동시에 사용 횟수(최대 힙의 횟수)가 1씩 증가하여 최소 힙이 재구성되고 요소는 루트에서 멀어집니다. 요소는 어느 단계에서든 log n 수준까지 아래로 이동할 수 있으므로 이 작업에도 O(log n) 시간이 걸립니다. 퇴거를 위해 요소가 선택된 후 결국 힙에서 제거되면 힙 데이터 구조가 크게 재구성될 수 있습니다. 사용 횟수가 가장 적은 요소는 최소 힙의 루트에 존재합니다. 최소 힙의 루트를 삭제하려면 루트 노드를 힙의 마지막 리프 노드로 교체하고 이 노드를 올바른 위치로 버블링해야 합니다. 이 연산 역시 런타임 복잡성이 O(log n)입니다.

 

5. The proposed LFU algorithm

제안된 LFU 알고리즘은 LFU 캐시에서 수행할 수 있는 각 사전 연산(삽입, 조회, 삭제)에 대해 런타임 복잡도가 O(1)입니다. 이는 2개의 연결된 목록을 유지함으로써 달성되는데, 하나는 액세스 빈도에 대한 목록이고 다른 하나는 액세스 빈도가 동일한 모든 요소에 대한 목록입니다. 해시 테이블은 키별로 요소에 액세스하는 데 사용됩니다(아래 다이어그램에는 명확성을 위해 표시되지 않음). 이중 링크 목록은 액세스 빈도가 동일한 노드 집합을 나타내는 노드를 함께 연결하는 데 사용됩니다(아래 그림에서 직사각형 블록으로 표시됨). 블록으로 표시됨). 이 이중 링크 목록을 빈도 목록이라고 합니다. 액세스 빈도가 동일한 노드 집합은 실제로는 이러한 노드의 이중 이중으로 연결된 목록입니다(아래 다이어그램에서는 원형 노드로 표시됨). 우리는 이 이중으로 연결된 목록(특정 빈도에 국한된)을 노드 목록이라고 합니다. 노드 목록의 각 노드에는 부모 노드에 대한 포인터가 있습니다. 빈도 목록(명확성을 위해 다이어그램에는 표시되지 않음)에 대한 포인터를 가집니다. 따라서 노드 x와 y는 노드 1에 대한 포인터를 가지며, 노드 z와 a는 노드 2에 대한 포인터를 가지게 됩니다. 2 등에 대한 포인터를 갖습니다...

그림 1: 6개의 요소로 구성된 LFU 딕셔너리

아래 의사 코드는 LFU 캐시를 초기화하는 방법을 보여줍니다. 키별로 요소를 찾는 데 사용되는 해시 키별로 요소를 찾는 데 사용되는 테이블은 bykey 변수로 표시됩니다. 우리는 동일한 액세스 빈도를 가진 요소를 저장하기 위해 링크된 목록 대신에 집합을 사용합니다. 구현을 단순화하기 위해 링크드 리스트 대신 SET을 사용합니다. 변수 항목은 표준 SET 데이터입니다.

그림 2: 키 'z'가 있는 요소에 한 번 더 액세스한 후

구조는 액세스 빈도가 동일한 요소의 키를 보유합니다. 삽입, 조회, 삭제 런타임 복잡성은 O(1)입니다.

 

액세스 빈도 값이 0(zero)인 새 'frequency node'를 생성.

NEW-FREQ-NODE()

01 Object o

02 o.value ← 0

03 o.items ← SET()

04 o.prev ← o

05 o.next ← o

06 return o

 

조회 테이블에 저장되는 새 LFU 항목을 bykey로 생성.

NEW-LFU-ITEM(data, parent)

01 Object o

02 o.data ← data

03 o.parent ← parent

04 return o

 

새 LFU 캐시 생성

NEW-LFU-CACHE()

01 Object o

02 o.bykey ← HASH-MAP()

03 o.freq head ← NEW-FREQ-NODE

04 return o

 

LFU 캐시 객체는 lfu 캐시 변수를 통해 액세스할 수 있습니다.

lfu 캐시 ← NEW-LFU-CACHE()

 

또한 링크된 목록 조작을 지원하는 몇 가지 헬퍼 함수를 정의합니다.

 

새 항목을 만들고 이전 및 다음 포인터를 이전 및 다음 항목으로 설정.

GET-NEW-NODE(value, prev, next)

01 nn ← NEW-FREQ-NODE()

02 nn.value ← value

03 nn.prev ← prev

04 nn.next ← next

05 prev.next ← nn

06 next.prev ← nn

07 return nn

 

링크된 목록에서 노드 제거(링크 해제).

DELETE-NODE(node)

01 node.prev.next ← node.next

02 node.next.prev ← prev

 

처음에 LFU 캐시는 빈 해시 맵과 빈 빈도 목록으로 시작됩니다. 첫 번째 요소가 추가되면 해시 맵에 이 새 요소를 가리키는 단일 요소 에 이 새 요소를 가리키는 단일 요소(bykey)가 생성되고 값이 1인 새 빈도 노드가 생성되고 값이 1인 노드가 빈도 목록에 추가됩니다. 해시 맵의 요소 수 해시 맵에 있는 요소의 수는 LFU 캐시의 항목 수와 같아야 합니다. 1의 빈도 목록에 새 노드가 추가됩니다. 이 노드는 실제로 는 자신이 멤버인 빈도 노드를 다시 가리킵니다. 예를 들어, x가 노드가 추가된 경우, 노드 x는 빈도 노드 1을 다시 가리킵니다. 따라서 요소 삽입의 런타임 복잡성은 O(1)입니다.

 

LFU 캐시에서 엘리먼트에 액세스(불러오기)하면서 동시에 해당 엘리먼트의 사용 횟수

ACCESS(key)

01 tmp ← lfu cache.bykey[key]

02 if tmp equals null then

03 throw Exception(”No such key”)

04 freq ← tmp.parent

05 next freq ← freq.next

06

07 if next freq equals lfu cache.freq head or

08 next freq.value does not equal freq.value + 1 then

08 next freq ← GET-NEW-NODE(freq.value + 1, freq, next freq)

09 next freq.items.add(key)

10 tmp.parent ← next freq

11

12 freq.items.remove(key)

13 if freq.items.length equals 0 then

14 DELETE-NODE(freq)

15 return tmp.data

 

이 요소에 다시 한 번 액세스하면 요소의 빈도 노드를 조회하고 다음 형제자매의 값을 쿼리합니다. 형제 노드가 존재하지 않거나 다음 형제 노드의 값이 해당 요소의 값보다 1이 더 크지 않은 경우, 이 빈도 노드의 값보다 1이 더 큰 새로운 빈도 노드가 이 빈도 노드의 값보다 1이 더 큰 값으로 새로 생성되어 올바른 위치에 삽입됩니다. 노드는 현재 세트에서 제거되고 새 빈도 목록의 세트에 삽입됩니다. 노드의 빈도 포인터 가 새 빈도 노드를 가리키도록 업데이트됩니다. 예를 들어, 노드 z가 한 번 더 액세스(1)하면 빈도 목록에서 제거되고 빈도 목록의 값을 갖는 빈도 목록에서 제거되고 3 값을 갖는 빈도 목록에 추가됩니다(2). 따라서 요소 액세스의 런타임 복잡성은 O(1)입니다.

 

LFU 캐시에 새 요소를 삽입.

INSERT(key, value)

01 if key in lfu cache.bykey then

02 throw Exception(”Key already exists”)

03

04 freq ← lfu cache.freq head.next

05 if freq.value does not equal 1 then

06 freq ← GET-NEW-NODE(1, lfu cache.freq head, freq)

07

08 freq.items.add(key)

09 lfu cache.bykey[key] ← NEW-LFU-ITEM(value, freq)

 

액세스 빈도가 가장 낮은 요소를 삭제해야 하는 경우 첫 번째(가장 왼쪽) 빈도 목록에서 아무 요소나 선택하여 제거합니다. 이 삭제로 인해 이 빈도 목록의 노드 목록이 비어 있으면 빈도 노드도 삭제됩니다. 해시 맵에서 요소의 참조도 삭제됩니다. 따라서 사용 빈도가 가장 낮은 요소를 삭제할 때의 런타임 복잡성은 O(1)입니다.

 

캐시에서 사용 횟수가 가장 적은 항목(가장 자주 사용하지 않는 항목) 가져오기.

GET-LFU-ITEM()

01 if lfu cache.bykey.length equals 0 then

02 throw Exception(”The set is empty”)

03 return lfu cache.bykey[ lfu cache.freq head.next.items[0] ]

 

따라서 LFU 캐시에서 각 딕셔너리 연산의 런타임 복잡성은 의 런타임 복잡도는 O(1)입니다.

 

References

[1] Hyokyung Bahn, Sang Lyul Min Sam H. Noh, and Kern Koh, Using full reference history for efficient document replacement in web caches, usenix (1999).

[2] Sorav Bansal and Dharmendra S. Modha, Car: Clock with adaptive replacement, usenix (2004).

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, second edition, (2002), 130–132.

[4] G. Karakostas and D. N. Serpanos, Practical lfu implementation for web caching, (June 19, 2000).

[5] Donghee Lee, Jongmoo Choi, Jong hun Kim, Sam H. Noh, Sang Lyul Min, Yookun Cho, and Chong sang Kim, Lrfu: A spectrum of policies that subsumes the least recently used and least frequently used policies, (March 10, 2000).

[6] Elizabeth J. O’Neil, Patrick E. O’Neil, and Gerhard Weikum, An optimality proof of the lru-k page replacement algorithm, (1996).

[7] Junho Shim, Peter Scheuermann, and Radek Vingralek, Proxy cache design: Algorithms, implementation and performance, IEEE Transactions on Knowledge and Data Engineering (1999).

[8] Dong Zheng, Differentiated web caching - a differentiated memory allocation model on proxies, (2004).

[9] Yuanyuan Zhou and James F. Philbin, The multi-queue replacement algorithm for second level buffer caches, usenix (2001).