대규모 시스템 설계 기초 2 (1장)

게시 2024/02/05 업데이트 2024/05/27

By seonb2n 12 분읽는 시간

가상 면접 사례로 배우는 대규모 시스템 설계 기초 2 (1장) 의 내용 중, 인상적이었던 부분을 발췌 및 요약합니다.

근접성 서비스

기능 요구사항

세 가지의 핵심 기능은 다음과 같다.

사용자의 위치(경도와 위도 쌍)와 검색 반경 정보에 매치되는 사업장 목록을 반환
사업장 소유주가 사업장 정보를 추가 삭제 갱신할 수 있지만 실시간 반영될 필요는 X
고객은 사업장의 상세 정보를 살필 수 있어야 한다.

API 설계

GET /v1/search/nearby

request
{
  latitude [위도],
  longitude [경도],
  radius [반경 범위]
}

response

{
  total: 10,
  businesses: [business object array]
}

특정 검색 기준에 맞는 사업장 목록을 반환한다.

사업장의 조회는 빈번하지만(읽기 연산은 자주 수행), 사업장 정보 업데이트는 빈번하지 않다.

개략적 설계

로드 밸런서

로드 밸런서는 유입 트래픽을 여러 서비스에 분산시킨다.

위치 기반 서비스(LBS)

시스템의 핵심으로, 주어진 위치 정보와 반경 정보를 통해 주변 사업장을 검색한다.

사업장 서비스

고객이 사업장 정보를 조회 및 소유주가 CUD 한다.

데이터베이스 클러스터

주 데이터베이스는 쓰기 요청을 처리하며, 부 데이터베이스는 읽기 요청을 처리한다.

사업장 서비스와 LBS 의 규모 확장성

사업장 서비스와 LBS 는 둘 다 무상태 서비스이다.

주변 사업장 검색 알고리즘

레디스 지오 해시나 PostGIS 를 활용한다. 어떤 방법을 사용할지 살펴보자

2차원 검색

주어진 반경으로 원 안에 놓인 사업장을 검색하는 방법이다.

  
SELECT business_id, latitude, longitude
FROM business_locations
WHERE latitude between {my_lat - radius and my_lat + radius} and longitude between {my_lon - radius and my_lon + radius}

이 질의는 테이블 전부를 읽어야 하므로 효율적이지 않다. 위도 경도 칼럼에 대해서 index 를 만들어서 효율을 조금 올릴 수는 있을 것이다. business_locations 의 latitude, longitude 컬럼에 대해서 인덱스를 만들기엔 데이터의 양 때문에 효율이 좋지 않다.
결국 문제는 2차원의 공간 인덱스를 어떻게 사용할 것인지이다.

postgis 에서는 R-Tree 로 geometry 타입의 데이터에 대해 공간 인덱스를 만들 수 있다.

공간 인덱스를 만드는 핵심 원리는 다음과 같다. 지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만드는 것이다.

균등 격자

지도를 작은 격자 또는 구획으로 나누는 단순한 접근법이다. 이렇게 하면 하나의 격자는 여러 사업장을 담을 수 있을 것이다. 그러나 이 방법에는 격자 내 사업장 분포가 균등하지 않다는 제약이 있다. 뉴욕 한복판의 격자와 사막 한 가운데의 격자의 사업장 분포는 큰 차이가 있을 것이다.
이 제약을 해결하기 위해 인구 밀집이 높은 지역은 작은 격자, 낮은 지역은 큰 격자를 사용할 수도 있겠다.

지오해시(Geohash)

지오해시는 2차원의 위도 경도 데이터를 1차원 문자열로 변환하는 것이다. 전 세계를 4분면으로 나누면 다음과 같을 것이다.

01 11
00 10

각각의 격자를 사분면으로 나누고, 반복해서 나누다 보면 원하는 정밀도에 도달할 수 있다.

구글 본사 지오 해시
9q9 hvu

지오해시의 길이에 따라 대략적으로 다음과 같은 범위를 포함한다.
4 자리 지오해시는 39.1 km * 19.5km
6 자리 지오해시는 1.2 km * 609.4 m
우리는 4-6 자리의 지오해시를 사용하면 된다. 지오해시는 해시값의 공통 접두어가 유사할 수록 가까운 위치에 놓이도록 보장한다.
그러나 그 역은 참이 아니어서 가깝다고 유사한 접두어를 갖고 있지는 않다. 두 지점이 적도나 자오선상의 다른 반쪽에 놓이는 경우다. 따라서, 단순한 접두어 기반 SQL 을 사용한다고 주변 모든 사업장을 가져올 수는 없다.

  
select * from geohash_index where geohash like '9q8zn%';

이처럼, 격자 가장자의 차이로 인해서 인접한 모든 격자의 사업장 정보를 가져오는 것은 어렵다. 따라서 현재 격자와 인접한 모든 격자의 모든 사업장 정보를 가져와야 할 것이다.

표시할 사업장이 충분하지 않은 경우

현재 격자와 주변 격자를 다 살펴도 표시할 사업장이 충분하지 않다면 검색 반경을 키워야 한다. 지오해시 값의 마지막 비트를 삭제하여 지오해시의 범위를 4배씩 확장해보자.

쿼드 트리

쿼드 트리 또한 널리 사용되는 해결책이다. 쿼드 트리는 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할하는 것이다.
예를 들면 격자 내 사업장 수가 100 개 이하가 될 때까지 분할하는 것이다. 이 쿼드트리는 질의에 사용될 트리 구조를 메모리 안에 만드는 것이다. 따라서 쿼드 트리는 LBS 서버에 존재해야 하며, 서버가 시작하는 시점에 구축된다. 코드로는 다음과 같은 로직일 것이다.

  
public void buildQuadTree(TreeNode node) {
  if (countNumberOfBusinessesInCurrentGrid(node) > 100) {
    // node 를 4분할 한다.
    node.subdivide();
    // 4분할된 각각의 child 에 대해서 다시 재귀함수를 호출한다.
    for (TreeNode child : node.getChildren()) {
      buildQuadtree(child);
    }
  }
}

전체 사업장이 n 개일 때, 쿼드트리 구축 시간 복잡도는 n/100 * log(n/100) 이다. 주변 사업장을 검색하기 위해서는 검색 시작점이 포함된 말단 노드를 만날 때까지 트리의 루트 노드부터 탐색하면 된다.

쿼드 트리 운영 시 고려사항

쿼드트리 구축에는 몇 분이 소요된다. 한번에 여러 대의 서버에 배포를 하게 되면, 서버는 그 시간 동안 트래픽을 처리할 수 없다.
배포 시, 일부 서버에만 순차적으로 배포하는 방안을 고려해야 하며 도그 파일에 주의하자.

구글 S2

구글 S2 기하 라이브러리는 이 분야에서 아주 유명한 솔루션이다. 메모리 기반 솔루션이며, 힐베르트 곡선을 사용해서 지도를 1차원 색인화하는 방안이다.

힐베르트 곡선 상에서 인접한 두 지점은 색인화 이후 1차원 공간 내에도 인접한 위치에 있다. 따라서 1차원 공간 내에서의 검색은 2차원 공간에서의 검색보다 훨씬 더 효율적이다.

지오해시 vs 쿼드트리

지오해시

구현과 사용이 쉽고, 트리를 구축할 필요가 없다.
반경 이내 사업장 검색을 지원한다.
동적인 격자 크기의 조정이 어렵다.
색인 갱신이 쉽다. 사업장 하나를 삭제하려면 지오 해시 값과 사업장 식별자가 같은 열 하나를 제거하기만 하면 된다.

쿼드트리

구현하기가 까다롭다. 트리 구축이 필요하다.
쿼드트리를 세밀하게 구축하면, K 번째로 가까운 사업장까지 찾을 수 있다.
인구 밀도에 따라 격자 크기를 동적으로 조절할 수 있다.
색인 갱신이 어렵다. 사업장 정보의 삭제를 위해서 루트 노드부터 말단 노드까지 트리를 모두 순회해야 한다.

캐시

캐시의 도입이 정말 좋은 결과로 이어질지는 고민해봐야 한다.

캐시 키

사용자의 위치를 캐시 키로 잡으면, 대부분의 경우 캐시 히트가 되지 않을 것이다. 지오 해시를 키로 잡는 것을 고려해보자. 해당 격자 내의 사업장 ID 목록을 값으로 설정하면 된다.
사업장 ID 도 키로 잡을 수 있을 것이다. 사업장 정보 객체를 캐싱하자.

독서, 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2