2권 목차를 보면서 조금 의문이 들었다. 1, 2, 3장 연달아서 지리 데이터를 다루기 때문이다.
- 1장: 근접성 서비스
- 2장: 주변 친구
- 3장: 구글 맵
1장을 다 읽은 뒤 나오는 새로운 장 이름이 ‘주변 친구’ 길래 뭐야? 하면서 2장을 슥 읽어봤다. 스포일러를 해보자면…
1장 ‘근접성 서비스’를 읽었다면 왜 그 서비스와 비슷해 보이는 ‘주변 친구’ 검색 기능에 별도 장을 할애해야 하는지 궁금할 것이다. 하지만 좀 더 주의 깊게 들여다보면, 두 기능 사이에는 큰 차이가 있음을 눈치챌 수 있다. 근접성 서비스의 경우 사업장 주소는 정적이지만, 주변 친구 위치는 자주 바뀔 수 있기 때문이다.
…음 그렇군, 납득! 3장도 비슷한 맥락에서 별도 장을 넣은 것 같았다.
하지만 1, 2, 3장 모두 지리 데이터를 다룬다는 사실은 변하지 않는다. 1장에서 나온 개념이 2장, 3장에서도 반복해서 나온다. 그러니 이번 장에서 지리 데이터를 다룰 때 어떤 방식을 사용하는지, 무엇을 주의해야 하는지 제대로 이해하고 넘어가보자.
들어가며
- 위치 기반 서비스(Location-Based Service)를 줄여서 LBS 라고 표현한다.
- 이번 장에서는 사용자의 위치를 바탕으로 ‘근처에 있는 음식점/카페/편의점/… 찾기’ 서비스를 구현해본다.
목표
요구사항은 크게 기능 요구사항과 비기능 요구사항으로 나눌 수 있다. 이번 장의 요구사항은 이렇다.
기능 요구사항
- 사용자는 자신의 위치와 검색 반경에 매치되는 사업장 목록을 확인하고 사업장의 상세 정보를 볼 수 있다.
- 검색 반경은 0.5km, 1km, 2km, 5km, 20km 중 선택할 수 있어야 한다.
- 사업장 소유주는 사업장 정보를 추가, 삭제, 수정할 수 있다. 단, 그 정보가 검색 결과에 실시간으로 반영될 필요는 없다.
비기능 요구사항
- 낮은 응답 지연(latency): 검색 속도가 빨라야 한다.
- 데이터 보호(data privacy): 위치 정보도 개인정보다. LBS를 설계할 때는 항상 사용자 정보를 보호할 방법을 고려해야 한다. 다만 책에서 이 부분을 자세히 다루지는 않았다.
- 고가용성(high availability) 및 규모 확장성(scalability): 인구 밀집 지역에서 이용자가 집중되는 시간에 트래픽이 급증해도 멀쩡하게 잘 동작해야 한다.
하는 일
위 요구사항을 만족하기 위해 책에서는 이런 일을 한다.
- 빠른 검색 속도를 보장하기 위해 적절한 데이터 스키마와 알고리즘을 사용한다.
- 데이터를 복제하고 캐싱하여 검색 속도를 보장하고 고가용성과 규모 확장성을 보장한다.
- 다행히 사업장 소유주가 수정한 데이터가 실시간으로 반영될 필요는 없다는 점을 함께 고려한다.
큰 그림
이번 장의 전체 설계도는 그렇게 복잡하지 않다. 대신 왼쪽에 있는 ‘위치 기반 서비스’의 내부 알고리즘에 집중하는 장이다.
데이터 모델 설계
읽기/쓰기 연산의 비율
가장 먼저 데이터 모델을 설계해보자. 책에서는 읽기, 쓰기 연산의 비율을 먼저 따져본다. 사용자가 사업장을 검색하는 트래픽이 사업장 소유주가 사업장을 등록, 수정, 삭제하는 트래픽보다 훨씬 많을 것이다. 즉, 이번 서비스에서는 읽기 연산이 쓰기 연산보다 압도적으로 많이 일어난다. 이럴 때에는 MySQL 같은 관계형 DB를 쓰는게 좋다. (왜인지는 책에 나와있지 않다. 다른 데이터베이스 유형과 비교하면 좋았겠지만, 이게 메인 주제가 아니기 때문에 생략한 것 같다. 뇌피셜로 얘기해보자면 우선 이번에 넣을 데이터는 스키마가 고정되어있고, 인덱스를 활용한 빠른 읽기 및 높은 성능의 Join 연산과 View를 지원하는 등의 장점이 있기 때문이 아닐까 싶다.)
위치 데이터를 넣을 때
사업장 데이터를 넣는 두가지 방법이 있다.
- 위치별로 사업장 목록을 저장하기
- 사업장별로 위치를 저장하기
첫 번째 방법은 비슷한 위치에 있는 사업장끼리 하나의 리스트로 묶어서 저장하는 방법이다. 그러니까 row 하나가 이렇게 생겼을 것이다.
| location | businessIds |
|---|---|
| (위치 1) | [12009, 2314412, 233943, …] |
(location_x, location_y 가 있어야 하지 않냐고 물어볼 수 있다. 하지만 우리는 아래에서 2차원 평면 상의 값을 하나의 숫자로 표현하는 방법을 알아볼 것이다. 그러니 지금은 ‘(위치 1)’ 이라고 하자.) 따라서 위치를 얼마나 잘게 나누었느냐에 따라 row 개수가 결정된다.
두 번째 방법은 사업장별로 위치를 저장하는 방법이다.
| businessId | location |
|---|---|
| 12009 | (위치 1) |
따라서 사업장 개수만큼 row 가 만들어진다.
책에서는 두 번째 방법을 권장한다. 첫 번째 방식을 쓰면 애플리케이션 로직이 복잡해지기 때문이다.
- (위치 1)만을 읽어올 때에는 아주 간편하지만
- 사업장을 추가 혹은 삭제해야 할 때 머리가 아파진다.
- 이런 상황을 생각해보자. 새로운 9999999 번 사업장이 (위치 1)에 들어가야 해서 쓰기 연산을 시작했다. 사업장 추가 연산이 완료되기 전에 (위치 1)에 있던 기존 사업장 12009 은 삭제해달라는 요청이 들어온다. 그러면 삭제 연산의 결과로 인해 사업장 추가 연산의 결과가 덮어씌워지지 않도록, (위치 1)에 대해 lock 을 잡고 새로운 사업장 추가 작업이 끝날 때까지 기다린 후 삭제 쿼리를 처리할 수 있다.
- 사업장을 수정할 때에도 시간이 걸린다.
- businessId 를 기준으로 검색을 하고 싶지만 배열 데이터에 들어가 있기 때문에 모든 데이터를 검색해봐야 한다. 어느 위치에 원하는 businessId 가 있는지 모르기 때문이다.
- 새 사업장을 추가하기 위해 businessId 가 기존에 존재하는 id 인지 확인하고 싶을 때에도 모든 데이터를 검색해봐야 한다.
하지만 두 번째 방법을 사용하면 편하다. businessId 와 location 을 기준으로 복합 키를 걸어버리면 된다. 그러면 검색 속도도 보장할 수 있고, lock 을 잡을 필요도 없다. BusinessId 에 단일 키를 설정하면 id 중복도 간단하게 막을 수 있다.
위치 기반 서비스에서 사용하는 알고리즘
이제 이 장의 핵심인 지리 데이터를 저장하는 방법을 알아보자. 우리는 지도에 있는 장소를 표현할 때 총 2개의 값을 사용한다. x축 값과 y축 값, 혹은 위도와 경도를 쓴다. 하지만 이걸 그대로 데이터베이스에 넣을 수는 없다. 이유는 검색 성능 때문이다.
만약 우리가 데이터를 위도 35.2, 경도 129.0 에 CU 편의점이 있다 라는 식으로 저장했고, 사용자의 위치도 마찬가지로 표현한다고 해보자. 사용자 근처에 있는 사업장을 찾기 위해서는 위도와 경도 이 2가지 값을 모두 검색 조건으로 넣어야 한다. 그러니까 지도를 놓고 보면 빨간색과 파란색 영역의 데이터를 검색한 다음, 교집합을 찾아야 하는 것이다.
당연히 이렇게 하면 검색 성능이 떨어진다. 다른 방법을 찾아야 한다.
균등 분할 격자
지도 데이터를 저장하는 특별한 방법이 있다. 바로 2차원 평면에 있는 점의 위치를 2개의 값이 아닌 1개의 값으로 표현하는 것이다. 대체 어떻게 (x, y) 를 a 하나로 표현한다는 말일까?
정답은 바로 지도를 격자로 나누는 것이다. (누가 이걸 맨 처음 생각해낸걸까? 정말 똑똑하다 🤔)
이제 우리는 저 위치에 서있는 사용자 근처의 사업장을 찾기 위해서 x, y 값을 모두 들고다닐 필요가 없다. 그냥 격자 번호만 알면 된다. 데이터베이스에 사업장을 저장할 때에도 이렇게 하면 된다.
| businessId | location |
|---|---|
| 12009 | (격자번호) |
하지만 이렇게 했을 때 두 가지 문제점(아쉬운 점!)이 있다. 첫째, 격자의 크기는 균등하지만 사업장의 분포는 균등하지 않다는 점이다. 우리나라 스타벅스 매장 분포도만 봐도 한 눈에 알 수 있다. 매장이 밀집된 곳의 격자는 작게, 그렇지 않은 곳의 격자는 크게 표현되면 좋을 것 같다.
둘째, 격자 하나가 주어졌을 때 근처에 있는 격자를 찾기가 까다로울 수 있다. 각 격자 칸의 식별자를 할당할 때 특별한 규칙이 없기 때문이다. 예를 들어 왼쪽 위부터 1, 2, 3, … 번이라는 번호를 부여했다고 해보자. 위쪽 파란 격자 예시에서 1번 격자와 인접한 격자는 2, 10, 11번이 되고 20번 격자와 인접한 격자는 10, 11, 12, 19, 21, 28, 29, 30번이 된다. 찾기 아주 귀찮아진다.
지오해시 Geohash
지오해시에서는 위에서 나온 균등 분할 격자의 두 번째 문제점을 해결한다. 서로 인접한 격자를 찾기 쉬워진다. 지오해시를 만들기 위해서는 먼저 아래와 같이 지도를 4등분한다. 여기서는 우리나라 지도를 그냥 4등분 하지만, 책의 예시에서는 전세계를 자오선과 적도 기준으로 자른다. 그리고 마치 수학 시간에 많이 보던 그래프처럼 각 사분면에 번호를 부여한다.
이렇게 나뉘어진 격자에서 똑같은 작업을 반복한다. 원하는 정밀도가 나올 때까지!
이렇게 지도를 모두 나누었다면, 마지막으로 각 숫자 하나를 비트 하나로 보고 문자열로 인코딩한다. 통상적으로 지오해시는 base32 표현법을 사용한다고 한다.
- 예를 들어 길이 6짜리 구글 본사 지오해시는
1001 11010 01001 10001 11111 11110를 base32 로 표현한9q9hvu가 된다.
그렇다면 ‘길이 6짜리’ 라는건 무슨 기준으로 정하는걸까? 요구사항을 되짚어보면 된다.
검색 반경은 0.5km, 1km, 2km, 5km, 20km 중 선택할 수 있어야 한다.
따라서 우리는 위 길이를 반지름으로 하는 원을 그리고, 그 원을 덮는 크기의 격자를 만들어내는 지오해시 길이를 구하면 된다. 지오해시 길이에 따른 격자 크기는 엘라스틱서치 공식 문서에서 확인할 수 있다. (왜인지 모르겠지만 책에서 여기를 참조로 걸어놓았다.) 필요한 지오해시 길이는 각각 6, 5, 5, 4, 4가 나온다.
지오해시를 사용했을 때, 공통 접두어(prefix)가 긴 격자들이 서로 더 가깝게 놓이도록 보장된다. 그러니까 9q9hvu 보다 9q8znc 가 9q8znf 와 더 가까운 지역이다. 9q8 이라는 글자 3개가 서로 동일하기 때문이다. 이건 직접 지오해시를 만들어보면 바로 이해할 수 있다. 맨 처음 단계의 01 칸을 쪼개어서 만들어진 격자들은 그 격자를 얼마나 잘게 쪼개든 모두 01로 시작하기 때문이다. 그 다음 단계도 마찬가지로 01 11 을 쪼개어서 만들어진 격자들은 계속해서 01 11 을 접두어로 갖게 되고, 그 다음도 계속해서 같은 현상이 반복된다.
지오해시에서의 문제점이 생길 일은 사용자가 각 격자의 경계선에 있는 경우다. 사용자가 9q8znc 와 9q8znf 의 경계에 서있는데 9q8znc 에 있는 사업장만 보여줘서는 안 된다. 이럴 때에는 그냥 두 격자에 해당하는 모든 사업장을 찾아서 보여주면 된다. 특정 지오해시의 주변 지오해시를 찾는 것은 상수 시간 내에 가능한 연산이기 때문이다. (궁금하다면 이곳 을 들어가보자. 코사인 법칙을 사용한다. 이렇게 천재들이 많다.!!!)
https://www.movable-type.co.uk/scripts/geohash.html 에 들어가보면 전세계 지도의 지오해시를 원하는 정밀도로 직접 확인해볼 수 있다.
쿼드트리 Quadtree
지오해시에서는 균등 분할 격자의 두 번째 문제점- 인접한 격자를 찾기 어려움 - 만 해결했다. 쿼드트리는 첫 번째 문제점(이라기 보다는 이상적이지 않은 점) - 격자의 크기가 동일함 - 까지 해결할 수 있다. 즉, 쿼드트리를 사용하면 인접한 격자를 빨리 찾으면서도 서로 다른 격자 크기를 만들어낼 수 있다.
쿼드트리도 비슷하게 사분면을 계속해서 분할하면서 만들어진다. 지오해시와의 차이점은 트리 모양의 자료구조를 만들어내는 방식이라는 점이다. 먼저 사분면을 분할하되, 사분면 안의 사업장이 원하는 개수만큼 존재하게 될 때까지 나눈다. 즉, 사업장이 많이 몰려있는 지역일수록 더 많이 쪼개게 된다. 지오해시에서는 정밀도를 고정시켰기 때문에 각 격자의 크기가 동일했지만 쿼드트리에서는 사업장 개수를 기준으로 하기 때문에 각 격자의 크기가 동일한게 아니라 사업장 개수가 비슷해진다. 따라서 사업장 밀도가 높은 지역이라면 격자 크기가 작아지고 그 반대라면 격자가 커진다.
이렇게 나눈 격자를 트리 형태로 표현한다.
- 내부 노드 (internal node)
- 격자를 식별하기 위한 좌상단, 우하단 꼭지점 좌표
- 하위 노드 4개를 가리킬 포인터
- 위 그림 두 번째 단계의 NW, NE, SW, SE 가 각각 하위 노드가 된다. 즉, 특정 단계에서 나눈 사분면이 그 단계 노드의 child 노드가 된다.
- 리프 노드 (leaf node)
- 격자를 식별하기 위한 좌상단, 우하단 꼭지점 좌표
- 노드 안에 위치하는 사업장 ID 목록
한 가지 주의점은 쿼드트리가 서버 메모리에 올라가야 한다는 점이다. 다행히 쿼드트리 자체의 크기는 그렇게 크지 않다. 격자 안에 최대 100개의 사업장이 존재할 수 있고, 총 2억개 사업장이 있다고 가정했을 때 쿼드 트리의 크기는 1.71GB 에 불과하다. 서버 한 대에 충분히 저장할 수 있는 크기다. 지오해시가 하나씩 추가되는 데이터를 DB에 넣을 때 사용하는 방식이라면 쿼드트리를 만드는 것은 이미 DB에 들어가있는 사업장 정보를 빠르게 탐색할 수 있는 자료구조를 구축하는 것이다. 그래서 지오해시와 쿼드트리를 동시에 사용할 수도 있다.
이렇게 구축한 쿼드 트리를 활용해서 주변 사업장을 검색하려면 어떻게 해야 할까? DFS를 쓰면 된다. 메모리에 쿼드트리 인덱스를 구축해두고, 검색 시작점이 포함된 리프 노드를 만날 때까지 트리를 타고 내려가는 것이다. 이 리프 노드에 원하는 개수만큼의 사업장이 있으면 탐색을 그만두고, 그렇지 않으면 인접 노드도 추가로 탐색하면 된다.
쿼드 트리를 썼을 때 장단점은 분명하다. 장점은 탐색이 빠르고 ‘원하는 k개 사업장 검색’과 같은 요구사항을 만족시킬 수 있다는 점이다. 단점은 트리이기 때문에 사업장 정보를 삭제하거나 추가하기 위한 비용이 많이 든다는 점이다. 하지만 이번 서비스에서는 이게 큰 단점으로 작용하지 않는다. 사용자가 검색하는 요청이 사업장을 추가, 삭제하는 요청보다 압도적으로 많고 사업장 변경 내용이 실시간으로 재빠르게 반영되지 않아도 되기 때문이다.
그럼 무슨 방법을 쓰면 좋을까?
현업에서는 두 방법 모두 사용되고 있다. 이번 글에서 언급하지는 않았지만, 구글의 S2 도 아주 유명한 솔루션이라고 한다.
- 지오해시: 빙(Bing) 지도, 레디스, 몽고DB
- 쿼드트리: 엑스트(Yext)
- 지오해시 + 쿼드트리: 엘라스틱서치
- S2: 구글 맵, 틴더
책에서는 지오해시를 쓰는 것을 가정하고 큰 그림을 그렸다.
좀 더 심화된 내용
데이터베이스 규모 확장
관계형 데이터베이스 규모 확장을 위해서는 크게 2가지 방법이 있다. 복제와 분할이다. 읽기 연산의 부하를 분산하기 위해 사본 데이터베이스를 두고 데이터를 거기다 복제하는 방법과, 데이터 저장 자체를 여러 서버에 분산하여 저장해버리는 분할(파티셔닝)이 있다. 책에서는 위치 기반 데이터를 저장할 때 샤딩을 사용하면 복잡하기 때문에 복제를 선택하라고 권장한다. 자세한 이유는 나와있지 않지만 샤딩 로직을 애플리케이션 계층에 구현해야 하기 때문이다.라고 하는걸 봐서는 인접한 격자들끼리 같은 샤드에 들어가야 하는데 이걸 항상 만족하게 할 수 있는 방법이 없어서가 아닌가, 하는 생각을 해본다.
캐시
그래서 책에서는 사본 데이터베이스 서버를 두고 캐시를 도입한다. 전체 설계도안을 다시 한 번 살펴보자. 사업장서비스의 쓰기 연산은 모두 주(primary) 데이터베이스로 보낸다. 위치 기반 서비스와 사업장 서비스에서 일어나는 읽기 연산은 레디스 클러스터를 참조한다. 부(secondary) 데이터베이스를 곧바로 바라보지 않는 이유는 레디스 클러스터가 캐싱 계층이기 때문이다.
레디스 클러스터에는 두가지 정보가 들어간다. 하나는 사업장 정보, 다른 하나는 지오해시다. 사업장 정보는 쉽다. 사용자가 확인할 사업장 이름, 주소, 사진 등의 상세 정보다. 지오해시는 위에서 살펴봤던 것이다. 각 지오해시 키값별로 해당 격자 내의 사업장 ID 목록을 저장한다. 요구사항을 만족하기 위해 필요했던 지오해시 길이는 4, 5, 6이기 때문에 길이별로 지오해시 데이터를 저장해놓는다. 이렇게 3가지 정밀도의 데이터를 모두 저장한다고 해도 2억개 사업장이 있다고 가정했을 때 약 5GB면 충분하다.
번외) 일반론적인 이야기
2권부터는 각 장을 읽으면서 다른 시나리오에도 적용할 수 있을만한 일반론적인 이야기를 모아보기로 했다. 이번 장에서는 이런 문구를 가져왔다.
고객에게 동일한 가치를 전달할 수 있다면, 가장 단순한 시스템이 최고로 좋은 시스템인 것이다. - 옮긴이(이병준)의 글
읽기 연산이 압도적인 시스템에는 MySQL과 같은 관계형 데이터베이스가 바람직할 수 있다. - 1장 근접성 서비스
→ DB 스키마 설계 할 때에는 읽기/쓰기 비율을 따져봐야 한다.
우리는 두 번째 방안을 추천하는데 그 이유는 다음과 같다. 방안 1의 경우 사업장 정보를 갱신하려면 일단 JSON 배열을 읽은 다음 갱신할 사업장 ID를 찾아내야 한다. 새 사업장을 등록해야 하는 경우에도 같은 사업장 정보가 이미 있는지 확인을 위해 데이터를 전부 살펴봐야 한다. (…) 하지만 방안 2의 경우에는 지오해시와 사업장 ID 칼럼을 합친 (
geohash,business_id)를 복합 키로 사용하면 사업장 정보를 추가하고 삭제하기가 쉽다. - 1장 근접성 서비스
→ DB 스키마 설계 할 때에는 read/write 연산을 할 때 일어나는 시나리오를 고려해야 한다.
결론
- 데이터 스키마를 저장할 때는 읽기/쓰기 연산의 비율과 실제 시나리오를 떠올려보자.
- 위치 기반 데이터를 저장할 때에는 1차원 값으로도 충분하다. 그리고 이렇게 하면 검색에 용이하다.
- 균등 분할 격자: 지도를 동일한 크기의 격자로 나눈다.
- 지오해시: 지도를 동일한 크기의 격자로 나누고, 각 격자마다 규칙성을 갖는 이름을 부여한다.
- 쿼드트리: 지도를 동일한 개수의 데이터를 갖는 단위로 나누고, 나눈 격자를 노드 하나로 한 트리를 만든다.
- 읽기 성능을 높이기 위해서 DB 복제와 캐싱을 선택했다.
