Spring 시니어 CS 기초 면접
새 면접Q. 대용량 실시간 검색어 순위 시스템을 설계한다고 가정합니다. 매초 수백만 건의 검색어가 입력되고, 상위 100개의 검색어를 실시간으로 집계해야 합니다. 이 문제를 효율적으로 해결하기 위해 어떤 자료구조를 조합해서 사용할 것인지, 그리고 시간 복잡도 관점에서 왜 그 선택이 최적인지 설명해주세요.
빈도 추적과 상위 K개 추출을 분리해서 생각해보세요. 각각에 최적화된 자료구조가 있습니다.
HashMap과 Min Heap을 조합하여 사용합니다. HashMap으로 각 검색어의 빈도를 O(1)에 추적하고, 크기 100인 Min Heap으로 상위 100개를 유지합니다. 새로운 검색어가 들어올 때 HashMap을 업데이트하고, 해당 검색어의 빈도가 Heap의 최소값보다 크면 교체합니다. 이 방식은 삽입 O(1), 상위 K개 유지 O(log K)로 효율적입니다. 실시간 조회 시에는 Heap을 정렬하여 O(K log K)에 결과를 반환할 수 있습니다. 대안으로 Count-Min Sketch 같은 확률적 자료구조를 사용하면 메모리를 더 절약할 수 있지만 정확도를 일부 희생합니다.
- • HashMap으로 빈도 카운팅 O(1)
- • Min Heap으로 상위 K개 유지 O(log K)
- • 메모리와 정확도 트레이드오프 고려
실시간 트렌딩 토픽, 인기 상품 랭킹, 이상 탐지 시스템에서 빈도 기반 집계가 필요한 모든 상황에 적용됩니다.
만약 분산 환경에서 여러 서버에 검색 요청이 분산되어 있다면, 전체 시스템의 Top 100을 어떻게 집계하시겠습니까?
Q. TCP의 혼잡 제어(Congestion Control) 알고리즘 중 Slow Start, Congestion Avoidance, Fast Retransmit, Fast Recovery의 동작 원리와 각 단계 간 전환 조건을 설명해주세요. 특히 cwnd(congestion window)와 ssthresh(slow start threshold)가 어떻게 변화하는지 포함해 설명해주세요.
패킷 손실 감지 방법(타임아웃 vs 3 duplicate ACKs)에 따라 다르게 동작합니다.
Slow Start는 cwnd를 1 MSS에서 시작해 ACK마다 지수적으로 증가시키며, cwnd가 ssthresh에 도달하면 Congestion Avoidance로 전환됩니다. Congestion Avoidance는 cwnd를 RTT마다 선형적으로 1 MSS씩 증가시킵니다. 3개의 duplicate ACK를 받으면 Fast Retransmit이 동작해 해당 패킷을 즉시 재전송하고, ssthresh를 cwnd/2로 설정한 뒤 Fast Recovery로 전환됩니다. Fast Recovery는 cwnd를 ssthresh + 3으로 설정하고 새로운 ACK를 받으면 cwnd를 ssthresh로 줄인 뒤 Congestion Avoidance로 돌아갑니다. 타임아웃이 발생하면 ssthresh를 cwnd/2로 설정하고 cwnd를 1로 초기화한 뒤 다시 Slow Start부터 시작합니다.
- • Slow Start는 지수 증가, Congestion Avoidance는 선형 증가
- • 3 duplicate ACKs는 Fast Retransmit/Recovery 트리거
- • 타임아웃은 cwnd를 1로 초기화하고 Slow Start 재시작
대용량 파일 전송, 스트리밍 서비스, API 서버 간 통신에서 네트워크 대역폭을 효율적으로 사용하면서도 패킷 손실을 최소화하는 데 핵심적인 역할을 합니다.
TCP Tahoe, Reno, NewReno, CUBIC의 차이점은 무엇이며, 최신 Linux 커널에서는 어떤 알고리즘을 기본으로 사용하나요?
Q. 멀티스레드 환경에서 발생할 수 있는 데드락(Deadlock)의 4가지 필요조건을 설명하고, 각 조건을 깨뜨려서 데드락을 예방하는 방법을 구체적으로 제시해주세요. 또한 데드락 예방(Prevention)과 회피(Avoidance), 탐지(Detection)의 차이점과 각각의 트레이드오프를 설명해주세요.
Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait 네 가지 조건을 모두 만족해야 데드락이 발생합니다.
데드락의 4가지 필요조건은 상호 배제(Mutual Exclusion), 점유와 대기(Hold and Wait), 비선점(No Preemption), 순환 대기(Circular Wait)입니다. 상호 배제는 공유 자원을 없애거나 lock-free 알고리즘으로, 점유와 대기는 필요한 모든 자원을 한 번에 획득하도록 하여, 비선점은 타임아웃을 두어 강제로 자원을 회수하여, 순환 대기는 자원에 순서를 부여해 항상 같은 순서로 획득하도록 하여 예방할 수 있습니다. 예방은 조건 자체를 원천 차단하지만 자원 활용률이 낮고, 회피는 Banker's Algorithm처럼 safe state를 유지하지만 사전 정보가 필요하며, 탐지는 주기적으로 Resource Allocation Graph를 검사하지만 오버헤드가 있고 복구 비용이 큽니다.
- • 4가지 필요조건을 모두 만족해야 데드락 발생
- • 각 조건을 깨뜨리는 구체적 방법 제시
- • 예방/회피/탐지의 트레이드오프 이해
데이터베이스 트랜잭션, 분산 락 관리, 멀티스레드 애플리케이션에서 자원 경합 상황을 설계할 때 반드시 고려해야 합니다.
실제 데이터베이스 시스템에서는 데드락을 어떻게 처리하며, 트랜잭션 격리 수준과 데드락 발생 빈도는 어떤 관계가 있나요?
Q. 데이터베이스 인덱스에서 B-Tree와 B+Tree의 구조적 차이를 설명하고, 왜 대부분의 RDBMS가 B-Tree 대신 B+Tree를 사용하는지 범위 검색과 순차 접근 관점에서 설명해주세요. 또한 B+Tree의 차수(order)가 성능에 미치는 영향도 포함해주세요.
리프 노드의 연결 구조와 데이터 저장 위치에 주목하세요.
B-Tree는 모든 노드에 키와 데이터를 저장하지만, B+Tree는 리프 노드에만 데이터를 저장하고 내부 노드는 키만 가집니다. B+Tree의 리프 노드는 연결 리스트로 연결되어 있어 범위 검색 시 리프 노드만 순차적으로 스캔하면 되므로 O(log N + M) 시간에 효율적으로 처리됩니다. 반면 B-Tree는 중위 순회가 필요해 비효율적입니다. B+Tree는 내부 노드가 더 많은 키를 저장할 수 있어 트리 높이가 낮아지고, 디스크 I/O 횟수가 줄어듭니다. 차수가 클수록 트리 높이는 낮아지지만 노드 내 검색 비용은 증가하므로, 디스크 블록 크기를 고려해 최적 차수를 결정합니다.
- • B+Tree는 리프 노드만 데이터 저장, 연결 리스트 구조
- • 범위 검색 시 순차 스캔으로 효율적
- • 차수와 트리 높이, 디스크 I/O 트레이드오프
대용량 테이블에서 WHERE 절의 범위 조건, ORDER BY를 사용한 정렬, 페이징 쿼리의 성능을 결정하는 핵심 요소입니다.
클러스터드 인덱스(Clustered Index)와 논클러스터드 인덱스(Non-Clustered Index)의 차이는 무엇이며, MySQL InnoDB에서는 어떻게 구현되어 있나요?
Q. 일관성 해싱(Consistent Hashing)의 동작 원리와 이것이 기존 해싱 대비 어떤 문제를 해결하는지 설명해주세요. 특히 노드 추가/제거 시 재배치되는 데이터의 비율과 가상 노드(Virtual Node)를 사용하는 이유를 포함해 설명해주세요.
분산 캐시나 샤딩 환경에서 노드 변경 시 전체 데이터를 재배치하지 않는 방법을 생각해보세요.
일관성 해싱은 해시 공간을 원형 링으로 구성하고, 데이터와 노드를 같은 해시 함수로 링 위에 배치합니다. 데이터는 시계 방향으로 가장 가까운 노드에 할당되며, 노드가 추가되거나 제거될 때 평균적으로 K/N(K는 키 개수, N은 노드 개수)의 데이터만 재배치됩니다. 기존 모듈로 해싱은 노드 변경 시 거의 모든 데이터가 재배치되는 문제가 있습니다. 가상 노드는 하나의 물리 노드를 링 위의 여러 지점에 배치하여 데이터 분포를 균등하게 만들고, 노드 간 부하 불균형을 해소합니다. 가상 노드 수가 많을수록 분포는 균등해지지만 메모리 오버헤드가 증가합니다.
- • 링 구조로 노드 변경 시 K/N만 재배치
- • 가상 노드로 부하 균등 분산
- • 기존 모듈로 해싱 대비 확장성 우수
분산 캐시(Redis, Memcached), NoSQL 데이터베이스, CDN, 로드 밸런서에서 서버 추가/제거 시 최소한의 데이터 이동으로 확장성을 확보하는 데 사용됩니다.
Redis Cluster나 Cassandra 같은 분산 시스템에서 일관성 해싱을 어떻게 활용하고 있으며, Rendezvous Hashing 같은 대안과는 어떤 차이가 있나요?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!