대규모 시스템 설계 리드·아키텍트 코딩·알고리즘 면접
새 면접Q. 10억 개의 URL을 크롤링하는 분산 크롤러 시스템에서, 이미 방문한 URL인지 확인하기 위해 Bloom Filter를 사용하려고 합니다. 메모리는 10GB로 제한되어 있고, False Positive Rate는 1% 이하로 유지해야 합니다. Bloom Filter의 최적 파라미터(비트 배열 크기, 해시 함수 개수)를 어떻게 결정하겠으며, 시간·공간 복잡도는 어떻게 되나요?
Bloom Filter의 False Positive Rate 공식과 최적 해시 함수 개수 공식을 고려해보세요.
Bloom Filter의 비트 배열 크기 m은 m = -(n * ln(p)) / (ln(2)^2) 공식으로 계산하며, 여기서 n=10억, p=0.01이므로 약 9.6GB가 필요합니다. 최적 해시 함수 개수 k는 k = (m/n) * ln(2)로 계산하여 약 7개가 적합합니다. 삽입과 조회의 시간 복잡도는 O(k)로 상수 시간이며, 공간 복잡도는 O(m)입니다. False Positive는 발생할 수 있지만 False Negative는 없으므로, 의심스러운 경우 실제 DB를 확인하는 2단계 검증 로직을 추가해야 합니다. 분산 환경에서는 URL 해시값 기준으로 파티셔닝하여 각 노드가 독립적인 Bloom Filter를 관리하게 합니다.
- • 비트 배열 크기와 해시 함수 개수를 False Positive Rate 공식으로 계산
- • 시간 복잡도 O(k), 공간 복잡도 O(m)으로 메모리 효율적
- • 분산 환경에서는 URL 해시 기반 파티셔닝으로 각 노드가 독립 관리
대규모 크롤러, 캐시 시스템, 중복 제거 파이프라인에서 메모리 효율적인 존재 여부 확인에 사용됩니다.
Bloom Filter가 가득 차서 False Positive Rate가 증가하는 상황에서는 어떻게 대응하시겠습니까?
Q. 글로벌 서비스에서 5개 리전에 분산된 데이터센터 간 분산 락을 구현해야 합니다. Redlock 알고리즘과 Raft 기반 합의 알고리즘 중 어느 것을 선택하시겠으며, 각각의 시간 복잡도와 네트워크 파티션 상황에서의 동작 방식은 어떻게 다른가요?
CAP 이론과 네트워크 지연, 클럭 동기화 문제를 고려해보세요.
Redlock은 과반수 노드에서 락 획득에 성공하면 락을 얻는 방식으로 O(N) 시간 복잡도를 가지며, 네트워크 파티션 시 클럭 드리프트로 인해 안전성 문제가 발생할 수 있습니다. Raft는 리더 선출과 로그 복제를 통한 강한 일관성을 보장하며, 쿼럼 기반 합의로 O(N) 복잡도이지만 네트워크 파티션 시에도 과반수 노드가 있는 파티션에서만 쓰기를 허용해 안전성을 보장합니다. 글로벌 서비스에서는 높은 네트워크 지연과 파티션 가능성을 고려해 Raft 기반 솔루션(etcd, Consul)을 선택하며, 각 리전에 Raft 클러스터를 두고 리전 간에는 최종 일관성을 허용하는 하이브리드 구조를 권장합니다. 락 타임아웃은 네트워크 RTT의 10배 이상으로 설정하여 오작동을 방지합니다.
- • Redlock은 클럭 드리프트 취약성, Raft는 강한 일관성 보장
- • 둘 다 O(N) 복잡도지만 네트워크 파티션 시 안전성이 다름
- • 글로벌 환경에서는 리전별 Raft 클러스터 + 리전 간 최종 일관성 구조 권장
분산 환경에서 중복 실행 방지, 리더 선출, 크리티컬 섹션 보호가 필요한 배치 작업이나 스케줄러에 사용됩니다.
Raft 클러스터에서 리더가 자주 변경되어 가용성이 떨어지는 상황을 어떻게 진단하고 해결하시겠습니까?
Q. 실시간으로 유입되는 무한 스트림 데이터에서 상위 K개의 빈도수가 높은 항목을 추적하는 시스템을 설계해야 합니다. 메모리는 제한적이고 데이터는 초당 100만 건씩 들어옵니다. Count-Min Sketch와 Min Heap을 조합한 알고리즘의 시간·공간 복잡도를 분석하고, 정확도를 높이기 위한 개선 방안을 제시하세요.
스트림 데이터에서는 모든 항목을 저장할 수 없으므로 확률적 자료구조를 활용해야 합니다.
Count-Min Sketch는 d개 해시 함수와 w개 카운터로 구성되어 O(d) 시간에 빈도수를 추정하며, 공간 복잡도는 O(d*w)로 메모리 효율적입니다. Min Heap은 상위 K개 항목을 유지하며 삽입/삭제가 O(log K)입니다. 전체 알고리즘은 각 항목마다 O(d + log K) 시간 복잡도로 처리되며, 공간 복잡도는 O(d*w + K)입니다. 정확도 개선을 위해 Conservative Update 방식을 적용하여 카운터 증가 시 최소값만 업데이트하고, Heavy Hitter Detection을 위해 Lossy Counting이나 Space Saving 알고리즘을 병행합니다. 분산 환경에서는 각 노드에서 로컬 Top-K를 계산한 후 중앙에서 병합하는 2단계 집계를 수행합니다.
- • Count-Min Sketch O(d*w) 공간으로 빈도수 추정, Min Heap O(K)로 상위 K개 유지
- • 전체 시간 복잡도 O(d + log K), 공간 복잡도 O(d*w + K)
- • Conservative Update와 Heavy Hitter Detection으로 정확도 개선
실시간 트렌딩 토픽 분석, 인기 검색어 추출, DDoS 공격 탐지에서 메모리 제약 하에 빈도 분석이 필요할 때 사용됩니다.
데이터 분포가 Zipf 법칙을 따르는 경우와 균등 분포인 경우, 알고리즘 파라미터를 어떻게 다르게 조정하시겠습니까?
Q. 소셜 네트워크에서 10억 명의 사용자와 1000억 개의 친구 관계가 있을 때, 두 사용자 간 최단 경로를 찾는 기능을 구현해야 합니다. 단순 BFS는 메모리와 시간이 과도하게 소요됩니다. Bidirectional BFS와 그래프 파티셔닝을 활용한 접근법의 시간·공간 복잡도를 분석하고, 6 Degrees of Separation 특성을 어떻게 활용할 수 있나요?
양방향 탐색과 그래프의 작은 세상 특성을 고려하면 탐색 공간을 크게 줄일 수 있습니다.
일반 BFS는 O(V+E) 시간, O(V) 공간 복잡도를 가지지만, Bidirectional BFS는 양쪽에서 동시에 탐색하여 O(b^(d/2))로 지수적 개선을 이룹니다(b는 분기계수, d는 깊이). 소셜 네트워크의 평균 경로 길이가 6이라면 탐색 노드 수를 b^6에서 2*b^3으로 대폭 줄일 수 있습니다. 그래프 파티셔닝은 커뮤니티 탐지 알고리즘(Louvain, Label Propagation)으로 밀집된 서브그래프를 식별하고, 같은 파티션 내부를 우선 탐색한 후 경계 노드를 통해 다른 파티션으로 확장합니다. 공간 복잡도는 O(2*b^(d/2) + P)로 P는 파티션 메타데이터입니다. 실무에서는 자주 조회되는 경로를 캐싱하고, 인플루언서 같은 허브 노드를 인덱싱하여 추가 최적화합니다.
- • Bidirectional BFS로 시간 복잡도를 O(b^d)에서 O(b^(d/2))로 지수적 개선
- • 그래프 파티셔닝으로 커뮤니티 내부 우선 탐색하여 검색 공간 축소
- • 6 Degrees 특성으로 평균 경로 길이가 짧아 실용적 성능 확보
소셜 네트워크의 친구 추천, LinkedIn의 연결 경로 표시, 네트워크 라우팅 최적화에 사용됩니다.
그래프가 동적으로 변경되는 환경에서 파티션 재구성의 비용을 어떻게 최소화하시겠습니까?
Q. 수백만 개의 센서에서 수집된 시계열 데이터를 압축 저장해야 합니다. 원본 데이터 대비 10분의 1 크기로 줄이되, 쿼리 시 허용 오차 범위 내에서 근사값을 제공해야 합니다. Piecewise Aggregate Approximation과 Symbolic Aggregate Approximation의 시간·공간 복잡도를 비교하고, 각각 어떤 쿼리 패턴에 적합한지 설명하세요.
시계열 데이터의 트렌드 보존과 패턴 매칭 요구사항을 고려해보세요.
PAA는 시계열을 N개 구간으로 나누어 각 구간의 평균값으로 표현하며, 압축 시간 복잡도는 O(n), 공간 복잡도는 O(N)으로 n/N 배 압축됩니다. 쿼리 시 O(N) 시간에 근사값을 복원하며, 범위 쿼리와 트렌드 분석에 적합합니다. SAX는 PAA 결과를 알파벳 심볼로 이산화하여 O(n) 시간에 압축하고, 공간은 O(N*log(a))입니다(a는 알파벳 크기). 심볼 기반 인덱싱으로 O(log N) 시간에 패턴 매칭이 가능하며, 유사 패턴 검색과 이상 탐지에 유리합니다. 실무에서는 정밀도가 중요한 집계 쿼리에는 PAA를, 패턴 인식이 중요한 모니터링에는 SAX를 선택하며, 두 방식을 계층적으로 조합하여 사용하기도 합니다. 압축률과 정확도는 트레이드오프 관계이므로 도메인 특성에 맞게 파라미터를 조정합니다.
- • PAA는 O(N) 공간으로 평균 기반 압축, 범위 쿼리와 트렌드 분석에 적합
- • SAX는 심볼화로 O(N*log(a)) 공간, 패턴 매칭과 이상 탐지에 유리
- • 쿼리 패턴에 따라 선택하거나 계층적 조합 사용
IoT 센서 데이터 저장, 모니터링 메트릭 압축, 금융 시계열 분석에서 스토리지 비용 절감과 쿼리 성능을 동시에 확보할 때 사용됩니다.
압축된 데이터에서 직접 쿼리 처리가 가능한 경우와 불가능한 경우를 구분하고, 불가능한 경우 어떻게 대응하시겠습니까?
Q. 1PB 규모의 로그 데이터를 타임스탬프 기준으로 정렬해야 합니다. 단일 서버 메모리는 64GB이고, 1000대의 서버를 사용할 수 있습니다. External Sort와 분산 샘플링 기반 파티셔닝을 조합한 알고리즘의 I/O 복잡도와 네트워크 복잡도를 분석하고, 데이터 스큐 문제를 어떻게 해결하시겠습니까?
디스크 I/O와 네트워크 전송이 병목이므로, 데이터 이동을 최소화하는 전략이 필요합니다.
먼저 각 서버에서 로컬 데이터를 External Sort로 정렬하며, 이는 O((n/k)*log(n/k)) 시간과 O(n/k*log(M)) I/O 복잡도를 가집니다(k는 서버 수, M은 메모리). 분산 샘플링으로 각 서버에서 s개 샘플을 추출해 전역 정렬 후 k-1개 피벗을 결정하며, 이는 O(s*k*log(s*k)) 시간입니다. 피벗 기준으로 데이터를 파티셔닝하여 각 서버로 전송하면 네트워크 복잡도는 O(n)이지만, 데이터 스큐가 있으면 특정 서버에 부하가 집중됩니다. 스큐 해결을 위해 샘플 크기를 늘리거나(adaptive sampling), 오버샘플링 후 히스토그램 기반으로 불균형 파티션을 분할하며, 최종적으로 각 서버에서 로컬 정렬 후 순차적으로 결과를 병합합니다. 전체 I/O는 O(n*log(n/k) / B)이며 B는 블록 크기입니다.
- • External Sort로 로컬 정렬 후 샘플링 기반 글로벌 파티셔닝
- • I/O 복잡도 O(n*log(n/k)/B), 네트워크 복잡도 O(n)
- • 데이터 스큐는 adaptive sampling과 히스토그램 기반 파티션 분할로 해결
대용량 로그 분석, 데이터 웨어하우스 ETL, MapReduce 프레임워크의 Shuffle 단계에서 사용됩니다.
정렬 중 일부 서버가 장애를 일으키는 경우, 체크포인팅과 재시작 전략을 어떻게 설계하시겠습니까?
Q. CDN 엣지 서버에서 동영상 청크를 캐싱하는데, LRU는 큰 파일에 의해 작은 인기 파일이 밀려나는 문제가 있고, LFU는 과거 인기 항목이 계속 남아있는 문제가 있습니다. 파일 크기와 접근 빈도, 최근성을 모두 고려하는 캐시 교체 알고리즘을 설계하고, 각 연산의 시간 복잡도와 구현 시 필요한 자료구조를 설명하세요.
여러 요소를 가중합으로 계산하는 스코어링 방식과, 효율적인 우선순위 관리 방법을 생각해보세요.
Greedy-Dual-Size-Frequency 알고리즘을 기반으로, 각 항목에 스코어 H = (frequency * cost) / size * decay_factor를 부여하며, cost는 네트워크 비용, decay_factor는 시간 경과에 따른 감쇠입니다. Min Heap으로 스코어가 가장 낮은 항목을 O(log n) 시간에 찾아 교체하고, HashMap으로 O(1) 시간에 항목을 조회합니다. 접근 시마다 frequency를 증가시키고 스코어를 재계산하여 Heap을 업데이트하는데, lazy update 방식으로 교체 시점에만 재계산하면 평균 O(1) 시간입니다. 주기적으로 모든 항목의 frequency를 감쇠시켜 과거 인기 항목이 영구 캐싱되는 것을 방지하며, 이는 백그라운드 작업으로 O(n) 시간에 수행합니다. 공간 복잡도는 O(n)이며, 파라미터 튜닝으로 workload 특성에 맞게 최적화합니다.
- • 크기, 빈도, 최근성을 반영한 스코어 기반 교체 정책
- • Min Heap O(log n)과 HashMap O(1) 조합으로 효율적 구현
- • 주기적 감쇠로 과거 인기 항목의 영구 캐싱 방지
CDN 엣지 캐싱, 프록시 서버, 브라우저 캐시에서 다양한 크기의 콘텐츠를 효율적으로 관리할 때 사용됩니다.
캐시 히트율을 모니터링하면서 실시간으로 알고리즘 파라미터를 자동 조정하는 방법을 제안해주세요.
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!