<div id="readability-page-1" class="page"><div><p id="1bc9">그리고 위 같은 지리공간 데이터 타입을 위해 제공되는 연산도 굉장히 다양하다. (물론 PostGIS 같은 특화 DB 보단 조금 적다.)</p><figure></figure><p id="b310">이쯤에서 문득 궁금해졌다. ES 가 텍스트 전문검색을 구현한 방식은 간단히 요약하면 텍스트 데이터를 토큰화하여 역인덱스(inverted-index) 구조로 만들고 각 토큰이 어떤 문서에 존재하는지 매핑 구조를 저장하여 여기서부터 검색하는 것이다. 그럼 지리공간 데이터는 어떻게 인덱싱 했을까? 텍스트 데이터처럼 역인덱스 구조로 저장했을까? 아니면 기존의 지리공간 DB 들 처럼 R-tree 나 S2 library 를 이용했을까? ES 라면 뭔가 다르게 구현했을지도.</p><h2 id="d6ea">Elasticsearch 는 공간 데이터를 어떻게 인덱싱할까</h2><p id="b724">Elasticsearch 가 빠르고 정확한 지리공간 데이터 검색을 지원하기 위해 채택한 인덱싱 방식은 여러번의 변화를 거쳤는데, 이번 글에서는 하나의 큰 변화를 기점으로 구버전의 인덱싱 방식과 신버전의 인덱싱 방식 두가지를 다루고자 한다.</p><h2 id="4fd4">inverted-index (quadTree)</h2><p id="625f">ES 는 기존 텍스트 검색을 위해 사용되던 inverted-index 구조를 공간 데이터 검색에도 그대로 활용했다. 공간 데이터를 어떻게 역인덱스 구조에 넣지? 싶을수도 있다. inverted-index 는 텍스트를 검색 가능한 작은 토큰 단위로 쪼개어 저장하는 방식이다. 공간 데이터도 똑같다. 하나의 큰 공간 데이터(예를 들면 polygon)를 작은 사각형 단위로 쪼개어 저장하는 것이다. 이 쪼개진 단위를 셀(cell)이라고 부른다. 그리고 이렇게 공간 데이터를 셀 단위로 쪼개는 방식을 <a href="https://en.wikipedia.org/wiki/Rasterisation" rel="noopener ugc nofollow" target="_blank">**rasterization</a>** 이라고 부른다. 특정 위치가 어느 polygon 에 있는지 알고 싶다고 하자. 그 위치가 어느 polygon 에 속해있는지는 몰라도 어떤 셀에 있는지는 간단히 알 수 있다. 앞서 우린 모든 셀을 inverted-index 구조에 저장했으니 해당 셀이 어떤 poylgon 에 속해있는지도알 수 있다. 대략 이런 방식으로 ES 는 공간 데이터 인덱싱을 구현했다. 이 방식의 큰 문제는 셀을 어떤 크기로 저장해야하는가? 이다.</p><figure></figure><p id="e6c7">위 그럼처럼 셀을 작게 지정하면 정확도는 증가하지만 인덱스 크기와 퍼포먼스를 희생해야하고 셀을 크게 지정하면 퍼포먼스는 좋아지지만 정확도는 떨어진다.</p><p id="2e8f">이 문제를 해결하기 위해 <a href="https://en.wikipedia.org/wiki/Quadtree" rel="noopener ugc nofollow" target="_blank">quadtrees</a> 를 사용한다. 간단히 요약하면 셀의 크기를 고정하지 않고 공간 데이터를 모두 채울 때 까지 셀을 작은 단위로 계속 쪼개는 것이다. 아래 그림을 보면 이해가 쉽다.</p><figure></figure><p id="f96a">셀을 quadtree 구조로 분리함으로서 셀 크기에 대한 절충점은 얼추 찾은 듯 했다. 이렇게 분리된 셀을 기존 inverted-index 에 적용하면 기존 ES 의 지리공간 데이터 인덱싱은 어느정도 완성된다.</p><p id="142f">하지만 위 방식도 완전하지는 못하다. 셀의 개수는 여전히 많으며 인덱스 크기는 비효율적으로 크다. 아래 간단한 그림을 보자. 점 8개로 이루어진 polygon 이다. 저 간단한 polygon 하나에 셀이 1,105,889 개가 필요하다.</p><figure></figure><p id="29ec">이 비효율을 어떻게 개선할 수 없을까?</p><h2 id="2786">BKD tree</h2><p id="889d"><a href="https://issues.apache.org/jira/browse/LUCENE-8396" rel="noopener ugc nofollow" target="_blank">기존 사각형 형태가 아닌 삼각형의 형태의 셀은 어떨까?</a></p></div><div><p id="df24">컴퓨터 그래픽 업계에서 어떻게 고해상도의 그래픽 객체를 효율적으로 렌더링 했을까. ES 가 고민하던 문제는 그렇게 새롭고 신선한 문제가 아니었다. <a href="https://en.wikipedia.org/wiki/Polygon_triangulation" rel="noopener ugc nofollow" target="_blank">이미 다른 업계에서 충분히 고민했던 문제였고 ES 는 여기서 힌트를 얻었다.</a> 결론적으로, ES 는 Ear Clipping 알고리즘을 사용하여 공간 데이터를 삼각형으로 분해하는 방법을 채택했다.</p><figure></figure><p id="7f02">이 방식을 사용하면, 앞서 봤던 단순한 폴리곤을 7ms 내에 단 8개의 삼각형으로 분해할 수 있었다. 이는 기존 quadtree 방식이 1,105,889 개를 생성했던 걸 생각하면 엄청난 발전이다. 심지어 벡터 공간에 남아있기 때문에 원래의 geometry 정확도를 유지할 수 있으며, 해상도에 대한 걱정도 사라진다.</p><p id="bb47">삼각형 형태의 셀을 채택해서 데이터를 효율적으로 토큰화 한 것 까지는 좋다. 이제 이걸 어떻게 인덱싱 할 것인가? 기존의 prefix tree 기반의 inverted-index 구조는 사용할 수 없다.</p><p id="95a2">여기서 ES는 기존에 IP, date 타입의 인덱싱에 사용했던 BKD tree 를 조금 변형해서 공간 데이터 인덱싱에 사용하기로 한다.</p><p id="6455">BKD tree 에 대한 내용은 2편에서 계속.</p></div></div>

Stories by allocProc on Medium

jaeyeong

일반적으로 공간 데이터 저장을 위한 선택지는 PostgreSQL(PostGIS) 아니면 MongoDB 가 무난한 것으로 알려져있다. 나 또한 당연히 그렇게 알고 있었고, 공간 데이터 저장용으로 이 둘만 적당히 성능 비교 해보고 더 나은쪽으로 선택하려 했다. 하지만 왜인지 로그만 저장하고 있던 Elasticsearch(이하 ES) 가 눈에 띄었고 아니나 다를까 ES 도 공간 데이터를 저장할 수 있다고 한다. 당장 이 셋의 성능을 비교해보았고 의외로 ES 가 공간 데이터 쿼리 성능 측면에서 앞선 둘에 밀리지 않았다. 전문검색도 빠르면서 공간 데이터 처리까지 빠르다니 참 다재다능한 친구다.
PostGIS, MongoDB 가 지리공간 데이터를 어떻게 저장하고 처리하는지는 잘 알려져있다. 전자는 r-tree, 후자는 구글 s2 geometry library 를 기반으로 빠르고 정확한 공간 데이터 인덱싱을 구현했다. 이는 각 DB 의 공식 문서에 잘 설명되어 있고 많은 블로그가 자세히 풀어서 설명해주기도 한다. 하지만 ES 의 공간 데이터 처리 방식에 대해 설명한 글은 거의 찾아 볼 수 없었다. 그래서!
이번 글에서는 ES 가 지리공간 데이터를 어떻게 처리하길래 이렇게 빠른 성능을 낼 수 있는지 그 기저에 대해 간단히 알아보고자 한다.
Elasticsearch 는 지리공간 데이터 타입을 지원한다.
ES 는 아파치 Lucene 기반 전문검색 엔진이다. 그래서 애플리케이션 로그를 수집하고 분석하거나 검색어 자동완성과 같은 텍스트 검색을 위한 용도로 주로 사용한다. 하지만 ES 가 기본적으로 지원하는 데이터 타입은 굉장히 다양하고 지리공간 데이터도 그 중 하나다.
그리고 위 같은 지리공간 데이터 타입을 위해 제공되는 연산도 굉장히 다양하다. (물론 PostGIS 같은 특화 DB 보단 조금 적다.)
이쯤에서 문득 궁금해졌다. ES 가 텍스트 전문검색을 구현한 방식은 간단히 요약하면 텍스트 데이터를 토큰화하여 역인덱스(inverted-index) 구조로 만들고 각 토큰이 어떤 문서에 존재하는지 매핑 구조를 저장하여 여기서부터 검색하는 것이다. 그럼 지리공간 데이터는 어떻게 인덱싱 했을까? 텍스트 데이터처럼 역인덱스 구조로 저장했을까? 아니면 기존의 지리공간 DB 들 처럼 R-tree 나 S2 library 를 이용했을까? ES 라면 뭔가 다르게 구현했을지도.
Elasticsearch 는 공간 데이터를 어떻게 인덱싱할까
Elasticsearch 가 빠르고 정확한 지리공간 데이터 검색을 지원하기 위해 채택한 인덱싱 방식은 여러번의 변화를 거쳤는데, 이번 글에서는 하나의 큰 변화를 기점으로 구버전의 인덱싱 방식과 신버전의 인덱싱 방식 두가지를 다루고자 한다.
inverted-index (quadTree)
ES 는 기존 텍스트 검색을 위해 사용되던 inverted-index 구조를 공간 데이터 검색에도 그대로 활용했다. 공간 데이터를 어떻게 역인덱스 구조에 넣지? 싶을수도 있다. inverted-index 는 텍스트를 검색 가능한 작은 토큰 단위로 쪼개어 저장하는 방식이다. 공간 데이터도 똑같다. 하나의 큰 공간 데이터(예를 들면 polygon)를 작은 사각형 단위로 쪼개어 저장하는 것이다. 이 쪼개진 단위를 셀(cell)이라고 부른다. 그리고 이렇게 공간 데이터를 셀 단위로 쪼개는 방식을 **rasterization** 이라고 부른다. 특정 위치가 어느 polygon 에 있는지 알고 싶다고 하자. 그 위치가 어느 polygon 에 속해있는지는 몰라도 어떤 셀에 있는지는 간단히 알 수 있다. 앞서 우린 모든 셀을 inverted-index 구조에 저장했으니 해당 셀이 어떤 poylgon 에 속해있는지도알 수 있다. 대략 이런 방식으로 ES 는 공간 데이터 인덱싱을 구현했다. 이 방식의 큰 문제는 셀을 어떤 크기로 저장해야하는가? 이다.
위 그럼처럼 셀을 작게 지정하면 정확도는 증가하지만 인덱스 크기와 퍼포먼스를 희생해야하고 셀을 크게 지정하면 퍼포먼스는 좋아지지만 정확도는 떨어진다.
이 문제를 해결하기 위해 quadtrees 를 사용한다. 간단히 요약하면 셀의 크기를 고정하지 않고 공간 데이터를 모두 채울 때 까지 셀을 작은 단위로 계속 쪼개는 것이다. 아래 그림을 보면 이해가 쉽다.
셀을 quadtree 구조로 분리함으로서 셀 크기에 대한 절충점은 얼추 찾은 듯 했다. 이렇게 분리된 셀을 기존 inverted-index 에 적용하면 기존 ES 의 지리공간 데이터 인덱싱은 어느정도 완성된다.
하지만 위 방식도 완전하지는 못하다. 셀의 개수는 여전히 많으며 인덱스 크기는 비효율적으로 크다. 아래 간단한 그림을 보자. 점 8개로 이루어진 polygon 이다. 저 간단한 polygon 하나에 셀이 1,105,889 개가 필요하다.
이 비효율을 어떻게 개선할 수 없을까?
BKD tree
기존 사각형 형태가 아닌 삼각형의 형태의 셀은 어떨까?
컴퓨터 그래픽 업계에서 어떻게 고해상도의 그래픽 객체를 효율적으로 렌더링 했을까. ES 가 고민하던 문제는 그렇게 새롭고 신선한 문제가 아니었다. 이미 다른 업계에서 충분히 고민했던 문제였고 ES 는 여기서 힌트를 얻었다. 결론적으로, ES 는 Ear Clipping 알고리즘을 사용하여 공간 데이터를 삼각형으로 분해하는 방법을 채택했다.
이 방식을 사용하면, 앞서 봤던 단순한 폴리곤을 7ms 내에 단 8개의 삼각형으로 분해할 수 있었다. 이는 기존 quadtree 방식이 1,105,889 개를 생성했던 걸 생각하면 엄청난 발전이다. 심지어 벡터 공간에 남아있기 때문에 원래의 geometry 정확도를 유지할 수 있으며, 해상도에 대한 걱정도 사라진다.
삼각형 형태의 셀을 채택해서 데이터를 효율적으로 토큰화 한 것 까지는 좋다. 이제 이걸 어떻게 인덱싱 할 것인가? 기존의 prefix tree 기반의 inverted-index 구조는 사용할 수 없다.
여기서 ES는 기존에 IP, date 타입의 인덱싱에 사용했던 BKD tree 를 조금 변형해서 공간 데이터 인덱싱에 사용하기로 한다.
BKD tree 에 대한 내용은 2편에서 계속.
reference
https://www.elastic.co/kr/blog/bkd-backed-geo-shapes-in-elasticsearch-precision-efficiency-speed

Elasticsearch 는 어떻게 위치 검색도 빠를까

댓글