로그 구조 스토리지(Log Structured Storage)

회계사는 기록을 수정해야 하면 이미 입력된 값을 지우지 않고 새로운 값을 다시 씁니다. 최종 결과를 구하려면 모든 항목을 재검토하고 합계액을 계산해야 합니다. 이러한 방식은 바로 오늘 포스트에서 살펴볼 로그 구조 스토리지(Log-Structured Storage)와 유사합니다.
또 다른 예로는 불변 스토리지(immutable storage)가 있습니다. 불변 스토리지에서 저장된 파일은 수정할 수 없습니다. 반대로 가변 스토리지(mutable storage)는 디스크에 저장된 레코드를 수정할 수 있습니다.
이와 같이 불변 자료 구조의 경우 함수형 프로그래밍에서 많이 사용되는데 그 이유는 한번 생성된 불변 자료 구조는 바뀔 수 없고 동시 참조 가능하고 무결성이 보장되는 장점이 있어서 안전하다는 특성을 가지고 있습니다.
불변 파일 역시 여러 버전의 파일 사본을 저장하며 최신 버전이 이전 버전을 덮어쓰는 형식으로 보여주고, 가변 파일은 최신 버전만 저장합니다.
지금까지 불변과 가변의 차이를 다양한 관점에서 살펴보았는데 그 이유는 데이터베이스에서 저장된 데이터를 처리하기 위한 자료구조가 이러한 특성에 따라 달라지기 때문입니다.
데이터베이스에서 B-트리는 가변 자료구조이며, LSMT(Log-Structured Merge Tree)는 불변 자료 구조입니다. LSM 트리는 추가 전용 구조가 기본이며 병합 조정(merge conciliation) 방식을 사용합니다. 반면에 B-트리의 경우 디스크에서 레코드를 찾고 해당 페이지의 기존 오프셋의 위치에 업데이트를 하는 방식을 사용합니다.

	B-트리	LSM 트리
읽기	Good	Bad
쓰기	Bad	Good

이러한 B-트리와 LSM트리는 각각의 특성에 따라 장단점이 서로 다릅니다. B-트리의 경우 읽기 작업에 효율적이지만 업데이트 대상 레코드를 디스크에서 찾아야 하므로 쓰기 성능은 떨어집니다. 반면에 LSM 트리는 쓰기 작업에 유리하지만 읽기 시 레코드의 여러 버전을 읽고 최신 버전을 찾아야 하기 때문에 읽기 성능이 조금 떨어집니다. 위 테이블에는 상대적으로 표현하기 위해 Good, Bad를 사용하였습니다.

LSM 트리

LSM 트리의 Merge는 중복된 복사본에 대한 유지보수 작업 시 병합 정렬과 유사한 방식으로 병합하는 것을 의미합니다.
LSM 트리는 데이터 파일 쓰기를 지연시키기 위해 변경 사항을 메모리 기반 테이블에 저장합니다. 그리고 일정량이 쌓이면 내용을 불변 디스크 파일에 저장해 변경 사항을 반영합니다. 불변 파일은 데이터를 연속된 공간에 저장해 단편화를 방지합니다. 이 방식은 업데이트 된 레코드가 원본 레코드보다 큰 경우를 위한 공간을 미리 할당하지 않아도 되는 장점을 갖습니다. 파일은 수정될 수 없으므로 삽입, 수정, 삭제 작업은 디스크에서 레코드를 찾이 않아도 되므로 쓰기 성능과 처리량이 크게 향상됩니다.
반면에 LSM 트리는 성능 최적화를 위해 유지보수 작업이 필요합니다. 읽기 작업 수행시 최대한 적은 수의 파일을 읽도록 하기 위해서 파일을 병합하고 재작성하는 과정이 필요합니다.

LSM 트리 구조

LSM 트리는 메모리 기반 컴포넌트와 디스크 기반 컴포넌트 2개로 구성됩니다. 메모리 기반 컴포넌트는 멤테이블이라고 하는데 불변 자료 구조입니다. 멤테이블은 데이터 레코드를 버퍼에 저장하고 일기와 쓰는 작업을 수행합니다. 멤테이블의 크기가 설정한 기준 값에 도덜하게 되면 디스크로 플러시를 합니다. 버퍼에 저장된 데이터는 디스크 기반 컴포넌트로 플러시 되는데 디스크 기반 컴포넌트의 경우 읽기 작업에만 사용되고 한번 저장된 데이터는 다시 수정할 수 없습니다. LSM 트리의 경우 인메모리 테이블에 쓰는 작업과 메모리, 디스크 기반의 테이블에서 읽는 작업, 병합 작업, 파일을 삭제하는 작업을 수행합니다.

멤테이블

멤테이블을 플러시 하려면 우선 멤테이블을 플러시 대상 테이블로 전환해야 합니다. 새로운 멤테이블을 할당해 그 이후에 들어오는 쓰기 작업을 담당하도록 서렁하고, 기존 테이블은 플러시 상태로 전환해야 하는데 이 두 단계는 원자적으로 수행해야 합니다. 또한 플러시 대상 테이블은 완전히 플러시될 때까지 읽기가 가능해야합니다. 플러시가 완료되면 멤테이블은 삭제되고 플러시된 내용은 디스크 기반 테이블에서 읽을 수 있습니다. 다음은 LSM 트리의 컴포넌트 사이의 전환 과정을 보여줍니다.

멤테이블이 완전히 플러시되기 전까지 해당 내용이 저장된 곳은 WAL(write-ahead log)이고 멤테이블이 플러시 되면 로그에서 멤테이블과 관련된 작업이 기록된 부분도 같이 삭제됩니다.

수정과 삭제

LSM 트리는 삽입, 수정, 삭제 시 디스크에서 데이터를 찾을 필요가 없습니다. 대신 읽기 중에 중복된 데이터들이 재조정됩니다. 삭제의 경우에는 명시적으로 삭제 여부를 기록하는데 해당 키의 값이 삭제됐음을 나타내는 툼스톤 마커를 표시합니다. 재조정 프로세스는 툼스톤을 찾아 마킹된 값을 제거합니다.

LSM 트리 유지보수

LSM 트리는 유지보수가 필요합니다. 이렇게 유지보수 하는 과정을 컴팩션이라고 합니다. 컴팩션을 최적화할 수 있는 다양한 전략이 존재합니다. 이제 다양한 컴팩션 기법에 대해 살펴보겠습니다.

Leveled 컴팩션

레벨 컴팩션은 디스크 테이블을 여러 레벨로 나눕니다. 레벨 별로 테이블의 수가 일정 수에 도달하면 데이터를 병합해 다음 레벨의 테이블을 생성합니다. 가장 최신의 데이터는 인덱스가 낮은 레벨에 있고 상대적으로 오래된 데이터는 높은 인덱스 레벨로 올라갑니다.

Size-tiered 컴팩션

Size-tiered 컴팩션은 레벨이 아닌 테이블의 크기를 기준으로 디스크 테이블을 그룹화하는 방식입니다. size-tiered 컴팩션의 문제중 하나는 테이블 기아 현상입니다. 컴팩션된 테이블의 크기가 여전히 작은 경우 높은 인덱스 레벨의 테이블은 컴팩션 기회를 얻지 못해 툼스톤이 정리되지 않고 읽기 비용이 올라가는 문제가 발생할 수 있습니다.

읽기, 쓰기, 공간 증폭

데이터를 디스크에 불변 방식으로 저장할 때 다음과 같은 세 가지 문제가 발생합니다.

읽기 증폭 : 데이터를 읽기 위해 여러 테이블을 참조하면서 발생
쓰기 증폭 : 컴팩션 과정에서 발생하는 지속적인 다시 쓰기로 인해 발생
공간 증폭 : 같은 키에 대해 여러 레코드가 존재할 때 발생

위와 같이 세 개의 문제는 RUM conjecture를 통해서 비용을 계산할 수 있습니다. 세 가지 오버헤드 중 두 가지를 줄이면 다른 한가지가 불가피하게 증가하게 되므로 선택이 필요합니다. 다양한 스토리지 엔진들마다 선택한 것들이 다릅니다.

상세 구현

SSTable

디스크 기반 테이블은 SSTable(Sorted String Table)을 사용해 구현합니다. SSTable은 레코드를 키 순서로 정렬해 저장합니다. SSTable은 인덱스 파일과 데이터 파일로 구성됩니다. 인덱스 파일은 B-트리나 해시 테이블 등의 룩업이 가능한 자료 구조를 사용해 구현합니다. 데이터 파일은 레코드를 키 순서로 저장합니다.

블룸 필터

LSM 트리의 경우 데이터가 여러 디스크에 저장된 테이블에 접근할 때 읽기 증폭이 발생될 수 있습니다. 디스크 기반 테이블에 검색 키에 대한 레코드가 존재하는지 미리 알 수 없기 때문입니다. 이를 위해 카산드라나 RocksDB 등에서 블룸 필터를 사용합니다. 블룸 필터는 어떤 원소가 집합에 속하는지 여부를 확인할 수 있는 공간 효율적인 확률적 자료 구조입니다. false-positive(실제 집합에 속하지 않지만 속한다고 잘못 판단)는 발생할 수 있지만 false-negative(결과가 음성인 원소는 집합에 확실히 속하지 않음)는 발생하지 않는 특징을 가집니다. 블룸 필터를 사용하면 특정 키가 테이블에 존재할 수 있는지 확인할 수 있습니다. 그래서 블룸 필터가 negative를 반환한 파일은 쿼리 수행 중에 필터링 됩니다. 이렇게 블룸 필터를 같이 사용하면 읽기 작업의 테이블 접근 횟수를 크게 줄일 수 있습니다. 블룸 필터에 관해 조금더 자세히 알고 싶은 분은 다음 슬라이드를 확인하시면 도움이 될 것입니다.

정렬되지 않은 LSM 스토리지

비트캐스크

Riak에서 사용되는 스토리지 엔진 중 하나인 비트캐스크는 정렬되지 않는 로그 구조 기반의 스토리지 엔진입니다. 비트캐스크는 데이터 레코드를 로그 파일에 바로 저장합니다. 그리고 레코드를 검색할 수 있도록 각 키의 최신 데이터 레코드에 대한 참조를 keydir이라는 자료 구조에 저장합니다. keydir에서 참조하지 않는 이전 데이터 레코드들이 디스크에 남아 있게 되는데 이런 데이터는 컴팩션 시 정리됩니다. keydir은 인메모리 해시맵 형태이며 시스템 기동시 로그 파일을 사용해 재구성합니다. 데이터 레코드는 로그 파일에 바로 쓰기 때문에 따로 WAL이 필요 없으며 공간 오버헤드와 쓰기 증폭이 줄어드는 장점을 갖습니다. 하지만 keydir과 데이터 파일의 레코드가 정렬되어 있지 않기 때문에 범위 스캔이 불가능하고 포인트 쿼리만 수행할 수 있는 단점이 있습니다.

위스키(WiscKey)

정렬되지 않은 스토리지에서 범위 스캔을 지원하기 위한 자료구조입니다. 위스키는 LSM 트리에 키를 정렬된 상태로 유지하고 vLog(value log)라는 정렬되지 않은 추가 전용 파일에 데이터 레코드를 저장해 가비지 컬렉션과 정렬 작업을 분리합니다. 이를 통해 위스키는 모든 키를 메모리에 저장하고 시스템 기동 시 해시 테이블을 재구성해야 하는 비트캐스크의 문제를 해결할 수 있습니다.

정리

이번 포스트에서는 로그 기반 스토리지에 관한 특성에 대해 살펴보았습니다. 로그 기반 스토리지에서 사용하는 자료구조는 LSM 트리를 사용합니다. 이번 포스트를 통해 LSM 트리의 특성과 장단점에 대해 이해하는데 도움이 되었으면 합니다.

References

데이터베이스 인터널스