LSM(Log Structured Merge)
아래 두 책에 있는 내용들을 기반으로 LSM(Log Structured Merge) 개념 정리한 글이다.
Log
보통 Log 라 하면 애플리케이션에서 무슨 일이 일어났는지 기술한 텍스트를 출력하는걸 말한다. 하지만 여기서 말하는 Log 는 append only 를 의미한다. 그럼 append only 는 무슨 뜻이냐?
'데이터 중심 애플리케이션 설계' 책에 나온, 세상 제일 간단한 DB 코드를 보자.
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
key 는 num, value 는 json 으로 db_set 을 통해 파일에 저장한다.
$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
db_set 을 호출할 때마다 파일 끝에 추가하므로, 같은 키를 여러 번 갱신해도 값의 예전 버전을 덮어 쓰지 않는다(append-only).
최신 값을 찾기 위해선 파일에서 키의 마지막 항목을 살펴봐야 한다. 그래서 de_get 로직에 tail -n 1 이 있다.
$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}
$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}
파일 추가 작업은 매우 효율적이다. 하지만 db_get 함수는 DB 에 레코드가 많을수록 성능이 안좋아진다. 키가 있는지 찾기 위해 항상 full scan 해야 되기 때문이다. 검색비용이 O(n) 다.
그래서 DB 는 특정 키의 값을 효율적으로 찾기 위해서 index 라는 데이터 구조가 필요하다. 하지만 이것은 저장소 시스템에서 중요한 trade off 다. index 를 통해 read 속도가 향상되지만, write 속도를 떨어뜨린다(데이터 쓸 때마다 매번 index 도 갱신해야 하기 때문).
가장 간단한 index 전략은, 데이터 파일의 byte offest 을 key 에 맵핑해 인메모리 해시 맵을 유지하는 전략이다.
Segment 와 Compaction
이렇게 같은 키를 여러 번 갱신해도 값의 예전 버전을 덮어 쓰지 않고 항상 파일 끝에 추가하므로 언젠간 결국 디스크 공간이 부족해진다. 이 상황은 어떻게 피할 수 있을까? 특정 크기의 segment 로 로그를 나누는 방식이 좋은 해결책이다. 다시말해 DB 파일 하나로 갖고 있는게 아니라 특정 크기에 도달하면 segment 파일을 닫고 새로운 segment 파일에 이후 write 를 수행한다.
이렇게 segment 파일로 나누면 무엇이 좋냐? 액티브한 파일 하나 빼고 이전에 만들어진 segment 파일들은 더이상 바뀌지 않는다(immutable 하다). 그래서 optimize 하기 편해진다.
아래와 같이 segment 파일들에 대한 compaction 을 수행할 수 있다. compaction 은 로그에서 중복된 키를 버리고(예전 값들) 각 키의 최신 갱신 값만 유지하는 것을 의미한다.
cf) 코맹탈출 유튜브에서는 segment 파일과 compaction 을 key(num), value(json) 을 갖고 설명했다. '데이터 중심 애플리케이션 설계' 책에서는 모든 고양이 동영상이 재생된 횟수를 더하는 케이스에서 compaction 을 보여준다.
아까 데이터 파일의 byte offest 을 key 에 맵핑해 인메모리 해시 맵을 유지하는 index 전략을 갖고, segment 파일과 연결시켜보면 아래와 같다. 조회 요청이 오면 맨 아래 hash index3 부터 시작해서 찾고 없으면 index2, index1 순서로 이동해서 찾는다.
이런 append-only 방식은 언뜻 보면 낭비처럼 보이지만 아래 3가지 측면에서 좋은 설계다.
1. 추가와 segment merge 는 순차적인 write 작업이기 때문에 보통 random IO 보다 훨씬 빠르다.
2. segment 파일이 append-only 거나 immutable 하면 동시성과 고장 복구는 훨씬 간단하다. 예를 들어 값을 덮어 쓰는 동안 DB 가 죽는 경우에 대해 걱정할 필요가 없다. 이전 값 부분과 새로운 값 부분을 포함한 파일을 나눠 함께 남겨두기 때문이다.
3. 오래된 segment merge 는 시간이 지남에 따라 조각화되는 데이터 파일 문제를 피할 수 있다.
하지만 장점만 있는건 아니다. hash index 또한 제한 사항이 있다.
1. hash table 은 메모리에 저장해야 하므로 키가 너무 많으면 문제가 된다. 원칙적으로는 디스크에도 유지할 수 있지만 좋은 성능을 기대하긴 어렵다. random IO 가 많이 필요하고 디스크가 가득 찼을 때 확장 비용이 비싸며 hash 충돌 해소를 위해 성가신 로직이 필요하다.
2. hash table 은 range query 에 효율적이지 않다. 예를 들어 kitty00000 ~ kitty99999 사이 모든 키를 쉽게 스캔할 수 없다. 모든 개별 키를 조회해야 한다.
SSTable(Sorted String Table)
위의 단점들은 SSTable 을 사용해서 개선시킬 수 있다. SSTable 은 Segment 파일과 비슷한데 파일 안에 key 로 정렬되어 있다. 언뜻 보기에 정렬을 시키니까 sequencial 한 write 가 안될거 같지만 가능하다.
새로운 key, value 를 추가할 때 SSTable 에 바로 넣지 않고, memTable 이라고 부르는 binary tree 에 추가한다(ex 레드블랙트리). 그후에 SSTable 에 key 가 정렬된 순서로 write 하므로 append-only 가 지켜진다.
만약 갑자기 DB 가 장애나면 어떻게 될까? memTable 은 메모리 영역에 있기 때문에, SSTable 로 옮겨지지 않은 데이터들은 다 날라간다. 이 문제를 피하기 위해서는 새로운 key/value 요청이 올 때 memTable 뿐만 아니라 디스크에 따로 또 저장시켜야 한다. 오직 장애 복구용이고 정렬은 필요없다.
SSTable 에는 key 가 정렬되어 있기 때문에 더이상 메모리에 모든 key 값을 안갖고 있어도 된다. 아래 그림에서, handiwork key 를 찾으려 하지만 메모리에 있는 sparse index 에는 handiwork 가 없다. 그래도 handbag 와 handsome key 의 offset 을 알고 있고 정렬돼 있으므로 handiwork 는 두 key 사이에 있다는 사실을 알 수 있다. 즉 handbag offset 으로 이동해 handiwork 가 나올 때까지 스캔하면 된다. 수 KB 정도는 매우 빠르게 스캔할 수 있기 때문에 segment 파일 내 수 KB 당 하나로 충분하다.
성능 최적화
LSM tree 알고리즘은 DB 에 존재하지 않는 key 를 찾는 경우 느릴 수 있다. memTable 을 확인한 다음 key 가 존재하지 않는다는 사실을 확인하기 전에는 가장 오래된 segment 까지 거슬러 올라가야 한다. 이런 종류의 접근을 최적화하기 위해 저장소 엔진은 Bloom filter 를 추가적으로 사용한다.
또한 SSTable 은 Compaction 하고 Merge 하는 순서와 시기를 결정하는 다양한 전략이 있다. 가장 일반적으로 선택하는 전략은 size-tiered 와 leveled compaction 이다.
size-tiered 는 상대적으로 좀 더 새롭고 작은 SSTable 을, 상대적으로 오래됐고 큰 SSTable 에 연이어 merge 한다.
leveled compaction 은 key 범위를 더 작은 SSTable 로 나누고 오래된 데이터는 개별 "레벨"로 이동하기 때문에 Compaction 을 점진적으로 진행해 디스크 공간을 덜 사용한다. 그래서 여러개의 hierarchy 로 저장이 되어 있다.
LSM tree 의 기본 개념은 백그라운드에서 연쇄적으로 SSTable 을 지속적으로 merge 하는 것이다.
leveled compaction 은 read 성능을 위해 compaction 을 자주 수행해야 하며, background 에서 I/O bandwidth 나 CPU 등의 리소스를 많이 소모하게 된다. size-tiered compaction 은 write 성능을 높히기 위한 방식이다. 그래서 write amplification이 줄어드나 탐색해야하는 SSTable의 수가 증가한다.
즉 leveled 방식과 size-tiered 방식은 trade-off 관계다.
LSM 트리의 장점
경험적으로 LSM 트리는 보통 write 에서 더 빠르고 B 트리는 읽기에서 더 빠르다고 여긴다. 읽기가 보통 LSM 트리에서 더 느린 이유는 각 Compaction 단계에 있는 여러 가지 데이터 구조와 SSTable 을 확인해야 하기 때문이다. 하지만 벤치마크는 보통 non-deterministic(작업부하 디테일에 따라 다름)하다.
B 트리 index 는 모든 데이터 조각을 최소한 두 번 기록해야 한다. WAL 한번과 트리 페이지에 한 번(페이지가 분리될 때 다시 기록)이다. 해당 페이지 내 몇 바이트만 바뀌어도 한 번에 전체 페이지를 기록해야 하는 오버헤드도 있다. 이렇게 DB write 한 번이 디스크에 여러 번의 write 를 야기하는 효과를 write amplification 이라 한다.
LSM index 또한 SSTable 의 반복된 Compaction 과 merge 로 인해 여러 번 데이터를 다시 쓴다. 하지만 보통 LSM 트리는 B 트리보다 write throughput 을 높게 유지할 수 있다. B 트리보다 write amplification 이 더 낮고 트리에서 여러 페이지를 덮어쓰는 것이 아니라 순차적으로 compaction 된 SSTable 파일을 쓰기 때문이다. 이런 차이는 HDD 에서 특히 중요하다. 하지만 대다수의 SSD 펌웨어는 내장 저장소 칩에서 random write 를 sequencial 한 write 로 전환하기 위해 내부적으로 로그 구조화 알고리즘을 사용한다. 그래서 저장소 엔진의 write 패턴이 SSD 에 미치는 영향은 분명하지 않다. 물론 낮은 write amplification 과 파편화 감소는 SSD 의 경우 훨씬 유리하다. 데이터를 더 밀집해 표현하면 가능한 I/O 대역폭 내에서 더 많은 read write 요청이 가능하다.
cf) Database Internals 에서 B-Tree 변형 내용
original B-Tree 는 HDD 에는 잘 동작하게 디자인되었지만, SSD 는 덜 효율적이다. 왜냐하면 높은 write amplification(caused by page rewrites) 과 높은 space overhead(have to reserve space in nodes for future writes) 가 있기 때문이다.
Lazy B-Trees 는 buffering 을 이용해 write amplification 을 줄여준다. 좀 더 자세히 말하면 node 업데이트를 buffering 해서 subsequent same-node 쓰기들의 I/O 요청을 줄여준다.
WiredTiger 는 MongoDB의 디폴트 스토리지 엔진으로, Lazy B-Trees 접근법을 사용한다. 업데이트는 먼저 업데이트 버퍼에 저장하고 나중에 일괄적으로 flush 한다.
아래 그림을 보면 clean page 는 변경 사항이 없는 페이지를 의미한다. 디스크에 저장된 원본 이미지와 정확히 일치한다. 이 페이지는 최근 업데이트가 반영되지 않았기 때문에 깨끗하다고 묘사된다. 반대로 dirty page 는 최근 업데이트가 이뤄진 페이지를 의미한다. update buffer 에 update 할것들이 쌓여있다.
두 페이지 모두 하단에 있는 Page Images 라고 표시된 디스크상의 기본 이미지를 참조한다. 이는 디스크에저장된 페이지의 원본을 의미한다. dirty page 는 이러한 기본 이미지에 대한 변경 사항을 갖고 있어, 그 변경 사항이 디스크에 저장되기 전까지 dirty 상태로 간주된다.
결론적으로 clean page 는 업데이트가 필요 없는 현재 디스크 상태를 반영하는 페이지고, dirty page 는 업데이트가 있어서 최종적으로 디스크에 저장되기 전에 메모리 내에서 관리되는 페이지다.
이 방식의 주된 장점은, 데이터 페이지의 업데이트나 구조적 변경(예: 페이지 분할 및 병합)이 백그라운드에서 처리되어, 사용자가 데이터를 읽거나 쓰는 동안 이러한 작업을 기다릴 필요 없이 연속적으로 작업을 수행할 수 있다는 것이다.
LSM 트리의 또 다른 장점은 압축률이 더 좋다. 그래서 보통 B 트리보다 디스크에 더 적은 파일을 생성한다. B 트리 엔진은 파편화로 인해 사용하지 않는 디스크 공간 일부가 남는다. 페이지를 나누거나 로우가 기존 페이지에 맞지 않을 때 페이지 일부 공간은 사용하지 않는다. LSM 트리는 페이지 지향적이지 않고 주기적으로 파편화를 없애기 위해 SSTable 을 다시 기록하기 때문에 저장소 오버헤드가 더 낮다. leveled compaction 을 사용하면 특히 그렇다.
LSM 트리의 단점
Compaction 과정이 때로는 진행중인 read write 성능에 영향을 준다. 디스크에서 비싼 Compaction 연산이 끝날 때까지 요청이 대기해야 하는 상황이 발생하기 쉽다.
또 다른 Compaction 문제는 높은 write 처리량에서 발생한다. 디스크의 write 대역폭은 유한하다. 초기 write(logging)와 MemTable 을 디스크로 flushing 그리고 백그라운드에서 수행되는 Compaction 스레드가 이 대역폭을 공유해야 한다. 빈 DB 에 write 하는 경우 전체 디스크 대역폭은 초기 write 만을 위해 사용할 수 있지만, DB 가 점점 커질수록 Compaction 을 위해 더 많은 디스크 대역폭이 필요하다.
write 처리량이 높음에도 Compaction 설정을 주의 깊게 하지 않으면 Compaction 이 유입 write 속도를 따라갈 수 없다. 보통 SSTable 기반 저장소 엔진은 Compaction 이 유입 속도를 따라가지 못해도 유입 write 속도를 조절하지 않으므로 모니터링이 필요하다. Compaction 이 잘 이뤄지지 않으면 segment 수가 계속 증가하게 되고, read 성능은 더욱 떨어진다.
Database Internals 책에서 Leveled compaction 에 대한 설명
Leveled compaction 은 디스크에 저장된 테이블들을 레벨로 나눈다. 각 레벨의 테이블은 목표 크기를 가지며, 각 레벨은 해당하는 인덱스 번호(식별자)를 가진다.
가장 최근의 데이터는 항상 가장 낮은 인덱스를 가진 레벨에 있으며, 오래된 데이터는 점차 더 높은 레벨로 이동한다.
각 레벨은 테이블 크기와 테이블의 최대 개수에 대한 제한을 갖고 있다. 레벨 1 또는 그보다 높은 인덱스를 가진 어떤 레벨의 테이블 수가 임계값에 도달하자마자, 현재 레벨의 테이블은 중첩된 키 범위를 가진 다음 레벨의 테이블과 merge 된다.
압축 과정. 점선으로 된 회색 상자는 현재 압축 중인 테이블을 나타낸다. 레벨 전체 상자는 해당 레벨에서 목표 데이터 크기 제한을 나타낸다. 레벨 1은 제한을 초과하고 있다.
Database Internals 책에서 Bloom filter 에 대한 설명
LSM 트리에서 read amplification 의 원인은 읽기 작업을 완료하기 위해 여러 디스크 상주 테이블을 접근해야 하기 때문이다. 이는 디스크 상주 테이블이 검색된 키에 대한 데이터 레코드를 포함하고 있는지 여부를 항상 알 수 없기 때문에 발생한다.
테이블 조회를 방지하는 방법 중 하나는 메타데이터에 해당 테이블에 저장된 가장 작은 키와 가장 큰 키의 범위를 저장하고, 검색된 키가 그 테이블의 범위에 속하는지 확인하는 것이다. 이 정보는 정확하지 않고 테이블에 데이터 레코드가 존재할 수 있음을 알려줄 뿐이다. 이 상황을 개선하기 위해 Apache Cassandra와 RocksDB를 포함한 많은 구현체들이 Bloom filter 라는 데이터 구조를 사용한다.
Bloom filter 는 1970년 버튼 하워드 블룸(Burton Howard Bloom)에 의해 고안된 공간 효율적인 확률적 데이터 구조로, 특정 요소가 집합의 멤버인지 아닌지를 테스트하는 데 사용된다.
거짓 긍정(false-positive) : 특정 요소가 데이터 세트에 없는데도 불구하고, Bloom filter 검사에서 그 요소가 존재한다고 잘못 보고하는 경우다.
Bloom filter 에서 거짓 긍정은 성능 저하를 일으킬 수 있다. 예를 들어, 데이터베이스나 캐시 시스템에서 Bloom filter 를 사용하여 불필요한 데이터 접근을 방지하고자 할 때, 거짓 긍정으로 인해 실제로는 필요하지 않은 데이터에 접근하게 되어 성능이 저하될 수 있다. 그러나 Bloom filter 는 거짓 부정(false negative)을 발생시키지 않는다.
거짓 부정(false negative) : 실제로는 있는데 없음다고 판단되는 오류다. Bloom filter 는 거짓 부정을 생성하지 않는 데이터 구조로 설계되었다. Bloom filter 에서 요소가 존재하지 않는다고 결론지어지면, 그 요소는 확실히 데이터 세트 내에 존재하지 않는다.
정리하면, 데이터가 없는데 있다고 구라칠순 있지만(그래서 실제 조회 작업을 하므로, 비효율) 데이터가 있는데 없다고 구라치진 않는다.
Bloom filter 가 "데이터가 있어!!" -> 구라일 수 있음 -> 실제 조회 operation 이뤄짐(성능저하, 그러나 감안)
Bloom filter 가 "데이터가 없어!!" -> 진짜 없는거임
Bloom filter 는 큰 비트 배열과 여러 해시 함수를 사용한다. 해시 함수는 테이블의 레코드 key 에 적용되어 비트 배열에서 인덱스를 찾는다. 그리고 해당 인덱스 비트는 1로 설정된다. 해시 함수에 의해 결정된 모든 위치의 비트가 1로 설정되면, 그 key 가 집합에 존재한다는 것을 나타낸다. 조회 시, Bloom filter 에서 요소의 존재 여부를 확인할 때, key 에 대해 다시 해시 함수를 계산하고, 모든 해시 함수에 의해 결정된 비트가 1이면, 해당 항목이 집합의 멤버라고 특정 확률로 긍정적 결과를 반환한다. 하지만 적어도 하나의 비트가 0이면, 그 요소가 집합에 존재하지 않는다고 정확하게 말할 수 있다.
다른 키에 적용된 해시 함수가 같은 비트 위치를 반환하여 해시 충돌이 발생할 수 있고, 1로 설정된 비트는 어떤 키에 대해 어떤 해시 함수가 이 비트 위치를 반환했다는 것을 의미할 뿐이다.
거짓 긍정의 확률은 비트 세트의 크기와 해시 함수의 수를 설정함으로써 관리된다. 더 큰 비트 세트에서는 충돌 가능성이 작아지고, 더 많은 해시 함수를 가지고 있다면 더 많은 비트를 검사하고 더 정확한 결과를 얻을 수 있다. 하지만 더 큰 비트 세트는 더 많은 메모리를 차지하고, 더 많은 해시 함수의 결과를 계산하는 것은 성능에 부정적인 영향을 미칠 수 있으므로, 수용 가능한 확률과 발생하는 오버헤드 사이에서 합리적인 중간 지점을 찾아야 한다. 확률은 예상 집합 크기로부터 계산될 수 있다. LSM 트리의 테이블은 불변이므로, 집합 크기(테이블의 key 수)는 미리 알려져 있다.
간단한 예를 들어보자. 우리는 16개의 방향을 가진 비트 배열과 3개의 해시 함수를 가지고 있으며, 이 함수들은 key1 에 대해 3, 5, 10의 값을 반환한다. 이제 이 위치에 비트를 1로 설정한다. 다음 키가 추가되고, key2 에 대해 해시 함수는 5, 8, 14의 값을 반환하며, 이에 대해서도 비트를 1로 설정한다.
이제 우리는 key3 이 집합에 있는지 없는지 확인하려고 하며, 해시 함수는 3, 10, 14의 값을 반환한다. 하지만 key1 과 key2 를 추가할 때 모든 세 비트가 이미 1로 설정되었기 때문에, Bloom filter 가 거짓 긍정을 반환하는 상황이 발생한다. key3 은 절대 추가되지 않았지만 계산된 모든 비트가 이미 1로 설정되어 있어서 그렇다. 그래도 이 결과는 받아들일 수 있다.
만약 우리가 key4 에 대한 조회를 시도하고 5, 9, 15의 값을 받는다면, 이미 설정된 비트는 5뿐이고 다른 두 비트는 설정되지 않았다는 것을 발견한다. 하나라도 비트가 설정되지 않은 경우, 그 요소가 필터에 절대 추가되지 않았다는 것을 확실히 알 수 있다. Bloom filter 가 사용하는 해시 함수들이 요소를 검색할 때, 모든 관련된 비트 위치가 1로 설정되어 있는지 확인하기 때문이다.
이 특성 덕분에 Bloom filter 는 데이터가 확실히 존재하지 않을 때 불필요한 검색이나 접근을 방지하는 데 유용하게 사용된다.