Google S2

Google S2

구글이 개발한 Google S2는 그리드 시스템의 일종입니다.

 

그리드 시스템이란 아래 사진 처럼 지구를 작은 사각형들로 쪼개 지구 표면을 덮는 시스템을 의미합니다.

 

Goolge은 프렉탈 구조(같은 구조의 반복)인 힐버트 곡선을 이용해서 지구 상의 표면을 끊어지지 않는 선을 이용해 덮습니다.

 

http://s2geometry.io/devguide/s2cell_hierarchy

 

직접 Google S2 라이브러리 시각화 도구로 그리드 시스템을 확인해보겠습니다.

 

https://s2.inair.space/

 

위 빨간색 사각형을 Google S2에선 Cell이라 부르고 같은 셀안에 포함된 지점(위경도)들은 모두 동일한 Cell ID를 부여받게 됩니다.

 

이 셀들은 고유한 Level이 존재하는데 Level이 작을 수록 더 넓은 면적을 갖고 Level이 클 수록 더 작은 면적을 같게 됩니다.

 

Cell Level 14

Cell Level 18

 

Cell Level은 우리가 찾고자 하는 영역을 얼마나 정확하게 찾을 수 있는지를 알려줍니다.

 

Cell Level이 얼마만큼 정밀하게 표현이 가능한 지는 아래 사이트를 참조하면 알 수 있습니다.

 

S2 Cell Statistics

 

 

셀 Cell

http://s2geometry.io/devguide/s2cell_hierarchy

 

S2는 우선 지구를 6개의 Face로 나눕니다.

 

6개의 Face 밑에 자식 Cell들을 구분하기 시작합니다. 재귀적으로 Cell들을 구획화하고 최대로 8mm 정도의 지역을 커버링할 수 있습니다.

 

6개의 Face는 64비트 중에서 앞 3비트를 차지합니다.

 

뒤이어 2비트씩 끊어서 자식 셀들을 표현하고 더 이상 자식 셀이 없다면 1로 끝내 마무리하여 Cell ID를 만듭니다.

 

Cell : 100 11 01 1000000 ~ 0 

100 : Face 3번

11 : 자식 셀 3번

01 : 자식 셀 1번

 

이렇게 생성된 64bit Cell ID는 애플리케이션에서 축약된 형태인 Cell Token으로 변환해 저장할 수 있습니다.

 

셀 정규화

S2가 가진 장점 중에서 많은 서비스 기업들이 좋아하는 기술은 셀 정규화 같습니다.

 

셀 정규화는 아래와 같이 특정 Area를 같은 Level의 셀들이 아닌 다양한 Level의 셀들로 영역을 커버합니다.

 

 

셀을 각기 다른 Level로 영역을 커버링한다면 더 세밀하게 영역을 표현할 수도 있고 큰 영역을 하나의 셀로 치환할 수 있어 저장공간도 절약할 수 있습니다.

 

이러한 기술은 PIP(Point In Polygon) 즉, 특정 지점이 특정 영역에 포함되는 지를 식별하는 시스템에서 유용하게 사용할 수 있습니다.

 

사용자의 위경도를 입력받아 시스템에서 설정한 최소 Level, 최대 Level의 Cell ID를 구하고 데이터베이스에 질의한다면 사용자가 특정 지역에 위치해있는 지를 판단할 수 있습니다.

 

물론 데이터베이스에는 미리 Cell ID를 정규화한 상태로 저장돼 있어야합니다.

 

Cell ID들에 인덱스를 걸어두게 되면 일반적인 RDB에서 제공하는 R-Tree가 아닌 B-Tree 방식의 인덱스를 사용할 수 있게 됩니다.

 

실제로 우버는 배차 시스템을 자체 개발한 H3라이브러리를 통해 서비스를 제공하고 있고, 배달의 민족은 S2라이브러리를 사용해 배달지역 시스템을 개편했습니다.

 

가게 배달지역 관리방식 개편 프로젝트 | 우아한형제들 기술블로그

 

Introduction | H3

 

다양한 지리 공간 API 제공

여타 많은 공간 DB와 마찬가지로 많은 지리 공간 API를 제공합니다.

 

Cell들이 겹치는 영역, 중심 좌표, 경계 지역, 인덱싱 등을 지원합니다.

 

S2와 같은 라이브러리가 가지는 또 다른 장점은 무거운 공간 연산을 데이터베이스에서 수행하지 않아도 된다는 점입니다.

 

데이터베이스에서 무거운 연산을 수행한다면 트래픽이 증가하면서 DB 부하는 높아지고 커넥션 고갈, API Latency 증가 등 다양한 문제가 발생할 수 있습니다.

 

S2나 H3같은 라이브러리는 메모리 상에서 지리 연산을 수행하고 Cell들을 검색하기 때문에 성능과 부하 측면에서 이점을 가집니다.

 

고전적인 GeoHash와 S2,H3 라이브러리는 무엇이 다를까?

S2나 H3는 지구 표면을 사각형으로 덮냐 육각형으로 덮냐의 차이점이 있을 뿐 기본 개념은 같습니다.(우버는 공식문서에서 S2보다 H3가 뛰어나다고 강력히 어필 중입니다.)

 

GeoHash를 통해서도 S2나 H3처럼 그리드 시스템을 구축할 수 있지만 왜곡이 상당히 심합니다. 위도에 따라서 그 왜곡은 커지게 되고 S2,H3와 같이 셀을 정규화하는 기능도 없어 저장공간을 절약하기도 어렵습니다.

 

또한 S2나 H3는 글로벌 기업들이 선택해 실제로 사용되고 있기 때문에 어느정도 검증을 받은 셈입니다.

 

S2의 치명적 단점

참고할 레퍼런스가 너무나도 적습니다. 공식문서와 소수의 블로거들이 남긴 글들로 기술을 학습해야합니다.

 

S2 Geometry

 

Google’s S2, geometry on the sphere, cells and Hilbert curve | Terra Incognita

 

Geospatial Indexing Explained: A Comparison of Geohash, S2, and H3