더 스마트한 캐싱을 사용하여 50배 더 ​​빠르게 맵 클러스터 제공

위치 마커가 있는 지도 구성요소는 오늘날 모바일 앱에서 일반적입니다. 예를 들어, Airbnb 앱은 웹 서비스에서 가져온 이러한 마커를 눈에 띄게 표시하여 지도에서 사용 가능한 속성을 나타냅니다.

마커 수가 증가함에 따라 가져온 데이터의 볼륨을 관리할 수 없게 되지 않도록 하기 위해 서버는 해당 마커를 클라이언트에 보내기 전에 함께 그룹화합니다. 지도 클러스터 는 해당 위치가 포함하는 마커의 평균 위치와 동일한 특수 마커입니다. 그것은 그것이 나타내는 마커의 수로 레이블이 지정됩니다.

그러나 웹 서비스는 데이터베이스에서 지정된 지리적 영역 내의 모든 단일 마커를 검색해야 하기 때문에 클러스터를 제공하면 성능 병목 현상이 발생할 수 있습니다. 다행히 이 문제는 캐싱 전략으로 해결할 수 있습니다. 캐시를 설계하고 유지 관리하는 방법을 더 잘 이해하기 위해 Playsports 앱용으로 만든 지도 API 끝점의 예를 살펴보겠습니다.

스케일링 문제와 순진한 솔루션

Playsports 지도에서 각 마커는 스포츠 시설을 나타냅니다. 지도의 API 끝점은 확대/축소 수준과 경계 상자가 있는 경우 마커 및 마커 클러스터 목록을 반환해야 합니다.

마커 수가 충분히 적으면 데이터베이스에서 경계 상자의 모든 마커를 로드하고 필요에 따라 클러스터링하고 결과 마커와 클러스터를 클라이언트에 반환할 수 있습니다.

처음에 Playsports에서 도달할 수 있는 경계 상자의 최대 마커 수는 ~400개였으며 결과적으로 끝점 속도는 ~0.5초였습니다. 이 사용 사례에서는 순진한 솔루션을 구현하는 것으로 충분했습니다.

그러나 마커의 수가 증가함에 따라 메커니즘의 비효율성이 명백해졌습니다. ~10,000개의 새로운 스포츠 시설 마커를 추가한 후 일부 확대/축소 수준에서 끝점 속도가 ~4.3초로 느려졌습니다. 이 속도는 일반적으로 모바일 앱에서 사용자 작업에 대해 허용 가능한 최대 지연으로 간주되는 1초보다 훨씬 낮습니다.

순진한 솔루션의 비효율성을 더 잘 이해하기 위해 마커 쿼리의 컨텍스트에서 분석해 보겠습니다.

1. 데이터베이스 에서 경계 상자의 모든 마커를 검색합니다 . 대부분의 앱의 경우 이 단계에는 위도/경도 위치 이외의 마커 세부 정보 가져오기가 포함되어야 합니다. 예를 들어, 에어비앤비의 마커에는 가격, 사용자가 이미 숙소를 보았는지, 즐겨찾기로 표시했는지 여부가 포함됩니다.
2. 검색된 마커에서 확대/축소 수준을 통합 하는 지도 클러스터링 알고리즘을 실행합니다 .
3. 클라이언트에 클러스터 및 (상세한) 마커를 반환 합니다.

마커 수가 증가하면 1단계와 2단계에서 성능이 저하됩니다.

• 경계 상자가 충분히 크고 10,000개 이상의 마커에 JOIN을 통한 세부 정보 조회가 필요한 경우 데이터베이스 쿼리가 크게(1~2초) 느려집니다.
• 맵 클러스터링 알고리즘에 10,000개의 항목을 제공하는 데 ~250밀리초가 더 걸립니다.

일정한 창 크기를 가정할 때 경계 상자가 비교적 클 때 확대/축소 수준은 일반적으로 낮습니다(즉, 멀리 축소). 낮은 확대/축소 수준에서 결과는 시각적 혼잡을 피하기 위해 클러스터를 선호하는 경향이 있습니다. 따라서 최적화의 가장 큰 가능성은 수천 개의 개별 마커가 로드되는 솔루션의 첫 번째 단계에 있습니다. 결과에 이러한 마커의 대부분이 필요하지 않습니다. 클러스터로 계산하기 위해 각각만 필요합니다.

최적화된 솔루션 설계

순진한 솔루션은 최악의 쿼리를 완료하는 데 훨씬 더 오래 걸립니다. 마커 밀도 영역의 최대 경계 상자입니다. 대조적으로, 최적화된 솔루션은 ~58배의 속도 향상을 나타내는 단 73ms가 소요됩니다. 높은 수준에서 보면 다음과 같습니다.

1. 캐싱 전략. 확대/축소 수준별 캐시에서 경계 상자의 마커 및 클러스터를 검색합니다.
2. 추가 마커 세부 정보(선택 사항). 데이터베이스에서 가져온 페이로드로 마커를 향상합니다.
3. 결과를 반환합니다. 마커와 클러스터를 클라이언트에 반환합니다.

주요 복잡성은 캐시 아키텍처(즉, 첫 번째 단계)에 있습니다.

1단계: 캐싱 전략

이 주요 단계는 6가지 구성 요소로 구성됩니다.

기술

Redis는 일반적으로 캐시로 사용되는 빠른 인메모리 데이터베이스입니다. 내장된 지리 공간적 인덱싱은 위도-경도 포인트의 효율적인 저장 및 검색을 위해 Geohash 알고리즘을 사용합니다. 이는 바로 마커에 필요한 것입니다.

각 확대/축소 수준에 대한 캐시

지도 클러스터링의 정도(단일 마커 또는 클러스터가 반환되는지 여부)는 끝점에 전달된 확대/축소 수준에 의해 결정됩니다.

• 높은 확대/축소 수준(예: 가까이 확대)의 경우 결과는 마커 밀집 영역을 제외하고 개별 마커를 선호합니다.
• 낮은 확대/축소 수준(즉, 멀리 축소)의 경우 결과는 마커가 부족한 영역을 제외하고 클러스터를 선호합니다.

Google 지도는 지역에 따라 0에서 최대 20까지 확대/축소 수준을 지원합니다. (다른 지도 서비스에서 지원하는 범위는 비슷합니다. 예를 들어 Mapbox는 0에서 최대 23까지의 확대/축소 수준을 사용합니다.) 이러한 확대/축소 수준도 정수 값이므로 각 확대/축소 수준에 대해 별도의 캐시를 간단히 만들 수 있습니다.

너무 많이 축소된 수준 0을 제외하고 Google 지도의 모든 확대/축소 수준을 지원하기 위해 20개의 개별 캐시를 만듭니다. 각 캐시는 나타내는 확대/축소 수준에 대해 클러스터된 대로 전체 지도에 대한 모든 마커와 클러스터를 저장합니다.

캐시 데이터 유형

각 캐시는 클러스터와 개별 마커를 저장합니다. 두 항목 유형에 대해 여러 필드를 채워야 합니다.

그러나 Redis를 사용하면 사용자가 위치와 단일 문자열만 지리 공간 집합의 값으로 저장할 수 있습니다. 이 제한을 피하기 위해 위의 필드를 JSON 문자열로 직렬화합니다. 그런 다음 이 문자열을 Redis에서 값으로 사용합니다. Redis에서 키와 값의 최대 크기는 512MB로 이 사용 사례에 충분합니다.

캐시 채우기

캐시를 채우기 위해 데이터베이스에서 모든 마커를 검색합니다. 각 확대/축소 수준에 대해 지도 클러스터링 알고리즘을 실행합니다. Redis의 GEOADD 를 사용하여 결과 마커와 클러스터를 해당 확대/축소 수준의 캐시에 삽입하고 위도와 경도와 함께 이전에 설명한 JSON 문자열을 전달합니다.

이 단계에서 전체 맵에서 맵 클러스터링 알고리즘을 실행하면(요청 시 사용자의 경계 상자에서가 아니라) 이론적으로 클러스터 배치에서 약간의 가장자리 차이가 발생할 수 있지만 전체 사용자 경험은 동일하게 유지됩니다.

캐시 쿼리

들어오는 요청에 대해 지정된 경계 상자를 Redis GEOSEARCH 명령에 전달합니다. 이 명령은 해당 영역의 마커 및 클러스터 후보를 검색하기 위해 지정된 확대/축소 수준의 캐시를 쿼리합니다.

캐시 새로 고침 계획 설계

20레벨 캐시 새로 고침은 비용이 많이 들기 때문에 프로젝트 요구 사항이 허용하는 한 자주 새로 고치는 것이 가장 좋습니다. 예를 들어 Playsports에서 스포츠 시설을 추가하거나 제거하면 캐시만 오래된 것으로 표시됩니다. 시간별 cron 작업은 필요한 경우 캐시를 새로 고칩니다. 캐시 부실 섹션에서 이에 대한 자세한 내용을 참조하십시오.

2단계: 추가 마커 세부 정보(선택 사항)

이 시점에서 대부분의 앱은 개별 마커 ID를 기반으로 세부정보를 가져와야 합니다. 이 세부 정보를 캐시에 있는 문자열화된 JSON 값의 일부로 만들 수 있지만 많은 앱에서 마커 세부 정보는 사용자별로 다릅니다. 모든 사용자를 위한 단일 공유 캐시가 있으므로 이러한 추가 필드를 거기에 저장할 수 없습니다.

우리의 최적화된 솔루션은 캐시 결과에서 개별 마커의 ID를 가져오고 데이터베이스에서 세부 정보를 가져옵니다. 이제 우리는 클러스터링 후에 남은 개별 마커만 찾고 있습니다. 지도가 축소될 때(대부분 클러스터가 있기 때문에) 또는 확대할 때(영역이 작기 때문에) 너무 많지 않습니다.

대조적으로, 순진한 솔루션은 클러스터링 전에 경계 상자의 모든 마커(및 세부 정보)를 찾습니다. 따라서 이 단계(선택 사항이지만 많은 앱에서 중요)는 이제 훨씬 빠르게 실행됩니다.

3단계: 결과 반환

클러스터가 구축되고 개별 마커가 향상되어 이제 이를 클라이언트에 전달할 수 있습니다. 일부 중요하지 않은 엣지 케이스를 제외하고 결과 데이터는 순진한 솔루션과 거의 동일하지만 훨씬 빠르게 제공할 수 있습니다.

추가 고려 사항

이제 두 가지 추가 요소를 살펴보겠습니다.

리소스 요구 사항

앱의 지도에 총 N개의 마커가 포함되어 있다고 가정해 보겠습니다. 최대 20개의 확대/축소 수준이 있으므로 최대 20N 캐시 항목을 저장해야 합니다. 그러나 실제로는 특히 더 낮은 확대/축소 수준에서 클러스터링으로 인해 캐시 항목의 실제 수는 훨씬 더 적습니다. 실제로 Playsports의 모든 캐시에 배포된 캐시 항목의 총 수는 ~2N에 불과합니다.

또한 캐시 값(문자열화된 JSON)의 길이가 ~250자(적어도 Playsports의 경우 합리적인 가정)이고 문자열 크기가 문자당 1바이트라고 가정하면 JSON 값은 약 2 * N * 250바이트입니다.

이 그림에 GEOADD 에서 사용하는 정렬된 집합에 대한 Redis의 내부 데이터 구조를 추가합니다. Redis는 1백만 개의 작은 키-값 쌍에 대해 85MB의 메모리를 사용하므로 Redis 내부가 캐시 항목당 100바이트 미만을 차지한다고 가정할 수 있습니다. 즉, 1GB RAM Redis 인스턴스를 사용하여 최대 140만 개의 마커를 지원할 수 있습니다. 마커가 전체 맵에 고르게 분포되어 캐시 항목 수가 20N에 가까운 드문 시나리오에서도 N은 여전히 ​​~140,000까지 올라갈 수 있습니다. Redis 인스턴스는 40억 개 이상의 키(정확히 말하면 2 ³² )를 처리할 수 있으므로 이것이 제한 요소가 아닙니다.

캐시 비활성

사용 사례에 따라 주기적으로 캐시를 새로 고치는 것만으로는 충분하지 않을 수 있습니다. 이러한 경우 속도가 제한된 작업 대기열을 사용할 수 있습니다. 캐시 부실을 줄이면서 캐시 새로 고침 횟수를 제한하여 시스템 부하를 줄입니다.

각 데이터베이스 업데이트 후에 캐시 새로 고침 작업을 대기열에 넣습니다. 이 대기열은 작업 수를 시간당 M으로 제한합니다. 이 절충안을 통해 시스템에 상대적으로 낮은 부하를 유지하면서(M에 따라 다름) 시간당 업데이트 속도를 높일 수 있습니다.

캐싱 전략이 맵 클러스터링 알고리즘보다 중요

순진한 솔루션보다 50배 이상 빠른 Playsports에 최적화된 솔루션이 잘 작동했습니다. 140만 마커 또는 기존 데이터의 100배 이상에 도달할 때까지 계속 잘 작동해야 합니다.

대부분의 지도 기반 웹 서비스 요청의 경우 확장성을 허용하기 위해 몇 가지 형태의 사전 계산이 필요합니다. 사용할 기술 유형과 특정 디자인은 비즈니스 요구 사항에 따라 다릅니다. 캐시 부실 요구, 마커 증대 및 마커 수는 솔루션을 설계할 때 고려해야 할 중요한 특성입니다.

Toptal 엔지니어링 블로그에 대한 추가 정보:

• 웹 개발자를 위한 최고의 온라인 매핑 도구 설문조사: 로드맵에 대한 로드맵
• GPS 프로그래밍 및 개발의 모험: 지리 공간 자습서