1. 저장소와 검색
•
가장 기본적인 수준에서 DB는 두 가지 작업을 수행한다.
◦
어떤 데이터를 받으면 데이터를 저장하고 나중에 그 데이터를 요청하면 다시 제공한다.
•
특정 작업부하 유형에서 좋은 성능을 내게끔 저장소 엔진을 조정하려면 저장소 엔진이 내부에서 수행되는 작업에 대해 대락적인 개념을 이해할 필요가 있음
2. 데이터베이스를 강력하게 만드는 데이터 구조
•
가장 기본적인 데이터베이스는 key-value 형식의 bash 명령어를 통해 파일에 저장하는 문서로 예시를 들수 있다.
•
많은 데이터베이스는 내부적으로 추가 전용 데이터 파일인 로그를 사용한다.
◦
로그는 일반적인 의미로 연속된 추가 전용 레코드다.
◦
로그는 사람이 읽을 수 있는 형식일 필요는 없다.
•
실제 데이터베이스는 다뤄야 할 더 많은 문제(동시성 제어, 오류처리, 레코드 처리 등)가 있지만 기본적인 원리는2.1 동일하다.
2.1 색인
•
데이터베이스에서 특정 키의 값을 효율적으로 찾기 위한 데이터 구조를 색인이라 한다.
•
색인은 기본 데이터(primary data)에서 파생된 추가적인 구조다.
•
많은 데이터베이스는 색인의 추가와 삭제를 허용한다.
•
어떤 색인이라도 쓰기 속도는 대개 느리지만 읽기 질의 속도 향상과의 트레이드오프를 적절히 선택해야 한다.
3. 해시 색인
•
키-값 데이터 색인 구조로 대부분의 프로그래밍 언어에서 볼 수 있는 사전타입과 매우 유사하다.
•
파일에 새로운 키-값 쌍을 추가할 때마다 기록한 데이터의 오프셋을 반영하기 위해 해시맵도 갱신해야 한다.
•
단순해 보이지만 실제로 많이 사용하는 접근법으로 비트캐스크(Bitcask)가 근본적으로 사용하는 방식이다.
◦
비트캐스크는 해시 맵을 전부 메모리에 유지하기 때문에 사용 가능한 램에 모든 키가 저장된다는 조건을 전제로 공성능 읽기/쓰기를 보장
◦
각 키의 값이 자주 갱시되는 상황에 매우 적합하다.
•
하지만 파일에 계속 키를 추가한다면 디스크 공간이 부족해지기 때문에 세그먼트를 이용해 로그를 나눌 수 있다.
◦
세그먼트 파일에 대해 컴팩션을 수행하여 중복된 키를 버리고 각 키의 최신 갱신 값만 유지한다.
•
병합을 통해 세그먼트 수를 적게 유지하기 때문에 조회할 때 많은 해시 맵을 확인할 필요가 없다.
3.1. 해시 색인의 중요 고려사항
•
파일 형식
◦
CSV는 로그에 가장 적합한 형식이 아니다.
◦
바이트 단위의 문자열 길이를 부호화한 다음 원시 문자열을 부호화하는 바이너리 형식을 사용하는 편이 더 빠르고 간단하다.
•
레코드 삭제
◦
키와 관련된 값을 삭제하려면 데이터 파일에 특수한 삭제 레코드(툼스톤 이라 불림)를 추가해야한다.
◦
로그 세그먼트가 병합될 때 툼스톤은 병합 과정에서 삭제된 키의 이전 값을 무시하게 한다.
•
고장(Crash) 복구
◦
데이터베이스를 재시작하면 인메모리 해시 맵은 손실되지만 세그먼트 해시맵을 통해 복원할 수 있다.
•
부분적으로 레코드 쓰기
◦
비트캐스크 파일은 체크섬을 포함해 로그의 손상된 부분을 탐지해 무시할 수 있다.
•
동시성 제어
◦
쓰기를 엄격하게 순차적으로 로그에 추가할 때 일반적인 구현 방법은 하나의 쓰기 스레드만 사용하는 것이다.
◦
데이터파일 세그먼트는 추가 전용이거나 불변이므로 다중 스레드로 동시에 읽기 가능
3.2. 해시 테이블 색인의 제약 사항
•
메모리에 저장해야 하는 키가 너무 많으면 문제가 된다.
•
범위 질의에 효율적이지 않다.
3.3. SS테이블과 LSM트리
•
세그먼트 파일의 형식에 키-값 쌍을 키로 정렬하는 간단한 변경사항을 추가해보자
◦
키로 정렬된 형식을 정렬된 문자열 테이블(Sorted String Table) 또는 짧게 SS테이블이라 부른다.
•
SS테이블은 해시 색인을 가진 로그 세그먼트보다 몇 가지 큰 장점이 있다.
◦
세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적이다.
▪
이 접근법은 병합정렬(mergesort) 알고리즘에서 사용하는 방식과 유사하다.
◦
파일에서 특정 키를 찾기 위해 더는 메모리에 모든 키의 색인을 유지할 필요가 없다.
◦
읽기 요청은 요청 범위 내에서 여러 키-값 쌍을 스캔해야 하기 때문에 해당 레코드들을 블록으로 그훕화라고 디스크에 쓰기 전에 압축한다.
▪
디스크 공간 절약과 I/O 대역폭 사용도 줄여준다.
3.3.1. SS테이블 생성과 유지
•
유입되는 쓰기는 임의 순서로 발생한다.
•
디스크 상에 정렬된 구조를 유지하는 일은 가능하지만 메모리에 유지하는 편이 훨씬 쉽니다.
•
레드 블랙 트리나 AVL 트리같이 잘 알려진 데이터 구조를 이용해 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 다시 읽을 수 있다.
◦
쓰시가 들어오면 인메모리 트리에 데이터를 추가한다. ⇒ 멤테이블
◦
멤테이블이 보통 수 메가바이트 정도의 임곗값보다 커지면 SS테이블 파일로 디스크에 기록한다.
◦
읽기 요청을 제공하려면 멤테이블에서 키를 찾고 디스크 상의 가장 최신 세그먼트를 찾고 두 번째 세 번째… 계속 반복한다.
◦
가끔 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 병합과 컴팩션을 백그라운드로 수행한다.
3.3.2. SS테이블에서 LSM 트리 만들기
•
리악에서는 비트캐스크의 대안으로 레벨DB를 구글의 빅테이블 논문에서 영감을 얻은 카산드리와 HBase에서도 유사한 저장소 엔진을 사용함
•
원래 이 색인의 구조는 로그 구조화 병합 트리란 이름으로 패트릭 오닐 등이 발표했다.
•
정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라 부른다.
3.3.3. 성능 최적화
•
LSM 트리 알고리즘은 데이터베이스에 존재하지 않는 키를 찾는 경우 느릴 수 있다.
•
없는 키를 찾아 멤테이블→최근 세그먼트 접근을 지속적으로 해야하기 때문이다.
◦
이런 경우 접근 최적화를 위한 블룸 필터를 추가적으로 사용한다.
▪
집합 내용을 근사한 메모리 효율적 데이터 구조로 키가 데이터베이스에 없음을 알려준다.
•
SS테이블을 압축하고 병합하는 순서와 시기를 결정하는 일반적인 전략으로는 크기 계층과 레벨 컴팩션이다.
◦
사이즈 계층 컴팩션 = 상대적으로 좀 더 새롭고 작은 SS테이블을 상대적으로 오래됐고 큰 SS테이블에 연이어 병합
◦
레벨 컴팩션 = 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별레벨로 이동하여 컴팩션을 점진적으로 진행
•
세부 사항이 있지만 LSM 트리의 기본 개념은 간단하고 효과적
◦
LSM 트리의 기본 개념은 백그라운드에서 연쇄적으로 SS테이블을 지속적으로 병합하는 것
▪
데이터셋이 가능한 메모리가 훨씬 더 크더라도 효과적
◦
데이터가 정렬되 질의를 효율적으로 실행할 수 있고 디스크 쓰기가 순차적이기 때문에 높은 처리량을 보장할 수 있음
4. B트리
•
앞서 설명한 로그 구조화 색은 보편화되고 있지만 일반적이지 않고 가장 널리 사용되는건 B 트리 구로조 로그 구조화 색인과는 상당히 다름
◦
1970년대 등장해 거의 대부분 관계형 데이터베이스에서 표준 색인으로 구현되고 비관계형에서도 사용한다.
4.1. B트리의 설계 철학
•
로그 구조화 색인은 수 메가바이트 이상의 가변크기의 세그먼트로 나누는 반면 B트리는 전통적으로 4KB 크기의 고정블록이나 페이지로 나눈다.
•
각 페이지는 주소나 위치를 이용해 식별할 수 있고 이를 통해 하나의 페이지가 다른 페이지를 참고할 수 있다.
•
한 페이지의 B트리의 루트를 시작으로 페이지 탐색을 시작하고, 페이지는 여러 키와 하위 페이지 참조를 포함한다.
•
페이지 탐색은 루트로 부터 시작해 최종적으로 개별 키(리프 페이지)에 도달한다.
•
B트리의 한 페이지에서 하위 페이지를 참조하는 수를 분기 계수(branching factor)라고 부른다.
◦
실제로 분기 계수는 페이지 참조와 범위 경계를 저장할 공간의 양에 의존적이고 보통 수백 개에 달한다.
페이지 분리 과정
•
새로운 키를 추가하기 위해선 새로운 키를 포함하는 범위의 페이지를 찾아 추가한다.
◦
페이지에 충분한 여유공간이 없다면 페이지 하나를 반쯤 채워진 페이지 둘로 나눠 상위 페이지가 새로운 키 범위를 알 수 있게 갱신한다.
•
해당 알고리즘을 통해 트리가 균형이 유지될 수 있도록 보장한다.
4.2. 신뢰할 수 있는 B트리 만들기
•
B트리의 기본 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓴다.
•
덮어쓰기가 페이지 위치를 변경하지 않는다 가정하기 때문에 페이지를 가르키는 참조는 남아있게 된다.
•
페이지를 나누게 된다면 하위 페이지 참조를 갱신하게끔 상위 페이지를 덮어써야 한다.
◦
일부만 기록할 시 색인이 훼손되고 고아 페이지가 발생하는 위험한 동작이다.
•
데이터베이스 고장 상황에서 스스로 복구할 수 있게 만들려면 디스크 상에 쓰기 전 로그(WAL) 데이터 구조를 추가한다.
•
같은 자리의 페이지 갱신의 동시성 제어는 주의깊게 제어해야 한다.
◦
그렇지 않으면 일괄성이 깨질 수 있다.
◦
보통 래치(latch)로 데이터를 보호한다.
4.3. B트리 최적화
•
페이지 덮어 쓰기와 고장 복구를 위한 WAL 유지 대신 일부 데이터베이스는 쓰기 시 복사 방식을사용한다.
•
페이지에 전체 키를 저장하는 게 아니라 키를 축약해 쓰면 공간을 절약할 수 있다.
•
트리에 양쪽 페이지에 관한 참조를 추가한다.
•
프랙탈 프리 같은 B트리 변형을 이용해 개선한다.
◦
로그 구조화 개념의 일부 도입
4.4. B트리와 LSM트리 비교
•
LSM 트리는 보통 쓰기에서 더 빠르고 B트리는 읽기에서 빠르다고 여겨진다.
◦
LSM이 읽기가 느린 이유는 각 컴팩션 단계에 있는 여러 데이터 구조와 SS테이블을 확인해야 하기 때문
•
하지만 벤치마크는 경정적이지 않기 때문에 시스템 테스트를 꼭 해보자
4.5. LSM 트리
4.5.1. 장점
•
B트리는 쓰기 전 로그와 트리 페이지에 두 번의 기록을 해야한다.
◦
또한 페이지 내 몇 바이트만 바뀌어도 전체 페이지를 기록해야 하는 오버헤드도 존재
•
쓰기 증폭 = 데이터베이스 수명 동안 디스크에 여러 번의 쓰기를 야기하는 효과
•
쓰기가 많은 애플리케이션의 경우 병목을 LSM을 도입한다면 처리량을 높게 유지할 수 있다.
◦
HDD의 경우 순차 쓰기가 임의 쓰기보다 훨씬 빠르다.
•
LSM 트리는 압축률도 B트리보다 좋기 때문에 파편화로 인한 오버헤드가 더 낮다.
◦
레벨 컴팩션을 사용하면 효과가 더 크다!
4.5.2. 단점
•
컴팩션 과정이 읽기와 쓰기 성능에 영향을 준다.
◦
디스크에 비싼 컴팩션 연산이 끝날 때까지 요청 대기가 발생하기 쉽다.
•
높은 쓰기 처리량으로 인해 백그라운드의 컴팩션과 스레드가 대역폭을 공유해야 하고 데이터가 커질수록 더 많은 디스크 대역폭이 필요하다.
◦
컴팩션 설정에 주의를 기울이지 않으면 병목이 발생할 수 있음
•
다른 세그먼트에 같은 중복 키가 다수 존재할 수 있다.
5. 기타 색인 구조
5.1. 색인 안에 값 저장
•
힙 파일에 특정 순서 없이 데이터를 저장하고 해당 파일에서 위치만 참조하고 실제 데이터는 일정한 곳에 유지한다.
•
덮에쓰기에 효과적이지만 새로운 값이 많은 공간을 필요로 한다면 위치를 이동해야 하기 때문에 복잡해진다.
◦
클러스터드 색인, 커버링 인덱스, 포괄열 있는 색인
5.2. 다중 칼럼 색인
•
하나의 컬럼에 다른 컬럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순히 결합
•
다차원 색인은 한 번에 여러 칼럼에 질의하는 조금 더 일반적인 방법
5.3. 전문 검색과 퍼지 색인
•
예정
5.4. 인메모리 색인
•
램이 점점 저렴해짐에 따라 메모리에 전체 데이터를 보관하는 방식도 점점 현실적이게 됨
•
이런 이유로 인메모리 데이터베이스가 개발
•
인메모리 데이터베이스가 재시작 되는 경우 특수 하드웨어를 사용하지 않는다면 디스카나 네트워크를 통해 복제본에서 상태를 다시 적재해야 함
•
인메모리 데이터베이스는 성능 외에도 디스크 기반 색인으로 구현하기 힘든 우선순위 큐, set 같은 다양한 데이터 모델을 제공 가능함
6. 트랜잭션 처리와 분석
•
초창기 비즈니스 데이터 처리는 데이터베이스에 각종 판매, 공급, 발주, 급여 등과 같은 커머셜 트랜잭션에 해당했다.
•
여기서 트랜잭션이란 용어는 변하지 않고 논리 단위 형태로서 읽기와 쓰기 그룹을 나타내고 있다.
•
온라인 트랜잭션 처리(OLTP) = 색인을 사용해 일부 키에 대한 적은 수의 레코드를 찾고 사용자 입력을 기반으로 삽입/갱신된다. 대화식
•
온라인 분석 처리(OLAP) = 원시 데이터 반환이 아닌 많은 수의 레코드를 스캔해 일부 칼럼만 읽어 집계 통계를 계산하는 행동
6.1. OLTP와 OLAP의 차이
•
1980년대 후반과 1990년대 초반 회사들은 OLTP 시스템을 분석 목적으로 사용하지 않고 개별 데이터 베이스에서 분석을 수행하려는 경향을 보임
•
이 개별 데이터베이스를 데이터 웨어하우스라고 부름
6.2. 데이터 웨어하우징
데이터 웨어하우스에 대한 ETL의 간략한 개요
•
OLTP 시스템은 사업 운영에 대단히 중요하기 떄문에 일반적으로 높은 가용성고 낮은 지연시간의 트랜잭션 처리를 기대
•
이 때문에 비즈니스 분석가가 OLTP 데이터베이스에 즉석 분석 질의(adhoc anaytic query)를 실행하는 것을 꺼려함
•
데이터 웨어하우스는 분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스
•
데이터 웨어하우스는 회사 내의 모든 다양한 OLTP 시스템에 있는 데이터의 읽기 전용 복사본
•
데이터 웨어하우스로 데이터를 가져오는 과정을 ETL(Extract-Transform-Load)라고 함
6.3. 분석용 스키마: 별 모양 스키마와 눈꽃송이 모양 스키마
•
많은 데이터 웨어하우스는 별 모양 스키마로 알려진 상당히 정형화된 방식을 사용한다.
◦
별 모양 스키마(star schema)는 스키마 중심에 소위 사실 테이블(fact table)과 차원 테이블(dimension table)의 결합
▪
fact table의 각 로우는 특정 시각에 발생한 이벤트에 해당(구매 이력)
▪
dimension table은 이벤트의 속성인 누가, 언제, 어디서, 무엇을, 어떻게, 왜를 나타냄(상품, 가게 등)
•
해당 템플릿의 변형으로 눈꽃 스키마는 dimension이 하위 dimension으로 더 세분화 됨
◦
예를 들어 브랜드와 제품 카테고리의 테이블을 분리할 수 있음
•
눈꽃 스키마는 star schema보다 더 정규화 됐지만 분석가들은 더 쉽다는 이유로 star schema를 더 선호함
6.4. 칼럼 지향 저장소
•
데이터가 크다면(페타바이트) 효율적 저장과 질의가 어렵다.
•
일반적인 데이터 웨어하우스 질의는 한 번에 4개 또는 5개 정도의 칼럼만 접근한다.
•
대부분의 OLTP 데이터베이스에서 저장소는 로우 지향 방식으로 데이터를 배치한다.
•
문서 데이터베이스에서 전체 문서는 보통 하나의 연속된 바이트 열로 저장
•
칼럼 지향 저장소의 기본 개념은 모든 값을 하나의 로우에 저장하지 않고 각 칼럼별로 모든 값을 함께 저장한다.
•
칼럼 지향 저장소 배치는 칵 컬럼 파일에 포함된 로우가 모두 같은 순서
•
때문에 로우의 전체 값을 다시 모으려면 개별 칼럼 파일의 n번째 항목을 가져온 다음 데이블의 n번째 로우 형태로 함께 모아 구성이 가능
6.5. 구체화 뷰
•
대부분의 데이터 웨어하우스 질의는 보통 COUNT, SUM, AVG, MIN, MAX 같은 집계 함수를 포함
•
동일한 집계를 다양한 질의에서 사용하는 것은 낭비이기 때문에 질의가 자주 사용하는 COUNT나 SUM을 캐시하는 건 어떨까?
•
이런 캐시를 만드는 방법이 구체화 뷰(materialized view)
•
관계형 데이터 모델에서는 이런 캐시를 일반적으로 표준(가상) 뷰로 정의함
•
원본 데이터를 변경하면 구체화 뷰를 갱신해야 하는데 이런 갱신으로 인한 쓰기는 비용이 비싸기 때문에 OLTP 데이터베이스에서는 구체화 뷰를 자주 사용하지 않음
•
집계 값은 특정 질의에 대한 성능 향상에만 사용하고 데이터 웨어하우스는 가능한 한 많은 원시 데이터를 유지하려고 함
