가상 면접 사례로 배우는 대규모 시스템 설계 기초 2
1장 근접성 서비스
[가상 면접 사례로 배우는 대규모 시스템 설계 기초 2] 도서 관련 참고 자료
GitHub - alex-xu-system/bytebytego
Contribute to alex-xu-system/bytebytego development by creating an account on GitHub.
github.com
1~3장은 지리적 위치 기반 관계성 데이터를 저장하고 서비스할 때 발생하는 문제를 다룹니다.
1. 문제 이해 및 설계 범위 확정
근접성 서비스(Proximity Service)
- 사용자의 위치나 다른 기기와의 물리적 거리를 기반으로 기능을 제공하는 서비스
기능 요구사항
- 사용자 위치와 검색 반경 정보에 매치되는 사업장 목록 반환
- 사업장 소유주가 사업장 정보 CRUD 가능, 실시간 반영 필요 X
- 고객은 사업장 상세 정보 읽기 가능
비기능 요구사항
- 낮은 응답 지연
- 데이터 보호
- 일반 데이터 보호 규정 (GDPR) : 개인정보 보호 권리 강화, 데이터 수집 전 동의, 데이터 보호 책임자(DPO) 지정, 데이터 침해 신고, 벌금
- 캘리포니아 소비자 개인정보 보호법 (CCPA) : 개인정보에 대한 접근, 삭제 및 거부 권리, 투명성, 옵트아웃 권리(소비자의 개인정보 판매 거부 권리), 차별 금지
- 고가용성 및 규모 확장성
개략적 규모 추정
- 일간 능동 사용자(DAU) : 1억 명
- 등록 사업장 : 2억 개
- QPS(Query per Second) = (1억X5) / 1일(10^5) = 5,000
2. 개략적 설계안 제시 및 동의 구하기
API 설계
- 검색 API
- [GET] 특정 검색 기준에 맞는 서업장 목록 반환
- 사업장 정보 관리 API
- [GET] 특정 사업장 상세 정보 반환
- [POST] 새로운 사업장 추가
- [PUT] 사업장 상제 정보 갱신
- [DELETE] 특정 사업장 정보 삭제
- 페이지 분할 (Pagination in the REST API)
- 장점 : 효율성(서버 및 네트워크 부하 감소), 관리 용이성, 사용자 경험 향상
- 주요 방법
- 오프셋 기반 : '오프셋(offset)'(데이터 시작 위치)과 '리밋(limit)'(한 페이지당 데이터 항목 수)을 사용
- 커서 기반 : 특정 항목을 기준으로 그 다음 페이지를 로드합니다. 이 '커서'는 일반적으로 특정 아이템의 ID나 타임스탬프를 사용
- 실제 장소 및 업장 검색 관련 API
데이터 모델
- 읽기/쓰기 연산 비율
- 읽기 연산 실행 빈도 多 ← 주변 사업장 검색, 사업장 정보 확인
- 읽기 연산 多 시스템은 MySQL 같은 RDBMS가 적합
- 데이터 스키마
- business 테이블 : 사업장 상세 정보
- 지리적 위치 색인 테이블 : 위치 정보 관련 연산 효율성을 높이고자 사용 (지리 데이터 처리 및 검색에 최적화)
개략적 설계안
- 사용자 (로드밸런서 기반 접근)
- 위치 기반 서비스 (LBS)
- 데이터베이스 클러스터
- DB Replication 아키텍처: Primary-Secondary (마스터-슬레이브)
- Primary DB : 쓰기 요청 처리
- Secondary DB (사본 DB) : 읽기 요청 처리
-
https://dev.mysql.com/doc/refman/5.7/en/group-replication-primary-secondary-replication.html
- 무상태 서비스(Stateless Service) : 서비스가 사용자의 이전 상태 정보를 저장하지 않고 각 요청을 독립적으로 처리하는 방식
- 시스템이 클라우드에 존재하는 경우, 여러 지역 및 가용성 구역에 서버를 추가하여 시스템 가용성 향상 가능
- DB Replication 아키텍처: Primary-Secondary (마스터-슬레이브)
- 데이터베이스 클러스터
- 사업장 관련 서비스
- 데이터베이스 클러스터
- 무상태 서비스
- 위치 기반 서비스 (LBS)
- 로드밸런서 : 유입 트래픽을 자동으로 여러 서비스에 분산시키는 컴포넌트
주변 사업장 검색 알고리즘
- 2차원 검색 : 주어진 반경으로 그린 원 안에 놓인 사업장 검색
- 위도 및 경도 컬럼 교집합 검색 → DB 색인으로는 한 차원의 검색 속도만 개선 가능, 비효율적
- 지리적 정보에 색인 생성 방법 : 지도를 작은 영역으로 분할하고 고속 검색 가능하도록 색인 생성
- 해시 기반 방법 : 균등 격자, 지오해시, 카르테시안 계층 등
- 트리 기반 방안 : 쿼드트리, 구글 S2, R 트리 등
- 균등 분할 격자
- 지도를 작은 격자 또는 구획으로 나누는 접근법
- 문제점 : 사업장 분포가 균등하지 않음, 주어진 격자의 인접 격자 찾기 어려움
- 지오해시
- 2차원의 위도 경도 데이터를 1차원의 문자열로 변환하고, 비트를 하나씩 증가하면서 재귀적으로 더 작은 격자로 분할하는 접근법
- 상세 설명 : https://guzene.tistory.com/337
- 지오해시는 12단계 정밀도를 가지며, 정밀도가 격자 크기를 결정함
- 최적 정밀도 : 사용자가 지정한 반경으로 그린 원을 덮는 최소 크기의 격자를 만드는 지오해시 길이
- 문제점1 : 격자 가장저리 처리
- 가까운 두 위치가 공통 접두어(prefix)를 갖지 않은 경우
- 지오해시는 해시값의 공통 접두어가 긴 격자들이 서로 더 가깝게 놓이도록 보장함
- 그러나, 가까운 두 위치가 공통 접두어를 갖지 않을 수 있다.
- 두 지점이 공통 접두어 길이는 길지만 서로 다른 인접 격자에 놓이는 경우
- 해결책 : 현재 격자를 비롯한 인접한 모든 격자의 모든 사업장 정보를 가져옴, 예시
- 가까운 두 위치가 공통 접두어(prefix)를 갖지 않은 경우
- 문제점2 : 표시 사업장 불충분
- 주어진 반경 내 사업장만 반환
- 검색 반경 확대
- 지오해시 값의 마지막 비트를 삭제하여 얻은 새 지오해시 값으로 주변 사업장 검색
- 충분한 사업장 수를 얻을 때까지 반복
- 2차원의 위도 경도 데이터를 1차원의 문자열로 변환하고, 비트를 하나씩 증가하면서 재귀적으로 더 작은 격자로 분할하는 접근법
- 쿼드트리
- 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할하는 접근법 (자료구조)
- ex. 격자에 담긴 사업장 수가 N개 이하가 될 때까지 분할
https://en.wikipedia.org/wiki/Quadtree - 쿼드트리 저장 메모리
- 말단 노드 수록 데이터 (832바이트)
- 격자 식별 목적 좌상단 및 우상단 꼭짓점 좌표 (32바이트=8바이트 X 4)
- 격자 내부 사업장 ID 목록 (ID당 8바이트 X 100)
- 내부 노드 수록 데이터 (64바이트)
- 격자 식별 목적 좌상단 및 우상단 꼭짓점 좌표 (32바이트=8바이트 X 4)
- 하위 노드 4개 가리킬 포인터 (32바이트=8바이트 X 4)
- 격자 안 최대 100개 사업장 → 말단 노드의 수=~200m/100=~200만, 내부 노드의 수=~200만/3=~37만
- 총 메모리 요구량 = 200만 X 832바이트 + 64만 X 64바이트 =~ 1.71GB
- 말단 노드 수록 데이터 (832바이트)
- 쿼드트리 구축 시간
- 시간 복잡도 : (n/100)log(n/100), n은 전체 사업장 수
- 서버 시작 시간 길어짐 → 적절한 배포 전략 고려 필요
- 쿼드트리 기반 주변 사업장 검색 방법
- 메모리에 쿼드트리 인덱스 구축
- 검색 시작점이 포함된 말단 노드와 만날 때까지 트리의 루트 노드부터 탐색
- 격자의 내용이 특정 기준을 만족할 때까지 2차원 공간을 재귀적으로 사분면 분할하는 접근법 (자료구조)
- 구글 S2
- 지구를 공간 채움 곡선 중 힐베르트 곡선을 사용하여 1차원 색인화하는 접근법
- 공간 채움 곡선(Space-filling curve) : 연속적인 선으로 2차원 또는 그 이상의 공간을 완전히 덮을 수 있는 곡선
- 힐베리트 곡성 상에서 인접한 두 지점은 색인화 이후 1차원 공간에서도 인접한 위치에 존재
https://s2geometry.io/
- S2의 장점
- 지오펜스(geofence) 구현
- 지오펜스 : 실세계 지리적 영역에 설정한 가상의 경계
- 동적 지정(특정 지점 반경 몇 km 이내) 또는 기존 경계선 기반 지정(스쿨 존이나 동네 경계) 가능
- 영역 지정 알고리즘
- 지오해시처럼 고정된 정밀도를 사용하는 대신 최소 수준, 최고 수준, 최대 셀 개수를 지정 가능
- 지오펜스(geofence) 구현
- 지구를 공간 채움 곡선 중 힐베르트 곡선을 사용하여 1차원 색인화하는 접근법
- 기업별 기술
- 지오해시 : Bing 지도, Redis, MongoDB, Lyft
- 쿼드트리 : Yext
- 지오해시 + 쿼드트리 : Elasticsearch
- S2 : Google Map, Tinder
3. 상세 설계
데이터베이스 규모 확장
- 사업장 정보 테이블
- 사업장 ID를 기준으로 샤딩(sharding)을 적용하여 부하 분산
- 샤딩 : 대규모 데이터베이스의 데이터를 여러 서버에 분산시켜 저장하는 방법
- 범위 기반 샤딩(Range-based Sharding): 데이터를 특정 범위에 따라 분할. 사용자 ID의 범위 또는 날짜 범위에 따라 데이터를 샤드에 할당 가능
- 해시 기반 샤딩(Hash-based Sharding): 데이터의 특정 키 값을 해시 함수를 통해 변환하고, 이 결과를 사용하여 데이터를 샤드에 할당
- 리스트 또는 디렉토리 기반 샤딩(List or Directory-based Sharding): 데이터를 샤드에 할당하기 위한 명시적인 목록 또는 디렉토리를 사용. 특정 규칙이나 리스트에 따라 데이터가 샤드에 할당
- 지오해시의 샤딩 로직은 까다로움 (추후 확인 필요)
- 지리 정보 색인 테이블
- 지오해시 방법 1 : 지오해시에 연결되는 모든 사업장 ID를 JSON 배열로 같은 열에 저장 (모든 사업장 ID가 한 열로. 갱신 어려움)
- 지오해시 방법 2 : 같은 지오해시에 속한 사업장 ID 각각을 별도 열로 저장 (사업장 ID가 각 행으로, 추천)
캐시
- 캐시 키
- 사용자 위치의 위도 경도 정보는 변동이 심하여 캐시 키로 부적절함
- 지오해시와 쿼드트리는 같은 격자 내 모든 사업장이 같은 해시 값을 갖도록 만들어서 해당 문제 해결
- { 키: 값 } : { 지오해시 : 해당 격자 내의 사업장 ID 목록}, { 사업장 ID : 사업장 정보 객체 }
- 데이터 유형
- 격자 내 사업장 ID
- 특정 지오해시에 해당하는 사업장 ID 목록을 미리 계산해서 레디스(Redis) 같은 키-값 저장소에 캐시
- 레디스 저장소 관련 메모리 요구랑 (추후 정리)
- 클라이언트 애플리케이션에 표시할 사업장 정보
- { 키: 값 } : { busniess_id : 사업장 이름, 주소, 사진 등을 담은 객체 }
- 격자 내 사업장 ID
지역 및 가용성 구역
- 기대효과
- 사용자와 시스템 사이의 물리적 거리 최소화
- 트래픽을 인구에 따라 고르게 분산
- 해당 지역의 사생활 보호법을 고려한 운영
최종 설계 도면 (시나리오)
- 주변 사업장 검색 : [목표] 주변 반경 500미터 내 모든 식당 검색
- 클라이언트 앱은 사용자의 위치 정보와 검색 반경(500미터)을 로드밸런서로 전송
- 로드밸런서는 해당 요청을 LBS로 보냄
- 사용자 위치 및 반경 정보를 기반으로 LBS는 검색 요건을 만족할 지오해시 길이 계산
- LBS는 인접한 지오해서를 계산하여 목록에 추가
- 목록 내에 있는 지오해시 각각에 대해 LBS는 '지오해시' 레디스 서버를 호출하여, 해당 지오해시에 대응하는 모든 사업장 ID를 추출
- 반환된 사업장 ID들로 '사업장 정보' 레디스 서버를 조회하여 각 사업장의 상세 정보를 취득
- 취득한 상세 정보를 기반으로 사업장과 사용자 간 거리를 계산하고, 우선순위를 매거 클라이언트 앱에 반환
- 사업장 정보 CRUD
- 해당 데이터가 '사업장 정보' 레디스 서버에 기록되어 있는지 확인
- 캐시된 경우 : 해당 데이터를 읽어 클라이언트로 반환
- 캐시되지 않은 경우 : DB 클러스터에서 사업장 정보를 읽어 캐시로 저장한 다음 클라이언트로 반환
- 해당 데이터가 '사업장 정보' 레디스 서버에 기록되어 있는지 확인