H3 Hexagonal Indexing을 통한 대규모 실시간 드라이버 매칭 최적화

Context

위경도 기반 Radius Search 방식의 잦은 Bounding-box 스캔과 거리 계산으로 인한 CPU 부하 증가. 동적 검색 영역 생성에 따른 Caching 불가 및 서버 간 Sharding 복잡성 증대로 인한 수평 확장 한계 직면.

Technical Solution

• 전 지구를 고정된 육각형 셀로 분할하는 H3 Geospatial Indexing 도입을 통한 공간의 이산화(Discretization) 구현
• Latitude/Longitude 좌표를 결정론적 알고리즘을 통해 고유 Hex ID로 변환하여 DB 조회 없는 Microseconds 단위의 매핑 처리
• 육각형 구조의 기하학적 특성을 활용한 중심점 기준 인접 셀(k-ring)의 균일한 거리 유지 및 탐색 일관성 확보
• 'Cheap Filtering → Expensive Computation'의 2단계 설계를 통한 검색 공간의 획기적 축소
• H3 Index를 통한 드라이버 위치의 정적 캐싱 및 예측 가능한 Grid 기반의 데이터 Sharding 구조 설계
• 최종 ETA 계산 대상을 소수의 Candidate Set으로 제한하여 실시간 도로 네트워크 라우팅 부하 최소화