코딩테스트 OT, 캐시와 핫키
하나의 값을 빠르게 찾는 코드에서 출발해 같은 값을 동시에 요청하는 서비스까지 설계합니다.
캐시 문제를 코딩테스트에서 만나면 보통 이런 요구사항이 나옵니다.
주어진 용량 안에서 값을 저장하고, 최근에 사용하지 않은 값을 제거하면서, 조회와 갱신을 빠르게 구현하라는 것입니다.
해시맵과 이중 연결 리스트를 조합하면 평균 O(1)에 처리할 수 있습니다.
그런데 이 코드를 서버에 넣었다고 해서 서비스의 캐시 문제가 해결되지는 않습니다.
사용자 수가 늘어나면 같은 키를 여러 요청이 동시에 읽습니다. 캐시가 만료되는 순간에는 여러 서버가 같은 데이터를 다시 가져옵니다. 데이터베이스에서 오래전에 읽기 시작한 값이 최신 값보다 늦게 도착할 수도 있습니다.
심지어 캐시 적중률이 높은 상태에서도 특정 노드의 응답 시간이 길어질 수 있습니다.
이번 OT에서는 LRU Cache 문제를 풀면서 자료구조를 선택하는 과정을 먼저 살펴보겠습니다. 이후 같은 문제에 동시성, 네트워크, 데이터 변경, 장애 복구를 추가하겠습니다.
코딩테스트에서는 연산의 정확성과 복잡도를 설명해야 합니다.
시스템 디자인에서는 여기에 더해 누가 같은 작업을 반복하는지, 어느 값까지 오래되어도 되는지, 실패한 요청이 어디로 이동하는지를 설명해야 합니다.
문제
제한된 공간에서 최근에 사용한 값을 남겨야 합니다
다음 연산을 지원하는 LRU Cache를 구현한다고 하겠습니다.
LRU는 가장 오랫동안 사용하지 않은 항목을 먼저 제거하는 정책입니다.
캐시에 공간이 부족하면 마지막으로 사용한 시점이 가장 오래된 항목을 제거합니다. 여기서 사용에는 조회와 갱신이 모두 포함됩니다.
문제의 조건은 다음과 같습니다.
* get(key)는 키가 존재하면 값을 반환하고 해당 키를 가장 최근에 사용한 상태로 변경합니다.
* get(key)는 키가 존재하지 않으면 -1을 반환합니다.
* put(key, value)는 새 키를 추가하거나 기존 키의 값을 변경합니다.
* 기존 키를 변경하면 해당 키도 가장 최근에 사용한 상태가 됩니다.
* 용량을 초과하면 가장 오랫동안 사용하지 않은 키를 제거합니다.
* 조회와 갱신은 평균 O(1)을 목표로 합니다.
* 값은 0 이상의 정수이며, 용량이 0이면 어떤 값도 보관하지 않습니다.
이 코딩 문제에서는 하나의 실행 흐름이 순서대로 연산한다고 가정합니다. TTL이나 네트워크 요청은 아직 포함하지 않습니다.
용량이 2라면 다음과 같이 동작합니다.
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
cache.get(1) # 10
cache.put(3, 30)
cache.get(2) # -1
cache.get(1) # 10
cache.get(3) # 30get(1)을 호출했으므로 키 1은 최근에 사용한 항목이 됩니다.
이후 키 3을 넣으면 키 2가 제거되어야 합니다.
단순히 먼저 들어온 값을 제거하면 이 요구사항을 만족하지 못합니다. 저장 순서와 사용 순서가 다르기 때문입니다.
같은 캐시를 서비스에 적용해 보겠습니다
온라인 코딩 학습 서비스에서 사용자들이 문제 설명을 읽는다고 하겠습니다.
평소에는 서로 다른 문제를 읽지만, 강의에서 특정 문제를 소개하거나 대회가 시작되면 같은 문제에 요청이 집중됩니다.
가장 단순한 구현은 요청마다 데이터베이스에서 문제 설명을 읽는 것입니다.
같은 설명을 반복해서 조회하므로 캐시를 추가할 수 있습니다. 문제 설명이 캐시에 있으면 바로 반환하고, 없으면 데이터베이스에서 읽어 캐시에 저장합니다.
이제 질문이 달라집니다.
문제 설명을 읽는 동안 같은 요청이 1,000개 더 도착하면 어떻게 해야 할까요.
