자료구조/알고리즘 리드·아키텍트 기술면접

Redis Sorted Set을 메인 자료구조로 사용하되, 쓰기 부하 분산을 위해 Sharding 전략을 적용합니다. 실시간 업데이트는 ZINCRBY로 처리하고, ZREVRANGE로 상위 100위를 조회합니다. 초당 10만 건의 업데이트를 감당하기 위해 Write-Behind 캐싱 패턴을 적용하여 배치로 묶어 처리하고, 읽기는 별도의 Read Replica에서 처리합니다. 완벽한 실시간 정확도 대신 eventual consistency를 허용하여 성능을 확보하며, 주기적으로 백그라운드에서 정합성을 검증합니다. 장애 대응을 위해 데이터는 Redis Persistence와 별도 DB에 이중화하고, Circuit Breaker 패턴으로 장애 전파를 방지합니다.

STAR 방식으로 답변을 구성합니다. Situation: 레거시 전환 시 개발팀은 기술부채 해소를, 비즈니스팀은 신규 기능 출시를 우선시한 상황을 설명합니다. Task: 양측의 요구를 모두 충족하면서 프로젝트를 성공시켜야 했던 과제를 명확히 합니다. Action: 각 요구사항의 비즈니스 임팩트와 기술 리스크를 정량화하여 우선순위 매트릭스를 작성하고, Strangler Fig 패턴을 제안하여 점진적 전환과 기능 개발을 병행할 수 있는 로드맵을 제시했던 구체적 행동을 설명합니다. Result: 합의된 일정과 달성한 성과(예: 3개월 내 핵심 기능 이전 완료, 기술부채 40% 감소)를 수치로 제시하고, 이 경험을 통해 배운 이해관계자 관리 원칙을 언급합니다.

Bloom Filter를 1차 필터로 사용하여 메모리를 획기적으로 절약합니다. Bloom Filter는 False Positive는 허용하지만 False Negative가 없어 중복 가능성이 있는 항목만 추려낼 수 있습니다. 1억 개 URL에 대해 1% 오탐률을 목표로 하면 약 120MB의 메모리만 필요합니다. Bloom Filter에서 중복 의심 판정이 나온 경우에만 Redis Set이나 Database로 2차 검증을 수행하여 정확도를 보장합니다. 시스템이 분산되어 있다면 Consistent Hashing으로 URL을 여러 노드에 분산하여 각 노드가 독립적으로 Bloom Filter를 유지하게 합니다. 주기적으로 Bloom Filter를 초기화하거나 Counting Bloom Filter를 사용하여 삭제 연산도 지원할 수 있습니다.

먼저 APM 도구로 분산 트레이싱을 확인하여 어느 구간에서 지연이 발생하는지 파악합니다. DB와 CPU가 정상이라면 Connection Pool 고갈, Thread Pool 포화, 외부 API 타임아웃 등을 의심합니다. Connection Pool 모니터링으로 Active/Idle 커넥션 수를 확인하고, 만약 Pool이 고갈되었다면 Long-running query나 커넥션 미반환 코드를 찾습니다. Thread Dump를 분석하여 BLOCKED 상태의 스레드가 많다면 동기화 이슈나 Deadlock을 확인합니다. 외부 서비스 호출이 있다면 Circuit Breaker 미적용으로 인한 Cascading Failure를 점검하고, 타임아웃 설정을 검토합니다. 근본 원인 파악 후 즉시 Connection Pool 크기 조정, 타임아웃 설정, Circuit Breaker 적용 등으로 해결하고, 재발 방지를 위해 알림 임계값을 설정합니다.

기본적으로 ReentrantReadWriteLock을 사용하여 읽기는 동시에, 쓰기는 배타적으로 처리할 수 있지만 이것만으로는 부족합니다. 더 나은 방법은 Segment 단위로 락을 분리하는 Lock Striping 기법을 적용하여 ConcurrentHashMap처럼 동시성을 높이는 것입니다. 각 세그먼트가 독립적인 LRU 리스트를 유지하면 서로 다른 세그먼트에 대한 접근은 동시에 처리됩니다. 또 다른 접근은 Lock-Free 알고리즘을 사용하는 것으로, CAS(Compare-And-Swap) 연산으로 Linked List 조작을 원자적으로 수행하지만 구현 복잡도가 매우 높습니다. 실무에서는 Caffeine 라이브러리처럼 W-TinyLFU 알고리즘을 사용하여 LRU보다 나은 hit rate와 동시성을 모두 확보하는 방법도 고려할 수 있습니다. 트레이드오프는 구현 복잡도, 메모리 오버헤드, 그리고 정확한 LRU 순서 보장 여부입니다.

Range Partitioning을 일 단위로 적용하여 매일 새로운 파티션을 생성하고, 오래된 파티션은 별도 스토리지로 이동하거나 압축합니다. 최근 7일 데이터(Hot Data)는 SSD 기반 스토리지에, 그 이전 데이터(Cold Data)는 저렴한 HDD나 Object Storage에 보관합니다. 인덱스는 timestamp + entity_id 복합 인덱스를 생성하되, 파티션별로 Local Index를 유지하여 인덱스 크기를 제한합니다. 쓰기 성능을 위해 Bulk Insert와 배치 처리를 활용하고, WAL(Write-Ahead Log) 설정을 최적화합니다. 조회 성능을 위해 최근 7일 데이터는 Materialized View나 Summary Table로 사전 집계하여 제공합니다. 파티션 관리는 자동화하여 매일 새 파티션 생성, 7일 이전 파티션 아카이빙, 90일 이전 파티션 삭제 등을 스케줄링합니다.

기본 Dijkstra는 인접 리스트와 Binary Heap을 사용하면 O((V+E)logV)이지만, Fibonacci Heap을 사용하면 O(E + VlogV)로 개선됩니다. 그러나 Fibonacci Heap은 구현 복잡도와 상수 계수가 커서 실무에서는 Binary Heap이 더 효율적인 경우가 많습니다. 그래프가 sparse하다면(E가 V^2보다 훨씬 작음) 인접 리스트가, dense하다면 인접 행렬이 유리합니다. A* 알고리즘을 사용하면 휴리스틱 함수로 탐색 공간을 줄여 실제 수행 시간을 크게 단축할 수 있습니다. 양방향 탐색(Bidirectional Search)을 적용하면 탐색 공간이 절반으로 줄어듭니다. 실시간 경로 탐색이 필요하다면 Contraction Hierarchies나 Highway Hierarchies 같은 전처리 기반 알고리즘을 사용하여 쿼리 시간을 밀리초 단위로 줄일 수 있지만, 그래프 변경 시 재계산 비용이 큽니다.