Uber — H3 육각 격자와 실시간 배차 매칭

애니메이션이 보여주는 것

평시 루프부터 시작한다 — 운전자 앱이 약 4초마다 GPS를 보내고(인덱스는 초당 백만 건 쓰기 목표), 좌표가 셀 ID로 변환되고, 셀 ID를 샤딩 키로 Ringpop consistent hash ring이 담당 샤드를 정해 기록한다. 호출이 오면 DISCO가 승객 중심 원을 덮는 이웃 셀들을 계산하고, 담당 샤드들을 병렬 질의해 근처 차량을 모은 뒤 도로망 기반 ETA로 평가한다 — 곧 운행이 끝날 차까지 후보에 넣는다.

후반부는 세 겹의 장애다. 샤드 크래시는 SWIM gossip이 수 초 내 감지해 키 범위를 재배치하고(crash-only 철학 — 크래시 복구 경로가 곧 정상 경로), 운전자 연결이 끊기면 위치 신선도를 잃어 매칭에서 제외되며, DC 전체가 죽으면 운전자 폰이 들고 있던 암호화 State Digest를 백업 DC에 올려 진행 중 trip을 복원한다.

왜 육각형인가 — 그리고 펜타곤 12개

육각형은 모든 이웃 셀 중심까지의 거리가 한 종류다. 정사각형은 변 이웃과 대각 이웃의 거리가 다르고(2종), 삼각형은 3종이다. 거리가 균일하면 거리 기반 분석이 단순해지고, surge pricing에서 인접 셀 간 가격 그라디언트가 매끄러워진다.

다만 구를 육각형만으로 덮을 수는 없다. H3는 정이십면체 투영 위에 해상도 0의 베이스 셀 122개를 놓는데, 모든 해상도에서 정확히 12개의 펜타곤이 생기고 이들은 전부 바다에 배치돼 실사용에서 마주칠 일을 줄였다. 해상도는 0~15로, 한 단계 내려갈 때마다 면적이 1/7이 되고(aperture 7), 해상도 15는 약 569조 개 셀(평균 약 0.9m²)에 이른다. 인덱스는 64비트 정수 하나라 비트 절단만으로 부모 셀을 얻는다.

왜 R-tree가 아니라 셀 샤딩인가

초당 백만 건 쓰기를 단일 공간 인덱스가 감당할 수 없다. 셀 ID를 샤딩 키로 쓰면 쓰기가 자연스럽게 분산되고, '반경 내 검색'은 이웃 셀들의 담당 샤드에 대한 병렬 키 조회로 바뀐다. 샤드 배치는 Ringpop consistent hash ring이 정하고, 멤버십은 SWIM gossip으로 중앙 코디네이터 없이 전파된다(AP 선택).

노드 간 통신은 TChannel(Thrift 기반 양방향 RPC)로, HTTP/JSON 대비 약 20배 빠르고 파이프라이닝으로 head-of-line blocking을 피한다. 느린 서버가 만드는 꼬리 지연은 backup request with cross-server cancellation — 두 서버에 경주를 붙이고 먼저 온 응답만 취하는 방식 — 으로 누른다.

• 셀 ID = 샤딩 키(geosharding): 쓰기 자연 분산, 읽기는 복제본 확장
• Ringpop: consistent hash ring + SWIM gossip, 중앙 코디네이터 없음(AP)
• 요청은 멱등하게 설계 — 노드가 죽어도 재시도로 흡수
• crash-only: graceful shutdown 경로를 따로 두지 않는다