『DDIA 3장. 저장소와 검색』

• 데이터베이스는 기본적으로 두 가지 작업을 수행한다:
  • 데이터를 받으면 데이터를 저장한다.
  • 나중에 그 데이터를 요청하면 데이터를 제공한다.

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

• kvp로 구성되어 set과 get으로 데이터를 저장, 요청할 수 있는 데이터베이스를 생각해보자.
• 레코드가 방대하면 get 성능이 $O(n)$으로 좋지 않다. 이를 해결하기 위해 색인(Index)을 사용한다.

해시 색인

• kvp 데이터를 색인하기 위해 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 만들 수 있다.
• 램에 모든 키를 저장하면 고성능의 읽기, 쓰기가 가능 하지만 결국 디스크 공간이 부족해지는 문제가 있다.
• 특정 크기의 세그먼트로 데이터를 나누면 된다:
  • 데이터가 특정 크기에 도달하면 기존 세그먼트를 닫고, 새로운 세그먼트에 쓰기를 수행하는 컴팩션을 진행한다.
  • 중복된 키를 버리고 각 키의 최신 값을 유지하기 때문에 공간을 줄일 수 있다.
• 하지만 해시 테이블 색인은 제한 사항이 있다:
  • 해시 테이블을 메모리에 저장해야 하므로 키가 너무 많으면 입출력이 많이 필요하다.
  • 디스크가 가득차면 확장하는 비용이 든다. 또한 해시 충돌 해소를 위해 성가신 로직도 필요하다.
  • 해시 테이블은 범위 질의에 효율적이지 않다. 범위 질의를 수행하기 위해선 모든 개별 키를 조회해야 한다.

SS테이블과 LSM 트리

• SS테이블(Sorted String Table)은 일련의 kvp를 키로 정렬한 테이블이다.
• 키가 정렬되어 있으면 세그먼트 병합을 효율적으로 할 수 있다.
• 주변 키의 오프셋을 이용해 특정 키를 쉽게 찾을 수도 있다.
• SS테이블은 데이터베이스가 고장나면 아직 디스크에 기록되지 않고 메모리의 멤테이블(Memtable)에 머물러있는 최신 데이터들이 손실된다.
• 손실을 방지하기 위해서는 쓰기를 즉시 추가할 수 있는 분리된 로그를 디스크에 유지해야 한다.

기타 색인 구조

• 색인 안에 값 저장:
  • 키는 질의가 검색하는 대상.
  • 값은 질의가 찾는 데이터거나 다른 곳의 데이터를 가리키는 참조가 될 수 있다.
  • 실제 데이터를 힙 파일(heap file)에 저장하고, 각 색인은 힙 파일의 데이터 위치만 참조한다.
• 다중 칼럼 색인:
  • 여러 개의 키에 색인을 적용할 수 있다.
  • 가장 일반적인 유형은 결합 색인(concatenated index)이다.
  • 결합 색인은 하나의 칼럼에 다른 칼럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순 결합한다.
• 전문 검색과 퍼지 색인:
  • 유사한 키(오타 등)에 대해 검색하기 위해 퍼지 검색 기술을 사용한다.
  • 전문 검색 엔진의 경우 특정 단어를 검색할 때 해당 단어의 동의어로 질의를 확장한다.

트랜잭션 처리나 분석?

• 트랜젝션 처리는 클라이언트가 지연 시간이 낮은 읽기와 쓰기를 가능하게 한다는 의미.
  • 반대로는 주기적으로 실행되는 일괄 처리 작업(배치 잡)이 있다.
  • 옛날에는 데이터베이스를 주로 상거래에 사용했기 때문에 트랜잭션이라는 용어를 사용했다.
  • 이러한 접근 패턴을 온라인 트랜잭션 처리(Online Transaction Processing, OLTP)라고 한다.
• 처음에는 트랙잭션 처리와 분석 질의를 위해 동일한 데이터베이스를 사용했다.
• 데이터가 방대해지자 분석을 위한 개별 데이터베이스를 만들었다:
  • 많은 회사들이 분석을 위한 개별 데이터베이스를 만들었으며, 이를 데이터 웨어하우스라고 불렀다.
  • 이러한 접근 패턴은 OLTP와 구별하기 위해 온라인 분석 처리(Online Analytic Processing, OLAP)라고 한다.

데이터 웨어하우징

• 개별 데이터 웨어하우스를 사용하는 큰 장점은 분석 접근 패턴에 맞게 최적화할 수 있다는 점이다.
• 데이터 웨어하우스와 OLTP 데이터베이스는 둘 다 SQL 인터페이스를 지원하기 때문에 비슷해 보이지만, 내부는 서로 다른 질의 패턴에 맞게 최적화됐기 때문에 완전히 다르다.

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

• 분석 영역의 데이터 모델은 트랜잭션 처리 영역과 다르게 다양성이 훨씬 적다.
• 많은 데이터 웨어하우스가 별 모양 스키마로 알려진 정형화된 방식을 사용한다.
  • 사실 테이블(fact table): 특정 시각에 발생한 이벤트의 집합.
  • 차원 테이블(dimension table): 사실 테이블의 일부 컬럼이 외래키로 가리키는 테이블. (이벤트의 속성을 나타낸다.)
  • 별 모양이라는 이름은 테이블 관계를 시각화했을 때 중앙에 있는 사실 테이블을 차원 테이블로 둘러싸고 있는 모습에서 비롯됐다.
• 눈꽃송이 모양 스키마는 별 모양 스키마의 차원을 더욱 세분화하여 변형한 템플릿이다.

칼럼 지향 저장소

• 테이블의 데이터가 방대해지면 효율적으로 저장하고 질의하기 어려워진다.
• 칼럼 지향 저장소는 값을 로우 단위가 아닌 칼럼 단위로 저장하는 방식이다.
• 칼럼 지향 저장소 배치는 각 칼럼에 포함된 로우가 모두 같은 순서인 점에 의존한다.
• 데이터를 압축하면 데이터 처리량을 더 줄일 수 있으며, 데이터 웨어하우스에서 특히 효과적인 방법은 비트맵 부호화다.

이 문서를 인용한 문서

• 『데이터 중심 어플리케이션 설계(DDIA)』

  • 3장. 저장소와 검색