책너두 (데이터 중심 애플리케이션 설계) 7일차 (~97p)

요약

• 데이터베이스의 구조인 B 트리의 신뢰성과 최적화를 이해하게 됨.
  • B 트리 → 새로운 데이터를 디스크 상의 페이지에 덮어 씀.
  • B 트리 → 여러 최적화 방식을 제공함.
• LSM 트리와 B 트리의 차이를 이해하게 됨.
• 기타 색인에 대한 종류들을 이해하게 됨.
  • 기본키 색인
  • 보조 색인
  • 색인 안에 값을 저장하는 방법을 이해하게 됨.
    • 클러스터드 색인
    • 비 클러스터드 색인
    • 커버링 색인
  • 다중 칼럼 색인을 지원함.
    • 결합 색인이라고 함.
  • 애매모호한 키에 대한 색인을 지원함.
    • 퍼지 색인
  • 아예 모든걸 메모리에 저장하는 방법도 있음.
• 트랜잭션의 처리와 분석에 대한 내용을 이해하게 됨
  • 트랜잭션 처리 → OLTP
  • 데이터 분석 → OLAP
• 데이터 웨어하우징에 대한 내용을 이해하게 됨.
  • OLTP 용 데이터베이스와 분리하여 데이터 웨어하우스를 사용함.
  • 각 데이터베이스에 맞는 패턴을 적용함.

발췌

• 램의 가격이 점점 저렴해지면서 메모리에 전체를 보관하는 방식도 꽤 현실적임. → 이 이유로 인메모리 데이터베이스가 개발됨 (p91)
• 트랜잭션 처리는 클라이언트가 지연 시간이 낮은 읽기, 쓰기를 가능하게 한다는 의미임. (p93)

메모

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

• B 트리의 기본 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어 씀.
  • 덮어쓰기가 페이지 위치를 변경하지 않는다고 가정한다.
  • LSM 트리와 같은 로그 구조화 색인과 대조되는 점임.
  • 디스크의 페이지를 덮어쓰는 일은 실제 하드웨어 동작으로 생각할 수 있다.
    • 자성의 하드드라이브의 경우, 플래터가 디스크 헤더를 적합한 섹터에 새로운 데이터를 덮어쓰게 한다.
    • SSD의 경우, 블록을 한번에 지우고 다시 쓰기를 해야함 (좀 더 복잡한 과정임)
• 일부 동작에서는 다양한 페이지의 덮어쓰기를 필요로 함.
  • 삽입 때문에 페이지가 분할될 경우, 두 하위 페이지의 참조를 갱신하기 위해 상위 페이지를 덮어쓰기 해야 함.
  • 만약, 위 과정에서 일부 페이지만 기록되고 데이터베이스가 고장나면 색인이 훼손될 수 있음. (상당히 위험한 동작임 → 고아 페이지가 발생할 수 있음.)
  • 데이터베이스는 고장 상황에서 스스로 복구할 수 있게 만들기 위해, 일반적으로 디스크 상에 쓰기 전 로그(wrtie-ahead log, 혹은 redo log) 라고 하는 데이터 구조를 추가하여 B 트리를 구현한다.
    • 쓰기 전 로그는 트리 페이지에 변경된 내용을 적용하기 전에 모든 B 트리의 변경 사항을 기록하는 추가 전용 파일임.
    • 이 쓰기 전 로그를 이용하여 데이터베이스가 고장났을 때 복구를 일관성있게 복원할 때 사용함.
• 같은 자리의 페이지를 갱신하는 작업은, 다중 스레드가 동시에 접근할 수 있으므로 동시성 제어를 해야함.
  • 동시성 제어는 래치(latch)로 트리의 데이터 구조를 보호함.

B 트리 최적화

• B 트리는 오랫동안 사용됐기에 최적화 기법이 많음.
  • 페이지 덮어쓰기와 고장 복구를 위한 WAL 보다, 복사 방식(copy-on-write)을 사용한다.
  • 페이지 전체 키를 저장하지 않고 키를 축약해서 공간을 절약할 수 있음.
  • 일반적으로 페이지는 디스크 상 어디에 위치할 수 있지만, 정렬 순서 키를 스캔할 때, 효율을 위해 리프 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리를 배치하려고 시도한다.
  • 트리에 포인터를 추가하면 상위 페이지 이동없이 순서대로 키 스캔 가능.
  • 프랙탈 트리와 같은 B 트리 변셩은 디스크 탐색을 줄이기 위해 로그 구조화 개념을 일부 빌림.

B 트리와 LSM 트리 비교

• B 트리는 LSM 트리보다 구현이 어려움
  • 하지만 LSM 트리도 성능 특성 때문에 관심을 받고 있음.
    • LSM 트리는 쓰기에 빠름
      • 읽기가 느린 이유는 컴팩션 단계에서 여러 데이터 구조와 SS테이블을 확인해야 하기 때문.
    • B 트리는 읽기에 더 빠름.
  • 위 성능에 대한 내용은 작업부하의 세부 사항에 따라 다름.
    • 작업부하로 시스템을 실제로 테스트해봐야 함.

LSM 트리의 장점

• B 트리 색인은 데이터 조각을 최소 두 번 기록해야 함.
  • 쓰기 전 로그 & 트리 페이지 → 총 2번
    • 만약 해당 페이지에 몇 바이트만 바뀌어도 한 번에 전체 페이지를 기록해야 하는 오버헤드도 있음.
• 로그 구조화 색인 또한 SS테이블의 반복된 컴팩션 & 병합으로 여러 번 데이터를 다시 씀.
• 데이터베이스에 쓰기 한 번이 데이터베이스 수명 동안 디스크에 여러 번의 쓰기를 야기하는 효과를 쓰기 증폭(write amplification) 이라고 함.
  • SSD는 수명이 다할 때까지 블록 덮어쓰기 횟수가 제한되므로, 쓰기 증폭은 SSD의 경우 특별 관심사이기도 함.
• 쓰기가 많은 애플리케이션에서 성능 병목은 데이터베이스가 디스크에 쓰는 속도일 수 있음.
  • 이때, 쓰기 증폭은 바로 성능 비용이 된다.
  • 저장소 엔진이 디스크에 기록할 수록 디스크 대역폭 내 처리할 수 있는 초당 쓰기는 점점 줄어듦.
• LSM 트리는 B 트리보다 쓰기 처리량을 높게 유지할 수 있음.
  • LSM 트리가 상대적으로 쓰기 증폭이 더 낮음.
    • 순차적으로 컴팩션된 SS테이블 파일을 쓰기 때문 (여러 페이지를 덮어씌우지 않음.)
    • 이 차이는 하드드라이브에서 특히 중요함. (하드드라이브는 순차 쓰기가 임의 쓰기보다 훨씬 더 빠름)
• LSM 트리는 압축률이 좋음.
  • B 트리보다 디스크에 더 적은 파일을 생성함.
  • B 트리 저장소 엔진은 파편화로 인해 사용하지 않는 디스크 공간 일부가 남을 수 있음.
  • LSM은 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하므로 저장소 오버헤드가 더 낮음.
• 대다수의 SSD 펌웨어는 내장 저장소 칩에서 임의 쓰기를 순차 쓰기로 전환하기 위해 내부적으로 로그 구조화 알고리즘을 사용함.

LSM 트리의 단점

• 컴팩션 과정이 때로, 진행 중인 읽기와 쓰기의 성능에 영향을 줌.
  • 저장소 엔진이 컴팩션을 점진적으로 수행 & 동시 접근의 영향이 없게 수행하려고 함.
  • 하지만 디스크 자원의 한계가 있기에 디스크에서 비싼 컴팩션 연산이 끝날 때까지 요청이 대기해야 하는 상황이 발생하기 쉬움.
• 컴팩션으로 인해 높은 쓰기 처리량이 문제를 야기함.
  • 디스크 쓰기 대역폭은 유한함.
    • 초기쓰기와 백그라운드에서 수행되는 컴팩션 스레드가 이 대역폭을 공유 해야 함.
  • 이때, 빈 데이터베이스라면 디스크 대역폭을 초기 쓰기만을 위해 사용할 수 있음.
  • 하지만, 데이터베이스가 커질 수록 컴팩션을 위한 더 많은 디스크 대역폭이 필요함.
  • 이러한 컴팩션 설정을 주의깊게 하지 않으면, 컴팩션이 유식 쓰기 속도를 따라갈 수 없기에 디스크 상에 병합되지 않은 세그먼트 수가 디스크 공간이 부족할 떄까지 증가하게 됨.
  • 이 상황을 감지하기 위한 명시적 모니터링이 필요함.
• B 트리의 장점은, 각 키가 색인의 한 곳에만 정확하게 존재한다는 점임.
  • 반면, LSM은 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있음.
  • 많은 관계형 데이터베이스에서 트랜잭션 격리는 키 범위의 잠금을 사용하여 구현함.
    • B 트리 색인에서는 트리에 직접 잠금을 포함시킴.

기타 색인 구조

• 지금까지 키-값 색인을 살펴봄.
  • 대표적인예로 관계형 모델의 기본키(primary key) 색인이 있음.
    • 이 기본키로 관계형 데이터베이스에서 하나의 로우, 문서 데이터베이스에 하나의 문서, 그래프 데이터베이스에서 하나의 정점을 고유하게 식별할 수 있음.
  • 보조 색인(secondary index)을 사용하는 방식도 매우 일반적임.
    • 보통 효율적으로 조인을 수행하는 데 결정적 역할을 함.
    • 기본키 색인과 다른 점은 키가 고유하지 않다는 점임.
      • 이때는 로우 식별자 목록을 만들거나 로우 식별자를 추가하여 각 키를 고유하게 만들 수 있음.

색인 안에 값 저장하기

• 색인에서 키는 질의가 검색하는 대상임
• 값은 다음 두 가지 중 하나에 해당함.
  • 질문의 실제 로우(문서, 정점)
  • 다른 곳에 저장된 로우를 가리키는 참조.
    • 참조일 경우, 로우가 저장된 곳을 힙 파일(heap file) 이라고 함. 특정 순서 없이 데이터를 저장함.
    • 힙 파일을 이용하면 여러 보조 색인이 존재할 때, 데이터 중복을 피할 수 있으므로, 일반적인 방식임.
    • 힙 파일 접근 방식은 키를 변경하지 않고 값을 갱신할 때 효율적임.
      • 만약 새 값이 이전 값보다 공간이 적으면 레코드를 제자리에 덮어쓸 수 있음.
      • 만약, 새 값이 이전 값보다 공간이 크다면, 힙에서 충분한 공간이 있는 새로운 곳으로 위치를 이동해야 함.
        • 색인에서 힙 파일로 다시 이동하는 일은 읽기 성능에 불이익이 너무 많아서 상황에 따라 색인 안에 바로 색인된 로우를 저장하는 편이 바람직함.
        • 색인된 로우를 저장하는 방식을 클러스터드 색인(clustered index) 라고 함.
          • MySQL InnoDB 에서 기본 키는 항상 클러스터드 색인이고, 보조 색인은 기본 키를 참조한다.
        • 클러스터드 색인, 비클러스터드 색인 사이의 절충안으로 커버링 색인(covering index)나 포괄열이 있는 색인(index with included column) 이라고 함.
          • 이 색인은 색인 안에 테이블의 칼럼 일부를 저장함.
          • 이렇게 하면 색인만 사용하여 일부 질의에 응답이 가능함.
• 데이터 복제와 마찬가지로 클러스터드 색인과 커버링 색인은 읽기 성능을 높일 수 있지만, 추가적인 저장소가 필요하고, 쓰기 과정에 오버헤드가 발생함.

다중 칼럼 색인

• 지금까지 설명한 색인은 하나의 키만 값에 대응한다.
  • 다중 칼럼에 동시에 질의에는 대응할 수 없음.
  • 다중 칼럼 색인을 이용한다.
• 다중 칼럼 색인의 가장 일반적인 유형은 결합 색인(concatenated index) 이라고 함.
  • 결합 색인은 하나의 칼럼에 다른 칼럼을 추가하는 방식임. (하나의 키에 여러 필드를 단순히 결합함.)
  • ex) 성, 이름
• 다차원 색인은 한 번에 여러 칼럼에 질의하는 일반적인 방법임.
  • ex) 지리 공간 데이터에 중요하게 사용됨. (위도, 경도)
  • 만약, 위도와 경도 범위를 주고 질의를 할 경우, B 트리와 LSM 트리 색인은 효율적으로 응답할 수 없음 (p90.)
    • 이 문제를 해결하려면 이차원 위치를 공간 채움 곡선을 이용하여 단일 숫자로 변환한 다음 일반 B 트리 색인을 사용할 수 있음.
    • 아니면, R트리처럼 전문 공간 색인을 사용한다.
  • 다차원 색인은 지리 공간 뿐만 아니라, 3차원 색을 검색하거나, 날짜, 기온을 검색할때 사용할 수 있다.

전문 검색과 퍼지 색인

• 지금까지의 색인은 정확한 데이터를 대상으로 키의 정확한 값이나 정렬된 키의 값 범위를 질의할 수 있다고 가정함.
  • 이 색인으로 철자가 틀린 단어와 같이 유사한 키에 대해서는 검색할 수 없음.
  • 이처럼 애매모호한(fuzzy) 질의에는 다른 기술이 필요함.
  • 루씬의 경우, 오타에 대처하기 위해 특정 편집거리 내 단어를 검색할 수 있음.
• 퍼지 검색 기술은 문서 분류 및 머신러닝의 방향으로 진행되고 있음.

모든 것을 메모리에 보관

• 지금까지 설명한 데이터 구조는 모두 디스크 한계에 대한 해결책이었음.
  • 디스크는 메인 메모리와 비교하면 다루기 어려움.
  • 자기 디스크, SSD를 사용할 때 읽기 쓰기에서 좋은 성능을 원한다면 주의해서 데이터를 디스크에 배치해야 함.
    • 디스크는 지속성이 있고 램보다 가격이 저렴하기 때문임.
  • 지금은 램 가격이 점점 저렴해지고, 데이터 셋 대부분이 크지 않기 때문에 메모리에 전체를 보관하는 방식도 꽤 현실적임.
    • 이런 이유로 인메모리 데이터베이스가 개발된 것임.
• 멤캐시드의 경우, 인메모리 키-값 저장소로 사용하며, 캐시 용도로만 사용됨 (데이터 손실을 허용함)
  • 다른 인메모리 데이터베이스는 지속성을 목표로 함.
    • 이 목표를 달성하려면 특수 하드웨어를 사용하거나, 디스크에 변경 사항의 로그를 기록하거나 주기적인 스냅숏을 기록하거나, 다른 장비에 인메모리 상태를 복제해야 함.
    • 디스크를 사용하더라도 여전히 인메모리 데이터베이스임.
      • 왜냐면 디스크는 전적으로 지속성을 위한 추가 전용 로그로 사용되고, 읽기는 전적으로 메모리에서 제공되기 떄문임.
• 인메모리 데이터베이스의 성능 장점이 디스크에서 읽지 않아도 된다는 사실만 있는 건 아님.
  • 디스크 기반 저장소 엔진도 운영체제가 최근 사용한 디스크 블록을 메모리에 캐시하고 있기도 함.
  • 인메모리 데이터 구조를 디스크에 기록하기 위한 형태로 부호화하지 않아도 되기에 이러한 오버헤드를 피할 수 있어서 더 빠를 수도 있음.
• 인메모리 데이터베이스는 디스크 기반 색인으로 구현하기 어려운 데이터 모델을 제공함.
  • ex) 레디스는 우선순위 큐와 셋 같은 다양한 데이터구조를 데이터베이스 같은 인터페이스로 제공함.
• 최근에는 인메모리 데이터베이스 아키텍처가 디스크 중심 아키텍처에서 발생하는 오버헤드 없이, 가용한 메모리보다 더 큰 데이터셋을 지원하게끔 확장할 수 있음.
  • 안티 캐싱(anti-caching) 접근 방식을 이용함.
  • 메모리가 충분하지 않을 때, 가장 최근에 사용하지 않은 데이터를 메모리에서 디스크로 내보내고, 다시 접근할 때 메모리에 적재하는 방식임.
  • 운영체제 가상 메모리와 스왑파일에서 수행하는 방식과 유사함. 하지만 데이터베이스는 전체 메모리 페이지보다 개별 레코드 단위 작업이 가능하므로 OS보다 더 효율적으로 메모리 관리가 가능함.
• 비휘발성메모리 기술이 더 널리 채택되면, 저장소 엔진 설계의 변경이 생길 수 있음.

트랜잭션 처리나 분석?

• 트랜잭션은 반드시 원자성, 일관성, 격리성, 지속성 속성을 가질 필요는 없음.
  • 일괄 처리 작업과 달리 트랜잭션 처리는 클라이언트가 지연 시간이 낮은 읽기, 쓰기를 가능하게 한다는 의미임.
• 보통 애플리케이션에서 색인을 사용하여 레코드를 찾고, 해당 레코드는 사용자 입력을 기반으로 삽입되거나 갱신됨.
  • 이러한 애플리케이션은 대화식이므로 이 접근 패턴을 온라인 트랜잭션 처리(online transaction processing, OLTP) 라고 함.
  • 하지만, 데이터베이스를 데이터 분석(data analytic)에도 점점 더 많이 사용하기 시작함.
    • 데이터 분석은 트랜잭션과 접근 패턴이 매우 다름.
      • 원시 데이터를 반환한다기 보다 많은 수의 레코드에서 일부 칼럼만 읽어서 집계 통계를 계산해야 함.
      • 이러한 질의는 비즈니스 분석가가 작성하고, 더 나은 의사결정을 하게끔 돕는 보고서를 제공함. (비즈니스 인텔리전스 라고 함)
      • 이러한 데이터베이스 사용 패턴을 트랜잭션 처리와 구별하기 위해 온라인 분석처리(online analytic processing, OLAP) 라고 부름
• 초반에는 OLTP, OLAP 모두 동일한 데이터베이스를 사용함.
  • 1980년대 후반 부터 OLTP 시스템을 분석 목적으로 사용하지 않고, 개별 데이터베이스에서 분석을 수행하는 경향을 보임.
  • 이 개별 데이터베이스를 데이터 웨어하우스(data warehouse) 라고 부름

데이터 웨어하우징

• OLTP 시스템은 대개 사업 운영이 중요하므로 일반적으로 높은 가용성과 낮은 지연 시간의 트랜잭션 처리를 기대함.
• 반면, 데이터 웨어하우스는 OLTP 작업에 영향을 주지 않고, 마음껏 질의할 수 있는 개별 데이터베이스임.
  • 데이터 웨어하우스는 OLTP 시스템에 있는 데이터의 읽기 전용 복사본임.
  • 대개 OLTP 데이터베이스에서 추출하여 분석 친화적인 스키마로 변환하고 정리하여 데이터 웨어하우스에 적재한다.
    • 이 과정을 ETL(Extract-Transform-Load) 라고 함.
• 개벌 데이터 웨어하우스를 사용하면 분석 접근 패턴에 맞게 최적화 할 수 있음.

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

• 데이터 웨어하우스의 데이터 모델은 가장 일반적인 관계형 모델을 사용함.
  • SQL을 이용한 일반적인 분석 질의가 적합하기 때문
• 표면적으로 OLTP 데이터베이스와 데이터 웨어하우스는 둘 다 SQL 질의 인터페이스를 지원하기 때문에 비슷해 보임.
  • 하지만, 매우 다른 질의 패턴에 맞게 최적화됐기에 시스템 내부는 완전히 다름.

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

• 데이터 모델은 트랜잭션 처리 영역에서 애플리케이션의 필요에 따라 광범위하고 다양하게 사용됨.
• 하지만, 분석에서 데이터 모델의 다양성은 훨씬 적음.
  • 많은 데이터 웨어하우스는 별 모양 스키마(star schema) or 차원 모델링(dimensional modeling)로 알려진 정형화된 방식을 사용함.
  • 스키마 중심에는 사실 테이블(fact table)이 있음.
    • 이러한 사실 테이블의 각 로우는 특정 시각에 발생한 이벤트를 뜻함.
    • 사실 테이블의 다른 칼럼은 차원 테이블이라 불리는 다른 테이블을 가리키는 외래 키 참조임.
  • 눈꽃송이 모양 스키마는, 차원에서 하위 차원으로 더 세분화되는 과정을 말함.
• 일반적인 데이터 웨어하우스에서 테이블의 폭은 매우 넓은
  • 사실 테이블에 대개 100개 이상의 칼럼이 있고, 수백개인 경우도 있음.
  • 차원 테이블 또한 분석과 관련된 메타 데이터를 포함하므로 그 폭은 매우 넓음.