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

Photo by GeoJango Maps on Unsplash

이전 글에서 Elasticsearch 는 폴리곤의 인덱싱에 있어서 사각형으로 쪼개는 기존의 rasterization 방식이 아닌 삼각형으로 쪼개는 triagular tessellation 방식으로 전환했다는 것 까지는 이야기했다. 이 개선으로 폴리곤을 인덱싱하는데 필요한 term 갯수가 획기적으로 줄었다는 것도 알았다. 그런데 삼각형을 어떻게 (그것도 효율적으로) 인덱싱할 수 있을까?

KD-tree

먼저 kd-tree 에 대해 짚고 넘어가야한다. ES 에서 triagular tessellation 을 거친 폴리곤의 삼각형 term 들을 인덱싱하기 위한 핵심 자료구조이기 때문이다.

kd-tree 는 내가 이해한게 맞다면 본질적으로 b-tree 와 같다. 사실상 “다차원 b-tree” 정도로 이름붙여도 되지 않을까 싶을 정도. (물론 balanced 하지는 않다) 먼저 2차원 kd-tree 의 간단한 예시를 먼저 살펴보자.

ref: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf

루트 노드가 x축을 기준으로 공간을 좌우로 나누고, 다음 레벨의 노드들은 y축을 기준으로 상하로 나누는 식으로 차원을 번갈아 가며 공간을 이등분한다. 우선 위 처럼 일곱개의 point 를 트리에 하나씩 집어넣는다고 생각해보자.

root node 바로 하위 depth 는 x 축 기준으로 나뉜다. 그래서 (5,25) 는 left node, (70,70) 는 right node 로 삽입 된 것이다. 다시 반대로 (5,25) 하위는 y 축 기준으로 나뉘기 때문에 (10,12) 는 left node 로 삽입되었다. insert 는 이런식으로 쭉 이어진다고 보면 된다. 노드 구조는 “데이터 포인트 + 분할 기준축 정보 + 좌/우 자식 포인터”로 구성된다고 보면 된다.

코드로는 아래처럼 표현해볼 수 있겠다.

insert(Point x, KDNode t, int cd) {
 if t == null
  t = new KDNode(x)
 else if (x == t.data)
  // error! duplicate
 else if (x[cd] < t.data[cd])
  t.left = insert(x, t.left, (cd+1) % DIM)
 else
  t.right = insert(x, t.right, (cd+1) % DIM)
 return t
}

kd-tree 는 보통 다차원 범위 검색(range search)과 최근접 이웃 검색(nearest neighbor search)에 자주 사용된다고 한다.

최근접 이웃 검색의 경우 질의 좌표와 각 노드 간 거리를 비교하면서 가지치기를 수행한다. 먼저 한쪽 서브트리로 내려가 최근접 후보를 찾은 뒤, 분할 초평면과의 거리 등을 이용해 다른 서브트리에 더 가까운 점이 있을 가능성을 판단한다.

특정 점과 가장 가까운 점을 찾는 시나리오를 생각해보면 그냥 b-tree 탐색하듯이 계속 밑으로 내려가면서 leaf-node 만 찾으면 되는게 아닌가 싶을 수 있지만 적당히 가까운 점은 찾을 수 있을지 몰라도 가장 가까운 점은 찾지 못할 수 있다.

위 사례 처럼 (8,7) 까지 탐색한 이후 다시 이전 노드로 돌아가 탐색하는 절차가 필요하다. 그래야 (10,2)를 찾을 수 있다.

BKD-tree

하지만 ES 에서 폴리곤 데이터 인덱싱에 앞서 설명한 kd-tree 를 사용하진 않고 이름이 살짝 다른 bkd-tree 라는 자료구조를 사용한다.

bkd-tree 란 kd-tree 의 변형으로 Block KD-tree 의 약자이다. (알파벳이 3개로 늘어나니 부르기가 참 힘들다) 디스크 I/O 효율에 특화된 KD-tree라고 볼 수 있다. 기본 개념은 KD-tree와 유사하게 다차원 공간을 재귀적으로 분할하지만, 분할 전략과 노드 구성에 몇 가지 차이가 있다.

• 기본적으로 in-memory 가 아닌 disk 기반 명령에 특화되어있다. 그래서 상대적으로 큰 데이터셋을 다루기에 용이하다.
• 기존 kd-tree는 보통 각 리프 노드가 하나의 포인트만 포함하지만, bkd-tree에서는 한 리프 노드가 여러 포인트를 담는 블록으로 구성된다.
  - 트리를 구성할 때 각 분할 셀(cell)에 포함된 포인트 수가 사전 지정한 임계값(예: 1024개) 이하가 되면 더 이상 분할하지 않고 그 셀의 모든 포인트를 하나의 리프 블록으로 저장하는 방식
• kd-tree 보다 복잡한 분할 정책을 사용할 수 있다. (kd-tree 는 일반적으로 중앙값(median)이나 순환되는 차원을 기준으로 공간을 분할)
  - 그래서 kd-tree 보다 balanced 한 트리를 만들 수 있음.
• 한번 생성 후 불변!
  - 트리가 한번 disk 에 쓰여진 후엔 별도 변경을 하지 않음.
  - Lucene의 세그먼트가 write-once로 만들어진 후 갱신되지 않는 설계와 부합.
  - 새로운 데이터가 생기면 새 세그먼트(BKD-tree)가 만들어지고, 삭제나 갱신은 나중에 세그먼트 머지 과정에서 반영.

(혹시라도 bkd-tree 에 대해 깊이있게 공부해보고 싶다면 아래 논문을 읽어보자.)
https://users.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf

Selective Indexing

이제 bkd-tree 가 어떤 자료구조인지 까지는 알았다. 이제 우리의 원래 궁금증을 해결해보자.

어떻게 삼각형 단위 term 들을 인덱싱 할 것인가?

한줄로 요약하면 “7차원의 bkd-tree 구조에 저장한다” 이다. 이게 무슨 소리인가 하면, 7차원 중 앞의 4차원을 인덱싱을 위해 사용하고 남은 3차원을 삼각형 구조를 나타내는데 사용한다는 뜻이다. 이게 차원이라는 단어를 사용하니 뭔가 더 어렵게 느껴지는데 트리의 각 노드가 7개 필드를 가지고 노드 별로 4개 필드는 인덱싱에만 쓰고 3개 필드는 삼각형 복원에만 쓴다는 의미이다.

• 인덱스 차원: 각 삼각형의 경계박스 4개 값이 색인 트리(BKD-tree)의 분할 기준으로 사용. 즉, 이 4개의 값에 따라 삼각형들이 BKD-tree 내부에서 정렬되고 분할됨.
• 데이터 차원: 추가로 삼각형의 실제 꼭짓점 정보를 복원하기 위한 부가 데이터(예: 삼각형의 나머지 3개 차원)가 리프 노드에 저장. 이 데이터는 삼각형을 재구성하는 데 필요한 정보를 담고 있어, 정확한 공간 관계를 판별할 때 사용.

ES 공식 블로그에 있는 표를 보면 이해가 더 쉽다.

• 삼각형의 최소경계사각형(minimum bounding rectangle, MBR)을 구해서 인덱싱에 사용한다.
• 우리가 저장한건 사각형이 아니라 삼각형이니 MBR 과 더불어 정보를 추가 저장하여 삼각형 복원에 사용한다.

결과적으로, 색인 단계에서는 기존 사각형 인덱싱과 유사하게 동작하되, 각 term(삼각형)이 갖는 부가 정보를 통해 최종적으로 원본 도형을 정확하게 재구성할 수 있다. 이 방식에 selective indexing 이란 이름을 붙였는데, 나름 삼각형을 어떻게 최대한 효율적으로 인덱싱할지 깊게 고민하고 내린 결론인 듯 하다.

이 밖에도 Quantization 방식으로 인덱스 하나의 차이를 최대한 줄이려는 노력도 한 것으로 보인다.

이제 우리는 ES 가 어떻게 폴리곤 데이터를 효율적으로 저장하고 인덱싱 했는지 이번 글과 앞선 글로 배울 수 있었다.

• ES 는 기존 텍스트 검색을 위해 사용되던 inverted-index 구조를 공간 데이터 검색에도 그대로 활용했다.
• 이를 위해선 공간 데이터를 사각형 셀 단위로 쪼개는 rasterisation 방식이 사용되었으나 굉장히 비효율적이었다.
• 삼각형 단위로 쪼개는 triagular tessellation 방식으로 변경하여 인덱스 크기를 획기적으로 줄였다.
• BKD-tree 자료구조와 Selective Indexing 으로 삼각형 단위 term 을 효율적으로 저장, 검색할 수 있게 되었다.

요약하면 위와 같으나 사실 정말 많은 내용이 생략되었고 키워드 하나 하나를 정말 겉핥기 식으로 밖에 다루지 못했다. 추후엔 이 각각의 개념들에 대해서만 깊게 다루는 글을 써봐도 좋을 듯 하다.

이번 글을 쓰면서 Elasticsearch 공식 블로그를 포함하여 정말 좋은 아티클을 많이 찾았는데, 저 말고 다른 분들도 꼭 보셨으면 좋겠다. 아마 내가 쓴 이 글을 찾았고 스크롤을 내려서 여기까지 읽었을 정도의 독자 라면 아래 글들도 정말 재밌게 읽으실 듯 하다. (내 누추한 글을 읽느라 짜증나고 피로해졌을 독자님들 눈을 아래의 예쁜 글들로 정화하셨으면 좋겠다.)

• https://www.elastic.co/blog/bkd-backed-geo-shapes-in-elasticsearch-precision-efficiency-speed
• https://www.elastic.co/blog/lucene-points-6-0https://orama.com/blog/bkd-trees-explained
• https://orama.com/blog/bkd-trees-explained
• https://www.cs.cornell.edu/courses/cs4780/2022sp/notes/LectureNotes19.html#:~:text=,space