🛠️ 처음부터 만드는 LRU Cache — lru-cache 스타일 최소 최근 사용 캐시 18줄 구현
문제
API 호출, DB 쿼리, 이미지 처리… 비싼 연산 결과를 캐싱하고 싶은데,
무한정 쌓으면 메모리가 터진다.
"가장 오래 안 쓴 것부터 버리자" — 이게 LRU(Least Recently Used) 캐시다.
`lru-cache` npm 패키지는 주간 다운로드 2억 건 이상.
핵심 원리를 18줄로 직접 만들어보자.
---
핵심 아이디어
ES6 `Map`은 삽입 순서를 기억한다.
→ 읽을 때마다 삭제 후 재삽입하면, Map의 첫 번째 항목이 항상 "가장 오래 안 쓴 것"이 된다.
---
코드 (TypeScript, 18줄)
```typescript
class LRUCache
private map = new Map
constructor(private capacity: number) {}
get(key: K): V | undefined {
if (!this.map.has(key)) return undefined;
const value = this.map.get(key)!;
this.map.delete(key); // 삭제 후
this.map.set(key, value); // 재삽입 → 맨 뒤(최신)로 이동
return value;
}
set(key: K, value: V): void {
if (this.map.has(key)) this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.capacity) {
const oldest = this.map.keys().next().value!; // 맨 앞 = 가장 오래된 것
this.map.delete(oldest);
}
}
}
```
---
사용 예제
```typescript
const cache = new LRUCache
cache.set('a', 1);
cache.set('b', 2);
cache.set('c', 3);
console.log(cache.get('a')); // 1 — 'a'가 최근 사용됨
cache.set('d', 4); // 용량 초과 → 'b' 제거 (가장 오래 안 씀)
console.log(cache.get('b')); // undefined — 퇴거됨
console.log(cache.get('c')); // 3 — 아직 살아있음
```
---
한 줄씩 뜯어보기
| 줄 | 설명 |
|----|------|
| `get()` — delete + set | 접근할 때마다 삭제 후 재삽입 → Map 맨 뒤로 이동 (= 최근 사용) |
| `set()` — has → delete | 이미 있는 키면 삭제 후 재삽입 (순서 갱신) |
| `keys().next().value` | Map의 첫 번째 키 = 가장 오래된 항목 (삽입 순서 보장) |
| `size > capacity` | 넘치면 가장 오래된 1개 제거 |
---
실전 활용: API 응답 캐싱
```typescript
const apiCache = new LRUCache
async function fetchUser(id: string) {
const cached = apiCache.get(id);
if (cached) return cached; // 캐시 히트
const res = await fetch(`/api/users/${id}`);
const data = await res.json();
apiCache.set(id, data); // 캐시 미스 → 저장
return data;
}
```
---
시간 복잡도
| 연산 | Map 기반 | 연결 리스트+해시맵 |
|------|---------|------------------|
| get | O(1) amortized | O(1) |
| set | O(1) amortized | O(1) |
| 구현 난이도 | ⭐ 쉬움 | ⭐⭐⭐ 어려움 |
Map의 delete+set은 엔진 최적화 덕에 실측 성능도 우수하다.
프로덕션에서 극한 성능이 필요하면 `lru-cache` 패키지를 쓰자.
---
TTL(만료 시간) 확장 — +8줄
```typescript
class LRUCacheWithTTL
getWithTTL(key: K): V | undefined {
const entry = this.get(key);
if (!entry) return undefined;
if (Date.now() > entry.expires) { this.set(key, undefined as any); return undefined; }
return entry.value;
}
setWithTTL(key: K, value: V, ttlMs: number): void {
this.set(key, { value, expires: Date.now() + ttlMs });
}
}
```
---
공식 문서 & 참고
👁 0 views
Comments (0)
💬
No comments yet.
Be the first to comment!