자료구조/알고리즘 리드·아키텍트 성능 최적화 면접

먼저 해시 함수를 사용해 로그 파일을 IP 주소 기준으로 1000개의 작은 파일로 분할합니다(External Hashing). 각 파일은 약 10GB로 메모리에 적재 가능합니다. 각 분할 파일마다 HashMap으로 IP별 빈도를 카운팅하고, Min Heap(크기 1000)을 유지하며 상위 1000개를 추출합니다. 마지막으로 1000개 파일에서 얻은 결과를 병합하여 최종 상위 1000개를 선정합니다. 시간 복잡도는 O(N + K*M*logM)이며(N=전체 레코드, K=파일 수, M=힙 크기), 공간 복잡도는 O(M)로 메모리 제약을 만족합니다. 실무에서는 MapReduce 패러다임으로 분산 처리하여 처리 시간을 단축할 수 있습니다.

쿼리 패턴 분석이 최우선입니다. WHERE user_id = ? ORDER BY order_date DESC 형태라면 (user_id, order_date, status) 순서가 최적입니다. user_id로 먼저 필터링하여 범위를 좁히고, order_date로 정렬되어 있어 추가 정렬 비용이 없으며, status는 커버링 인덱스 효과를 제공합니다. (order_date, user_id) 순서는 날짜 범위 검색 시 유리하지만 사용자별 조회에는 인덱스 스캔 범위가 넓어집니다. 카디널리티가 높은 user_id를 선두에 두면 인덱스 분기가 효율적이고, 파티셔닝과 결합 시 파티션 프루닝 효과도 얻을 수 있습니다. 실제 쿼리 실행 계획과 통계를 확인하여 인덱스 힌트나 파티셔닝 전략을 함께 검토해야 합니다.

읽기가 쓰기보다 4배 많은 상황에서는 Optimistic Concurrency Control과 Lock-free 자료구조 조합이 유리합니다. CAS(Compare-And-Swap) 연산 기반의 AtomicInteger로 재고를 관리하고, 버전 번호를 활용한 낙관적 락으로 업데이트 충돌을 처리합니다. 비관적 락은 경합이 높을 때 대기 시간이 길어지지만, Lock-free 방식은 retry 오버헤드가 있어도 전체 처리량이 높습니다. 다만 ABA 문제와 메모리 순서 보장을 위해 Memory Barrier를 적절히 사용해야 합니다. 최종 일관성을 허용할 수 있다면 Read Replica와 Write-through Cache를 결합하여 읽기 성능을 더욱 향상시킬 수 있습니다. 재고 정합성이 중요하다면 분산 락(Redis, Zookeeper)과 이벤트 소싱 패턴을 고려합니다.

CDN은 정적 리소스와 변경이 드문 상품 기본 정보를 1시간 TTL로 캐싱하고, Redis는 실시간성이 필요한 재고/가격 정보를 5분 TTL로 관리합니다. Application Cache는 사용자 세션별 데이터를 LRU로 메모리에 유지합니다. Cache Stampede 방지를 위해 Probabilistic Early Expiration 기법을 적용하여 TTL 만료 전 일정 확률로 미리 갱신하고, Redis의 SETNX를 활용한 Lock 메커니즘으로 동시 갱신 요청을 직렬화합니다. 또한 Stale-While-Revalidate 패턴으로 만료된 캐시를 임시로 제공하면서 백그라운드에서 갱신합니다. 각 레이어별 모니터링을 통해 히트율과 지연시간을 추적하고 TTL을 동적으로 조정합니다.

Inverted Index의 포스팅 리스트는 정렬된 문서 ID 배열로 유지하며, AND 연산 시 가장 짧은 리스트를 기준으로 다른 리스트들과 병합합니다. Skip List를 사용하면 O(n) 순차 탐색을 O(log n)으로 개선하여 긴 포스팅 리스트를 건너뛸 수 있습니다. OR 연산은 Priority Queue를 사용한 K-way Merge로 처리합니다. 고빈도 용어(stopwords)는 Bitmap Index로 변환하여 비트 연산으로 빠르게 교집합/합집합을 계산합니다. 저빈도 용어는 압축된 포스팅 리스트로 유지하여 공간 효율성을 높입니다. WAND(Weak AND) 알고리즘을 적용하면 상위 K개 결과만 필요할 때 조기 종료로 성능을 크게 향상시킬 수 있습니다. 샤딩 전략으로 문서를 분산 저장하고 병렬 검색 후 결과를 병합합니다.

먼저 Connection Pool 크기를 모니터링하여 대기 시간이 발생하는지 확인하고, 피크 트래픽의 1.5배로 설정합니다. HTTP Keep-Alive를 활성화하고 idle timeout을 60초로 설정하여 연결 재사용률을 높입니다. TCP_NODELAY 옵션으로 Nagle 알고리즘을 비활성화하여 작은 패킷의 지연을 줄입니다. Hedged Request 패턴을 도입하여 P95 지연시간 후 동일 요청을 다른 인스턴스로 병렬 전송하고 먼저 응답한 결과를 사용합니다. Adaptive Timeout을 구현하여 최근 응답 시간의 P99 기준으로 타임아웃을 동적 조정합니다. gRPC의 경우 Multiplexing을 활용하고, HTTP/2의 Stream Priority를 설정하여 중요한 요청의 우선순위를 높입니다.

먼저 G1GC의 Region 크기와 Heap 비율을 조정하여 Humongous Object 할당을 줄입니다. 대용량 HashMap을 Caffeine이나 Chronicle Map 같은 Off-heap 캐시로 전환하여 GC 대상에서 제외시킵니다. 데이터를 Weak Reference나 Soft Reference로 래핑하여 메모리 부족 시 자동 회수되도록 합니다. 객체 풀링을 도입하여 반복적으로 생성되는 객체의 할당 비용을 줄이고, Primitive 타입 특화 컬렉션(Trove, FastUtil)으로 Boxing 오버헤드를 제거합니다. 데이터가 시계열 특성이 있다면 시간 기반 파티셔닝으로 Old Generation 진입을 지연시킵니다. Shenandoah나 ZGC 같은 Low-latency GC로 전환을 검토하고, JVM 옵션으로 GC 로그를 상세히 수집하여 지속적으로 모니터링합니다.

먼저 Virtual Node 개수를 128에서 512로 증가시켜 해시 링의 분포를 균등하게 만듭니다. 하지만 이것만으로는 Hot Key 문제를 해결할 수 없으므로 Bounded Load 알고리즘을 도입합니다. 각 서버의 현재 부하를 추적하여 평균 부하의 1.25배를 초과하면 다음 서버로 라우팅합니다. Power of Two Choices 전략을 결합하여 두 개의 후보 서버 중 부하가 낮은 쪽을 선택합니다. Hot Key는 클라이언트 사이드에서 Local Cache로 처리하거나, 서버에서 Key Splitting 기법으로 여러 복제본을 만들어 부하를 분산시킵니다. Request Hedging은 읽기 전용 워크로드에만 제한적으로 적용하여 쓰기 중복을 방지합니다. 실시간 메트릭 기반의 Adaptive Load Balancing으로 동적으로 가중치를 조정합니다.

실시간 스트리밍에서는 지연시간이 중요하므로 LZ4나 Snappy를 선택합니다. LZ4는 압축 속도가 500MB/s 이상으로 CPU 오버헤드가 낮고 압축률은 2~3배 수준입니다. 배치 처리에서는 네트워크 비용 절감이 우선이므로 Zstandard나 Gzip을 사용하여 5~10배 압축률을 달성합니다. Kafka 같은 메시지 큐에서는 Producer에서 압축하고 Consumer에서 해제하는데, Snappy가 CPU와 압축률의 균형이 좋아 많이 사용됩니다. 로그 데이터의 반복 패턴이 많다면 Dictionary 기반 압축인 Zstandard가 유리하며, 사전 학습을 통해 압축률을 더욱 높일 수 있습니다. 벤치마크로 실제 데이터 샘플의 압축률, 처리량, CPU 사용률을 측정하여 비용 모델을 수립합니다.

먼저 전체 스캔을 증분 처리로 전환하여 변경된 데이터만 처리합니다. Change Data Capture나 타임스탬프 기반 파티셔닝으로 처리 대상을 90% 줄일 수 있습니다. 데이터를 독립적인 청크로 분할하고 Spark나 Flink로 병렬 처리하여 선형 확장성을 확보합니다. 알고리즘 복잡도를 개선하여 O(N²)를 O(N log N)으로 줄이고, 불필요한 조인과 집계를 제거합니다. Columnar Storage(Parquet, ORC)로 전환하여 필요한 컬럼만 읽어 I/O를 70% 감소시킵니다. Predicate Pushdown과 Partition Pruning으로 스캔 범위를 최소화합니다. 중간 결과를 Materialized View로 저장하여 재계산을 방지하고, Lambda Architecture로 실시간 레이어와 배치 레이어를 분리하여 부하를 분산합니다. 처리 시간을 모니터링하여 임계값 도달 시 자동으로 리소스를 스케일 아웃합니다.