H3 Hexagonal Indexing을 통한 주변 드라이버 탐색 지연시간 100ms 미만 달성

Context

수백만 명의 드라이버 위치 데이터를 기반으로 한 Brute Force 거리 계산 방식의 높은 Latency 발생. Geohash의 사각형 그리드 구조에서 발생하는 경계 지점(Edge Problem)의 데이터 누락 및 불균형한 거리 계산 문제 해결 필요.

Technical Solution

• 모든 인접 셀과의 거리가 동일한 Hexagonal Grid 구조를 채택하여 검색 편향성 제거
• H3 Index Resolution 8(~0.74 km²)을 적용하여 검색 공간을 수백만 개에서 수십 개 단위로 축소
• K-Ring 알고리즘을 통한 중심 셀 및 인접 6개 셀(K=1)의 단계적 확장 검색으로 검색 범위 최적화
• Redis에 H3 Cell ID를 Key로 저장하여 O(1) 시간 복잡도의 드라이버 목록 조회 구현
• Consistent Hashing을 통한 H3 Cell 데이터의 다중 Redis 노드 분산 저장으로 메모리 병목 해결
• K-Ring 쿼리 수행 시 여러 노드에서 데이터를 수집하는 Scatter-Gather 패턴 적용