Redis Geospatial 자료구조 동작원리

결론

• Redis Geospatial은 내부적으로 Sorted Set (ZSET) 자료구조를 사용합니다 Redis 공식 문서 (opens in a new tab)

Redis 공식 문서에서 "These commands actually piggy back on the sorted set datatype. This is achieved by encoding the latitude and longitude into the score of the sorted set using the geohash algorithm" 라고 명시되어 있습니다.

• 위도/경도 좌표는 Geohash 알고리즘을 통해 52-bit 정수로 인코딩되어 Sorted Set의 score에 저장됩니다 DEV Community (opens in a new tab)

DEV Community 글에서 "Redis represents positions of elements using a variation of the Geohash technique where positions are encoded using 52 bit integers" 라고 명시되어 있습니다.

• 52-bit를 사용하는 이유는 double 타입의 score가 52-bit 정수를 정밀도 손실 없이 표현할 수 있기 때문입니다 Redis Geo (opens in a new tab)

Redis Geo 문서에서 "A sorted set double score can represent a 52-bit integer without losing precision. Doubles are 64-bit floating point representations with a special property: 52-bit integers are perfectly represented with no loss of accuracy" 라고 명시되어 있습니다.

내부 구조: Sorted Set + Geohash

Redis Geospatial은 특별한 자료구조가 아니라 기존 Sorted Set을 활용한 구현입니다.

• Key: 위치명 (예: "Seoul", "Busan")
• Score: Geohash로 인코딩된 52-bit 정수
• 장점: Sorted Set의 logarithmic 시간 복잡도와 선형 메모리 사용량을 그대로 활용 Memurai 블로그 (opens in a new tab)

Memurai 블로그에서 "Sorted Sets exhibit a good space-time balance by consuming a linear amount of RAM while providing logarithmic computing complexity for most operations" 라고 명시되어 있습니다.

Geohash 알고리즘 동작원리

Geohash는 2차원 좌표를 1차원 정수로 변환하는 알고리즘입니다.

1. Binary Encoding (이진 인코딩)

위도와 경도를 각각 이진수로 인코딩합니다 Medium - How Geohash Works (opens in a new tab):

• 위도 범위: -90 ~ 90도
• 경도 범위: -180 ~ 180도
• 각 단계에서 범위를 반으로 나누고, 좌표가 하위 절반이면 0, 상위 절반이면 1을 추가

Medium 글에서 "The algorithm gradually narrows down coordinate ranges by encoding whether a coordinate lies in the lower or upper half of the current interval, appending a 0 for the lower half and a 1 for the upper half" 라고 명시되어 있습니다.

2. Bit Interleaving (비트 인터리빙)

경도와 위도의 비트를 교차 배치합니다 Yat Man Wong - Medium (opens in a new tab):

경도: 1 0 1 1 0
위도: 0 1 1 0 1

결과: 1 0 0 1 1 1 1 0 0 1  (경도, 위도, 경도, 위도, ...)

Medium 글에서 "The algorithm takes one bit from longitude, then one from latitude, then one from longitude again, alternating like that until we have a single longer binary string, with the first bit always being the longitude bit" 라고 명시되어 있습니다.

• 짝수 인덱스 비트: 경도
• 홀수 인덱스 비트: 위도

3. 52-bit 정수로 변환

인터리빙된 이진 문자열을 52-bit 정수로 변환하여 Sorted Set의 score에 저장합니다.

거리 계산: Haversine 공식

Redis는 두 지점 간 거리를 계산할 때 Haversine 공식을 사용합니다 Redis 블로그 (opens in a new tab).

Redis 공식 블로그에서 "Redis uses the Haversine formula to calculate the distances as the model assumes that the Earth is a sphere" 라고 명시되어 있습니다.

수학적 정의

Haversine 공식은 구면 위의 두 점 사이의 **대원 거리(great-circle distance)**를 계산하는 공식입니다. 대원 거리란 구의 중심을 지나는 평면으로 자른 원(대원) 위에서의 최단 거리를 의미합니다.

Haversine 함수

Haversine 함수는 다음과 같이 정의됩니다:

이 함수는 각도를 입력으로 받아 0과 1 사이의 값을 반환하며, 구면 삼각법에서 중요한 역할을 합니다.

완전한 공식

두 지점 사이의 거리 $d$는 다음과 같이 계산됩니다:

또는 Haversine 함수를 전개하면:

변수 설명

계산 과정

1. 좌표 변환: 위도/경도를 degree에서 radian으로 변환 $\text{radian} = \text{degree} \times \frac{\pi}{180}$

2. 차이 계산: 위도 차이 $\Delta\varphi = \varphi_2 - \varphi_1$와 경도 차이 $\Delta\lambda = \lambda_2 - \lambda_1$를 계산

3. Haversine 적용: $a = \sin^2\left(\frac{\Delta\varphi}{2}\right) + \cos(\varphi_1) \cdot \cos(\varphi_2) \cdot \sin^2\left(\frac{\Delta\lambda}{2}\right)$

4. 중심각 계산: $c = 2 \cdot \arcsin(\sqrt{a})$

5. 거리 계산: $d = r \cdot c$

계산 예시

서울(37.5665°N, 126.9780°E)과 부산(35.1796°N, 129.0756°E) 간의 거리:

1. Radian 변환:

   • $\varphi_1 = 37.5665° \times \frac{\pi}{180} = 0.6555$ rad
   • $\varphi_2 = 35.1796° \times \frac{\pi}{180} = 0.6139$ rad
   • $\lambda_1 = 126.9780° \times \frac{\pi}{180} = 2.2155$ rad
   • $\lambda_2 = 129.0756° \times \frac{\pi}{180} = 2.2521$ rad

2. 차이 계산:

   • $\Delta\varphi = 0.6139 - 0.6555 = -0.0416$ rad
   • $\Delta\lambda = 2.2521 - 2.2155 = 0.0366$ rad

3. Haversine 적용: $a = \sin^2\left(\frac{-0.0416}{2}\right) + \cos(0.6555) \cdot \cos(0.6139) \cdot \sin^2\left(\frac{0.0366}{2}\right)$ $a \approx 0.000433 + 0.789 \times 0.814 \times 0.000335 \approx 0.000648$

4. 중심각과 거리: $c = 2 \cdot \arcsin(\sqrt{0.000648}) \approx 0.0509 \text{ rad}$ $d = 6371 \times 0.0509 \approx 324 \text{ km}$

Haversine 공식의 특징

• 지구를 구체로 가정하므로 최대 0.5% 오차 발생 가능 Redis GEODIST 문서 (opens in a new tab)

Redis 공식 문서에서 "The distance is computed assuming that the Earth is a perfect sphere, so errors up to 0.5% are possible in edge cases" 라고 명시되어 있습니다.

• 구 표면의 최단 경로 (대원 거리) 를 계산
• 삼각함수 연산이 CPU 사이클의 약 55%를 차지 Redis 7 성능 개선 (opens in a new tab)

Redis 블로그에서 "These calculations rely heavily on trigonometric functions to compute the Haversine distance, and calling trigonometric functions is expensive in terms of CPU cycles. In a bottleneck analysis of a simple GEOSEARCH command, around 55% of the CPU cycles are spent within those functions" 라고 명시되어 있습니다.

반경 쿼리 동작원리

반경 내 위치를 검색할 때 Redis는 Bounding Box 방식을 사용합니다 Matt's Redis Geo (opens in a new tab).

Matt's Redis Geo 문서에서 "This format allows for bounding box and radius querying by checking the 1+8 areas needed to cover the whole shape, with areas checked by calculating the range of the box covered and computing the score range to query" 라고 명시되어 있습니다.

검색 과정

1. 중심점을 기준으로 반경을 포함하는 1+8개의 영역을 계산
2. 각 영역의 Geohash 범위를 Sorted Set에서 조회 (ZRANGEBYSCORE)
3. 후보 지점들의 실제 거리를 Haversine 공식으로 계산
4. 반경 내에 있는 지점만 필터링하여 반환

주요 명령어와 시간 복잡도

GEOADD

위치를 추가합니다 Redis GEOADD 문서 (opens in a new tab).

GEOADD locations 126.9780 37.5665 "Seoul" 129.0756 35.1796 "Busan"

• 시간 복잡도: O(log(N)) per item
• 제약사항:
  • 경도 범위: -180 ~ 180도
  • 위도 범위: -85.05112878 ~ 85.05112878도

Redis 공식 문서에서 "The time complexity for this command is O(log(N)) for each item added, where N is the number of elements in the sorted set" 라고 명시되어 있습니다.

GEOSEARCH

반경 또는 사각형 영역 내 위치를 검색합니다 (Redis 6.2.0+) Redis GEOSEARCH 문서 (opens in a new tab).

GEOSEARCH locations FROMLONLAT 126.9780 37.5665 BYRADIUS 100 km

• 시간 복잡도: O(N+log(M))
  • N: 필터 영역 내 요소 수
  • M: 인덱스 내 전체 요소 수
• Redis 7에서 4배 성능 향상 달성

Redis 블로그에서 "We can reach four times the throughput on GEOSEARCH queries, and that enhancement has already been released as part of Redis 7" 라고 명시되어 있습니다.

GEORADIUS (Deprecated)

GEOSEARCH로 대체되었습니다 Redis GEORADIUS 문서 (opens in a new tab).

Redis 공식 문서에서 "This command should be used in place of the deprecated GEORADIUS and GEORADIUSBYMEMBER commands" 라고 명시되어 있습니다.

GEORADIUS locations 126.9780 37.5665 100 km WITHDIST

• 시간 복잡도: O(N+log(M))

GEODIST

두 지점 간 거리를 계산합니다 Redis GEODIST 문서 (opens in a new tab).

GEODIST locations "Seoul" "Busan" km

• 시간 복잡도: O(log(N))
• 지원 단위: m (미터), km (킬로미터), mi (마일), ft (피트)

실제 사용 예시

# 1. 위치 추가
GEOADD stores 126.9780 37.5665 "GangnamStore"
GEOADD stores 127.0276 37.4979 "SeoulNationalUniv"
GEOADD stores 126.9520 37.4563 "SeoulArts"
 
# 2. 반경 10km 내 매장 검색
GEOSEARCH stores FROMLONLAT 126.9780 37.5665 BYRADIUS 10 km WITHDIST
 
# 3. 두 매장 간 거리 계산
GEODIST stores "GangnamStore" "SeoulNationalUniv" km
 
# 4. 매장의 Geohash 확인
GEOHASH stores "GangnamStore"
 
# 5. 매장 좌표 조회
GEOPOS stores "GangnamStore"

성능 특성 및 최적화

장점

• 빠른 검색 속도: O(log(N)) 시간 복잡도
• 공간 효율적: Sorted Set의 선형 메모리 사용량
• 정확한 거리 계산: Haversine 공식 사용

제한사항

• 극지방 근처에서 최대 0.5% 오차 발생 가능 (지구를 구체로 가정)
• 삼각함수 연산으로 인한 CPU 부하
• 반경이 클수록 실행 시간 증가

최적화 팁 Groupon Engineering - Medium (opens in a new tab)

Medium 글에서 "It is important to keep the key size small and the data partitioned to avoid overloading any single node. Increases in radius can cause the command execution time to increase" 라고 명시되어 있습니다.

• 키 크기를 작게 유지하고 데이터를 분할
• 반경을 필요한 만큼만 제한
• Redis 7 이상 사용 (성능 4배 개선)
• GEOSEARCH 사용 (GEORADIUS는 deprecated)

참고 자료

• Redis 공식 문서 - Geospatial (opens in a new tab)
• Redis 7 Geographic Commands 성능 개선 (opens in a new tab)
• Geohash 알고리즘 설명 (opens in a new tab)
• Haversine 공식 (opens in a new tab)