LSM 트리의 배경, 기본 알고리즘, 컴팩션(기본/레벨드) 방식과 읽기·쓰기 성능 트레이드오프, 그리고 관련 확장 연구와 파일 시스템 관점의 보충 설명을 정리한다.
(또한 Hacker News의 댓글도 참고)
Google이 ‘Big Table’ 논문을 발표한 지도 어느덧 거의 10년이 되어 간다. 그 논문의 여러 멋진 점 중 하나는 그것이 사용하는 파일 구성 방식이다. 이 접근은 1996년에 나온 이 논문을 따라 좀 더 일반적으로 로그 구조 병합 트리(Log Structured Merge Tree)로 알려져 있다. 다만 그 논문에 기술된 알고리즘은 실제 환경에서 쓰이는 대부분의 구현과는 꽤 크게 다르다.
LSM은 이제 여러 제품에서 주요 파일 구성 전략으로 사용된다. HBase, Cassandra, LevelDB, SQLite는 물론이고, MongoDB 3.0도 Wired Tiger를 인수한 뒤 선택 가능한 LSM 엔진을 제공한다.
LSM 트리가 흥미로운 이유는 수십 년 동안 이 분야를 지배해 온 이진 트리 스타일의 파일 구성 방식에서 벗어나 있기 때문이다. LSM은 처음 보면 거의 직관에 반하는 듯 보이지만, 현대의 메모리 중심 시스템에서 파일이 어떻게 동작하는지 면밀히 고려하면 비로소 이해가 된다.
요약하면 LSM 트리는 전통적인 B+ 트리나 ISAM 접근에 비해 더 나은 쓰기 처리량을 제공하도록 설계되었다. 이를 위해 흩어진 위치에 대한 in-place 업데이트(update-in-place) 작업을 수행할 필요를 없앤다.
그렇다면 왜 이것이 좋은 생각일까? 핵심에는 ‘디스크는 랜덤 작업에는 느리지만 순차 접근에는 빠르다’는 오래된 문제가 있다. 이 두 접근 방식 사이에는, 디스크가 자기식이든 SSD든, 심지어(다소 덜하긴 하지만) 주 메모리이든 간에 큰 격차가 존재한다.
이 ACM 보고서의 수치(여기/여기)는 그 점을 잘 보여준다. 그 그래프는 다소 직관에 반하게도, 순차 디스크 접근이 주 메모리를 랜덤으로 접근하는 것보다 더 빠르다는 것을 보여준다. 더 중요한 점은, 자기 디스크든 SSD든 간에 디스크에 대한 순차 접근이 랜덤 IO보다 최소 세 자릿수(10^3) 이상 빠르다는 사실이다. 이는 랜덤 작업을 피해야 한다는 뜻이다. 순차 접근은 그에 맞게 설계할 가치가 충분하다.
이 점을 염두에 두고 간단한 사고 실험을 해보자. 우리가 쓰기 처리량에 관심이 있다면 어떤 방법이 최선일까? 좋은 출발점은 파일 끝에 데이터를 단순히 덧붙이는 것이다. 이런 접근은 흔히 로깅(logging), 저널링(journaling) 또는 힙 파일(heap file)이라 불리는데, 완전히 순차적이므로 이론적인 디스크 속도에 근접한 매우 빠른 쓰기 성능을 제공한다(일반적으로 드라이브당 200~300MB/s).
단순성과 성능이라는 두 장점 덕분에 로그/저널 기반 접근은 많은 빅데이터 도구에서 당연히 인기를 끌어왔다. 하지만 명백한 단점도 있다. 로그에서 임의의 데이터를 읽는 일은 쓰기보다 훨씬 많은 시간이 들며, 필요한 키를 찾을 때까지 시간 역순으로 스캔해야 한다.
이는 로그가 실제로는 단순한 워크로드에만 적용 가능함을 뜻한다. 예를 들어 대부분의 데이터베이스가 사용하는 write-ahead log처럼 데이터를 전체로 접근하거나, Kafka 같은 단순 메시징 제품처럼 알려진 오프셋으로 접근하는 경우에 해당한다.
따라서 키 기반 접근이나 범위 검색 같은 더 복잡한 읽기 워크로드를 효율적으로 수행하려면 저널만으로는 부족하다. 크게 보면 이를 도울 수 있는 접근은 네 가지다: 이진 검색, 해시, B+, 또는 외부 파일.
이들 접근은 모두 읽기 성능을 크게 개선한다(대부분에서 n->O(log(n))). 하지만 이러한 구조는 질서를 부여하고, 그 질서가 쓰기 성능을 방해한다. 그 과정에서 고속 저널 파일의 장점은 사라진다. 케이크를 가지고 먹기까지는 어렵다는 말이 맞는 듯하다.
여기서 중요한 통찰 하나는 위 네 가지 옵션 모두 데이터에 어떤 형태로든 ‘전체를 관통하는 구조(overarching structure)’를 강제한다는 점이다.
인덱스가 나중에 빠르게 다시 찾을 수 있도록 데이터를 파일 시스템 여기저기에 의도적으로 배치한다. 이 구조 덕분에 탐색이 빨라진다. 하지만 데이터가 쓰일 때도 당연히 그 구조를 지켜야 한다. 이 지점에서 랜덤 디스크 접근이 추가되며 쓰기 성능이 떨어지기 시작한다.
구체적인 문제는 몇 가지가 있다. 각 쓰기마다 IO가 두 번 필요하다. 하나는 페이지를 읽기 위해, 다른 하나는 다시 쓰기 위해서다. 반면 로그/저널 파일은 한 번의 IO로 처리할 수 있었다.
더 나쁜 점은 해시나 B+ 인덱스의 구조 자체를 업데이트해야 한다는 것이다. 이는 파일 시스템의 특정 부분을 갱신하는 것을 의미한다. 이를 update-in-place라고 하며, 느린 랜덤 IO를 필요로 한다. 이 점이 중요하다: 이런 in-place 접근은 파일 시스템을 산탄총처럼 여기저기 흩뿌리며 update-in-place를 수행한다*. 이는 한계가 된다.
흔한 해결책 하나는 (4) 저널에 대한 인덱스를 두되, 인덱스를 메모리에 유지하는 것이다. 예컨대 해시 테이블을 사용해 키를 저널 파일(로그)에서 최신 값의 위치(오프셋)로 매핑한다. 이 접근은 랜덤 IO를 비교적 작은 영역(메모리에 있는 키→오프셋 매핑)으로 격리하므로 꽤 잘 동작한다. 값을 조회할 때는 IO가 한 번만 든다.
반면 확장성의 한계가 있는데, 특히 작은 값이 많을 때 그렇다. 값이 단순한 숫자 같은 것뿐이라면 인덱스가 데이터 파일 자체보다 더 커질 수도 있다. 그럼에도 이 패턴은 Riak부터 Oracle Coherence에 이르기까지 많은 제품이 사용하는, 합리적인 절충안이다.
이제 로그 구조 병합 트리로 넘어가자. LSM은 위 네 가지와 다른 접근을 취한다. 완전히 디스크 중심일 수 있으며 효율을 위해 메모리에 거의 저장하지 않아도 되면서, 단순 저널 파일에 기대하던 많은 쓰기 성능을 유지한다. 단 하나의 단점은 B+Tree와 비교했을 때 읽기 성능이 다소 떨어진다는 점이다.
요컨대 디스크 접근을 가능한 한 순차적으로 만들기 위해 온갖 일을 한다. 여기에는 산탄총식 접근이 없다!
*update-in-place를 요구하지 않는 여러 트리 구조도 존재한다. 가장 널리 알려진 것은 append-only Btree로, copy-on-write 트리라고도 한다. 이들은 쓰기가 발생할 때마다 트리 구조를 파일 끝에 순차적으로 덮어써서 동작한다. 최상위 노드를 포함한 이전 트리 구조의 관련 부분은 고아(orphaned) 상태가 된다. 이 방식으로 update-in-place는 피할 수 있는데, 트리가 시간이 지나며 순차적으로 자기 자신을 재정의하기 때문이다. 다만 대가가 있다. 매 쓰기마다 구조를 다시 쓰는 것은 장황하며 상당한 write amplification을 유발하는데, 이는 그 자체로 단점이다.
개념적으로 기본 LSM 트리는 꽤 단순하다. 하나의 거대한 인덱스 구조(이는 파일 시스템을 산탄총처럼 흩뿌리거나 상당한 write amplification을 추가할 것이다)를 갖는 대신, 쓰기 배치를 여러 개의 더 작은 인덱스 파일 집합에 순차적으로 저장한다. 즉 각 파일은 짧은 시간 구간을 커버하는 변경 배치 하나를 담는다. 각 파일은 나중에 빠르게 검색할 수 있도록 쓰기 전에 정렬된다. 파일은 불변(immutable)이며 결코 업데이트되지 않는다. 새로운 업데이트는 새 파일로 들어간다. 읽기는 모든 파일을 검사한다. 주기적으로 파일을 서로 병합해 파일 수를 줄인다.
좀 더 자세히 보자. 업데이트가 도착하면 먼저 메모리 내 버퍼에 추가되는데, 보통 키 순서를 유지하기 위해 트리(레드-블랙 등)로 유지한다. 이 ‘memtable’은 대부분의 구현에서 복구 목적만을 위해 write-ahead-log로 디스크에도 복제된다. memtable이 가득 차면 정렬된 데이터가 디스크의 새 파일로 플러시된다. 이후 더 많은 쓰기가 들어오면 이 과정이 반복된다. 중요한 점은 파일을 편집하지 않으므로 시스템이 순차 IO만 수행한다는 것이다. 새 엔트리나 수정은 단지 연속된 파일을 만들어낼 뿐이다(위 그림 참조).
따라서 시스템으로 더 많은 데이터가 유입될수록, 불변이며 정렬된 파일이 점점 더 많이 생성된다. 각 파일은 시간 순으로 가까운 변경의 작은 부분집합을 정렬된 상태로 보관한다.
오래된 파일이 업데이트되지 않으므로, 이전 레코드를 대체하는 중복 엔트리(또는 삭제 마커)가 생성된다. 이는 초기에 일정한 중복을 만든다.
주기적으로 시스템은 컴팩션(compaction) 을 수행한다. 컴팩션은 여러 파일을 선택해 하나로 병합하면서, 중복된 업데이트나 삭제를 제거한다(이 동작 방식은 뒤에서 더 설명한다). 이는 앞서 언급한 중복을 없애기 위해서도 중요하지만, 더 중요한 목적은 파일 수가 늘면서 악화되는 읽기 성능을 관리하기 위해서다. 다행히 파일이 정렬되어 있으므로 병합 과정은 꽤 효율적이다.
읽기 요청이 오면 시스템은 먼저 메모리 버퍼(memtable)를 확인한다. 키가 없으면 여러 파일을 최신 것부터 하나씩(역시간 순으로) 검사하여 키를 찾는다. 각 파일은 정렬되어 있어 탐색 가능하다. 그러나 파일 수가 늘수록 각각을 검사해야 하므로 읽기는 점점 느려진다. 이는 문제다.
즉 LSM 트리의 읽기는 in-place 방식의 친척들보다 느리다. 다행히 이 패턴을 충분히 성능 좋게 만드는 몇 가지 트릭이 있다. 가장 흔한 접근은 메모리에 페이지 인덱스를 유지하는 것이다. 이는 목표 키 ‘근처’로 빠르게 이동하게 해 주며, 데이터가 정렬되어 있으므로 그 지점부터 스캔하면 된다. LevelDB, RocksDB 그리고 BigTable은 각 파일 끝에 블록 인덱스를 두고 이를 활용한다. 이는 가변 길이 필드를 허용하고 압축 데이터에 더 적합하므로, 단순 이진 검색보다 더 잘 동작하는 경우가 많다.
파일별 인덱스가 있어도 파일 수가 늘면 읽기 성능은 여전히 저하된다. 이는 주기적으로 파일을 병합함으로써 억제된다. 이런 컴팩션은 파일 수(따라서 읽기 성능)를 허용 가능한 범위에 묶어 둔다.
컴팩션이 있어도 읽기는 여전히 많은 파일을 방문해야 한다. 대부분의 구현은 Bloom filter를 사용해 이를 회피한다. 블룸 필터는 어떤 파일이 특정 키를 포함하는지 여부를(확률적으로) 알아내는 메모리 효율적인 방법이다.
따라서 ‘쓰기’ 관점에서 보면, 모든 쓰기는 배치로 모여 오직 순차적인 덩어리로만 기록된다. 여기에 컴팩션 라운드에 따른 추가적이고 주기적인 IO 페널티가 있다. 반면 읽기는 단일 행을 찾기 위해 많은 파일을 건드릴 가능성이 있다(즉 읽기 시 산탄총). 이것이 알고리즘의 본질이다. 쓰기에서의 랜덤 IO를 읽기에서의 랜덤 IO로 바꾸는 트레이드오프를 하는 셈이다. 블룸 필터 같은 소프트웨어 트릭이나 큰 파일 캐시 같은 하드웨어 트릭으로 읽기 성능을 최적화할 수 있다면, 이 트레이드오프는 합리적이다.
LSM 읽기를 상대적으로 빠르게 유지하려면 파일 수를 관리해 줄이는 것이 중요하다. 따라서 컴팩션을 좀 더 깊게 보자. 이 과정은 세대별 가비지 컬렉션(generational garbage collection)과 약간 비슷하다.
특정 개수의 파일이 생성되면(예: 10행씩 들어 있는 파일 5개), 이들을 병합해 50행(또는 약간 더 적을 수도 있음)의 단일 파일로 만든다.
이후 10행짜리 파일이 더 생성된다. 다섯 번째 파일이 가득 찰 때마다 이들은 50행짜리 파일로 병합된다.
결국 50행짜리 파일이 다섯 개가 된다. 이 시점에서 50행 파일 5개를 병합해 250행짜리 파일 하나를 만든다. 이 과정은 계속되며 점점 더 큰 파일이 만들어진다. 그림을 보라.
이 일반 접근의 앞서 언급한 문제는 생성되는 파일 수가 많다는 점이다. 결과를 읽기 위해(최악의 경우) 모두를 개별적으로 검색해야 한다.
LevelDB, RocksDB, Cassandra 같은 비교적 새로운 구현은 컴팩션에서 크기 기반이 아니라 레벨 기반 접근을 구현함으로써 이 문제를 해결한다. 이는 최악의 경우 읽기에서 참조해야 하는 파일 수를 줄이고, 단일 컴팩션의 상대적 영향을 낮춘다.
이 레벨 기반 접근은 위의 기본 접근에 비해 두 가지 핵심 차이가 있다.
첫 번째 레벨은 특수한 경우로, 위 성질이 성립하지 않는다. 키가 여러 파일에 걸쳐 있을 수 있다.
이러한 변화는 레벨 기반 접근이 컴팩션의 영향을 시간에 걸쳐 분산시키고, 전체 공간 요구량도 줄인다는 뜻이다. 또한 읽기 성능이 더 좋다. 하지만 대부분의 워크로드에서 총 IO는 더 커지므로, 단순한 쓰기 지향 워크로드는 이점을 보지 못할 수도 있다.
LSM 트리는 저널/로그 파일과 전통적인 단일 고정 인덱스(B+ 트리나 해시 인덱스 등) 사이의 중간 지점에 있다. LSM은 더 작은 개별 인덱스 파일 집합을 관리하는 메커니즘을 제공한다.
단일 인덱스가 아니라 여러 인덱스를 관리함으로써, LSM 방식은 B+ 또는 해시 인덱스의 update-in-place에서 발생하는 비싼 랜덤 IO를 빠른 순차 IO로 교환한다.
대신 치르는 비용은, 읽기가 단 하나의 인덱스 파일이 아니라 많은 인덱스 파일을 대상으로 해야 한다는 점이다. 또한 컴팩션을 위한 추가 IO 비용이 있다.
아직도 조금 흐릿하다면 여기와 여기에 다른 좋은 설명이 있다.
그렇다면 LSM 접근은 전통적인 단일 트리 기반 방식보다 정말 더 나을까?
LSM이 비용을 치르긴 하지만 더 나은 쓰기 성능을 가진다는 것은 보았다. LSM에는 다른 이점도 있다. LSM 트리가 생성하는 SSTable(정렬된 파일)은 불변이다. 이는 그 위의 락킹(locking) 시맨틱을 훨씬 단순하게 만든다. 일반적으로 경합되는 자원은 memtable뿐이다. 이는 서로 다른 레벨에서의 변경을 관리하기 위해 복잡한 락킹 메커니즘이 필요한 단일 트리와 대비된다.
결국 질문은 예상 워크로드가 얼마나 쓰기 지향적인가에 달려 있을 것이다. 쓰기 성능이 중요하다면 LSM이 제공하는 절감은 큰 의미가 될 가능성이 높다. 대형 인터넷 기업들은 이 주제에 대해 꽤 결론이 난 듯하다. 예를 들어 Yahoo는 이 논문에서, 이벤트 로그와 모바일 데이터의 유입 증가에 크게 힘입어 워크로드가 읽기 중심에서 읽기-쓰기 혼합으로 꾸준히 이동하고 있다고 보고한다. 하지만 많은 전통적 데이터베이스 제품은 여전히 더 읽기 최적화된 파일 구조를 선호하는 듯하다.
로그 구조 파일 시스템(각주 참고)과 마찬가지로, 핵심 논거는 메모리 가용성 증가에서 나온다. 메모리가 많아지면 운영체제가 제공하는 큰 파일 캐시를 통해 읽기는 자연스럽게 최적화된다. 반면 쓰기 성능은(메모리가 늘어도 그만큼 개선되기 어렵기 때문에) 지배적인 관심사가 된다. 다시 말해 하드웨어 발전은 쓰기보다 읽기 성능에 더 큰 도움을 준다. 따라서 쓰기 최적화된 파일 구조를 선택하는 것이 합리적이다.
실제로 LevelDB나 Cassandra 같은 LSM 구현은 단일 트리 기반 접근보다 더 나은 쓰기 성능을 정기적으로 제공한다(각각 여기와 여기).
LSM 접근을 바탕으로 한 추가 작업도 상당히 있었다. Yahoo는 Pnuts라는 시스템을 개발했는데, LSM과 B 트리를 결합해 더 나은 성능을 보여준다. 다만 이 알고리즘의 공개 구현은 아직 본 적이 없다. IBM과 Google도 비슷한 흐름에서, 다만 다른 경로를 통해 더 최근의 작업을 했다. 또한 전체를 관통하는 구조를 유지하면서도 유사한 성질을 갖는 관련 접근도 있다. 여기에는 Fractal Trees와 Stratified Trees가 포함된다.
물론 이는 대안 중 하나일 뿐이다. 데이터베이스는 미묘하게 다른 엄청나게 다양한 옵션을 사용한다. 점점 더 많은 데이터베이스가 서로 다른 워크로드를 위한 플러그형 엔진을 제공한다. Parquet는 HDFS에서 인기 있는 대안으로, 거의 정반대 방향(컬럼 지향 포맷을 통한 집계 성능)으로 나아간다. MySQL은 여러 엔진(예: Toku의 프랙탈 트리 기반 인덱스)으로 플러그 가능한 스토리지 추상화를 갖고 있다. 이는 MongoDB에서도 사용할 수 있다. Mongo 3.0에는 B+와 LSM 접근을 모두 제공하는 Wired Tiger 엔진과 레거시 엔진이 포함된다. 많은 관계형 데이터베이스는 서로 다른 파일 구성을 활용하는 구성 가능한 인덱스 구조를 갖는다.
사용 중인 하드웨어도 고려할 가치가 있다. FusionIO 같은 비싼 SSD는 랜덤 쓰기 성능이 더 좋다. 이는 update-in-place 접근에 어울린다. 반면 저렴한 SSD와 기계식 드라이브는 LSM에 더 적합하다. LSM은 SSD를 망가뜨릴 정도로(수명을 급격히 줄일 정도로) 작은 랜덤 접근 패턴을 반복하는 일을 피한다**.
LSM에는 비판도 없지 않다. 가장 큰 문제는 GC처럼 수집(컬렉션) 단계와 그것이 귀중한 IO에 미치는 영향이다. 이에 대한 흥미로운 논의가 이 hacker news 스레드에 있다.
따라서 BDB vs. LevelDb, Cassandra vs. MongoDb 같은 데이터 제품을 비교할 때, 상대 성능의 일정 부분을 그들이 사용하는 파일 구조로 환원해 볼 수 있다. 측정 결과도 이 철학을 뒷받침하는 것으로 보인다. 사용하는 시스템이 어떤 성능 트레이드오프를 선택하고 있는지 아는 것은 분명 가치가 있다.
**SSD에서는 각 쓰기마다 전체 512K 블록에 대해 지우기-재쓰기(clear-rewrite) 사이클이 발생한다. 따라서 작은 쓰기가 드라이브에 불균형하게 큰 소모(churn)를 유발할 수 있다. 블록 재쓰기 횟수에 고정된 한계가 있으므로 이는 수명에 큰 영향을 줄 수 있다.
이름과 쓰기 처리량에 대한 초점 외에는, 내가 보기에 LSM과 로그 구조 파일 시스템 사이에는 그리 큰 관련이 없다.
오늘날 사용되는 일반 파일 시스템은 대체로 ‘저널링(journaling)’을 사용한다. 예를 들어 ext3, ext4, HFS 등은 트리 기반 접근이다. 고정 높이의 inode 트리가 디렉터리 구조를 나타내고, 장애 상황에 대비하기 위해 저널이 사용된다. 이러한 구현에서 저널은 논리적(logical)인데, 내부 메타데이터만 저널링된다는 의미다. 이는 성능상의 이유 때문이다.
로그 구조 파일 시스템은 write amplification이 더 적기 때문에 플래시 매체에서 널리 사용된다. 또한 더 일반적인 상황에서 파일 캐싱이 읽기 워크로드를 지배하기 시작하고 쓰기 성능이 더 중요해지면서, 더 많은 주목을 받고 있다.
로그 구조 파일 시스템에서는 데이터가 단 한 번만, 시간 순으로 전진하는 버퍼로 표현되는 저널에 직접 기록된다. 그 버퍼는 중복된 쓰기를 제거하기 위해 주기적으로 가비지 컬렉션된다. LSM과 마찬가지로 로그 구조 파일 시스템은 더 빠르게 쓰지만, 이중 쓰기를 하는 트리 기반 대응물보다 더 느리게 읽는다. 역시 RAM이 많아 파일 캐시를 충분히 공급할 수 있거나, 플래시처럼 update-in-place에 약한 매체를 쓰는 경우라면 이는 받아들일 만하다.
