데이터 중심 어플리케이션 설계 - 3장. 저장소와 검색

학습 목표 : 데이터베이스가 데이터를 저장하는 방법과 데이터를 요청했을 때 다시 찾을 수 있는 방법을 알아본다. 다양한 인덱스 구조를 알아보고 여러 인덱스 구조를 비교해 본다. 

 

개발자는 어플리케이션에 맞는 저장소 엔진을 선택해야 한다. 트랜잭션 작업 부하에 맞춰 최적화된 저장소 엔진(페이지 지향 계열 저장소 엔진)과 분석을 위해 최적화된 엔진(로그 구조 계열 저장소 엔진)은 다르다. 

 

DB를 강력하게 만드는 데이터 구조

DB는 내부적으로 append-only(추가 전용) 데이터 파일(=로그)를 사용한다. 로그는 연속된 추가 전용 레코드를 의미한다. 

인덱스는 특정 키의 값을 효율적으로 찾기 위해 사용하는 데이터 구조로, 기본 데이터에서 파생된 부가적인 구조인 메타 데이터를 유지하는 것이다. 인덱스를 사용하면 데이터를 쓸 때마다 매번 인덱스를 갱신해야 하기 때문에 쓰기 과정에서 오버헤드가 존재한다. 이것은 개발자 고려해야 할 중요한 트레이드 오프이다. 좋은 인덱스는 읽기 쿼리 속도를 높이기 때문에 적절한 선택이 필요하다. 

 

해시 색인

사전 타입의 해시 맵으로 키-값 쌍으로 이루어져 있다.

• 단순히 파일에 추가하는 방식으로 데이터 저장소를 구성하면 간단하게 가능한 인덱스 전략
• 키를 데이터 파일의 오프셋에 매핑해서 인메모리 해시 맵을 유지하는 전략
• 파일에 새로운 키-값 쌍을 추가할 때마다 방금 기록한 데이터의 offset을 반영하기 위해서 해시 맵도 갱신해야 한다.
• 장점) 해시 맵을 전부 메모리에 유지한다. 그러다 보니 사용 가능한 램에 모든 키가 저장되고 고성능의 읽기와 쓰기가 가능해진다. 따라서 각 키의 값이 자주 갱신되는 상황에 매우 적합하다.
• 단점) 파일에 항상 추가만 하다보면 디스크 공간이 부족해지게 된다. 따라서 특정 크기의 세그먼트로 로그를 나누는 방식이 좋다. 세그먼트가 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행한다. 그리고 주기적으로 컴팩션을 수행해준다. 

*컴팩션 : 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지한다. 세그먼트를 작게 만들어주며 동시에 여러 세그먼트를 병합할 수도 있다. 세그먼트는 쓰여진 후에는 절대 변경되지 않는다. 따라서 병합할 세그먼트는 새로운 파일로 쓰게 된다. 고정된 세그먼트의 병합과 컴팩션은 백그라운드 스레드에서 수행한다. 병합 후 읽기 요청은 새로 병합한 세그먼트를 사용하게끔 전환하고, 전환 후에는 이전 세그먼트 파일을 삭제해 공간을 비운다. 

구현 시 고려 사항 

• 파일 형식 : csv 대신 byte 단위의 문자열 길이를 부호화 + 원시 문자열 부호화한 바이너리 형식
• 레코드 삭제 : 키 관련 값 삭제 시 특수 삭제 레코드(툼스톤)를 추가해야 한다. 세그먼트 병합 시 툼스톤은 병합과정에서 삭제된 키의 이전 값을 무시할 수 있다. 
• 고장 복구 : DB 재시작 시 인메모리 해시 맵이 손실된다. 따라서 빠른 복구를 위해 스냅샷을 디스크에 저장한다. 
• 부분적으로 레코드 쓰기 : 로그에 레코드를 추가하다가 DB가 죽을 수 있다. 이럴 때는 체크섬으로 손상된 부분을 탐지할 수 있다. 
• 동시성 제어 : 단일 쓰기 스레드를 통해서 쓰기를 엄격히 제어하고 데이터 세그먼트 파일은 추가 전용(불변)으로 만든다. 이렇게 하면 다중 스레드로 동시 읽기가 가능하다. 

추가 전용 로그의 장점

• 추가와 세그먼트 병합은 순차적인 쓰기 작업으로 무작위 쓰기보다 빠르다. 
• 추가 전용 세그먼트 파일은 불변하기 때문에 동시성과 고장 복구가 간단하다. 
• 오래된 세그먼트 병합은 시간이 지남에 따라 조각화되는 데이터 파일 문제를 피할 수 있다. 

해시 색인의 제한 사항

• 키가 너무 많으면 문제가 된다. (디스크에 맵을 유지할 수도 있지만 IO가 늘어나고 디스크가 꽉 차면 확장 비용이 크며, 해시 충돌 해소를 위한 로직이 복잡하다는 문제로 인해 성능이 떨어진다)
• 범위 질의에 효과적이지 못하다. 범위 내의 모든 키를 한 번에 스캔할 수 없기 때문에 모든 키를 개별로 조회해야 하기 때문이다. 

이런 제한이 없는 인덱싱 구조를 만들기 위해 등장한 것이 SS 테이블과 LSM 트리이다. 

SS테이블과 LSM 트리

해시 구조와의 공통점 : 로그 구조화 저장소 세그먼트로 키-값 쌍의 연속. 쓰여진 순서대로 나타난다. 로그에서 같은 키를 갖는 값 중 나중의 값이 이전 값보다 우선한다. 

SS 테이블은 키-값 쌍을 키를 기준으로 정렬한 문자열(Sorted String) 테이블이다. 

SS 테이블의 장점 

• 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적으로 진행한다. (병합 정렬과 유사한 방식)
• 파일에서 특정 키를 찾기 위해 모든 키의 인덱스를 메모리에 유지할 필요는 없다. (인덱스 내용이 드문드문 희소하게 들어감)
• 여러 키-값 쌍 레코드들을 블록으로 그룹화하여 디스크에 쓰기 전에 압축한다. 희소 인메모리 인덱스에는 각 블록의 시작을 가리키는 값들을 모아두면 디스크 공간을 절약하고 IO 대역폭 사용도 줄일 수 있다. 

SS 테이블의 생성과 유지 (데이터를 키로 정렬하는 방법)

디스크 상에 정렬된 구조를 유지해야 하지만 메모리에 유지하는 것이 더 쉽다. (레드 블랙 트리나 AVL 트리 등을 사용하면 된다)

저장소 엔진을 구성하는 방법은 다음과 같다 

• 쓰기가 들어오면 인메모리 균형 트리 데이터 구조(예를 들면 레드 블랙 트리 같은 것)에 추가한다. 이 균형 트리는 멤테이블이다. 
• 멤테이블이 임계값보다 크면 SS 테이블 파일로 디스크에 기록한다. 트리가 이미 키로 정렬되어 있기 때문에 효율적으로 이를 진행할 수 있다. 새로운 SS 테이블 파일은 데이터베이스의 가장 최신 세그먼트가 된다. SS 테이블을 디스크에 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록한다. 
• 읽기 요청 시 먼저 멤테이블에서 키를 탐색한다. 없으면 그 다음 디스크 상의 가장 최신 세그먼트를 탐색하고, 거기에도 없으면 두 번째 세그먼트를 탐색한다. 
• 종종 병합과 컴팩션을 백그라운드 스레드에서 수행한다. 

이러한 구성의 문제는 DB 고장 시 아직 디스크로 기록되지 않고 멤테이블에 남아 있는 가장 최신 쓰기가 손실될 수 있다는 것이다. 따라서 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지해야 한다. 해당 로그는 손상 후 멤테이블 복원에만 필요하기 때문에 순서 정렬이 불필요하다. 

SS 테이블에서 LSM 트리 만들기

로그 구조화 병합트리(log-structured merge-tree)는 SS 테이블 방식 인덱스를 사용한다. 

LSM 저장소 엔진 : 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진.

사용 사례 : 루씬(Lucene, 엘라스틱 서치나 솔라에서 사용하는 전문 검색 엔진용 색인)

성능 최적화

• 문제 1: DB에 아예 존재하지 않는 키를 찾을 때, 멤테이블부터 가장 오래된 세그먼트까지 거슬러 올라가서 찾아야 한다. 
    -> 블룸 필터를 사용해서 집합처럼 만들면 존재하지 않는 키를 찾는 비용을 절약할 수 있다. 
• 문제 2: SS 테이블 압축, 병합 순서와 시기를 결정하는 전략이 필요하다. 
   -> 크기 계층, 레벨 컴팩션 전략이 있다. 

 

B트리

로그 구조화 인덱스와는 다른, 가장 널리 사용되는 인덱스 구조이다. 

SS 테이블과의 공통점 : 키로 정렬된 키-값 쌍을 유지한다. 따라서 키-값 검색과 범위 질의에 효과적이다. 

저장 단위:

• SS 테이블 : 수 MB 이상의 가변 크기를 가진 세그먼트로 나누고 순차적으로 기록한다. 
• B트리 : 4KB 크기의 고정크기 블록이나 페이지로 나누고 한 번에 하나의 읽기 / 쓰기를 한다. 

B 트리의 특징

• 한 페이지는 B트리의 루트로 지정한다. (인덱스에서 키 검색 시 루트에서 시작한다)
• 페이지는 여러 키와 하위 페이지의 참조를 포함한다. 
• 각 하위 페이지는 키가 계속 이어지는 범위를 담당하고 참조 사이의 키는 해당 범위의 경계를 나타낸다. 
• 최종적으로 개별 키를 포함하는 리프(leaf) 페이지에 도달한다. 

분기계수(branching factor) : B트리의 한 페이지에서 하위 페이지를 참조하는 수. (실제로는 보통 수 백개에 달한다)

키의 값 갱신 방법 

1. 키가 존재하는 리프 페이지 검색
2. 페이지의 값 변경
3. 페이지를 디스크에 다시 기록 (페이지에 대한 모든 참조는 계속 유효하다)

새로운 키를 추가하는 방법 

1. 새로운 키를 포함하는 범위의 페이지를 찾는다
2. 해당 페이지에 키와 값을 추가
3. 만약 새로운 키를 수용한 페이지에 충분한 여유 공간이 없다면
4. 페이지 하나를 반쯤 채워진 페이지 둘로 나눈다
5. 상위 페이지가 새로운 키 범위의 하위 부분을 알 수 있게 갱신

이런 알고리즘을 통해 트리가 균형을 유지하도록 보장한다. n개의 키를 가진 B트리의 depth는 O(log n)이다. 

 

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

B트리의 쓰기 동작 : 새로운 데이터를 디스크 상의 페이지에 덮어쓴다. 페이지를 덮어써도 페이지를 가리키는 모든 참조는 온전히 남는다. 이는 파일에 추가만 할 뿐 같은 위치의 파일을 변경하지 않는 로그 구조화 인덱스와는 다른 점이다. 

하드웨어 동작과의 연관성 : 디스크의 페이지 뿐만 아니라서 여러 다양한 페이지 덮어쓰기가 필요한 만큼 하드웨어 동작과 연관성이 높다.
 

B트리로 발생할 수 있는 문제 

• 만약 페이지를 분할할 때 중도 오류가 발생 한다면 고아 페이지(어떤 페이지와도 부모관계가 없는 페이지)가 발생할 수 있다. 따라서 디스크 상에 쓰기 전 로그(write-ahead log, WAL)라는 데이터 구조를 추가해서 B트리를 구현한다.
  *WAL : 트리 페이지에 변경된 내용 적용 전의 모든 B트리의 변경 사항을 기록하는 추가 전용 파일
• 같은 자리의 페이지 갱신 시 다중 스레드 동시성 문제 : 래치(latch, 가벼운 잠금)로 데이터 구조를 보호한다. 

 

B트리 최적화

• 일부 DB에서는 WAL 대신 쓰기 시 복사 방식(copy-on-wrute schema, 데이터의 수정이 발생할 때 원본 데이터를 복사하여 새로운 버전을 생성하는 방식)를 사용한다. 
• 전체 키의 문자열이 아니라 키 범위 사이의 경계 역햘을 할 수 있을 정도의 축약된 키로 공간을 절약한다. 
• 키 범위가 가까운 페이지는 원래 디스크 상에서 가까이 있을 필요는 없지만, 광범위를 스캔할 때 유리하게 하기 위해서 디스크 상에서도 붙어있도록 노력해서 효율을 높인다.
• 트리에 포인터를 추가한다. 리프 페이지에 양쪽 형제 페이지를 참조하면 상위 페이지로 다시 이동할 필요가 없어진다. 
• 프랙탈 트리(fractal tree) : B트리의 변형과 로그 구조화 개념이 섞인 트리도 있다.

 

B트리와 LSM트리의 비교

	B트리	LSM 트리
등장 시기	오래됨 (구현 성숙도가 높음)	비교적 최근
유리한 연산	읽기	쓰기 (각 컴팩션 단계에 있는 여러가지 데이터 구조와 SS 테이블을 확인하기 때문에 읽기는 느림)
쓰기 빈도	모든 데이터 조각을 최소한 두 번 기록 (WAL 한번, 트리 페이지에 한 번 해당 페이지 내 작은 변경에도 전체 페이지를 기록해야 하는 오버헤드 존재)	여러 번 데이터를 다시 씀 (SS테이블의 반복된 컴팩션과 병함)
저장소	저장소 파편화(임의 저장) + 페이지 나누는 경우에 일부 공간은 사용하지 않음	순차쓰기 방식(쓰기 처리량 높게 유지) + 압축률이 높음. (디스크에 더 적은 파일 생성) 주기적으로 SS 테이블에 다시 기록 (= 저장소 오버헤드 적음)
컴팩션	컴팩션 진행 X = 성능 예측이 쉬움	컴팩션 진행 O = 진행 중인 읽기와 쓰기의 성능에 영향을 줄 수 있음.  컴팩션이 유입 쓰기 속도를 따라가지 못하면 디스크 공간이 부족할 수도 있음. (디스크 공간 부족 가능성 있음. 명시적 모니터링 필요)
키의 중복	각 키가 인덱스의 한 곳에만 정확히 존재.  (강력한 트랜잭션 시멘틱을 제공하는 DB에 적합)	다른 세그먼트에 같은 키의 다중 복사본 존재 가능.
비교	이미 깊게 뿌리내려져 있음.	점점 인기가 높아지고 있음.

B트리나 LSM 트리를 선택할 때에는 정해진 규칙이 없다. 테스트를 통해 경험적으로 결정할 필요가 있다. 

 

기타 인덱스 구조

키-값 색인의 활용 예 : 기본키(pk), 보조 색인 (secondary index)

색인 안에 값 저장하기

• 키 : 질의가 검색하는 대상
• 값 : 질의의 실제 로우(문서형 DB- 문서, 그래프 DB - 정점) 혹은 저장된 로우를 가리키는 참조. (만약 참조되었다면 로우가 저장된 곳은 힙 파일. heap file. 특정 순서가 없이 저장된다.)

힙 파일 접근 방식 :

• 일반적으로 사용
• 여러 보조 색인이 존재할 때 데이터 중복을 피할 수 있다. 위치만 참조하고 실 데이터는 일정한 곳에 유지하기 때문이다.
• 키 변경이 없고 값만 갱신하는 경우에 유리하다.
• 새로운 값이 이전 값보다 공간 차지를 덜 하면 제자리에 덮어쓸 수 있지만 그 반대의 경우에는 충분한 공간이 있는 곳으로 이동해야 한다. 따라서 모든 인덱스가 새 힙 위치를 가리키도록 갱신되어야 하거나 이전 힙 위치에서 전방향 포인터를 두어야 한다.
• 인덱스가 힙 파일에 접근할 때 IO가 발생하므로 읽기 성능에 불이익이 있다. 따라서 클러스터드 색인을 사용하기도 한다. 이는 색인 안에 바로 색인된 로우를 저장하는 방식이다. 

커버링 인덱스 : 클러스터드 색인과 비클러스터드 색인(인덱스 안에 데이터의 참조만 존재) 사이의 절충안. 클러스터드 인덱스와 커버링 인덱스는 읽기 성능이 좋지만 추가적인 저장소가 필요하며 쓰기 과정 중에 오버헤드가 발생한다. 또한 복제로 인한 불일치를 파악하기가 어렵다. 

다중 컬럼 인덱스 : 결합 인덱스나 조금 더 일반적으로 사용하는 다차원 인덱스가 있다. 

전문 검색에서 사용하는 퍼지 인덱스 (fuzzy index) : 유사한 키와 같은 모호한(fuzzy) 질의에는 다른 기술이 필요하다. 따라서 전문 검색 엔진에서는 질의어의 동의어로 검색을 확장하고 용어 사전을 위해서는 인메모리 인덱스인 SS 테이블 구조를 가진다. 

 

모든 것을 메모리에 보관하는 인메모리 DB

디스크의 장점 : 지속성(전원이 들어오지 않아도 내용이 유지된다), 저렴한 비용

하지만 램의 가격이 낮아지면서 인메모리 데이터베이스가 개발될 수 있었다. 

인메모리 데이터베이스 

• 지속성이 목표이기 때문에 특수 하드웨어를 이용/ 변경 사항 로그 기록 / 디스크에 주기적 스냅샷 기록 하는 방식으로 보완
• 이 때 디스크에 기록되더라도 인메모리 DB로 취급되는 이유는 디스크는 추가 전용(append-only) 로그로 사용되고 읽기는 메모리에서만 제공되기 때문이다.
• 안티 캐싱 접근 방식을 사용한다.
• 추후에 비휘발성 메모리가 더욱 발전하면 인메모리 데이터베이스에도 긍정적인 영향을 미칠 것으로 예견된다. 

 

OLTP와 OLAP

OLTP (online transaction processing) : 온라인 트랜잭션 처리

OLAP (online analytic processing) : 온라인 분석 처리(데이터 분석). 비즈니스 인텔리전스에서 사용

이 둘은 최근 들어 사용되는 DB가 달라지고 있다. 분석에 사용하는 데이터베이스를 데이터 웨어하우스라고 한다. 

데이터 웨어하우스

• OLTP 시스템 : 높은 가용성과 낮은 지연 시간의 트랜잭션 처리. 만약 분석 질의를 OLTP 시스템에 진행하면 시스템의 성능 저하가 발생할 수 있다. 
• 데이터 웨어하우스 : 분석 전용으로 OLTP 작업에 영향이 없다. OLTP 시스템 내 데이터의 읽기 전용 복사본이다. ETL 작업으로 적재된다. (OLTP DB에서 추출-E-하고 분석 친화적인 스키마로 전환-T-하고 깨끗하게 정리해서 데이터 웨어하우스에 적재-L-한다)

 

분석용 스키마 : 별 모양 스키마, 눈꽃송이 모양 스키마

분석에서는 데이터 모델의 다양성이 훨씬 적다. 

사실 테이블 : 각 로우에 특정 시각에 발생한 데이터(개별 이벤트)를 저장. 분석의 유연성을 극대화할 수 있음. 테이블이 매우 커질 수 있다. 

차원 테이블 : 사실 테이블에서 외래 키 참조로 사용. 이벤트의 속성인 누가, 언제, 어디서, 무엇을, 어떻게, 왜를 나타냄. ex) 제품 테이블 - 재고 관리 코드, 설명, 브랜드 이름, 카테고리, 상품 크기 등

• 별 모양 스키마 : 사실 테이블에 참조된 차원 테이블들로 이루어져 있음. 
• 눈꽃송이 모양 스키마 : 별 모양 스키마에서 변형된 것으로, 차원이 하위 차원으로 더 세분화된다. ex) 제품 차원 테이블에서 브랜드와 제품 카테고리 테이블을 분리하고 제품 테이블에서는 외래키로 이를 참조한다

 

칼럼 지향 저장소 vs 로우 지향 저장소

로우 지향 저장소 : 대부분의 OLTP DB가 사용하는 것

칼럼 지향 저장소  : 사실 테이블의 총 칼럼 수는 많지만 하나의 질의에 보통 4-5개의 칼럼만 사용하게 된다. 즉 모든 칼럼에 접근할 필요가 없다. 따라서 모든 값을 하나의 로우에 함께 저장하지 않고 각 칼럼별로 모든 값을 함께 저장한다. 따라서 각 칼럼 파일에 포함된 로우가 모두 같은 순서인 점에 의존하게 된다. 

칼럼 압축

데이터를 압축하면 디스크 처리량을 더 줄일 수 있다. 이 때 반복되는 값을 줄이는데 비트맵 부호화를 이용할 수 있다. 보통 칼럼에서 고유 값의 수는 로우 수에 비해 적다. (중복이 존재하므로) n개의 고유 값을 가진 칼럼을 가져와 n개의 개별 비트맵으로 변환할 수 있다. 

이런 비트맵 인덱스는 데이터 웨어하우스에서 일반적으로 사용되는 질의 종류(IN, AND 등)에 매우 적합하다. 

 

메모리 대역폭과 벡터화 처리

데이터 웨어하우스 질의는 수백만 로우를 스캔해야 하므로 메인 메모리에서 CPU 캐시로 가는 대역폭을 효율적으로 사용해야 한다. 따라서 질의 엔진은 압축된 칼럼 데이터를 CPU의 L1 캐시에 딱 맞게 덩어리로 나누어 가져오고 타이트 루프에서 이 작업을 반복한다. 또한, 칼럼 압축을 사용하면 같은 양의 L1 캐시에 칼럼의 더 많은 로우를 저장할 수 있다. (앞서 말한 비트 AND, OR 연산자는 압축된 칼럼 데이터를 바로 연산 가능) 이런 기법을 벡터화 처리(vectorized processing)이라고 한다. 

 

칼럼 저장소의 순서 정렬

각 칼럼을 독립적으로 정렬할 수는 없고 데이터는 한번에 전체 로우를 정렬해야 한다. 1차 정렬 키로 정렬을 하고 동일한 1차 정렬 키의 로우들을 2차 정렬키로 정렬한다.

순서 정렬의 장점:

• 그룹화나 필터링 질의에 도움이 된다.
• 칼럼 압축에 도움이 된다. (특히 첫 번째 정렬 키) > 런 렝스 부호화(run-length encoding)를 이용하기 쉽다.

*칼럼 지향 저장에서 여러 정렬 순서를 갖는 것 vs 로우 지향 저장에서 여러 2차 색인을 갖는 것

• 로우 지향 저장 : 한 곳(힙 파일이나 클러스터드 색인)에 모든 로우를 유지
• 칼럼 지향 저장 : 데이터를 가리키는 포인터가 없고 값을 포함한 칼럼만 존재. 

 

칼럼 지향 저장소에 쓰기

칼럼 지향 저장소, 압축, 정렬은 모두 읽기 질의에는 유리하지만 쓰기에는 불리하다. 압축된 칼럼에서는 제자리 갱신(update-in-place, B트리에서 사용하는 방식)은 어렵고 LSM 트리처럼 충분한 쓰기를 모으면 디스크의 칼럼 파일에 병합하고 대량으로 새로운 파일에 기록하는 방식을 택할 수 있다. 

질의도 LSM 트리처럼 디스크의 칼럼 데이터와 메모리의 최근 쓰기를 모두 조사해서 두 가지를 결합해서 사용한다. 

 

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

데이터 웨어하우스는 구체화 집계(count, sum, avg, min, max 등)를 많이 사용한다. 이를 위해서 구체화 뷰(materialized view)를 캐싱하기도 한다. 

• 구체화 뷰 : 원본 데이터의 비정규화된 복사본. DB는 이 작업을 자동으로 수행할 수 있다. 비싸기 때문에 OLTP에서는 사용하지 않는다. 
• 데이터 큐브 (=OLAP cube): 일반화된 구체화 뷰의 특별 사례. 다양한 차원으로 그룹화된 집계 테이블. 유연성이 없다. 따라서 원시 데이터를 유지하려고 노력하면서 특정 질의에 대한 성능 향상에만 사용한다.