배차 정확도를 높이는 실거리 시스템 구축하기: OSRM, Redis, 그리고 Kafka

5 hours ago 1

들어가며

배민커넥트 배차시스템에서는, 배차에 활용되는 거리를 단순한 직선거리에서 실제 경로 기반의 실거리로 고도화하는 작업을 진행했습니다. 고도화 과정에서 이벤트 드리븐 설계를 도입하고 대량 대량의 트래픽을 효율적으로 처리하기 위해 Redis를 다방면으로 활용했습니다. 이 글은 배차시스템팀에서 얻은 경험과 지식을 정리한 것으로, 유사한 서비스를 개발하시는 분들께 많은 도움이 되는 글이 되었으면 좋겠습니다.

ㅤ

배차시스템이란?

배차시스템 소개

배차시스템은 배달을 고객에게 전달할 수 있도록 적합한 라이더를 찾아 배정하는 시스템입니다. 따라서 주문과 라이더의 상태, 그리고 특성을 잘 고려해 빠르고 효율적으로 배차하는 것이 중요합니다.

ㅤ

5만 개의 배달이 존재하고 5만 명의 라이더가 활동 중이라고 가정했을 때, 단순히 경우의 수를 계산하면 배차시스템은 25억 건의 계산을 수행해야 합니다. 그러나 현실적으로 매 배차 사이클마다 25억 건을 모두 계산하는 것은 불가능하므로, 이를 최적화하는 과정을 거치게 됩니다. 따라서 배차시스템은 다음과 같은 과정을 통해 배차를 최적화합니다.

ㅤ

라이더의 상태를 수치화하는 방법

앞서 소개드린 배차 과정에서는 ‘비용 계산’이라는 용어가 등장합니다. 배차 최적화 과정은 배달과 라이더의 매칭 문제를 수리 최적화로 해결하기 때문에, 현재 라이더의 상태와 신규 배차를 반영한 상태 변화를 수치적으로 모델링해야 합니다. 배달과 라이더의 특성에는 다양한 속성이 있지만, 그중 가장 중요한 속성은 다음과 같습니다:

라이더의 속도
라이더가 이미 수행 중인 배달들의 거리 및 소요 시간
라이더가 새로 배차받을 배달들의 예상 거리 및 소요 시간

이 세 가지 속성을 종합해보면, 결국 라이더가 배달을 어떤 순서로, 얼마나 빠르게 수행하는지가 배차에서 매우 중요한 요소가 됩니다.

다음은 오토바이 라이더와 자전거 라이더가 동일한 경로를 수행하는 예시입니다.

ㅤ

A와 B 두 개의 배달 건을 위와 같은 순서로 평균 시속 30km로 주행하는 오토바이 라이더가 수행한다면, 주행 시간만 약 4분 36초가 걸립니다. 같은 상황에서 평균 시속 5km인 자전거 라이더가 수행한다면 약 13분 48초가 걸립니다. 그러나 오토바이 라이더가 더 빠르게 배달을 수행할 수 있다고 해서 무조건 오토바이 라이더에게 배차하는 것이 좋은 것은 아닙니다. 배달이 많은 상황에서는 오토바이 라이더와 자전거 라이더를 모두 활용해, 시스템 입장에서 최대한 효율적인 조합을 찾아 배차해야 합니다. 따라서 최적화 알고리즘의 입력으로 활용하기 위해, 라이더가 수행할 것으로 예상되는 배달의 진행 순서를 시퀀스화해 수치화 작업을 진행하게 됩니다.

이 글의 주제가 되는 실거리는, 이러한 수치화 작업의 성능과 정확도를 좌우하는 중요한 요소입니다. 이어서 배차시스템의 경로 문제를 설명하면서, 실거리의 중요성에 대해 자세히 이야기해보겠습니다.ㅤ

왜 실거리가 중요할까?

배차시스템의 경로 문제

배달 진행 순서의 시퀀스, 다시 말해 라이더가 배달을 수행하기 위한 위치들의 순서를 경로라고 부릅니다.

여기서 ‘배달을 수행하기 위한 위치’란 배달의 픽업지와 전달지를 의미합니다. 그렇다면, 한 명의 라이더가 배달을 수행하는 과정에서 가능한 경로의 경우의 수는 몇이나 될까요? 배달의 진행 상태와 배달 개수에 따라 가능한 경로는 매우 다양하게 달라집니다.

경로를 계산하기 위해 그래프를 한 번 그려보면, 꽤 많은 간선이 만들어집니다. 라이더에게 할당된 신규 배달이 N개라고 했을 때, 정점과 간선의 수는 다음과 같습니다.

정점: 픽업지와 전달지를 모두 거쳐야 하므로 2N개
간선: C(2N, 2)개

이때 그려본 것은 하나의 조합(라이더:매칭=1:1)에 대한 그래프에 불과합니다. 실제 최적화 과정에서는 한 명의 라이더가 수행할 수 있는 여러 배달 조합(라이더:매칭=1:N)에 대해서도 모두 수치화를 해보아야 합니다. 즉, 라이더당 배차 가능한 모든 배달 조합에 대해 경로를 계산하고 수치화하여 최적화 알고리즘에 전달해야 합니다. 그리고 이 수치화를 위해서는 각 간선에 대한 거리값을 반드시 알아야 합니다.

ㅤ

거리는 예민한 문제이다

배달 도메인에서 거리는 예민한 문제입니다. 라이더분들은 짧은 시간과 짧은 이동 거리로 최대한 많은 배달을 수행해야 하기 때문입니다. 다만 한 가지 강조할 것은, 배차 경로에서의 거리는 실제 배달료를 책정하는 데 사용되는 수행 거리는 아니라는 점입니다.

참고: 배달료 책정이나 배민커넥트 앱상에서 활용되는 거리 계산에는 상용 내비게이션이 사용됩니다.

그럼에도 거리는 중요합니다. 배차 최적화를 하려면, 거리값이 정확하고 일관돼야 합니다. 거리를 기반으로 효율적인 경로를 만들어보고, 그 경로를 기반으로 한 수치들이 최적화에 사용됩니다. 그러므로 단순히 직선거리로 셈하기보다는 가능한 현실 세계에 가까운 거리를 사용할 수 있어야 합니다.

ㅤ

작은 변화가 배차시스템 전체의 성능을 좌우한다

두 지점 간의 거리를 계산하는 일은 얼핏 단순해 보일 수 있습니다. 하지만 수많은 경우의 수에 따른 경로를 고려해야 하기 때문에, 작은 변화도 배차시스템 성능에 큰 영향을 미칠 수 있습니다. 마치 나비효과와도 같죠. 배차해야 할 배달이 많아질수록 이러한 영향은 더욱 커집니다. 이처럼 직선거리에서 실거리로의 전환은 단순한 변화가 아니라, 배차 전반의 효율성과 정확도에 영향을 미치는 중요한 변화가 될 수 있습니다.

지금까지 배차시스템에서 실거리가 왜 중요한지 설명드렸습니다. 배차시스템은 한 번의 배차 과정에서 필요한 모든 간선의 실거리를 계산합니다. 이 실거리는 배차의 정확도를 결정짓는 중요한 요소입니다. 하지만 작은 변화만으로도 시스템 성능이 쉽게 저하될 수 있는 민감한 부분이기도 합니다. 따라서 배차의 정확도와 성능을 모두 고려하기 위해 실거리 시스템을 도입했던 과정을 소개합니다.

ㅤ

배차시스템에서 실거리를 계산하는 방법

한 번의 배차에는 몇 번의 실거리 계산이 필요할까?

배차시스템은 라이더분들에게 배차 요청을 하기 위해 주말 피크 시간 기준 분당 약 15만~20만 건의 경로를 계산합니다. 만약 모든 라이더가 무배차 상태이고, 1건의 배달을 배차한다면 각 경로마다 1건의 배달 위치 간 실거리가 필요합니다.

n=1, C(2, 2) = 1

알뜰배달 서비스가 론칭된 이후부터는 라이더가 1개 이상의 배달을 한 번에 수행할 수 있게 되었습니다. 예를 들어, 라이더가 이미 1건의 배달을 수행 중인 상태에서 시스템이 1건을 추가 배차하는 상황이나, 한 번에 2건을 배차하는 상황이라면 6건의 실거리가 필요하고, 한 번에 3건을 배차하는 상황이라면 15건의 실거리가 필요합니다.

n=2, C(4, 2) = 6
n=3, C(6, 2) = 15

물론, 반대 방향의 경우도 고려하면 계산해야 하는 거리는 2배가 됩니다. 실제로 A-B 거리와 B-A 거리는 다르지만, 이 포스팅에서는 동일하다고 가정하고 해당 내용은 다루지 않겠습니다.

만약 시스템이 모든 라이더를 대상으로 2건의 배달 경로를 계산해야 하고, 주말 피크 기준 분당 20만 건의 경로를 계산해야 한다면, 시스템은 분당 600만 건의 실거리 계산을 수행해야 하며, 초당 약 10만 건으로 시스템 성능이 중요 지표인 TPS(Transaction Per Second) 기준으로도 매우 높은 수준입니다.

배달들의 위치 사이의 거리를 직선거리가 아닌 실제 거리로 반영하려면 내비게이션이 필요합니다. 실거리 계산이 분당 수백만 건에 이르는 만큼, 이를 뒷받침할 수 있는 내비게이션 시스템이 필요했습니다.

어떤 내비게이션을 사용할까?

배달의민족의 딜리버리플랫폼은 여러 기능에서 상용 내비게이션을 활용합니다. 예를 들어, 배달료 계산이나 배달 수행 중 이동 경로 추천 기능 등이 있습니다. 하지만 초당 10만 건에 달하는 경로 계산을 위해 API 호출마다 비용이 발생하는 상용 내비게이션을 사용하는 것은 현실적으로 어렵습니다. 게다가 배차를 추천받은 라이더분이 바로 수락하는 경우, 한 번 계산한 거리를 오랜 시간 재활용하기도 쉽지 않습니다.

이번 배차 실거리 프로젝트는 배차 정확도와 시스템 성능을 동시에 높이기 위해 기획되었습니다. 단순히 직선거리를 사용하는 대신, 실제 경로를 고려한 실존 거리를 활용하면 기존보다 더욱 현실적인 수행 거리와 시간을 기반으로 배차 최적화를 할 수 있다는 가정에서 시작되었습니다.

비용 문제를 고려하여 상용 내비게이션 대신, 우리나라 지리 정보가 잘 반영되고 최신화와 업데이트가 빈번하고, 오픈소스 지도 API 중 가장 성능이 좋다고 알려진(Open Source Routing Machine, Project OSRM)을 선택하게 되었습니다. OSRM은 공개된 지도 데이터 정보를 기반으로 경로를 제공하는 엔진입니다. 공통시스템팀에서 여러 지도 서비스를 필요에 따라 제공하기 위해 운영하는 지도 미디에이터 서비스 덕분에, 안전하고 편리하게 API 방식으로 OSRM 실거리를 받아올 수 있었습니다.

앞서 언급했지만 중요한 내용이기에 다시 한번 강조드립니다.
배달료 책정이나 배민커넥트 앱상에서 활용되는 거리 계산에는 상용 내비게이션이 사용됩니다.

다음 그림은 OSRM 지도 상 한 지점에서 다른 지점으로 이동하는 동선의 예시입니다.

ㅤ

거리를 저장해서 활용해야만 하는 이유?

오픈소스 지도를 활용하더라도 여전히 초당 10만 TPS 수준의 부하는 신중히 고민해야 합니다. 현실적인 배차 상황에서는 다음 그림과 같이 여러 라이더에게 다양한 배달 조합이 고려되어 경로가 계산됩니다.

또한, 한 번의 배차로 라이더분이 바로 수락하여 배달이 수행되는 경우가 드물어, 한 번 경로가 계산된 배달도 평균 3~5회 정도 다른 조합으로 재계산되는 경우가 많습니다. 이처럼 매번 거리를 재계산하면 중복된 요청이 다수 발생하고, 중복 요청까지 포함된 초당 10만 건의 TPS를 OSRM 서버가 모두 처리해야 하므로 OSRM 서버에 과도한 부하가 발생하게 됩니다.

앞서 살펴본 배차 예시에서 활용된 모든 배달 간 실거리를 미리 구하면, 위와 같은 그림으로 표현할 수 있습니다. 실제 배차 환경에서는 가까운 거리의 배달들이 짧은 시간 내에 여러 번 반복되기 때문에, 유사한 조합의 배차가 자연스럽게 여러 차례 발생할 수밖에 없습니다. 그리고 유사한 조합의 배차가 반복된다면, 동일한 거리를 재사용할 가능성이 높아집니다. 따라서 매번 필요한 실거리를 실시간으로 모두 계산하는 데 리소스를 쏟기보다는, 보다 효율적인 방식으로 미리 계산한 거리 데이터를 저장하고 재활용하는 방안을 고민하게 되었습니다.

이러한 이유로 시스템 아키텍처를 설계할 때, 거리 데이터의 재활용을 적극 고려하여 진행했습니다.

ㅤ

이벤트 드리븐 아키텍처 기반 실거리 데이터 관리

배달의 라이프 사이클에 따라 거리를 저장해보자

배달의민족의 딜리버리플랫폼에서 수행되는 배달의 라이프 사이클은 다음과 같습니다.

또한 배달의 상태와 직접적으로 연관되지는 않지만, 전달 위치 변경이나 조리 완료 등 배달 수행에 중요한 정보가 변경되는 상황에서도 이벤트가 발행됩니다. 배달 처리 시스템은 이러한 다양한 상태 변경 사항을 Kafka를 통해 이벤트로 발행합니다.

하지만 거리 계산을 위해 모든 배달 상태 변경 이벤트를 수신할 필요는 없습니다. 따라서 거리 계산에 필요한 배달 생성, 위치 변경, 배달 완료, 배달 취소 이벤트만을 수신하여 도메인 로직을 처리합니다.

ㅤ

각 이벤트에서 처리해야 할 내용을 간단히 정리하면 다음과 같습니다:

배달이벤트 거리 계산

배달 생성 (DeliveryCreated)	• 픽업지 → 전달지 거리 계산 • 픽업지 → 지역 내 모든 픽업지, 전달지 거리 계산 • 전달지 → 지역 내 모든 픽업지, 전달지 거리 계산
픽업지 변경 (PickupLocationChanged)	• 변경된 픽업지 → 전달지 거리 계산 • 변경된 픽업지 → 지역 내 모든 픽업지, 전달지 거리 계산
전달지 변경 (DeliveryLocationChanged)	• 변경된 전달지 → 픽업지 거리 계산 • 전달지 → 지역 내 모든 픽업지, 전달지 거리 계산
배달 완료 (DeliveryDelivered) / 배달취소 (DeliveryCanceled)	• 지역 내 동일 위치가 더이상 존재하지 않는 경우 • 픽업지 → 지역 내 모든 픽업지, 전달지 거리 제거 • 전달지 → 지역 내 모든 픽업지, 전달지 거리 제거

ㅤ

위 표에 정리한 내용을 각 이벤트 프로세서를 나누어 수행하도록 EventProcessorFactory를 정의합니다.

public class EventProcessorFactory { public EventProcessor create(Event<?> event) { switch (event.getEventType()) { case DeliveryCreated.EVENT_TYPE: return new DeliveryCreatedProcessor(DeliveryCreatedSpec.from(event), ...); case PickupLocationChanged.EVENT_TYPE: return new PickupLocationChangedProcessor(PickupLocationChangedSpec.from(event), ...); case DeliveryLocationChanged.EVENT_TYPE: return new DeliveryLocationChangedProcessor(DeliveryLocationChangedSpec.from(event), ...); case DeliveryDelivered.EVENT_TYPE: return new CompletedDeliveryProcessor(DeliveryStatusChangedSpec.from(event), ...); case DeliveryCanceled.EVENT_TYPE: return new CanceledDeliveryProcessor(DeliveryStatusChangedSpec.from(event), ...); default: throw new IllegalArgumentException("..."); } } }

ㅤ

이벤트는 Kafka를 통해 발행되므로, Kafka 컨슈머가 각 이벤트를 수신하여 처리합니다. 다음은 각 이벤트에 따라 EventProcessorFactory를 사용해 적절한 이벤트 프로세서를 반환하고, 로직을 수행하는 예제 코드입니다.

public class EventConsumer { private static final List<String> SUPPORTED_EVENT_TYPES = List.of(...); @KafkaListener(topics = "...", groupId = "...", containerFactory = ...) public void consume(Message<Event<?>> message, Acknowledgment acknowledgment) { if (!SUPPORTED_EVENT_TYPES.contains(event.getEventType())) { acknowledgment.acknowledge(); return; } EventProcessor processor = processorFactory.create(event); processor.execute(); acknowledgment.acknowledge(); } }

ㅤ

이와 같이 발행되는 모든 이벤트를 무작정 수신하지 않고, 프로세서가 정의된 이벤트 타입, 즉 컨슈머 도메인의 관심사에 해당하는 이벤트만 처리하도록 명확히 구분할 수 있습니다. 또한, 관심 없는 이벤트는 조기에 리턴하여 처리하지 않음으로써 성능 향상에도 기여할 수 있습니다.

ㅤ

Kafka 스트림 리파티션

배달 처리 후에는 배달 ID가 키로 구성된 이벤트가 발행됩니다. 만약 배달 이벤트를 실거리 컨슈머가 그대로 받아 처리한다면 어떤 문제가 발생할까요?

예를 들어, 하나의 지역에서 여러 배달이 동시에 생성된다면, 어떤 이벤트는 처리가 완료되었음에도 결과가 저장되지 못할 수도 있습니다. 즉, 나중에 들어온 배달 이벤트로 트리거된 작업이 직전에 들어온 배달 데이터를 포함하지 못하는 상황이 발생할 수 있는 것입니다.

ㅤ

Kafka는 기본적으로 각 파티션에 들어오는 이벤트를 오프셋 기반으로 처리하기 때문에, 동일 파티션 내 이벤트는 순차로 처리됩니다. 배달 이벤트를 지역별로 순차 처리하려면, 이벤트 키를 배달 ID가 아닌 배달이 속한 지역 ID로 변경해야 합니다. 이에 따라 이벤트 처리 기준을 변경하는 리파티션 작업을 자체적으로 수행하여, 지역별 배달 이벤트가 순서를 유지하며 처리되도록 재발행했습니다.

리파티션된 이벤트를 처리하면, 배달 생성, 픽업 완료, 배달 취소와 같은 이벤트들이 순서가 꼬이지 않고 처리됩니다. 이를 통해 배달의 라이프사이클에 맞춰 지역별 거리 계산과 데이터 제거가 정확하게 이루어질 수 있습니다.

ㅤ

실거리는 어떻게 효율적으로 저장할까

실거리 저장소에서의 제약 사항

실거리는 배달의 라이프사이클에 따라 단기간 활용되는 데이터이기 때문에, 빠른 읽기/쓰기가 가능한 인메모리 저장소인 Redis(AWS ElastiCache Redis)를 저장소로 사용하고 있습니다. 거대한 트래픽의 실거리 문제를 해결할 때 큰 제약 사항은 Redis의 저장 용량과 네트워크 대역폭이었습니다. 이를 극복하기 위해 자료 구조와 데이터 형식 등을 다양하게 변경하며 여러 시행착오를 겪었습니다.

ㅤ

지역별로 실거리 그래프를 관리한다면

배차시스템에서는 동일한 지역에 속한 배달들끼리 묶어 배차를 수행합니다. 따라서 서로 묶일 수 있는 배달들 간의 실거리만 모아 관리하는 것이 효율적입니다. 예를 들어, 종로구에 있는 가게와 송파구에 있는 가게 간의 거리를 계산할 필요는 없습니다. 그렇다면 아래와 같이, 각 지역별로 실거리 그래프를 저장하는 방법은 어떨까요?

위 방식은 인터페이스가 간단하고 직관적이라는 장점이 있습니다. 다만, 한 지역 내 모든 실거리를 하나의 데이터로 저장하려면 다음 세 가지 정보를 모두 포함할 수 있는 구조화된 형식이 필요합니다.

첫 번째 지점의 좌표 (위도, 경도)
두 번째 지점의 좌표 (위도, 경도)
두 지점 간의 실거리 값

ㅤ

위 정보를 하나의 JSON 데이터로 표현해보면 아래와 같습니다. 단순한 인터페이스를 위하여 Redis String에 지역 ID를 key로, 아래 실거리 JSON 데이터를 value로 저장하는 것이 초기의 계획이었습니다.

Key: "region:1234567" Value: { "distanceGraph": { "37.479482,127.135229-37.511794,127.101274": 5612, "37.479482,127.135229-37.496764,127.133687": 2311, "37.496764,127.133687-37.511794,127.101274": 3973, "37.479482,127.135229-37.480794,127.144663": 1014, "37.480794,127.144663-37.490578,127.113274": 3570, "37.480794,127.144663-37.511794,127.101274": 6180, "37.490578,127.113274-37.511794,127.101274": 3102, "37.490578,127.113274-37.496764,127.133687": 2312, "37.479482,127.135229-37.490578,127.113274": 2755, "37.480794,127.144663-37.496764,127.133687": 2426 } }

ㅤ

실거리 그래프의 단점과 네트워크 대역폭의 관계

다만, 이 구조는 데이터가 커질수록 치명적인 단점이 드러납니다. 특정 실거리 하나만 조회하거나 갱신하더라도, 해당 지역에 저장된 모든 데이터를 한꺼번에 가져와 수정한 뒤 다시 저장해야 하기 때문입니다.

매번 전체 데이터를 주고받다 보니, 데이터가 클수록 네트워크 대역폭 초과 위험이 커집니다. 네트워크 대역폭이 초과되면 커넥션 장애와 부하가 발생해 시스템 다운으로 이어질 수 있습니다.

여기서 이야기하는 네트워크 대역폭은, ElastiCache 노드가 네트워크를 통해 초당 전송할 수 있는 최대 데이터 용량을 의미합니다. AWS ElastiCache 사용자 가이드 문서에서 다음과 같이 노드 타입별 네트워크 대역폭 정보를 확인할 수 있습니다. Baseline bandwidth은 항상 보장되는 최소 처리량을, Burst bandwidth은 순간적으로 사용할 수 있는 최대 처리량을 의미합니다.

Instance type Baseline bandwidth (Gbps) Burst bandwidth (Gbps)

cache.r6g.large	0.75	10.0
cache.r6g.xlarge	1.25	10.0
cache.r6g.2xlarge	2.5	10.0

대역폭 사용량은 CloudWatch에서 제공하는 아래 지표로 모니터링이 가능합니다.

NetworkBandwidthInAllowanceExceeded
NetworkBandwidthOutAllowanceExceeded
NetworkPacketsPerSecondAllowanceExceeded
NetworkConntrackAllowanceExceeded

ㅤ

실거리 그래프 관리를 효율화하기 위한 시도 1. 데이터 압축

실거리 그래프의 비효율 문제를 해결하고자 가장 먼저 데이터 압축을 시도했습니다.

Spring Data Redis에서는 RedisSerializer를 직접 구현하여 원하는 압축 알고리즘을 사용할 수 있습니다. 이를 활용해 ZstdRedisSerializer를 주입한 RedisTemplate을 생성하면 됩니다. 압축 알고리즘으로는 높은 압축률과 빠른 처리 속도를 제공하는 효율적인 알고리즘인 Zstd(Zstandard)를 사용했습니다.

public static <T> RedisTemplate<String, T> zstdRedisTemplate(RedisConnectionFactory connectionFactory, Class<T> clazz) { RedisSerializer<T> serializer = new ZstdRedisSerializer<>(jackson2JsonRedisSerializer(clazz)); return objectRedisTemplate(connectionFactory, serializer); }

ㅤ

하나의 지역에 1000개의 서로 다른 좌표 간 모든 실거리를 저장할 경우, JSON 데이터 원본 크기는 약 24MB였으며, 압축한 크기는 3MB였습니다. 만약 최대 대역폭이 10Gbps라고 했을 때, 3MB 크기로는 초당 3400회의 조회도 버티기 어렵습니다. 압축률이 높더라도 원본 데이터가 워낙 커서 압축만으로는 대역폭 문제를 해결할 수 없었습니다.

또한, 문자열은 숫자에 비해 메모리 사용량이 많아 소수점 생략이나 구분자 축소 등 형식 변경을 시도했으나 효과는 미미했습니다. 데이터 대부분이 숫자임에도 불구하고, 결국 Redis에 String 타입으로 저장되기 때문입니다. 따라서, 실거리 그래프를 하나의 문자열로 표현하는 구조에서는 더 이상의 개선이 어렵다고 판단했습니다.

ㅤ

실거리 그래프 관리를 효율화하기 위한 시도 2. Redis 자료구조 활용

데이터 타입이나 압축보다도 자료구조 자체의 변경이 필요했습니다. 지역별로 실거리 데이터를 관리하는 콘셉트는 유지하되, 데이터를 단일 String으로 압축해 사용하는 방식 대신 Redis Hash 자료구조를 활용했습니다. Redis Hash 자료구조로 지역별 실거리 관리 인터페이스를 어느 정도 유지하면서도 읽기와 쓰기 성능을 크게 개선할 수 있었습니다.

구체적으로는 지역 ID를 Key로 하고, 각 Hash의 필드에는 실거리를 이루는 두 좌표를, 값에는 실거리를 저장하도록 설계했습니다. 이 구조에서는 매번 모든 데이터를 읽고 쓸 필요 없이 필요한 Hash 필드에만 접근할 수 있어, 네트워크 송수신 데이터량을 크게 줄일 수 있었습니다. 또한, 거리 값 자체를 Integer로 저장함으로써 메모리 사용도 더욱 효율적으로 관리할 수 있었습니다.

더 나아가 해시 필드 접근 시 단일 커맨드를 여러 번 호출하는 대신, 다중 인자를 한 번에 전달해 여러 필드에 동시에 접근하도록 하여 네트워크 오버헤드를 줄였습니다. 다만 다중 인자를 받는 커맨드의 시간 복잡도는 O(N)이므로 호출 횟수와 인자 수에 주의가 필요합니다. 또, AWS ElastiCache 사용자 가이드를 보면 요청당 최대 인자 수를 3,999개로 제한하는 것을 확인할 수 있습니다. 이를 감안해 인자 개수를 적절한 크기로 청크 처리하여 슬로우 쿼리 없이 적용할 수 있었습니다.

ㅤ

Redis 성능 최적화

EXPIRE 커맨드 줄이기

TTL은 Redis가 제공하는 매우 유용한 기능이지만, 지나치게 많이 사용될 경우 네트워크 오버헤드가 증가할 수 있습니다. 또한 만료 시간이 긴 경우 내부적으로 CPU와 메모리 리소스도 불필요하게 소모될 수 있습니다.

실거리 관리 시스템 초기 배포 시에는 버그나 롤백 상황에 대비해 일정 시점마다 메모리를 반드시 비워야 한다는 판단 하에, 모든 HMSET 요청에 6시간 EXPIRE 명령을 함께 실행하도록 설계했습니다. 하지만 배달이 N시간 안에 모두 완료된다는 가정은 현실적이지 못하고 비효율적이었습니다. TTL을 너무 짧게 설정하면 캐시 히트율이 떨어지고, 너무 길면 리소스 낭비로 이어집니다.

특히 실거리 시스템은 Redis Hash 구조를 사용해 지역 ID별로 거리 데이터를 관리하기 때문에, HMSET 요청 시마다 EXPIRE 명령을 함께 실행하면 Hash key의 TTL이 불필요하게 자주 갱신됩니다. 이로 인해 네트워크 비용이 낭비되는 문제가 발생합니다.

위 단점을 극복하기 위해, 일정 시간 TTL을 설정하는 대신 배달이 완료 또는 취소되는 시점에 해당 배달과 동일한 위치가 더 이상 사용되지 않는 경우에만 실거리 데이터를 명시적으로 삭제하는 방식을 선택했습니다.

이 방식은 별도의 삭제 로직이 필요하다는 단점이 있지만, 불필요한 가정을 하지 않아도 되고 CPU와 메모리 자원을 보다 효율적으로 관리할 수 있습니다. 또한 HMSET 수행 시마다 EXPIRE 명령을 함께 실행하지 않아도 되므로 네트워크 비용이 줄어듭니다. 더 나아가, 레플리카 복제 과정에서 발생하는 쓰기 트래픽 역시 감소하여 네트워크 송수신 데이터 양을 효과적으로 줄일 수 있습니다.

ㅤ

ㅤ TTL로 삭제 (expire) 명시적 삭제 (delete)

장점	• 배달 주기 신경 쓸 필요 없음 • 별도 로직 구현 불필요	• 배달 주기에 맞춰 실거리 그래프 관리 가능 • TTL 대비 단순하고 명확한 처리 가능
단점	• 배달마다 완료 시간이 달라 TTL 설정 모호 • 해시 필드별 TTL은 저수준 직접 구현 필요 (Spring Data Redis 미지원) • 지역별 해시 TTL은 매번 expire 연장 발생 • TTL 만료 시 콜드 스타트 이슈 발생 가능 • 대량 만료 시 CPU 사용량 증가	• 명시적 삭제 로직 구현 필요

ㅤ

쓰기 분산을 위한 Redis 클러스터 모드 적용

TTL과 명시적 삭제 방식을 비교해보며, 실거리 그래프는 쓰기 트래픽이 많다는 점을 확인했습니다. 따라서 이를 위한 분산 전략이 매우 중요합니다.

Redis는 고가용성을 위해 마스터-레플리카 모드와 클러스터 모드를 지원합니다. 마스터-레플리카 모드에서는 모든 쓰기 작업이 Primary 노드에 집중되고, Primary 노드는 변경사항을 Replica 노드에 전송해야 합니다. 이 과정에서 Primary 노드의 네트워크 병목과 대역폭 초과가 발생할 수 있습니다. 반면 클러스터 모드는 쓰기 작업도 여러 노드에 분산할 수 있습니다.

Redis 클러스터 모드의 샤딩은 키 공간을 해시 슬롯으로 나누어 동작합니다. 실거리 그래프는 지역 ID를 키로 관리하므로, 서로 다른 지역에 대한 HMGET, HMSET 요청을 각기 다른 샤드가 분산 처리할 수 있어 성능 향상에 유리합니다.

멀티 키 연산이 필요한 경우 클러스터 모드 적용 시 해시 태그 등의 추가 고려가 필요하지만, 실거리 그래프는 동일 키에 대해서만 멀티 연산(HMGET, HMSET, HDEL)이 발생하므로 서비스 코드 수정 없이 적용할 수 있었습니다. 따라서 클러스터 모드로의 전환만으로도 쓰기 트래픽 분산이 가능했습니다. 물론 트래픽 급증 시 네트워크 부하 문제는 여전히 발생할 수 있으나, 클러스터 모드는 노드를 수평 확장하기 쉬워 새로운 노드 추가로 유연한 대응이 가능합니다.

이처럼 클러스터 모드 적용을 통해 네트워크 용량 확장과 분산 처리, 성능 최적화를 통해 보다 안정적인 실거리 관리 시스템을 구축할 수 있었습니다. 실거리 관리 시스템 도입 후 Redis 지표 모니터링과 최적화 시도를 병행하며 지역별 점진 배포를 진행했고, 클러스터 모드 적용 후에는 전 지역으로 안정적 확장을 빠르게 마칠 수 있었습니다.

ㅤ

마무리

지금까지 배차시스템에서 OSRM 지도, Kafka, Redis를 활용한 이벤트 기반 실거리 시스템 개발 사례와 과정을 공유드렸습니다. 배달의민족 배차시스템팀은 배달에서 발생하는 대량 트래픽을 처리하기 위해 다양한 고민과 개발을 이어가고 있으며, 이번 실거리 시스템은 그중에서도 가장 많은 트래픽을 다루는 핵심 도메인 중 하나입니다.

이번 프로젝트를 통해 Kafka 기반 이벤트 드리븐 아키텍처(EDA)를 경험하고, Redis를 활용한 대규모 트래픽 처리 기술을 적용할 수 있었습니다. 또한 라이더분들의 효율적인 배달 수행을 지원하여 배차 효율 향상에 기여할 수 있었습니다. 저희의 경험과 사례가 글을 읽으시는 분들의 서비스 개선에 도움이 되길 기대합니다.

Read Entire Article