1. 근접서비스란?

- 사용자 위치 데이터를 기반으로 사용자 경험을 제공하고 운영을 더 효율적으로 만들어준다.

실제 사용사례들은 승차 공유 (우버, 리프트), 지역 검색 및 추천 서비스 (옐프, 포스퀘어), 소셜 네트워킹 및 데이팅 앱 (틴더, 범블), 음식 배달 서비스 (도어대시, 그럽허브), 네비게이션 및 지도 서비스 (구글 맵, 웨이즈), 피트니스 및 건강 추적 앱(스트라바, 핏비트) 등 많은 곳에서 쓰이고 있다. 우리나라도 관련 분야를 찾아보면 많은 서비스 들이 있을 듯하다.

2. 기능적 요구사항과 비기능적 요구사항

- 책에서는 내 주변 음식점 찾기와 주문하기라는 단순화된 서비스를 가정하고 요구사항을 정의한다.

기능적 요구사항은 아래와 같다.

- 사용자는 자신의 위치를 기반으로 음식점 검색이 가능.

- 음식을 선택하여 주문이 가능.

비기능적 요구사항은 아래와 같다.

가용성, 확장성(1억명 처리 가능), 지연시간(쓰기는 많지 않은나 읽기는 200ms 이내), 일관성(가끔 최종 일관성 허용), 신뢰성

3. api 설계해보기
(기능적 요구사항에 따라 api를 생각해봅시다. API 주소, API 응답 등...) 다른 블로그들에 API 쓴 분들도 있겠죠?

4. 요구사항을 충족하기 위한 계산 방법

서비스별 특징에 따라 계산 방법에 들어가는 요소들을 따로 추려야 한다. 9장 단축 url에서는 단축 url에 들어갈 수 있는 문자 개수와 사용자수를 비교했다면 근접서비스에서는 비기능적 요구사항의 읽기 속도도 충족해야하므로 트래픽과 검색 속도인 QPS와 DAU(하루 사용자수)등이 계산 요소로 들어간다.

예상 사용자수 - 약 1억명

DAU 예상 사용자수의 10% - 1000만명
DAU를 통해 초당 쿼리수 짐작(QPS) 짐작 - 대부분 점심 저녁 시간에 주문을 하므로 점심 3시간 저녁 3시간을 합해 1000만을 나눈다. 따라서 QPS = 10000000 / (6*60*60) .. 주문 QPS는 약 1200 QPS로 짐작 가능
아마 저자의 경험으로 본듯한데 트래픽 폭주시에 평소의 5배정도의 트래픽 폭주가 일어난다. 따라서 6000QPS

1명이 음식점 탐색이나 검색을 하는 횟수도 고려 = 1인당 5번정도 (너무 적은거 아닌가) .. 초당 6000QPS

앱에 등록된 음식점 수 : 전 세계 1000만개 중 100만개가 주문 가능.

5. 시스템 설계

주변 음식점 검색과 주문을 주로 하는 시스템은 쓰기보다는 읽기가 중요한 서비스이다.

그런데 주변 음식점을 모두 db에서 검색해서 처리하는 방식은 효율이 떨어질 것이다.

따라서 음식점들만 따로 검색할 수 있는 분산된 시스템을 하나 추가해서 효율을 늘린다.

책에서는 위치 기반 검색 서비스에 효율적으로 사용되고 있는 효율적인 방법론을 크게 두가지로 소개한다.(그냥 쿼리 검색은 제외)

바로 쿼드트리와 지오해싱이다.
나는 처음에 쿼드트리가 알고리즘적인 요소로 레디스처럼 db와 서비스 중간에 위치한 캐시 역할을 하는 것으로 봤는데 구글 검색을 해보고 책에 나온 시스템 설계도를 보고 나서 쿼드트리라는 저장소(?)를 하나 만드는걸 깨달았다. 쿼드트리는 실제로 자료 구조 중 하나이다(tree인데 자식 노드가 4개라서 쿼드 트리임)

쿼드트리의 작동 방식은 이렇다.
1. 처음에는 루트노드에서 탐색 시작
2. 현재 노드의 위도,경도의 최소/최대 범위 안에 사용자 위치가 포함되는지 확인
3. 포함되면 자식노드 네 개를 대상으로 DFS를 수행하며 1,2를 반복.
4. 리프 노드에 도달하면 해당 구역의 음식점 목록 가져옴, 사용자 위치에서 반경내 음식점 목록을 가져옴. 반환

만약 음식점 수가 충분하지 않으면 부모노드로 돌아가서 검색하여 추가.

나는 쿼드트리를 추가할때의 단점이 궁금했다. 그래서 우리의 친구 chatgpt에게 쿼드트리로 요구사항의 1000만개를 저장하는데 용량이 어느정도 들까를 검색해봤다.

짧은 답부터 말하면 👉 데이터 분포에 따라 극단적으로 달라지고,
그래도 대략 감 잡을 수 있는 범위는 있어요.

전제부터 깔고 갈게요

아래 가정으로 계산해볼게요.

2D 좌표 (x, y)
각 포인트는 단순 좌표만 저장 (속성 거의 없음)
쿼드트리 노드는 보통 이렇게 가짐:
- 경계 정보 (minX, minY, maxX, maxY) 또는 center + size
- 자식 포인터 4개
- 포인트 리스트 또는 포인트 1개 (leaf)
리프 노드에 최대 1개 또는 소수 포인트 저장하는 일반적인 쿼드트리

1️⃣ 포인트 데이터 자체 용량

좌표를 double로 저장한다고 하면:

x, y = 8바이트 × 2 = 16바이트
1000만 개 →
약 160MB

float(4바이트)면 80MB까지 줄어듦

2️⃣ 쿼드트리 노드 수 추정

이게 핵심인데, 분포에 따라 다름

✔ 이상적인 경우 (균등 분포)

리프 노드 ≈ 포인트 수
내부 노드는 리프보다 적음 (대략 리프의 1/3~1/2)

👉 전체 노드 수 ≈ 1.3 ~ 1.5 × 포인트 수

즉,

노드 ≈ 1300만 ~ 1500만 개

3️⃣ 노드 1개당 용량 (대략)

보수적으로 잡아볼게요.

구성크기

경계 정보 (double 4개)	32B
자식 포인터 4개 (64bit)	32B
기타 플래그 / padding	8~16B
합계	72~80B / node

4️⃣ 노드 용량 총합

1300만 노드 × 80B
👉 약 1.04GB
1500만 노드 × 80B
👉 약 1.2GB

5️⃣ 전체 합산

항목용량

포인트 데이터	~160MB
쿼드트리 노드	~1.0 ~ 1.2GB
총합	약 1.2 ~ 1.4GB

⚠️ 최악의 경우

한쪽으로 몰린 데이터
좌표가 거의 동일
depth 제한 없이 분할

👉 노드 수 폭발 → 수 GB 이상 가능

📌 현실적인 결론

메모리 쿼드트리로 1000만 포인트
👉 서버 메모리 16GB 이상 아니면 부담
디스크 기반 or 최적화 안 하면 실무에서 꽤 위험

🔥 줄이는 방법 (실무 팁)

float 사용
경계 정보 공유 (implicit boundary)
leaf에 여러 포인트 저장 (ex. 8~32개)
포인터 대신 index 사용 (int)
Quadtree → Loose Quadtree / R-tree 고려

원하면
👉 R-tree랑 용량 비교
👉 leaf capacity 바꿨을 때 시뮬레이션 계산
👉 DB(RDBMS/PostGIS) 기준 저장 용량

이 중에서 더 파볼까?

대충 요약하면 최소 16Gib 정도의 서버 메모리 이상이 필요하다고 한다.
rdbs에 저장하면 어느정도 용량이 필요할까? 기승전gpt(도망)

물음 :쿼드트리를 안쓰고 rdbs에 저장할떄 용량과 불러오는 속도 비교해줘

좋은 비교 포인트다 👍
이건 실무 기준으로 봐야 감이 딱 와서, 숫자랑 체감 같이 정리해줄게.

아래는 1000만 개 2D 포인트 (x, y) 기준이야.

1️⃣ 저장 용량 비교

✅ RDBMS (인덱스 없음)

예: MySQL / MariaDB / PostgreSQL

테이블 구조 예시

id BIGINT (8) x DOUBLE (8) y DOUBLE (8)

Row 크기

항목크기

id	8B
x, y	16B
Row header / alignment	~10~20B
합계	약 36~44B / row

👉 1000만 rows ≈ 360~440MB

✅ RDBMS + B-Tree 인덱스 (x, y)

INDEX idx_xy (x, y)

인덱스 비용

인덱스 엔트리 ≈ 24~32B
1000만 개 → 240~320MB

총합

👉 약 600~750MB

✅ Spatial Index (R-tree / GiST)

(PostgreSQL PostGIS / MySQL SPATIAL)

추가 비용

공간 인덱스 ≈ 테이블 크기의 30~60%
대략 150~300MB

총합

👉 약 550~700MB

📌 용량 요약

방식대략 용량

Quadtree (메모리)	1.2~1.4GB
RDBMS (No index)	~400MB
RDBMS + B-Tree	600~750MB
RDBMS + Spatial Index	550~700MB

➡️ 용량은 RDBMS가 압승

2️⃣ 조회 속도 비교 (핵심)

🎯 전제

조건:
WHERE x BETWEEN a AND b AND y BETWEEN c AND d
결과 수: 수십 ~ 수천 건

⚡ 쿼드트리 (메모리)

시간복잡도: O(log N + k)
디스크 I/O 없음
1~10ms 이하
초당 수만~수십만 쿼리 가능

👉 실시간 렌더링 / 게임 / 시각화 최강

🐢 RDBMS (B-Tree)

x 인덱스 타고 들어간 뒤 y 필터링
range query 성능 제한
디스크 I/O + 버퍼 히트 여부 영향

⏱️ 10~100ms

인덱스 잘 타면 10~30ms
캐시 안 타면 100ms+

🚀 RDBMS + Spatial Index (R-tree)

내부적으로 R-tree 탐색
디스크 기반이지만 locality 좋음

⏱️ 5~30ms

캐시 히트 시 5~10ms
SSD 환경에서 안정적

📊 속도 요약

방식조회 속도

Quadtree (RAM)	⭐⭐⭐⭐⭐ (1~10ms)
RDBMS + Spatial	⭐⭐⭐⭐ (5~30ms)
RDBMS + B-Tree	⭐⭐ (10~100ms)

3️⃣ 로딩 / 초기화 비용

쿼드트리

서버 시작 시:
- DB → 메모리 로딩 필요
- 1000만 건 로딩 = 수십 초 ~ 수 분
메모리 점유 고정

RDBMS

서버 시작 부담 없음
인덱스 유지 자동
장애/재시작 복구 쉬움

4️⃣ 실무 결론 (진짜 중요)

❌ 쿼드트리 단독이 좋은 경우

초당 수천~수만 공간 쿼리
실시간 줌/패닝
게임 서버, 지도 타일, 영상 분석
메모리 여유 충분

✅ RDBMS가 좋은 경우

데이터 영속성 중요
트랜잭션 / 백업 / 복구
쿼리 복잡함
운영 인력 적음

⭐ 베스트 프랙티스

DB = 정답 데이터
메모리 쿼드트리 = 캐시 / 가속기

DB: PostGIS + GiST
메모리: 요청 많은 영역만 쿼드트리

원하면 다음도 바로 이어서 설명해줄 수 있어 👇

🔍 1000만 건 실제 PostGIS 쿼리 예시 & 실행계획
⚙️ Redis + Geo / Elasticsearch 비교
🧠 왜 게임 서버는 DB 인덱스 안 믿는지

지피티의 말이 정말 사실인지는 모르겠다. 나중에 테스트를 한번 짜봐야겠다.
아무튼 용량을 빼고 속도만 봤을때 쿼드트리가 rdbs에 비해 몇배에서 몇십배 강점을 가진다.

쿼드트리는 해당 자료의 위치가 빈번히 변하지 않을 때 쓰면 좋다.(만약 이런 환경이면 수정이 번거롭고 비효율적이다)

두번째는 지오해시이다.

지오해시는 큰 구역의 정밀도는 낮게 세부적인 구역의 정밀도는 높게 만드는 방식이다. 예를들면 큰 구역은 01 작은 구역은 010101010101 이런식으로 정밀도가 높아진다. 지구상 위치를 코드화하여 표현하는 방식이라고 한다.

지오해시는 정밀도에 따라 고유한 해시값을 가지며 낮은 정밀도일때 값부터 높은 정밀도일때 값이 순차적으로 생성되기 때문에 어찌보면 쿼드트리와 비슷한 느낌도 든다.
w(낮은 정밀도)->f(그다음 낮은 정밀도)...->1(높은 정밀도) 이런식으로 비슷한 구역에 있는 음식점들의 해시가 생성된다.
따라서 쿼리로 검색이 쉬워진다.

select restaurant_ids where geohash like "wfa3sdfdf%";

이런식으로 말이다.

그럼 두가지 중 한가지만 선택한다고 했을 떄, 이 책에 있는 요구사항에 맞는 방법은 뭘까.. 두개의 장단점을 비교하면 쿼드트리가 더 맞다고 한다. 쿼드트리의 단점이 빈번한 정보 변경이 있을 때 수정이 번거롭다인데 음식점들이 빈번히 수정되는 일이 별로 없다. 반면에 지오해시는 음식점이 없는 공간 데이터도 생성되어 메모리 낭비가 발생할 수 있다고 한다.

책을 읽으면서 생각드는건 실무에서는 요구사항이 어떻느냐에 따라 시스템에 적용할 수 있는 여러 방법들을 찾아본 후 장단점을 비교하여 최선의 선택이나 차악을 고려해야한다. (구축시간이나 비용문제까지 여러 조건들이 경합한다..) 트레이드 오프라는 말은 항상 고려해야하는 것이다.

c_turtle이 만든다. 프로그램을

요즘 개발자를 위한 시스템 설계 수업 10장 - 근접 서비스