1. 개요
최신 데이터베이스 시스템은 데이터 쓰기 및 읽기에 정교한 스토리지 엔진을 활용하여 안정성, 일관성, 높은 처리량 등과 같은 일련의 기능을 보장하도록 Custom화되었습니다.
이 예제에서는 Apache Cassandra 에서 사용하는 스토리지 엔진의 내부에 대해 자세히 살펴보겠습니다. 이 엔진 은 쓰기 작업이 많은 워크로드용으로 설계되었으며 읽기 성능도 우수합니다 .
2. LSMT(로그 구조 병합 트리)
Apache Cassandra는 저장을 위해 2단계 로그 구조 병합 트리 기반 데이터 구조를 활용합니다 . 높은 수준에서 이러한 LSM 트리에는 인메모리 캐시 구성요소(C 0 )와 온디스크 구성요소(C 1 ) 의 두 가지 트리형 구성요소가 있습니다.
메모리에서 직접 읽고 쓰는 것이 일반적으로 디스크보다 빠릅니다. 따라서 설계상 모든 요청은 C 1 에 도달하기 전에 C 0 에 도달합니다 . 또한 동기화 작업은 C0에서 C1까지 주기적으로 데이터를 유지합니다 . 결과적으로 I/O 작업을 줄임으로써 네트워크 대역폭을 효율적으로 사용합니다 .
다음 섹션 에서는 일반적으로 각각 MemTable 및 SSTable로 알려진 Apache Cassandra의 2단계 LSM 트리 의 C 0 및 C 1 데이터 구조에 대해 자세히 알아봅니다 .
3. 멤테이블
이름에서 알 수 있듯이 MemTable은 자체 균형 이진 검색 트리 속성 이 있는 Red-black 트리 와 같은 메모리 상주 데이터 구조 입니다. 결과적으로 모든 읽기 및 쓰기 작업, 즉 검색, 삽입, 업데이트 및 삭제는 O(log n) 시간 복잡성으로 달성할 수 있습니다.
메모리 내 변경 가능한 데이터 구조인 MemTable 은 모든 쓰기를 순차적으로 만들고 빠른 쓰기 작업을 허용합니다 . 또한 제한된 용량 및 휘발성 특성과 같은 물리적 메모리의 일반적인 제약으로 인해 MemTable에서 디스크로 데이터를 유지해야 합니다.
MemTable의 크기가 임계값에 도달하면 모든 r/w 요청이 새 MemTable로 전환되고 이전 MemTable은 디스크에 플러시한 후 삭제됩니다.
여태까지는 그런대로 잘됐다! 많은 수의 쓰기를 효율적으로 처리할 수 있습니다. 그러나 플러시 작업 전에 노드가 충돌하면 어떻게 됩니까? 음, 간단합니다. 아직 디스크로 플러시되지 않은 데이터를 잃게 됩니다.
다음 섹션에서는 Apache Cassandra가 WAL(Write-Ahead Logs) 개념을 사용하여 이 문제를 해결하는 방법을 살펴보겠습니다.
4. 커밋 로그
Apache Cassandra는 데이터를 메모리에서 디스크로 유지하는 플러시 작업을 연기합니다. 따라서 예기치 않은 노드 또는 프로세스 충돌로 인해 데이터가 손실될 수 있습니다.
내구성은 모든 최신 데이터베이스 시스템의 필수 기능이며 Apache Cassandra도 예외는 아닙니다. Commit Log 라는 추가 전용 파일의 디스크에 모든 쓰기가 지속되도록 하여 내구성을 보장합니다 . 그 후 쓰기 경로에서 쓰기 되돌림 캐시로 MemTable을 사용합니다.
추가 전용 작업은 디스크에서 임의 검색을 피하기 때문에 빠릅니다. 따라서 Commit Log는 쓰기 성능을 손상시키지 않으면서 내구성 기능을 제공합니다. 또한 Apache Cassandra는 충돌 복구 시나리오 중에만 Commit Log를 참조하는 반면 일반 읽기 요청은 Commit Log로 이동하지 않습니다.
5. SS테이블
SSTable(Sorted String Table)은 Apache Cassandra 스토리지 엔진에서 사용하는 LSM 트리의 디스크 상주 구성 요소입니다 . Google의 BigTable 데이터베이스에서 처음 사용된 유사한 데이터 구조에서 이름을 가져오고 데이터를 정렬된 형식으로 사용할 수 있음을 나타냅니다. 일반적으로 MemTable의 각 플러시 작업은 SSTable에서 새로운 불변 세그먼트를 생성합니다.
동물원에 보관된 다양한 동물의 수에 대한 데이터를 포함하면서 SSTable이 어떻게 보이는지 시각화해 봅시다.
그럼에도 불구하고 세그먼트가 키별로 정렬되지만 동일한 키가 여러 세그먼트에 존재할 수 있습니다. 따라서 특정 키를 찾아야 하는 경우 최신 세그먼트에서 검색을 시작하고 찾자마자 결과를 반환해야 합니다.
이러한 전략을 사용하면 최근에 작성된 키에 대한 읽기 작업이 빠릅니다. 그러나 최악의 경우 알고리즘은 O( N *log( K )) 시간 복잡성으로 실행됩니다. 여기서 N 은 총 세그먼트 수이고 K 는 세그먼트 크기입니다. K 는 상수 이므로 전체적인 시간복잡도는 O( N )로 비효율적이라고 할 수 있다.
다음 몇 개의 섹션에서는 Apache Cassandra가 SSTable에 대한 읽기 작업을 최적화하는 방법을 알아봅니다.
6. 희소 인덱스
Apache Cassandra는 키를 찾는 동안 스캔해야 하는 세그먼트 수를 제한하기 위해 희소 인덱스를 유지합니다 .
희소 인덱스의 각 항목에는 디스크의 페이지 오프셋 위치와 함께 세그먼트의 첫 번째 구성원이 포함됩니다. 또한 인덱스는 B-Tree 데이터 구조 로 메모리에 유지되므로 O(log( K )) 시간 복잡도 로 인덱스에서 오프셋을 찾을 수 있습니다 .
"맥주"라는 키를 검색한다고 가정해 보겠습니다. 희소 인덱스에서 "beer"라는 단어 앞에 나오는 모든 키를 검색하는 것으로 시작하겠습니다. 그런 다음 오프셋 값을 사용하여 제한된 수의 세그먼트만 살펴보겠습니다. 이 경우 첫 번째 키가 "악어"인 네 번째 세그먼트를 살펴보겠습니다.
반면에 "캥거루"와 같은 부재 키를 검색해야 하는 경우 모든 세그먼트를 살펴봐야 합니다. 따라서 희소 인덱스를 사용하면 검색이 제한된 범위로 최적화된다는 것을 알고 있습니다.
또한 SSTable은 동일한 키가 다른 세그먼트에 존재할 수 있도록 허용한다는 점에 유의해야 합니다. 따라서 시간이 지남에 따라 동일한 키에 대해 점점 더 많은 업데이트가 발생하므로 희소 인덱스에도 중복 키가 생성됩니다.
다음 섹션에서는 Apache Cassandra가 블룸 필터 및 압축을 통해 이 두 가지 문제를 해결하는 방법을 알아봅니다.
7. 블룸 필터
Apache Cassandra는 블룸 필터 로 알려진 확률적 데이터 구조를 사용하여 읽기 쿼리를 최적화합니다 . 간단히 말해서 먼저 블룸 필터를 사용하여 키에 대한 멤버십 확인을 수행하여 검색을 최적화합니다.
따라서 SSTable의 각 세그먼트에 블룸 필터를 연결하면 읽기 쿼리, 특히 세그먼트에 없는 키에 대해 상당한 최적화를 얻을 수 있습니다.
블룸 필터는 확률적 데이터 구조이므로 누락된 키에 대해서도 응답으로 "미정"을 얻을 수 있습니다. 그러나 응답으로 "아니오"가 표시되면 키가 확실히 누락되었음을 확신할 수 있습니다.
한계에도 불구하고 더 큰 저장 공간을 할당하여 블룸 필터의 정확도를 개선할 계획을 세울 수 있습니다 .
8. 압축
블룸 필터와 희소 인덱스를 사용하더라도 읽기 쿼리의 성능은 시간이 지남에 따라 저하됩니다. 이는 서로 다른 버전의 키를 포함하는 세그먼트 수가 각 MemTable 플러시 작업과 함께 증가할 가능성이 높기 때문입니다.
이 문제를 해결하기 위해 Apache Cassandra는 각 키에 대한 최신 값만 유지하면서 더 작은 정렬 세그먼트를 더 큰 세그먼트로 병합 하는 백그라운드 압축 프로세스를 실행합니다 . 따라서 압축 프로세스는 더 적은 스토리지로 더 빠른 읽기라는 이중 이점을 제공합니다 .
압축의 단일 실행이 기존 SSTable에서 어떻게 보이는지 봅시다.
압축 작업이 최신 버전만 유지하여 일부 공간을 회수했음을 알 수 있습니다. 예를 들어 "elephant" 및 "tiger"와 같은 이전 버전의 키가 더 이상 존재하지 않으므로 디스크 공간이 확보됩니다.
또한 압축 프로세스를 통해 키를 영구 삭제할 수 있습니다. 삭제 작업은 삭제 표시로 키를 표시하지만 실제 삭제는 압축될 때까지 연기됩니다.
9. 결론
이 기사에서는 Apache Cassandra 스토리지 엔진의 내부 구성 요소를 살펴보았습니다. 그렇게 하면서 LSM Tree, MemTable 및 SSTable과 같은 고급 데이터 구조 개념에 대해 배웠습니다 . 또한 Write-Ahead Logging, Bloom Filters, Sparse Index 및 Compaction을 사용하는 몇 가지 최적화 기술도 배웠습니다.
