근접성 서비스

근접성 서비스(Proximity Service) 는 "내 주변에 뭐가 있어?"를 시스템으로 풀어내는 문제야. 구글 맵에서 "근처 식당"을 검색하거나, 배달 앱에서 가까운 가게를 보여주는 게 전부 이 설계의 변형이지. 위치 기반 서비스(LBS)의 가장 기본적인 형태라 시스템 설계 면접에서도 자주 나와.

면접관이 "근접성 서비스를 설계해 보세요"라고 하면, 먼저 범위를 좁혀야 해. 핵심 기능은 두 가지거든.

• 사용자의 위치(위도, 경도)와 검색 반경이 주어지면 주변 사업장 목록을 반환한다
• 사업장 주인이 사업장 정보를 추가, 수정, 삭제할 수 있다 (실시간 반영은 필요 없음)

비기능 요구사항도 중요해. 낮은 지연시간은 필수 — 사용자가 주변 식당 검색에 5초를 기다리진 않잖아. 높은 가용성과 확장성도 당연히 필요하고, 트래픽이 밀집 지역에 몰리는 특성도 고려해야 하지.

시스템은 크게 두 부분으로 나뉘어.

LBS(Location-Based Service) — 읽기 요청을 처리해. 사용자 위치 기반으로 근처 사업장을 찾아 반환하는 서비스지. 읽기 비중이 압도적으로 높고, QPS가 상당해. 무상태(stateless) 서비스라 수평 확장이 쉬워.

사업장 서비스(Business Service) — 사업장 정보의 CRUD를 처리해. 쓰기 요청의 QPS는 상대적으로 낮아. 사업장 정보가 변경되면 반영에 약간의 지연이 있어도 괜찮지.

핵심 질문은 이거야 — 2차원 공간에서 "가까운 것"을 어떻게 빠르게 찾을 것인가?

책에서 다루는 위치 검색 알고리즘들을 하나씩 보자.

1. 단순한 방법 — 2차원 범위 검색

위도와 경도 각각에 범위 조건을 걸어서 SQL로 검색하는 방식이야. WHERE latitude BETWEEN ? AND ? AND longitude BETWEEN ? AND ? 이런 식. 각각의 칼럼에 인덱스를 걸어도 두 차원의 교집합을 구해야 하니 효율이 떨어져. 데이터가 많아지면 느려지지.

2. 균등 격자(Evenly Divided Grid)

지구 표면을 균등한 격자로 나누고, 각 격자에 사업장을 할당해. 내가 속한 격자와 인접 격자만 검색하면 돼. 문제는 사업장 분포가 균등하지 않다는 거야. 서울 강남과 산골짜기의 사업장 밀도가 같을 리 없으니, 격자 크기 결정이 어렵지.

3. 지오해시(Geohash)

2차원 위치 정보를 1차원 문자열로 변환하는 기법이야. 지구를 반복적으로 반으로 쪼개면서 비트를 할당해. 경도는 좌/우, 위도는 상/하로 나누고, 이 비트들을 번갈아 조합한 뒤 Base32로 인코딩하면 9q8yyk 같은 문자열이 나오지.

지오해시의 핵심 성질은 접두사가 같으면 가까운 위치라는 거야. 9q8yyk와 9q8yym은 가까울 가능성이 높아. 이 성질 덕분에 DB에서 LIKE '9q8yy%' 같은 접두사 검색으로 근처 사업장을 찾을 수 있지.

하지만 함정이 있어. 접두사가 같다고 반드시 가까운 건 아니고, 가깝다고 접두사가 같은 것도 아니야. 경계선에 걸치는 케이스가 있거든. 바로 옆인데 지오해시 격자가 다른 경우가 생겨. 이 문제를 해결하려면 자신의 격자 + 인접 8개 격자를 함께 검색해야 해.

지오해시의 정밀도(문자열 길이)를 얼마로 할 것인지도 중요해. 길이 4면 약 39km x 19km, 길이 5면 약 4.9km x 4.9km, 길이 6이면 약 1.2km x 0.6km. 검색 반경에 맞게 적절한 정밀도를 선택해야 하지.

4. 쿼드트리(Quadtree)

메모리 내 자료구조로, 2차원 공간을 재귀적으로 4등분하는 트리야. 각 노드가 격자 하나를 나타내고, 그 안에 사업장이 일정 개수(예: 100개) 이상이면 다시 4등분해. 사업장이 밀집한 지역은 깊게 쪼개지고, 텅 빈 지역은 큰 격자 하나로 남지.

장점은 사업장 밀도에 따라 격자 크기가 자동 조절된다는 거야. 단점은 트리를 메모리에 올려야 하니 서버 시작 시 구축 시간이 필요하고, 업데이트가 좀 번거롭지.

5. 구글 S2

구면 기하학 기반 라이브러리로, 지구 표면을 힐베르트 곡선을 이용해 1차원으로 매핑해. 지오해시보다 경계 문제가 적고, 임의 형태의 영역을 셀로 표현할 수 있다는 장점이 있어.

책에서는 지오해시와 쿼드트리를 중점적으로 다뤄. 둘 다 면접에서 자주 등장하고, 실제 서비스에서도 많이 쓰이거든.

사업장 정보 테이블과 지오해시 인덱스 테이블이 필요해. 사업장 정보의 읽기 비중이 높으므로 **읽기 복제본(read replica)**을 두는 게 효과적이야. 사업장 정보 업데이트는 주(primary) DB에 쓰고, 복제본으로 전파하면 되지.

지오해시를 쓰는 경우, geohash와 business_id를 복합 키로 하는 테이블을 만들어. 같은 지오해시 접두사를 가진 사업장을 빠르게 찾을 수 있도록 인덱스를 걸지.

지오해시는 구현이 쉽고, DB 인덱스로 처리할 수 있어서 별도의 메모리 내 자료구조가 필요 없어. Redis에 지오해시를 키로 해서 사업장 목록을 캐싱하면 아주 빠르지.

쿼드트리는 밀도 적응형이라 사업장 분포가 극단적으로 불균일한 경우에 유리해. 하지만 전체 트리를 메모리에 올려야 하고, 서버 시작 시 구축 시간이 필요해. 멀티스레드 환경에서 업데이트 시 락(lock) 관리도 신경 써야 하지.

실무에서는 지오해시가 더 흔하게 사용돼. 구현 복잡도가 낮고, 기존 DB 인프라를 활용할 수 있으니까.

LBS는 무상태 서비스라 로드 밸런서 뒤에 서버를 쭉 늘리면 돼. 캐싱은 두 레이어로 구성하지.

• 지오해시 기반 캐시 — geohash: [사업장 ID 목록] 형태로 Redis에 저장. 같은 지역을 검색하는 요청이 반복되면 DB를 안 찍고 바로 반환.
• 사업장 정보 캐시 — 사업장 상세 정보를 business_id를 키로 캐싱.

사업장 정보가 업데이트되면, 먼저 DB를 갱신하고, 그다음 캐시를 무효화하는 방식으로 처리해.

최종 설계 흐름은 이래:

1. 사용자가 위도, 경도, 반경을 보낸다
2. LBS가 반경에 맞는 지오해시 정밀도를 계산한다
3. 해당 지오해시 + 인접 8개 지오해시를 구한다
4. 각 지오해시로 Redis 캐시 또는 DB에서 사업장 ID 목록을 가져온다
5. 사업장 ID로 상세 정보를 조회한다 (캐시 히트 시 바로 반환)
6. 실제 거리를 계산해서 반경 밖의 결과를 필터링하고 반환한다

근접성 서비스는 위치 기반 시스템의 기초 중의 기초야. 여기서 나온 지오해시와 쿼드트리 개념은 3장 구글 맵, 2장 주변 친구 등에서도 계속 재등장하지.

---

정리

1장 읽고 기억할 거 세 가지:

1. 2차원 공간 검색은 단순 SQL로 해결하기 어려워. 지오해시나 쿼드트리 같은 공간 인덱싱 기법이 필요하지.
2. 지오해시는 2차원 좌표를 1차원 문자열로 바꿔서 접두사 검색으로 근접 검색을 가능하게 해. 단, 경계 문제를 해결하려면 인접 격자도 함께 검색해야 하고.
3. 쿼드트리는 밀도 적응형이라 불균일한 분포에 강하지만, 메모리 기반이라 운영 복잡도가 올라가. 실무에서는 지오해시가 더 흔하게 쓰이지.