저장소와 검색
데이터베이스가 어떻게 저장과 검색을 다루는지 근본적인 내용에 대한 장이다.
데이터베이스를 강력하게 만드는 데이터 구조
다음과 같은 키-값 저장소로 이뤄진 DB를 생각해보자.
#!/bin/bash
db_set () {
echo "$1,$2" » database
}
db_get () {
grep "A$1," database j sed -e "s/A$1,//" j tail -n 1
}$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attracti에 s":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}많은 데이터베이스는 내부적으로 추가 전용(append-only) 데이터 파일인 로그(log)를 사용한다.
반면 db_get 함수는 데이터베이스에 많은 레코드가 있으면 성능이 매우 좋지 않다. : O(n)
데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서는 다른 데이터 구조가 필요하다. 바로 색인이다.
색인의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것이다.
기본 데이터(primary data)에서 파생된 추가적인 구조. 데이터베이스의 내용에는 영향을 미치지 않는다. 단지 질의 성능에만 영향을 준다.
색인을 잘 선택했다면 읽기 질의 속도가 향상된다. 하지만 모든 색인은 쓰기 속도를 떨어뜨린다.
해시 색인
보통 해시 맵으로 구현
키를 데이터 파일의 오프셋에 매핑해서 인메모리 해시 맵을 유지
비트캐스크가 근본적으로 사용하며 키가 자주 갱신되는 상황애 적합
하지만 추가만 한다면 디스크 공간 부족 문제 발생
-> 특정 크기에 세그먼트로 로그를 나눈다. 특정 크기에 도달하면 세그먼트를 닫고 새로운 세그먼트를 열며 세그먼트 파일에 대한 compaction을 수행한다. compaction은 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것.
컴팩션 후 세그먼트는 작아지기 때문에 여러 세그먼트를 병합하는 일이 수행된다.
제한 사항 존재
- 키가 너무 많으면 문제 -> 디스크/해시 충돌 해소
- 범위 질의에 효율적이지 않다.
SS 테이블과 LSM 트리
정렬된 문자열 테이블 = SS 테이블
SS 테이블의 장점
- 정렬되어 있으므로 병합이 효율적
- 특정 키를 찾기 위해서 메모리에 모든 키의 색인을 유지할 필요가 없다. -> 정렬된 키 보고 찾음
- 레코드들을 블록으로 그룹화하과 디스크에 쓰기 전에 압축 -> 디스크 공간 절약/IO 대역폭 감소
데이터를 키로 정렬하려면?
디스크 상에 정렬된 구조를 메모리에 유지하는 편이 더 쉽다.
이 때 멤 테이블이라는 인메모리 트리를 정렬 후 SS 테이블에 저장.
데이터베이스가 고장나면 SS 테이블에 저장하기 전에 멤 테이블 데이터 손실될 수 있다 -> 로그 필요
LSM 트리는 로그 구조화 파일 시스템의 기반이 되는 트리 구조.
정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진 = LSM 저장소 엔진
LSM 트리는 존재하지 않는 키를 찾을 경우 느리므로 블룸 필터 사용.
크기 계층 (size-tiered), 레벨 컴팩션(leveled compaction) 이용해서 SS 테이블 압축 및 병합 시기 결정.
크기 계층 : 작고 새로운 SS 테이블을 크고 오래된 SS 테이블에 병합
레벨 컴팩션 : 키 범위를 더 작은 SS 테이블로 나누고 오래된 테이블은 개별 레벨로 이동하여 점진적 컴팩션 진행
B트리
가장 널리 사용되는 색인 구조
SS 테이블처럼 정렬된 키-값 구조이기에 검색, 범위 질의에 효과적이지만 SS 테이블과 철학이 다르다.
SS 테이블의 세그먼트와 달리 B 트리는 특정 크기를(보통 4KB) 기반으로 블록이나 페이지로 나누고 페이지에 읽기/쓰기 작업을 진행 -> 하드웨어 친화적
B트리와 LSM 트리
LSM 트리 : 일반적으로 쓰기 빠르다 -> SS 테이블 / 컴팩션 단계의 데이터 확인해야 하기 때문엥 읽기 느림
B 트리 : 일반적으로 읽기 빠르다
B트리와 비교했을 때 LSM 트리의 장점
B 트리 색인은 쓰기 시 모든 데이터를 최소한 두번 기록 (로그/트리 페이지) -> 쓰기 증폭 발생
LSM 트리는 여러 페이지를 덮어 쓰지 않고 순차적으로 SS 테이블에 쓰기때문에 처리량 높다.
LSM 트리는 압축률이 좋다 -> B 트리보다 더 적은 파일 생성, 파편화 발생 x
B트리와 비교했을 때 LSM 트리의 단점
컴팩션 과정이 읽기/쓰기 성능에 영향을 줄 수 있다.
컴팩션이 데이터 유입 속도를 따라가지 못하면 세그먼트가 매우 많아진다.
B 트리는 키가 색인의 한곳에만 정확히 존재 -> 키 범위의 잠금에 유리(transaction semantic)
OLTP와 OLAP
OLTP (online transaction processing) : 온라인 트랜잭션 처리
- 읽기/쓰기 적은 양
- 일반 사용자
- 데이터 최신 상태
OLAP (online analytic processing) : 온라인 분석 처리
- 읽기/쓰기 대규모 데이터
- 분석가 사용
- 일어난 이벤트 이력
데이터 웨어 하우스
분석가들이 OLTP 작업에 영향 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스
이 때 ETL을 이용하여 데이터 적재
Extract - Transform - Load
드릴 다운, 슬라이싱, 다이싱 등의 작업을 통해서 분석가가 질의, 탐색 -> 버티카도 이 중 하나
해당 작업은 질의가 많은 수의 로우를 순차적으로 스캔해야 하므로 색인은 적절하지 않고 디스크에서 읽는 데이터 양을 최소화하기 위해서 데이터를 작게 부호화하는 일이 중요하다.
이 때 컬럼 지향 저장소를 사용한다.
칼럼 지향 저장소 : 모든 값을 하나의 로우에 함께 저장하지 않는 대신 각 칼럼별로 모든 값을 함께 저장
