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

근접성 서비스는 음식점, 호텔, 극장, 박물관 등 현재 위치에서 가까운 시설을 찾는 데 이용되며, 구글 맵의 경우에는 가까운 k개 주유소 검색 등의 기능 구현에 이용된다. 근접성 서비스를 설계하고, 생각해보면 좋을 키워드에 대해 정리해보자.

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

• 최대 허용 반경은 20km 이다.
• 사용자가 UI에서 검색 반경을 변경할 수 있다.
• 사업장 소유주가 사업장 정보를 시스템에 추가/삭제/갱신할 수 있고, 다음날까지 변경된 정보가 반영된다.
• 사용자의 이동속도는 빠르지 않아서, 상시적으로 페이지를 갱신할 필요는 없다.
• 주어진 반경 내의 사업장만 대상으로 하고, 시간이 남으면 주어진 범위 안에 사업장이 많지 않은 경우를 어떻게 처리할지 고민해보자.

요구사항

요구사항 종류	요구사항 내용
기능	사용자의 위치와 검색 반경 정보에 매치되는 사업장 목록 반환
기능	사업장 소유주가 사업장 정보를 추가/삭제/갱신 가능 (실시간 반영 필요 없음)
기능	고객은 사업자의 상세 정보 조회 가능
비기능	사용자는 주변 사업장을 신속히 검색 가능
비기능	사용자의 위치 정보 보호 방법 고려
비기능	인구 밀집 지역에서 트래픽 급증 시에도 감당할 수 있는 설계

개략적 규모 추정

항목	추정값
DAU (일일 활성 사용자 수)	1억 명
등록된 사업장 수	2억 개
QPS (초당 쿼리 수)	5000 (사용자는 하루에 5회 검색을 시도한다고 가정)

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

개략적 설계 및 시스템 구성 요소

로드밸런서 (Load Balancer)

• 기능: URL 경로를 분석하여 트래픽을 적절한 서비스로 분배한다.

LBS (Location-Based Service)

• 기능: 주어진 위치와 반경 정보를 이용해 주변 사업장을 검색한다.
• 특징:
  • 읽기 요청 중심: 쓰기 요청은 거의 없고, 주로 읽기 요청이 빈번하게 발행한다.
  • 높은 QPS: 특히 인구 밀집 지역에서는 트래픽이 급증할 수 있다.
  • 무상태 서비스: 무상태 서비스이므로 수평적 규모 확장이 용이하다.

사업장 서비스

• 기능:
  • 사업장 정보 관리: 사업장 소유주가 사업장 정보를 생성, 갱신, 삭제한다.
  • 고객 조회: 고객이 사업장 정보를 조회한다.
• 특징:
  • 쓰기 요청: 사업장 정보의 생성/갱신/삭제로 인해 쓰기 요청이 발생한다.
  • 변동 QPS: QPS는 높지 않지만 특정 시간대에 조회 요청으로 인해 QPS가 높아질 수 있다.

데이터베이스 클러스터

• 구성: 주-부 데이터베이스 형태로 구성된다.
  • 주 데이터베이스: 쓰기 요청을 처리한다.
  • 부 데이터베이스: 읽기 요청을 처리한다.
• Replica Lag: 발생할 수 있지만, 사업장 정보가 실시간으로 갱신될 필요가 없기 때문에 큰 문제가 되지 않는다.

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

• 무상태 서비스: 두 서비스 모두 무상태 서비스이므로 특정 시간대에 스케일아웃하여 대응하고, 유휴 시간대에는 스케일인한다.
• 클라우드 배포: 여러 지역 및 가용성 구역에 서버를 배치하여 확장성과 가용성을 높인다.

주변 사업장 검색 알고리즘

1. 2차원 검색:

   • 설명: 단순히 x, y 좌표를 기준으로 범위 내의 점들을 검색한다.
   • 특징: 구현이 간단하지만, 검색 효율이 떨어질 수 있다.

2. 균등 격자 (Uniform Grid):

   • 설명: 공간을 균등한 격자로 나누고, 각 격자에 속한 점들을 관리한다.
   • 특징: 빠른 검색이 가능하지만, 데이터 분포가 고르지 않을 경우 효율이 떨어질 수 있다.

3. 지오해시 (Geohash):

   • 설명: 지리적 위치를 문자열로 인코딩하여 검색 및 저장한다.
   • 특징: 인접한 지역이 유사한 문자열을 가지며, 범위 검색에 효율적이다.

4. 쿼드트리 (Quadtree):

   • 설명: 2차원 공간을 재귀적으로 4분할하여 트리 구조로 관리한다.
   • 특징: 공간 분할을 통해 효율적인 검색을 가능하게 한다.

5. 구글 S2:

   • 설명: 지구를 3차원 구체로 간주하고, 이를 2차원 평면에 투영하여 셀로 나눈다.
   • 특징: 높은 정밀도로 지리적 위치를 표현하며, 다양한 크기의 셀을 통해 유연한 검색이 가능하다.

3단계: 상세 설계

상세 설계 부분에서 고민해볼 수 있는 포인트를 정리해보자.

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

지리 정보 색인 테이블, 2개의 데이터 구조를 설계할 수 있을텐데 어떤 방법이 더 적절할까?

알고리즘의 경우 비교적 간단한 지오해시를 사용한다.

방안 1: JSON 배열로 저장

• 설명: 각각의 지오해시에 연결되는 모든 사업장 ID를 JSON 배열로 만들어 같은 열에 저장.
• 특징:
  • JSON 배열을 사용하여 한 열에 다수의 사업장 ID 저장.
  • JSON 배열을 읽고, 갱신할 사업장 ID를 찾아내어 갱신.
  • 새 사업장을 등록할 때 중복 여부 확인을 위해 전체 데이터를 조회.
  • 병렬 갱신 연산 시 데이터 소실 방지를 위해 락 사용.

장점	단점
데이터 조회 시 한 번의 읽기로 모든 관련 사업장 ID 확인 가능	갱신 시 JSON 배열 전체를 읽고 수정해야 함
특정 지오해시에 속한 사업장 목록을 쉽게 관리	새 사업장 추가 시 중복 확인 위해 전체 데이터 조회 필요
구조가 간단하여 구현이 쉬움	병렬 처리 시 락 사용 필요, 성능 저하 가능

방안 2: 별도 열로 저장

• 설명: 같은 지오해시에 속한 사업장 ID 각각을 별도 열로 저장.
• 특징:
  • 지오해시와 사업장 ID를 각각의 열로 분리하여 저장.
  • 지오해시와 사업장 ID 컬럼을 합친 복합키 사용.
  • 사업장 정보 추가/삭제가 용이.

장점	단점
데이터 추가/삭제 시 복합키를 활용하여 효율적으로 처리 가능	특정 지오해시에 속한 모든 사업장 ID 조회 시 다수의 읽기 연산 필요
병렬 처리에 유리, 락 사용 불필요	조회 시 각 열을 개별적으로 접근해야 함
확장성과 성능 향상	구현 복잡도 증가 가능

방안 비교 및 추천

항목	방안 1	방안 2
데이터 조회 효율성	JSON 배열을 한 번에 읽어 효율적	다수의 읽기 연산 필요
데이터 갱신 효율성	배열 전체를 읽고 수정해야 함	개별 열에 접근하여 효율적
중복 확인 용이성	전체 데이터 조회 필요	복합키 활용으로 효율적
병렬 처리 적합성	락 사용 필요	락 사용 불필요
구현 난이도	상대적으로 쉬움	상대적으로 어려움

• 방안 1: 데이터 조회 빈도가 매우 높고, 갱신 빈도가 낮은 경우.
• 방안 2: 데이터 갱신 및 추가/삭제 빈도가 높고, 병렬 처리 효율성이 중요한 경우.

지리 정보 색인의 규모 확장, 어떻게 부하를 분산할 것인가?

지리 정보 색인의 규모 확장 방안 2가지

현재 지리 정보 색인 테이블 구축에 필요한 전체 데이터는 1.71GB의 메모리를 필요로 하여 서버 한 대에 충분히 수용 가능하지만, 읽기 연산의 빈도가 높을 경우 단일 서버의 CPU와 네트워크 대역폭으로 감당하지 못할 수 있다.

방안 1: 읽기 연산을 지원할 사본 데이터베이스 서버 늘리기

• 설명: 읽기 연산을 지원하기 위해 여러 사본 데이터베이스 서버를 추가하여 부하를 분산.
• 특징:
  • 개발이 상대적으로 쉽고 관리가 간편.
  • 데이터 일관성 유지가 필요.

장점	단점
개발 및 구현이 상대적으로 쉽다	데이터 일관성 유지에 추가적인 노력이 필요
관리가 간편하다	데이터 동기화 지연 발생 가능성
수평적 확장이 용이하다	대규모 읽기 트래픽을 처리하는 데 한계가 있을 수 있다

방안 2: 샤딩 적용

• 설명: 데이터베이스를 여러 샤드로 분할하여 부하를 분산.
• 특징:
  • 샤딩 로직을 애플리케이션 계층에 구현.
  • 관리가 까다로울 수 있음.
  • 필요에 따라 유일한 선택지가 될 수 있음.

장점	단점
데이터 분산으로 읽기 및 쓰기 성능 향상	구현 및 관리가 복잡함
대규모 트래픽을 효과적으로 처리 가능	샤딩 로직을 애플리케이션 계층에 구현해야 함
각 샤드의 부하를 독립적으로 조절 가능	데이터 재분할 시 다운타임 발생 가능성

우형 기술 블로그 DB분산처리를 위한 sharding, 우아콘 대규모 트랜잭션을 처리하는 배민 주문시스템 규모에 따른 진화 에서 관련 이슈를 다루고 있다.

방안 비교 및 추천

항목	방안 1: 사본 데이터베이스 서버 늘리기	방안 2: 샤딩 적용
개발 난이도	상대적으로 쉬움	상대적으로 어려움
관리 용이성	간편함	까다로움
데이터 일관성	동기화 지연 가능성 있음	샤드 간 일관성 유지 필요
확장성	수평적 확장 용이	수평적 확장 용이
트래픽 처리 능력	대규모 읽기 트래픽 처리에 한계 가능성	대규모 트래픽 효과적 처리 가능

• 방안 1: 시스템의 읽기 트래픽이 중간 수준이고, 데이터 일관성이 상대적으로 중요하지 않은 경우
• 방안 2: 시스템의 읽기 및 쓰기 트래픽이 매우 높고, 성능 최적화가 중요한 경우

지역 및 가용성 구역

서비스를 여러 지역과 가용성 구역에 설치했을 때 얻는 장점은 무엇일까?

1. 물리적 거리 최소화:
   • 사용자와 시스템 사이의 물리적 거리를 줄여 네트워크 지연 시간을 감소시킴.
2. 트래픽 분산:
   • 트래픽을 인구 밀집도에 따라 고르게 분산하여 시스템 부하를 효과적으로 관리할 수 있음.
3. 사생활 보호법 준수:
   • 국가별로 데이터 전송 제한 규정을 준수할 수 있음.
   • 특정 국가에서 발생하는 트래픽을 해당 국가 내 서비스로 처리하여 법적 규제에 대응.

여러 지역과 가용성 구역에 설치했을 때 고려해야 할 점

1. 데이터베이스 간 싱크:
   • 여러 지역에 걸친 데이터베이스 간의 데이터 동기화 문제
   • 글로벌 데이터베이스 저장 빈도가 너무 높아 부하가 발생할 수 있으며, 이를 줄이는 작업이 필요

글로벌서비스 블리자드의 장애보고서에서 관련 이슈를 다루고 있다. 데이터베이스 동기화 문제로 인해 발생하는 부하를 줄이기 위한 노력이 필요하다고 한다.

최종 설계도, 주변 반경 500미터 내 모든 식당을 찾는 경우 어떻게 동작할까?

1. 클라이언트 앱은 사용자의 위치와 검색 반경을 로드밸런서로 전송한다.
2. 로드밸런서는 해당 요청을 LBS로 보낸다.
3. 주어진 사용자 위치와 반경 정보에 의거하여, LBS는 검색 요건을 만족할 지오해시 길이를 계산한다.
4. LBS는 인접한 지오해시를 계산한 다음 목록에 추가한다.
5. 목록에 있는 지오해시 각각에 대해 LBS 는 지오해시 레디스 서버를 호출하여 해당 지오해시에 대응하는 모든 사업장 ID를 추출한다.
6. 반환된 사업장 ID들을 가지고 사업장 정보 레디스를 조회하여 각 사업장의 상세정보를 취득한다. 조건에 맞게 필터링 및 소팅 후에 클라이언트 앱에 반환한다.