근접성 서비스 설계: 지오해시와 쿼드트리

새롭게 시작한 SM 업무에서 지루함을 느끼고 스터디 그룹에 합류해 이 시리즈를 작성하게 되었습니다.
2027년은 자격증 공부를 주로 할 계획이기 때문에 올해 마지막으로 읽는 기술 서적일 것 같습니다.

『가상 면접 사례로 배우는 대규모 시스템 설계 기초 2』를 읽으며 정리하는 시리즈의 첫 글입니다.
1장은 근접성 서비스(Proximity Service), 즉 내 주변의 식당이나 주유소 같은 시설을 찾아 주는 서비스를 설계합니다.

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

면접에서 던지는 질문

• 사용자가 검색 반경(radius)을 지정할 수 있는가?
• 반경은 최대 어느 정도인가? (예: 2km)
• UI에서 검색 반경을 조절할 수 있는가?
• 사업장 소유주가 사업장 정보를 추가·수정·삭제할 수 있는가? 그 변경은 실시간으로 반영되어야 하는가?
• 사용자가 이동하면 검색 결과도 그 위치를 기준으로 갱신해야 하는가?

기능 요구사항

• 사용자 위치(위도·경도)와 검색 반경을 받아, 그 안에 있는 사업장 목록을 돌려준다.
• 사업장 소유주는 사업장 정보를 추가·수정·삭제할 수 있다.
  단, 실시간으로 반영될 필요는 없다 (다음 날 반영되어도 된다).
• 고객은 사업장의 상세 정보를 볼 수 있다.

비기능 요구사항

• 낮은 응답 지연(latency): 주변 사업장을 빠르게 보여 줘야 한다.
• 데이터 보호(data privacy): 위치 기반 서비스(Location-Based Service, LBS)는 사용자 위치를 다루므로 개인 정보 보호가 중요하다.
• 고가용성(high availability)과 확장성(scalability): 특정 지역·시간대에 몰리는 트래픽을 감당해야 한다.

개략적 규모 추정

면접 질문으로 범위를 좁히고, 거기서 기능·비기능 요구사항을 끌어내는 과정이 처음부터 끝까지 논리적으로 이어집니다.
내가 요구사항을 정리하던 방식과 많이 달라서 흥미롭게 시작할 수 있었습니다.

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

API 설계

주변 검색 API가 받는 값은 다음과 같습니다.

검색 결과에는 사업장 목록만 담고, 상세 정보는 사용자가 사업장을 눌렀을 때 /v1/businesses/:id로 따로 가져옵니다.
결과가 많을 수 있으므로 실제로는 페이지 나누기도 필요합니다.

데이터 모델

두 기능의 읽기·쓰기 비율(read/write ratio)을 따져 봅니다.

• 주변 사업장 검색: 읽기
• 사업장 상세 정보 보기: 읽기
• 사업장 추가·수정·삭제: 쓰기 (자주 일어나지 않음)

읽기가 압도적으로 많은 시스템입니다.
이런 시스템은 MySQL 같은 관계형 DB로 충분하고, 읽기 부하는 사본(replica) DB를 늘려서 나눠 받습니다.

전체 구조

flowchart TB
  U[사용자] --> LB[로드밸런서]
  LB -- "/v1/search/nearby" --> LBS["위치 기반 서비스 (LBS)"]
  LB -- "/v1/businesses" --> BS[사업장 서비스]

  subgraph DB[DB 클러스터]
    P[(주 DB)]
    R1[(사본 1)]
    R2[(사본 2)]
    R3[(사본 3)]
    P -. 복제 .-> R1
    P -. 복제 .-> R2
    P -. 복제 .-> R3
  end

  BS -- 쓰기 --> P
  BS -- 상세 조회 --> R1
  LBS -- 검색 --> R2
  LBS -- 검색 --> R3

로드밸런서

로드밸런서는 들어오는 트래픽을 하나의 DNS 진입점으로 받아서, 어느 서비스로 보낼지 정합니다.

위치 기반 서비스 (LBS)

• 주변 사업장을 찾는 핵심 서비스로, 쓰기 요청 없이 읽기 요청만 받는다.
• 인구가 밀집한 지역은 특정 시간대에 QPS가 높아진다.
• 무상태(stateless) 서비스라서 수평 확장이 쉽다.

사업장 서비스

• 사업장 추가·수정·삭제(쓰기)는 QPS가 낮다.
• 고객이 사업장 상세 정보를 보는 읽기는 특정 시간대에 QPS가 높아진다.

DB 클러스터

• 주(primary) DB: 쓰기 요청을 처리한다.
• 사본(replica) DB: 읽기 요청을 처리한다.

주 DB에서 사본으로 복제될 때 지연(replication delay)이 생기지만, 사업장 정보는 실시간으로 반영될 필요가 없으므로 문제가 되지 않습니다.

서비스 확장

LBS와 사업장 서비스는 둘 다 무상태 서비스이므로, 트래픽이 몰리면 서버를 추가하고 한가한 시간대에는 서버를 줄이도록 구성할 수 있습니다.
시스템을 클라우드에 둔다면 여러 지역(region)과 여러 가용 영역(availability zone)에 서버를 나눠 두어 가용성을 높입니다.

주변 사업장 검색 알고리즘

실무에서는 보통 이미 있는 도구를 씁니다.

• Redis의 지오해시 (GEOADD, GEOSEARCH)
• PostgreSQL의 PostGIS 확장 (이번 스터디를 통해서 처음 접함)

하지만 면접에서는 이 이름만 대고 끝내기보다, 지리 정보 색인(geospatial index)이 어떻게 동작하는지 설명할 수 있어야 합니다.

방안 1: 2차원 검색

원을 그리고 그 안의 사업장을 찾는 가장 직관적인 방법입니다.

SELECT business_id, latitude, longitude
  FROM business
 WHERE (latitude  BETWEEN :my_lat  - :radius AND :my_lat  + :radius)
   AND (longitude BETWEEN :my_long - :radius AND :my_long + :radius)

색인이 없으면 테이블 전체를 읽어야 하므로 효율적이지 않습니다.
위도와 경도에 각각 색인을 두어도, 위도 조건에 맞는 집합과 경도 조건에 맞는 집합을 따로 구한 뒤 교집합을 구해야 합니다.
각 집합은 지구를 가로·세로로 길게 자른 띠라서 데이터가 매우 많고, 교집합 연산이 비쌉니다.

flowchart LR
  A["위도 조건 → 가로 띠 전체<br/>(수천만 건)"] --> C{교집합}
  B["경도 조건 → 세로 띠 전체<br/>(수천만 건)"] --> C
  C --> D["실제로 필요한 건<br/>가운데 작은 사각형"]

그래서 2차원 데이터를 1차원에 대응시키는 방법이 필요합니다.

다른 방안들

구현 방법은 서로 다르지만 목적은 같습니다.
지도를 작은 영역으로 나누고, 빠르게 찾을 수 있는 색인을 만드는 것입니다.

방안 2: 균등 격자

지도를 같은 크기의 격자로 나누는 단순한 방법입니다.
하지만 사업장 분포는 균등하지 않습니다.
바다나 사막에는 사업장이 없고, 도심에는 몰려 있습니다.
어떤 격자는 텅 비고 어떤 격자는 꽉 찹니다.

방안 3: 지오해시

2차원의 위도·경도를 1차원 문자열로 바꾸는 방법입니다.
비트를 하나씩 늘려 가며 격자를 재귀적으로 둘로 나눕니다.

1. 경도를 반으로 나눠 왼쪽이면 0, 오른쪽이면 1
2. 위도를 반으로 나눠 아래면 0, 위면 1
3. 고른 칸을 다시 1~2처럼 나눈다.
   경도 비트와 위도 비트가 번갈아 붙는다.
4. 비트 5개씩 묶어 base32 문자 하나로 바꾼다. (예: 9q8zn)

첫 두 비트로 세계를 나누면 이렇게 됩니다.

각 칸을 다시 같은 방식으로 넷으로 나누면 0100, 0101 …처럼 비트가 길어집니다.
이 칸들을 비트 순서대로 이으면 Z자를 그리며 지도를 훑습니다(Z-order curve).

문자열 길이(정밀도)가 곧 격자 크기입니다.

검색 반경마다 쓸 길이를 위 표처럼 미리 정해 두고, 요청이 오면 반경에 맞는 길이로 지오해시를 계산합니다.

⚠️ 격자 가장자리 문제

지오해시는 공통 접두어가 길수록 두 위치가 가깝다는 것을 보장합니다.
하지만 그 역은 참이 아닙니다.

문제 1. 아주 가까운데 공통 접두어가 하나도 없을 수 있다. 적도나 본초 자오선처럼 첫 번째 분할선 양쪽에 있는 두 지점은 몇 미터 떨어져 있어도 첫 비트부터 다릅니다.
그래서 접두어로만 검색하면 바로 옆 사업장을 놓칩니다.

SELECT *
  FROM geohash_index
 WHERE geohash LIKE '9q8zn%'

문제 2. 공통 접두어가 길어도 서로 다른 격자에 있을 수 있다.
두 지점의 지오해시가 9q8zn까지 같고 마지막 한 글자만 달라도(9q8znf, 9q8znc), 길이 6으로 검색하면 둘은 다른 격자입니다.
내가 격자 가장자리에 서 있으면, 바로 옆 격자의 가까운 사업장이 내 격자 검색에서는 빠집니다.

👉 해결책: 내 격자와 인접한 8개 격자를 함께 조회합니다.
인접 격자의 지오해시는 계산으로 바로 구할 수 있습니다.

찾은 사업장이 너무 적다면?
지오해시 끝 글자를 하나씩 떼어 격자를 넓혀 가며 다시 검색합니다. (9q8znf → 9q8zn → 9q8z)

방안 4: 쿼드트리

격자 안의 사업장 수가 기준(예: 100개) 이하가 될 때까지, 2차원 공간을 재귀적으로 사분면(4개)으로 나누는 방법입니다.
사업장이 많은 도심은 잘게, 적은 곳은 크게 나뉘므로 균등 격자의 문제를 해결합니다.

flowchart TB
  root["세계 전체<br/>2억 개"] --> nw["북서<br/>4천만"]
  root --> ne["북동<br/>3천만"]
  root --> sw["남서<br/>7천만"]
  root --> se["남동<br/>6천만"]
  sw --> a["…"]
  sw --> b["…"]
  sw --> c["…"]
  sw --> d["…"]
  c --> leaf1["말단 노드<br/>100개 이하"]
  c --> leaf2["말단 노드<br/>100개 이하"]
  c --> leaf3["말단 노드<br/>100개 이하"]
  c --> leaf4["말단 노드<br/>100개 이하"]

쿼드트리는 DB가 아니라 메모리에 올리는 자료구조입니다.
LBS 서버가 시작될 때 각 서버가 직접 만듭니다.

📌 메모리는 얼마나 필요할까

사업장 2억 개를 다 담아도 2GB가 안 되므로 서버 한 대 메모리에 충분히 들어갑니다.

📌 검색

1. 루트에서 시작해, 검색 위치가 들어 있는 말단 노드까지 내려간다.
2. 그 노드에 사업장이 충분히(예: 100개) 있으면 돌려준다.
3. 부족하면 인접 노드의 사업장을 더해 가며 개수를 채운다.

📌 운영할 때 생각할 점

• 서버 시작이 느리다.
  2억 개로 트리를 만드는 데 몇 분이 걸린다.
  그동안 그 서버는 요청을 받을 수 없다.
• 배포는 조금씩 나눠서 한다.
  모든 서버를 한꺼번에 새로 띄우면 서비스 용량이 크게 줄고, 서버들이 동시에 DB에서 2억 건을 읽어 DB에 부담을 준다.
  청/녹 배포(blue/green deployment)도 쓸 수 있지만, 새 클러스터 전체가 동시에 DB를 읽는 부담은 마찬가지다.
• 사업장이 추가·삭제되면 트리를 바로 고치지 않고 점진적으로 갱신한다.
  실시간으로 고치려면 여러 스레드가 트리를 동시에 읽고 쓰므로 락(lock)이 필요해 복잡해진다.
  다행히 요구사항이 "다음 날 반영"이므로 밤에 일괄로 다시 만들어도 된다.

방안 5: 구글 S2

구의 표면을 힐베르트 곡선(Hilbert curve) 으로 1차원에 대응시키는 라이브러리입니다.
힐베르트 곡선은 2차원에서 가까운 두 점이 1차원에서도 가깝게 놓이도록 공간을 훑기 때문에, 지오해시의 Z자 곡선보다 "가까운데 멀리 떨어진 값"이 덜 생깁니다.
구글 지도, 틴더 같은 서비스에서 쓰며, 지오펜스(geofence)를 다루기 좋고 영역 덮기(region cover) 알고리즘으로 격자 크기를 유연하게 고를 수 있습니다.
다만 면접에서 설명하기 어렵기 때문에 보통은 지오해시나 쿼드트리를 고릅니다.

지오해시 vs 쿼드트리

쿼드트리를 갱신하다 노드를 다시 나눠야 하는 리밸런싱(rebalancing)은 구현이 어렵습니다.
말단 노드가 담당하는 범위를 처음부터 넉넉하게 잡아 두면 어느 정도 피할 수 있습니다.

3단계: 상세 설계

2단계에서 그린 개략적 설계를 바탕으로, 다음 주제를 더 깊이 살펴봅니다.

• DB 규모 확장
• 캐시(cache)
• 지역(region)과 가용 영역(availability zone)
• 최종 아키텍처 다이어그램

DB 규모 확장

📌 사업장 테이블

사업장 데이터는 한 서버에 담기 부담스러울 만큼 많기 때문에 샤딩(sharding)하기 좋은 후보입니다.
사업장 ID를 기준으로 나누면 데이터가 모든 샤드에 고르게 퍼지고, 유지보수하기도 쉽습니다.

📌 지리 정보 색인 테이블

지오해시 색인을 테이블에 저장하는 방법은 두 가지입니다.

방안 1. 지오해시마다 사업장 ID 목록을 한 행에 담는다

방안 2. 지오해시와 사업장 ID를 한 행씩 담는다

방안 1을 쓰면 사업장을 등록하거나 고칠 때마다 배열 전체를 살펴봐야 하고, 동시에 고치는 경우를 막으려고 락까지 걸어야 해서 다루기 까다롭습니다.
방안 2는 (geohash, business_id)를 복합 키(compound key)로 쓰면 추가·삭제가 행 하나를 넣고 빼는 일이 되어 위 문제가 쉽게 해결됩니다.
복합 키의 앞 열이 geohash이므로, 앞에서 본 WHERE geohash LIKE '9q8zn%' 같은 접두어 검색도 이 키의 색인을 그대로 탑니다.
그래서 방안 2를 고릅니다.

색인 규모 확장

성급하게 샤딩을 결정하기보다는, 색인 테이블을 만드는 데 필요한 전체 데이터 양부터 살펴봅니다.
지리 정보 색인은 지오해시와 사업장 ID 정도만 담으므로 생각보다 크지 않습니다.
메모리에 통째로 올리는 쿼드트리조차 약 1.71GB였듯이, 색인 데이터는 서버 한 대에 충분히 들어갑니다.

그런데도 샤딩 얘기가 나오는 이유는 읽기 부하입니다.
읽기 요청이 많아지면 서버 한 대의 CPU와 네트워크 대역폭으로는 감당하기 어려울 수 있어서, 부하를 나눌 방법이 필요합니다.

하지만 샤딩은 DB가 알아서 해 주는 게 아니라 어느 샤드로 보낼지 애플리케이션 계층에서 직접 구현해야 하고, 한 번 나눈 뒤에는 줄이기도 까다롭습니다.
그래서 기술적으로 꼭 필요한 이유가 없다면, 이 책은 사본(replica) DB를 늘려 읽기 부하를 나누는 방법을 권합니다.

캐시

캐시를 무작정 넣기 전에, 정말 필요한지부터 따져 봐야 합니다.

• 읽기 중심의 부하인가?
• 디스크 I/O 병목 때문에 성능이 떨어지고 있는가?
• 메모리 캐시를 쓰면 DB보다 성능이 눈에 띄게 좋아지는가?
• 사본 DB를 늘려 읽기 대역을 넓히는 것만으로는 해결되지 않는가?

이 시스템은 읽기가 압도적으로 많지만, 앞에서 본 것처럼 지리 정보 색인 데이터는 DB 서버 한 대의 메모리에 다 들어갈 만큼 작습니다.
데이터가 메모리에 올라가 있으면 디스크 I/O 병목이 크지 않으므로, 사본 DB만으로도 충분할 수 있습니다.
캐시는 이런 논의를 거친 뒤에 도입을 결정하고, 그래도 둔다면 아래 내용을 정해야 합니다.

📌 캐시 키

가장 먼저 떠오르는 키는 사용자의 위도·경도입니다.
하지만 위도·경도는 캐시 키로 적절하지 않습니다.

• 사용자는 움직이기 때문에 위도·경도가 계속 조금씩 바뀝니다.
  조금 움직여도 검색 결과는 거의 같은데 좌표는 달라지므로, 좌표를 키로 쓰면 캐시가 거의 적중하지 않습니다.
• 사용자가 움직이지 않아도, 위도·경도는 측정할 때마다 조금씩 다르게 나올 수 있습니다.

그래서 좌표 대신 지오해시를 키로 씁니다.
같은 격자 안에 있는 사용자는 좌표가 조금씩 달라도 지오해시가 같으므로, 같은 캐시를 함께 씁니다.

📌 캐시 데이터 유형

두 데이터 모두 자주 바뀌지 않기 때문에 키-값 캐시에 담기 좋습니다.
지오해시로 사업장 ID 목록을 가져오는 과정은 다음과 같습니다.

1. DB에서는 지오해시 접두어로 사업장 ID를 찾습니다.

SELECT business_id
  FROM geohash_index
 WHERE geohash LIKE CONCAT(:geohash, '%')

2. 먼저 캐시를 보고, 없을 때만 위 SQL로 DB에서 읽어 캐시에 채웁니다.

public List<String> getNearbyBusinessIds(String geohash) {
    String cacheKey = hash(geohash);
    List<String> listOfBusinessIds = redis.get(cacheKey);

    if (listOfBusinessIds == null) {
        listOfBusinessIds = findBusinessIdsByGeohash(geohash); // 위 SQL 질의
        redis.set(cacheKey, listOfBusinessIds, "1d");
    }

    return listOfBusinessIds;
}

flowchart TB
  start["LBS: 지오해시로 캐시 조회"] --> hit{"캐시에 있나?"}
  hit -->|있음| ret["사업장 ID 목록 반환"]
  hit -->|없음| db["사본 DB에서 SQL 질의"]
  db --> set["캐시에 저장 (TTL 1일)"]
  set --> ret

사업장 정보가 추가·수정·삭제되면 해당 캐시 항목을 무효화(invalidate)하면 됩니다.
또 TTL을 1일로 두었기 때문에, 무효화를 놓치더라도 늦어도 다음 날에는 새 데이터로 바뀝니다.
요구사항이 "다음 날 반영되어도 된다"였으므로 이 정도면 충분합니다.

📌 정밀도별 캐시와 지역별 Redis

2단계의 정밀도 표에서 봤듯이, 검색 반경마다 쓰는 지오해시 길이가 다릅니다.
그래서 길이 4, 5, 6 각각에 대해 "지오해시 → 사업장 ID 목록" 캐시를 만들어 둡니다.

사업장 하나는 정밀도마다 격자 하나에만 속하므로, 사업장 ID는 정밀도별로 한 번씩 저장됩니다.
사업장 ID 하나를 8바이트로 잡으면 필요한 메모리는 다음과 같습니다.

8바이트 × 2억 개 × 정밀도 3가지 ≈ 약 5GB

5GB 정도면 Redis 서버 한 대에도 들어갑니다.
하지만 고가용성을 보장하고 트래픽 전송 지연을 막기 위해, Redis 클러스터를 전 세계 지역마다 두고 같은 데이터를 각 지역에 중복해서 저장합니다.

지역 및 가용 영역

LBS는 한 곳에만 두지 않고 여러 지역(region)과 가용 영역(availability zone)에 나눠 배치합니다.
이렇게 하면 다음과 같은 이점이 있습니다.

1. 사용자와 시스템 사이의 물리적 거리를 줄인다.
   미국 사용자는 미국 지역에, 아시아 사용자는 아시아 지역에 연결되므로 응답이 빨라집니다.
2. 트래픽을 인구에 따라 고르게 분산할 수 있다.
   일본이나 한국처럼 인구가 몰린 곳은 별도 지역을 두거나 가용 영역을 더 둬서 부하를 나눕니다.
3. 나라마다 다른 데이터 사생활 보호법을 지킬 수 있다.
   어떤 나라는 사용자 데이터를 나라 밖으로 내보내지 못하게 합니다.
   그래서 DNS 라우팅으로 그 지역에서 생긴 모든 요청을 그 지역 안의 서비스가 처리하게 하고, 데이터를 다른 지역으로 내보내지 않습니다.

지역 안에서도 가용 영역을 여러 개 두면, 한 영역에 장애가 나도 다른 영역이 요청을 받아 서비스가 계속됩니다.
지역은 사용자와의 거리와 법을, 가용 영역은 장애 대비를 맡는다고 보면 됩니다.

flowchart TB
  user["사용자"] --> dns["DNS<br/>(사용자 위치에 따라 라우팅)"]
  dns -->|미국 사용자| us
  dns -->|아시아 사용자| asia

  subgraph us["미국 서부 지역"]
    usa["가용 영역 A<br/>LBS · Redis · DB"]
    usb["가용 영역 B<br/>LBS · Redis · DB"]
  end

  subgraph asia["아시아 지역"]
    asa["가용 영역 A<br/>LBS · Redis · DB"]
    asb["가용 영역 B<br/>LBS · Redis · DB"]
  end

최종 아키텍처

2단계 그림에 Redis 클러스터와 DB 클러스터를 더하고, 요청 API에 따라 LBS와 사업장 서비스가 읽기·쓰기·동기화를 어떻게 처리하는지 그렸습니다.
실선은 읽기·쓰기 요청이고, 점선은 복제와 동기화입니다.

flowchart TB
  user["사용자"] --> lb["로드밸런서"]
  lb -- "/v1/search/nearby" --> lbs["위치 기반 서비스 (LBS)"]
  lb -- "/v1/businesses" --> biz["사업장 서비스"]

  subgraph redis["Redis 클러스터"]
    geo["지오해시 캐시<br/>지오해시 → 사업장 ID 목록"]
    info["사업장 정보 캐시<br/>사업장 ID → 사업장 정보"]
  end

  subgraph db["DB 클러스터"]
    primary[("주 DB")]
    replica[("사본 DB")]
  end

  lbs -- "1. 주변 사업장 ID 조회" --> geo
  lbs -- "2. 사업장 정보 조회" --> info
  lbs -- "캐시 미스" --> replica
  biz -- "상세 조회" --> info
  biz -- "캐시 미스" --> replica
  biz -- "추가·수정·삭제" --> primary
  primary -. "복제" .-> replica
  replica -. "밤마다 일괄 동기화" .-> sync["캐시 동기화 작업"]
  sync -. "캐시 갱신" .-> redis

여러 지역에 나눠 두는 구성은 앞의 지역 및 가용 영역 그림과 같으므로, 이 도면은 지역 하나만 그렸습니다.

마치며

그동안은 대규모 트래픽을 다룬다는 채용 공고에 맞춰 공부해 왔는데, 이번 스터디는 실제 면접이었다면 어떻게 대답하는 게 좋을지 생각해 보는 계기가 되었습니다.
물론 글로 보면 쉽게만 느껴지고, 실무에서는 훨씬 많은 제약이 있을 거라고 생각합니다.
그래도 이 스터디를 시작한 것은 잘한 일이라고 생각합니다.
지금까지의 행보만 보면 나중에 실무에서 이런 비슷한 고민이라도 하게 될지 의구심이 들지만, 지금은 공부 자체가 목적이라고 생각하고 하는 게 맞는 것 같습니다.

참고

• 알렉스 쉬, 산 란, 『가상 면접 사례로 배우는 대규모 시스템 설계 기초 2』, 인사이트 — 1장 근접성 서비스