designing-data-intensive-applications

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

• 가장 간단한 구조의 데이터베이스를 두 개의 bash 함수로 구현해보자.

#!/bin/bash

db_set () {
  echo "$1,$2" >> database
}

db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
# grep은 database 파일에서 키를 포함한 line을 찾아서 반환
# sed -e는 문자열 편집, s 하위명령어("s/aaa/bbb/")는 aaa를 bbb로 치환

• db_set() : 일반적으로 append-only 데이터파일인 로그 기반의 파일 추가 작업은 매우 효율적이다.
• db_get() : 반면 이런 구조에선 검색 비용이 O(n) 으로 매우 비효율적이다.
• 특정 키의 값을 효율적으로 찾기 위해 색인(index) 구조가 필요하다.
  • index의 일반적인 개념은 탐색을 위해 부가적인 메타데이터를 유지하는 것
  • 읽기 질의 속도가 향상되지만 쓰기 속도가 떨어지는 트레이드오프를 동반
  • 이런 트레이드오프 때문에 보통 자동으로 모든 것을 index 적용하진 않으며
  • 앱개발자나 DBA는 애플리케이션의 전형적인 질의 패턴을 활용하여 수동으로 index를 선택해야 한다.

해시 색인

• 키-값 저장소는 dictionary type과 매우 유사하며 보통 hash map(hash table)로 구현한다.
• 키 → 바이트 오프셋(데이터의 위치) 매핑 정보를 in-memory hash map에 유지하는 전략이 있다.

• e.g. 키가 동영상 URL이고 값은 동영상의 재생횟수인 경우의 예시
  • 각 키의 값이 자주 갱신되는 상황 (동영상 재생 횟수가 계속 갱신)
  • 쓰기 부하가 많지만 고유키는 적어서 메모리에 모든 키 보관 가능(새로운 키가 계속 추가되기 보단 기존 키의 값이 계속 갱신되므로)
  • 단, 값(재생횟수 정보 로그)을 디스크에 계속 append하므로 언젠간 디스크 공간이 부족해진다.
• 위 예시에서 디스크 공간 부족은 로그를 세그먼트로 나눠 저장하는 방식으로 해결할 수 있다.
  • 세그먼트 파일들에 대해 컴팩션(compaction)을 수행해 중복된 키를 버리고 각 키의 최신 상태값만 유지할 수 있다.
  • 컴팩션을 수행할 때 여러 세그먼트를 병합해 디스크 공간을 확보할 수 있다.

  

  • 병합과 컴팩션 수행은 새로운 세그먼트 파일을 만드는 방식으로 동작한다.
  • 따라서 병합과 컴팩션 동안 이전 세그먼트 파일을 이용해 읽기와 쓰기 요청을 정상적으로 계속 수행할 수 있다.
  • 전환 후 이전 세그먼트 파일은 간단히 삭제하면 끝
• 이러한 해시 index 세그먼트 방식을 구현하기 위해 고려해야 할 사항들
  • 파일 형식
    • CSV 같은 형식보단 원시 문자열(이스케이핑 필요X)을 부호화하는 바이너리 형식이 더 빠르고 간편하다.
  • 레코드 삭제
    • 키에 대한 값을 삭제하려면 툼스톤(tombstone)과 같은 특수한 삭제 레코드를 추가해야 한다.
    • 세그먼트 병합 과정에서 툼스톤은 삭제된 키의 이전 값을 무시하게 한다.
  • Crash 복구
    • DB 재시작 시 메모리 상의 hash map이 손실되므로 디스크 전체를 읽고 hash map을 복구해야 한다.
    • 이 작업은 시간이 오래걸리므로 스냅숏을 디스크에 저장해 복구 속도를 높일 수 있다.
  • 부분적으로 레코드 쓰기
    • DB는 레코드 추가 도중에도 죽을 수 있으므로 파일에 체크섬을 포함하여 로그의 손상된 부분을 탐지해 무시하도록 조치할 수 있다.
  • 동시성 제어
    • 쓰기 ⇒ 로그 추가를 엄격하게 순차적으로 수행하려면 하나의 쓰기 스레드만 사용하는 방법이 있다.
    • 읽기 ⇒ 데이터 파일 세그먼트는 append-only이거나 immutable하므로 다중 스레드로 동시에 읽기를 할 수 있다.
• append-only 방식이 정해진 자리에 파일을 갱신하는 방식 보다 좋은 점
  • 순차적인 쓰기 작업이 보통 무작위 쓰기보다 훨씬 빠르다.
  • append-only이나 immutable이면 동시성과 Crash 복구가 훨씬 간단하다. (장애 시 이전 값 부분과 새로운 값 부분이 구분되므로)
  • 오래된 세그먼트 병합은 시간에 따라 조각화되는 데이터 파일 문제를 피할 수 있다.
• hash table의 제한 사항
  • 키가 많아지면 hash table을 메모리에 비해 성능이 떨어지는 디스크로 확장하여 저장해야 한다. (낮은 무작위 I/O 속도, 디스크가 가득 찼을 때의 비싼 확장 비용, 해시 충돌을 위한 성가신 로직 등)
  • hash table은 범위 질의(range query)에 효율적이지 않다.
• 위와 같은 이러한 제한이 없는 index 구조는?

SS테이블과 LSM 트리

• SS테이블(Sorted String Table)
  • 앞의 append-only 방식의 세그먼트는 키-값 로그가 쓰여진 순서대로 저장되며 나중의 키 값이 이전의 키 값보다 우선이었다.
  • 반면, SS테이블은 일련의 키-값 쌍을 키로 정렬한다.
  • 각 키는 각 병합된 세그먼트 파일 내에 한 번만 나타난다. (컴팩션 과정이 이를 보장)
  • SS테이블이 hash index의 로그 세그먼트보다 나은 장점
    • 파일이 메모리보다 커도 효율적으로 병합할 수 있다.
      • SS테이블의 세그먼트 병합은 병합정렬(Merge Sort) 방식과 유사하다. 이미 정렬된 각 세그먼트 파일의 첫 번째 키부터 가져오며 새로운 병합된 세그먼트 파일을 생성한다.
    • 메모리에 모든 키의 index를 유지할 필요가 없다.
      • 디스크 상의 세그먼트 파일에서 키들이 정렬되어 있으므로, index에 없는 키는 index의 다른 두 키 사이 범위만 스캔하여 빠르게 찾을 수 있다. 즉, index가 드문드문 희소하더라도 탐색에 문제가 없다.

      

    • 레코드 블록을 압축하여 디스크에 저장한다.
      • 읽기 요청은 여러 키-값 쌍 범위를 스캔하므로 해당 레코드들을 그룹화하여 압축 저장한다. 그러면 index의 각 항목은 블록의 시작을 가리키게 된다. 이는 디스크 공간 절약 뿐만 아니라 I/O 대역폭 감소라는 장점을 갖는다.

SS테이블 생성과 유지

• 쓰기 요청이 들어오면 멤테이블(memtable)에 추가한다.
  • 정렬된 데이터 구조는 디스크보다 메모리에서 유지하는 편이 훨씬 쉽다. (레드블랙 트리나 AVL 트리 등의 in-memory balanced tree)
    • 멤테이블이 임곗값보다 커지면 SS테이블 파일로 디스크에 기록한다.
• 읽기 요청이 들어오면 먼저 멤테이블에서 키를 찾고, 없으면 그 다음엔 디스크의 최신 세그먼트 파일에서, 그 다음 최신 세그먼트에서 찾는 식으로 탐색한다.
• 세그먼트 파일의 병합과 컴팩션은 백그라운드에서 실행한다.
• DB 장애 시, 아직 디스크에 기록되지 않은 멤테이블의 데이터 소실 문제
  • 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지해야 한다.
  • 멤테이블을 SS테이블로 기록하고 나면 해당 로그를 버릴 수 있다.
  • WAL같은걸 말하는 듯

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

• 로그 구조화 병합 트리(Log-Structured Merge-Tree, LSM 트리)
  • 앞서 다룬 SS테이블처럼 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라 한다.
• LevelDB, RocksDB 등에서 앞서 기술된 알고리즘을 사용한다.
• 구글 Bigtable(SS테이블, 멤테이블 용어 소개)에서 영감을 받은 카산드라와 HBase 또한 유사한 저장소 엔진을 사용한다.
• ES, Solr에서 사용하는 Lucene 전문 검색 엔진
  • term dictionary를 저장하는데 유사한 방법을 사용
  • 검색 질의가 들어오면 단어가 언급된 모든 문서를 찾는다.
  • 키가 term, 값은 단어를 포함한 모든 문서의 ID 목록인 키-값 구조

성능 최적화

• 키가 DB에 없는 경우를 미리 확인하여 DB 전체 탐색을 사전에 방지
  • DB에 존재하지 않는 키를 찾는 경우, 멤테이블 → 최근 세그먼트 파일 → 오래된 세그먼트 파일 순으로 DB 전체를 탐색하므로 성능이 느려진다.
  • 블룸 필터(Bloom filter)를 적용하면 집합 내용을 approximating한 데이터 구조로 DB 내 키 존재 여부를 빠르게 판단할 수 있으므로 불필요한 디스크 읽기를 절약할 수 있다.
• 병합 순서와 시기를 결정하는 전략으로 성능 개선을 고려
  • 크기 계층 컴팩션(size-tiered compaction)
    • 더 작고 새로운 SS테이블을 더 크고 오래된 것에 연이어 병합하는 방식
    • HBase, 카산드라
  • 레벨 컴팩션(leveled compaction)
    • 키 범위를 작게 나누고 오래된 데이터를 개별 레벨로 이동하는 방식
    • 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용한다.
    • LevelDB, RocksDB, 카산드라
• 그 밖에 LSM 트리의 성능상 이점
  • LSM 트리의 기본 개념은 백그라운드에서 연쇄적으로 SS테이블을 지속적으로 병합하는 것으로, 데이터셋이 메모리보다 훨씬 크더라도 효과적이다.
  • 데이터가 정렬된 상태로 저장되어 있으므로 range query에도 효과적이다.
  • 쓰기 또한 순차적이므로 높은 쓰기 처리량도 보장한다.

B 트리

• 관계형에서 표준 색인 구현으로 사용되는 것은 B-tree이며 많은 비관계형에서도 사용된다.
• 키로 정렬된 키-값 쌍을 유지하여 range query에 효율적이란 점만 SS테이블과 유사하고 설계 철학이 매우 다르다.
  • 로그 구조화 색인 : DB를 수 MB 이상의 가변 크기를 가진 세그먼트로 나누고 항상 순차적으로 세그먼트를 기록한다.
  • B 트리 : 4KB 정도의 고정 크기의 페이지(혹은 블록)로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 수행한다.

• 한 페이지가 B 트리의 루트(root)로 지정되어 루트에서부터 탐색이 시작된다.
• 각 페이지는 여러 키와 하위 페이지에 대한 참조를 가진다.(참조는 포인터와 유사하나 메모리가 아닌 디스크상에 저장됨)
• 최종적으로 leaf page까지 도달하여 키에 대한 값을 탐색
• 분기 계수(branching factor) : 한 페이지에서 하위 페이지를 참조하는 수. 클 수록 트리의 깊이 수준을 낮출 수 있다.
• B 트리의 키 값 갱신과 추가 방법
  • 키 값 갱신 : 키를 포함하는 leaf page 검색하여 페이지의 값을 바꾼 다음 디스크에 다시 기록한다.
  • 키 값 추가 : 추가할 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 추가한다. 페이지에 여유공간이 없다면 페이지를 둘로 나눠 상위 페이지가 나눠진 두 페이지를 참조하도록 갱신한다.

  

  • 위 알고리즘은 트리가 계속 균형을 유지하는 것을 보장한다. n 개의 키를 가진 트리는 깊이가 항상 O(log n)이다.

  

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

• WAL(write-ahead log)
  • B 트리는 로그 구조화 색인과 달리, 새로운 데이터를 디스크 상의 페이지에 덮어쓴다.(append-only가 아님)
  • 덮어쓰기는 하드웨어 동작이 복잡하며 DB가 고장나면 index가 훼손될 수 있다. (다른 페이지와의 참조를 잃어버린 고아 페이지(orphan page))
  • 트리 페이지에 내용을 적용하기 전에 B 트리의 모든 변경사항을 WAL로 기록해두면 DB 고장 시 복구가 가능하다. (WAL은 append-only로 기록)
• 래치(latch) 동시성 제어
  • 같은 자리의 페이지를 갱신할 때 다중 스레드가 트리에 접근하는 것을 제어하기 위해 latch로 lock을 걸어 데이터 구조를 보호한다.
  • 반면, 로그 구조화 접근 방식은 유입 질의 간섭 없이 백그라운드로 모든 병합을 수행. 동시성 제어 측면에서 매우 간단함

B 트리 최적화

• WAL 대신 쓰기 시 복사 방식(copy-on-write scheme)을 사용하여 동시성 제어까지 확보할 수 있다.
  • 변경된 페이지는 다른 위치에 기록하고 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키게 하는 방식
• 페이지에 전체 키가 아니라 축약된 키를 사용하여 공간을 절약할 수 있다.
  • 페이지의 분기 계수가 늘어나면 트리 깊이 수준을 낮출 수 있다.
• leaf page를 최대한 디스크 상에 연속된 순서로 배치하여 range query 성능을 높인다.
  • 하지만 트리가 커지면 순서를 유지하기 어렵다.
  • 반면, LSM 트리는 병합 과정에서 새로운 세그먼트 파일을 저장하므로 순서 유지가 더 쉽다.
• 트리에 포인터를 추가하여 형제 leaf page들끼리 참조를 가지면 상위 페이지로 이동하지 않고도 순서대로 키를 스캔할 수 있다.

B 트리와 LSM 트리 비교

• 일반적으로 LSM 트리는 쓰기에서 빠르고 B 트리는 읽기에서 더 빠르다.
• LSM 트리는 컴팩션 단계의 데이터 구조와 SS 테이블을 확인해야 하므로 읽기에서 상대적으로 느릴 수 있다.
• LSM 트리의 장점
  • B 트리보다 쓰기 증폭(write amplification)이 낮다.
    • DB 쓰기 한 번이 디스크에 여러번 쓰기를 야기하는 효과
    • B 트리는 WAL과 페이지 저장으로 최소 2번 기록(+덮어쓰기)
    • 반면 로그 구조화 색인은 컴팩션, 병합으로 여러번 쓰지만 append-only
  • B 트리보다 쓰기 처리량을 높게 유지할 수 있다.
    • LSM 트리는 순차적으로 컴팩션된 SS테이블 파일을 쓰기 때문 (덮어쓰기X)
  • B 트리보다 압축률이 더 좋다.
    • 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하므로(컴팩션)
• LSM 트리의 단점
  • 컴팩션 과정이 읽기와 쓰기 성능에 영향을 미친다
    • 디스크가 가진 자원은 한계가 있으며 비싼 컴팩션 연산이 끝날 때까지 요청을 대기해야하는 상황이 발생하기 쉽다.
    • HBase compaction storms https://docs.aws.amazon.com/whitepapers/latest/comparing-dynamodb-and-hbase-for-nosql/apache-hbase-configurations.html
  • 높은 쓰기 처리량으로 인한 디스크 대역폭 제한
    • 디스크 대역폭을 초기 쓰기와 백그라운드 컴팩션 작업이 공유하므로 DB가 커질 수록 컴팩션에 더 많은 대역폭을 사용해야 한다.
  • 컴팩션 속도가 유입 쓰기 속도를 따라가지 못 하는 경우
    • 아직 병합되지 않은 세그먼트 수가 디스크 공간이 부족해질 때까지 증가
    • 많은 세그먼트 파일을 확인해야 하므로 읽기 속도 또한 느려진다.
  • 강력한 트랜잭션 시맨틱을 제공하는 DB에선 B 트리가 더 매력적
    • B 트리는 각 키가 index의 한 곳에만 정확하게 존재한다.
    • 반면, 로그 구조화 저장소 엔진은 같은 키의 다중 복사본이 존재할 수 있다. (여러 세그먼트를 병합하며 같은 키의 최신 값을 찾던 예시)

기타 색인 구조

• 기본키 색인(primary key index)
  • 키-값 색인의 대표적인 예는 관계형 모델의 primary key
  • 관계형 : 기본키 ⇒ 로우
  • 문서형 : 기본키 ⇒ 문서
  • 그래프형 : 기본키 ⇒ 정점
• 보조 색인 (seconday index)
  • 보통 효율적으로 조인을 수행하는데 사용
  • CREATE INDEX 명령으로 보조 색인 생성

(이하부턴 대충대충 훑어만 봄)

색인 안에 값 저장하기

• 힙 파일(heap file)
  • 실제 데이터가 저장되는 곳이며 각 index는 힙 파일에서 위치만 참조하고 실제 데이터는 일정한 곳에 유지한다.
  • 여러 보조 색인이 존재할 때 데이터 중복을 피할 수 있어 일반적인 방식이다.
  • 키를 변경하지 않고 값을 갱신할 때 효율적이다.
• 클러스터드 색인(clusterd index)
  • index에서 heap file로 다시 이동하는게 성능상 불이익이 많아서 index 안에 바로 색인된 로우(실제 데이터)를 저장하는 것이 바람직할 수 있다.
• 커버링 색인(covering index), 포괄열이 있는 색인(index with included column)
  • 클러스터드 색인과 비클러스터드 색인 사이의 절충안

다중 칼럼 색인

• 결합 색인(concatenated index)
  • 하나의 키에 여러 필드를 단순히 결합한다. (성, 이름)
  • 순서가 정렬되어 있어 특정 성인 모든 사람을 찾거나 특정 성 이름 조합을 가진 모든 사람을 찾을 때 유용

모든 것을 메모리에 보관

• 인메모리 데이터베이스
  • 램이 점점 저렴해지고 데이터셋 대부분은 그다지 크지 않기 때문에 메모리에 전체를 보관하는 방식이 현실성 있게 되었다.(혹은 여러 장비 간 분산해서 보관)
  • 재시작 시 디스크나 네트워크를 통해 복제본에서 상태를 다시 적재해야 한다.
  • VoltDB, MemSQL, Oracle TimesTen, RAMCloud, Redis, Couchbase 등
  • (+ Apache Ignite)

(훑어만 본 구간 끝)

트랜잭션 처리나 분석?

• OLTP와 OLAP의 차이점(사실 차이점이 명확하진 않다)

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

데이터 웨어하우징

• OLTP 시스템은 사업 운영에 중요한 컴포넌트로 높은 가용성과 낮은 지연시간의 트랜잭션 처리를 기대한다.
• 때문에 DBA는 분석가가 OLTP에 ad-hoc analytic query를 실행하는 것을 꺼려한다.(사람 사는 곳은 비슷)
• 데이터 웨어하우스 : 분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스로 사내 여러 OLTP 시스템에 있는 데이터의 읽기 전용 복사본이다.
• ETL(Extract-Transform-Load) : 데이터는 OLTP 데이터베이스에서 추출(extract)하고 분석 친화적인 스키마로 변환(transform)하고 데이터 웨어하우스에 적재(load)한다.
• OLTP가 아닌 개별 데이터 웨어하우스를 사용하면 분석 접근 패턴에 맞게 최적화를 할 수 있다.
• SQL은 분석 질의에도 적합하므로 데이터 웨어하우스의 데이터 모델은 가장 일반적인 관계형 모델을 사용한다.
• 상용 라이선스 데이터 웨어하우스 벤더
  • Teradata, Vertica, SAP HANA, ParAccel, Amazon RedShift
• 오픈소스 SQL-on-Hadoop
  • Apache Hive, Spark SQL, Cloudera Impala, Presto → Trino(리브랜딩)
  • (+ clickhouse, Apache Druid)

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

• OLTP에서 데이터 모델이 다양한 것과 달리(2장 데이터 모델과 질의 언어) 분석에선 데이터 모델의 다양성이 훨씬 적다.
• star schema (dimensional modeling)
  • 데이터 웨어하우스에 사용되는 상당히 정형화된 방식
  • fact table : 각 row가 특정 시각에 발생한 이벤트에 해당하는 테이블(e.g. 고객의 제품 구매, 페이지 뷰, 사용자 클릭 등)
  • dimension table : 이벤트의 속성에 해당하는 테이블로, fact table의 속성 칼럼들은 dim table을 foreign key로 참조한다.
  • 심지어 날짜와 시간도 보통 dimenstion table을 사용해 표현한다 → (나는 처음 봄)
  • 일반적인 데이터 웨어하우스에서 테이블은 보통 폭이 매우 넓다.(칼럼 수가 100개 이상~수백개)

  

• snowflake schema
  • star schema 템플릿의 변형으로 차원이 하위차원으로 더 세분화된다.
  • Star schema와 Snowflake schema 비교 (tistory.com)
  • star schema보다 더 정규화됐지만 분석가들은 star schema를 작업하기 더 쉽다는 이유로 선호한다.

칼럼 지향 저장소

• 데이터 웨어하우스에선 fact table의 칼럼이 수백개 이상이 들어갈 수 있지만 보통 질의는 한 번에 4~5개 정도의 칼럼만 접근한다. (분석에 “SELECT *“ 질의는 보편적이지 않음)
• 대부분의 OLTP 저장소는 로우 지향 방식으로 데이터를 배치하여 한 로우의 모든 값은 인접하게 저장된다.
  • 문서 DB에서 전체 문서는 하나의 연속된 바이트 열로 저장(그림 3-1)
• 이러한 방식을 데이터 웨어하우스에 적용한다면 4~5개 칼럼에 대한 SELECT 문도 모든 로우(수 TB 규모)를 메모리에 적재하여 처리해야 하므로 매우 오래 걸릴 수 있다.
• 칼럼 지향 저장소
  • 각 칼럼 별로 모든 값을 함께 저장하여 질의 시 사용할 칼럼만 읽고 분석하게 해준다.
  • 각 칼럼 파일에 포함된 로우가 모두 같은 순서로 저장된다.
  • e.g. 구글 Dremel을 기반으로 한 문서 데이터 모델을 지원하는 칼럼 저장소 형식 Parquet

칼럼 압축

• 비트맵 부호화(bitmap encoding)
  • 보통 칼럼에서 고유한 값의 수는 로우 수에 비해 적다. (e.g. 거래 건수는 1000만건인데 실제 상품의 종류는 수천개)
  • 아래와 같이 한 칼럼에 대해 고유 값들을 0과 1의 비트맵으로 표현하고, 이를 run-length encoding하여 부호화를 줄일 수 있다. (1000만건의 로우 수를 수천개 길이 부호화된 값으로 압축)

  

  • 이런 비트맵 색인은 데이터 웨어하우스의 일반적인 질의 종류에 매우 적합하다.

WHERE product_sk IN (30, 68, 69) -- 세 조건의 비트맵 3개를 적재하고 비트 OR을 계산
WHERE product_sk = 31 AND store_sk = 3 -- 두 조건의 비트맵을 적재하고 비트 AND를 계산

• (참고1) 칼럼 지향 저장소와 칼럼 패밀리
  • 구글 Bigtable에서 영향을 받은 카산드라, HBase의 칼럼 패밀리는 엄밀히 칼럼 지향적이라할 수 없다.
  • 각 칼럼 패밀리 안에는 rowkey에 따라 row와 모든 칼럼을 함께 저장한다. (칼럼 별로 저장X)
  • 따라서 Bigtable 모델은 여전히 대부분 로우 지향이다.
  • Is Hbase a columnar DB - Stack Overflow
• (참고2) 메모리 대역폭과 벡터화 처리
  • 데이터 웨어하우스 질의는 데이터를 디스크에서 메모리로 데이터를 가져오는 대역폭, CPU의 L1 캐시로 가져오는 CPU 주기 등이 병목이 될 수 있다.
  • 칼럼 압축을 사용하면 같은 양의 L1 캐시에 칼럼의 더 많은 로우를 저장할 수 있다.
  • 비트 AND, OR 같은 연산자는 압축된 칼럼 데이터 덩어리를 바로 연산할 수 있게 설계할 수 있다.
  • 이런 기법을 벡터화 처리(vectorized processing)이라 한다.

칼럼 저장소의 순서 정렬

• 칼럼 저장소에서 각 칼럼을 독립적으로 정렬할 수는 없다. 칼럼의 어떤 항목이 동일한 항목에 속하는지 알 수 없게 되므로
• 따라서 칼럼별로 따로 저장되었어도 정렬을 할 땐 칼럼별로가 아니라 한 번에 전체 로우를 정렬해야 한다.
• 정렬된 순서의 장점
  • 시계열 값 등 원하는 범위의 로우만 스캔할 수 있으며 이는 모든 로우를 스캔하는 것보다 훨씬 빠르다.
  • 정렬된 값에선 같은 값들이 연속으로 길게 반복되기 쉬우므로 칼럼 압축에 도움이 된다. (run-length encoding)

칼럼 지향 저장소에 쓰기

• 데이터 웨어하우스에서 대부분의 질의는 분석가가 수행하는 대량의 읽기 전용 질의이다.
• 칼럼 지향 저장소, 압축, 정렬은 모두 읽기 질의를 빠르게 하지만 쓰기는 어렵게 한다는 단점이 있다.
• B 트리와 같은 제자리 갱신(update-in-place) 접근 방식은 압축된 칼럼에서는 불가능하다. (모든 칼럼을 재작성해야 함)
  • 이는 앞서 배운 LSM 트리 방식으로 해결 가능하다.
  • 모든 쓰기는 먼저 in-memory 저장소의 정렬된 구조에 추가하고 디스크에 쓸 준비한다.
  • 쓰기가 충분히 모이면 디스크의 칼럼 파일에 병합하고 대량으로 새로운 파일에 기록한다.

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

• 데이터 웨어하우스 질의는 보통 SQL에 집계함수를 포함한다. (COUNT, SUM, AVG, MIN, MAX)
• 구체화 집계(materialized aggregation) : 동일한 집계를 여러 질의에서 사용하며 매번 원시 데이터를 처리하는 것은 매우 낭비 → 자주 사용하는 집계를 캐시하는 것을 어떨까?
• 구체화 뷰(materialized view) : 이런 캐시를 만드는 방법. 특별 사례로 데이터 큐브(data cube) 또는 OLAP 큐브라 불리는 구체화 뷰가 있다.
  • 장점 : 특정 질의를 미리 계산했기 때문에 해당 질의를 수행했을 때 매우 빠르다.
  • 단점 : 원시 데이터에 질의하는 것과 동일한 유연성이 없다.

  

정리

• 데이터베이스가 어떻게 저장과 검색을 다루는지에 대한 근본적인 내용
• 트랜잭션 처리 최적화(OLTP)와 분석 최적화(OLAP)의 접근 패턴 차이
  • OLTP는 보통 애플리케이션이 각 질의마다 작은 수의 레코드만 다룬다. 요청한 키의 데이터를 찾기 위해 index를 사용한다. 이 경우는 대개 디스크 탐색이 병목이다.
  • OLAP는 최종 사용자가 아닌 분석가가 주로 사용한다. 각 질의는 다루기 어렵고 짧은 시간에 수백만 개의 레코드를 스캔해야 한다. 이 경우는 디스크 대역폭이 병목이다.
• OLTP 측면에서 두 가지 주요한 관점
  • 로그 구조화 관점 : 파일에 추가와 오래된 파일의 삭제만 허용. 저장된 파일의 갱신 없음. (비트캐스크, SS테이블, LSM트리, LevelDB, 카산드라, HBase, Lucene)
  • 제자리 갱신 관점 : 덮어쓰기 가능한 고정 크기 페이지 구조로 디스크를 다룬다. B 트리가 예이며 모든 주요 관계형 DB와 많은 비정형 DB에서도 사용한다.
• 데이터 웨어하우스의 분석 작업 부하가 OLTP와 다른 점
  • 대량의 로우를 순차적으로 스캔하는 질의에는 index를 사용하는 방법이 적절하지 않다.
  • 대신 디스크에서 읽는 데이터 양을 최소화하기 위해 데이터를 작게 부호화하는 일이 중요해졌다. (칼럼 저장소의 bitmap encoding)