배달 플랫폼의 핵심인 배차 시스템은 고객에게 음식을 빠르고 효율적으로 전달하기 위해, 수많은 주문과 라이더 사이에서 최적의 조합을 찾아내는 복잡한 시스템입니다. 이 최적화 과정에서 '거리'는 매우 중요한 변수입니다.
이번 글에서는 배차에 활용되는 거리를 단순한 직선거리에서 실제 도로망을 고려한 실거리(Real-distance)로 고도화했던 프로젝트 경험을 공유하고자 합니다. 이 과정에서 이벤트 드리븐 아키텍처(EDA)를 도입하고, 대량의 트래픽을 효율적으로 처리하기 위해 OSRM, Kafka, Redis를 어떻게 활용했는지 그 여정과 기술적 고민들을 상세히 풀어보겠습니다. 유사한 대규모 트래픽 및 위치 기반 서비스를 개발하시는 분들께 실질적인 도움이 되기를 바랍니다.
1. 배차 시스템과 '실거리'의 중요성
배차 시스템이란?
배차 시스템의 목표는 간단합니다. "수많은 주문을 가장 효율적으로 처리할 수 있는 라이더에게 배정하는 것"입니다. 여기서 '효율적'이라는 것은 단순히 빠른 것만을 의미하지 않습니다. 라이더의 현재 위치, 이동 수단(오토바이, 자전거 등), 이미 수행 중인 다른 배달 건, 그리고 새로 배정될 배달의 픽업지와 전달지 위치 등 수많은 요소를 종합적으로 고려해야 합니다.
만약 5만 개의 배달과 5만 명의 라이더가 있다면, 이론적으로 25억 건의 가능한 조합이 생깁니다. 이 모든 경우의 수를 매번 계산하는 것은 불가능하므로, 배차 시스템은 수리 최적화(Mathematical Optimization) 기법을 사용하여 이 문제를 해결합니다.
최적화를 위한 수치화, 그리고 거리의 역할
수리 최적화 알고리즘이 작동하려면, 라이더의 상태와 배달 수행 경로의 효율성을 수치적인 '비용(Cost)'으로 모델링해야 합니다. 이 비용을 계산하는 데 가장 중요한 속성은 다음과 같습니다.
- 라이더의 평균 이동 속도
- 라이더가 이미 수행 중인 배달들의 남은 거리 및 예상 소요 시간
- 라이더가 새로 배차받을 배달들의 예상 이동 거리 및 소요 시간
결국, 라이더가 배달을 어떤 순서로, 얼마나 빠르게 수행할 수 있는지를 정확하게 예측하는 것이 배차의 핵심이며, 이 예측의 기반이 되는 것이 바로 '거리' 데이터입니다.
왜 '실거리'가 중요할까?
배달 도메인에서 거리는 매우 민감한 문제입니다. 라이더는 제한된 시간 안에 효율적인 동선으로 최대한 많은 배달을 수행하고자 합니다. 배차 시스템이 제안하는 경로의 거리가 비현실적이라면, 라이더의 수락률이 떨어지고 배차 효율도 저하될 수 있습니다.
- 직선거리의 한계: 직선거리는 실제 도로망(일방통행, 강, 건물 등)을 전혀 고려하지 못해, 실제 이동 거리와 큰 오차를 보일 수 있습니다.
- 정확도와 일관성의 필요성: 배차 최적화 알고리즘에 입력되는 거리값이 정확하고 일관되어야만, 시스템은 더 효율적이고 현실적인 배달 경로를 생성하고 최적의 배차 조합을 찾을 수 있습니다.
- 나비효과: 두 지점 간 거리 계산의 작은 오차는, 수많은 배달과 라이더 조합으로 이루어진 전체 배차 시스템에서는 예측 불가능한 비효율과 성능 저하라는 큰 결과로 이어질 수 있습니다. 마치 나비효과와도 같죠.
따라서, 배차의 정확도와 시스템 성능을 모두 향상시키기 위해, 우리는 직선거리 대신 실제 도로망을 반영한 '실거리' 데이터를 활용하는 시스템을 구축하기로 결정했습니다.
🤔 꼬리 질문: 배차 시스템 외에, 실시간 '실거리' 데이터가 서비스 품질에 결정적인 영향을 미치는 다른 도메인에는 어떤 것들이 있을까요? (예: 차량 호출 서비스, 물류/배송 경로 최적화 등)
2. 대규모 실거리 계산을 위한 아키텍처 설계
한 번의 배차에는 몇 번의 실거리 계산이 필요할까?
배차 시스템은 최적의 조합을 찾기 위해, 주말 피크 시간 기준 분당 약 15만~20만 건의 잠재적인 배달 경로를 계산합니다. 라이더가 한 번에 여러 배달을 수행하는 '묶음 배달'을 고려하면, 필요한 실거리 계산 횟수는 기하급수적으로 늘어납니다.
- 신규 배달 1건 배차 시: C(2, 2) = 1개의 간선 (픽업지 → 전달지)
- 신규 배달 2건 배차 시: C(4, 2) = 6개의 간선
- 신규 배달 3건 배차 시: C(6, 2) = 15개의 간선
만약 분당 20만 건의 경로 계산에서 평균적으로 2건의 배달을 고려한다면, 시스템은 분당 120만 건 (20만 * 6), 초당 약 2만 건의 실거리 계산을 수행해야 합니다. 이는 TPS(Transaction Per Second) 기준으로도 매우 높은 수준입니다.
어떤 내비게이션을 사용할까? OSRM의 선택
초당 수만 건에 달하는 경로 계산을 위해 API 호출마다 비용이 발생하는 상용 내비게이션을 사용하는 것은 현실적으로 불가능했습니다. 따라서 우리는 비용 효율적이면서도 우리나라 지리 정보가 잘 반영된 오픈소스 경로 탐색 엔진인 OSRM(Open Source Routing Machine)을 선택했습니다. OSRM은 공개된 지도 데이터(예: OpenStreetMap)를 기반으로 경로와 거리를 제공하며, 사내 공통 지도 서비스 플랫폼을 통해 안정적인 API 형태로 사용할 수 있었습니다.
중요! 이 글에서 다루는 '실거리'는 배차 최적화를 위한 예측 거리이며, 실제 라이더에게 지급되는 배달료 책정에 사용되는 공식 수행 거리와는 다릅니다. 배달료 산정 등 민감한 부분에는 일반적으로 검증된 상용 내비게이션이 사용됩니다.
거리를 저장해서 활용해야만 하는 이유
OSRM을 사용하더라도, 초당 수만 건 이상의 부하는 신중하게 다뤄야 합니다. 실제 배차 환경에서는 가까운 거리의 배달들이 짧은 시간 내에 여러 라이더에게 다양한 조합으로 고려되는 경우가 많습니다. 이는 동일한 두 지점 간의 거리 계산 요청이 중복으로 발생할 가능성이 매우 높다는 것을 의미합니다.
따라서 매번 실시간으로 모든 거리를 계산하는 대신, 미리 계산한 거리 데이터를 효율적으로 저장하고 재활용하는 아키텍처를 설계하는 것이 필수적이었습니다.
3. 이벤트 드리븐 아키텍처(EDA) 기반의 실거리 데이터 관리
우리는 배달의 생명주기(Lifecycle)에 따라 발생하는 이벤트를 기반으로 실거리 데이터를 관리하는 이벤트 드리븐 아키텍처(EDA)를 도입했습니다. 배달 처리 시스템은 배달의 다양한 상태 변경(생성, 위치 변경, 완료, 취소 등)을 Kafka를 통해 이벤트로 발행합니다.
배달의 라이프사이클에 따른 거리 계산 전략
실거리 시스템은 모든 이벤트를 수신하는 것이 아니라, 거리 계산에 직접적으로 필요한 이벤트만을 선별하여 처리합니다.
| 배달 이벤트 | 실거리 시스템의 처리 로직 |
|---|---|
| 배달 생성 (DeliveryCreated) | • (픽업지 ↔ 전달지) 거리 계산 및 저장 • (픽업지/전달지 ↔ 해당 지역 내 다른 모든 배달 위치) 거리 계산 및 저장 |
| 픽업지/전달지 변경 | • 변경된 위치를 기준으로 위와 동일한 거리 계산 및 저장 (기존 위치 관련 거리는 제거) |
| 배달 완료/취소 | • 해당 배달의 위치(픽업/전달지)가 더 이상 다른 배달과 묶일 필요가 없으므로, 관련 거리 데이터를 저장소에서 제거. |
이러한 로직은 EventProcessorFactory와 같은 패턴을 사용하여, 각 이벤트 타입에 맞는 적절한 프로세서가 실행되도록 구현했습니다.
Kafka 스트림 리파티션: 지역별 순서 보장을 위하여
배달 이벤트는 기본적으로 '배달 ID'를 키로 하여 Kafka에 발행됩니다. 하지만 실거리 계산 로직은 '지역' 단위로 순서가 보장되어야 정확하게 동작합니다. 예를 들어, 같은 지역에서 발생한 '배달 A 생성' 이벤트와 '배달 B 완료' 이벤트의 처리 순서가 뒤바뀌면, '배달 A'에 대한 거리 계산 시 이미 완료된 '배달 B'의 위치 정보가 포함되거나, 반대로 아직 필요한 '배달 B'의 거리 정보가 먼저 삭제되는 등의 데이터 정합성 문제가 발생할 수 있습니다.
이 문제를 해결하기 위해, 우리는 Kafka 스트림을 그대로 소비하지 않고 리파티션(Repartition) 작업을 수행했습니다. 즉, 수신한 배달 이벤트의 키를 '배달 ID'에서 '지역 ID'로 변경하여 새로운 토픽으로 재발행했습니다.
이를 통해, 동일한 지역에서 발생한 이벤트들은 Kafka의 파티션 내 순서 보장 특성에 따라 실거리 컨슈머에게 순차적으로 전달됩니다. 덕분에 배달의 라이프사이클에 맞춰 지역별 거리 데이터의 생성과 제거가 정확하게 이루어질 수 있었습니다.
🤔 꼬리 질문: 이벤트 드리븐 아키텍처에서 이벤트 처리의 순서 보장이 중요한 이유는 무엇일까요? Kafka 외에 메시지의 순서를 보장할 수 있는 다른 기술이나 패턴에는 어떤 것들이 있을까요?
4. 실거리는 어떻게 효율적으로 저장할까? Redis 성능 최적화 여정
실거리 데이터는 배달의 라이프사이클 동안만 단기간 활용되므로, 빠른 읽기/쓰기가 가능한 인메모리 저장소인 Redis(AWS ElastiCache for Redis)를 저장소로 선택했습니다. 하지만 거대한 트래픽을 처리하며 Redis를 사용하는 과정에서, 저장 용량과 네트워크 대역폭이라는 두 가지 큰 제약 사항과 마주하게 되었습니다.
시도 1: 지역별 실거리 그래프를 단일 String으로 저장 (그리고 실패)
초기 아이디어는 배차가 지역 단위로 이루어진다는 점에 착안하여, 각 지역별로 모든 위치 간의 실거리 정보를 하나의 그래프 데이터로 묶어 Redis String 타입에 저장하는 것이었습니다.
- Key:
region:{지역 ID} - Value:
{"37.1,127.1-37.2,127.2": 5612, "37.1,127.1-37.3,127.3": 2311, ...}(JSON 형태의 문자열)
이 구조는 인터페이스가 직관적이라는 장점이 있었지만, 데이터가 커질수록 치명적인 단점이 드러났습니다. 특정 거리 하나만 조회하거나 갱신하려 해도, 해당 지역의 전체 데이터를 한꺼번에 읽고(GET), 수정한 뒤, 다시 통째로 써야(SET) 했습니다.
매번 전체 데이터를 주고받다 보니 네트워크 대역폭 사용량이 급증했고, ElastiCache 인스턴스의 네트워크 대역폭 한계를 초과할 위험이 커졌습니다. 데이터 압축(Zstd)을 시도했지만, 원본 데이터 자체가 워낙 커서 압축만으로는 근본적인 해결책이 될 수 없었습니다.
시도 2: Redis 자료구조 활용 (Hash 타입으로의 전환)
문제의 근본 원인은 자료구조에 있었습니다. 우리는 단일 String 대신 Redis Hash 자료구조를 활용하여 구조를 변경했습니다.
- Key:
region:{지역 ID} - Hash Field:
{출발지 좌표}-{도착지 좌표}(예:"37.1,127.1-37.2,127.2") - Hash Value:
{실거리 값}(예:5612)
이 구조로 변경함으로써 얻은 이점은 명확했습니다.
- 네트워크 효율성: 매번 전체 데이터를 주고받을 필요 없이,
HGET,HSET,HDEL등의 명령어로 필요한 필드에만 개별적으로 접근할 수 있어 네트워크 송수신 데이터량을 획기적으로 줄였습니다. - 메모리 효율성: 거리 값을 숫자(Integer) 형태로 저장할 수 있게 되어, 문자열로 저장할 때보다 메모리 사용량을 더욱 효율적으로 관리할 수 있었습니다.
- 다중 필드 접근 최적화:
HMGET,HMSET등 다중 인자를 받는 커맨드를 활용하여 여러 필드에 대한 작업을 한 번의 네트워크 왕복으로 처리함으로써 오버헤드를 줄였습니다. (단, 시간 복잡도는 O(N)이므로 한 번에 너무 많은 인자를 전달하지 않도록 적절한 크기로 청크(Chunk) 처리)
Redis 성능 추가 최적화
EXPIRE커맨드 줄이기: 초기에는 데이터 정합성을 위해 모든 쓰기 작업에 TTL(Time-To-Live)을 설정했지만, 이는 불필요한EXPIRE명령을 유발하여 네트워크 비용과 CPU 리소스를 낭비하는 원인이었습니다. 이 방식을 배달이 완료/취소되는 시점에 명시적으로HDEL을 통해 데이터를 삭제하는 방식으로 변경하여, 불필요한 네트워크 트래픽과 리소스 낭비를 줄였습니다.- 쓰기 분산을 위한 Redis 클러스터 모드 적용: 실거리 시스템은 쓰기 트래픽이 많기 때문에, 단일 Primary 노드에 모든 쓰기 작업이 집중되는 마스터-레플리카(Master-Replica) 모드보다는 클러스터 모드가 더 적합했습니다. 클러스터 모드는 키(지역 ID)를 해시 슬롯에 분산시켜 여러 Primary 노드가 쓰기 작업을 분산 처리하므로, 쓰기 병목 현상을 해결하고 수평적 확장을 용이하게 합니다.
마무리
지금까지 배차 시스템에서 OSRM, Kafka, Redis를 활용하여 대규모 트래픽을 처리하는 이벤트 기반 실거리 시스템을 개발하고 최적화했던 과정을 공유드렸습니다.
이번 프로젝트를 통해 Kafka 기반의 이벤트 드리븐 아키텍처를 실무에 깊이 있게 적용하고, Redis를 활용한 대규모 트래픽 처리 및 성능 최적화에 대한 귀중한 경험을 얻을 수 있었습니다. 또한, 더 정확한 거리 데이터를 기반으로 라이더분들의 효율적인 배달 수행을 지원함으로써, 배차 효율 향상에 직접적으로 기여할 수 있었습니다.
저희의 경험과 사례가 비슷한 기술적 도전을 마주하고 있는 분들의 서비스 개선에 조금이나마 도움이 되기를 바랍니다. 긴 글 읽어주셔서 감사합니다.
