[데이터 중심 애플리케이션 설계] 03. 저장소와 검색

 

 

 

 

 

 

[데이터 중심 애플리케이션 설계] 03. 저장소와 검색

 

 

• 관계형 DB와 NoSQL DB에 사용되는 저장소 엔진에 대해 공부한다.
• 로그 구조(log-structured) 계열 저장소 엔진과 (B-tree 같은) 페이지 지향(page-oriented) 계열 저장소 엔진을 검토한다.

 

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

많은 데이터베이스는 내부적으로 추가 전용(append-only) 데이터 파일인 로그(log)를 사용한다.

• 로그 : 연속된 추가 전용 레코드(an append-only sequence of records)
• 추가 전용 파일은 조회시 풀스캔을 하기 때문에 데이터베이스에 많은 레코드가 있으면  성능이 매우 나쁘다.

데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서는 색인(index)이 필요하다.

• 색인은 기본 데이터에서 파생된 추가적인 구조다.
• 색인의 추가와 삭제는 데이터베이스의 내용에는 영향을 미치지 않는다.
• 색인을 잘 선택하면 읽기 질의 속도가 향상된다.
• 그러나 색인은 쓰기 속도를 떨어뜨린다.
  • 데이터를 쓸 때마다 색인도 갱신해야 하기 때문이다.

 

2. 해시 색인

2. 1 가장 간단한 색인 전략

• 색인으로 key-value 저장소를 쓴다.
• key 값에 value로 데이터 파일의 바이트 오프셋을 넣어둔다.
• 해시 맵을 전부 메모리에 유지하면 읽기/쓰기를 고성능으로 할 수 있다.
  • 고유 키는 아주 많지 않지만, 키의 값이 자주 갱신되는 상황에 매우 적합하다.

2.2 디스크 공간이 부족해 질 경우

• 특정 크기의 segment로 로그를 나눈다.
• 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 쓴 후 컴팩션(compaction)을 수행한다.
  • compaction : 로그에서 중복된 키를 버리고 각 키의 최신 개인 값만 유지하는 것.
  • compaction을 하면 세그먼트가 작아지므로, 여러 세그먼트를 병합할 수 있다.
  • 세그먼트는 수정이 불가하기 때문에 병합할 세그먼트는 새로운 파일로 만들도록 한다.
  • compaction 도중에는 이전 세그먼트 파일을 사용해 읽기/쓰기 요청을 처리한다.
  • 병합/compaction이 끝난 이후에 이전 세그먼트를 삭제한다.
• 조회할 때에는 다음과 같이 한다.
  • 찾고자 하는 키의 값을 최신 세그먼트 해시 맵부터 확인한다.
  • 키가 없으면, 두 번째 세그먼트를 확인한다.

2.3 추가 전용(append-only) 세그먼트의 장점

• 세그먼트 파일이 append-only이면 동시성/고장 복구가 간단해진다.
  • 값을 업데이트하는 동안 DB가 죽어도, 이전 값과 새로운 값(쓰다가 죽은 값)이 남아 있기 때문.
• 세그먼트 병합으로 시간이 지남에 따라 조각화되는 데이터 파일 문제를 피할 수 있음.
  • append-only가 아니라 update도 되고 delete도 된다면, 세그먼트를 오래 썼을 때 구멍이 생길 수 있음.

 2.4 해시 색인의 문제점

• 해시 테이블은 매모리에 저장해야 하므로 키가 너무 많으면 문제가 된다.
• 범위 질의에 효율적이지 않다. 00000~99999 사이 모든 키를 쉽게 스캔할 수 없고 해시 맵에서 모든 개별 키를 조회해야 한다.

 

3. SS 테이블과 LSM 트리

3.1 정렬된 문자열 테이블(SS테이블 : Sorted String Table)

• 세그먼트 파일의 형식에서, key 값을 정렬한 것.
• 각 키는 각 병합된 세그먼트 파일 내에 한 번만 나타나야 한다.(컴팩션 과정은 이를 이미 보장함)
• 이미 정렬된 상태이므로, 메모리에 키의 일부만을 색인을 유지할 필요가 없음.

3.2 SS테이블 생성과 유지

• red-black tree나 AVL 트리 같은 트리 데이터 구조를 사용한다.
• 쓰기 요청이 들어오면 인메모리 균형 트리(balanced tree) 데이터 구조에 추가한다. 이 인메모리 트리는 memtable이라고도 부른다.
  • memtable이 너무 커지면 SS 테이블 파일로 디스크에 기록한다.
    • memtable은 이미 정렬되어 있으므로, SS 테이블을 파일로 기록은 효율적이다.
    • 새로 만든 SS 테이블 파일은 DB의 최신 세그먼트가 된다.
    • SS 테이블을 기록하는 동안 들어온 쓰기 요청은 새로운 멤테이블 인스턴스에 기록한다.
• 읽기 요청이 들어오면 먼저 memtable에서 키를 찾는다.
  • 그 다음, 디스크 상의 가장 최신 세그먼트에서 찾는다.
  • 그 다음, 디스크 상의 두 번째 오래된 세그먼트등에서 찾는다.
• 디스크로 기록되지 않은 memtable 손실 방지를 위해 분리된 로그를 디스크에 유지하고, 기록 되면 해당 로그는 버린다.

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

LSM 트리

• 로그 구조화 병합 트리 Log-Structured Merge-Tree.
• 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라 부른다.
• LSM 트리의 기본 개념: 백그라운드에서 연쇄적으로 SS 테이블을 지속적으로 병합한다.

 

4. B 트리

LSM 같은 로그 구조화 색인이 보편화되고는 있으나 가장 일반적인 색인 유형은 아님.

• 가장 널리 사용되는 색인 구조는 B-tree.
  • 거의 대부분의 RDB에서 표준 색인 구현으로 B 트리를 사용.
  • 많은 비관계형 DB에서도 B 트리를 사용.
• B 트리는 정렬된 key-value 쌍을 유지하는 방식.
  • key 검색과 범위 검색에 효율적.
  • 그러나 LSM 과는 설계 철학이 다르다.

4.1 B 트리

• 고정 크기 블록 배열
• 각 페이지는 주소나 위치를 이용해 식별 가능.
• 하나의 페이지가 다른 페이지를 참조할 수 있음.
• B 트리의 루트 역할로 한 페이지가 지정된다.
  • 루트부터 검색 시작.

B 트리는 이미지로 보면 한 눈에 이해간다.

• 검색 

  

• 쓰기 

  

4.2 B 트리에 존재하는 키 값 갱신

• 키를 포함하고 있는 리프 페이지를 검색한다.
• 페이지의 값을 바꾼다.
• 페이지를 디스크에 기록한다.

4.3 B 트리에 새로운 키를 추가하기

• 새로운 키를 포함하는 범위의 페이지를 찾는다.
• 해당 범위의 페이지에 키와 값을 추가한다.
  • 페이지에 공간이 부족하다면, 페이지를 절반으로 쪼개고, 상위 페이지의 링크를 갱신한다.
• 위의 알고리즘은 트리가 계속 균형을 유지하는 것을 보장한다.
  • n개의 키를 가진 B 트리는 깊이가 항상 O(log n) 이다.

 

5. 기타 색인 구조

• 보조 색인
  • 색인의 각 값에 일치하는 로우 식별자 목록을 만드는 방법.
  • 로우 식별자를 추가해 각 키를 고유하게 만드는 방법.
• 색인 안에 색인된 로우를 저장
  • 클러스터드 색인(clustered index)
  • MySQL InnoDB의 경우, 테이블의 기본키가 언제나 클러스터드 색인.
  • MS의 SQL Server에서는 테이블당 하나의 클러스터드 색인을 지정 가능.
• 색인 안에 테이블의 칼럼 일부를 저장
  • 커버링 색인(covering index), 포괄열이 있는 색인(index with included column)이라 부름.
  • 어떤 질의는 색인만으로 응답이 가능("색인이 질의를 cover 했다(the index is said to cover the query)")
• 다중 칼럼 색인(multi column index)
  • 지금까지 설명한 색인은 하나의 키 값에 대한 것들.
  • 결합 색인(concatenated index)
    • 하나의 키에 여러 필드를 결합하여 키를 만든다.
    • 필드가 연결되는 순서는 색인 정의로 명시.
  • 다차원 색인(Multi-dimensional indexes)
    • 한 번에 여러 칼럼에 질의한다.
    • 특히 지리 공간 데이터에서 중요하게 사용.
    • R 트리 같은 공간 색인에 특화(specialized spatial index)된 알고리즘을 사용.

 

6. 트랜잭션 처리와 분석

• 온라인 트랜잭션 처리(OnLine Transaction Processing, OLTP)
• 온라인 분석 처리(OnLine Analytic Processing, OLAP)

특성트랜잭션 처리 시스템(OLTP)분석 시스템(OLAP)

주요 읽기 패턴	질의당 적은 수의 레코드, 키 기준으로 가져옴	많은 레코드에 대한 집계
주요 쓰기 패턴	임의 접근, 사용자 입력을 낮은 지연 시간으로 기록	대규모 불러오기, 이벤트 스트림
주요 사용처	웹 애플리케이션을 통한 최종 사용자	의사결정 지원을 위한 내부 분석가
데이터 표현	데이터의 최신 상태	시간이 지나며 일어난 이벤트 이력
데이터셋 크기	기가바이트에서 테라바이트	테라바이트에서 페타바이트
	사업 운영에 중요
	높은 가용성, 낮은 지연 시간의 트랜잭션 처리 기대
병목	디스크 탐색	디스크 대역폭

6.1 데이터 웨어하우징

data warehouse

• OLTP 작업/운영에 영향을 주지 않고, 분석가들이 마음껏 질의할 수 있는 개별 DB.
• OLTP DB의 읽기 전용 복사본.
• 분석 방법에 따라 최적화.

6.2 분석용 스키마

• 별 모양 스키마(star schema)
• 눈꽃송이 모양 스키마(snowflake schema)

6.3 칼럼 지향 저장소

칼럼 지향 저장소의 기본 개념

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