[Book - 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2] 1. 근접성 서비스

근접성 서비스(proximity service)는 음식점, 호텔, 극장, 박물관 등 현재 위치에서 가까운 시설을 찾는 데 이용된다.

1단계: 문제 이해 및 설계 범위 확정

사용자가 검색 반경(radius)을 지정할 수 있어야 하나요?
검색 반경에 표시할 사업장이 충분치 않은 경우에는 검색 반경을 시스템이 알아서 넓혀도 괜찮을까요?
>> 주어진 반경 내의 사업장만 대상으로 가정
>> 시간이 남으면 주어진 범위 안에 사업장이 많지 않은 경우를 어떻게 처리할지 이야기 가능

최대 허용 반경은 얼마입니까?
20km(12.5mile)로 가정해도 괜찮을까요?
>> good

사용자가 UI에서 검색 반경을 변경할 수 있어야 하나요?
>> yes

사업장 정보는 어떻게 시스템에 추가되고, 삭제되고, 갱신되나요?
사업장 정보에 대한 작업 결과가 사용자에게 실시간으로 보여져야 할까요?
>> 사업장 소유주가 사업장 정보를 시스템에 추가, 삭제, 갱신 가능
>> 정보는 다음날까지 반영되어야 한다고 계약서에 명시되어 있다고 가정

사용자가 이동 중에 앱이나 웹사이트를 이용한다면 검색 결과는 시간이 흐름에 따라 달라져야 할텐데,
검색 결과를 항상 현재 위치 기준으로 유지하기 위해 화면을 자동 개신해야 할까요?
>> 사시적으로 페이지를 갱신할 필요X

기능 요구사항

위 대화에 근거하여, 다음 세 가지 핵심 기능에 집중

• 사용자의 위치(경도와 위도 쌍)와 검색 반경 정보에 매치되는 사업장 목록을 반환
• 사업장 소유주가 사업장 정보를 추가, 삭제, 갱신할 수 있도록 하되, 그 정보가 검색 결과에 실시간으로 반영될 필요는 없다고 가정
• 고객은 사업장의 상세 정보를 살필 수 있어야 함

비기능 요구사항

위 사업 요구사항으로부터 다음과 같은 비기능 요구사항을 도출할 수 있다.(이 각각을 면접관과 확인해야 함)

• 낮은 응답 지연(latency)
  • 사용자는 주변 사업장을 신속히 검색할 수 있어야 한다.
• 데이터 보호(data privacy)
  • 사용자 위치는 민감한 정보다.
  • 위치 기반 서비스를 설계할 때는 언제나 사용자의 정보를 보호할 방ㅇ법을 고려해야 한다.
• 고가용성(high availability) 및 규모 확장성(scalability) 요구사항
  • 인구 밀집 지역에서 이용자가 집중되는 시간에 트래픽이 급증해도 감당할 수 있도록 시스템을 설계해야 한다.

개략적 규모 추정

DAU는 1억 명이며 등록된 사업장 수는 2억이라고 하자.

---

2단계: 개략적 설계안 제시 및 동의 구하기

데이터 모델: 읽기/쓰기 비율

다음 두 기능의 이용 빈도가 높기 때문에 읽기 연산은 굉장히 자주 수행된다.

• 주변 사업장 검색
• 사업장 정보 확인

읽기 연산이 압도적인 시스템에는 MySQL 같은 RDBMS가 바람직할 수 있다.

개략적 설계

이 시스템은 위치 기반 서비스(location-based service, LBS)와 사업장 관련 서비스 두 부분으로 구성된다.

로드밸런서

로드밸런서는 유입 트래픽을 자동으로 여러 서비스에 분산시키는 컴포넌트다.
로드밸런서에 단일 DNS 진입점(entry point)을 지정하고, URL 경로를 분석하여 어느 서비스에 트래픽을 전달할지 결정한다.

위치 기반 서비스(LBS)

LBS는 시스템의 핵심 부분으로, 주어진 위치와 반경 정보를 이용해 주변 사업장을 검색한다.
다음과 같은 특징을 갖는다.

• 쓰기 요청이 없는, 읽기 요청만 빈번하게 발생하는 서비스이다.
• QPS가 높다. 특히 특정 시간대의 인구 밀집 지역일수록 그 경향이 심하다.
• 무상태(stateless) 서비스이므로 수평적 규모 확장이 쉽다.

사업장 서비스

주로 다음 두 종류의 요청을 처리한다.

• 사업장 소유주가 사업장 정보를 생성, 갱신, 삭제한다. 기본적으로 쓰기 요청이며, QPS는 높지 않다.
• 고객이 사업장 정보를 조회한다. 특정 시간대에 QPS가 높아진다.

데이터베이스 클러스터

primary-secondary DB 형태로 구성할 수 있다.
주 DB는 쓰기 요청을 처리하며, 부 DB는 일기 요청을 처리한다.

데이터는 주 DB에 기록된 다음에 부 DB로 복사된다.
복제에 걸리는 delay 때문에 주 DB 데이터와 부 DB 데이터 사이에는 차이가 있을 수 있다.

사업장 정보는 실시간으로 갱신될 필요가 없기 때문에 문제가 되지 않는다.

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

사업장 서비스와 LBS는 둘 다 stateless 서비스이므로 점심시간 등의 특정 시간대에 집중적으로 몰리는 트래픽에는 자동으로 서버를 추가하여 대응하고,
야간 등 유휴 시간 대에는 서버를 삭제하도록 구성할 수 있다.

시스템을 클라우드에 둔다면 여러 지역, 여러 가용성 구역(availability zone)에 서버를 두어 시스템 가용성을 높일 수 있다.

주변 사업장 검색 알고리즘

몇 방안들을 훑어보고 그 이면의 사고 프로세스를 검토한 다음,
각 방안에 어떤 타협적 측면(trade-off)이 존재하는지 논의하자.

방안 1: 2차원 검색

주어진 반경으로 그린 원 안에 놓인 사업장을 검색하는 방법이다.
가장 직관적이지만 지나치게 단순하다는 문제가 있다.

이 절차를 유사(pseudo) SQL 질의문으로 옮기면 다음과 같다.

SELECT business_id, latitude, longitude,
FROM business
WHERE (latitude BETWEEN {:my_lat} - radius AND {:my_lat} + radius)
AND
    (longitude BETWEEN {:my_long} - radius AND {:my_long} + radius)

이 질의는 테이블 전부를 읽어야 하므로 효율적이지 않다.

위도와 경도 컬럼에 색인을 만들어 두면 어떨까?
그래도 효율이 썩 좋아지지 않는다.
데이터가 2차원적이므로 컬럼별로 가져온 결과도 여전히 엄청난 양이다.

아래 그림을 보자.
위도 컬럼과 경도 컬럼에 색인을 만들어 놓으면 데이터 집합 1과 데이터 집합 2는 신속히 추출할 수 있을 것이다.
하지만 주어진 반경 내 사업장을 얻으려면 이 두 집합의 교집합을 구해야 한다.

이 연산은 각 집합에 속한 데이터의 양 때문에 효율적일 수 없다.

이 방안의 문제는 DB 색인으로는 오직 한 차원의 검색 속도만 개선할 수 있다는 것이다.

2차원 데이터를 한 차원에 대응시킬 방법을 살펴보기에 앞서, 우선 색인을 만드는 방법들부터 살펴보자.

• 해시 기반 방법
  • 균등 격자(even gird)
  • 지오 해시(Geohash)
  • 카르테시안 계층(Cartesian tiers)
• 트리 기반 방안
  • 쿼드트리(Quadtree)
  • 구글 S2
  • R 트리(R-tree)

각 색인법의 구현 방법은 서로 다르지만 개략적 아이디어는 같다.
즉, 지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만드는 것이다.

그 가운데 지오해시, 쿼드트리, 구글 S2는 실제로 가장 널리 사용되는 방안이다.

방안 2: 균등 격자

작은 격자 또는 구획으로 나누는 단순한 접근법이다.
하나의 격자는 여러 사업장을 담을 수 있고, 하나의 사업장은 오직 한 격자 안에만 속하게 된다.

이 방안의 문제는 사업장 분포가 균등하지 않다.

방안 3: 지오해시(Geohash)

지오해시는 균등 격자보다 나은 방안이다.
2차원의 위도 경도 데이터를 1차원의 문자열로 변환한다.

지오해시 알고리즘은 비트를 하나씩 늘려가면서 재귀적으로 세계를 더 작은 격자로 분할해 나간다.

우선, 전 세계를 본초 자오선과 적도 기준 사분면으로 나눈다.

그 각각의 격자를 또다시 사분면으로 나눈다.
이때 각 격자는 경도와 위도 비트를 앞서 살펴본 순서대로 반복하여 표현한다.

이 절차를 원하는 정밀도(precision)를 얻을 때까지 반복한다.

지오해시는 통상적으로 base32 표현법을 사용한다.

• 구글 본사 지오해시
  • 1001 11010 01001 10001 11111 11110 → 9q9hvu
• 메타 본사 지오해시
  • 1001 11010 01001 10011 10001 11011 → 9q9jhr

지오해시는 12단계 정밀도를 갖는다.
이 정밀도가 격자 크기를 결정한다.

지오해시 길이	격자 너비 × 높이
1	5,009.4km × 4,992.6km (지구 전체)
2	1,252.3km × 624.1km
3	156.5km × 156km
4	39.1km × 19.5km
5	4.9km × 4.9km
6	1.2km × 609.4m
7	152.9m × 152.4m
8	38.2m × 19m
9	4.8m × 4.8m
10	1.2m × 59.5cm
11	14.9cm × 14.9cm
12	3.7cm × 1.9cm

최적 정밀도는 어떻게 정할까?

사용자가 지정한 반경으로 그린 원을 덮는 최소 크기 격자를 만드는 지오해시 길이를 구해야 한다.
반경과 지오해시 사이의 관계를 보자.

반경 (킬로미터)	지오해시 길이
0.5km (0.31마일)	6
1km (0.62마일)	5
2km (1.24마일)	5
5km (3.10마일)	4
20km (12.42마일)	4

이 접근법은 대체로 잘 동작하지만 격자 가장자리 처리 방식에 관한 경계 조건(edge case)이 몇 가지 있다.(면접관과 상의)

• 격자 가장자리 관련 이슈

  • 지오해시는 해시값의 공통 접두어(prefix)가 긴 격자들이 서로 더 가깝게 놓이도록 보장한다.

    

• 격자 가장자리 이슈 1
  • 하지만 그 역은 참이 아니다.
  • 아주 가까운 두 위치가 어떤 공통 접두어도 갖ㅈ지 않는 일이 발생할 수 있다.
  • 이 문제점 때문에 단순한 접두어 기반 SQL 질의문을 사용하면 주변 모든 사업장을 가져올 수 없다.

    SELECT * FROM geohash_index WHERE geohash LIKE '9q8zn%'
    

• 격자 가장자리 이슈 2

  • 두 지점이 공통 접두어 길이는 길지만 서로 다른 격자에 놓이는 경우

    

  • 가장 흔히 사용되는 해결책은 현재 격자를 비롯한 인접한 모든 격자의 모든 사업장 정보를 가져오는 것이다.
  • 특정 지오해시의 주변 지오해시를 찾는 것은 상수 시간에 가능한 연산이다.
• 표시할 사업장이 충분하지 않은 경우
  • 선택지 1: 주어진 반경 내 사업장만 반환
  • 선택지 2: 검색 반경을 키운다.
    • 지오해시 값의 마지막 비트를 삭제하여 얻은 새 지오해시 값을 사용해 주변 사업장을 검색

    • 충분한 수 이상의 사업장을 얻을 떄까지 한 비트를 지워가며 격자 크기를 확장시킨다.

      

방안 4: 쿼드트리

쿼드트리는 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할하는 데 흔히 사용되는 자료 구조다.
예를들어 격자에 담긴 사업장 수가 특정 N 이하가 될 때까지 분할하는 것이다.

쿼드트리를 사용한다는 것은 결국 질의에 답하는 데 사용될 트리 구조를 메모리 안에 만드는 것이다.

아래 그림은 세계를 쿼드트리를 사용해 분할하는 자세한 과정을 시각화한 것이다.
이 트리의 루트 노드는 세계 전체 지도를 나타내고, 사분면을 나타내는 하위 노드의 사업장이 N개(예시는 100개)를 넘지 않을 떄까지 재귀적으로 분할한다.

쿼드트리 인덱스가 메모리를 많이 잡아먹지 않으므로 서버 한 대에 충분히 올릴 수 있다는 점만 확실히 알아 두자.

일기 연산 양이 많아지면 서버 한대의 CPU나 네트워크 대역폭으로는 감당하기 어려워진다.
그런 상황이 실제로 닥치면 읽기 연산을 여러 대 쿼드트리 서버로 분산시켜야 한다.

• 전체 쿼드트리 구축에 소요되는 시간은?
  • 각 말단 노드에는 대략 N개(예시는 100개) 사업장 ID가 저장된다.
  • 트리를 구축하는 시간 복잡도 = n/100 log n/100
  • 200m개의 사업장 정보를 인덱싱하는 쿼드트리 구축에는 몇 분정도가 소요될 수 있다.
• 쿼드트리로 주변 사업장을 검색하려면?
  1. 메모리에 쿼드트리 인덱스를 구축
  2. 검색 시작점이 포함된 말단 노드를 만날 떄까지, 트리의 루트 노드부터 탐색하여 충분한 사업장 수가 확보될 떄까지 인접 노드도 추가
• 쿼드트리 운영 시 고려사항
  • 서버를 시작하는 순간에 트리를 구축하면 서버 시작 시간이 길어져, 그동안 서버는 트래픽을 처리할 수 없다.
  • 따라서 새로운 버전의 서버 소프트웨어를 릴리스 할 때는 동시에 너무 많은 서버에 배포하지 않도록 조심해야 한다.
  • 시간이 흘러 사업장이 추가/삭제되었을 때 쿼드트리를 점진적으로 갱신하자.
• 실제로 쓰이는 쿼드트리 사례

  • 엑스트(Yext)가 제공한 덴버(Denver) 인근 쿼드트리 구축 사례

    

    • 인구 밀집 지역에는 작은 격자를, 그렇지 않은 지역에는 큰 격자를 사용하고 있다.

방안 5: 구글 S2

구글 S2 기하(geometry) 라이브러리는 쿼드트리와 마찬가지로 메모리 기반(in-memory)이다.

지구(sphere)를 힐베르트 곡선(Hilbert curve)이라는 공간 채움 곡선(space-filling curve)을 사용하여 1차원 인덱싱하는 방안이다.

힐베르트 곡선에 아주 유명한 특성이 하나 있는데, 힐베르트 곡선 상에서 인접한 두 지점은 인덱싱 이후 1차원 공간 내에서도 인접한 위치에 있다는 것이다.

S2의 장점을 간단히 짚어보자.

• 지오펜스(geofence)
  • 임의 지역에 다양한 수준의 영역 지정이 가능하다.

  • 관심 있는 영역의 경계를 정한 다음 해당 경계를 벗어난 사용자에게 알림을 보낼 수도 있다.

    

• 영역 지정 알고리즘(Region Cover Algorithm)
  • 지오해시처럼 고정된 정밀도를 사용하는 대신 최소 수준, 최고 수준 그리고 최대 셀 개수 등을 지정할 수 있다.
  • 셀 크기를 유연하게 조정할 수 있으므로 S2가 반환하는 결과가 좀 더 상세하다.

추천

면접 시에는 지오해시나 쿼드트리 가운데 하나를 선택하길 추천한다.(S2는 면접 시간 동안에 분명하게 설명하기 까다롭다.)

지오해시 vs 쿼드트리

지오해시

• 구현과 사용이 쉽다. 트리를 구축할 필요가 없다.
• 지정 반경 이내 사업자 검색을 지원한다.
• 정밀도를 고정하면 격자 크기도 고정된다. 인구 밀도에 따라 동적으로 격자 크기를 조정할 수는 없다.

• 색인 갱신이 쉽다.(row 하나를 제거하기만 하면 된다.)

  geohash	business_id
  9q8zn	3
  9q8zn	8
  9q8zn	4

쿼드 트리

• 트리 구축이 필요해서 구현하기가 살짝 더 까다롭다.
• k개 사업장을 찾을 때까지 검색 범위를 자동으로 조정할 수 있기 때문에, k번쨰로 가까운 사업장까지의 목록을 구할 수 있다.
• 인구 밀도에 따라 격자 크기를 동적으로 조정할 수 있다.
• 사업장 정보를 갱신하려면 루트 노드부터 말단 노드까지 트리를 순회해야 하기 때문에, 지오해시보다는 색인 갱신은 까다롭다.
  • 색인 갱신 시간 복잡도 = O(log n)
  • multi-thread를 지원해야 하는 경우에는 lock을 사용해야 하기 때문에 구현이 더 복잡해진다.
  • 말단 노드에 새로운 사업장을 추가할 수 없는 경우에는 리밸런싱을 해야 한다.

---

3단계: 상세 설계

시스템의 전반적인 형태를 파악하였으니, 이제 그 가운데 몇 부분을 좀 더 상세히 살펴보자.

• 데이터베이스 규모 확장
• 캐시(cache)
• 지역(region) 및 가용성 구역(AZ)
• 시간대 또는 사업장 유형에 따른 검색
• 최종 아키텍처 다이어그램

데이터베이스의 규모 확장성

본 설계에서 가장 중요한 두 가지 테이블인 사업장 테이블과 지리 정보 색인 테이블의 규모 확장성을 살펴보자.

사업장 테이블

한 서버에 담을 수 없을 수도 있다.
따라서 sharding을 적용하기 좋은 후보다.

이 테이블을 샤딩하는 가장 간단한 방법은 사업장 ID를 기준으로 하는 것이다.

지리 정보 색인 테이블

쿼드트리 보다 좀 더 단순한 지오해시를 사용해 보자.

같은 지오해시에 속한 사업장 ID 각각을 별도 열로 저장하는 방안을 사용하자.
즉 사업장마다 한 개 레코드가 필요하다.

이 경우에는 지오해시와 사업장 ID 컬럼을 합친 복합 키를 사용하면 lock을 사용할 필요가 없기 때문에 사업장 정보를 추가하고 삭제하기가 쉽다.

지리 정보 색인의 규모 확장

색인 전부를 최신 DB 서버 한 대에 충분히 수용할 수 있더라도,
읽기 연산의 빈도가 높다면 서버 한 대의 CPU와 네트워크 대역폭으로는 요청 전부를 감당하지 못할 수도 있다.
그런 상황에서는 여러 DB 서버로 부하를 분산해야 한다.

RDB 서버의 경우 부하 분산에는 읽기 연산을 지원할 사본 DB 서버를 늘리거나, 샤딩을 적용하는 방법을 사용한다.

지오해시 테이블의 경우 샤딩을 application layer에 구현하는 것은 까다롭고, 이번 설계안에서는 데이터 전부를 서버 한 대에 담을 수 있으므로, 읽기 부하를 나눌 사본 DB 서버를 두는 방법이 더 좋을 것이다.

지리 정보 색인 테이블의 규모를 확장할 때는 사본 DB 활용을 추천한다.

캐시

캐시 계층 도입 전에는 정말 필요한가? 질문을 먼저 던져야 한다.

• 처리 부하가 읽기 중심이고 DB 크기는 상대적으로 작아서 모든 데이터는 한 대 DB 서버에 수용 가능하다.
  • 이 경우 질의문 처리 성능은 I/O에 좌우되지 않으므로 메모리 캐시를 사용할 때와 비슷하다.

  DB 전체 크기가 서버 메모리(RAM)에 다 올라갈 정도로 작다는 의미
  따라서 디스크가 아니라 메모리에서 데이터가 조회됨

• 읽기 성능이 병목이라면 사본 DB를 증설해서 읽기 대역폭을 늘릴 수 있다.

면접관과 캐시 도입을 의논할 때는 벤치마킹과 비용 분석에 각별히 주의해야 한다는 사실을 유념하자.

캐시 키

위치가 조금 달라지더라도 변화가 없어야 이상적이므로 사용자 위치 정보(위도, 경도)는 캐시 키로 적절하지 않다.
지오해시나 쿼드트리는 이 문제를 같은 격자 내 모든 사업장이 같은 해시 값을 갖도록 만들 수 있기 때문에 효과적으로 해결한다.

캐시 데이터 유형

• 격자 내 사업장 ID
  • 사업장 정보는 상대적으로 안정적이라 자주 변경되지 않는다.
  • 따라서 특정 지오해시에 해당하는 사업장 ID 목록을 미리 계산한 다음 Redis 같은 key-value 저장소에 cache할 수 있다.
• 클라이언트 애플리케이션에 표시할 사업장 정보
  • 이 유형의 데이터는 쉽게 캐시할 수 있다.

지역 및 가용성 구역

지금까지 살펴본 위치 기반 서비스는 여러 지역과 가용성 구역에 설치하면 기대 효과는 다음과 같다.

• 사용자와 시스템 사이의 물리적 거리를 최소한으로 줄일 수 있다.
  • 사용자에게 가까운 지역의 데이터센터로 연결될 것이다.
• 트래픽을 인구에 따라 고르게 분산하는 유연성을 확보할 수 있다.
  • 일본과 한국 같이 인구 밀도가 아주 높은 국가는 별도 지역으로 빼거나, 아예 한 지역 안에서도 여러 가용성 구역을 활용하여 부하를 분산시키는 것이 바람직할 수 있다.
• 그 지역의 사생활 보호법에 맞는 운영이 가능하다.

추가 질문: 시간대, 혹은 사업장 유형별 검색

지오해시나 쿼드트리 메커니즘 사용 시 검색 결과로 얻어지는 사업장 수가 적으므로,
근처 사업장 ID부터 전부 확보한 다음 그 사업장 정보를 전부 추출해서 필터링

최종 설계도

주변 사업장 검색

1. 주변 내 모든 식당을 찾는 경우, 우선 클라이언트 앱은 사용자의 위치와 검색 반경을 로드밸런서로 전송한다.
2. 로드밸런서는 해당 요청을 LBS로 보낸다.
3. 주어진 사용자 위치와 반경 정보에 의거하여, LBS는 검색 요건을 만족할 지오해시 길이를 계산한다.
4. LBS는 인접한 지오해시를 계산한 다음 목록에 추가한다.
5. LBS는 지오해시 레디스 서버를 호출하여 해당 ‘지오해시’에 대응하는 모든 사업장 ID를 추출한다.
6. 반환된 사업장 ID들을 가지고 ‘사업장 정보’ 레디스 서버를 조회하여 각 사업장의 상세 정보를 취득한다.
   • 해당 상세 정보에 의거하여 사업장과 사용자 간의 거리를 확실하게 계산하고, 우선순위를 매긴 다음 클라이언트 앱에 반환한다.

사업장 정보 조회, 갱신, 추가 그리고 삭제

모든 사업장 정보 관련 API는 LBS와는 분리되어 있다.

새로 추가하거나 갱신한 정보는 다음날 반영된다는 것을 사업장과 합의하였으므로, 캐시에 보관된 정보 갱신은 밤사이 작업을 돌려서 처리할 수 있다.

---

4단계: 마무리

주변 검색 기능의 핵심인 근접성 서비스를 설계해 보았다.
지리 정보 색인 기법을 활용하는 전형적인 LBS 서비스다.

1장 요약