데이터베이스의 저장, 검색 처리 원리를 애플리케이션 개발자가 이해해야하는 이유는, 특정 작업부하 유형에서 좋은 성능을 내개끔 저장소 엔진을 조정하려면 내부 원리에 대해 이해할 필요가 있기 때문이다.

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

• 색인 데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서 필요한 다른 데이터 구조 색인의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것. 이것은 이정표 역할을 하여 데이터 위치를 찾는 데에 도움을 줌. 색인은 기본 데이터에서 파생된 추가적인 구조. 원본 데이터에 영향을 주지 않고, 질의 성능에만 영향을 줌. 좋은 색인은 읽기 질의 속도를 향상시키지만, 모든 색인은 쓰기 속도를 떨어뜨림.
  

해시 색인

키를 데이터 파일의 바이트 오프셋에 매핑하여 인메모리 해시 맵을 유지하는 전략. (간단해보이지만 실제로 많이 사용)

비트캐스크가 사용하는 방식인데, 해시 맵을 전부 메모리에 유지하여 고성능으로 읽기, 쓰기를 보장함.

각 키의 값이 자주 갱신되는 상황에 매우 적합.

항상 추가만 한다면 결국 디스크 공간이 부족해지는데, 이를 해결하기 위해 특정 크기의 세그먼트로 로그를 나누는 방식이 있음. 세그먼트로 나누면 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 컴팩션 수행할 수 있음.

• 실제 구현에서 중요한 문제
  • 파일 형식
  • 레코드 삭제
  • 고장 복구 (스냅숏을 디스크에 저장해 복구 속도를 높일 수 있음)
  • 부분적으로 레코드 쓰기
  • 동시성 제어
• 추가 전용 설계의 장점
  • 순차적인 쓰기 작업이므로 무작위 쓰기보다 빠름
  • 세그먼트 파일이 추가 전용이나 불변이면 동시성, 고장 복구 간단함
  • 오래된 세그먼트 병합으로 데이터 조각화 피할 수 있음
• 해시 테이블 색인의 제한 사항
  • 메모리에 저장하므로 키가 너무 많으면 문제
  • 범위 질의에 비효율적

SS테이블과 LSM트리

• SS테이블 (Sorted String Table) : 세그먼트 파일을 키로 정렬한 형식
• SS테이블의 장점 (해시 색인을 가진 로그 세그먼트와 비교)
  • 세그먼트 병합 과정이 효율적 (병합정렬과 유사함)
  • 메모리에 모든 키의 색인을 유지하지 않아도 됨. (정렬되어있으므로 범위 찾기 가능)
  • 압축을 통해 디스크 공간 절약, IO 대역폭 사용 줄임

SS테이블 생성과 유지

저장소 엔진 만들기

• 쓰기가 들어오면 인메모리 균형 트리에 추가함 (멤테이블)
• 멤테이블이 임곗값보다 커지면 SS테이블 파일로 디스크에 기록
• 읽기 요청은 멤테이블 → 가장 최신부터 점점 오래된 세그먼트에서 찾음
• 병합과 컴팩션 수행 (백그라운드)

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

• LSM트리 (Log-Structured Merge-Tree) : 로그 구조화 병합 트리

성능 최적화

• 블룸 필터 존재하지 않는 키를 찾는 경우, 가장 오래된 세그먼트까지 가야해서 비효율적 (디스크까지 가야할 수도) 블룸 필터는 키가 데이터베이스에 존재하지 않음을 알려주므로 불필요한 디스크 읽기 절약 가능
  
• SS테이블 압축, 병합 순서와 시기를 결정하는 다양한 전략
  • 크기 계층 (size-tiered) 좀더 새롭고 작은 SS테이블을 오래되고 큰 테이블에 연이어 병합
    
  • 레벨 컴팩션 (leveled compaction) 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 레벨로 이동하므로 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용
    

LSM 트리의 기본 개념은 백그라운드에서 연쇄적으로 SS테이블을 지속 병합하는 것. 정렬되어 있어 범위 질의가 효율적이고, 디스크 쓰기가 순차적이라 쓰기 처리량이 높음.

B트리

• 가장 널리 사용되는 색인 구조
• 가변 크기인 세그먼트가 아닌, 고정 크기의 블록이나 페이지로 나눔
• 루트에서 시작하여 범위 검색하여 최종적으로 개별 키(리프 페이지)를 포함하는 페이지에 도달
• 트리가 계속 균형을 유지하는 것이 보장됨

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

• B트리 기본적인 쓰기 동작은 새로운 데이터를 덮어쓰는 것
• 고장 상황에서 스스로 복구할 수 있도록 쓰기 전 로그(write-ahead log)를 추가하여 트리를 구현 쓰기 전 로그는 변경된 내용을 트리에 적용하기 전, 모든 B트리 변경사항을 기록하는 추가 전용 파일
  
• 동시성 제어는 래치(latch)로 트리의 데이터 구조를 보호

B트리 최적화

• 쓰기 전 로그 유지 대신, 쓰기 시 복사 방식(copy-on-write scheme) 사용
• 페이지에 전체 키를 저장하는 것이 아닌, 키를 축약해 쓰기
• 트리에 포인터 추가

B트리 최적화

• 쓰기 전 로그 유지 대신, 쓰기 시 복사 방식(copy-on-write scheme) 사용
• 페이지에 전체 키를 저장하는 것이 아닌, 키를 축약해 쓰기
• 트리에 포인터 추가

B트리와 LSM트리 비교

• 읽기 : B트리 > LSM트리
• 쓰기 : B트리 < LSM트리

LSM트리 장점

• B트리 색인은 모든 데이터 조각을 최소한 두 번 기록해야 한다. (쓰기 전 로그, 트리 페이지)
• 데이터베이스에 쓰기 한 번이 데이터베이스 수명 동안 디스크에 여러 번의 쓰기를 야기하는 효과를 쓰기 증폭이라고 한다.
• LSM트리는 B트리보다 쓰기 처리량을 높게 유지할 수 있다. LSM트리가 쓰기 증폭이 더 낮고, 트리에서 여러 페이지를 덮어쓰는 것이 아니라, 순차적으로 컴팩션된 SS테이블을 쓰기 때문
  
• 압축률이 더 좋다.

LSM트리 단점

• 컴팩션 과정이 진행 중인 읽기, 쓰기 성능에 영향을 준다. 컴팩션 연산은 비쌈. 이게 끝날 때까지 대기해야할 수도.
  
• 쓰기 처리량이 높아, 컴팩션이 유입 쓰기 속도를 따라가지 못해, 병합되지 못한 세그먼트로 인해 디스크 공간이 부족해질 수 있다.
• B트리는 각 키가 색인의 한 곳에만 정확하게 존재한다는 장점이 있다.

기타 색인 구조

색인 안에 값 저장하기

• 힙 파일 색인에서 값은 실제 로우거나, 다른 로우에 대한 참조일 수 있다. 다른 로우에 대한 참조가 저장된 곳을 힙 파일이라고 한다. 힙 파일 접근 방식은 키를 변경하지 않고 값을 갱신할 때 효율적이다.
  
• 클러스터드 로우 색인에서 힙 파일로 다시 이동하는 일은 읽기 성능에 안좋아서, 색인 안에 바로 색인된 로우를 저장하는 편이 바람직하다. 이것이 클러스터드 색인이다.
  

다중 칼럼 색인

• 결합 색인 하나의 칼럼에 다른 칼럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순히 결합한다.
  

전문 검색과 퍼지 색인

철자가 틀린 단어와 같이 유사한 키에 대해 검색할 수 있도록 한다. (애매모호한 질의)

퍼지 검색 기술에는 머신러닝이 사용된다.

모든 것을 메모리에 보관

디스크는 지속성이 있고, 저렴하다는 장점이 있다.

램이 점점 저렴해져서 메모리에 전체를 보관하는 것도 꽤 현실적인 선택지가 되었고, 여러 장비에 분산 저장할 수 있다. → 인메모리 데이터베이스

인메모리 데이터베이스가 지속성을 달성하기 위해, 특수 하드웨어를 사용하거나 디스크에 주기적인 스냅숏을 기록할 수 있다.

인메모리 데이터베이스는 디스크 기반 색인으로 구현하기 어려운 데이터 모델을 제공할 수 있다.

트랜잭션 처리나 분석?

• 온라인 트랜잭션 처리 (OLTP) 색인을 사용해 일부 키에 대한 적은 수의 레코드를 찾는다. 사용자 입력 기반으로 레코드가 삽입, 갱신된다.
  
• 온라인 분석 처리 (OLAP) 데이터 분석 용도. 많은 수의 레코드를 스캔하여 레코드당 일부 칼럼만 읽어 집계 통계한다.
  

데이터 웨어하우징

• 데이터 웨어하우스 OLTP는 높은 가용성과 낮은 지연 시간의 트랜잭션 처리를 기대한다. OLTP 데이터베이스에 분석 질의를 실행면 비용이 비싸고, 트랜잭션 성능을 저하시킬 수 있다. 분석가들이 OLTP에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스
  
• ETL (Extract-Transform-Load) OLTP 데이터베이스에서 추출하고, 분석 친화적 스키마로 변환하고, 데이터 웨어하우스에 적재하는 과정
  

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

분석용과 OLTP에서의 색인 알고리즘은 달라야 한다. 분석 데이터베이스는 분석에 적합한 개별 데이터 모델을 갖는다.

• 별 모양 스키마 중심에 사실 테이블이 있다. 사실 테이블의 일부 칼럼은 실제 속성이고, 다른 칼럼은 차원 데이블이라는 다른 테이블을 가리키는 외래 키 참조이다. 사실 테이블이 가운데 있고, 차원 테이블로 둘러싸고 있는 테이블 관계
  
• 눈꽃송이 모양 스키마 별 모양 스키마의 변형으로, 차원이 하위 차원으로 더 세분화됨
  

칼럼 지향 저장소

데이터 웨어하우스 질의는 한 번에 적은 수의 칼럼에만 접근한다. 많은 수의 로우에 접근하지만, 접근할 칼럼 수는 매우 적다.

대부분의 OLTP 데이터베이스에서 저장소는 로우 지향 방식으로 데이터를 배치한다. 테이블에서 한 로우의 모든 값은 서로 인접하게 저장된다. 이 경우, 분석용 질의를 처리하려면 모든 로우를 메모리로 적재한 다음 구문을 해석해 필요한 조건을 충족하지 않은 로우를 필터링해야한다.

• 칼럼 지향 저장소의 개념 모든 값을 하나의 로우에 함께 저장하지 않는 대신 각 칼럼별로 모든 값을 함께 저장한다. 각 칼럼을 개별 파일에 저장하면 질의에 사용되는 칼럼만 읽고 구분 분석하면 된다.
  

칼럼 압축

압축하면 디스크 처리량을 더 줄일 수 있다. 칼럼 지향 저장소는 압축에 적합하다.

• 비트맵 부호화 보통 칼럼에서 고유 값의 수는 로우 수에 비해 적다. n개의 고유 값을 가진 칼럼을 n개의 개별 비트맵으로 변환할 수 있다. 비트맵 색인은 데이터 웨어하우스에서 일반적으로 사용되는 질의 종류에 매우 적합하다.
  

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

데이터 웨어하우스 질의는 디스크로부터 메모리로 데이터를 가져오는 대역폭이 큰 병목이다.

디스크로부터 적재할 양 줄이기 외에도 칼럼 저장소 배치는 CPU 주기를 효율적으로 사용하기에 적합하다.

비트 AND, OR과 같은 연산자는 압축된 칼럼 데이터 덩어리를 바로 연산할 수 있게 설계할 수 있다. 이런 기법이 벡터화 처리다. (사실 이해 잘 안갔음..; 다시 볼 부분)

칼럼 저장소의 순서 정렬

칼럼 저장소에서 로우가 저장되는 순서가 반드시 중요하지는 않다. 하지만 순서를 도입해 색인 메커니즘으로 사용할 수 있다.

각 칼럼을 독립적으로 정렬할 수는 없다. 그렇게 하면 칼럼의 어떤 항목이 동일한 로우에 속하는지 알 수 없기 때문이다.

순서 정렬하면 칼럼 압축에 도움이 된다.

다양한 순서 정렬

데이터를 잃지 않으려면 여러 장비에 복제해둬야 한다. 복제 데이터를 서로 다른 방식으로 정렬해서 저장하면 질의를 처리할 때 질의 패턴에 가장 적합한 버전을 사용할 수 있다.

칼럼 지향 저장소에서 여러 정렬 순서를 갖는 것은, 로우 지향 저장소에서 여러 2차 색인을 갖는 것과 비슷하다.

칼럼 지향 저장소에 쓰기

칼럼 지향 저장소, 압축, 정렬은 읽기 질의를 빠르게 하지만 쓰기를 어렵게 한다.

B트리 같은 제자리 갱신 접근 방식은 압축된 칼럼에서는 불가능하다.

LSM 트리가 좋은 방법이다. 모든 쓰기는 먼저 인메모리 저장소로 이동해 정렬된 구조에 추가하고 디스크에 쓸 준비를 한다. 충분한 쓰기를 모으면 디스크의 칼럼 파일에 병합하고 대량으로 새로운 파일에 기록한다.

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

• 구체화 집계 (materialized aggregate) 동일한 집계를 많은 다양한 질의에서 사용할 때, 질의가 자주 사용하는 일부 카운트나 합을 캐시하는 것
  
• 구체화 뷰 (materialized view) 위의 캐시를 만드는 방법 중 하나. RDBMS에서 일반적으로 쓰는 뷰와 살짝 다르다. 구체화 뷰는 디스크에 기록된 질의 결과의 실제 복사본이고, 가상 뷰는 단지 질의를 작성하는 단축키이다.
  

구체화 뷰는 원본 데이터의 비정규화된 복사본이기 때문에, 원본 데이터를 변경하면 구체화 뷰를 갱신해야 한다. 쓰기 비용이 비싸지만, 데이터 웨어하우스는 읽기 비중이 크기 때문에 구체화 뷰를 사용하는 전략은 합리적이다.

• 데이터 큐브 (OLAP 큐브) 구체화 뷰의 특별 사례. 다양한 차원으로 그룹화한 집계 테이블.

  • 장점 : 특정 질의를 효과적으로 미리 계산했기 때문에 해당 질의를 수행할 때 매우 빠르다.

  • 단점 : 원시 데이터에 질의하는 것과 동일한 유연성이 없다.

    데이터 큐브와 같은 집계 값은 특정 질의에 대한 성능 향상에만 사용한다.