위치 기반 서비스 설계: 지오해시, 쿼드트리, 지도

주변 검색 서비스

"반경 1km 안의 식당"을 찾는 서비스는 보통 둘로 나눈다.

왜 색인이 필요한가

위도·경도 컬럼만 두면 질의마다 모든 업체와의 거리를 계산해야 한다. 위도 범위 색인과 경도 범위 색인을 따로 걸어도, 두 범위의 교집합을 구하는 데 각각 큰 결과를 읽어야 해서 느리다. 그래서 2차원 공간을 1차원 키나 트리로 바꿔 색인한다.

지오해시

지오해시(geohash) 는 지도를 반복해서 나누며 비트를 붙이는 방식이다.

flowchart TB
  A["1단계: 경도 [-180, 0) → 0, [0, 180] → 1<br>위도 [-90, 0) → 0, [0, 90] → 1"] --> B["2단계: 각 칸을 다시 반으로 → 비트 추가<br>(경도·위도 비트를 번갈아)"] --> C["...반복"] --> D["5비트씩 묶어 Base32 문자로<br>예 #quot;wydm9q#quot;"]

• 접두사가 같으면 같은 칸 안에 있다. 그래서 WHERE geohash LIKE 'wydm9%' 같은 접두사 검색이 일반 B-트리 색인으로 된다.
• 길이가 길수록 칸이 작다. 한 글자가 5비트라 글자 하나가 늘 때마다 칸이 32개로 쪼개진다. 반경에 맞는 길이를 고른다.

• 짧은 문자열이라 DB에 저장하기 쉽고 URL로 공유하기도 좋다. 길이를 줄여 저장하면 「이 근처 어딘가」까지만 드러나 정확한 위치를 감추는 효과도 있다. 지오해시는 2008년 Gustavo Niemeyer가 만들었고, Redis(GEOADD·GEOSEARCH), Elasticsearch, MySQL·PostgreSQL(PostGIS) 같은 DB가 지원한다. 예를 들어 샌프란시스코(37.7564, −122.4016)는 9q8yy9mf이고, 9q8yy9vx와 접두사 9q8yy9를 공유하니 가깝다.
• 경계 문제: 바로 옆이어도 칸 경계를 넘으면 접두사가 전혀 다를 수 있다. 그래서 내 칸과 이웃 8칸을 함께 조회한 뒤 실제 거리로 거른다.
• 결과가 적으면 길이를 줄여(칸을 키워) 다시 찾는다.
• 칸 크기가 고정이라 도심의 한 칸에는 업체가 너무 많고 바다의 칸은 텅 빈다.

쿼드트리

쿼드트리(quadtree) 는 2차원 공간을 네 칸으로 재귀 분할하되, 칸 안의 업체가 기준(예: 100개)을 넘을 때만 더 쪼개는 트리다. 밀도에 맞춰 칸 크기가 달라지는 것이 지오해시와의 차이다.

flowchart TB
  root["루트 = 전 세계"] --> nw["북서 (업체 많음)"]
  nw --> nwnw["북서 ...<br/>(100개 이하가 될 때까지 분할)"]
  nw --> nwne["북동"]
  nw --> nwsw["남서"]
  nw --> nwse["남동"]
  root --> ne["북동 (100개 이하) → 잎 노드"]
  root --> sw["남서 ..."]
  root --> se["남동 ..."]

• 검색: 루트에서 내 위치가 든 잎 노드까지 내려간다. 업체가 모자라면 이웃 노드에서 더 가져온다.
• DB가 아니라 메모리 자료구조다. LBS 서버마다 시작할 때 전체 업체로 트리를 만든다.
• 업체가 수억 개면 트리를 만드는 데 몇 분이 걸리고, 그동안 그 서버는 트래픽을 받지 못한다. 그래서 새 버전을 일부 서버씩 순차 배포해 클러스터 전체가 동시에 빠지지 않게 한다.
• 업체 추가·삭제는 즉시 반영하기보다 다음 날 재구축처럼 늦게 반영하는 경우가 많다.
• 위경도만 있으면 모든 점과 유클리드 거리를 계산할 수 있지만 데이터가 크면 CPU를 감당할 수 없다. 쿼드트리는 2차원 범위 검색을 트리 탐색으로 줄이고, 기준 개수를 넘을 때만 쪼개 계산을 아낀다. 칸을 힐베르트 곡선(Hilbert curve) 순서로 1차원에 펴면 가까운 칸이 번호도 가까워져 범위 검색과 분할이 쉬워진다(Google S2가 이 방식).
• 담는 데이터에 따라 점 쿼드트리, 점-영역(PR) 쿼드트리, 다각형 지도(PM) 쿼드트리, 압축 쿼드트리, 엣지 쿼드트리로 나뉜다. 3차원으로 넓힌 것이 옥트리(octree)다. 위치 서비스 말고도 이미지 표현·압축, 메시 생성과 컴퓨터 그래픽스, 희소 데이터 저장에 쓰인다.

고르는 기준

실무에서는 PostGIS·Redis·Elasticsearch의 공간 색인이나 S2(구면 셀)·H3(육각형 격자) 같은 라이브러리를 쓰는 경우가 많다. 원리는 위와 같다.

지도 서비스의 세 부분

도로망은 그래프이고 최단 경로는 다익스트라·A* 계열로 찾는다. 전 세계 도로를 한 번에 탐색할 수 없으므로 지역 타일로 나누고, 고속도로 같은 상위 계층 그래프를 따로 두어 먼 거리를 빠르게 잇는다.

오프라인 위치 찾기 네트워크

AirTag 같은 분실물 추적기는 GPS나 통신 모듈 없이 주변 기기를 중계기로 쓴다.

flowchart TB
  t["추적기: 주기적으로 블루투스 신호(바뀌는 공개키) 송출"] --> p["근처를 지나는 남의 휴대폰이 신호를 받음"]
  p --> u["자기 GPS 위치를 추적기의 공개키로 암호화해 서버에 업로드"]
  u --> o["주인 기기만 개인키로 복호화해 지도에 표시"]

• 중계한 사람도, 서버 운영자도 위치를 읽을 수 없다. 공개키를 주기적으로 바꿔 신호로 특정 추적기를 따라다니지도 못하게 한다.
• 정확도와 갱신 빈도는 주변 기기 밀도에 달렸다. 사람이 드문 곳에서는 위치가 늦게, 부정확하게 갱신된다.
• 남을 몰래 추적하는 데 악용될 수 있어, 낯선 추적기가 함께 이동하면 알려 주는 기능이 플랫폼 간 표준으로 들어갔다.

지도 이미지 비식별화

거리 사진을 공개하는 서비스는 얼굴과 번호판을 자동으로 흐린다. 전형적인 머신러닝 파이프라인 세 단계로 나뉜다.

탐지 모델은 놓치는 것(미탐)이 더 위험하므로 재현율을 높게 잡고, 신고된 이미지는 다시 처리하는 경로를 둔다.

육각형 격자로 이동 거리 근사하기

배달·호출 서비스는 「얼마나 떨어져 있나」를 초당 수많은 요청에 답해야 한다. 직선거리(하버사인 공식) 는 구면 위 최단 거리라 산·강·공원 같은 장애물을 무시해 실제 이동 거리와 크게 다를 수 있다. 외부 길찾기 API는 정확하지만 호출 비용과 응답 시간이 대량 요청에 맞지 않는다. 그 사이의 절충이 격자 위 경로 탐색이다.

위치 로그는 결측과 잡음이 많다. 같은 좌표가 반복되면 고정된 신호원(기지국·와이파이) 위치일 가능성이 있어 전처리에서 걸러 낸다. 수집 주기가 길면 경로 정보가 사라지므로, 분석 목적에 맞는 해상도로 처음부터 수집해야 한다. 목표는 완벽한 최단 경로가 아니라 충분히 그럴듯하고 빠른 근사다.

실시간 배차: 움직이는 공급과 수요 맞추기

차량 호출 배차는 주변 검색에 위치가 계속 바뀐다는 조건이 붙은 문제다. 공급(기사)도 수요(승객)도 제멋대로 움직이고, 위치 색인에 초당 수백만 건의 쓰기가 들어오며 읽기는 그 몇 배다.

기사 앱 --위치 갱신(수 초마다)--> 공급 서비스 --> 공급 위치 색인(geo by supply)
승객 요청 --> 수요 서비스 --> 배차 최적화(DISCO)
  1. 위치 색인에서 근처 후보를 거칠게 거른다(셀 단위)
  2. 경로·ETA 서비스가 직선거리가 아니라 도로망 기준 도착 시간을 계산한다
  3. ETA로 정렬해 기사에게 차례로 제안한다

호출 한 건의 흐름과 데이터

• 서비스 나누기: 승객, 기사, 배차(매칭·쿼드트리 집계), 운행, 결제, 알림, 분석 서비스로 나누고 각자 자기 데이터를 갖는다. 서비스 사이는 gRPC로, 찾기는 서비스 디스커버리·서비스 메시로 한다.
• 테이블: customers, drivers, cabs(차량 번호·차종), trips(출발지·목적지·상태), ratings(별점·의견), payments(운행 ID와 결제 정보).
• API: requestRide(customerID, source, destination, cabType, paymentMethod), cancelRide(customerID, reason?), acceptRide·denyRide(driverID, rideID), startTrip·endTrip(driverID, tripID), rateTrip(customerID, tripID, rating, feedback?).
• 위치 보고: 수 초마다 위치를 보내므로 요청마다 연결을 여는 폴링보다 WebSocket 같은 지속 연결로 받는다. 앱이 백그라운드에 있어도 GPS 위치를 보내는 백그라운드 작업이 필요하다.
• 순진한 SQL: WHERE lat BETWEEN X-R AND X+R AND lng BETWEEN Y-R AND Y+R도 동작하지만 두 범위 조건을 한 B-트리 인덱스로 함께 좁힐 수 없어 데이터가 크면 느리다. 그래서 지오해시·쿼드트리로 색인한다.
• 경쟁 조건: 승객 여럿이 동시에 같은 기사를 잡을 수 있다. 기사 배정을 뮤텍스나 DB 조건부 갱신(UPDATE drivers SET status='busy' WHERE id=? AND status='free')으로 원자적으로 만들어 한 기사가 두 호출에 배정되지 않게 한다.
• 기사 순위: 주변 후보를 거리만이 아니라 평균 별점, 과거 피드백, 관련도로 정렬해 좋은 기사에게 먼저 제안한다.
• 수요 폭증: 수요가 몰리고 공급이 모자라면 탄력 요금(surge pricing)으로 기본 요금에 배율을 붙여 수요를 줄이고 기사를 그 지역으로 끈다.
• 결제: 직접 만들지 않고 Stripe 같은 결제 대행사에 맡기고, 결제가 끝나면 대행사가 앱으로 돌려보낸다(결제 시스템 설계).
• 알림·분석: 알림은 Kafka 같은 브로커를 거쳐 FCM·APNs로 보내고(알림 시스템 설계), 이벤트는 Spark로 분석한다. 최근 위치는 Redis에 두고 LRU로 내보낸다.

기사 위치 갱신과 전파

차량 호출 설계의 핵심은 「기사 위치가 3초마다 바뀐다」는 쓰기 부하를 어떻게 받아 내느냐다.

가정: 승객 3억·기사 100만 명, 하루 활성 승객 100만·기사 50만 명, 하루 운행 100만 건, 활성 기사는 3초마다 위치를 보낸다.

• 쿼드트리만으로는 3초 갱신을 따라가지 못한다. 위치가 바뀌면 이전 칸에서 빼고 새 칸에 넣어야 하고, 칸이 한도를 넘으면 다시 쪼개야 한다. 그래서 최신 위치는 해시 테이블(DriverLocationHT)에 두고, 쿼드트리는 15초 안에 반영되도록 덜 자주 갱신한다.

• 해시 테이블 크기: 기사 ID 3B + 이전·현재 위도·경도 각 8B = 35B. 기사 100만 명이면 35MB라 메모리에 넉넉히 들어간다.

• 수신 대역폭: 기사 ID와 새 위치(3 + 16 = 19B) × 활성 기사 50만 = 3초마다 9.5MB.

• 분산: DriverLocationHT를 기사 ID로 여러 서버(기사 위치 서버)에 나눈다. 이 서버는 위치를 받으면 관련 승객에게 전파하고 쿼드트리 서버에 갱신을 알린다.

• 전파(푸시): 승객이 앱을 열면 주변 기사들을 구독시키는 발행·구독 알림 서비스를 둔다. 기사 한 명당 구독자 5명이라 하면 구독 표는 (50만 × 3B) + (50만 × 5 × 8B) ≈ 21MB, 전송량은 250만 구독 × 19B ≈ 초당 47.5MB다. 알림은 롱 폴링이나 푸시 알림으로 보낸다.

• 당겨 오기(풀): 새 기사가 승객 주변에 들어올 때마다 구독을 동적으로 더하는 것은 복잡하다. 대신 승객이 현재 위치를 보내면 서버가 쿼드트리에서 주변 기사를 찾아 돌려주는 방식으로 단순화할 수 있다.

• 재분할 완충: 칸이 한도를 넘자마자 쪼개지 않고 10% 정도 더 자라거나 줄 여유를 두면 재분할 부하가 준다.

• 공급과 수요를 「승용차·배달 같은 제품」에 묶지 않고 능력과 요구 조건으로 일반화하면, 도시·제품마다 따로 만든 배차를 한 시스템으로 합칠 수 있다.

• 배차 가능한 차만 색인하던 단순화를 버리고 모든 공급을 추적하면, 손님을 내려 줄 예정인 차까지 후보로 넣어 전체 대기 시간을 줄인다. 공항처럼 도착 순서가 중요한 곳은 가상 대기열을 따로 둔다.

• 지도 셀로 색인을 나누고 셀을 서버에 배치할 때 일관된 해싱 링 + 가십 기반 멤버십(Uber의 Ringpop, SWIM 프로토콜)을 쓰면, 서버가 늘고 줄어도 각 노드가 자기 담당 셀을 알고 요청을 주인에게 넘긴다.

• 데이터센터 장애에는 기사 앱을 상태 저장소로 쓰는 방식이 나왔다. 서버가 주기적으로 여정 상태 요약을 기사 폰에 내려 두고, 다른 데이터센터로 넘어갔을 때 폰이 그 상태를 올려 이어 가게 한다.

정리

• 주변 검색은 2차원을 색인 가능한 형태로 바꾸는 문제다. 지오해시는 접두사 검색, 쿼드트리는 밀도 적응형 메모리 트리다.
• 지오해시는 경계 때문에 이웃 칸까지 조회하고, 쿼드트리는 재구축 시간 때문에 순차 배포한다.
• 지도는 위치 수집(쓰기 폭주), 타일 서빙(정적 + CDN), 경로 계산(그래프 + 교통 예측)으로 나뉜다.
• 위치 데이터는 민감하다. 오프라인 찾기 네트워크의 종단 간 암호화와 거리 사진 비식별화가 그 예다.

관련 노트: CDN, 데이터베이스 샤딩, 웹 확장성의 구성 요소, 블록·파일·오브젝트 스토리지