1. 접근성 서비스

결론을 이야기하자면 작업에서 발생할 수 있는 시간 복잡도를 계산하는게 정말 중요함을 깨달았다. 상승하는 데이터 양에 따라 유지가 가능한지를 확인할 수 있기 때문이다. 우리가 예측한 결과가 나오지 않을 수 있다. 그래도 일관성있는 수치라면 성능 튜닝 포인트가 될 수 있다.

책 정리 내용

근접성 서비스는 가까운 시설을 찾는 데 이용된다.

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

설계 범위 좁히기

• 사용자 기준
  • 사용자가 검색 반경(radius)를 지정할 수 있는지?
  • 사용자가 확인할 수 있는 최대 허용 반경은 얼마인지
  • 사용자가 UI에서 검색 반경 설정이 가능한지?
  • 검색 반경 내 표시할 사업장이 충분하지 않은 경우 검색 반경을 자동으로 늘릴지?
  • 검색 결과를 현재 위치 기준으로 갱신해야 하는지?
• 사업장 기준
  • 사업장 정보는 어떻게 관리되는지?
  • 사업자 정보가 업데이트되면 실시간으로 반영해야 하는지?

요구사항 정제

• 기능 요구사항
  • 사용자 위치와 검색 반경 기준으로 사업장 목록 반환
  • 사업장 소유주가 정보 추가, 삭제, 갱신 가능
  • 사용자는 사업장 상세 정보 조회 가능
• 비기능 요구사항
  • 낮은 응답 지연 필요
  • 개인 데이터 보호(사용자 위치 정보 보호)
  • 고가용성 및 규모 확장성 필요

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

대략적으로 API 스펙과 데이터 모델을 결정한다. API 스펙은 넘어가고 데이터 모델을 살펴보겠다.

데이터 모델

데이터 모델에서 읽기/쓰기 비율에 따라 어떤 데이터베이스를 사용할지 결정한다. 책에서는 읽기 연산이 많은 경우 RDBMS를 추천하고 있다.

책에서는 RDBMS를 추천하고 있지만 명확한 이유는 모르겠다. NoSQL을 사용할 경우 정형화가 되어 있지 않아 조인이 어렵고 최적화가 되어 있지 않을 수 있곤 하지만 조인 없이 데이터를 저장할 수 있다. 그리고 읽기 시 데이터 변환 오버헤드가 발생할 수 있지만 BSON으로 관리하면 그 문제를 해결 할 수 있어보인다.

개략적 설계

개략절 설계는 위치 기반 서비스(LBS)와 사업장 관리 서비스로 구성한다. 각각의 서비스는 성격이 다르니 성격에 맞게 구현한다.

• 위치 기반 서비스
  • 읽기 요청이 많고 쓰기 요청은 없다.
  • 특정 시간대에 QPS가 높다.
  • 인구 밀집 지역에 QPS가 높다.
• 사업장 관리 서비스
  • 읽기 요청과 쓰기 요청이 미비하다.
  • 특정 시간대에 QPS가 높다.
  • TPS는 미비하다.

데이터베이스

데이터베이스는 primary-secondary 형태를 추천한다. 데이터 읽기 처리량을 높이기 위해서 secondary를 늘리기만 한다면 성능이 떨어질 가능성이 있다. primary 에 여러 secondary 가 접근한다면 작업량만 늘어나게 된다. 성능 향상을 위해 primary와 secondary 사이 읽기만을 처리하는 secondary를 추가하는 것도 방법이다.

출처 : https://dev.mysql.com/doc/refman/8.3/en/replication-solutions-performance.html

복제하는 시간이 지연(delay)되더라도 실시간으로 갱신될 필요가 없다면 적용해도 괜찮아 보인다. 지연(delay)을 얼만큼 유지할지는 선택 옵션이다. 지연되는 시간을 줄이더라도 성능에 영향을 주는건 아니다. 단지 지연했을 때의 장점을 얻지 못할 뿐이다.

실제로 지연 시간을 설정했지만 업데이트를 따라오지 못하는 경우도 발생한다. 이런 경우는 성능 이슈이기 때문에 다음 링크를 참고해서 해결하길 바란다.

주변 사업장 검색 알고리즘

어떻게 검색하냐에 따라 많은 차이가 발생한다. 검색 방법은 다음과 같다.

• 2차원 검색
• 균등 격자
• 지오 해시
• 쿼드 트리
• 구글 S2
• (new)h3

2차원 검색

2차원 검색은 말그대로 범위 검색이다. 예를 들면 경도 범위에 있는 데이터 중 원하는 위도 범위에 있는 데이터를 찾게 된다.

위 케이스처럼 다중 컬럼 인덱스를 건다고 해도 범위에 경도 탐색을 진행할 수 밖에 없다.

위도와 경도 중 데이터가 적은 영역을 기준으로 해도 상상이상으로 많다. 절대 이 방법을 고려하면 안된다. 책에서 이야기 하는 것처럼 하나의 인덱스(1차원)만 속도를 개선해서는 문제를 해결 할 수 없다. 인덱스 하나로 2차원 범위를 표현할 수 있어야 한다.

균등 격자

균등한 거리로 공간을 나누고 사업장을 담는 방식도 가능하다. 우리가 해당 공간에 존재한다면 해당 공간을 반환하면 된다.

이 방법의 문제는 균등한 거리가 고정되어서 조회 조건 마다 성능이 달라질 수 있고, 데이터 불균형으로 특정 영역에서 데이터 조회가 비용이 비싸진다.

지오 해시

지오 해시는 위도 경도 데이터를 문자열로 변환해 표현하는 방식이다. 비트를 하나씩 늘려나가며 재귀적으로 작은 격자로 분할한다.

작은 격자는 12단계로 나뉘어지게 되고 원하는 영역이 나올 만큼 분할한다. 아래 그림처럼 최소 크기로 덮을 만큼의 정밀도를 찾아 격자를 반환한다.

생각할 수 있는 문제는 연관되지 않은 범위 밖 데이터가 포함된다는 문제가 있다. 또한 데이터가 집중되어 있는 경우 조회 비용이 비싸진다는 점도 해결하기 못한다.

쿼드 트리

격자 내용이 원하는 기준에 만족할 때까지 2차원 공간을 재귀적으로 4분할 하게 된다. 원하는 조건이 사업장 수가 100 이하일 때까지 분할하라가 될 수 있다. 대충 지도로 표현하면 다음처럼 표현된다. 데이터가 집중되어서 조회 비용이 비싸지는 문제를 일부 해결할 수 있다.

쿼드트리를 담는 메모리 양이 많아 보일 수 있지만 말단 노드 데이터 양과 내부 노드 데이터 양을 고려하면 총 메모리 요구량이 작은 편이다.

쿼드트리는 색인 갱신이 까다롭다. 사업장 정보를 갱신하려면 트리를 순회해야 하고 리밸런싱이 필요하다면 더욱 복잡해진다.

쿼드 트리의 아쉬운점은 서버에 직접 구현해야 한다는 점이다. 상태를 가지는 서버는 관리하기 어렵다. 서버 시작마다 쿼드 트리 생성 소요 시간으로 인해 추가적인 다운 타임이 발생한다. 그 발생을 줄이기 위해 블루-그린 배포를 운영하게 되면 여러 대의 쿼드 트리가 데이터베이스에 접근하는 문제가 있을 수 있다. 운영하게 된다면 어떻게 다운 타임을 줄이고 데이터베이스 부하를 줄일 수 있을지가 고민 포인트다.

구글 S2

쿼드트리와 마찬가지로 메모리 기반으로 공간을 힐베르트 곡선을 사용해 색인화하는 방법이다. 힐베르트 곡선은 1차원 만 색인화 하지만 인접한 두 지점은 1차원 공간에서도 인접해있다는 특징을 사용했다.

s2는 지오펜스 구현에도 두각을 나타낸다. 일반적인 그리드 표현 방식은 현재 영역을 포함하는 최소 단위를 제공하다보니 포함되지 않는 영역까지 전달해야 하는 경우가 있다.

s2를 사용하게 되면 현재 영역 보다 작게 분할해서 표출해주는 영역 단위를 이용해 포함되는 영역을 쉽게 조절할 수 있다.

또한 영역 지정 알고리즘(Region Cover Algorithm)을 제공해 정밀도를 조절할 수 있게 된다. 다음처럼 셀 크기를 조절해 정밀한 결과를 반환할 수 있다.

h3

h3는 uber에서 공간 데이터를 시각화해 배차 기능을 최적화하기 위해 만든 그리드 시스템이다. 지구를 정이십면체로 20개의 평면으로 구분하고 내부를 육각형으로 표현하게 된다. 왼쪽 도형은 정이십면체를 의미하고 오른쪽 도형은 지구로 표현했을 경우 그림이다.

그리드를 육각형으로 가져가는데 이웃 도형과의 중심 거리가 일정하다는 장점으로 인접 영역과의 거리 편차가 적다.

즉, 가장자리로 갈 수록 멀어지는 문제를 일부 해소할 수 있다.

중요한건 육각형으로 정이십면체를 표현이 불가능하고 일부 셀은 두 개 이상의 상위 셀에 포함되기도 한다. 그림을 살펴보면 내부 정육면체를 모두 포함할 수 없는 것을 확인할 수 있다.

h3는 압축해서 표현도 가능하므로 사실상 쿼드 트리도 제공하는 셈이다. 또한 압축 과정은 비트 연산으로 진행되기 때문에 효율적으로 분할하거나 압축도 가능하다.

w3w

지구를 3m x 3m 로 나눈 뒤 3 개의 단어를 이용해 고유 코드를 부여한 그리드 시스템이다. w3w 를 사용하면 3m x 3m 단위로 정확하게 전달이 가능하다. 주소가 없는 공간도 전달 가능하다는 장점도 있다.

단점은 높 낮이 구분이 되지 않는다는 점과 인접한 그리드와 연관성이 없다는 것이다. 위 사진에서 pile.knots.debit 과 fower.bigger.salon 사이 연관성을 이해할 수 있는가? 이해하면 이상한 사람이다. 연관성이 없기 때문이다.

정리

대표적으로 솔루션은 어떤 기술을 사용하고 있는지 살펴볼 수 있다.

3 단계 : 상세 설계

시스템의 형태를 파악했으니 상세한 설계를 고민해보자. 다음은 고민해 볼 포인트다.

• 데이터베이스 확장성
• 캐싱
• 지역 한정

데이터베이스 확장성

사업장 테이블은 어떤 방법을 사용해도 된다. 그러나 지리 정보가 포함된 정보는 관리하기 어렵다. 샤딩을 수행할 경우 애플리케이션 레이어에서 샤딩 로직을 구현해야 하는데 위에 이야기 나온 알고리즘을 샤딩된 데이터를 가져와 수용할 수 있어야 하는데 복잡해진다.

캐싱

면접관과 캐시 도입을 의논할 때는 벤치마킹과 비용 분석에 각별히 주의해야 한다. 캐시는 처리 부하가 읽기 중심이고 캐시 히트가 높을 수록 유용하다. 위 조건을 만족하지 못한다면 데이터베이스를 증설해서 읽기 대역폭을 늘리는 것도 방법이다.

캐싱을 수행한다면 그리드로 인덱싱된 데이터를 기준으로 어떤 사업장이 포함되는지 캐싱하게 된다.

지역 한정

사용자와 시스템 사이 물리적 거리를 최소화 해 휴율적으로 부하를 분산할 수 있다. 또한 지역을 한정하게 되면 지역마다 원하는 데이터가 캐싱될 것이고 더 빠르게 데이터를 받을 수 있게 된다. DNS 라우팅을 통해 해당 지역 내 서비스가 처리되도록 설정하자.

4 단계 : 마무리

근정성 서비스를 설계하면서 어떤 알고리즘을 사용하느냐에 따라 성능 차이가 발생하는 모습을 확인했다. 알고리즘마다 고려해야 하는 고민 포인트를 가지고 어떻게 확장성 있게 설계해야할지가 중요하다. 그 밖에 가용성을 높이기 위해 고민할 필요가 있다.

보면 재밌을 자료

• 주변 맛집을 찾으려면 어떻게 해야 검색이 빠를까? | blog
• 가게 배달지역 관리방식 개편 프로젝트 | 우아한형제들 기술블로그
• Hello, Geo-fence! | 우아한형제들 기술블로그
• h3 | uber
• What3words| wiki
• what3words 기능 카카오맵 반영 | 카카오맵APP