📖 오늘 읽은 범위
3장. 저장소와 검색
💡 책에서 기억하고 싶은 내용을 써보세요.
데이터베이스를 강력하게 만드는 데이터 구조
#!/bin/bash
db_set() {
echo "$1,$2" >> database
}
db_get() {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}- 키-값 저장소를 db_set, db_get 두개의 함수로 구현
- db_set key value 호출 시 데이터베이스에 key, value를 저장
- db_get key 호출 시 해당 키와 연관된 가장 최근 값을 찾아 반환
- db_set 함수와 마찬가지로 다수의 데이터베이스에서 추가 전용(append-only) 데이터 파일인 로그(log)를 사용
- db_get 함수의 경우 레코드가 많을 경우 성능이 매우 좋지 않음(O(n))
- 데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서는 '색인(index)'이라는 데이터 구조가 필요함
- 색인은 부가적인 메타데이터를 유지하는 것으로, 이 메타데이터는 이정표 역할을 함으로써 데이터의 위치를 찾는데 도움을 줌
- 색인은 읽기 질의 속도를 향상시켜 주지만 쓰기 속도를 떨어뜨림
해시 색인
- 키-값 저장소는 프로그래밍 언어의 사전 타입(dictionary type)과 유사하고 보통 hash map, hash table로 구현
- 인메모리 데이터 구조를 위한 해시맵은 이미 있으니 디스크 상의 데이터를 색인하기 위해 인메모리 데이터 구조를 사용해보자
- 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 유지
- 값을 조회할 때 해시맵을 사용해 데이터 파일에서 오프셋을 찾아 해당위치를 구하고 값을 읽음
- 위 방법은 각 키의 값이 자주 갱신되는 상황에 적합
- 하지만 파일에 항상 추가만 한다면 디스크 공간이 부족해짐
- 이 때는 특정 크기의 세그먼트(segment)로 로그를 나누어 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행
- 또한 세그먼트 파일들에 컴팩션(compaction)을 수행하여 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지
- 이 방법을 실제로 구현하려면 세부적으로 많은 사항을 고려해야 함
- 레코드 삭제
- 키와 관련된 값을 삭제하려면 데이터 파일에 특수한 삭제 레코드(툼스톤(tombstone))를 추가해야 함
- 로그 세그먼트가 병합될 때 툼스톤은 병합 과정에서 삭제된 키의 이전 값을 무시하게 함
- 고장 복구
- 데이터베이스가 재시작되면 인메모리 해시맵은 손실
- 복구하려면 전체 세그먼트 파일을 읽은 후 각 키에 대한 최신 값의 오프셋을 확인 필요
- 하지만 세그먼트 파일이 크면 해시맵을 복원하는데 오래 걸림
- 부분적으로 레코드 쓰기
- 데이터베이스는 로그에 레코드를 추가하는 도중에 죽을 수 있음
- 비트캐스크 파일은 체크섬을 포함하고 있어 로그의 손상된 부분을 탐지해 무시 가능
- 동시성 제어
- 쓰기를 엄격하게 순차적으로 로그에 추가할 때 하나의 쓰기 쓰레드만 사용하는 것이 권장됨
- 레코드 삭제
- 해시 테이블 색인의 제한 사항
- 메모리에 저장해야 하므로 키가 너무 많으면 문제가 됨
- 범위 질의(range query)가 비효율적임(해시맵은 모든 키를 개별 조회해야 함)
SS테이블과 LSM 트리
- 해시색인이 가지고 있는 제한이 없는 색인 구조
- 키로 정렬된 형식을 정렬된 문자열 테이블(Sorted String Table) 이라고 부름
- 로그 세그먼트에 비해 SS테이블이 가지는 장점
- 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적(merge sort 알고리즘과 유사)
- 파일에서 특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없음
- 디스크 공간 절약 및 압축을 이용하여 I/O 대역폭을 줄임
SS테이블 생성과 유지
- 데이터를 키로 정렬하려면?
- red-black tree나 AVL tree와 같은 데이터 구조를 이용하면 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 다시 읽을 수 있음
- 쓰기가 들어오면 인메모리 균형 트리 데이터 구조에 추가함(AVL 또는 red-black)
- 이 인메모리 트리를 멤테이블(memtable)이라고 함
- 데이터베이스가 고장나면 아직 디스크로 기록되지 않은 멤테이블에 있는 데이터는 유실
- 이를 문제를 방지하기 위해 매번 쓰기를 즉시 추가하는 분리된 로그를 디스크 상에 유지
성능 최적화
- 블룸 필터(Bloom filter)
- LSM 트리 알고리즘은 데이터베이스에 존재하지 않은 키를 찾는 경우 느릴 수 있음
- 이를 최적화하기 위해 저장소 엔진은 보통 블룸 필터를 사용
- 크기 계층과 레벨 컴팩션
B 트리
- 가장 널리 사용되는 색인구조로 로그 구조화 색인과는 상당히 다름
- 대부분의 관계형 데이터베이스에서 표준 색인 구현으로 B 트리를 사용
- SS테이블과 같이 키로 정렬된 키-값 쌍을 유지하기 때문에 키-값 검색과 범위 질의에 효율적
- 일반적으로 4KB 크기의 고정 크기 블록이나 페이지로 나누고 한번에 하나의 페이지에 읽기 또는 쓰기를 진행
- 각 페이지는 주소나 위치를 이용해 실별할 수 있기 때문에 이방식으로 하나의 페이지가 다른 페이지를 참조할 수 있음
- 한 페이지는 B 트리의 루트로 지정되고 색인에서 키를 찾으려면 루트에서 시작
- 페이지는 여러 키와 하위 페이지의 참조를 포함
- 키 값을 갱신하려면 먼저 키를 포함하고 있는 리프 페이지를 검색 후 페이지의 값을 바꾼 다음 페이지를 디스크에 다시 기록
- 새로운 키를 추가하려면 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가
- 이 알고리즘은 트리가 계속 균형을 유지하는 것을 보장
- n개의 키를 가진 B트리는 깊이가 항상 O(log n)
LSM 트리의 장점
- LSM 트리는 보통 B트리보다 쓰기 처리량을 높게 유지 가능
- B트리보다 압축률이 더 좋음
LSM 트리의 단점
- 컴팩션 과정이 떄로는 진행중인 읽기와 쓰기의 성능에 영향을 줌
- 디스크 쓰기 대역폭의 한계
- B트리의 장점은 각 키가 색인의 한 곳에만 정확하게 존재한다는 점
- 이런 B트리의 측면 때문에 강력한 트랜잭션을 제공하는 데이터베이스에는 B트리가 훨씬 유용
다중 칼럼 색인
- 하나의 컬럼에 다른 컬럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순히 결합
- 다차원 색인은 한 번에 여러 칼럼에 질의하는 조금 더 일반적인 방법
모든 것을 메모리에 보관
- 램이 점점 저렴해짐에 따라 메모리에 전체 데이터를 보관하는 방식도 점점 현실적이게 됨
- 이런 이유로 인메모리 데이터베이스가 개발
- 인메모리 데이터베이스가 재시작 되는 경우 특수 하드웨어를 사용하지 않는다면 디스카나 네트워크를 통해 복제본에서 상태를 다시 적재해야 함
- 인메모리 데이터베이스는 성능 외에도 디스크 기반 색인으로 구현하기 힘든 우선순위 큐, set 같은 다양한 데이터 모델을 제공 가능함
트랜잭션 처리나 분석
- 데이터베이스를 트랜잭션 처리 뿐만이 아니라 데이터 분석에도 점점 더 사용하기 시작
- 초반에는 트랜잭션 처리와 분석 질의를 위해 동일한 데이터베이스를 사용
- 1980년대 후반과 1990년대 초반 회사들은 OLTP 시스템을 분석 목적으로 사용하지 않고 개별 데이터 베이스에서 분석을 수행하려 함
- 이 개별 데이터베이스를 데이터 웨어하우스라고 부름
데이터 웨어하우징
- OLTP 시스템은 사업 운영에 대단히 중요하기 떄문에 일반적으로 높은 가용성고 낮은 지연시간의 트랜잭션 처리를 기대
- 이 때문에 비즈니스 분석가가 OLTP 데이터베이스에 즉석 분석 질의(adhoc anaytic query)를 실행하는 것을 꺼려함
- 데이터 웨어하우스는 분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스
- 데이터 웨어하우스는 회사 내의 모든 다양한 OLTP 시스템에 있는 데이터의 읽기 전용 복사본
- 데이터 웨어하우스로 데이터를 가져오는 과정을 ETL(Extract-Transform-Load)라고 함
분석용 스키마: 별 모양 스키마와 눈꽃송이 모양 스키마
- 대다수의 데이터 웨어하우스는 star schema로 알려진 방식을 사용
- star schema는 fact table + dimension table
- fact table의 각 로우는 특정 시각에 발생한 이벤트에 해당(구매 이력)
- dimension table은 이벤트의 속성인 누가, 언제, 어디서, 무엇을, 어떻게, 왜를 나타냄(상품, 가게 등)
- 눈꽃스키마는 dimension이 하위 dimension으로 더 세분화 됨
- 예를 들어 브랜드와 제품 카테고리의 테이블을 분리할 수 있음
- 눈꽃 스키마는 star schema보다 더 정규화 됐지만 분석가들은 더 쉽다는 이유로 star schema를 더 선호함
칼럼 지향 저장소
- fact table에 대량의 로우와 페타바이트 데이터가 있다면 효율적으로 저장하고 질의하기 어려움
- 일반적인 데이터 웨어하우스 질의는 한 번에 4개 또는 5개 정도의 칼럼만 접근함
- 대부분의 OLTP 데이터베이스에서 저장소는 로우 지향 방식으로 데이터를 배치함
- 문서 데이터베이스에서 전체 문서는 보통 하나의 연속된 바이트 열로 저장
- 칼럼 지향 저장소의 기본 개념은 모든 값을 하나의 로우에 저장하지 않고 각 칼럼별로 모든 값을 함께 저장함
- 칼럼 지향 저장소 배치는 칵 컬럼 파일에 포함된 로우가 모두 같은 순서임
- 때문에 로우의 전체 값을 다시 모으려면 개별 칼럼 파일의 n번째 항목을 가져온 다음 데이블의 n번째 로우 형태로 함께 모아 구성이 가능
칼럼 지향 저장소의 특징
- 칼럼 압축률 향상
- 칼럼 별로 데이터를 저장하기 때문에 비슷한 크기의 데이터가 반복해서 나타남
- 이는 압축을 하기에 매우 좋음
- 메모리 대역폭과 벡터화 처리
- CPU 주기를 효율적으로 사용하기에 적합
- 칼럼 압축을 사용하면 같은 양의 L1 캐시에 칼럼의 더 많은 로우를 저장 가능
- 칼럼 저장소의 순서 정렬
- 칼럼 저장소에서 로우가 저장되는 순서가 중요하지는 않음
- 하지만 순서를 도입해 이를 색인 매커니즘으로 사용 가능
- 각 컬럼을 독립적으로 정렬해 버리면 더 이상 칼럼의 어떤 항목이 동일한 로우에 속하는지 알 수 없게 됨
- 데이터베이스 관리자는 테이블에서 정렬해야 하는 칼럼을 선택할 수 있음
- 예를 들어 질의가 지난 달처럼 시간 범위를 목표로 한다면 1차 정렬 키를 date_key로 해야 함
- 그러면 질의 최적화기는 지난 달에 해당하는 로우만 스캔할 수 있으며 모든 로우를 스캔하기보다 훨씬 빠름
- 기본 정렬 칼럼에 고유 값을 많이 포함하지 않는다면 정렬한 후 기본 정렬 칼럼은 연속해서 같은 값이 길게 반복되기 때문에 칼럼 압축에 좋음
구체화 뷰
- 대부분의 데이터 웨어하우스 질의는 보통 COUNT, SUM, AVG, MIN, MAX 같은 집계 함수를 포함
- 동일한 집계를 다양한 질의에서 사용하는 것은 낭비이기 때문에 질의가 자주 사용하는 COUNT나 SUM을 캐시하는 건 어떨까?
- 이런 캐시를 만드는 방법이 구체화 뷰(materialized view)
- 관계형 데이터 모델에서는 이런 캐시를 일반적으로 표준(가상) 뷰로 정의함
- 원본 데이터를 변경하면 구체화 뷰를 갱신해야 하는데 이런 갱신으로 인한 쓰기는 비용이 비싸기 때문에 OLTP 데이터베이스에서는 구체화 뷰를 자주 사용하지 않음
- 집계 값은 특정 질의에 대한 성능 향상에만 사용하고 데이터 웨어하우스는 가능한 한 많은 원시 데이터를 유지하려고 함
