[Index]검색엔진에서의 SS테이블/LSM트리인덱스 활용(1)

Intro

몇 달전에 "데이터 중심 어플리케이션" 책을 읽다가 CH 03에서 등장하는 Index(색인)개념에서 책을 아무리 읽어도 도저히 이해가 가지 않아서 책을 더 읽는 것을 멈추고 책에 등장하는 인덱스에 대해서 더 공부를 했었다.

 

 

기본적으로 해시나 B+Tree에 대해서는, 인덱스를 공부할 때나 평소에 들어본 개념이고, 알고리즘 자체도 익숙한 알고리즘이라서 이해가 쉬웠다. 그러나  SS테이블와 LSM트리에 대한 개념은 책에서 처음 접했을 때 너무 생소했어서 이해하는데 시간이 꽤나 걸렸던 기억이 난다. 

 

그리고 얼마 전 인덱스 개념에 대해서 복습을 하려고 당시 공부한 글을 살펴보는데, 이해가 더 되는 부분이 있는 반면, 이해가 잘 되지 않는 부분이 생겼고 SS테이블/LSM트리의 개념보다는 이해가 되지 않는 부분을 중심으로 좀 더 공부해야겠다고 생각했다.

 

내가 의문이 생겼던 부분은 "LSM트리에서 SS테이블 방식을 활용한 인덱스는 Elasticsearch나 solr같은 전문 검색엔진에서 활용된다"는 부분이었다.

내가 인덱스를 공부할 때 이해한 바로는 SS테이블/LSM트리를 활용한 인덱스는 기존 B+tree 방식이 지니는 쓰기 작업에서의 비효율성을 극복하기 위해 등장하였고, 어느정도 읽기 작업에 대한 효율성을 포기하고 쓰기작업에서의 효율성을 취하기 위해 등장하고/ 활용되는 인덱스 방식이라는 것이었다.

 

내가 해당 인덱스 방식에 대해 잘못 이해하고 있는 것일까? 아니면 아예 전문검색엔진에 대해서 내가 잘못 이해하고 있던 것일까? 

즉 1) SS테이블과 LSM트리에 대해서 좀 더 정리하는 것이 필요할 것이고 2) 해당 인덱스 방식을 활용하고 있는 전문 검색 엔진에 대해서 정리하는 것이 필요하다 생각했다. 

 

따라서 이번 글은 1) SS테이블과 LSM트리에 대해서 좀 더 정리하는 글이다.

 

SS테이블/LSM트리 인덱스의 등장

해당 인덱스 방식에 대해서는 이미 블로그에서 정리를 해두었으므로, 해당 링크를 참고하면된다.

이번 글에서는 해당 인덱스의 개념 자체는 핵심이 아니므로 간단하게 정리하고 요약만 해보려 한다.

 

우선 해시색인이나 B트리방식 외의 인덱스를 고려하게된 이유는 무엇일까?

이는 데이터를 점점 추가할 때마다 메모리 소요가 커져버리는 문제가 발생하기 시작했다. 즉 데이터의 추가에 따른 쓰기 작업은 불가피하므로 데이터베이스 내의 인덱스 알고리즘 방식도 이를 고려해야 했다.

 

해결책 1. Linked List

Log가 Linked List 기반으로 구현된 개념이며, 이 말인 즉슨 해당 자료구조는 순차쓰기를 지원하여 쓰기 작업이 O(1)으로 최적화된다.

그러나 읽기 작업이 O(N)으로 비효율적이다.

 

해결책 2. Sorted Array

이에 따라 등장한 해결책이 Sorted Array를 결합하는 방식이다. 

당연히 정렬되어있으니 읽기속도를 O(logN)까지 향상시킬 수 있으나, 쓰기속도가 O(logN)으로 감소하게 된다.

 

해결책 3. SS테이블 + LSM트리

이러한 여러 해결책들이 제시되면서 해당 알고리즘을 활용한 인덱스 방식이 등장하게 되었다.

 

인덱스를 우선은 Log 형태로 쌓다가(쓰기 최적화), 어느정도 메모리 임계점에 다다르면 Sorted String Array로 정렬하여 기존 세그먼트와 병합정렬해준다. 이 때 정렬하는 과정에서 속도가 지연된다. 

 

그러나 이 또한, 병합하는 과정에서 O(NlogN)이라는 큰 시간이 소요되어 버리면서, 실제로 해당 병합 과정 도중에 데이터베이스 내에 쓰기와 읽기 연산 작업에도 영향을 주는 경우도 발생하게 되는 문제가 생겼다.

 

해결책 4. 

이에 따라 기존 세그먼트와 신규 세그먼트는 병합하지 않고, 각 세그먼트내에서만 정렬하고 각 세그먼트끼리는 그냥 합치는 방식이 등장했다. 

물론 해당 방식으로 인해 읽기 작업에서 시간이 많이 소요되게 되었으며, 결국은 모든 세그먼트들이 합쳐지다가 메모리 임계점에 다다르면 전체를 병합정렬해야 하는 경우가 발생하기는 했다.

 

병합정렬은 결국 거쳐야하는 과정이었고 너무 많은 리소스를 쓰지 않으면서도 적절하게 병합하기 위해서 two pointer 방식으로 병합 후 정렬하는 방식도 고려하게 되었다. 

개인적으로 해당 해결책은 그냥 조삼모사이지 않은가? 하는 생각도 들긴 들었다. 
물론 해당 방식을 통해 세그먼트끼리 병합정렬을 해야하는 수는 줄어서 쓰기 작업에 대한 리소스가 약간 줄었다고 볼 수도 있을거 같다.

 

LSM트리의 기본 구조

 

위의 그림을 참고하여 설명하자면, LSM트리는 실제로 0~L까지의 다양한 레벨이 존재한다.

간단하게 설명할 때는 임시 세그먼트(메모리 기반) -> 기존 세그먼트(디스크)로 설명했지만 실제로 데이터가 write되고, 병합되고 정렬되는 과정에 다양한 레벨이 존재하게 된다.

 

기본적으로 0번 레벨은 메모리에 위치하고, 1~L번 레벨은 디스크에 존재한다. 0번 레벨에 위치한 buffer는 데이터가 저장되며, buffer의 크기가 가득 차면 그 때부터 한 칸씩 아래 레벨로 flush된다.

 

해당 데이터를 아래의 레벨로 내려줄 때 내부에서 정렬된 상태를 유지하여야 하기 때문에 원래 아래 레벨에서 가지고 있던 데이터들과 합쳐 다시 한 번 정렬을 하게 된다. 이 과정에서 merge sort 방식이 들어가기 때문에, LSM Tree라는 이름이 붙게 되었다.

 

LSM트리에 새로운 데이터가 insert될경우, 작동하는 방식에 대한 예시가 위의 그림이다.

13이라는 데이터가 추가가 되면 해당 세그먼트가 가득차게 되고, 그다음 레벨로 내려가게 된다. 그리고 그 다음 레벨이 가득 찬 경우에는 바로 그 다음 레벨로 또 내려 가게 된다. 

 

최종적으로 가장 아래 쪽의 형태를 띄게 된다. 

 

읽기 작업을 해야 하는경우, 레벨이 낮은 단계부터 탐색을 하게 되며 이에 따라 읽기 작업은 비교적(비교 대상은 B트리) 느리다.

이에 대한 대안으로 각 레벨에 bloom filter을 유지하게 된다.

 

bloom filter는 원소가 집합에 속하는지 여부를 확률적으로 알아낼 수 있는 자료구조로, Bloom filter를 통해 데이터가 없다고 판단되었을 경우, 실제로도 찾으려는 데이터가 존재하지 않는다는 것을 보장할 수 있기 때문에 추가적인 extra I/O를 줄일 수 있다.

다만, 실제로 찾으려는 데이터가 존재하지 않음에도 bloom filter에서는 데이터가 없다고 판단하지 않는, False positive가 발생할 수도 있다.

 

SS테이블/LSM 트리의 성능적 특징

LSM트리는 메모리 임계점에 다다르기 이전에 데이터가 쌓이는 임시 세그먼트의 경우 memtable에 메모리로 저장될지라도, 기본적으로 Disk기반의 Sequantial Read/Write 방식을 활용한다.

이러한 방식의 속도는 Memory 의 Random access에 비해서도 10배 가까이 빠른 성능을 내므로, LSM tree 는 B+ tree에 비해 더 높은 write workloads를 처리할 수 있다.

Random write가 발생하는 b tree와 다르게, SSTable의 write는 항상 sequantial하기 때문이다.

 

B+ Tree는 경험적으로 높은 read workload를 처리할 수 있다고 알려져있으며 높은 write workload에서도 LSM Tree에 비해 처리 속도는 느리지만 안정적이다.

 

그러나 앞에서도 계속 이야기 했듯이 LSM트리 방식은 Random Read 또는 역 탐색에 대해서는 Write 작업에 비해 매우 낮은 성능을 보인다.

 

결론

결국 LSM트리 방식은 Disk 기반의 sequantial Read/Write 방식을 활용함으로써 높은 write workload를 처리할 수 있으나, read workload에서는 낮은 성능을 보인다고 볼 수 있다.

 

그러나 여전히 "Bigtable paper에 기반한 Elasticsearch, Hbase, Cassandra, Riak, rocksdb 같은 최근 DB 들/ 전문 검색엔진들은 LSM tree를 사용하고 있다."는 문장은 이해가 되지 않는다.

 

이건 아무래도 ElasticSearch, solr 같은 전문 검색 엔진에 대한 이해도가 없기 때문이라는 생각이 들었다..😂

시리즈로 글을 정리할 의도는 아니었는데, 다음 글은 LSM트리방식을 활용한다는 맥락 하에 전문 검색엔진의 구조나 특징에 대해서 정리해보아야 겠다.

 

 

Reference

• LSM트리에 대해서 
• LSM 트리에 대해서 (2)
• B트리와 LSM트리
• LSM트리에 대해서 (3)