[자료구조] LSM(Log-Structured Merge-Tree) 트리

우리팀에 같이 있는 Kenny가 추천해준 책(데이터 중심 애플리케이션 설계)을 보면서 유용한 정보를 알게 되어 정리할 겸 작성한다.

 

데이터 저장과 관련해서 LSM 트리와 B 트리 라는 구조가 나온다.

오늘은 LSM 트리에 대해 알아보도록 한다. 

LSM 트리(Log-Structured Merge-Tree)

현재 우리팀에서 사용하고 있는 ElasticSearch를 사용하면서 알게 된 내용이 있었는데 그것은 바로 데이터를 세그먼트라는 단위의 파일로 관리를 하고 있는 것이였다. 세그먼트 파일은 일정 시간 마다 백그라운드로 Merge라는 작업을 통해 작게 조각 나있는 조각들을 합치고 있는데 바로 이 개념이 LSM 트리였다. 여기서는 Merge가 아니라 ①컴팩션이라고 부른다. (실은 ElasticSearch에서 사용하는게 아니라 Lucene에서 사용한다.)

컴팩션 과정

 

LSM 트리에서도 데이터베이스에 존재하지 않는 키를 찾는 경우 느릴 수 있다. 그 이유는 멤테이블(인메모리 트리)을 확인한 다음 키가 존재하지 않는다는 사실을 확인하기 전에는 가장 오래된 세그먼트까지 거슬러 올라가야 하기 때문이다(디스크에서 읽기를 해야 할 수 있다). 이런 종류의 접근을 최적화하기 위해 저장소 엔진은 보통 블룸 필터(Bloom filter)를 추가적으로 사용한다. (블룸 필터는 집합 내용을 근사한 (approximating) 메모리 효율적 데이터 구조다. 블룸 필터는 키가 데이터베이스에 존재하지 않음을 알려주므로 존재하지 않는 키를 위한 불필요한 디스크 읽기를 많이 절약할 수 있다.)

 

또한 SS테이블을 압축하고 병합하는 순서와 시기를 결정하는 다양한 전략이 있다. 가장 일반적으로 선택하는 전략은 크기 계층(szie-tiered)과 레벨 컴팩션(leveled compaction)이다. 사이즈 계층 컴팩션은 상대적으로 좀 더 새롭고 작은 SS테이블을 상대적으로 오래 됐고 큰 SS테이블에 연이어 병합하며 레벨 컴팩션은 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 "레벨"로 이동하기 때문에 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용하게 한다.

 

물론 여러 중요한 세부 사항이 있지만 LSM 트리의 기본 개념은 간단하고 효과적이다. LSM 트리의 기본 개념은 백그라운드에서 연쇄적으로 SS테이블(Sorted String Table)을 지속적으로 병합하는 것이다. 그로 인해 사용가능한 데이터를 항상 최신 상태로 유지하고 필요 없는 데이터(오래 된 세그먼트 파일들)은 지속적으로 삭제를 하여 Disk 관점에서도 사이즈가 계속 커지지 않고 적정 수준에서 유지가 된다. 

그리고 항상 새로운 데이터를 Append하기 때문에 매우 높은 쓰기 처리량을 보장 할 수 있다. 

 

참고 문서

• 데이터 중심 애플리케이션 설계