[분산시스템] 분산 시스템 개념 정리

분산 시스템  AI 인프라, 컨센서스, RDMA, 벡터 DB, 폴트 톨러런스

한 학기 동안 배운 분산 시스템 핵심 개념들을 정리했다.
AI 인프라/LLM 서빙부터 시작해서 컨센서스(Paxos), 분산 락, RDMA, 분산 벡터 데이터베이스, 폴트 톨러런스까지 — 최근 연구(vLLM, ShiftLock, DiskANN)까지 포함해서 정리해봤다.

 

 

 

---

 

1. AI 인프라 & LLM 서빙 시스템

1-1. 메모리 월(Memory Wall)

GPU 컴퓨팅 코어 성능은 지난 10년간 약 80배 증가했지만, 메모리 대역폭은 17배밖에 늘지 않았다. 연산 속도는 빨라졌는데 데이터를 옮기는 속도가 따라오지 못하면서 GPU 코어가 유휴 상태에 빠지는 문제가 생긴다. 이를 해결하기 위해 등장한 것이 HBM(High Bandwidth Memory)이다.

HBM은 GPU 바로 옆에 붙은 초고속 대용량 메모리로, 일반 GDDR(12~20GB) 대비 40~80GB 수준의 용량을 제공한다. 특히 KV 캐시처럼 메모리를 많이 요구하는 LLM 서빙 워크로드에서 HBM의 중요성은 점점 커지고 있다.

 

1-2. 프리필(Prefill) vs 디코드(Decode)

LLM이 답변을 생성하는 과정은 크게 두 단계로 나뉜다.

구분	프리필(Prefill)	디코드(Decode)
역할	프롬프트를 읽고 답변 생성 준비	실제 토큰을 하나씩 생성
특징	컴퓨트 바운드, 상대적으로 느림	토큰 단위로 순차 생성
관련 지표	TTFT	TPOT

• TTFT(Time To First Token): 첫 토큰이 생성되기까지 걸리는 시간. 프리필 단계의 속도에 좌우된다.
• TPOT(Time Per Output Token): 토큰 하나가 생성되는 데 걸리는 시간. 디코드 단계의 속도에 좌우된다.

둘 다 값이 작을수록 좋고, 스루풋(초당 처리 토큰 수)은 클수록 좋다.

 

1-3. 왜 KV 캐시가 필요한가

 

LLM은 다음 토큰을 생성할 때 이전에 생성한 모든 토큰을 입력에 누적해서 다시 넣어야 한다.

"안" 생성 → "안" 처리 → "녕" 생성 → "안녕" 처리 → "하" 생성 → ...

 

문제는 이미 처리가 끝난 토큰을 매번 다시 처리한다는 점이다. 5만 단어짜리 문서를 생성한다면 마지막 단어를 만들기 위해 앞선 49,999개의 단어를 또 처리해야 하는 셈이다. 이는 명백한 GPU 자원 낭비다.

KV 캐시는 이미 처리한 토큰의 연산 결과를 메모리에 저장해두고, 다음 토큰 생성 시 재사용하는 방식으로 이 문제를 해결한다. 다만 컨텍스트가 길어질수록  KV 캐시 자체가 수십 GB에 달하는 메모리를 요구하게 되는데, 이것이 HBM이 중요해지는 핵심 이유이기도 하다.

이때 트랜스포머가 "병렬 처리"를 한다고 해서 토큰 생성 순서 자체가 바뀌는 건 아니다. 텍스트는 여전히 한 토큰씩 순차적으로 생성된다. 트랜스포머가 바꾼 것은 내부 연산을 병렬화해서 생성에 걸리는 "시간"을 단축한 것이다. 즉 "순서는 그대로, 처리 속도만 빨라진 것"으로 이해해야 한다.

 

1-4. vLLM  

초기 LLM 서빙 시스템은 GPU 메모리 관리가 비효율적이어서 심각한 프래그멘테이션 문제를 겪었다. vLLM은 OS가 수십 년간 발전시켜온 페이징(Paging) 기법을 GPU의 KV 캐시 관리에 그대로 적용해 이 문제를 해결했다.

2023년 SOSP(시스템 분야 최상위 컨퍼런스)에서 발표됐고, 처리량을 기존 대비 2~4배 향상시켰다. 현재는 사실상 AI 서빙 백엔드의 표준으로 자리 잡았다.

 

1-5. MoE(Mixture of Experts)의 두 가지 장점

MoE는 모델 전체를 하나의 GPU에 올리는 대신, 모델을 여러 "엑스퍼트"로 쪼개서 여러 GPU에 분산 배치하는 방식이다.

1. 메모리 분산 가능: 단일 GPU의 메모리 한계를 초과하는 대형 모델도 운용할 수 있다.
2. 연산량 감소: 입력 토큰에 적합한 일부 엑스퍼트만 활성화되므로, 전체 모델 대비 훨씬 적은 연산으로 처리가 가능하다. 예를 들어 10개 엑스퍼트 중 1개만 동작한다면 연산량이 10분의 1로 줄어든다.

MoE는 결국 로드 밸런싱/라우팅 문제와 동일한 구조를 갖는다. 어떤 토큰을 어떤 엑스퍼트(=어떤 GPU)로 보낼지 결정하는 게이팅 라우터는 네트워크 스위치의 패킷 포워딩과 매우 닮아있다.

 

1-6. AI 에이전트 시대, CPU가 다시 중요해진 이유

 

기존 AI 워크로드는 학습과 추론 모두 GPU 중심이었다. 그런데 Claude Code, Codex 같은 AI 에이전트 시대가 오면서 상황이 달라졌다. 에이전트는 단순 추론만 하는 게 아니라 웹 데이터를 다운로드하고 분석하는 등의 부수 작업을 수행하는데, 이런 작업은 GPU가 아니라 CPU가 처리한다. 문제는 CPU 성능 자체는 지난 수년간 거의 발전하지 않았다는 점이다. 그래서 결국 CPU 사용량 자체를 줄이는 것이 중요해졌고, 이것이 RDMA가 오늘날 데이터센터 인프라에서 주목받는 핵심 배경이다.

 

---

 

 

2. 컨센서스(Consensus)

2-1. 로지컬 클락

분산 시스템에는 글로벌 클락이 존재하지 않는다. 모든 노드의 시계가 완벽히 동기화될 수 없기 때문에, 이벤트의 순서를 정하기 위해 로지컬 클락을 사용한다.

• 램포트 클락: max(로컬 카운터, 수신된 타임스탬프) + 1로 갱신. 전체 순서(Total Order)는 제공하지만 동시에 발생한 이벤트를 구분하지 못한다.
• 벡터 클락: 노드 수만큼의 벡터로 클락을 관리해서, 동시 발생(Concurrent) 이벤트까지 구분할 수 있다.

 

2-2. 컨센서스의 3속성

Validity (유효성)	결정된 값은 반드시 누군가가 제안한 값이어야 함
Termination (종료성)	모든 정상 노드는 반드시 결정을 내려야 함
Integrity (무결성)	한 번 결정한 값은 번복할 수 없음

 

2-3. FLP Impossibility

 

"비동기 시스템에서 단 하나의 프로세스가 크래시하더라도 컨센서스를 완벽하게 보장하는 것은 불가능하다." (Fischer, Lynch, Patterson, 1985)

비동기 시스템에서는 메시지 딜레이와 프로세스 크래시를 구분할 수 없기 때문이다. 실제 시스템에서는 무한 대기 대신 타임아웃을 도입해 이 문제를 우회한다.

 

2-4. Paxos

1단계: Prepare / Promise

Proposer가 고유한 번호 n으로 Prepare 메시지를 브로드캐스트한다. Acceptor는 n이 자신이 본 번호 중 가장 크면 Promise를 보낸다. 이때 이전에 수락했던 값(na, va)이 있다면 함께 회신한다.

 

2단계: Accept / Accepted

Proposer가 사용할 값 v를 결정하는 규칙이 핵심이다.

• Promise 응답 중 이전 수락값이 있으면 → na가 가장 높은 va를 사용 (기존 컨센서스 보호)
• Promise 응답이 전부 null이면 → Proposer 자신이 원래 제안하려던 값 사용

과반수 Acceptor가 Accept하면 값이 확정되고, f개의 장애를 허용하려면 최소 2f+1개의 Acceptor가 필요하다.

Multi-Paxos & Raft: Multi-Paxos는 안정적인 리더를 미리 선출해서 Phase 1을 생략하고 Phase 2만 반복하는 최적화 버전이다. Raft는 여기서 더 나아가 Paxos를 단순화한 알고리즘으로, 리더-팔로어 구조와 하트비트 기반 리더 선출을 사용한다.

 

2-5. 쿼럼 시스템 — R + W > N

• R = 읽기 정족수, W = 쓰기 정족수, N = 전체 노드 수

R + W > N이 성립하면 읽기 집합과 쓰기 집합 사이에 반드시 겹치는 노드가 존재한다는 것이 수학적으로 보장된다. 이 겹치는 노드는 항상 최신값을 가지고 있으므로, 읽기 작업이 구버전 데이터를 반환하지 않도록 보장한다. 반대로 R + W ≤ N이면 겹치는 노드가 없을 수 있어 구버전을 읽을 위험이 생긴다.

 

---

 

3. 분산 락(Distributed Lock)

3-1. 락의 세 가지 프로퍼티

Safety	최대 하나의 프로세스만 락을 소유할 수 있음
Liveness	락을 요청한 모든 프로세스는 언젠가는 반드시 획득함
Fairness	요청이 합리적인 순서로 승인됨 (엄격한 순서는 아님)

 

3-2. 분산 락이 어려운 세 가지 이유

1. 네트워크 페일러: 메시지가 100% 전달된다는 보장이 없다.
2. 클락 스큐: 글로벌 클락이 없어 요청 순서를 명확히 판단하기 어렵다.
3. 프로세스 크래시: 락 홀더가 크래시하면 락이 영원히 풀리지 않는 "락 스턱" 문제가 발생한다.

 

3-3. 해결 방법들

• 센트럴라이즈드 락 서비스: 단순하지만 단일 장애점(SPOF) 문제가 있다.
• 램포트 알고리즘: 브로드캐스트 기반이라 n-1개의 메시지가 필요해 비효율적이다.
• 리스(Lease)/TTL: 일정 시간이 지나면 자동으로 락이 해제되어 크래시 문제를 완화한다.
• 레드락(Redlock): 쿼럼 기반으로 과반수 동의만 받으면 락을 획득한 것으로 간주한다.
• 리더-라이터 락: 읽기는 공유(Shared) 가능, 쓰기는 독점(Exclusive)으로 처리해 처리량을 높인다.

 

---

4. RDMA & 아토믹 연산

 

4-1. RDMA가 빠른 이유

RDMA(Remote Direct Memory Access)는 상대방의 커널과 CPU를 거치지 않고 NIC가 직접 원격 메모리에 접근하는 기술이다. 전통적인 TCP/IP 방식이 약 100마이크로초의 레이턴시를 갖는 반면, RDMA는 약 1~2마이크로초로 약 50배 빠르다. (로컬 메모리 접근보다는 여전히 느리지만, 분산 시스템 메시징 측면에서는 압도적인 속도다.)

4-2. One-sided vs Two-sided RDMA

구분	One-sided	Two-sided
CPU 개입	없음	있음
연산	Read / Write / CAS / FA	Send / Receive
특징	상대방 CPU가 메시지 수신을 모름	상대방이 수신을 인식 가능

 

4-3. CAS와 FA — 원자성 연산

• CAS(Compare-And-Swap): *addr == old이면 new로 교체. 락 획득에 사용된다. CAS(락변수, 0, 1)은 락변수가 0(미점유)이면 1로 바꿔 락을 획득한다.
• FA(Fetch-And-Add): 현재 값을 반환한 후 원자적으로 더한다. 카운터나 리더-라이터 락의 리드 카운트에 사용된다.

둘 다 읽기-계산-쓰기가 중간에 끊기지 않는 원자성(Atomicity) 연산이다. RDMA 환경에서는 NIC가 CPU 개입 없이 원격 메모리에서 직접 이 연산을 수행할 수 있다.

---

 

 

5. ShiftLock — RDMA 기반 분산 락 매니저

 

Shift lock은  RDMA 기반 락 매니저가 가진 근본적인 문제를 해결한 연구다.

5-1. 문제: 락 컨텐션 시 스루풋 급락

전통적인 CPU 기반 락 매니저는 CPU가 모든 요청을 순서대로 인지하는 글로벌 뷰를 가지고 있어서, 락이 점유 중이면 요청을 웨이트 큐에 줄 세워 스케줄링할 수 있다. 반면 One-sided RDMA 기반 락 매니저는 CPU가 개입하지 않기 때문에 웨이트 큐 자체가 존재할 수 없다. 락 획득에 실패한 클라이언트는 그저 무한히 재시도할 수밖에 없다. 실험 결과 클라이언트가 240개로 늘어나자 스루풋이 94.4% 감소했고, 전체 요청의 85% 이상이 실패한 재시도였다.

 

 

5-2. 해결: MCS 락을 차용한 분산 웨이트 큐

ShiftLock의 핵심 아이디어는 "서버가 줄을 세워줄 수 없다면, 클라이언트들끼리 스스로 줄을 서자"는 것이다. 약 30년 전에 나온 MCS 락의 아이디어를 RDMA 환경에 접목했다.

 

락을 점유한 클라이언트는 릴리즈할 때 자기 뒤에서 대기 중인 클라이언트에게 직접 소유권을 넘겨준다(락 핸드오버). 각 클라이언트는 자기 바로 뒤의 차례만 알면 되므로, 전체 클라이언트를 알 필요가 없다. 흥미로운 점은 클라이언트 간 통신에 One-sided가 아닌 Two-sided RDMA를 사용한다는 것이다. One-sided RDMA는 상대방 CPU가 메시지 수신 여부를 알 수 없어 핸드오버 메시지를 전달할 방법이 없기 때문이다.

 

---

 

6. 분산 벡터 데이터베이스

6-1. KNN vs ANN

• KNN(K-Nearest Neighbor): 전체 데이터셋을 일일이 비교. Recall 100%지만 데이터가 많아지면 비현실적으로 느리다.
• ANN(Approximate Nearest Neighbor): "근사적 최근접 이웃 탐색". 약간의 오차를 허용하는 대신 속도를 비약적으로 높인다. 현재 벡터 검색의 사실상 표준이다.

Recall은 찾아야 할 정답 중 실제로 맞춘 비율을 의미한다. 예를 들어 정답 10개 중 9개를 맞췄다면 Recall은 90%다.

 

6-2. 벡터 인덱스 종류

PQ (Product Quantization)	벡터를 서브벡터로 압축	메모리 절약, 정확도 다소 하락
IVF (Inverted File Index)	K-means 클러스터링 후 센트로이드 비교	빠름, Recall은 상대적으로 낮음
HNSW	계층적 그래프, Coarse → Fine 탐색	속도와 Recall 모두 우수 → 현재 주류

 

그래프 기반 인덱스(HNSW)가 지배적인 이유는 단순하다. IVF는 빠르지만 Recall이 낮고, PQ는 메모리만 절약될 뿐이다. HNSW는 계층 구조 덕분에 속도와 정확도를 동시에 확보할 수 있다.

 

6-3. DiskANN — SSD를 활용한 빌리언 스케일 벡터 검색

 

데이터가 수십억 개 규모로 커지면 인메모리 방식으로는 감당이 안 된다. 예컨대 10억 개의 1536차원 벡터는 약 6TB에 달하는데, 일반 서버 메모리(128~256GB)로는 어림도 없다.

DiskANN(NeurIPS 2019)은 DRAM과 SSD의 역할을 분리해서 이 문제를 해결한다.

• DRAM에 저장: PQ로 압축된 벡터 + 그래프 토폴로지(이웃 정보) → 빠른 후보군 선별
• SSD에 저장: Full Vector(원본, FP32) + 4KB 페이지 정렬 레이아웃 → 정확한 거리 재계산

검색 흐름은 먼저 DRAM의 압축 벡터와 그래프로 후보 ID를 추리고, SSD에서 해당 노드의 원본 벡터를 한 번의 NVMe 읽기로 가져와 정밀하게 거리를 재계산하는 방식이다. 인덱스 구조로는 계층이 없는 단일 레이어 그래프인 Vamana Graph를 사용하며, HNSW 대비 약 1/10의 메모리로 빌리언 스케일 데이터를 처리할 수 있다.

 

6-4. 분산 벡터 검색의 두 가지 전략

• 로컬 샤딩: 서버별로 독립된 인덱스를 운용. 쿼리마다 모든 서버에 브로드캐스트하는 스캐터-게더 패턴이 필요해 비효율적이다.
• 글로벌 인덱스: 논리적으로는 하나의 인덱스지만 물리적으로는 여러 서버에 분산. 원격 노드 접근이 빈번하므로 RDMA를 활용한다.

---

7. 폴트 톨러런스(Fault Tolerance)

7-1. 에러 → 폴트 → 페일러

에러(사람의 실수) → 폴트(잘못된 결과 출력) → 페일러(외부에서 관측 가능한 이상 동작)

 

 

7-2. 폴트 톨러런스 vs 하이 어베일러빌리티

 

장애 후 상태	폴트 톨러런트	하이 어베일러블
성능 그대로 유지	✅	✅
성능 저하	❌	✅
완전 접속 불가	❌	❌

폴트 톨러런스는 장애가 발생해도 평상시와 완전히 동일하게작동하는 것을, 하이 어베일러빌리티는 어떤 식으로든 서비스가 돌아가기만 하는 것을 의미한다. 실무에서는 보통 하이 어베일러빌리티를 더 우선시한다. 느리더라도 작동하는 것과 아예 접속이 안 되는 것의 차이가 훨씬 크기 때문이다.

 

 

7-3. 페일러의 네 가지 종류

범위가 좁은 것부터 넓은 순서로:

1. 크래시 페일러: 서버가 완전히 멈춤. 가장 흔한 타입.
   • 페일 스톱(Fail-stop): 크래시 페일러 중에서도 주변 노드가 장애를 확실하게 감지할 수 있는 경우. (Crash Failure ⊃ Fail-stop 관계)
2. 오미션 페일러: 작동은 하지만 메시지 송수신이 실패함.
3. 타이밍 페일러: 송수신은 되지만 데드라인보다 너무 느림.
4. 비잔틴 페일러: 임의의 시간에 임의의(거짓) 메시지를 생성함.

 

7-4. 비잔틴 페일러와 블록체인

 

블록체인은 중앙 보증기관 없이 P2P 노드들이 거래의 진위를 보증하는 시스템이다. 비잔틴 페일러는 노드가 임의의 시점에 거짓 메시지(조작된 거래 정보)를 생성할 수 있는 상황을 의미하므로, 블록체인의 신뢰성에 직접적인 위협이 된다.

이를 해결하기 위해 블록체인은 다수결(컨센서스) 방식을 사용한다. 전체 노드의 과반수(51% 이상)가 동의해야만 거래가 확정되며, 악의적인 노드가 네트워크를 조작하려면 전 세계에 분산된 노드의 절반 이상을 장악해야 하는데 이는 현실적으로 매우 어렵다.

7-5. 페일 슬로우와 캐스케이딩 이펙트

페일 슬로우(Fail-slow)는 하드웨어가 기능적으로는 작동하지만 간헐적으로 성능이 저하되는 현상이다. 내부 원인으로는 펌웨어 버그, 외부 원인으로는 온도 상승(CPU 스로틀링), 진동, 전력 문제 등이 있다.

페일 슬로우를 탐지하기 어렵게 만드는 가장 큰 원인은 캐스케이딩 이펙트(Cascading Effect)다. 근본 원인과 실제로 관측되는 증상이 다르기 때문이다.

냉각 팬 고장 → 다른 팬이 풀 스피드로 회전
            → 진동 발생 → 디스크 성능 저하

 

운영자가 관측하는 것은 디스크 성능 저하이지만 실제 원인은 팬 고장이다. 디스크를 교체해도 같은 문제가 재발하며, 근본 원인을 역추적하기까지 수개월이 걸리기도 한다. 이 때문에 풀스택 모니터링을 통한 통계적 상관관계 분석이 중요하다.

 

---

 

 

분산 시스템은 한 학기 동안 배운 내용 중에서도 가장 최신 트렌드(AI 인프라, RDMA, 벡터 DB)와 깊게 연결된 과목이었다. 특히 vLLM, ShiftLock, DiskANN 같은 최신 연구들이 결국 OS나 네트워크 같은 기존 분산 시스템 개념(페이징, 컨센서스, 쿼럼)을 새로운 도메인에 재적용한 것이라는 점이 인상 깊었다.