데이터 중심 애플리케이션 설계 - 3. 3장 요약

NoSQL의 저장소 엔진과 데이터 구조

이 장에서는 NoSQL의 저장소 엔진과 로그구조, 페이지 지향 계열 저장소 엔진을 검토한다

데이터 구조

아주 간단한 데이터 구조에 대해서 생각해보자. 키와 값의 구조로 저장이 가능하고 이는 JSON과 같은 키와 값의 형태를 생각하면 된다. 이런 데이터 구조는 간단한 작업에 좋은 성능을 보여준다.

많은 데이터베이스가 내부적인 추가 전용 데이터 파일인 로그(log)를 사용한다. 하지만 단순히 키와 값의 형태로 저장하는 일반적인 데이터 구조에서 검색은 효율적이지 못하다. 알고리즘 용어로 O(n)의 검색비용이 발생하는데, 이는 데이터의 양이 두 배가 되면 검색 소요 시간도 두 배가 걸린다는 걸 의미한다.

그렇기 때문에 검색에 있어서는 조금 다른 구조가 필요한데, 바로 색인이다. 색인은 기본 데이터에서 파생된 구조로 데이터 베이스의 내용에 영향을 미치지 않고 질의 성능에만 영향을 준다.

색인은 읽기 속도를 향상시켜주지만, 쓰기 속도를 느리게 한다. 데이터를 쓸 때마다 색인 역시 갱신해줘야하기 때문이다. 따라서 필요 이상으로 오버헤드를 발생시키지 않고 이익을 주는 색인을 선택해야 한다.

여기서 오버헤드란 프로그램 실행 흐름과 다른 처리를 위해 들어가는 추가적인 시간, 메모리, 자원 등을 의미한다.

해시 색인

키-값의 저장소는 프로그래밍 언어의 사전 타입과 유사하고 보통 해시 맵으로 구현한다. 만약 간단한 파일 추가 형식의 데이터 저장소에서 기본적인 색인 전략은 다음과 같다.

키를 데이터 파일의 바이트 오프셋에 매핑해서 인메모리 해시 맵을 유지하는 것이다. 여기서 바이트 오프셋이란, 값을 바로 찾을 수 있는 위치 정보이다. 따라서 만약 데이터에 새로운 키-값의 쌍을 추가하면 데이터 오프셋을 반영하기 위해 해시 맵도 갱신한다.

만약 계속해서 파일에 추가만 하면 디스크 공간 부족이 일어난다. 이 상황은 특정 크기의 세그먼트로 로그를 나누어 해결한다. 또한 세크먼트에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 컴팩션을 수행한다.

이런 해시 테이블 색인은 문제점이 존재한다.

1. 메모리에 저장하는 구조이기 때문에, 키가 너무 많으면 디스크에 해시 맵을 유지할 수 있지만, 좋은 성능을 기대할 수 없다.
2. 범위 질의에 효율적이지 않다. 가령 0000과 9999사이의 모든 키를 쉽게 스캔하는 방법이 없고 개별 조회를 해야한다.

SS테이블과 LSM트리

위의 세그먼트 파일 형식에서 간단한 변경을 한 가지 해보기로 하자. 만약 키-값의 쌍을 키로만 정렬하면, 이 형식을 정렬된 문자열 테이블(Sorted String Table)이라고 한다(SS테이블).

SS테이블은 해시 색인을 가진 로그 세그먼트보다 큰 장점이 있다.

1. 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 효율적이다.

2. 파일에 특정 키를 찾기 위해서 모든 키의 색인을 유지할 필요가 없다. 일부 키에는 필요하지만, 수 킬로바이트 정도는 매우 빠르게 스캔이 가능한다.

3. 읽기 요청은 요청 범위 내 여러 키-값의 쌍을 스캔해야해서 디스크에 쓰기 전 압축한다. 희소 인메모리 색인은 압축된 블록 시작을 가르키게 된다. 이는 디스크 공간 절약 외에도 I/O 대역폭을 줄이게 된다.

만약 유입되는 쓰기가 있을 경우 레드 블랙 트리나 AVL트리와 같은 잘 알려진 구조를 사용한다.

이 때는 아래와 같은 순서로 저장소 엔진을 구성하게 된다.

1. 쓰기가 들어오면 인메모리 균형 트리 데이터구조에 추가한다(가령 레드 블랙 트리). 이 때 인메모리 트리는 멤테이블이라고 한다.

2. 멤테이블이 임계값보다 커지면 SS테이블 파일로 기록한다. 이 때 SS파일은 데이터벵스의 가장 최신 세그먼트가 된다. SS테이브를 기록하는 동안 새 쓰기는 새로운 멤테이블 인스턴스에 기록한다.

3. 읽기 요청을 제공하려면 먼저 멤테이블에서 키를 찾고 다음으로 최신 세그먼트를 찾고 그 다음 순차적으로 오래된 세그먼트를 찾는다.

4. 가끔 오래된 세그먼트를 합치고 삭제된 값을 버리는 병합, 컴펙션 과정을 거친다.

이런 과정은 잘 동작하지만 한 가지 문제가 있는데, 데이터베이스가 고장이 날 시 기록되지 않는 멤테이블의 쓰기가 손실되는 것이다. 이 문제를 피하기 위해 매선 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크상에 유지해야하며, 이는 복원 시에만 필요하므로 특별히 정렬되지 않는다. 만약 SS테이블에 기록이 되면 로그는 버릴 수 있다.

원래 이 색인 구조는 로그 구조화 병합 트리(LSM트리)라고 발표했다. 이 색인 구조는 로그 구조화 파일 시스템의 초기 작업의 기반이 되었다. 이 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라고 부른다.

B트리

이런 로그 구조화 색인이 보편화 되었지만 일반적으로 가장 널리 쓰이는 색인 구조는 B트리이다. B트리 구조는 로그 구조화 색인과는 상당히 다르다.

B트리는 전통적으로 4KB나 그 이상의 고정 크기 블록이나 페이지로 나누어 한 번에 하나의 페이지에 읽기나 쓰기를 한다.

각 페이지의 주소나 위치를 이용해 다른 페이지를 참조하며, 한 페이지는 B트리의 루트로 지정된다. 페이지는 여러 키와 하위 페이지의 참조를 포함하고, 하위 페이지는 키가 이어지는 범위를 담당한다.

가령 255이라는 키를 찾으면 200고 300의 범위를 참조를 따라간다. 그럼 하위 페이지에서 더 세밀한 부분인 250과 260 사이의 참조를 따라가고, 그 밑에서 또 하위 페이지를 찾아 나가는 방식이다.

B트리의 한 페이지에서 하위 페이지를 참조하는 수를 분기 계수라고 한다. 분기 계쑤는 보통 수백 개에 달한다.

만약 키를 갱신하면 키를 포함한 리프 페이지를 찾고 페이지의 값을 바꾸어 디스크에 새로 기록한다.

B트리와 LSM트리의 비교

B트리가 LSM보다 구현 성숙도가 높지만, LSM트리 역시 성능 특성 때문에 많이 사용된다. 보통 LSM트리는 각 컴팩션 탄계의 데이터 구조와 SS테이블을 확인하므로 B트리보다 읽기에서는 느리다. 반면 쓰기에서는 LSM트리가 더 빠르다.

LSM트리의 장점

LSM트리는 보통 B트리보다 쓰기 처리량을 높게 유지할 수 있다. 쓰기 증폭이 낮고 순차적으로 컴팩션된 SS테이블 파일을 쓰기 때문이다. 또한 LSM트리는 압축률이 좋다.

LSM트리의 단점

컴펙션 과정이 떄로 진행 중인 읽기와 쓰기의 성능에 영향을 준다. 또한 디스크의 쓰기 대역폭은 유한한데, 컴팩션 쓰레드가 이 대역폭을 공유하므로 데이터베이스가 커지면 컴팩션을 위해 더 많은 디스크 대역폭이 필요하다.

B트리는 각 키가 색인의 한 곳에만 정확하게 존재하는데 비해 LSM트리는 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있다.

트랜잭션 처리와 분석

초기 비지니스에서 데이터베이스는 주로 상거래(commercial transaction)에서 사용되었다. 데이터베이스가 이제 상거래가 아닌 영역으로 확장되었지만 트랙잭션이라는 용어 자체는 남아있다.

색인을 이용한 적은 수의 레코드를 찾고, 사용자 입력을 기반으로 삽입되거나 갱신되는 패턴을 온라인 트랜잭션 처리(OLTP)라고 한다.

반면 데이터 분석 영역에서, 많은 수의 레코드를 스캔해서 카운트, 합, 평균과 같은 집계 통계를 계산하는 식으 처리를, 온라인 분석 처리(OLAP)라고 한다.

둘의 차이를 표로 나타내면 아래와 같다.

특성	OLTP	OLAP
주요 읽기 패턴	적은 수 레코드, 키 기준	많은 수의 레코드 집계
주요 쓰기 패턴	임의 접근	대규모 불러오기 또는 이벤트 스트림
주요 사용처	소비자	의사 결정을 위한 분석가
데이터 표현	데이터 최신 상태	시간이 지나며 일어난 이벤트 이력
데이터셋 크기	GB ~ TB	TB ~ PB

데이터 웨어하우징

대개 기업은 수십 가지의 트랙잭션 처리 시스템을 갖추고 있다. 이런 시스템은 복잡하기 때문에 유지보수를 위한 팀이 필요하기 때문에 각 시스템이 서로 독자적으로 운영된다.

데이터 웨어하우스는 분석자들이 OLTP작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스이다. 데이터 웨어하우스는 회사 내의 모든 다양한 OLTP 시스템에 있는 데이터의 읽기 전용 복사본이다. 데이터 웨어하우스로 데이터를 가져오는 이 과정을 ETL(Extract-Transform-Load)라고 한다.

OLTP 데이터베이스와 데이터 웨어하우스의 차이점

SQL은 일반적으로 분석 질의에 적합해서 데이터 웨어하우스의 데이터 모델은 가장 일반적인 관계형 모델을 사용한다. SQL 질의를 생성하고 결과를 시각화하고 분석가가 드릴 다운(drill-down), 슬라이싱(slicing), 다이싱(dicing)같은 작업을 통해 데이터를 탐색할 수 있게 해주는 여러 그래픽 데이터 분석 도구가 있다.

일반적으로 관계형 OLTP와 데이터 웨어하우스 모두 SQL 질의 인터페이스를 지원하므로 비슷하다. 하지만 시스템의 내부는 매우 다르다.