[01일차] | 대규모 시스템 설계 기초2 | 책너두

1장 근접성 서비스

• 근접성 서비스(proximity service)는 네이버, 카카오, 구글 지도 등의 사용자의 위치를 기반으로 주변 정보를 제공하는 서비스를 말한다.

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

기능 요구사항 vs 비기능 요구사항

• 특정 프로덕션 앱의 모든 기능을 주어진 시간 내에 설계하지 못하는 것은 당연하다.

• 어느 수준까지, 어느 부분을 중점적으로 설계할지에 대한 범위를 좁혀나가야 한다.

  • 이 과정이 오히려 면접자로 하여금 걱정을 덜어주고, 힌트를 얻을 수 있는 기회라고 생각한다.
  • 오히려 면접 과정에서, 실무에서보다 더 많은 정보를 제공받을 수 있다고 생각한다.

• 결과적으로 아래의 두 가지 산물이 나와야 한다.

  • 기능 요구사항
  • 비기능 요구사항

• 기능 요구사항은 면접관이 명백하게 필요로하는 기능을 말한다.

  • 여기서는 아래의 세 가지를 예시로 들었다.
    • 사용자의 위경도와 검색 반경에 매치외는 주변 정보를 제공한다.
    • 사업 소유주가 사업장의 정보를 등록/수정할 수 있으며, 실시간으로 반영될 필요는 없다.
    • 고객은 사업장의 상세 정보를 조회 할 수 있어야 한다.

• 비기능 요구사항은 면접관이 명시하지는 않았지만, 달성이 필요한기능을 말한다.

  • 여기서는 아래의 세 가지를 추정할 수 있다.
    • 낮은 지연시간
    • 개인정보보호
    • 고가용성

개략적 규모 추정

• 사용자 수(DAU): 1억(100,000,000)명
• 사업장 수: 2억(200,000,000)개
• 개략적 QPS 추산
  • 앞으로 1일(86400s)는 100,000s로 가정한다.
  • 1일 1명의 사용자가 5회의 조회를 한다고 가정한다.
  • 결과적으로 QPS는 5,000(5억 / 100,000)이 된다.

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

• 이 과정에서는 큰 틀에서의 설계안을 제시하고, 면접관의 동의를 구한다.

• 주요 주제는 아래와 같다.

  • API 설계
  • 개략적 설계
  • 주변 사업장 검색 알고리즘
  • 데이터 모델링

API 설계

위치 기반 검색 API

GET /v1/search/nearby

사업장 관련 API

GET /v1/businesses/:id
POST /v1/businesses
PUT /v1/businesses/:id
DELETE /v1/businesses/:id

개략적 설계

• 위치 기반 서비스(LBS)와 사업장 서비스로 구분한다.
• 이는 읽기 위주의 서비스와 쓰기/수정/삭제가 필요한 서비스로 구분하기 위함이다.

주변 사업장 검색 알고리즘

Q? 사실 엄밀히 말하면 이 방법들 모두 공통적으로 '반경'을 기준으로 검색하는 것이 아닌 것으로 보인다.

방안 1: 2차원 검색

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

• 이 방법은 크게 두 가지 단점이 있다.
  • 위도, 경도별 데이터를 구한 뒤 이를 교집합 하는 과정에서 성능이 떨어질 수 있다.
  • 인덱스를 사용할 수 없다.

방안 2: 균등 격자

• 위도, 경도를 균등한 격자로 나누어서, 해당 격자에 속하는 사업장을 찾는 방법이다.
• 하지만 하나의 격자 안에 존재하는 사업장이 균일하지 않다.

방안 3: 지오해시

• 지오해시는 위도, 경도를 문자열로 변환하는 방법이다.

  • 최대 12단계 정밀도를 가지며, 12단계는 3cm 정도의 정밀도를 가진다.
  • 필요한 반경에 따라 적당한 정밀도를 선택할 수 있다.

• 하지만 이 방법에도 단점이 있다.

  • 인접한 격자를 찾는 방법이 복잡하다.
    • 일반적인 경우 지오해시는 공통 접두어로 인접지역을 찾을 수 있다.
    • 하지만 특정 지점에서는 이 방법이 적용되지 않기 때문이다.
  • 공통 접두어를 갖지만 다른 지역에 속하는 경우가 있다.
    • 이로인해 주변 격자의 데이터도 함께 가져와야 한다.

방안 4: 쿼드트리

• 쿼드트리는 2차원 공간을 재귀적으로 4개의 사분면으로 나누는 방법이다.
• 내부 노드와 말단 노드의 구분과, 식별자를 사용하는 방법이 중요하다.
  • 처리하는 시간과 저장을 위한 공간이 생각보다 크지 않다는 것만 확인 하면 된다.

Q? 좌상/우하단 좌표를 32바이트로 저장할거라면, 지오해시처럼 비트로 구분하는게 낫지 않을까?
좌표를 기준으로 분할한다면, 공간도 공간이지만 탐색도 어렵고 부동소수점 오차도 생길텐데?

• 사업장이 업데이트되고, 트리를 리밸런싱하는 방법이 골치아플 것 같다.

방안 5: 구글 S2

• 힐베르트 곡선을 사용한 방법이다.
• 이를통해 2차원 공간을 1차원으로 색인 할 수 있다.
  • 특징으로는, 2차원으로 인접한 지역이 1차원으로도 인접하다. 또한 역도 성립한다.
• 지오펜스(geofence)와 같은 기능을 구현할 때 유용하다.
  • 이를 통해 보다 풍부한 기능을 제공 할 수 있다.

+@ 지오해시 vs 쿼드트리

• 둘 다 사용해보지는 않았지만, 지오해시가 더 간단하고 편리한 솔루션이 아닌가 싶다.
• 쿼드트리는 유지보수 소요가 매우 커 보인다. 그렇다고 몹시 뛰어난 기능을 제공하는 것은 아닌것 같다.

Q? 쿼드트리가 뛰어난 점이 뭐가 있나? 특정 구간에 밀집도가 매우 큰 경우?
하지만 cm단위까지 정밀도를 요구하는 서비스가 아니라면, 지오해시가 더 효율적이지 않을까?