안녕하세요!
K-DEVCON (이하 “데브콘”) 그로스 매니저 박종훈입니다.
시스템 디자인 스터디가 돌아왔습니다 : )
이번 스터디에서는 『가상 면접 사례로 배우는 대규모 시스템 설계 기초 2 (1~6장)』 를 보며 함께 디자인 해볼 계획입니다.
이 글에서는 12/04 (목)에 진행된 스터디에서 나눈 이야기를 정리합니다.
이번 시간에는 “근접성 서비스” 에 대한 시스템 설계를 해보았습니다.
“근접성 서비스” 라는 서비스는 뭘 하는 서비스 일까요? 표현을 좀 바꿔보면 “위치 기반 서비스” 라고도 할 수 있을 것 같습니다. 특정 위치를 기준으로 가까운 거리 내에 있는 사물이나 장소를 찾는 기능을 제공합니다. 내 주변의 식당/시설/부동산을 찾거나, 주변의 사람을 찾는 서비스들이 이에 해당됩니다. (Yelp, 직방, 다이닝코드, Tinder 등)
이러한 서비스를 만들어 본다면 어떤 부분들을 신경써야 할지 같이 같이 알아보겠습니다.
[1] 기본적인 시스템 설계
이번 장의 기초 설계안은 매우 단순합니다.
따라서 이번장의 핵심은 LBS(Location-based service, 위치 기반 서비스) 가 어떻게 동작하는지 이해하는 것이라고 생각됩니다.
사용자는 LBS에 좌표 정보와 반경(혹은 zoom level)을 제공하고, LBS는 지리적 위치를 효율적으로 조회 할 수 있어야 합니다.
[2] 어떻게 효율적으로 조회할 수 있을 것인가.
가장 단순한 조회 방법은, 일반적인 RDB에 좌표정보를 직접 넣어두고 2차원 데이터를 조회하기 위한 쿼리를 작성하는 것 일 것입니다.
예전에 학부생 시절에 했던 프로젝트에서, 실제로 이런 방법을 사용해서 조회를 했던 기억이 납니다.
이러한 방식은 데이터베이스에서 효과적으로 쿼리하지 못할 가능성이 높습니다. 그럼 어떤 더 좋은 방식이 있을까요?
지리 정보를 사용하는 서비스들은 각자의 방법으로 지도의 구역을 나눠서 데이터를 관리합니다.
몇 년 전에 ‘포켓몬 고’ 가 한국에 정식 출시 되기 이전, 속초 지역에서만 서비스가 되었던 재밌는 일이 있었습니다. 그리고 당시에 아래와 같은 이미지를 볼 수 있었습니다.
위와 같은 경우도 효과적으로 데이터를 관리하기 위해 구역을 구분한 사례중 하나로 볼 수 있을 것입니다.
책에서는 GeoHash, Quadtree, 구글 S2 에 대해서 설명하며, 이 중 이 글에서는 GeoHash에 대해서 더 알아볼 수 있도록 하겠습니다.
각 방법의 구현 방법은 다르지만 아이디어는 “지도를 작은 영역으로 분할하여 고속 검색을 가능하도록 색인한다.”로 동일합니다. 각자 장점과 단점이 있을 것이며, 본인의 상황/요구사항에 맞는 방식을 선택하면 될 것입니다.
[3] GeoHash
GeoHash(https://en.wikipedia.org/wiki/Geohash) 는 2차원의 위도 경도 데이터를 1차원의 문자열로 변환 합니다. GeoHash 알고리즘은 비트를 하나씩 늘려가면서 재귀적으로 더 작은 격자로 분할해 나갑니다.
이 과정을 반복하여 원하는 정밀도를 얻을 때까지 반복하면 됩니다.
[4] Lyft 에서 GeoHash를 사용한 사례
지리 정보 색인: Lyft를 지탱하는 천만 QPS 지원 레디스 아키텍처
(Geospatial Indexing: The 10 Million QPS Redis Architecture Powering Lyft):
https://www.youtube.com/watch?v=cSFWlF96Sds
위 발표의 내용을 정리하여 스터디 원들과 스터디에서 이야기를 나눴습니다. 이 글에서도 간단하게 이야기를 정리해보겠습니다.
Lyft는 승차 공유(ridesharing) 서비스 회사입니다. 서비스를 위해 고객의 위치와 기사의 위치를 효율적으로 관리해야 합니다. Lyft 에서는 이를 위해 GeoHash 를 사용하였습니다.
초기에는 MongoDB 를 이용하여 지역을 기반으로 서비스를 구성하였습니다. 이 때 발생되는 문제는 지역 경계에 있을 경우 적절한 결과값을 받지 못할 경우가 있을 수 있다는 것입니다.
예를 들어, 커피숍 A는 사용자 위치에서 5km가 떨어져 있지만, 같은 행정 구역 안에 있습니다. 커피숍 B는 1km 떨어져 있지만, 사용자 위치와 다른 행정 구역에 있습니다. 이 경우 지역 기반 서비스의 경우 가까운 커피숍 B 가 아닌 멀리있는 커피숍 A 에 대한 정보를 제공하게 됩니다.
이를 개선하기 위해 Redis 에 GeoHash 를 활용하여 데이터를 관리하게 되었습니다.
GeoHash 자체에 대한 설명은 위에서 하였기 때문에 구체적으로 설명하지는 않겠습니다.
여기서 재밌는 부분은 Redis 에서 자체적으로 제공해주는 GeoHash 가 있지만, Lyft 에서는 직접 구현하는 방식을 선택하였다는 점입니다. 그 이유는 GeoHash는 만료기능을 제공하지 않았기 때문입니다.
만료 기능을 사용하기 위해 Lyft는 ZSet을 사용하였습니다. ZSet 은 score 를 기준으로 정렬해주는 자료구조 입니다. Lyft는 timestamp를 score 로 두어 특정 score 이하는 제거하는 방향으로 만료 기능을 구현하였습니다.
Lyft 는 envoy proxy 를 만든것으로 유명한데요. (현재는 CNCF 에서 관리하고 있음.) 이 기술을 활용하여 redis proxy를 위한 envoy redis를 구현하였고, 이를 통해 데이터들을 적절히 여러 redis에 배분할 수 있는 환경을 구성하였습니다. 이를 통해 약 50개의 클러스터, 750개의 인스턴스 에서 데이터를 관리하고 있다고 합니다.
[5] 그 외의 방안
길게 다루지는 않고 대략적인 컨셉을 이해할 정도로만 간단하게 적어보겠습니다.
<1> Quadtree
Quadtree는 말 그대로 트리 형태의 자료구조입니다. 메모리에 Quadtree 인덱스를 구축하여 사용하게 됩니다. 격자 구조를 이용하여 기준을 만족할 때까지 재귀적으로 분할하여 데이터를 구축합니다. 메모리 안에 놓이는 자료 구조일 뿐 데이터베이스는 아니며, 서버가 시작하는 시점에 구축되어야 합니다.
<2> 구글 S2
구글 S2는 힐베르트 곡선 (https://en.wikipedia.org/wiki/Hilbert_curve) 을 사용하여 1차원 색인화(indexing)을 하여 사용합니다.
사실 ‘1차원 색인화’를 한다는 표현이 이해하기가 정말 어려웠는데요. 조금 더 설명해보자면 힐베르트 곡선은 공간 채움 곡선(space-filling curve) 입니다. 즉 공간을 채워나갑니다. 공간을 채워나가면서 cell 마다 번호를 붙이게 되면 모든 위치에 대한 정의가 가능해 집니다. 이를 통해 2차원 데이터를 1차원으로 바꾸어 indexing을 할 수 있습니다. 이 때 2차원에서 가까운 두 지점은 1차원 인덱스에서도 가까운 번호를 가지므로 효율적으로 검색할 수 있습니다.
또 하나의 특징은 Geofence (https://en.wikipedia.org/wiki/Geofence) 기능을 제공해 준다는 것입니다. 이를 통해 관심있는 영역의 경계를 지정하여 데이터를 관리할 수 있습니다. 사용자의 특정 영역 진입/이탈을 감지하여 이벤트를 발생시킬 수 있습니다.
틴더와 배달의 민족 에서 사용중이라고 합니다.
<3> Uber H3
독특하게 hexagon 방식을 사용한 것이 특징입니다.
육각형 셀을 사용하여 분석 및 시각화의 효율성과 정확성을 높였다고 합니다. 재밌어 보이는 사례같아서 가져왔습니다.
자세한 내용은 “H3: Uber's Hexagonal Hierarchical Spatial Index (https://www.uber.com/en-KR/blog/h3/)” 에서 확인해보실 수 있습니다.
<4> R-Tree
R-Tree(https://en.wikipedia.org/wiki/R-tree)는 최소 경계 사각형(MBR) 이라는 컨셉을 사용하는데요, 가까운 위치정보 데이터들을 MBR 로 묶어서 관리합니다, MBR 이 너무 많아지면 더 큰 상위 폴더로 묶습니다. (MBR들은 서로 겹칠 수 있습니다.) 데이터가 있는 영역만 묶어서 관리하는 것이 특징입니다. MBR 을 통해서 공간 데이터의 쿼리 속도를 향상시켰습니다.
새로 참여하신 분들과 함께하게 되어 더 풍성한 이야기를 나눌 수 있었습니다.
스터디에서 더 많은 이야기를 나눴지만, 오늘은 여기서 마쳐보겠습니다.
우리 스터디에서는 실제 사례들을 통해 문제를 어떻게 해결해 나갔을까 많은 고민을 해보고 이야기를 나눠보고 있습니다. 이번주도 다들 열심히 참여해주셔서 더 풍성한 스터디가 될 수 있었습니다.
✅ 직접 스터디를 개설해보고 싶은 분이 계시다면, K-DEVCON에서 운영을 도와드리겠습니다. 데브콘의 '랩짱'에 도전하여 커뮤니티 성장을 함께 이끌어주세요! 슬랙을 통해 운영진에게 DM 부탁드리겠습니다😉
'데브콘 활동 후기' 카테고리의 다른 글
| 🐯 DEVCON 2025 후기 - 한 장면 한 장면이 선명하게 남는 하루 (0) | 2025.11.23 |
|---|---|
| [행사후기] 데이터로 보는 DEVCON 2025 리포트 📊 (0) | 2025.11.13 |
| [Review] 시스템 디자인 스터디 8주차 후기 (0) | 2025.11.10 |
| [DEVCON 2025] K-DEVCON Hunters 일원이 되다! (0) | 2025.11.04 |
| [DEVCON 2025] 발표 자료 공유 (0) | 2025.11.03 |