Java 리드·아키텍트 CS 기초 기술면접
새 면접Q. 대규모 분산 캐시 시스템에서 Consistent Hashing을 사용하는 이유와 동작 원리를 설명해주세요. 특히 노드 추가/삭제 시 데이터 재분배 비용을 최소화하는 메커니즘과 Virtual Node(가상 노드)를 사용하는 이유, 그리고 실제 구현 시 고려해야 할 해시 함수 선택 기준을 포함해 설명해주세요.
일반적인 해싱과 달리 노드 변경 시 전체 데이터가 아닌 일부만 이동하는 원리에 집중하세요.
Consistent Hashing은 해시 링(0~2^32-1) 구조에서 데이터와 노드를 모두 해싱하여 배치하고, 데이터는 시계방향으로 가장 가까운 노드에 저장됩니다. 노드 추가/삭제 시 전체 데이터의 1/N만 재분배되어 일반 해싱의 O(K) 대비 효율적입니다. Virtual Node는 각 물리 노드를 여러 개의 가상 노드로 매핑하여 데이터 분산의 불균형을 해소하고, 노드 용량 차이를 반영할 수 있게 합니다. 해시 함수는 MD5, MurmurHash 등 충돌이 적고 균등 분포를 보장하며 계산 속도가 빠른 것을 선택해야 합니다. Redis Cluster, Cassandra, DynamoDB 등에서 실제로 사용되는 핵심 기술입니다.
- • 해시 링 구조에서 데이터와 노드를 모두 해싱하여 배치
- • 노드 변경 시 1/N만 재분배되어 효율적
- • Virtual Node로 데이터 분산 불균형 해소
- • 균등 분포와 낮은 충돌률을 가진 해시 함수 선택 필요
분산 캐시, NoSQL 데이터베이스, CDN, 로드 밸런서 등에서 노드 확장 시 최소한의 데이터 이동으로 시스템을 확장할 때 사용됩니다.
Rendezvous Hashing(HRW)과 Consistent Hashing을 비교하고, 각각의 장단점과 적합한 사용 시나리오를 설명해주세요.
Q. 실시간 추천 시스템에서 사용자별 최근 1시간 내 조회한 상품 중 빈도수 상위 10개를 실시간으로 추적해야 합니다. 수백만 사용자가 초당 수천 건의 이벤트를 발생시키는 환경에서 메모리 효율적으로 이를 구현하기 위한 자료구조와 알고리즘을 제시하고, 정확도와 메모리 사용량의 트레이드오프를 설명해주세요.
정확한 카운팅 대신 근사 알고리즘을 사용하면 메모리를 대폭 절약할 수 있습니다.
Count-Min Sketch와 Min-Heap을 결합한 방식이 효과적입니다. Count-Min Sketch는 여러 개의 해시 함수와 2차원 카운터 배열로 빈도를 근사 추정하여 O(1) 시간에 업데이트하고 메모리를 고정적으로 사용합니다. Top-K를 유지하기 위해 크기 K의 Min-Heap을 사용하며, 새 항목의 추정 빈도가 힙의 최소값보다 크면 교체합니다. 시간 윈도우 처리를 위해 Sliding Window Count-Min Sketch나 Time-decaying 기법을 적용할 수 있습니다. 정확도는 해시 함수 개수와 배열 크기에 비례하며, 실무에서는 99% 정확도로 메모리를 1/100 이하로 줄일 수 있습니다. Redis의 TopK 모듈이나 Apache DataSketches 라이브러리에서 이러한 구현을 제공합니다.
- • Count-Min Sketch로 O(1) 시간에 빈도 근사 추정
- • Min-Heap으로 Top-K 유지
- • Sliding Window 기법으로 시간 제약 처리
- • 정확도와 메모리 사용량을 파라미터로 조절 가능
실시간 트렌딩 토픽 분석, 인기 검색어 추출, 이상 트래픽 탐지 등 대용량 스트리밍 데이터에서 빈도 기반 분석이 필요할 때 사용됩니다.
HyperLogLog, Bloom Filter, Count-Min Sketch 등 확률적 자료구조의 특징을 비교하고, 각각 어떤 문제에 적합한지 설명해주세요.
Q. TCP의 혼잡 제어(Congestion Control) 알고리즘인 Slow Start, Congestion Avoidance, Fast Retransmit, Fast Recovery의 동작 원리를 설명하고, 각 단계에서 cwnd(congestion window)가 어떻게 변화하는지 설명해주세요. 특히 데이터센터 내부 통신과 인터넷 통신에서 TCP 성능 차이가 발생하는 이유와 이를 개선하기 위한 TCP 변형(CUBIC, BBR)의 특징도 포함해 설명해주세요.
패킷 손실을 네트워크 혼잡의 신호로 해석하는 방식과, 이것이 최적이 아닌 환경이 무엇인지 생각해보세요.
Slow Start는 cwnd를 1 MSS에서 시작해 ACK마다 지수적으로 증가시켜 빠르게 대역폭을 탐색하고, ssthresh(slow start threshold)에 도달하면 Congestion Avoidance로 전환되어 RTT마다 1 MSS씩 선형 증가합니다. 패킷 손실 감지 시 Fast Retransmit은 3개의 중복 ACK로 즉시 재전송하고, Fast Recovery는 ssthresh를 cwnd/2로 줄인 후 선형 증가를 재개합니다. 데이터센터는 낮은 지연과 높은 대역폭 환경이라 Slow Start가 과도하게 보수적이며, 인터넷은 다양한 RTT와 대역폭으로 인해 손실 기반 혼잡 제어가 비효율적입니다. CUBIC은 손실 이후 빠른 회복을 위해 3차 함수로 cwnd를 증가시켜 고속 네트워크에 적합하고, BBR은 패킷 손실 대신 RTT와 처리량을 측정해 병목 대역폭을 추정하여 버퍼 팽창을 방지합니다.
- • Slow Start는 지수 증가, Congestion Avoidance는 선형 증가
- • Fast Retransmit/Recovery로 타임아웃 없이 빠른 복구
- • 손실 기반 혼잡 제어는 고속/저지연 환경에서 비효율적
- • CUBIC은 고속 네트워크, BBR은 버퍼 팽창 문제에 최적화
클라우드 환경에서 VM 간 통신 최적화, CDN 성능 튜닝, 대용량 파일 전송 시스템 설계 시 TCP 파라미터를 조정하거나 프로토콜을 선택할 때 필요합니다.
HTTP/3에서 QUIC 프로토콜이 TCP 대신 UDP를 사용하는 이유와, QUIC의 혼잡 제어가 TCP와 어떻게 다른지 설명해주세요.
Q. 멀티스레드 애플리케이션에서 발생할 수 있는 교착상태(Deadlock)의 4가지 필요조건을 설명하고, 각 조건을 깨뜨려 교착상태를 예방하는 방법을 제시해주세요. 특히 데이터베이스 트랜잭션 레벨과 애플리케이션 레벨에서 교착상태를 탐지하고 복구하는 전략을 비교하고, 실무에서 교착상태를 최소화하기 위한 설계 원칙을 설명해주세요.
상호배제, 점유와 대기, 비선점, 순환 대기 네 가지 조건을 모두 만족해야 교착상태가 발생합니다.
교착상태의 4가지 필요조건은 상호배제(자원을 동시에 사용 불가), 점유와 대기(자원을 보유한 채 추가 요청), 비선점(강제로 자원 회수 불가), 순환 대기(자원 대기 그래프에 사이클 존재)입니다. 예방 방법으로는 모든 자원을 한 번에 획득(점유와 대기 방지), 자원에 순서를 부여해 항상 같은 순서로 획득(순환 대기 방지), 타임아웃 설정(비선점 완화) 등이 있습니다. 데이터베이스는 Wait-For Graph로 교착상태를 탐지하고 희생자 선택 알고리즘으로 트랜잭션을 롤백하며, 애플리케이션 레벨에서는 락 순서 강제, 락 타임아웃, try-lock 패턴을 사용합니다. 실무에서는 락 범위 최소화, 락 보유 시간 단축, 낙관적 락 우선 고려, 모니터링을 통한 조기 발견이 중요합니다.
- • 4가지 필요조건: 상호배제, 점유와 대기, 비선점, 순환 대기
- • 락 순서 강제와 타임아웃으로 예방
- • 데이터베이스는 자동 탐지/복구, 애플리케이션은 설계로 예방
- • 락 범위와 보유 시간 최소화가 핵심
분산 트랜잭션 처리, 멀티스레드 배치 작업, 동시성이 높은 API 서버에서 자원 경합 시 교착상태를 예방하고 처리하는 데 필요합니다.
Livelock과 Starvation의 차이를 설명하고, 각각을 해결하기 위한 방법을 제시해주세요.
Q. MVCC(Multi-Version Concurrency Control)의 동작 원리를 설명하고, PostgreSQL과 MySQL(InnoDB)의 MVCC 구현 차이를 비교해주세요. 특히 Undo Log와 Redo Log의 역할, 스냅샷 격리 수준에서의 동작 방식, 그리고 장시간 실행되는 트랜잭션이 시스템 성능에 미치는 영향과 이를 완화하는 방법을 포함해 설명해주세요.
여러 버전의 데이터를 유지하여 읽기와 쓰기가 서로 블로킹하지 않는 원리에 집중하세요.
MVCC는 각 트랜잭션이 시작 시점의 데이터 스냅샷을 보도록 여러 버전을 유지하여 읽기와 쓰기가 락 없이 동시에 수행됩니다. PostgreSQL은 각 튜플에 xmin/xmax를 저장해 가시성을 판단하고 VACUUM으로 오래된 버전을 정리하며, MySQL InnoDB는 Undo Log에 이전 버전을 저장하고 트랜잭션 ID로 가시성을 결정합니다. Undo Log는 롤백과 일관된 읽기를 위한 이전 버전 보관, Redo Log는 크래시 복구를 위한 변경 사항 기록입니다. 스냅샷 격리에서는 트랜잭션 시작 시점의 커밋된 데이터만 보이며, Write Skew 같은 이상 현상이 발생할 수 있습니다. 장시간 트랜잭션은 오래된 버전을 계속 유지하게 만들어 VACUUM 지연, Undo Log 증가, 성능 저하를 유발하므로 트랜잭션 분할, 타임아웃 설정, 모니터링이 필요합니다.
- • 여러 버전 유지로 읽기-쓰기 비블로킹 동시성 제공
- • PostgreSQL은 튜플 버전 관리, MySQL은 Undo Log 사용
- • Undo Log는 롤백/읽기, Redo Log는 복구용
- • 장시간 트랜잭션은 버전 정리 지연으로 성능 저하 유발
높은 동시성이 요구되는 OLTP 시스템에서 읽기 성능을 유지하면서 트랜잭션 격리를 보장하고, 배치 작업과 실시간 쿼리를 동시에 처리할 때 필요합니다.
Serializable Snapshot Isolation(SSI)이 일반 스냅샷 격리와 어떻게 다르며, Write Skew 문제를 어떻게 해결하는지 설명해주세요.
Q. B-Tree와 B+Tree의 구조적 차이를 설명하고, 데이터베이스 인덱스에서 B+Tree를 선호하는 이유를 설명해주세요. 특히 범위 검색 성능, 캐시 효율성, 디스크 I/O 최적화 관점에서 비교하고, LSM-Tree와 B+Tree의 쓰기 성능 차이와 각각의 적합한 사용 시나리오를 제시해주세요.
B+Tree는 모든 데이터를 리프 노드에만 저장하고 리프 노드가 연결 리스트로 연결된 구조입니다.
B-Tree는 모든 노드에 키와 데이터를 저장하지만, B+Tree는 리프 노드에만 데이터를 저장하고 내부 노드는 키만 가져 더 많은 키를 메모리에 캐싱할 수 있습니다. B+Tree의 리프 노드는 연결 리스트로 연결되어 범위 검색 시 순차 스캔이 가능하고 디스크 I/O가 효율적입니다. 내부 노드가 작아 트리 높이가 낮아지고 캐시 히트율이 높아집니다. LSM-Tree는 메모리에서 쓰기를 버퍼링하고 주기적으로 디스크에 순차 쓰기하여 쓰기 성능이 뛰어나지만, 읽기 시 여러 레벨을 검색해야 하고 Compaction 오버헤드가 있습니다. B+Tree는 읽기 중심 OLTP, LSM-Tree는 쓰기 중심 로그 데이터나 시계열 데이터에 적합하며, RocksDB, Cassandra, HBase 등에서 사용됩니다.
- • B+Tree는 리프 노드에만 데이터 저장, 내부 노드는 키만
- • 리프 노드 연결로 범위 검색과 순차 스캔 효율적
- • LSM-Tree는 순차 쓰기로 쓰기 성능 우수
- • B+Tree는 읽기 중심, LSM-Tree는 쓰기 중심 워크로드에 적합
데이터베이스 인덱스 설계, NoSQL 스토리지 엔진 선택, 쓰기 집약적 애플리케이션의 성능 최적화 시 적절한 자료구조를 선택하는 데 필요합니다.
Fractal Tree Index나 Bw-Tree 같은 최신 인덱스 구조의 특징과, 전통적인 B+Tree 대비 장점을 설명해주세요.
Q. DNS 조회 과정을 Recursive Query와 Iterative Query의 차이를 포함하여 설명하고, DNS 캐싱이 여러 레벨(브라우저, OS, 리졸버, 네임서버)에서 작동하는 방식을 설명해주세요. 특히 TTL 설정 전략과 DNS 장애 시 애플리케이션 레벨에서 대응할 수 있는 방법, 그리고 대규모 서비스에서 DNS 기반 로드 밸런싱의 한계를 설명해주세요.
DNS는 계층적 구조로 Root → TLD → Authoritative 순서로 조회되며, 각 단계에서 캐싱이 발생합니다.
Recursive Query는 클라이언트가 DNS 리졸버에 요청하면 리졸버가 모든 조회를 대신 수행해 최종 결과를 반환하고, Iterative Query는 각 네임서버가 다음 네임서버의 주소만 알려줘 클라이언트가 반복 조회합니다. DNS 조회는 Root 네임서버 → TLD 네임서버(.com) → Authoritative 네임서버 순으로 진행되며, 브라우저 캐시, OS 캐시, 리졸버 캐시에서 각각 TTL 기반으로 캐싱됩니다. TTL은 변경 빈도와 장애 복구 속도를 고려해 설정하며, 짧으면 유연하지만 조회 부하가 높고 길면 반대입니다. DNS 장애 시 애플리케이션은 캐시된 IP 사용, 다중 DNS 서버 설정, 헬스체크 기반 Fallback, Connection Pool 유지 등으로 대응합니다. DNS 로드 밸런싱은 클라이언트 캐싱으로 실시간 반영이 어렵고, 지리적 라우팅의 정확도가 낮으며, 헬스체크가 제한적이라 L4/L7 로드 밸런서와 병행해야 합니다.
- • Recursive는 리졸버가 전체 조회, Iterative는 단계별 조회
- • 다층 캐싱으로 조회 성능 향상, TTL로 제어
- • DNS 장애 시 캐시 활용과 다중 DNS 서버 구성 필요
- • DNS 로드 밸런싱은 캐싱과 헬스체크 한계로 L4/L7와 병행
글로벌 서비스의 지역별 트래픽 라우팅, 장애 시 빠른 Failover, CDN 연동, 마이크로서비스의 서비스 디스커버리 구현 시 DNS 이해가 필요합니다.
DNSSEC의 동작 원리와 도입 시 고려사항, 그리고 DNS over HTTPS(DoH)와 DNS over TLS(DoT)의 차이를 설명해주세요.
Q. 가상 메모리 시스템에서 페이지 교체 알고리즘(FIFO, LRU, LFU, Clock)의 동작 원리를 비교하고, 각각의 장단점을 설명해주세요. 특히 LRU를 실제로 구현할 때 사용하는 자료구조와 시간 복잡도, 그리고 운영체제에서 근사 LRU 알고리즘을 사용하는 이유를 설명해주세요. 애플리케이션 레벨 캐시에서 이러한 알고리즘을 적용하는 방법도 포함해주세요.
정확한 LRU 구현은 모든 페이지 접근을 추적해야 하므로 오버헤드가 크다는 점을 고려하세요.
FIFO는 가장 먼저 들어온 페이지를 교체하여 구현이 간단하지만 Belady's Anomaly가 발생할 수 있고, LRU는 가장 오래 사용되지 않은 페이지를 교체하여 지역성을 잘 반영하지만 모든 접근을 추적해야 합니다. LFU는 사용 빈도가 낮은 페이지를 교체하고, Clock(Second Chance)은 Reference Bit를 사용해 근사 LRU를 O(1)에 구현합니다. LRU 구현은 Double Linked List와 HashMap을 사용해 O(1) 접근과 갱신을 달성하지만, 하드웨어 지원 없이는 모든 메모리 접근을 추적할 수 없어 운영체제는 Clock 알고리즘 같은 근사 방식을 사용합니다. 애플리케이션 레벨에서는 LinkedHashMap, Guava Cache, Caffeine 등의 라이브러리로 LRU를 구현하며, 메모리 제약과 접근 패턴에 따라 적절한 알고리즘을 선택합니다.
- • FIFO는 간단하지만 비효율적, LRU는 지역성 반영하지만 오버헤드
- • LRU는 Double Linked List + HashMap으로 O(1) 구현
- • 운영체제는 하드웨어 제약으로 Clock 같은 근사 LRU 사용
- • 애플리케이션 캐시는 접근 패턴에 맞는 알고리즘 선택 필요
애플리케이션 레벨 캐시 설계, 데이터베이스 버퍼 풀 관리, CDN 캐싱 전략, Redis 같은 인메모리 저장소의 메모리 관리 정책 수립 시 필요합니다.
Working Set 모델과 Thrashing 현상을 설명하고, 멀티프로세스 환경에서 페이지 교체를 어떻게 공정하게 수행하는지 설명해주세요.
Q. 대규모 로그 파일에서 특정 패턴을 빠르게 검색하기 위한 문자열 매칭 알고리즘을 비교해주세요. Naive 알고리즘, KMP, Boyer-Moore, Rabin-Karp의 시간 복잡도와 동작 원리를 설명하고, 각각의 장단점과 적합한 사용 시나리오를 제시해주세요. 특히 여러 패턴을 동시에 검색해야 하는 경우 Aho-Corasick 알고리즘의 효율성을 설명해주세요.
패턴의 특성(길이, 개수)과 텍스트 특성(길이, 알파벳 크기)에 따라 최적 알고리즘이 달라집니다.
Naive 알고리즘은 O(nm) 시간으로 모든 위치에서 패턴을 비교하며 구현이 간단하지만 비효율적입니다. KMP는 실패 함수로 불필요한 비교를 건너뛰어 O(n+m)이지만 전처리가 복잡하고, Boyer-Moore는 패턴 끝에서부터 비교하고 불일치 시 여러 칸 건너뛰어 평균 O(n/m)으로 실무에서 가장 빠릅니다. Rabin-Karp는 해시를 사용해 O(n+m) 기대 시간이며 다중 패턴 검색에 유리하지만 해시 충돌 처리가 필요합니다. Aho-Corasick은 Trie와 실패 링크를 사용해 k개 패턴을 O(n+m+z) 시간에 동시 검색하여 침입 탐지 시스템, 안티바이러스, 로그 분석에 적합합니다. 실무에서는 패턴 수가 적으면 Boyer-Moore, 많으면 Aho-Corasick을 선택합니다.
- • Boyer-Moore는 평균 O(n/m)으로 단일 패턴 검색에 가장 빠름
- • KMP는 O(n+m) 보장하지만 전처리 복잡
- • Aho-Corasick은 다중 패턴을 한 번의 스캔으로 검색
- • 패턴 수와 길이에 따라 적절한 알고리즘 선택 필요
로그 분석 시스템, 침입 탐지 시스템, 텍스트 에디터의 검색 기능, 웹 크롤러의 콘텐츠 필터링 등에서 대용량 텍스트 검색 성능 최적화에 사용됩니다.
정규표현식 엔진의 내부 동작 원리(NFA, DFA)와 백트래킹으로 인한 성능 문제(ReDoS)를 설명하고, 이를 방지하는 방법을 제시해주세요.
Q. 분산 데이터베이스에서 CAP 정리(Consistency, Availability, Partition Tolerance)를 설명하고, 실제로는 CP와 AP 중 하나를 선택해야 하는 이유를 설명해주세요. 특히 네트워크 파티션 발생 시 각 선택의 트레이드오프를 구체적인 시나리오로 설명하고, PACELC 정리가 CAP 정리를 어떻게 확장하는지, 그리고 eventual consistency를 달성하기 위한 구체적인 기법들을 설명해주세요.
네트워크 파티션은 분산 시스템에서 항상 발생할 수 있으므로 P는 포기할 수 없습니다.
CAP 정리는 분산 시스템에서 일관성(Consistency), 가용성(Availability), 파티션 허용성(Partition Tolerance)을 모두 만족할 수 없다는 것으로, 네트워크 파티션은 항상 발생 가능하므로 실제로는 CP(일관성 우선, 일부 노드 응답 불가) 또는 AP(가용성 우선, 일시적 불일치 허용)를 선택합니다. CP는 금융 거래, 재고 관리처럼 정확성이 중요한 경우 적합하고, AP는 SNS 피드, 조회수 카운트처럼 일시적 불일치가 허용되는 경우 적합합니다. PACELC는 파티션 발생 시(PA 또는 PC) 뿐 아니라 정상 상태에서도 지연(Latency)과 일관성(Consistency) 간 트레이드오프가 있음을 설명합니다. Eventual consistency는 Vector Clock, CRDT(Conflict-free Replicated Data Types), Gossip Protocol, Read Repair, Hinted Handoff 등으로 달성하며, 각 기법은 충돌 해결과 수렴 보장 방식이 다릅니다.
- • 네트워크 파티션은 불가피하므로 CP 또는 AP 선택 필요
- • CP는 정확성 우선, AP는 가용성 우선
- • PACELC는 정상 상태의 지연-일관성 트레이드오프 추가
- • Eventual consistency는 Vector Clock, CRDT 등으로 구현
분산 데이터베이스 선택(Cassandra, MongoDB, DynamoDB), 마이크로서비스 간 데이터 동기화, 글로벌 서비스의 다중 리전 아키텍처 설계 시 일관성 모델 결정에 필요합니다.
Strong Consistency, Sequential Consistency, Causal Consistency, Eventual Consistency를 비교하고, 각 일관성 모델의 구현 복잡도와 성능 영향을 설명해주세요.
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!