추가 전용 로그

많은 데이터베이스는 내부적으로 추가 전용 데이터 파일인 로그를 사용한다.

여기서의 로그는 애플리케이션에서 사용되는 로그가 아니라 추가 전용 레코드라는 의미로 사용된다.

세그먼트와 컴팩션

• 파일에 데이터를 항상 추가만 한다면 결국 디스크 공간은 부족해진다. 이를 해결하기 위해 특정 크기의 세그먼트로 로그를 나누고, 컴팩션을 수행하면 된다.
• 로그 구조화 저장소 세그먼트는 키-값 쌍의 연속으로 이루어지며 순차쓰기를 하므로 같은 키를 갖는 나중 값이 우선시된다.
• 컴팩션은 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것을 의미한다.
  • 컴팩션을 수행하면 세그먼트는 작아지므로 동시에 여러 세그먼트들을 병합할 수 있다.

추가 전용 로그는 낭비인가?

• 추가 전용 로그는 데이터를 계속해서 추가하기 때문에 낭비같아 보이지만 여러 측면에서 장점을 가진다.
  1. 순차적인 쓰기이므로 추가 및 병합이 무작위 쓰기보다 훨씬 빠르다.
  2. 세그먼트 파일이 추가전용이나 불변이면 동시성과 고장 복구가 간단하다.

인덱스

인덱스는 기본 데이터(primary data)에서 파생된 추가적인 구조다. 인덱스는 쓰기 과정에서 오버헤드가 발생한다. 데이터를 쓸 때마다 매번 인덱스를 갱신해야 하기 때문이다.

인덱스를 잘 선택하면 읽기 성능이 좋아지지만, 모든 인덱스는 쓰기 속도를 떨어뜨린다.

해시 테이블 인덱스

• 인메모리 해시 맵을 유지하여 인덱스를 유지하는 방법이다.
• 고유 키 수가 적고 각 키의 값이 자주 갱신되는 경우에 적합하다.
• 하지만 인메모리 방식은 키가 너무 많으면 유지할 수고, 해시 테이블의 경우 range query에 효율적이지 못하다.
• SS테이블과 LSM트리는 이러한 제한이 없는 인덱스 구조이다.

SS테이블과 LSM트리

키-값 쌍을 가지는 세그먼트 파일 형식에서 키-값쌍을 키로 정렬하는 형식을 SS(Sorted String)테이블이라고 부른다.

SS테이블은 해시 테이블 인덱스를 가진 로그 세그먼트보다 몇 가지 큰 장점을 가진다.

1. 병합정렬 알고리즘과 유사한 방식을 통해 세그먼트 병합이 간단하고 효율적이다.

• 세그먼트 병합 시 각 세그먼트의 첫 번째 키들을 비교하여 낮은 키들을 하나씩 뽑아와서 병합한다.(중복키들은 최신꺼 한개만 가져옴)

2. 파일에서 특정 키를 찾기 위해 더는 메모리에 모든 키의 인덱스를 유지할 필요가 없다.

• 모든 키가 정렬상태로 저장되기 때문에 메모리에는 특정 키들의 인덱스만 유지하고 입력 키와 가장 근접한 인덱스 하위, 상위 값을 파악하여 효율적으로 스캔할 수 있다.

SS테이블 생성과 유지

• 키를 정렬하여 저장하기 위해서는 단순히 쓰기를 저장하면 안된다.
• 정렬을 유지하기 위한 방법으론 레드 블랙 트리와 같은 트리 데이터 구조를 활용하는게 대표적이다.
• 그리고 정렬된 구조를 유지를 디스크가 아닌 메모리에 유지하는 편이 훨씬 쉬울 것이다.
• 쓰기가 들어오면 인메모리 레드 블랙 트리와 같은 인메모리 균형 트리에 데이터를 추가하며 이 인메모리 트리를 멤테이블(memtable)이라고 한다.
• 멤테이블이 임곗값에 도달하면 SS테이블 파일로 디스크에 기록한다.
  • 트리가 이미 키로 정렬되어있으므로 효율적으로 수행 가능하다.
  • 새로운 SS테이블 파일은 DB의 가장 최신 세그먼트가 되고, SS 테이블에 기록하는 동안 새로운 쓰기는 새로운 멤테이블에 수행된다.
• 읽기 요청시 먼저 멤테이블에서 키를 찾고, 그 다음 디스크에서 가장 최신 세그먼트순으로 찾는다.
• 백그라운드에서 지속적으로 세그먼트 파일을 컴팩션하고 병합하는 과정을 수행한다.
  • 이러한 방식으로 디스크에 쓰면 순차적이기 때문에 매우 높은 쓰리 처리량을 보장할 수 있게 된다.
• DB 고장을 대비하기 위해 멤테이블에 쓰기 작성 시 디스크에도 멤테이블 복원용 로그를 남기는 것이 필요하다.
  • 해당 로그는 복원시에만 사용되므로 정렬이 필요 없다.
• 이렇게 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM(Log-Structured Merge-Tree) 저장소 엔진이라고 부른다.
  • 이러한 구조를 따르는 DB는 BigTable, Cassandra, HBase등이 있다.

LSM 트리 알고리즘 성능 최적화

• LSM 트리 알고리즘은 DB에 존재하지 않는 키를 찾는 경우 멤테이블부터 가장 오래된 세그먼트까지 읽어야하므로 느릴 수 있다.
• 이런 종류의 접근을 최적화하기 위해 보통 블룸 필터(Bloom filter)를 추가적으로 사용한다.
  • 블룸 필터는 키가 DB에 존재하지 않음 알려줄 수 있는 확률적 자료구조다. 참고 (opens new window)
  • 블룸 필터가 DB에 키가 있다고 했을 때 실제로 DB에 키가 없을 순 있지만, DB에 키가 없다고 했다면 반드시 DB에도 존재하지 않는다.
• SS테이블 압축하고 병합하는 순서와 시기를 결정하는 다양한 전략도 존재한다.
  • 크기 계층(size-tiered)컴팩션은 상대적으로 작은 SS테이블을 상대적으로 오래된 큰 SS테이블에 병합한다.
  • 레벨 컴팩션은 키 범위를 더작은 SS테이블로 나누고 오래된 데이터는 개별 "레벨"로 이동시켜 컴팩션을 점진적으로 진행한다.

B 트리

B 트리는 대부분의 RDB에서 사용되는 인덱스 구조로 LSM 인덱스 방식와 상당히 다르다.

B 트리도 SS테이블과 동일하게 키로 정렬된 키-값 쌍을 유지하지만 공통점은 이게 전부이고 설계 철학이 매우 다르다.

• LSM트리 기반 DB는 일반적으로 수 MB이상의 가변 크기를 가진 세그먼트로 나누고 항상 순차적으로 세그먼트를 기록한다.
• 반면 B 트리는 전통적으로 고정된 크기(4KB)의 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 한다.

각 페이지는 주소나 위치를 이용해 식별할 수 있고 하나의 페이지가 여러 키와 하위 페이지를 참조할 수 있다(메모리가 아닌 디스크에 있을 뿐 포인터와 비슷하다.)

한 페이지는 B 트리의 root로 지정되고 인덱스에서 키를 찾으려면 루트에서 시작하여 참조된 하위 페이지로 이동하여 최종적으로 개별키를 포함한 리프(leaf) 페이지에 도달한다.

• B 트리의 한 페이지에서 하위 페이지를 참조하는 수를 분기 계수(branching factor)라고 부르며 보통 수백 개에 달한다.

키의 값 갱신 및 새로운 키 저장하기

• B 트리에 존재하는 키의 값을 갱신하려면 키를 포함하고 있는 리프 페이지를 검색하고 페이지의 값을 바꾼 다음 페이지를 디스크에 다시 기록한다.
• 새로운 키를 추가하려면 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가하면 된다.
  • 만약 해당 페이지에 여유 공간이 없다면 아래 사진과 같이 해당 페이지를 반쯤 채워진 페이지 둘로 나누고 상위 페이지가 새로운 키 범위의 하위 부분들을 알 수 있게 참조를 갱신한다.

• 키 추가 알고리즘은 트리가 계속 균형을 유지하는 것을 보장하므로 깊이가 항상 O(logN)이다.
• 대부분 DB는 B 트리의 깊이가 3이나 4단계면 충분하므로 검색하려는 페이지를 찾기 위해 많은 페이지 참조를 따라가지 않아도 된다.
  • 분기 계수 500의 4KB 페이지의 4단계 트리는 256TB까지 저장 가능하다.

신뢰할 수 있는 B 트리 만들기

• B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓴다.
  • LSM 트리 방식는 한번 쓰여진 데이터는 변경되지 않고 계속해서 추가만 되기 때문에 매우 대조적이다.
• 삽입으로 인한 페이지 분리와 같은 동작은 여러 페이지의 덮어쓰기를 필요로 한다.
  • 분할된 두 페이지를 기록하고 두 하위 페이지의 참조를 갱신하게끔 상위 페이지를 덮어쓰기 해야 함.
• 일부 페이지만 기록하고 DB가 고장나면 결국 인덱스가 훼손되므로 매우 위험한 동작이다.
• DB 고장에 스스로 복구 가능하도록 일반적으로 디스크 상에 쓰기 전 로그(write-ahead log. WAL)를 추가하여 B 트리를 구현한다.
• 같은 자리에 페이지를 갱신하기 때문에 동시성 제어가 필요하고 보통 래치를 활용한다.
  • LSM 트리 방식은 데이터가 불변하므로 동시성 제어가 따로 필요하지 않다.

B 트리 최적화

• 페이지에 전체 키가 아닌 키를 축약해서 공간을 절약한다.
  • 키 범위 사이의 경계만 표현하는데 문제만 없다면 키를 축약할 수 있어 높은 분기 계수를 얻을 수 있다.(흔히 B+ 트리라고 함)
• 키 범위가 가까운 값을 가지는 리프 페이지들을 디스크 상에 연속된 순으로 배치하려고 시도하여 효율적으로 디스크 탐색을 가능하도록 한다.
  • 트리가 커질 수록 순서를 유지하는데 어렵다.
  • LSM 트리는 병합 시 연속된 키 순으로 세그먼트를 다시 쓰기 때문에 연속된 키를 서로 가깝게 유지하기 쉽다.
• 각 리프 페이지의 양쪽 형제에 대한 참조를 가지도록 하여 상위 페이지로 이동하지 않고 순서대로 스캔이 가능하게 한다.

B 트리 vs LSM 트리

• B 트리가 LSM 트리보다 일반적으로 구현 성숙도가 높으나 LSM 트리의 성능 특성으로 인해 관심이 많아졌다.
• 저자 경험으로 LSM 트리는 보통 쓰기에서 더 빠르고, B 트리는 읽기에서 더 빠르다고 여긴다.
  • 읽기가 보통 LSM 트리에서 더 느린 이유는 각 컴팩션 단계에 있는 여러 가지 데이터구조와 SS테이블을 확인해야 하기 때문이다.
• 정확한 비교를 위해선 실제로 필요한 작업부하로 시스템을 테스트해봐야 한다.

LSM 트리의 장점

• LSM 트리는 보통 B 트리보다 쓰기 처리량을 높게 유지할 수 있다.
  • B 트리는 모든 데이터 조각을 최소한 두 번 기록해야 한다. 쓰기 전 로그에 한 번, 트리 페이지에 한 번이다.
  • LSM 트리 인덱스 또한 SS테이블의 반복되는 컴팩션과 병합으로 인해 여러 번 데이터를 다시 쓴다.
  • DB 쓰기 한 번에 의해 여러 번의 쓰기를 야기하는 효과를 쓰기 증폭(write amplification)이라 한다.
  • LSM 트리 방식이 B 트리에 비해 쓰기 증폭이 더 낮기 때문에 쓰기 효율이 뛰어나다.
• LSM 트리는 압축률이 좋아 보통 B 트리보다 디스크에 더 적은 파일을 생성한다.
  • B 트리는 구조상 고정된 페이지를 사용하므로 파편화가 발생한다.
  • LSM 트리는 고정된 페이지가 아닌 가변크기의 세그먼트를 사용하고 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하기 때문에 저장소 오버헤드가 더 낮다.

LSM 트리의 단점

• 컴팩션 과정이 때로는 진행 중인 읽기와 쓰기 성능에 영향을 준다.
  • 저장소 엔진은 컴팬션을 점진적으로 수행하고 동시 접근의영향이 없게 수행하려 한다.
  • 하지만 디스크가 가진 자원은 한계가 있다. 그래서 디스크에서 비싼 컴팩션 연산이 끝날 때까지 요청이 대기해야 하는 상황이 발생할 수 있다.
  • 이로 인해 평균 응답 시간 성능에 영향은 적으나 상위 백분위(p95, p99, p999) 응답 시간은 때때로 꽤 길다.
• 컴팩션이 많은 디스크 대역폭을 사용해 높은 쓰기 처리량에 영향을 준다.
  • 초기 쓰기(logging)과 멤테이블을 디스크로 방출과 백그라운드에서 수행되는 컴팩션 스레드가 유한한 쓰기 디스크 쓰기 대역폭을 공유해야 한다.
  • DB가 점점 커질 수록 컴팩션에 더 많은 디스크 대역폭이 필요해진다.
• 컴팩션 설정이 적절하지 않아 유입 쓰기 속도를 따라갈 수 없다면 디스크 상에 병합되지 않은 세그먼트 수는 디스크 공간이 부족할 때까지 증가한다
  • 확인해야 할 세그먼트도 늘어나니 읽기 성능에도 영향을 준다.
  • 보통 이런 상황에 대해 자동으로 속도를 조절하는 기능이 없으므로 명시적인 모니터링이 필요하다.
• 강력한 트랜잭션 시맨틱을 제공하기 어렵다.
  • B 트리는 각 키가 색인의 딱 한 곳에만 존재하지만 LSM 트리는 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있다.

기타 색인 구조

• B 트리, LSM 트리는 키-값 색인에 사용할 수 있다. 키-값 색인의 대표적인 예는 관계형 모델의 PK 색인이다.
• 하지만 LSM 트리, B 트리를 보조 색인(secondary index)으로 사용하는 방식도 매우 일반적이다. 보조 색인은 키-값 색인에서 쉽게 생성할 수 있다.
  • 보조색인과 PK와의 주요 차이점은 키가 고유하지 않다는 점이다.

인덱스 안에 값 저장하기

• 인덱스에서 키는 질의가 검색하는 대상이지만 값은 다음 두가지 중에 하나에 해당한다.
  • 실제 로우
  • 다룬 곳에 저장된 로우를 가르키는 참조
• 후자의 경우 로우가 저장된 곳을 힙 파일이라고 하며 특정 순서 없이 데이터를 저장한다.
  • 힙 파일 접근법은 여러 보조 색인이 존재할 때 데이터 중복을 피할 수 있으므로 일반적인 방식이다.
• 색인에서 힙 파일로 다시 이동하는 일은 읽기 성능에 불이익이 많으므로 어떤 상황에서는 인덱스안에 바로 로우를 저장하는 편이 바람직하다. 이를 클러스터드 색인이라고 한다.
  • MYSQL의 InnoDB에서는 테이블의 PK가 언제나 클러스터드 색인이고 보조 색인은 힙 파일의 위치가 아닌 기본키를 참조한다.
• 클러스터드 색인(인덱스 안에 모든 로우 데이터를 저장)과 비클러스터드 색인(인덱스 안에 데이터의 참조만 저장) 사이의 절충안을 커버링 인덱스라고 하는데 이 색인은 색인 안에 테이블의 컬럼 일부를 저장한다.
  • 이렇게 하면 색인만 사용해 일부 질의에 응답하는가능하며 이런 경우를 인덱스가 질의를 커버했다고 말한다.

모든 종류의 데이터 복제와 마찬가지로 클러스터드 인덱스와 커버링 인덱스는 읽기 성능을 높일 수 있지만 추가적인 저장소가 필요하고 쓰기 과정에 오버헤드가 발생한다.

다중 컬럼 인덱스

• 다중 컬럼 인덱스의 가장 일반적인 유형은 결합 인덱스로 하나의 키에 여러 필드를 단순히 결합한다.
• 인덱스는 순서가 정렬되어 있기 때문에 해당 인덱스를 사용하기 위해선 첫번째에 위치한 인덱스가 반드시 사용되어야 한다.

인메모리 DB

• 위에서 설명된 모든 데이터 구조는 모두 디스크 한계에 대한 해결책이었다.
• 램의 가격이 저렴해지고, 여러 장비간 분산 저장이 가능한 시스템들이 확산되면서 인메모리 DB가 개발되었다.
• 인메모리 DB는 재시작 시 보통 디스크나 네트워크를 통해 데이터를 다시 적재해야 한다.
• 보통 인메모리 DB는 지속성을 위해 추가 전용 로그를 디스크에 기록한다.
  • 레디스는 비동기로 디스크에 기록하므로 약한 지속성을 제공한다.
• 인메모리 DB 성능 장점이 디스크에서 읽지 않아도 된다는 사실이 아니라 디스크에 기록하기 위한 형태로 부호화하는 오버헤드를 피할 수 있어서 일 수도 있다.

OLTP와 OLAP(데이터 웨어하우스)

일반적인 애플리케이션은 인덱스를 이용해 일부 키에 대한 적은 수의 레코드를 찾고, 레코드는 사용자 입력을 기반으로 삽입되거나 갱신된다. 이런 대화식 애플리케이션들의 접근 패턴을 OLTP(online transaction processing)이라고 한다.

애플리케이션은 OLTP이외에도 비즈니스 분석가가 비즈니스 의사결정을 돕기 위한 보고서(business intelligence)를 제공한다. 이런 데이터베이스 사용 패턴을 트랜잭션 처리와 구별하기 위해 OLAP(online analytic processing)라고 부른다.

• OLAP를 위한 개별 데이터베이스를 데이터 웨어하우스(data warehouse)라고 부른다.

OLTP와 OLAP 특성 비교

특성	트랜잭션 처리 시스템(OLTP)	분석 시스템(OLAP)
주요 읽기 패턴	쿼리당 적은 수의 레코드, 키 기준으로 쿼리	많은 레코드에 대한 집계
주요 쓰기 패턴	임의 접근, 사용자 입력을 낮은 레이턴시로 기록	대규모 불러오기 또는 이벤트 스트림
주요 사용처	웹 애플리케이션을 통한 최종 사용자/소비자	의사결정 지원을 위한 내부 분석가
데이터 표현	데이터의 최신 상태	시간이 지나며 일어난 이벤트 이력
데이터셋 크기	기가이트 ~ 테라바이트	테라바이트 ~ 페타바이트

데이터 웨어하우징

• OLTP 시스템은 대개 비즈니스 운영에 매우 중요하므로 일반적으로 높은 가용성과 낮은 지연 시간의 트랜잭션 처리를 기대한다. 그러므로 OLTP 데이터베이스 시스템은 철저하게 보호되어야 한다.
• 반대로 데이터 웨어하우스는 분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터 베이스이다.
• 데이터는 OLTP 데이터베이스에서 추출(extract)하고 분석 친화적인 스키마로 변환(transform)하고 정리한 후 데이터 웨어하우스에 적재(load)한다.
  • 이러한 과정을 ETL(Extract-Transform-Load)이라고 부른다.
• 분석을 위해 OLTP 시스템이 아닌 개별 데이터 웨어하우스를 사용하는 큰 장점은 분석 접근 패턴맞게 최적화할 수 있는 것이다.
• 위에서 설명했던 인덱스 알고리즘들은 OLTP에서는 잘 동작하지만 분석 질의 응답에는 별로 좋지 않은 편이다. 분석 질의 응답에 최적화되는 저장소 엔진을 살펴보자.

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

• 표면적으로 둘 모두 SQL 질의 인터페이스를 지원하기 때문에 비슷해 보이지만 각각 매우 다른 쿼리 패턴에 최적화되어 있기 때문에 시스템 내부는 완전히 다르다.
  • 다수의 DB Vendor는 트랜잭션 처리와 분석 작업부하 모두를 지원하기 보다 둘 중 하나를 잘 지원하는데 중점을 두고 있다.
  • 데이터 웨어하우스 시스템의 대표적인 예로 Apache Hive, Spark SQL, Facebook Presto 등이 있다.

정리

고수준에서 저장소 엔진은 트랜잭션 처리 최적화(OLTP)와 분석 최적화(OLAP)라는 큰 두 가지 범주로 나눈다.

• OLTP 시스템은 보통 사용자 대면이기 때문에 대량의 요청을 감당할 수 있고 쿼리마다 일부 키에 대한 작은 수의 레코드를 다룬다.
  • 일부 키에 대한 데이터를 찾기 위한 인덱스를 사용하고 이 경우 대개 디스크 탐색이 병목이 된다.
• OLAP 시스템은 최종 사용자가 아닌 비즈니스 분석가가 주로 사용하며 OLTP 시스템보다 각 쿼리는 매우 많은 레코드들을 스캔해야 한다.
  • 이 경우 일반적으로 디스크 탐색이 아닌 디스크 대역폭이 병목이된다.

OLTP 측면에서 LSM 트리와 B 트리 방식을 살펴봤다.

• LSM 트리 관점에선 파일에 추가와 오래된 파일의 삭제만 허용하고 한 번 쓰여진 파일은 절대 갱신하지 않는다.
  • 카산드라, HBase, 루씬등이 이 그룹에 속한다.
• B 트리 관점에선 덮어쓰기 할 수 있는 고정 크기 페이지의 셋으로 디스크를 나눈다.
  • B 트리는 모든 주요 관계형 데이터베이스와 많은 비정형 데이터베이스에서도 사용한다.

애플리케이션 개발자가 저장소 엔진의 내부에 대한 지식이 있다면 특정 애플리케이션에 어떤 도구가 적합한지 판단하기 유리하다.

데이터베이스 파라미터 조정이 필요하다면 이런 이해는 설정 값이 가지는 효과가 무엇인지 상상할 수 있게 해준다.