[대규모 시스템 설계 기초2] 1장 근접성 서비스(지오해시)

1일 = 24시간 * 60분 * 60초 = 86,400초 = 10^5초

QPS query per second 1초에 검색 수

위도: 0~+-90 경도: 0~+-180

위도는 적도를 기준으로 북이 + 경도는 본초자오선(그리니치 천문대) 동쪽이 + 

 

위도/경도/반경을 넘기면 주변 사업장을 알 수 있는 서비스

읽기 연산이 자주 수행되고 쓰기 연산 빈도는 낮음

읽기 연산이 압도적인 시스템에는 RDB가 유리

• 사업장 테이블은 사업자 아이디로 샤딩
• 지리 정보 테이블은(지오해시 기반) 지오해시 - 사업장 아이디로 n개 넣음(두 개를 모두 pk로 잡아서 락없이 추가 삭제 가능)
  • 지리 데이터는 총 1.7G 정도라 샤딩할 필욘 없고 읽기 연산을 위해 replica를 만든다.

 

주어진 반경 안의 사업장 검색?

위도와 경도에 인덱스를 둬도 인덱스는 오직 한 차원의 검색 속도만 개선하지 교집합을 구할 때는 효율적이지 않다.

지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만든다.

지오해시 geo hash 

지오해시는 위도(latitude)와 경도(longitude)를 이진수로 변환하고 이를 문자 코드(알파벳+숫자)로 압축하여 지리적 위치를 표현하는 기법

1. 경도(longitude)와 위도(latitude) 범위 설정

• 경도 범위: [-180°, 180°]
• 위도 범위: [-90°, 90°]

2. 이진 구간 분할

• 경도와 위도를 각각 이진 구간 분할(Binary Subdivision)
• 예시: 경도 [-180, 180]
  • 첫 비트가 1이면 오른쪽 절반 [0, 180],
  • 첫 비트가 0이면 왼쪽 절반 [-180, 0].
• 이 과정을 반복하여 점점 더 좁은 구간을 설정

3. 이진수 결합

• 경도와 위도의 이진수를 교차 결합(Interleaving)
  • 경 -> 위 -> 경 -> 위.. 순으로 나열 
  • 예: 경도 101, 위도 011이면 결합 결과는 100111.

4. 문자 변환(Base32 인코딩)

• 이진수를 Base32 문자(0~9, a~z 중 일부)를 사용해 문자열로 변환
• 예시: 이진수 11010 -> 문자 t
• 100111 -> 10011 + 1 0000 (5자리를 맞추기 위해 뒤에 0 4개로 패딩) -> 19 + 16 -> mh

지오해시 문자열 길이는 위치의 정밀도를 결정

• 1자리: 약 5,000km
• 2자리: 약 1,200km
• 3자리: 약 150km
• 6자리: 약 610m
• 9자리: 약 2m

지오해시 길이가 길어질수록 더 작은 영역을 나타냄

011011 -> eh

격자 가장자리 이슈

지오해시는 인접한 모든 격자가 공통 prefix를 갖도록 한다 다만 아래 케이스는 예외이다.

• 적도 가장자리 놓일 때
• 자오선상 반대쪽에 놓일 때 

1. 경계 값 문제 (Boundary Values):
   • 지오해시는 격자 기반의 위치 인코딩 시스템이므로, 각 격자의 경계에서 인코딩 된 값들이 인접한 다른 격자와 겹치는 경우가 발생할 수 있다. 예를 들어, 한 격자의 북쪽, 남쪽, 동쪽, 서쪽 끝에 위치한 좌표가 동일한 해시 값을 가지면, 그 점들이 실제로는 다른 격자에 속해 있어야 할 수도 있다.
2. 정확도 부족 (Precision):
   • 지오해시는 좌표를 고정된 비트 수로 인코딩하므로, 격자 크기가 정해져 있다. 이로 인해, 격자의 가장자리 근처에 위치한 좌표들이 부정확할 수 있다. 특히, 정밀도가 낮을수록 큰 격자에서 가장자리 문제를 겪기 쉽다.
3. 경계 면을 넘는 경우:
   • 위도와 경도가 극한값 (북극, 남극, 극한의 경도)에서 격자 경계를 넘는 좌표는 정상적으로 인코딩 되지 않거나 예상치 못한 해시 값으로 변환될 수 있다. 예를 들어, 위도 90도는 북극을 나타내는데, 이 주변의 지오해시 값은 정확하게 분리되지 않을 수 있다.
4. 지리적 불일치 (Geographic Mismatch):
   • 격자 경계가 곡선이 아닌 직선으로 표현되기 때문에, 실제 지리적 경계에서 작은 불일치가 발생할 수 있다. 예를 들어, 대륙 간 경계나 섬과 같은 지리적 특징이 정확하게 격자와 일치하지 않을 수 있다.

해결 방법:

1. 더 높은 정밀도 사용:
   • 가장자리 이슈를 줄이기 위해, 지오해시의 비트 수를 늘려 더 작은 격자를 사용하면 경계 인식이 더 정확해진다. 예를 들어, 5 비트의 해시값보다는 6 비트 이상의 값을 사용하여 정확도를 높일 수 있다.
2. 경계에 대한 예외 처리:
   • 격자의 경계에서 발생할 수 있는 예외를 처리하는 로직을 추가할 수 있다. 예를 들어, 특정 좌표가 경계를 넘어서는 경우, 이를 적절히 인식하고 인접 격자로 조정한다.
3. 경계 분할 알고리즘 개선:
   • 더 정밀한 경계 계산을 위해 알고리즘을 개선할 수 있다. 예를 들어, 격자의 경계에 인접한 다른 격자들을 미리 계산하고, 해당 격자에서 제외되는 좌표들이나 범위 값을 처리하는 방법을 도입할 수 있다.
4. 지오해시의 확장 사용:
   • 지오해시 외에도, 다른 격자 시스템을 함께 사용하거나, 지오해시를 보완할 수 있는 다른 데이터 포맷 (예: 하플릭스 공간 또는 비트맵)을 사용할 수도 있다

 

표시할 사업장이 충분치 않으면 검색 반경을 키운다. 지오해시 값의 마지막 비트를 삭제하여 얻은 새 지오해시 값을 사용해 주변 사업장을 검색한다.

 

쿼드트리(QuadTree)의 구조:

• 2차원 공간을 효율적으로 분할하고 관리하기 위해 사용되는 트리 자료 구조
• 쿼드트리는 각 노드가 4개의 자식 노드를 가질 수 있는 트리로 2차원 공간을 네 개의 사각형 영역으로 분할하여 데이터를 관리
• 일반적으로 한 노드는 특정 공간을 대표하고, 그 공간이 더 세분화될 필요가 있으면 4개의 자식 노드를 생성하여 해당 영역을 분할
• 트리구조를 메모리 안에 만드는 것. 이 자료구조는 각각 LBS 서버에 존재해야 하며 서버가 시작될 때 구축된다.

1. 분할:
   • 공간을 네 개의 사각형(혹은 직사각형) 영역으로 분할. 이때, 각 자식 노드는 상위 노드의 공간을 4등분하여 맡게 되며 분할된 각 자식 노드는 해당 영역 내의 데이터를 관리
   • 어떤 노드의 사업장도 100개를 넘기지 않도록 재귀적으로 분할
2. 리프 노드와 내부 노드:
   • 리프 노드: 더 이상 분할할 필요가 없는 공간으로 데이터를 저장하는 노드
   • 내부 노드: 해당 공간을 더 세분화할 필요가 있을 때 자식 노드를 가진 노드
3. 데이터 저장:
   • 데이터는 리프 노드에 저장. 각 노드는 공간 내에서 특정 데이터를 가지고 있으며, 해당 데이터를 저장할 위치를 찾기 위해 트리를 탐색
4. 공간의 분할 방식:
   • 사각형 또는 직사각형 공간을 네 개의 자식 노드로 분할. 분할된 각 자식 노드는 부모 노드의 영역을 차지
   • 공간의 크기가 충분히 작을 때까지 분할하며, 공간에 저장될 수 있는 데이터가 많은 경우 리프 노드로 저장

쿼드트리 전부를 저장하는데 드는 메모리 약 1.7GB. 서버 한 대에 충분히 올릴 수 있다.

다만 읽기 연산 양이 많아지면 여러 쿼드 트리로 분산시켜야 할 것..

고려사항

• 서버를 시작하는 순간에 쿼드트리를 구축하면 서버 시작 시작이 길어진다. downtime 고려
• 한 번에 모든 서버가 동시 시작하면 많은 양의 데이터를 디비에서 읽게 되므로 부하가 발생한다.
• 따라서 순차적으로 갱신하도록 해야 한다.
• 사업장이 추가/삭제될 경우 트리를 갱신해야 하는데 루트노드부터 말단노드까지 트리를 순회해야 한다. O(logN)
• 밤 사이 캐시를 일괄 갱신(수많은 키가 한 번에 무효되면 캐시 서버에 막대한 부하가 생긴다)
• 쿼드 트리를 실시간 갱신하려면 동시 접근하지 않도록 락을 걸어야 한다(멀티 스레드에서도).
• 말단 노드에 새로운 사업장을 추가할 수 없다면 rebalancing이 필요한데 이는 복잡하다.
• 검색반경에 상관없이 가장 가까운 k개 검색 시 적합
• 인구 밀도에 따라 격자 크기를 동적으로 저장 가능

 

구글 S2 라이브러리의 주요 개념:

S2는 2D 공간을 효율적으로 처리하고, 특히 구체적이고 세밀한 공간 분할을 가능하게 하는 기하학적 알고리즘을 제공. 주로 구면 좌표계에서의 계산을 다루며, Google 지도에서의 공간 계산에 많이 사용

1. 구면 좌표계와 다각형 처리:
   • S2는 구면 좌표계(Spherical Geometry)를 기준으로 공간을 다루며, 구면 위의 점들을 다루는 방식으로, 지구와 같은 구형 물체에서의 좌표 계산에 유리
2. 공간 분할 (S2 Cell):
   • S2는 공간을 셀(Cell)이라는 단위로 나누어 데이터를 처리. 각 셀은 구면을 사각형 모양의 격자 형태로 나눈 것으로 이 셀들은 더 작은 하위 셀로 계속 분할될 수 있음
   • S2의 셀은 기하학적 정확성을 유지하면서도, 작은 셀을 통해 정확한 공간 계산을 가능
3. S2 Cell ID:
   • S2는 셀을 고유하게 식별할 수 있는 S2 Cell ID를 부여하여 셀을 식별. 이 ID는 공간에 따라 다른 값으로 매핑되며, 이를 이용해 빠르게 공간을 검색하고 위치 기반 쿼리를 수행할 수 있다.
4. 계층적 공간 분할:
   • S2는 계층적으로 공간을 분할한다. 상위 셀은 더 큰 지역을 나타내며, 하위 셀은 더 작은 지역을 나타낸다. 이렇게 계층적으로 분할된 셀들을 사용하여, 특정 지역을 검색할 때 효율성을 높일 수 있다.
5. 효율적인 범위 쿼리:
   • S2는 범위 쿼리를 매우 효율적으로 처리할 수 있다. 예를 들어, 특정 반경 내의 점들을 찾거나, 주어진 다각형 내의 점들을 찾는 데 매우 효율적이다.
6. 고정밀 좌표 계산:
   • S2는 구면에 대한 고정밀 계산을 수행하므로, 위도/경도 등의 지리적 데이터를 매우 정밀하게 처리할 수 있다. 이를 통해 대규모 지리 데이터셋을 정확하게 분석할 수 있다.

 

캐시

• 서버 하나에 다 올라가는(상대적으로 양이 적은) 데이터는 메모리에서 처리하는 것과 비슷하여 굳이 캐시를?
• 상대적으로 덜 바뀌는 지오해시-사업장 아이디는 캐시해도 좋다.
• 캐시에서 조회하고 없으면 디비에서 조회한 후 캐싱
• 사업장 정보를 추가/편집/삭제 시에는 디비를 갱신하고 캐시를 invalidate 해야 한다. 이 연산의 빈도는 상대적으로 낮아서 락을 사용할 필요 없다.
• 필요한 레디스 용량은 약 5G 정도라 한대로도 충분하지만 HA를 보장하고 지역별 traffic latency를 위해 클러스터를 전 세계/지역별로 두고 동일 데이터를 각 지역에 중복하여 저장해야 한다. 
• 사업자 아이디에 따른 각 상세 정보도 캐시 해둔다.

추가 필터링이 필요하다면 작은 격자 안의 모든 사업장 아이디를 확보 -> 상세정보를 가져와서 필터링

 

1. 위도, 경도, 검색반경을 LB로 보낸다

2. LB는 LBS로 요청을 보낸다

3. LBS는 검색 요건을 만족하는 지오해시 길이를 계산한다. (반경 500미터의 경우 6)

4. LBS는 인접한 지오해시를 계산하여 목록에 추가한다

리스트 = [현재 지오해시, 인접한 8개 지오해시]

5. 리스트에 있는 지오해시 각각에 대해 레디스 서버를 호출하여 해당 지오해시에 대응하는 모든 사업장 ID를 추출한다. 이때 지오해시별로 병렬처리한다.

6.  반환된 사업장 아이디들과 사업장 정보 레디스를 조회하여 상세 정보를 취득한다. 레디스에 없다면 디비를 조회한다. 상세 정보에 의거하여 사업장과 사용자 간 거리를 확실하게 계산하고 우선순위를 매긴 다음 클라이언트에 반환한다.

7. 추가/삭제/갱신되는 사업장 정보는 우선 디비에 저장하고 배치로 레디스에 올려 캐싱한다.