📚 지식 노트

LRU 캐시: 해시 맵과 이중 연결 리스트

캐시(cache)는 느린 원본(디스크, 네트워크, 무거운 계산) 앞에 둔 작고 빠른 저장소다. 칸이 모자라면 무엇을 내보낼지 정해야 하는데, 가장 흔한 규칙이 LRU(least recently used, 가장 오래 안 쓴 것부터)다. 최근에 쓴 것은 곧 또 쓸 가능성이 높다는 시간 지역성에 기대는 규칙이다.

요구 사항은 둘이다. 키로 값을 O(1)에 찾아야 하고, “가장 오래 안 쓴 것”도 O(1)에 알아야 한다. 해시 맵 하나로는 순서를 모르고, 리스트 하나로는 찾기가 O(n)이다. 그래서 둘을 겹친다. 해시 노트의 해시 맵은 키 → 리스트 노드를 들고, 선형 자료구조 노트의 이중 연결 리스트는 쓴 순서대로 노드를 줄 세운다.

• get: 맵에서 노드를 찾아, 리스트에서 떼어 맨 앞에 붙인다. 이중 연결이라 앞뒤 노드를 바로 알아서 떼는 데 O(1)이다.
• put: 새 노드를 맨 앞에 붙이고 맵에 넣는다. 칸이 다 찼으면 tail 바로 앞 노드를 떼고 맵에서도 지운다. 노드에 키를 같이 적어 두는 이유가 이것이다.
• 머리·꼬리 보초(sentinel): 실제 값이 없는 head·tail 노드를 양 끝에 두면 “리스트가 비었나, 맨 앞인가” 같은 예외 처리가 사라진다.

LRU에도 약점이 있다. 한 번만 읽고 말 큰 파일을 훑으면(스캔) 자주 쓰던 것이 모두 밀려난다. 그래서 두 번 이상 쓴 것만 오래 두는 2Q·SLRU, 쓴 횟수를 세는 LFU, 둘을 저울질하는 ARC 같은 변형이 있다. 정확한 LRU는 요청마다 리스트를 고쳐야 해서, 아주 빠르거나 큰 곳에서는 흉내만 낸다.

• CPU 캐시: 묶음(set)마다 몇 비트만으로 대략의 순서를 기억하는 의사 LRU(pseudo-LRU)를 쓴다. 캐시 계층은 CPU 노트에 있다.
• 운영체제: 메모리가 모자라 페이지를 디스크로 내릴 때, 페이지마다 “최근에 쓰였나” 비트 하나만 두고 시계 바늘처럼 돌며 고르는 CLOCK 계열을 쓴다. 스왑은 RAM 노트에 있다.
• Redis: 키 전체를 줄 세우지 않고, 키 몇 개를 무작위로 뽑아 그중 가장 오래 안 쓴 것을 내보낸다(근사 LRU). 뽑는 수를 늘리면 진짜 LRU에 가까워지고 CPU를 더 쓴다.
• 언어 기본 기능: Python의 functools.lru_cache, Java의 LinkedHashMap(접근 순서 모드 + removeEldestEntry)이 바로 이 구조다.

Redis의 근사 방식과 정책별 차이는 Redis 문서의 Key eviction에, 여러 교체 정책의 비교는 Wikipedia의 Cache replacement policies에 있다.

문제 풀기 →Python 코드 →

스킵 리스트: 확률로 만드는 급행 차선

정렬된 연결 리스트는 넣고 빼기가 쉽지만 찾으려면 처음부터 하나씩 걸어야 한다(O(n)). 스킵 리스트(skip list)는 그 위에 듬성듬성한 리스트를 몇 층 더 쌓는다. 맨 아래층은 모든 노드를, 그 위층은 대략 절반을, 또 그 위층은 다시 절반을 잇는다. 지하철의 급행과 완행처럼 위층에서 멀리 건너뛰다가 내려와 촘촘하게 찾는다.

• 층 정하기: 새 노드를 넣을 때 동전을 던져 앞면이 나오는 동안 한 층씩 올린다. 그러면 층마다 노드가 대략 절반씩 줄어 층 수가 평균 log₂ n이 되고, 한 층에서 걷는 거리도 평균 두어 칸이다.
• 복잡도: 찾기·넣기·빼기가 평균 O(log n), 공간은 평균 O(n)이다(노드당 평균 2층). 최악은 O(n)이지만 동전이 계속 한쪽만 나와야 하므로 확률이 극히 작다.
• 균형 트리와 비교: 같은 O(log n)인 트리 노트의 균형 이진 탐색 트리는 회전으로 모양을 고쳐야 하지만, 스킵 리스트는 넣을 자리 앞뒤 포인터만 바꾼다. 구현이 짧고, 여러 스레드가 동시에 고치는 잠금 없는(lock-free) 구현을 만들기도 쉽다. 대신 포인터가 많아 메모리를 더 쓰고 캐시 효율은 배열 기반 구조보다 떨어진다.
• 쓰임: Redis의 정렬 집합(sorted set)이 해시 테이블과 함께 스킵 리스트를 쓴다. LevelDB·RocksDB는 디스크에 쓰기 전 메모리 버퍼(memtable)를, Java는 ConcurrentSkipListMap을 이것으로 만든다.

층을 무작위로 정해도 왜 평균이 보장되는지는 Wikipedia의 Skip list 문서에 정리돼 있다.

문제 풀기 →Python 코드 →

HyperLogLog: 적은 메모리로 개수 어림하기

“오늘 방문한 서로 다른 사용자 수”처럼 중복을 뺀 개수(카디널리티, cardinality)를 정확히 세려면 본 값을 모두 집합에 담아야 한다. 값이 수억 개면 메모리도 그만큼 든다. HyperLogLog는 몇 KB만 쓰고 개수를 몇 % 오차로 어림한다.

직관은 동전 던지기다. 동전을 던져 앞면이 처음 나올 때까지 뒷면이 몇 번 이어졌는지 적는다고 하자. 뒷면이 다섯 번 이어지는 일은 32번에 한 번꼴이다. 그런 기록을 봤다면 대략 32번쯤은 던졌을 것이다. 값마다 해시를 구하면 그 비트가 동전 던지기 결과처럼 고르게 섞이므로, “첫 1이 나오기 전까지 이어진 0의 개수”의 최댓값이 본 값의 개수를 알려 준다. 같은 값은 해시도 같으니 중복은 저절로 무시된다.

• 통을 여럿 두는 이유: 최댓값 하나는 운에 크게 흔들린다. 해시의 앞 비트로 값을 m개의 통에 나누고, 통마다 최댓값을 따로 들고, 통들의 추정을 조화 평균으로 합친다. 오차는 대략 1.04/√m이다.
• 메모리: 통 하나에 작은 숫자(최대 rank) 하나뿐이다. Redis는 통 16384개를 약 12 KB에 담고 표준 오차 0.81%를 낸다. 값이 몇 개든 크기가 늘지 않는다.
• 합치기: 두 HyperLogLog의 통마다 큰 쪽을 고르면 합집합의 HyperLogLog가 된다. 서버마다 따로 세고 나중에 합칠 수 있다. 교집합은 이렇게 바로 구하지 못한다.
• 작은 개수 보정: 값이 적으면 빈 통이 많아 식이 틀어진다. 그때는 빈 통의 비율로 세는 방법(linear counting)으로 바꾼다. 비슷한 생각의 확률적 자료구조로 해시 노트의 블룸 필터가 있다.

분석과 보정식은 Flajolet 등의 원 논문(2007)에, 실무 명령과 오차는 Redis의 PFCOUNT 문서에 있다.

문제 풀기 →Python 코드 →

P와 NP: 확인은 쉬운데 풀기도 쉬울까

지금까지의 알고리즘은 대부분 n², n log n처럼 입력 크기의 다항식 시간에 끝난다. 이렇게 다항 시간에 풀리는 예·아니오 문제(결정 문제)의 모임이 P다. 그런데 오랫동안 아무도 다항 시간 풀이를 찾지 못한 문제들이 있다. 이들의 공통점은 답을 찾기는 어려워 보여도 누가 답을 건네주면 확인하기는 쉽다는 것이다. 답 후보(증거, certificate)를 다항 시간에 확인할 수 있는 결정 문제의 모임이 NP다.

빨리 풀 수 있으면 확인도 빠르니 P는 NP 안에 있다. 거꾸로 확인이 빠른 문제는 모두 빨리 풀 수도 있을까, 곧 P = NP인가가 컴퓨터 과학에서 가장 유명한 미해결 문제다. 클레이 수학 연구소가 2000년에 정한 밀레니엄 문제 일곱 개 중 하나로, 풀면 상금 100만 달러가 걸려 있다. 대부분의 연구자는 P ≠ NP라고 믿지만 증명은 없다.

• 환원(reduction): 문제 A의 입력을 다항 시간에 문제 B의 입력으로 바꿔 B의 답으로 A를 풀 수 있으면, B는 A만큼은 어렵다. 어려움을 비교하는 자다.
• NP-완전(NP-complete): NP에 속하면서 NP의 모든 문제가 그것으로 환원되는 문제다. 1971년 쿡(Cook)이 논리식 만족 문제(SAT)가 그렇다는 것을 보였고, 이듬해 카프(Karp)가 그래프 색칠, 정점 덮개, 배낭 등 21개 문제가 모두 같은 무리임을 환원으로 보였다.
• NP-난해(NP-hard): NP의 모든 문제가 환원되기만 하면 되고 NP에 속할 필요는 없다. 외판원 문제의 “가장 짧은 경로를 내놓아라”는 최적화 버전이나 정지 문제가 여기 있다.
• 실무에서의 뜻: 문제가 NP-완전이라고 포기할 필요는 없다. 입력이 작거나, 특별한 구조가 있거나(트리 모양 그래프 등), 최적이 아니어도 되면 풀린다. SAT 풀이기는 변수가 수백만 개인 실제 문제(회로 검증, 패키지 의존성 풀기)를 일상적으로 푼다. 최악이 지수일 뿐이다.
• 암호와의 관계: 소인수분해처럼 공개 키 암호가 기대는 문제는 NP에 속한다. P = NP가 실용적인 알고리즘과 함께 증명되면 이런 암호의 바탕이 흔들린다. 다만 소인수분해가 NP-완전인지는 모른다.
• 이름의 오해: NP는 "다항 시간이 아님"(non-polynomial)이 아니라 비결정적 다항 시간(nondeterministic polynomial time)의 줄임말이다. P도 NP 안에 든다. 정지 문제와 NP-완전을 둘러싼 다른 흔한 오해는 계산 이론 노트에 모았다.

문제 정의와 상금 규정은 Clay Mathematics Institute의 P vs NP 페이지에, NP-완전 문제의 목록과 증명의 흐름은 Wikipedia의 NP-completeness에 있다.

문제 풀기 →Python 코드 →

근사 알고리즘: 최적은 못 해도 얼마나 가까운지는 보장한다

NP-난해한 최적화 문제는 최적해를 빨리 구할 수 없다고 봐야 한다. 근사 알고리즘(approximation algorithm)은 다항 시간에 끝나면서, 답이 최적의 몇 배 안에 든다는 것을 증명으로 보장한다. “대개 좋은 답을 낸다”는 경험 규칙(휴리스틱)과 다른 점이 이 보장이다.

정점 덮개(vertex cover)는 모든 간선이 적어도 한쪽 끝에 고른 정점을 갖도록 정점을 가장 적게 고르는 문제다. 감시 카메라를 길목(정점)에 두어 모든 길(간선)을 보게 하는 문제와 같다. 2-근사 알고리즘은 아주 단순하다. 간선을 차례로 보며 양 끝이 모두 안 골라진 간선을 만나면 두 끝을 다 고른다.

• 증명의 틀: 최적값을 모르니 최적값의 하한(여기서는 고른 간선 수)을 찾고, 내 답이 그 하한의 몇 배인지 보인다. 근사 비율 증명은 거의 다 이 모양이다.
• 다른 예: 집합 덮개는 “아직 안 덮인 것을 가장 많이 덮는 집합”을 고르는 탐욕으로 약 ln n배 안에 든다. 거리가 삼각 부등식을 지키는 외판원 문제는 최소 신장 트리로 2배, 크리스토피데스 알고리즘으로 1.5배 안의 경로를 낸다. 배낭 문제는 오차 ε을 원하는 만큼 줄일 수 있다(대신 시간이 1/ε에 따라 는다).
• 한계: 일반 외판원 문제는 P ≠ NP라면 어떤 상수 배의 근사도 불가능하다. 정점 덮개도 2보다 확실히 좋은 상수 비율은 아직 아무도 찾지 못했다. 문제마다 근사가 되는 정도가 다르다.
• 쓰임: 배송 경로, 기지국 배치, 작업 배정처럼 정확한 최적보다 “충분히 좋은 답을 제때”가 중요한 곳이다. 실무에서는 근사 알고리즘의 답을 출발점으로 삼아 국소 탐색으로 더 다듬는 경우가 많다.

탐욕법과 동적 계획법이 근사에서 어떻게 쓰이는지는 설계 기법 노트에, 정점 덮개의 다른 근사와 한계는 Wikipedia의 Vertex cover에 있다.

문제 풀기 →Python 코드 →