자료구조/알고리즘 시니어 성능 최적화 면접

먼저 LRU 기반의 다단계 캐싱 전략을 적용합니다. L1은 인메모리 캐시로 활성 사용자 10만 명 정도를 Redis의 Sorted Set과 Hash 조합으로 관리하고, TTL을 5-10분으로 설정합니다. L2는 Redis Cluster로 100만 명 규모를 1시간 TTL로 관리합니다. 사용자 행동 이벤트 발생 시 해당 사용자의 캐시만 선택적으로 무효화하는 Write-Through 패턴을 적용합니다. 캐시 키는 'user:{id}:rec:{version}' 형태로 버저닝하여 무효화 시 버전만 증가시켜 stale read를 방지합니다. 메모리는 사용자당 평균 5KB로 계산 시 L1에 500MB, L2에 5GB 정도 필요하며, 캐시 히트율 목표는 85% 이상으로 설정합니다. Bloom Filter를 추가로 두어 존재하지 않는 키에 대한 불필요한 캐시 조회를 사전에 차단합니다.

Red-Black Tree 기반의 Ordered Map 또는 Skip List를 사용하여 점수를 키로, 사용자 ID 리스트를 값으로 저장합니다. 이렇게 하면 삽입/삭제/검색이 모두 O(log n)으로 개선됩니다. 추가로 사용자 ID를 키로 하는 Hash Map을 유지하여 현재 점수를 O(1)에 조회 가능하게 합니다. 점수 업데이트 시 기존 점수 노드에서 제거 후 새 점수 노드에 삽입하는 방식으로 O(log n)에 처리합니다. 순위 조회는 트리 순회로 O(log n + k) 시간에 가능하며, 각 노드에 서브트리 크기를 저장하는 Augmented Tree 기법을 사용하면 정확한 순위를 O(log n)에 계산할 수 있습니다. 메모리는 기존 대비 약 2배 증가하지만(포인터와 메타데이터), 100만 건 기준 약 100MB 추가로 충분히 감당 가능합니다. 실무에서는 Redis Sorted Set을 사용하면 이러한 구조가 이미 구현되어 있어 빠르게 적용 가능합니다.

먼저 Elasticsearch나 OpenSearch 같은 검색 엔진으로 마이그레이션하여 역인덱스 기반 검색을 활용합니다. 상품 데이터를 비정규화하여 단일 도큐먼트에 모든 필터 속성을 포함시키고, 각 필터 필드에 대해 적절한 인덱스를 생성합니다. Bool Query로 다중 필터를 조합하면 O(log n) 수준으로 검색이 가능합니다. RDB는 마스터 데이터로 유지하고, CDC(Change Data Capture)를 통해 Elasticsearch와 실시간 동기화합니다. 자주 사용되는 필터 조합은 Materialized View나 Redis에 사전 집계하여 캐싱합니다. 카테고리별로 샤딩하여 검색 범위를 줄이고, Aggregation 기능으로 필터별 상품 수를 한 번의 쿼리로 반환합니다. 페이징은 Search After 방식을 사용해 deep pagination 문제를 해결합니다. 이 구조로 대부분의 검색을 50ms 이하로 처리 가능하며, 복잡한 쿼리도 100ms 이내 응답이 가능합니다.