<div id="readability-page-1" class="page"><div><h2 id="cache">Cache</h2>
캐시는 연산에 필요한 데이터, 값을 미리 갖다놓는 임시 메모리이다. 본래 CPU 에서 주기억장치, 보조기억장치까지 도달하는 비용은 매우 크다. 물리적으로도 거리가 멀다고 할 수 있다. 그런데 캐시의 경우 CPU 바로 옆에 딱 달라붙어있기 때문에 물리적으로 거리가 매우 짧아 접근 비용이 매우 적다. 따라서 자주 사용되는 값이나, 사용될 예정인 값을 미리 캐시에 적재해놓는다면 참조 시간을 대폭 줄여 성능을 높일 수 있다. 
<img src="https://media.vlpt.us/images/haero_kim/post/edeb68c6-3e72-47bf-9cc2-d208c2320cca/screenshot.png">
CPU 는 어떤 값이 필요할 때 가장 먼저 캐시를 방문하고 만약 캐시에 원하는 값이 있을 경우 이를 사용하는데, 만약 없다면 주기억 장치를 방문하게 된다. 따라서, CPU 가 자주 사용하는 값, 필요로 하는 값 등을 적절히 캐시에 배치해두어야 한다. 즉, 캐시 히트율을 높여야 성능을 높일 수 있는 것이다.
위의 설명만 봐도 캐시의 내용물들을 자주 갈아끼워질 필요가 있다. 캐시의 용량은 한정적인데다가 자주 사용되는 값 혹은 사용될 예정인 값은 시시각각 변하기 때문이다. 그런데 막무가내로 내용물을 갈아끼우면 캐시 히트율을 항상 높게 유지하기 어려울 것이고, 성능 악화로 이어질 수 있다. 따라서 캐시 히트율을 높게 유지하는 메모리 교체 알고리즘이 필요하다. 이를 위해 고안된 여러 알고리즘이 있고, 이번 포스팅에선 그 중 하나인 LRU 알고리즘을 적용한 LRU Cache 에 대해 알아보고자 한다.
 
<h2 id="lru-least-recently-used">LRU (Least Recently Used)</h2>
운영체제의 페이지 교체 알고리즘 중 하나이다. 페이지를 교체할 때 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법이다. 
 
<h2 id="lru-cache">LRU Cache</h2>
그렇다면, LRU Cache 는 캐시에 공간이 부족할 때 가장 오랫동안 사용하지 않은 항목을 제거하고 새로운 녀석을 배치하는 형식으로 동작된다고 유추할 수 있다. LRU Cache 의 전제 이론은 '오랫동안 사용되지 않은 항목은 앞으로도 사용되지 않을 가능성이 농후하기 때문에, 가장 오랫동안 참조되지 않은 녀석을 캐시에서 제거하자' 이다. 이 이론에 따라 캐시 메모리를 운영한다면 캐시 히트율을 높게 유지할 수 있다는 가정이 깔려있다. 실제로 성능이 입증됐으며, 가장 많이 사용되는 알고리즘이기도 하다.
<h3 id="구현-방식">구현 방식</h3>
LRU Cache 의 구현은 Double Linked List 를 통해 이루어질 수 있다. Head 에 가까운 데이터일 수록 최근에 사용된 데이터이고, Tail 에 가까울 수록 오랫동안 사용되지 않은 데이터로 간주한다. 따라서 새로운 데이터를 삽입할 때, Tail 값을 가장 먼저 삭제시키고 Head 에 데이터를 삽입하도록 하여 캐시 교체 시간 복잡도를 O(1) 로 갖게 된다.
그리고 만약 캐시에 적재된 어떤 데이터를 사용한 경우, 해당 데이터를 Head 로 옮겨 가장 최근에 사용된 값임을 명시한다. 즉, 삭제 우선순위에서 멀어지게 하는 것이다.
이를 도식화하면 아래와 같이 표현할 수 있다.
<img src="https://media.vlpt.us/images/haero_kim/post/8bde175e-366a-4973-9e28-373a9c370019/68747470733a2f2f6b2e6b616b616f63646e2e6e65742f646e2f6257377038492f6274717635686a6d4235452f58336c774d4e5150384e70324a746c326b516731454b2f696d672e706e67%20(2).png">
 
<h2 id="번외-android-에서의-lru">[번외] Android 에서의 LRU</h2>
안드로이드는 <code>LruCache</code> 라는 자료구조를 제공해준다. 내부 구현을 보면 <code>LinkedHashMap</code> 을 사용한 모습을 확인해볼 수 있다. Key-Value 형식으로 값을 참조할 수 있게끔 하기 위함이다.
<pre><code>public class LruCache&lt;K, V&gt; {
 @UnsupportedAppUsage
 private final LinkedHashMap&lt;K, V&gt; map;

 /** Size of this cache in units. Not necessarily the number of elements. */
 private int size;
 private int maxSize;
		
		...
}</code></pre>
<code>LruCache&lt;K, V&gt;</code> 는 아래와 같이 사용해볼 수 있다.
<pre><code>val cache = LruCache&lt;String, Int&gt;(5) // maxSize = 5

cache.put("A",0) // [A]
cache.put("B",0) // [A, B]
cache.put("C",0) // [A, B, C]
cache.put("D",0) // [A, B, C, D]
cache.put("E",0) // [A, B, C, D, E] - A부터 E까지 캐싱 완료
cache.put("F",0) // [B, C, D, E, F] - F를 캐싱하면, A는 제거됨
cache.put("D",0) // [B, C, E, F, D] - D를 다시 캐싱하면 최근 참조된 상태로 변경
cache.get("C") // [B, E, F, D, C] - C를 통해 캐시된 데이터 접근시 최근 참조된 상태로 변경</code></pre>
이를 응용하면, 안드로이드에서의 <code>Bitmap</code> 캐싱을 구현할 수 있다. 실제로 <code>Glide</code> 이미지 라이브러리도 비트맵 캐싱 방식을 활용하여 성능을 최적화하게 된다.
<pre><code>int cacheSize = 4 * 1024 * 1024; // 4MB
LruCache&lt;String, Bitmap&gt; bitmapCache = new LruCache&lt;String, Bitmap&gt;(cacheSize) {
 protected int sizeOf(String key, Bitmap value) {
 return value.getByteCount();
 }
}</code></pre>
<hr>
<h3 id="참고자료">참고자료</h3>
<a href="https://www.charlezz.com/?p=44551">https://www.charlezz.com/?p=44551</a></div></div>

해로, HAERO, 海路

Cache
캐시는 연산에 필요한 데이터, 값을 미리 갖다놓는 임시 메모리이다. 본래 CPU 에서 주기억장치, 보조기억장치까지 도달하는 비용은 매우 크다. 물리적으로도 거리가 멀다고 할 수 있다. 그런데 캐시의 경우 CPU 바로 옆에 딱 달라붙어있기 때문에 물리적으로 거리가 매우 짧아 접근 비용이 매우 적다. 따라서 자주 사용되는 값이나, 사용될 예정인 값을 미리 캐시에 적재해놓는다면 참조 시간을 대폭 줄여 성능을 높일 수 있다. 
CPU 는 어떤 값이 필요할 때 가장 먼저 캐시를 방문하고 만약 캐시에 원하는 값이 있을 경우 이를 사용하는데, 만약 없다면 주기억 장치를 방문하게 된다. 따라서, CPU 가 자주 사용하는 값, 필요로 하는 값 등을 적절히 캐시에 배치해두어야 한다. 즉, 캐시 히트율을 높여야 성능을 높일 수 있는 것이다.
위의 설명만 봐도 캐시의 내용물들을 자주 갈아끼워질 필요가 있다. 캐시의 용량은 한정적인데다가 자주 사용되는 값 혹은 사용될 예정인 값은 시시각각 변하기 때문이다. 그런데 막무가내로 내용물을 갈아끼우면 캐시 히트율을 항상 높게 유지하기 어려울 것이고, 성능 악화로 이어질 수 있다. 따라서 캐시 히트율을 높게 유지하는 메모리 교체 알고리즘이 필요하다. 이를 위해 고안된 여러 알고리즘이 있고, 이번 포스팅에선 그 중 하나인 LRU 알고리즘을 적용한 LRU Cache 에 대해 알아보고자 한다.
LRU (Least Recently Used)
운영체제의 페이지 교체 알고리즘 중 하나이다. 페이지를 교체할 때 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 삼는 기법이다. 
LRU Cache
그렇다면, LRU Cache 는 캐시에 공간이 부족할 때 가장 오랫동안 사용하지 않은 항목을 제거하고 새로운 녀석을 배치하는 형식으로 동작된다고 유추할 수 있다. LRU Cache 의 전제 이론은 '오랫동안 사용되지 않은 항목은 앞으로도 사용되지 않을 가능성이 농후하기 때문에, 가장 오랫동안 참조되지 않은 녀석을 캐시에서 제거하자' 이다. 이 이론에 따라 캐시 메모리를 운영한다면 캐시 히트율을 높게 유지할 수 있다는 가정이 깔려있다. 실제로 성능이 입증됐으며, 가장 많이 사용되는 알고리즘이기도 하다.
구현 방식
LRU Cache 의 구현은 Double Linked List 를 통해 이루어질 수 있다. Head 에 가까운 데이터일 수록 최근에 사용된 데이터이고, Tail 에 가까울 수록 오랫동안 사용되지 않은 데이터로 간주한다. 따라서 새로운 데이터를 삽입할 때, Tail 값을 가장 먼저 삭제시키고 Head 에 데이터를 삽입하도록 하여 캐시 교체 시간 복잡도를 O(1) 로 갖게 된다.
그리고 만약 캐시에 적재된 어떤 데이터를 사용한 경우, 해당 데이터를 Head 로 옮겨 가장 최근에 사용된 값임을 명시한다. 즉, 삭제 우선순위에서 멀어지게 하는 것이다.
이를 도식화하면 아래와 같이 표현할 수 있다.
[번외] Android 에서의 LRU
안드로이드는 LruCache 라는 자료구조를 제공해준다. 내부 구현을 보면 LinkedHashMap 을 사용한 모습을 확인해볼 수 있다. Key-Value 형식으로 값을 참조할 수 있게끔 하기 위함이다.
public class LruCache<K, V> {
 @UnsupportedAppUsage
 private final LinkedHashMap<K, V> map;
 /** Size of this cache in units. Not necessarily the number of elements. */
 private int size;
 private int maxSize;
 ...
}
LruCache<K, V> 는 아래와 같이 사용해볼 수 있다.
val cache = LruCache<String, Int>(5) // maxSize = 5
cache.put("A",0) // [A]
cache.put("B",0) // [A, B]
cache.put("C",0) // [A, B, C]
cache.put("D",0) // [A, B, C, D]
cache.put("E",0) // [A, B, C, D, E] - A부터 E까지 캐싱 완료
cache.put("F",0) // [B, C, D, E, F] - F를 캐싱하면, A는 제거됨
cache.put("D",0) // [B, C, E, F, D] - D를 다시 캐싱하면 최근 참조된 상태로 변경
cache.get("C") // [B, E, F, D, C] - C를 통해 캐시된 데이터 접근시 최근 참조된 상태로 변경
이를 응용하면, 안드로이드에서의 Bitmap 캐싱을 구현할 수 있다. 실제로 Glide 이미지 라이브러리도 비트맵 캐싱 방식을 활용하여 성능을 최적화하게 된다.
int cacheSize = 4 * 1024 * 1024; // 4MB
LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
 protected int sizeOf(String key, Bitmap value) {
 return value.getByteCount();
 }
}
참고자료
https://www.charlezz.com/?p=44551

LRU Cache 이해하기

댓글