쿠팡이 '공간 색인'으로 로켓배송 개선한 방법

12분

2023.05.04.

12.4K

국내 IT 기업은 한국을 넘어 세계를 무대로 할 정도로 뛰어난 기술과 아이디어를 자랑합니다. 이들은 기업 블로그를 통해 이러한 정보를 공개하고 있습니다. 요즘IT는 각 기업의 특색 있고 유익한 콘텐츠를 소개하는 시리즈를 준비했습니다. 이들은 어떻게 사고하고, 어떤 방식으로 일하고 있을까요?

이번 글은 국내 대표 이커머스 기업 ‘쿠팡(Coupang)’이 공간 색인 기반의 배송 영역 관리 시스템으로 로켓배송을 개선한 사례에 대해 소개합니다.

배송 영역 시각화 프로젝트를 통해 구축한 직관적이고 최적화된 배송 시스템에 대해
By Geo J Son & Sam HS Jeon

로켓배송은 쿠팡의 가장 중요하고 매력적인 서비스들 중 하나입니다. 고객들이 “쿠팡 없이 어떻게 살았을까?”라고 생각하게 만들고 고객들의 삶이 더 나아질 수 있도록, 저희는 최적화된 배송 시스템을 마련하고 배송 기사인 쿠팡친구(이하 쿠친)들과 함께 노력하고 있습니다.

쿠친이 택배 상자와 봉투들을 가장 효율적으로 배송하려면, 배송 시스템은 정확히 배송지 주소를 파악하고 이를 바탕으로 가장 적합한 배송 영역을 찾아낸 다음 쿠친에게 운전 경로를 안내해 주어야 합니다. 또한 시스템에 의해 택배 상자와 봉투들이 배송 영역으로 균등하게 할당되고 분배되려면, 경험 많은 캠프 작업자들이 배송 영역 정보를 수시로 업데이트할 수 있어야 합니다.

저희의 기존 시스템은 텍스트로 된 주소와 우편번호에 의존했고, 직관적이고 기능적인 부분도 부족하여 저희의 복잡한 운영 니즈를 만족시키지 못했습니다. 이에 저희는 배송 영역을 지도 위에 시각화하고, 직접 지도를 수정할 수 있는, 그리고 최적화에 필요한 수치 및 통계가 추가로 제공되는 시스템의 개발을 위한 프로젝트를 2021년에 시작했습니다.

과제: 텍스트 기반의 우편번호

우편번호는 정부 및 각종 공공기관들이 보장하는 가장 잘 조직된 시스템 중 하나로, 특정 배송 영역에 할당된 코드를 가리킵니다. 지형적 요소와 배송 수요 측면에서 봤을 때 할당된 영역의 물리적 넓이는 제각각이긴 하지만 우편번호는 최적화된 실질 배송 효율을 제공합니다. 그래서 로켓배송은 처음부터 우편번호를 배송 영역의 기본 단위로 채택했습니다. 서비스 초기에는 잘 작동했지만, 쿠팡이 성장하면서 훨씬 더 많은 것들이 필요해졌습니다. 우편번호당 매일 처리해야 하는 배송 건수가 두 자릿수에서 세 자릿수로 증가했습니다. 한 명의 쿠친이 하루에 처리하기에는 너무 많은 양이었습니다.

그러다 보니 단일 우편번호를 분할해 처리 가능한 여러 영역으로 세분화해야 할 필요가 생겨났습니다. 처음에는 아파트 단지 몇 개가 단일 영역이었지만, 분할되어 단지 하나가 단일 영역이 되었고, 결국엔 단지도 분할되어 아파트 동 하나가 단일 영역으로 세분화되었습니다. 그러나 텍스트로만 되어 있는 주소에서 공간 관련 정보를 식별해 내기는 쉽지 않기 때문에, 배송 영역의 특성을 잘 알고 있는 숙련된 캠프 리더와 쿠친 그룹 리더만이 세분화 작업을 수행할 수 있었습니다.

배송 영역 관리 시스템의 새로운 목표

지도 위에 배송 영역들을 좀 더 효율적이고 쉽게 시각화하기
관계자들 모두 쉽게 배송 영역들을 확인하고, 만들고, 수정하고, 다른 사람들과 공유하기
신축 및 철거 건물과 같은 변동 상황 발생 시에도 지속적으로 운영 가능하도록 배송 영역들을 우편번호 및 문자로 된 주소가 아닌 공간 데이터 기반으로 관리하기

시스템에 H3 도입하기

저희는 배송 영역 관리 시스템의 새로운 목표를 달성하기 위한 프로젝트를 시작했습니다. 지도 위에 그려진 다각형(polygon)들로 직관적인 공간 영역 관리가 가능하도록 육각형 격자(hexagon grid) 기반의 공간 색인 시스템(spatial indexing system)을 활용했습니다.

지도 위 영역들을 다각형으로 그리는 것이 간단해 보일 수도 있지만, 영역들 모두를 중복되고 생략되는 것 없이 깔끔하고 명확한 경계들로 그려내 빈틈없이 관리하는 것은 매우 어렵습니다. 이런 다각형 세트들이 상호배제와 전체 포괄(mutually exclusive and collectively exhaustive, MECE) 원칙하에 관리될 수 있게끔, 공간 단위를 정의하는 일부터 시작했습니다.

지형공간 색인 시스템

먼저 GIS 전문가들에 의해 개발된 다양한 지형공간 색인 시스템(geospatial indexing system)들을 검토했습니다. 지형공간 색인 시스템은 일종의 격자 세트(a set of grids)로, 고유 식별자를 갖는 격자들로 지리적 표면을 채워 관리합니다. 행정기관에 의해 유연하게 변경될 수 있는 우편번호와 행정구역 같은 경우에는 불규칙한 형태의 격자를 가집니다. 이렇게 공간 영역에 고유 식별자가 할당되면서도 공간의 경계는 유연한 시스템은 결합 시계열 분석(analysis of integrated time series) 시에 이점이 있습니다.

공간 색인 시스템

W3W (What3Words)는 가장 널리 사용되는 공간 색인 시스템(spatial indexing system)들 중 하나이며, 전 세계를 3m² 정사각형으로 구분하여 각각의 정사각형을 3개의 단어로 표현합니다. 위도-경도 좌표계는 긴 숫자 배열로 구성되어 있어 말로 전달하기 어려운 반면, W3W는 3개 단어들의 고유한 조합만으로 위치를 나타낼 수 있습니다. 예를 들어 쿠팡의 사무실들 중 하나인 로켓 연구소의 위치는 위도-경도 좌표로는 [37.503819, 127.0481493]이고 W3W로는 [scoring.eager.patch]입니다. 하지만 아쉽게도 분석에 필요한 해상도 조정은 불가능합니다.

Google의 S2와 Uber의 H3는 잘 알려져 있는 불변 공간 색인 시스템으로 격자들이 부모-자식(parent-child)의 상하위 위계 구조를 갖습니다. N개의 하위 격자가 1:N 관계에 의해 하나의 상위 격자로 매핑됩니다. 하위 격자들을 합쳐 하나의 상위 격자를 만들 수 있고, 반대로 상위 격자를 하위 격자들로 분할할 수도 있습니다. 설정 가능한 격자의 크기는 다양하며 지리 좌표로 변환하려는 지도의 목적과 규모에 따라 유연하게 선택할 수 있습니다. 저희의 프로젝트 같은 경우 확장성 및 구현의 이점을 위해 H3를 채택했습니다.

왜곡도: 위의 표에서 알 수 있듯이, S2와 H3의 가장 큰 차이점은 기본 격자의 모양입니다. H3는 육각형 격자로 구성되어 있어 공간 대부분에서 왜곡이 최소화됩니다. S2는 구에서 정방형으로 지구를 투영(projection)하는 과정에서 상당한 오류를 발생시킵니다. 따라서 같은 레벨의 격자들이라도 투영 중심(center of projection)으로부터의 거리에 따라 서로 크기가 다를 수도 있습니다. 한편, H3는 육각형마다 투영 중심점이 존재하는 풀러린이나 축구공 모양과 유사합니다. 이는 왜곡을 최소화하는 데 도움이 됩니다.
이웃 격자: H3는 동일한 영역을 더 적은 수의 격자들로 변환할 수 있습니다. 특정 영역을 나타낼 때, S2는 영역을 더 작은 사각형, 엄밀히 말해 마름모로 분할합니다. H3은 육각형을 이용하기에 서로 인접해 있는 격자들의 표면적이 더 넓어 영역이 상대적으로 더 큼직하게 분할됩니다.
위계 구조 & 조밀도:H3 같은 경우, 상위 격자들이 물리적으로 모든 하위 격자들을 포함하지는 않습니다. 바다처럼 배송지가 없는 곳에는 육각형 대신 예외적으로 오각형 격자로 분할합니다.

새로운 기술들로 시스템 재설계하기

격자 해상도

쿠팡의 배송 서비스가 제공되는 영역들 전부를 육각형 격자로 정확히 표현해 내려면 어떻게 해야 할까요? 기본적으로 최적의 크기를 갖는 육각형으로 대한민국 전체를 담아낼 수 있어야 합니다. 크기가 너무 크면 하나의 같은 육각형에 여러 건물 또는 주소들이 할당될 수 있습니다. 크기가 너무 작으면 하나의 건물이나 주소가 여러 다른 육각형들로 할당될 수 있습니다.

아래 그림 2의 왼쪽 부분은 약 300m²의 해상도를 가진 12 레벨 육각형의 예를 보여줍니다. 그러나 이 크기의 육각형으로는 기본적으로 도로와 서로 이웃한 건물들로 나누어지는 블록(block)들을 구분해낼 수가 없습니다. 블록을 배달 영역들로 분할하고 주변의 다른 블록들과 상호 배타적으로 만드는 것이 매우 중요하기 때문에 저희는 6.3m²의 해상도를 가진 14 레벨 육각형을 채택했습니다. 이를 통해 해상도로 입구와 우편함 같은 정확한 위치의 위도와 경도 좌표를 대체할 수 있었습니다.

데이터 관리

서비스 목적에 맞는 육각형의 크기를 정의했으니, 그다음으로는 해당 크기의 데이터를 확장성 있게 관리하는 방법을 정의해야 했습니다. 대한민국은 12 레벨의 해상도로 약 4억 3200만 개의 육각형으로 나눌 수 있습니다. 상위 육각형에는 7개의 하위 육각형이 있으므로 13 레벨 해상도는 31억 육각형으로, 14 레벨 해상도는 217억 육각형으로 변환됩니다. 확장성을 충분히 확보하면서 데이터를 관리할 수 있는 방법이 필요했습니다.

데이터를 관리하는 방법들 중 하나는 RDBMS를 사용하는 것입니다. 육각형의 ID를 키로 사용해 데이터를 저장할 수 있습니다. 그러나 RDBMS는 읽기/쓰기(read/write)의 성능 유지를 위해 일반적으로 테이블의 행(row)을 1억에서 10억 개로 제한합니다. ID를 행 단위로 관리하면 12 레벨 해상도로 대한민국 전역을 하나의 테이블에 담아낼 수 있지만, 14 레벨 해상도를 적용하려면 지역별로 테이블을 나누거나 다른 방법을 채택해야 합니다. 그리고 데이터베이스 샤딩(database sharding)을 통해 어떻게든 데이터를 관리하더라도 국내외 더 많은 지역들에 서비스를 적용하게 될 경우 데이터 저장 공간이 늘어날 수밖에 없습니다. 따라서 저희는 RDBMS에 육각형 ID를 키로 해 특정 데이터를 저장하는 것은 저희의 유즈 케이스에 적합하지 않다는 결론을 내렸습니다.

이에 각 배송 영역이 영역 내 육각형들의 정보를 갖도록 설계하였습니다. 물론 하나의 매우 큰 영역의 경우 수없이 많은 14 레벨 육각형들의 정보를 갖고 있어야 하기 때문에 메모리 또는 데이터 크기와 관련된 문제가 발생할 수 있습니다. 이를 방지하기 위해 H3에서 제공하는 압축(compaction) 관련 기능들을 사용하는 것을 고려하였습니다. 하위 육각형들이 모두 존재하는 경우 해당 기능들을 사용하면, 하위 육각형들(finer)과 상위 육각형(coarser)의 해상도를 오고 가면서 원하는 작업을 수행할 수 있습니다. 그리고 이를 통해 데이터 전체를 저장하는데 필요한 메모리 양도 줄일 수 있습니다.

이 디자인으로 배달 영역들을 효율적으로 저장하고, 많은 영역들을 저희가 원하는 만큼 14 레벨 해상도로 표현할 수 있습니다. 지역 제한이나 확장성에도 문제가 없습니다. 따라서 아래의 그림 4와 같이 특정 위도-경도 좌표인 [34.111, 127.111]에 대한 영역을 검색하는 경우, 간단히 좌표를 14 단계 해상도를 갖는 육각형의 ID인 85283473fffffff로 변환하고, 이 육각형 ID가 포함된 육각형 그룹을 찾습니다. PostGIS나 다른 지오데이터베이스(Geodatabase) 모듈이 설치되어 있지 않은 환경에서도 육각형 ID와 육각형 그룹 사이의 포함 관계를 쉽게 분석할 수 있습니다.

육각형 그룹을 육각형으로 채워진 다각형으로

시스템 개발의 첫 단계를 완료한 후 몇 가지 개선이 필요한 부분들을 발견했습니다. 예를 들어 육각형 ID 목록 사용 시 제한되는 것들이 몇 가지 있었습니다. 복잡한 공간을 분석하거나 특정 지점에서 멀리 떨어져 있는 배달 영역들 몇몇을 찾아내는 것이 어려웠습니다. 이를 개선하기 위해 영역의 기본 단위는 육각형 격자로 유지하되 실제 데이터는 다각형 포맷으로 저장했습니다. 어떤 다각형이든 polyfill 기능을 이용해 14 레벨의 육각형들로 변환한 다음 경계를 다시 다각형으로 바꿔 저장할 수 있습니다. 이것은 픽셀 아트(pixel art)를 그리는 것과 비슷합니다. 벡터화된 .ai 파일을 .jpg 비트맵 파일로 변환한 다음, 변환된 파일을 분할해 다시 벡터화된 이미지를 만듭니다.

또한 위치 정보 검색 및 배송 영역 관리에 있어 육각형으로 채워진 다각형들을 활용하면 겹치고 누락되는 영역 없이 좀 더 쉽게 원하는 결과를 얻을 수 있습니다. 아래 그림 5와 같이 클라이언트 사용자가 지도 UI에 사각의 녹색 다각형을 그리면 서버는 이를 육각형 그룹으로 변환한 다음 외부와 접하는 경계만 다시 다각형으로 변환하여 육각형으로 채워진 적색 다각형을 만들어냅니다. 따라서 사용자가 그린 녹색 다각형과 육각형으로 채워진 적색 다각형으로 단일 영역을 표시할 수 있습니다.

이 방법의 유일한 단점은 클라이언트 측에서 매우 복잡한 다각형을 만들어내는 경우 육각형으로 변환하는 데 시간이 조금 더 걸릴 수 있다는 것입니다. 이를 해결하기 위해 사용자가 처음 생성한 다각형은 그대로 저장하고, 나중에 육각형으로 채워진 다각형을 비동기적으로 생성해 활용했습니다.

시스템에 새로운 기술들 적용하기

사용자가 어떻게 육각형 그룹들을 생성하고 관리할 수 있는지에 대해 다루었습니다. 이번 섹션에서는 이러한 기술들을 실제 배송 영역 관리 시스템에 적용한 방법을 소개하고자 합니다. 로켓배송 서비스는 앞에서 언급한 바와 같이 우편번호를 배송 영역의 기본 단위로 두고 필요에 따라 영역을 세분화해 적용할 수 있습니다. 따라서 실제 시스템에서는 목록에서 우편번호 선택 시 해당 영역의 공간이 지도 위에 표시됩니다.

아래의 그림 6과 같이 실제 시스템에서 사용자는 우편번호가 가리키는 영역의 안쪽에 자유롭게 다각형을 그리고 영역에 대한 설명을 채워 넣을 수 있습니다. 저장 버튼을 누르면 영역 관련 데이터와 사용자가 그린 다각형이 서버로 전송되어 육각형으로 채워진 다각형으로 변환됩니다.

예를 들어, 서울의 우편번호인 06961을 선택하면 육각형 그룹들로 구성된 두 개의 영역이 지도 위에 나타납니다. 두 영역 모두 선택한 우편 번호 내에 위치한 개별 아파트 단지입니다. 지도 영역 상단에 제공되는 그리기 도구로 영역들을 그리면 각 영역은 육각형이 채워진 다각형으로 자동 변환됩니다. 각 영역의 테두리를 자세히 살펴보면 테두리가 매끄러운 직선이 아닌 육각형 모양으로 잘려 있는 것을 볼 수 있습니다.

그림 6의 오른쪽은 Edit버튼을 클릭할 경우 파란색 윤곽선으로 표시된 영역이 수정되는 걸 보여줍니다. 노란색 윤곽선 영역은 여전히 육각형이 채워진 다각형으로 표시되는 반면, 파란색 윤곽선 영역은 사용자가 그린 다각형의 윤곽이 매끄러운 선으로 다시 그려졌습니다. 수정이 완료되면 다각형은 서버에서 처리된 다음 새로운 육각형이 채워진 다각형으로 업데이트됩니다.

향후 계획

이번 포스트에서는 지오데이터베이스와의 일관성을 유지하면서 배송 영역을 효율적으로 관리하기 위해 시스템을 어떻게 설계했는지에 대해 소개했습니다. 새 시스템은 사용자에게 더 향상된 경험을 제공하기 위해 기존의 시스템을 개선한 것으로, 기존 시스템과 계속 함께 사용할 수 있습니다. 또한 배송 영역의 텍스트 주소 모두를 GIS 기반의 공간 데이터로 변환하면서, 시스템을 앞으로도 더 개선할 수 있는 기회들을 갖게 되었습니다.

배송 상태 및 관련 수치들을 육각형 격자에 기반해 분석하게 되면서, 더 이상 우편 번호나 주소로부터 영향받지 않고, 공간 기반의 절대(absolute) 통계를 생성할 수 있게 되었습니다. 어떤 이유로 배송 영역에 변화가 일어나더라도 이전과 동일한 기준으로 통계들을 비교할 수 있습니다. 배송 영역에 대해 정확하게 평가할 수 있으며, 비효율적인 배송 영역을 빠르게 식별해 낼 수 있습니다. 이를 통해 저희 팀은 배송 속도의 저하 요인을 심층적으로 분석하고 문제를 해결하기 위한 대책을 찾을 수 있게 되었습니다.

또한 배송 난이도 평가, 배송 영역 간 거리 측정, 이동시간 등 배송 영역의 상황도 분석 가능해졌습니다. 덕분에 1) 배송 영역의 난이도를 보다 정확하게 평가하고, 2) 배송 물량에 따라 배송 영역을 동적으로 관리하며, 3) 쿠친이 보다 안전하고 빠르게 배송할 수 있도록 최적화된 이동 경로를 추천할 수 있게 되었습니다.

로켓배송 서비스가 처음 시작됐을 때, 주문한 상품이 하루 만에 배송되는 일은 불가능해 보인다는 의구심도 있었습니다. 하지만 지금 익일 배송은 대한민국 쇼핑 문화의 새로운 표준이 되었습니다. 쿠팡은 앞으로도 더 많은 기술 혁신으로 배송 시스템을 발전시켜 고객들을 더욱더 감동시킬 것입니다.

<원문>

쿠팡 로켓배송: 공간 색인 기반의 새로운 배송 영역 관리 시스템

로그인하고 자유롭게 의견을 남겨주세요.