근처에 있는 사용자 조회 기능: Redis Geospatial가 적합한 선택일까?

들어가면서..

IT 연합 동아리 디프만에서 진행한 프로젝트에서 '위치기반 주변 유저를 조회'하는 기능을 구현해야 했습니다.

이번 글에서는 다양한 공간 인덱싱 알고리즘과 시스템을 비교 분석하고, Redis Geospatial를 선택한 과정과 구현 방법에 대해 공유하려 합니다.

요구사항 및 제약 조건

프로젝트 런칭까지 2주, 이 기능 개발에 1주 이내로 개발해야했습니다.
위치 정보는 영구 저장이 필요없습니다. (명함 교환 시점에만 필요)
사용자 경험을 위해 검색 결과는 빠르게 제공될 수록 좋습니다.
같은 테이블~같은 건물 내 유저 검색 필요하고, 매우 정밀한 검색은 요구되지 않습니다.

우리팀은 Web팀이었고, 백엔드팀에 비해 많은 리소스를 할애할 수 없는 상황이었습니다.

따라서 프론트엔드에 부담을 줄 수 있는 Geolocation API나 PWA 위치 검색 기능과 같은 기술은 지양하려 했습니다.

해당 요구사항을 해결할 수 있는 방법을 추려보겠습니다.

1. Redis의 Geospatial [선택된 방법]

장점:

인메모리 특성으로 인한 빠른 응답 시간 (10~100ms이내)
Sorted Set 기반 구현으로 효율적인 범위 검색
구현 난이도가 낮아 빠른 개발 가능
현재 서비스에 Redis 시스템이 구축되어 있음

단점:

복잡한 공간 연산 제한(2차원까지 가능)
대용량 데이터 처리 시 메모리 제약(인메모리의 한계)

2. MongoDB의 2dsphere

장점:

GeoJSON 형식 지원으로 다양한 지리적 객체 표현 가능
영구 저장에 적합한 도큐먼트 기반 DB

단점:

새로운 인프라 구성 필요
설정 및 인덱스 최적화에 추가 시간 필요

3. PostgreSQL의 PostGIS

4. 우버의 H3/구글의 S2 라이브러리와 Redis

장점:

정밀한 공간 인덱싱 제공
계층적 격자 구조로 효율적인 영역 검색

단점:

Redis와 별도 통합 작업 필요
구현 복잡성 증가
학습 곡선이 가파름

결론적으로 Redis Geospatial이 최적의 선택이라고 생각했습니다.

기존 인프라를 활용하면 빠른 개발이 가능하고, 약간의 오차범위가 있어 정밀하진 않지만 범위가 요구사항을 해치지 않는다는 것이 이유였습니다.

실제로 Redis에서 Geospatial를 어떻게 구현하고 있는지 정리하면서 서비스에 적용될 기술에 대해 이해하고자 했습니다.

Geohash 알고리즘

먼저 Redis 구현의 핵심 원리인 Geohash가 무엇인지 알아보겠습니다.

Geohash란 무엇인가?

출처: https://en.wikipedia.org/wiki/Geohash

Geohash는 위도와 경도로 표현되는 2차원 좌표를 1차원 문자열로 변환하는 알고리즘입니다.

지구를 재귀적으로 분할하여 위치를 인코딩하는 방식이며, 위도와 경도의 비트를 번갈아가며 조합하는 것이 핵심입니다.


  
    
    
    
    
  
# Geohash 인코딩의 핵심 개념
def encode_geohash(lat, lon, precision):
    lat_range = (-90.0, 90.0)
    lon_range = (-180.0, 180.0)
    bits = ""

    is_lon = True  # 경도와 위도 비트를 번갈아 생성
    while len(bits) < precision * 5:
        if is_lon:
            mid = (lon_range[0] + lon_range[1]) / 2
            if lon > mid:
                bits += "1"
                lon_range = (mid, lon_range[1])
            else:
                bits += "0"
                lon_range = (lon_range[0], mid)
        else:
            # 위도 처리 (유사한 방식)
            ...
        is_lon = not is_lon

    # 5비트씩 Base32로 변환
    return bits_to_base32(bits)[:precision]

Geohash의 주요 특성

1. 계층적 구조:

같은 접두사를 가진 Geohash는 같은 지역에 위치
문자열이 길수록 더 정확한 위치 표현

2. 정밀도와 크기:

5자: 도시 구역 수준(±2.4km)
6자: 동네 수준(±0.61km)
8자: 건물 수준(±38m)

실습 사이트: https://www.movable-type.co.uk/scripts/geohash.html

3. 한계점:

경계 문제: Geohash 경계 부근에서는 실제로 가까운 두 지점이 완전히 다른 해시값을 가질 수 있음
Z-order curve 특성으로 인한 공간 불연속성

Redis의 Geohash 구현

소스코드: https://github.com/redis/redis/blob/unstable/src/geohash.c

이번에는 Redis에서는 어떤 방식으로 이 Geohash를 구현하고 있는지 확인해보겠습니다. (c언어로 구현되어있습니다.)

1. 52비트 정수 Geohash 표현

Redis는 일반적인 Base32 문자열 대신 52비트 정수를 사용합니다.

위도와 경도를 각각 26비트(약 3.7cm 정밀도)로 변환한 후, 이를 번갈아 조합하여 52비트 정수를 생성합니다.


  
    
    
    
    
  
uint64_t geohashEncode(double longitude, double latitude) {
    uint64_t lat_bits = 0, lon_bits = 0;

    /* 위도를 26비트로 변환 */
    lat_bits = latToGeohashBits(latitude);

    /* 경도를 26비트로 변환 */
    lon_bits = longToGeohashBits(longitude);

    /* 비트 인터리빙하여 52비트 정수 생성 */
    return interleave52(lat_bits, lon_bits);
}

2. 비트 인터리빙 최적화

Redis는 비트 조작을 통해 효율적인 인터리빙 알고리즘을 구현했습니다:


  
    
    
    
    
  
static inline uint64_t interleave52(uint32_t xlo, uint32_t ylo) {
    uint64_t x = xlo;
    uint64_t y = ylo;

    x = (x | (x << 16)) & 0x0000ffff0000ffff;
    x = (x | (x << 8)) & 0x00ff00ff00ff00ff;
    x = (x | (x << 4)) & 0x0f0f0f0f0f0f0f0f;
    x = (x | (x << 2)) & 0x3333333333333333;
    x = (x | (x << 1)) & 0x5555555555555555;

    y = (y | (y << 16)) & 0x0000ffff0000ffff;
    y = (y | (y << 8)) & 0x00ff00ff00ff00ff;
    y = (y | (y << 4)) & 0x0f0f0f0f0f0f0f0f;
    y = (y | (y << 2)) & 0x3333333333333333;
    y = (y | (y << 1)) & 0x5555555555555555;

    return x | (y << 1);
}

이 알고리즘은 비트 시프트(수학적으로 곱셈, 나눗셈)와 마스킹 연산(AND, OR)을 통해 O(log n) 시간 복잡도로 인터리빙을 수행합니다.

여기서 Bit Interleaving이란 두 개의 정수 값에서 각각의 비트를 번갈아가며 조합하는 기술을 말합니다.

3. Sorted Set 자료구조 활용

Redis는 Geospatial 데이터를 저장하기 위해 기존 Sorted Set 자료구조를 재활용합니다:


  
    
    
    
    
  
int geoaddCommand(client *c) {
    // ...

    /* 좌표를 geohash로 변환 */
    bits = geohashEncode(xy[0], xy[1]);

    /* geohash를 score로 사용하여 Sorted Set에 저장 */
    robj *score = createObject(OBJ_STRING, sdsfromlonglong((long long)bits));

    /* 내부적으로 ZADD 명령 호출 */
    zaddCommand(c);

    // ...
}

지리적으로 가까운 점들이 Sorted Set 내에서도 가까이 위치하게 되어 범위 검색이 매우 효율적입니다.

4. 반경 검색 최적화

GEORADIUS 명령은 다음과 같은 단계로 최적화되어 있습니다:

중심점과 반경으로 경계 상자(bounding box) 계산
이 경계 상자를 포함하는 geohash 범위 결정
Sorted Set에서 해당 범위의 멤버 검색
Haversine 공식으로 정확한 거리 계산 및 필터링


  
    
    
    
    
  
double geohashGetDistance(double lon1d, double lat1d, double lon2d, double lat2d) {
    double lat1r, lon1r, lat2r, lon2r, u, v;
    lat1r = deg_rad(lat1d);
    lon1r = deg_rad(lon1d);
    lat2r = deg_rad(lat2d);
    lon2r = deg_rad(lon2d);
    u = sin((lat2r - lat1r) / 2);
    v = sin((lon2r - lon1r) / 2);
    return 2.0 * EARTH_RADIUS_KM * asin(sqrt(u * u + cos(lat1r) * cos(lat2r) * v * v));
}

먼저 geohash의 공간 지역성을 활용해 후보를 대략적으로 필터링한 후, 정확한 거리 계산으로 최종 결과를 얻는 2단계 접근법을 사용합니다.

5. Geohash 경계 문제와 Redis의 해결책

앞서 언급한 Geohash의 경계 문제(가까운 두 지점이 완전히 다른 해시값을 가질 수 있는 문제)에 대해 Redis는 다음과 같은 방법으로 이를 해결합니다:

1. 경계 상자(Bounding Box) 확장:

GEORADIUS 명령을 실행할 때, Redis는 지정된 반경보다 약간 더 큰 경계 상자를 계산합니다.
이 확장된 경계 상자는 여러 Geohash 셀을 포함할 수 있습니다.

2. 거리 계산:

경계 상자 내의 모든 후보 위치에 대해 Haversine 공식을 사용하여 비교적 정확한 거리를 계산합니다. (Haversine 공식을 사용하므로, 지구가 완벽한 구라고 가정합니다.)
이 두 번째 필터링 단계에서 실제 반경 내에 있는 위치만 결과에 포함됩니다.

Redis Geospatial 기능 간단 정리

Redis Geospatial은 위치 기반 데이터를 저장하고 쿼리하기 위한 명령어를 제공합니다. 간단하게 어떤 기능이 존재하는지 정리해보겠습니다.

1. GEOADD

지리 공간 데이터를 추가합니다.


  
    
    
    
    
  
GEOADD key longitude latitude member [longitude latitude member ...]

예시:


  
    
    
    
    
  
GEOADD locations:session1 127.0281 37.4981 "user1"

2. GEOPOS

멤버의 위치(위도와 경도)를 조회합니다.


  
    
    
    
    
  
GEOPOS key member [member ...]

예시:


  
    
    
    
    
  
GEOPOS locations:session1 "user1"

3. GEODIST

두 멤버 간의 거리를 계산합니다.


  
    
    
    
    
  
GEODIST key member1 member2 [unit]

단위는 m(미터), km(킬로미터), mi(마일), ft(피트) 중 선택 가능합니다.

예시:


  
    
    
    
    
  
GEODIST locations:session1 "user1" "user2" m

4. GEORADIUS

중심점으로부터 특정 반경 내에 있는 멤버를 찾습니다.


  
    
    
    
    
  
GEORADIUS key longitude latitude radius unit [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC]

옵션:

WITHCOORD: 결과에 좌표 포함
WITHDIST: 결과에 거리 포함
COUNT : 반환할 최대 항목 수 제한
ASC/DESC : 거리에 따른 정렬 방식

예시:


  
    
    
    
    
  
GEORADIUS locations:session1 127.0281 37.4981 100 m WITHDIST

5. GEORADIUSBYMEMBER

특정 멤버를 중심으로 일정 반경 내에 있는 멤버를 찾습니다.


  
    
    
    
    
  
GEORADIUSBYMEMBER key member radius unit [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC]

예시:


  
    
    
    
    
  
GEORADIUSBYMEMBER locations:session1 "user1" 100 m WITHDIST

6. GEOHASH

멤버의 Geohash 문자열을 반환합니다.


  
    
    
    
    
  
GEOHASH key member [member ...]

예시:


  
    
    
    
    
  
GEOHASH locations:session1 "user1"

Redis Geospatial 검증 테스트 결과

Redis Geospatial을 사용한 위치 검색의 정밀도를 검증하기 위해 다양한 거리에서의 검색 정확도와 성능을 테스트했습니다.

테스트는 대략적인 거리 테스트(10m, 1m, 10cm, 정확히 같은 위치)와 1~10m 거리 범위의 세분화된 정밀도 테스트로 진행했습니다.

테스트 결과는 다음과 같았습니다.

(자세한 테스트는 해당 PR에서 확인할 수 있습니다. https://github.com/depromeet/Took-BE/pull/63 )

1. 위치 등록 및 조회 정확도

테스트 결과, Redis는 요구사항 범위 내에서 정확하게 저장하고 조회할 수 있었습니다:

10m 떨어진 위치: 정확히 저장 및 조회 가능 (오차 < 0.0001도)
1m 떨어진 위치: 정확히 저장 및 조회 가능 (오차 < 0.0001도)
10cm 떨어진 위치: 정확히 저장 및 조회 가능 (오차 < 0.0001도)
동일 위치의 여러 사용자: 모두 정확히 같은 위치로 저장됨

2. 거리 계산 정확도

두 사용자 간 거리 계산 테스트 결과:

10m 거리: 8.0~16.0m 사이로 계산 (평균 오차 ±3m)
1m 거리: 0.7~1.6m 사이로 계산 (평균 오차 ±0.4m)
10cm 거리: 0.05~0.3m 사이로 계산 (평균 오차 ±0.12m)
동일 위치: 0.1m 미만으로 계산 (오차범위 감안)

1~10m 세분화 거리 테스트 결과:

테스트 로그에서 관찰된 실제 거리 측정값과 정확한 오차율을 정리해봤습니다.

예상거리	테스트 측정 거리	오차율(%)
1m	0.95m	-5.34%
2m	1.89m	-5.34%
3m	2.84m	-5.34%
4m	3.79m	-5.34%
5m	4.73m	-5.34%
6m	5.68m	-5.34%
7m	7.10m	+1.43%
8m	8.05m	+0.58%
9m	8.99m	-0.08%
10m	9.94m	-0.60%

1m~6m 거리에서는 일관되게 약 -5.34%의 오차 발생
7m 이상에서는 오차 패턴이 변화하며, 정확도가 높아짐(±1.5% 이내)

3. 반경 검색 정확도 및 성능

반경 15m 내 사용자 검색

모든 테스트 사용자(기준점, 10cm, 1m, 10m 떨어진 사용자) 검색
거리 기준 정렬 정확히 작동
평균 응답 시간: 38ms

반경 5m 내 사용자 검색

기준점, 10cm, 1m 떨어진 사용자만 검색 (10m 사용자 제외)
평균 응답 시간: 23ms

반경 50cm 내 사용자 검색

기준점과 10cm 떨어진 사용자만 검색
평균 응답 시간: 29ms

정밀 검색의 한계

반경 15cm 내 검색 시 기준점만 검색됨 (10cm 떨어진 사용자 미포함)
반경 20cm로 설정해야 10cm 떨어진 사용자까지 검색 가능
평균 응답 시간: 25ms

4. 사용자 위치 조회 테스트 성능

단일 사용자 위치 정확히 조회: 평균 26ms
두 사용자 간 거리 계산: 평균 55ms

정밀도 검증 결론

테스트 결과를 통해 다음과 같은 결론을 얻을 수 있었습니다.

1. 위치 저장 정밀도: Redis Geospatial은 센티미터 단위의 저장이 가능하며, 이는 요구사항에 적합한 정도의 범위를 가지고 있음을 의미함.

2. 거리 계산 정확도:

1~6m 범위: 일관된 패턴으로 약 -5.34%의 오차율 유지
7~10m 범위: 매우 높은 정확도로 약 ±1.5% 이내의 오차율 유지
전체적으로 10% 이내의 오차로 실용적 사용에 적합

3. 반경 검색 한계:

Redis는 반경 검색에서 다소 보수적으로 범위를 설정하는 듯했습니다.(구현 방식의 한계일 수도 있고요..!)
실제 적용 시 의도한 범위보다 약 5~10% 크게 설정하는 것이 필요하다고 판단했습니다.

4. 응답 시간:

단일 연산: 평균 20~50ms 이내
복잡한 검색: 평균 40~60ms 이내
모든 테스트에서 100ms 이내의 빠른 응답 속도 유지

이러한 테스트 결과는 구현하고자 하는 명함 교환과 같은 실시간 근접 사용자 검색 기능에 Redis Geospatial이 충분한 정밀도와 성능을 제공함을 검증할 수 있었습니다.

특히 같은 테이블(1m)이거나 같은 건물(5m) 내 사용자 검색에 적합하다는 생각이 들고, 충분히 빠른 응답 시간으로 좋은 사용자 경험을 제공할 수 있.

마치며

Redis Geospatial이 가장 적합한 선택인지는 좀더 정밀한 검증이 필요하겠지만, 테스트 결과에서 구현 시간, 성능, 정밀도 측면에서 요구사항을 모두 충족시키는 것을 확인할 수 있었습니다.

최소 거리인 15-20cm 이하의 초정밀 검색에서는 일부 한계가 있었지만, 이는 실제 명함 교환 시나리오에서는 큰 문제가 되지 않을 것으로 판단되었습니다.

1-5m 반경 내의 검색에서는 매우 빠르고 정확한 결과를 제공하여 사용자 경험 측면에서도 충분히 만족스러운 성능을 보여주었습니다.

뿌듯하네요!

참고 자료

Redis 공식 문서: https://redis.io/docs/latest/develop/data-types/geospatial/
Redis 소스 코드: geohash.c, geo.c
Geohash 알고리즘: Wikipedia - Geohash
Redis 개발자 블로그: Redis의 Geospatial 기능

'개발 일지 > Depromeet (디프만, IT 연합동아리)' 카테고리의 다른 글

[디프만] 16기 서버 파트 최종 합격 후기 (3)	2024.12.31

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`