[데이터 중심 애플리케이션 설계] 3. 저장소와 검색

개요

데이터베이스의 기능

DB 의 가장 기본적인 기능은 데이터를 저장(set)하고, 조회(get)하는 것이다.

3장의 내용

3장에서는 데이터베이스 엔진의 get, set 동작을 설명한다.

이 장에서는 다음의 것들을 알아본다.

• RDB, NoSQL DB 에 사용되는 엔진
• 로그 구조(log-structured) 계열 저장소 엔진
• 페이지 지향(paged-oriented) 계열 저장소 엔진

애플리케이션 개발자한테 DB 엔진 이해가 필요한 이유

애플리케이션 개발자가 특정 작업부하(workload) 유형에서 좋은 성능을 내게끔 적합한 저장소 엔진을 선택하고, 튜닝하기 위해선 저장소 엔진의 동작 방식을 이해할 필요가 있다.

특히, 다음 두 엔진에 대해선 구분하고 사용할 줄 알아야한다.

• 트랜잭션 작업부하에 최적화된 저장소 엔진
• 분석을 위해 최적화된 엔진

본문

로그(log)

• 추가 전용(append-only) 데이터를 로그 라고 부른다.
• 쓰기시 append 방식은 매우 효율적이다.
• 많은 데이터베이스에서 log 를 사용한다.

인덱스(index)

• full search 는 시간 복잡도가 O(n) 이다.
• full search 를 피하고 좀 더 빠른 조회를 위해 인덱스를 사용한다.
• 인덱스는 기본 데이터(primary data)에서 파생된 추가적인 구조.
• 인덱스는 읽기는 빠르게 하지만 쓰기는 느리게 하는 트레이드 오프가 있다.

해시 인덱스

데이터의 key 에 바이트 오프셋 인덱스를 맵핑하여 해시맵에 유지.

단순해보이지만 읽기, 쓰기가 고성능이며, 실제로 비트캐스크(Bitcaks)에서 사용.
단, 메모리에 안에 모든 키가 들어갈 수 있어야 함.

로그 방식의 쓰기와 해시 인덱스를 사용하는 것이 적절한 경우

• 키는 많지 않고, 같은 키에 대한 갱신이 많은 경우.

세그먼트와 컴팩션

파일에 계속 추가하다보면 결국 디스크가 부족해진다.
이를 해결하기 위해, 세그먼트(segment) 단위로 로그를 나누어 저장하고, 지난 세그먼트는 컴팩션(compaction)을 수행한다. 컴팩션은 같은 키에 대해 최신 값만 남기는 것이다.

컴팩션을 수행할 때, 동시에 여러 세그먼트를 병합할 수 있다.

각 세그먼트는 해시 인덱스를 가진다. 키의 값을 찾으려면 최신 세그먼트부터 해시 인덱스를 조회하여 찾는다. 없으면 다음 세그먼트의 해시 인덱스를 조회한다.

append-only의 장점

• append 와 세그먼트 병합은 순차적인 쓰기(sequential write) 를 사용하는데 보통 무작위 쓰기(random write) 보다 빠르다. 특히 HDD 에서 그렇다.
• 세그먼트 파일이 추가 전용이고 불변이면 동시성 제어(concurrency control)와 고장 복구(crash recovery) 문제는 간단해진다.

해시 인덱스의 한계

• 해시맵을 메모리에 저장해야하므로 키가 너무 많으면 문제가 된다.
• 해시맵은 범의 질의(range query)에 효율적이지 않다. 범위에 해당하는 모든 키를 개별 조회해야한다.

SS 테이블과 LSM 트리

해시 인덱스의 한계가 없는 인덱스 구조를 살펴본다.

SS테이블 방식은 세그먼트를 정렬된 형태로 저장하며, 모든 키가 아닌 희소한 키에 대해서만 인메모리 인덱스를 갖는다. 이를 통해, 메모리 크기의 제한을 극복한다.

sequential write 방식은 나중에 쓰여진 로그가 이전의 값보다 우선된다. 근데 방식에 로그를 키로 정렬할 수 있을까?

SS테이블(Sorted String Table)
키로 정렬된 형식의 세그먼트를 의미한다.
각 키는 병합된 세그먼트 파일 내에 한 번만 나타나야 한다.

SS테이블의 장점

• 병합정렬(mergesort) 알고리즘을 사용하여 세그먼트 컴팩션/병합이 간단하고 효율적이다.
• 메모리에 모든 키의 인덱스를 유지할 필요가 없다. 로그가 정렬돼있으므로 희소 인덱스(sparse index)만 보유해도 된다.
• sparse index 에 나타나지 않은 키들을 오프셋키와 한 그룹으로 묶고 압축하여 디스크에 저장한다. 이로 인해 디스크 공간을 절약하고 I/O 대역폭 사용을 줄인다.
• 정렬돼있으므로 range query 에 좀 더 효율적이다.

SS테이블 생성과 유지

멤테이블(memtable) 을 사용한다.

• 정렬된 구조를 디스크보단 메모리에 유지하는 편이 더 쉽다.
• 레드 블랙 트리(red-black tree)나 AVL 트리와 같은 균형 트리(balanced tree) 구조를 사용한다. 임의 순서로 삽입한다 해도 정렬된 순서로 해당 키를 읽을 수 있다.
• 인메모리 균형 트리를 맴테이블이라고 한다.

저장소 엔진을 다음과 같이 만들 수 있다.

• 인메모리 균형 트리 데이터 구조에 로그를 추가한다.
• 맴테이블이 보통 수 메가바이트 정도의 임곗값보다 커지면 SS테이블 파일로 디스크에 기록한다. 기록된 SS테이블이 가장 최신의 세그먼트가 된다. SS테이블을 디스크에 기록하는 동안, 새로운 맴테이블 인스턴스에 쓰기를 수행한다.
• 읽기 요청을 위해 맴테이블에서 키를 찾는다. 그 다음부터 새로운 순으로 세그먼트를 조회하면서 키를 찾는다.
• 백그라운드에서 세그먼트의 컴팩션/병합이 이루어진다.

맴테이블 동작의 한계

• 맴테이블이 디스크에 쓰이기 이전에 DB 가 고장나면 데이터가 손실될 수 있다.

이를 해결하기 위해, 맴테이블에 쓰는 동작과 디스크에 로그를 남기는 동작을 함께한다. 이 디스크에 남겨지는 로그는 복구시에만 사용되므로, 정렬될 필요는 없다. 맴테이블이 성공적으로 SS테이블로 쓰여지면 해당 로그들은 버려도 괜찮다.

LSM 트리

LevelDB, RocksDB, 카산드라, HBase, Lucene(루씬) 에서도 이러한 SS테이블과 sparse 인덱스를 사용하는 저장소 엔진을 사용한다.

이러한 인덱스 구조는 LSM 트리(Log-Structured Merge-Tree) 란 이름으로 발표됐다.

정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진 이라고 부른다.

LSM 저장소 엔진 최적화

저장소 엔진은 보통 블룸 필터(Bloom filter) 추가적으로 사용해서, 존재하는 키인지 빠르게 반환한다.

SS테이블을 압축하고 병합하는 순서와 시기를 결정하는 전략
1. 크기 계층(size-tiered) : HBase, 카산드라
2. 레벨 컴팩션(leveled compaction) : LevelDB, RocksDB. 카산드라

B 트리

SS테이블과 공통점

• 정렬된 키-값 쌍을 유지하기 때문에, 범의 질의에 효율적이다.

SS테이블과 차이점

• SS테이블은 세그먼트의 크기가 가변적이고 순차적으로 세그먼트를 기록한다. 반면, B트리는 4KB 고정 크기의 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 한다. 디스크가 고정 크기 블록으로 배열되기 때문에 이런 설계는 근본적으로 하드웨어와 조금 더 밀접한 관련이 있다.
• LSM 엔진은 데이터를 추가만하기에 같은 위치의 파일은 변경하지 않으나, B 트리는 같은 위치의 페이지를 덮어쓴다.

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

어떤 페이지와도 부모 관계가 없는 페이지를 고아 페이지(orphan page)라고 한다. 가령, 데이터 삽입 됐는데, 페이지의 여유 공간이 부족하면 페이지를 나누고 상위 페이지에 새로운 페이지에 대한 참조값도 삽입해주어야 한다. 허나, 페이지 분리만 이루어지고 상위 페이지를 갱신하지 못하고 데이터 베이스가 고장난다면 고아 페이지가 발생할 수 있다.

데이터베이스가 고장 상황에서 스스로 복구할 수 있게 만드려면, 디스크 상에 쓰기 전 로그(write-ahead log, WAL) (재실행 로그(redo log) 라고도 함) 가 필요하다. 이 로그는 데이터베이스 고장 이후 B 트리를 다시 복원하는 데 사용한다.

같은 자리의 페이지를 갱신하면, 다중 스레드가 동시에 B트리에 접근할 때, 동시성 제어가 필요하다.

B 트리와 LSM 트리 비교

LSM 트리는 보통 쓰기에 빠르고, B 트리는 읽기에 더 빠르다고 여긴다.

LSM 트리가 느리다고 여겨지는 이유는 컴팩션 단계에 있는 여러 가지 데이터 구조와 SS테이블을 확인해야하기 때문이다.

하지만 작업부하의 세부사항에 민감하므로 실제 필요한 작업부하로 시스템을 테스트해봐야 한다.

LSM 트리의 장점

B 트리 인덱스는 모든 쓰기가 최소 두 번 기록해야 한다.

• WAL 로그
• 페이지 기록
• 페이지 분리는 추가적인 쓰기를 요구한다.

LSM 인덱스 또한 SS 테이블의 반복된 컴팩션과 병합으로 인해 데이터를 다시 쓴다.

쓰기 증폭(write amplification) : DB 쓰기 한 번이 DB 수명 동안 디스크에 여러 번의 쓰기를 야기하는 효과
SSD 는 수명이 다할 때까지 블록 덮어쓰기 횟수가 제한되기 때문에 SSD 에선 중요한 관심사이다.

보통 LSM 트리는 B 트리보다 쓰기 처리량을 높게 유지할 수 있다. LSM 트리가 상대적으로 쓰기 증폭이 더 낮고 트리에서 여러 페이지를 덮어쓴느 것이 아니라 순차적을 컴팩션된 SS테이블 파일을 쓰기 때문이다.

LSM 트리는 압축률이 더 좋다. B 트리는 파편화로 인해 사용하지 않는 디스크 공간 일부가 남는다. 페이지의 일부 공간은 사용하지 않을 수 있다. 반면, LSM 트리는 SS테이블에 다시 기록하기 때문에 저장소 오버헤드가 더 낮다.

SSD 의 경우 낮은 쓰기 증폭과 파편화 감소의 효과가 더 좋기 때문에 내부적으로 LSM 알고리즘을 사용하는 것이 유리할 수 있다. 대다수의 SSD 펌웨어는 내장 저장소 칩에서 임의 쓰기를 순차 쓰기로 전환하기 위해 LSM 알고리즘을 사용한다.

LSM 트리의 단점

컴팩션이 진행 중인 읽기와 쓰기 성능에 영향을 준다. 컴팩션 연산이 끝날 때까지 요청이 대기해야 하는 상황이 발생하기 쉽다.

컴팩션으로 인해 높은 쓰기 처리량이 발생한다. 이로 인해 디스크의 높은 쓰기 대역폭을 필요로 할 수 있다. 초기 쓰기(logging)와 멤테이블의 방출(flushing)과 컴팩션 스레드가 이 대역폭을 공유해야 한다.

컴팩션이 유입 쓰기(logging) 속도를 따라갈 수 있도록 주의 깊은 컴팩션 설정이 요구된다. 그러지 않으면 병합되지 않은 세그먼트 수가 디스크 공간이 부족할 때까지 증가한다.

트랜잭션 시멘틱을 제공하기 까다롭다. B 트리의 장점은 각 키가 인덱스의 한 곳에만 정확하게 존재한다는 점이다. 반면 LSM 엔진은 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있다. 많은 관계형 DB 는 트랜잭션 격리(transaction isolation)는 키 범위의 잠금을 사용하고, B 트리 인덱스에서는 트리에 잠금을 포함시키기도 한다.

다른 인덱스 구조

primary index(기본키 인덱스)

• 기본키로 RDB에서 하나의 로우를, 문서DB 에서는 하나의 문서를, 그래프DB 에서는 하나의 정점을 고유하게 식별한다.

secondary index(보조 인덱스)

• RDB 에서 CREATE INDEX 명령을 사용해 같은 테이블에 다양한 보조 인덱스를 생성할 수 있다.
• 효율적인 조인을 수행하는 데 도움을 준다.
• primary index 와의 차이점
  • 키가 고유하지 않아서, 같은 키를 가진 많은 로우(문서, 정점)가 있을 수 있다.
• B트리 엔진이나 LSM 엔진이나 모두 사용할 수 있다.

clusterd index

인덱스에서 값은 다음 두가지 중 하나에 해당한다.

1. 실제 데이터(로우/문서/정점) : clusterd index
2. 참조 : nonclusterd index

후자의 경우 로우가 저장된 곳을 힙 파일(heap file)이라 하고 특정 순서 없이 데이터를 저장한다. 힙 파일 접근은 일반적인 방식인데, 여러 보조 인덱스가 있는 경우 데이터 중복을 피할 수 있기 때문이다.

힙 파일 접근 방식은 바이트 오프셋을 변경하지 않을 때 효율적이다. 갱신해야할 새로운 값이 이전 값보다 더 많은 공간을 필요로 한다면 힙에서 새로운 곳으로 위치를 이동하고, 모든 인덱스가 새로운 힙 위치를 가리키게끔 갱신하거나, 이전 힙 위치에 새로운 힙 위치 포인터를 남겨두어야 한다.

첫 번째 방식을 clustered index(클러스터드 인덱스) 라고 한다. 힙 파일로 이동할 필요가 없어 읽기 성능이 더 좋다.

• 예시
  • MySQL의 InnoDB 엔진은 primary index 가 clustered index 이고 secondary index 가 non_clustered index 이다.

covering index(커버링 인덱스) 는 clusterd index 와 nonclustered index 의 절충안이 된다. 인덱스 안에 테이블 칼럼의 일부를 저장한다. 모든 로우를 저장하는 clusterd index 와는 달리 일부만을 저장하여, 일부 질의에만 인덱스로 응답이 가능하다.

clustered/covering index 는 읽기 성능은 높이지만 추가적인 저장소가 필요하고 쓰기 과정에 오버헤드가 발생한다. 복제로 인한 불일치(inconsistency)를 해소하기 위해 DB는 트랜잭션 보장해야 한다.

multi-colum index

지금까지의 인덱스는 하나의 키만 값에 대응한다. 이 방식은 테이블의 다중 컬럼에 동시에 질의를 해야 한다면 충분하지 않다.

concatenated index(결합 인덱스) 하나의 컬럼에 다른 컬럼 포인터를 추가하는 방식이다. 첫 번째 컬럼부터 순서대로 포함 시킨 질의를 커버할 수 있다. 컬럼별로 정렬돼있어서 범위 쿼리를 커버할 수 있다. 이전 컬럼을 포함시키지 않은 질의는 커버하지 못한다.

인메모리 DB

Redis 는 우선순위 큐와 셋 같은 다양한 데이터 구조를 DB 같은 인터페이스로 제공한다.

안티 캐싱(anti-caching) 은 메모리가 충분하지 않을 때 가장 최근에 사용하지 않은 데이터를 메모리에서 디스크로 내보내고 나중에 다시 접근할 때 메모리에 적재하는 방식이다. 이 방법을 통해 인메모리 DB 가 가용한 메모리보다 더 큰 데이터셋을 지원하게 할 수 있다.

트랜잭션 처리 vs 분석

OLTP(online transaction processing, OLTP) DB 접근 패턴

• 인덱스를 사용해 일부 키에 대한 적은 수의 레코드를 찾는다.
• 레코드는 사용자 입력을 기반으로 사입되거나 갱신된다.
• 이런 대화식의 DB 접근 패턴

OLAP(online analytic processing) DB 접근 패턴

• 많은 수의 레코드를 스캔하되, 레코드 중 일부 칼럼만 읽고 집계 통계를 계산한다.
• ETL(or bulk import), 이벤트 스트림으로 쓴다.

198O년대 후반부터 OLTP 시스템이 아닌 개별 DB에서 OLAP 하는 경향을 보였다. 이런 개별 DB를 데이터 웨어하우스(data warehouse) 라고 한다.

데이터 웨어하우스

즉석 분석 질의(ad hoc analytic query)를 OLTP DB 실행하는 것은 지양하는 편이다. OLTP 는 비즈니스 운영에 굉장히 직접적이고 중요하기에 높은 가용성고 낮은 지연 시간의 트랜잭션 처리를 기대한다. 그런 시스템에 비용이 비싼 편인 즉석 분석 질의를 수행하는 것은 트랜잭션의 성능을 저하시킬 가능성이 있다.

데이터 웨어하우스는 분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스다. 대게 OLTP 시스템에서 ETL(Extract-Transform-Load) 과정을 통해 얻어낸 읽기 전용 복사본이다.

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

SQL은 일반적으로 분석 질의에 적합하기 때문에, 데이터 웨어하우스의 가장 일반적인 관계형 모델을 사용한다.

하지만, 각각 매우 다른 질의 패턴에 맞게 최적화됐기 때문에 시스템의 내부는 완전히 다르다.

분석용 스키마: star and snowflake schema

OLAP 에서는 데이터 모델의 다양성이 비교적 적다. star 스키마 로 알려진 정형화된 방식을 사용한다.

사실(fact) 테이블이 가운데 있고 6하원칙을 나타내는 차원(dimension) 테이블이 외래키로 연결된다.

snowflake 스키마 는 star 스키마보다 차원이 하위 차원으로 더 세분화된다.

컬럼 지향 저장소(Column-Oriented Storage)

보통 분석용 쿼리는 모든 컬럼의 데이터가 필요하지 않다.

대부분의 OLTP DB의 저장소는 한 로우의 모든 값이 인접하게 저장되는 row-oriented 방식으로 데이터를 배치한다. 문서 DB 도 전체 문서를 하나의 연속된 바이트 열로 저장한다.

column-oriented 저장소는 각 컬럼별로 모든 값을 함께 저장한다. 로우는 각 컬럼 파일에서 같은 순서에 있는 값들을 모아서 만든다.

컬럼 압축

데이터를 압축하면 디스크 처리량을 더 줄일 수 있다.

다양한 압축 기법 중 bitmap encoding 은 데이터 웨어하우스에서 특히 효과적이다.

보통 컬럼의 고육값(distinct)은 로우수보다 적다. 고유값마다 비트맵을 지정한다. 비트맵은 로우가 고유값을 가지면 1로 표시한다. 1의 비트를 가지는 경우는 희소(sparse)하므로 run-length encoding 으로 효과적으로 비트맵의 길이를 압축할 수 있다.

이후 비트맵을 이용한 처리를 할때도 비트 연산으로 더욱 효율적으로 계산을 수행할 수 있다고 한다.

벡터화 처리

vectorized processing 을 활용하면 CPU 캐시를 더욱 효율적으로 사용할 수 있다.
CPU L1 캐시에 딱 맞게 덩어리로 메모리에서 데이터를 가져온다. 데이터에 컬럼 압축을 사용하면 더 많은 로우를 가져올 수 있다. 비트 AND, OR 연산자를 사용하면 압축된 컬럼 데이터에서 바로 연산을 수행할 수 있다. 이런 기법을 vectorized processing 이라고 한다.

column-oriented 저장소의 순서 정렬

순서정렬을 하면 같은 값이 연속해서 등장하므로 run-length encoding 압축 효율을 높인다.

colum-oriented 저장소의 순서 정렬은 기본적으로 하나의 1차 정렬키를 선택해서 정렬한다. 추가적으로 보조 정렬키를 설정할 수 있다.

자주 사용될 공통 질의를 예상하여 1차 정렬키를 선택해야 한다.

다양한 정렬

colum-oriented 저장소에서 다양한 순서 정렬이 필요하다면, 다른 정렬키를 샤옹해서 데이터를 복제 저장하는 방법을 사용할 수 있다.

row-oriented 의 secondary index 를 사용하는 것과 근본적인 차이는, row-oriendted 에선 값이 포인터지만, column-oriented 에선 실제 값을 저장한다.

쓰기

colum-oriented, 압축, 정렬은 데이터 웨어하우스를 대량의 읽기 전용 질의에 강점을 보이게 하지만, 쓰기는 어렵게 한다.

B 트리 처럼 update-in-place 접근 방식이 압축된 컬럼에서는 불가능하다. 중간에 삽입을 원하는 경우 모든 컬럼 파일을 재작성해야 한다. 로우는 컬럼파일들 안의 위치에 따라 식별되기 때문이다.

LSM 트리 방식을 사용하여 이를 해결할 수 있다. 균형 트리와 같은 인메모리 정렬 구조에 데이터를 추가한다. 충분한 쓰기가 모인 후 디스크로 flush 하고 compaction 한다.

집계: 데이터 큐브와 구체화 뷰

데이터 웨어하우스는 구체화 집계(materialized aggregate) 라는 특성을 보인다. 자주 사용되는 집계 연산을 캐싱 해두는 것이다.

집계 연산 결과를 캐시하는 view를 만드는 것이다. 데이터 웨어하우스에선 주로 실제 집계 결과를 복사하는 materialized view 를 제공한다. 반면, RDBS 에서는 query 를 복사해두는 virtual view 방식을 제공하는 편이다.

원본 테이블이 변경되면, materialized view 를 갱신해야 한다. 이런 갱신 쓰기는 비싸기 때문에 OLTP DB 에서는 materialized view 를 자주 사용하지 않는다. 반면 데이터웨어하우스는 꽤나 빈번하게 대규모 집계 쿼리를 사용하므로 materialized view 를 사용하는 것이 합리적인 편이다.

data cube 또는 OLAP cube 는 materialized view 의 special case 이다.

n개의 외래 key 로부터 n 차원 테이블을 만들고, 해당 컬럼 값으로 집계 대상 값을 기입한다. 이후 하나의 key 를 고정시킨 상태에서 집계 연산을 수행한다. 그리고 그 집계 연산 결과를 다시 집계한다.

이런 방법으로 빠르게 materialized view 를 갱신할 수 있다.

data cube 의 단점은 query 에 대한 유연성이 떨어진다는 것이다. 가령, 차원이 아닌 속성에 대해선 materialized 되어있지 않기 때문에 차원이 아닌 속성을 조건절로 하는 query 는 수행할 수 없다.

data cube 는 특정 query 에 대한 성능 향상에만 사용한다.