DB는 기본적으로 두가지 일을 수행한다. 데이터를 받으면 저장하고, 후에 요청하면 다시 데이터를 제공한다. 이 챕터는 데이터를 저장하는 방법과 요청하는 방법에 대해 살펴보는데 이것을 알아두어야 하는 이유는 개발자는 처음부터 저장소 엔지는 구현하는 것이 아닌 사용 가능한 여러 저장소 엔진 중에서 개발해야 하는 application 에 적합한 엔진을 선택하는 것이 중요하다.
이번 장은 익숙한 RDB, NoSQL 등의 저장소 엔진을 다룬다. 그리고 로그 구조(log-structured) 계열 저장소 엔진과 B-tree 같은 페이지 지향(page-oriented) 계열 저장소를 검토한다.
데이터베이스를 강력하게 만드는 구조
매우 간단한 형태의 DB를 bash 함수로 구현했다.
#!/bin/bash
db_set() {
echo "$1, $2" >> database
}
db_get() {
echo "^$1, " database | sed -e "s/^$1,//" | tail -n 1
}
Bash
복사
key-value 저장소의 함수이며 데이터가 저장되며 다음과 같이 실행된다.
db_set 을 호출할 때 마다 끝에 추가하므로 키를 여러번 갱신해도 예전 값을 덮어 쓰지 않으며, 최신 값은 키의 가장 마지막 항목을 살펴봐야 한다. (tail -n 1 을 실행하는 이유)
이러한 파일에 추가 작업은 매우 효율적이기 때문에 꽤 좋은 성능을 보여주고 많은 DB가 내부적으로 추가 전용 로그를 사용한다. 물론 실제 DB 라면 다뤄야 할 더 많은 문제가 있다. (동시성 제어, 로그가 영원히 사라지지 않게끔 디스크 공간 회수, 오류 처리, 부분적으로 기록된 레코드 처리 등등)
반면, db_get 은 record 가 많아질 수록 성능이 좋지 않다. key 를 찾기 위해 로그를 전부 봐야 하므로 이 된다. 레코드 수가 두배 늘면 검색도 두배 오래 걸리는 것이다.
여기서 index 가 나온다.
특정 키의 값을 효율적으로 찾기 위해 필요한 것이 색인 이다.
•
색인의 일반적인 개념은 어떤 부가적인 metadata를 유지하는 것이다.
•
기본 데이터에서 파생된 추가적인 구조이다.
◦
이 작업은 DB의 내용에 영향을 미치지 않는다.
◦
추가적인 구조(인덱스)의 유지보수는 오버헤드를 동반한다.
•
대개 쓰기 속도를 느리게 만든다. 추가시 색인도 갱신해야 하기 때문이다.
•
하지만 읽기 속도를 향상 시킬 수 있다.
해시 색인 (Hash index)
현재 DB는 key-value 저장소 형태이다. 대부분 언어에서 보는 HashMap, Dictionary 타입과 매우 유사하다. 키를 데이터 파일의 byte offset 과 매핑해 in-memory 해시 맵을 유지하는 전략으로 색인을 접근해보자
CSV와 유사한 형식의 key-value 쌍의 로그 저장하기, 인메모리 해시 맵으로 색인했다.
파일에 새로운 key-value 쌍을 추가할 때 마다 방금 기록한 데이터의 offset 을 반영하기 위해 hash map 도 갱신해야 한다.
조회할 대는 hash map 을 사용해 데이터 파일에서 offset 을 찾아 해당 위치를 구하고, 그 위치에서 값을 읽는다.
이 방식은 단순해 보이지만 많이 사용하는 접근법이다.
이 방법은 리악의 bitcask 가 사용하는 방식이다. 비트캐스크는 해시맵을 전부 메모리에 유지하기 때문에 RAM에 모든 키가 저장된다는 조건을 전제로 고성능 읽기, 쓰기를 보장한다. 게다가 데이터 파일의 일부가 파일 시스템 캐시에 있다면 읽기에 디스크 입출력도 필요하지 않다.
이런 형태의 저장소는 key 의 value 가 자주 갱신되는 상황에 매우 유용하다.
그런데 지금과 같은 상황으로 파일에 계속해서 추가만 한다면 결국 disk 공간이 부족한 상황이 발생한다. 이럴때 특정 크기의 segment로 로그를 나누는 방식이 좋은 해결책이다.
특정 크기에 도달하면 compaction을 수행한다.
key-value 로그를 컴팩션하고 각 키의 최신값을 유지한다.
컴팩션은 segment를 더 작게 만들기 때문에 여러 segment를 병합할 수 있다.
segment 가 쓰여진 후에는 변경할 수 없기 때문에 병합할 세그먼트는 새로운 파일로 만든다. 이러한 병합 과정은 background 에서 수행할 수 있으며, 병합이 종료 되면 읽기 요청은 이전 segment 대신 병합하여 새로 만들어진 segment를 사용하게끔 전환한다. (전환이 완료되면 기존 segment는 삭제)
컴팩션과 세그먼트 병합을 동시에 수행한다.
병합된 segment의 offset을 색인 in-memory hash map 에 반영한다. 병합 과정을 통해 segment 수를 적게 유지하면 조회할 때 많은 hash map을 확인할 필요가 없다.
실제 구현할 때 주의해야 할 점
•
파일 형식
◦
key-value 를 구분하는 것이 , 이다. 그렇다고 해서 CSV 가 적합한 형식은 아니다.
◦
문자열을 byte 단위로 부호화 하여 bin 형식을 갖는 것이 더 빠르고 간편한다.
•
record 삭제
◦
key 에 해당하는 값을 삭제하는 것은 특수한 삭제 record (tombstone)를 추가 하여 병합 과정에서 무시되게 해야한다.
•
crash 복구
◦
DB가 재시작 되면 in-memory hash map 은 손실된다.
◦
데이터가 커지면 hash map을 복원하는데 오래 걸리기 때문에 snapshot 을 만들어 디스크에 저장하여 복구 속도를 높일 수 있다.
•
부분적으로 record 쓰기
◦
DB에서 로그에 record를 추가하는 도중 죽을 수 있는데 bitcask 파일은 checksum 을 포함하고 있어서 로그의 손상된 부분을 탐지해 무시할 수 있다.
•
동시성 제어
◦
순차적으로 로그에 추가할 때 일반적인 구현한 single thread 이다.
◦
읽기는 immutable 하기 때문에 multi thread 로 동시에 읽기를 할 수 있다.
append-only 로그는 언뜻 보면 낭비처럼 보인다. 왜 파일의 그 자리에서 오래된 값을 갱신하지 않는 것일까?(하지만 append-only 설계는 여러 측면에서 좋은 설계이다.)
•
append-only 와 segment 병합은 순차적인 쓰기 작업이기 때문에 보통 무작위 쓰기보다 빠르다.
◦
특히 자기 회전 디스크 하드 드라이브에서 더 빠르다.
•
segment 파일이 추가 전용이나 불변이면 동시성과 고장 복구가 간단하다
◦
값을 덮어 쓰는 동안 DB 가 죽는 경우에 대해서 걱정할 필요가 없다. 이전 값 부분과 새로운 값 부분을 포함한 파일을 나누어 함께 남겨두기 때문이다.
•
오래된 segment 병합은 시간이 지나면서 조각화 문제를 피할 수 있다.
그러나 hash table index 역시 한계가 있다.
•
memory 저장이기 때문에 키가 너무 많으면 문제가 된다.
◦
해시 충돌
◦
디스크에 hash map 을 유지할 수 있지만 디스크 상에서 좋은 성능을 기대하기 어렵다.
◦
이는 무작위 접근 I/O 가 많이 발생하고 디스크가 가득 찼을 때 확장하는 비용이 비싸다.
•
range query 에 효율적이지 않다.
이런 제한이 없는 색인 구조를 만들어보자
SS테이블과 LSM 트리 (SSTables and LSM-Trees)
이제 key-value 를 key 로 정렬하는 것이다. 이 변경은 append-only 가 적용될 수 없는것 같지만, 후에 알아본다.
이렇게 key 로 정렬 하는 것을 Sorted String Table → SSTable 이라 한다. 각 키가 병합된 segment 에서 딱 한번만 나타나야 하며 compaction 과정이 이를 보장한다.
1.
segment 병합은 파일이 사용가능한 memory 보다 크더라도 간단하고 효율적이다. (mergesort 알고리즘의 방식과 유사하다)
여러 SS테이블 segment를 병합하고 각 키의 최신 값만 유지한다.
각 segment를 읽고 첫 번째 키를 본다(이미 정렬되어있고, 그 순서대로) 그리고 가장 낮은 키를 출력 파일로 복사한뒤 이 과정을 반복한다.
여러 segment 에 동일한 키가 있다면 어떻게 해야 할까? 다중 segment 가 동일한 키를 포함하는 경우 가장 최근 segment 의 값은 유지하고 오래된 segment 의 값은 버린다.
2.
파일에서 특정 키를 찾기 위해 모든 key 를 메모리에 색인으로 올려둘 필요는 없다.
in-memory 색인을 가진 SS테이블
위 예시에서 handiwork 를 보면 handbag 과 handsome 사이에 있음을 알 수 있다.
3.
읽기 요청은 요청 범위 내에서 key-value 를 스캔해야 한다. 따라서 record를 블록으로 그룹화 하고 디스크에 쓰기 전에 압축한다. 그러면 key는 압축된 블록의 시작을 가리키게 된다.
disk 공간을 절약하는 것 외에도 I/O를 줄일 수 있다.
SS테이블 생성과 유지 (Constructing and maintaining SSTables)
그런데 이러한 기능을 구현할 수 있는것은 key 가 정렬되어 있기 때문이다. 쓰기 요청은 유입되는 순서대로 쓰기가 발생한다. 디스크에 정렬된 구조를 유지하는 것은 가능하지만, 메모리에 유지하는 편이 더 쉽다.
하지만 red-black tree나 AVL 트리와 같이 잘 알려진 데이터 구조를 사용하면 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 다시 읽을 수 있다.
•
쓰기가 들어오면 balanced tree 에 추가한다. 이 인메모리는 memtable 이라고도 한다.
•
이 memtable 이 임계값 보다 커지면 SS테이블 파일로 disk 에 기록한다. 이미 정렬되어 있기 때문에 효율적으로 저장할 수 있으며, 이 SS테이블은 DB의 가장 최신 segment 가 된다.
•
읽기 요청이 있으면 memtable 에서 키를 찾고, 그 다음 가장 최신의 segment, 그 다음 segment 를 찾는다.
•
가끔 compaction 작업을 background 에서 수행한다.
DB가 고장나서 디스크로 기록되지 않은 memtable 이 있다면, 이 데이터는 손실 될 수 있으므로 append-only 로그를 디스크 상에 유지해야 한다. 이 로그는 데이터를 복구하는데만 사용하며 정렬되지 않아도 문제가 없다.
SS테이블에서 LSM 트리 만들기 (Making an LSM-tree out of SSTables)
이러한 색인 구조를 Log-Structred Merge-Tree(또는 LSM) 트리라 한다.
정렬된 파일 병합과 compaction 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라 부른다.
루씬은 용어 사전을 저장하기 위해 유사한 방법으로 전문 검색을 구현했다. 질의 단어가 들어오면 단어가 언급된 모든 문서를 찾는데 이 접근법이 용어로 같은 값을 포함한 모든 문서의 id 목록을 제공하고 이 목록은 key-value 로 구현한다. 용어와 용어에 해당하는 문서를 SS테이블 같은 정렬 파일에 유지하고 필요에 따라 background 에서 병합한다.
성능 최적화 (Performance optimizations)
LSM은 존재하지 않는 키를 찾는 경우 느릴 수 있다. 앞서 설명했듯 memtable 을 검색하고, segment, segment 로 검색하면 검색해야 하는 범위가늘어난다.
이런 종류의 접근을 최적화하기 위해 bloom filter 라는 것을 사용한다.(집한 내용을 approximating 한 메모리 효율적 구조이다. key 가 존재하지 않음을 알려주는데 사용하고 불필요한 디스크 읽기를 줄일 수 있다)
또한 compaction, merge 에도 다양한전략이 있다
대표적으로 size-tiered(크기, 사이즈 계층) 와 level compaction 이 있다. LevelDB, LocksDB가 이 이름을 따왔다고 한다.
•
사이즈 계층 컴팩션: 키 범위를 더 작은 SS테이블로 나누고 오래되고 큰 SS테이블에 연이어 병합한다.
•
레벨 컴팩션: 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 "level" 로 이동하기 때문에 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용했다.
기본적인 접근법은 SS테이블을 나누고 순차적으로 병합하는 것이다.
이 접근법은 디스크 쓰기가 순차적이기 때문에 LSM 트리가 매우 높은 쓰기 처리량을 보장할 수 있는 특징을 이용했다.
B-tree
로그 구조는 보편적인 색인 구조가 아니다. 가장 널리 사용되는 색인 구조가 B-Tree 이고 비슷한 점은 딱 key-value 로 유지하는 점 하나 뿐이다.
B-tree 인덱스는 RDB, NoSQL 모두 사용된다.
log 구조는 segment를 나누고 항상 순차적으로 segment 에 기록하는 방식이지만, B-Tree 는 4KB 크기의 고정 블록 이나 페이지로 나누고 한번에 하나의 페이지에 읽기 또는 쓰기를 한다.
디스크가 고정 크기 블록으로 배열되기 때문에 하드웨어와 더 밀접한 관련이 있다.
B 트리 색인을 이용한 key 검색(각 페이지가 다른 페이지를 참조하는 모습을 묘사함)
각 페이지는 위치, 주소를 통해 식별할 수 있고 이 방식 때문에 다른 페이지를 참조할 수도 있다.
한 페이지가 root 로 지정된다. 위 예제에서 보면 root의 200, ref, 300 에서 ref는 200~300 사이에 있는 값들을 가질 수 있다. 그래서 참조를 따라가면 leaf 에 도착하는데 여기서 key 에 해당하는 value를 포함한다.
위 그림에서 ref 의 개수를 분기 계수(branching factor) 라고 부르는데 여기는 6이다. 분기 계수는 페이지 참조와 범위 경계를 저장하는데 보통 수백 개에 달한다.
갱신 key에 해당하는 value를 갱신하고 싶다면 leaf를 찾아내고 페이지의 값을 바꾼 다음 페이지를 디스크에 다시 기록한다.
새로운 key를 추가하는 것은 새로운 키의 범위를 포함하는 page를 찾아 해당 페이지에 키와 값을 추가한다.
해당 페이지에 충분한 공간이 없다면 페이지를 반쯤 채워 페이지 둘로 나누고 상위 페이지가 새로운 키 범위의 하위 부분을 알 수 있게 갱신하는 작업을 한다.
페이지 분리로 커진 B-Tree
이 알고리즘은 Tree 가 계속 균형을 유지하는 것을 보장한다. n개의 키를 가진 B-tree는 깊이가 항상 이다. 대부분 DB에서 깊이는 3~4 단계면 충분하다.
분기 계수 500의 4KB페이지의 4단계 트리는 256TB 까지 저장할 수 있다.
신뢰할 수 있는 B트리 만들기 (Making B-trees reliable)
B-tree의 기본적인 쓰기 동작은 새로운 데이터를 disk 상 페이지에 덮어쓴다.
이 동작은 덮어 쓰기가 페이지 위치를 변경하지 않는다고 가정한다. 페이지를 덮어 쓴다고 해도 페이지를 가리키는 참조는 온전하게 남는다. LSM과 대조적이다.
디스크 페이지를 덮어쓰는 일은 실제 H/W 동작이라 생각할 수 있다. SSD의 경우는 칩의 상당한 블록을 한번에 지우고 다시 쓰기를 해야하기 때문에 조금 더 복잡하다.
DB가 고장 상황에서 스스로 복구하게 하려면 WAL(Write-ahead log. 쓰기전 로그, 재실행 로그 redo)log 를 추가해 B-Tree를 구현한다. B-Tree의 변경 사항을 기록하는 append-only 파일이다.
고장 이후 복구될 때 일관성 있게 B-Tree를 복원하는 데 사용한다.
다중 thread 가 동시에 B-Tree에 접근한다면 주의 깊게 동시성 제어를 해야하는데 이때 latch(가벼운 잠금)로 트리를 보호한다.
로그 기반은 이 상황에서 더 간단하다. 유입 질의에 간섭 없이 background 에서 모든 merge를 수행하고 이따금 원자적으로 새로운 segment로 이전 segment를 대체한다.
B-tree optimizations
오랜 시간에 걸쳐 개발되었기 때문에 많은 최적화 기법이 있다. 몇가지를 언급하면 다음과 같다.
•
페이지 덮어쓰기와 WAL을 유지하는 대신, 쓰기 시 복사 방식을 사용한다(copy-on-write scheme). 변경된 페이지는 다른 위치에 기록하고 트리 상위 페이지의 새로운 버젼을 만들어 새로운 위치를 가리킨다.
◦
동시성 제어에 유용하다.
•
키를 축약해 쓰면 공간을 절약할 수 있다. 페이지 하나에 키를 더 많이 채워 더 높은 분기 계수를 얻는다
◦
leaf 를 찾는 깊이 수준을 낮출 수 있다.
•
페이지는 디스크 상 어디든지 존재할 수 있다. 하지만 leaf 페이지 만큼은 디스크 상 연속된 순서로 나타나게끔 트리를 배치하려 시도한다.(하지만 트리가 커진다면 어렵다)
◦
Log 기반과 비교하면, 병합과 압축 과정에서 segment를 다시 쓰기 때문에 연속된 키를 더 가깝게 유지하기 쉽다.
•
트리에 포인터를 추가해 상위 페이지로 이동하지 않고 형제 페이지로 바로 이동하게 만들 수 있다.
B-tree 와 LSM 트리 비교 (Comparing B-Trees and LSM-Trees)
LSM 트리도 그 성능 특성 때문에 여전히 관심을 받는다. LSM은 쓰기에 빠르고 B-tree 는 읽기에 더 빠르다
읽기가 보통 LSM에서 더 느린 이유는 compaction 단계에 있는 여러 데이터 구조와 SS 테이블을 확인해야 하기 때문이다.
LSM 트리의 장점 (Advantages of LSM-trees)
•
B-Tree
◦
색인은 모든 데이터 조각을 최소한 두번 기록한다.
▪
WAL에 한번, Tree page에 한번(페이지가 분리될 때 다시 기록) 이다.
◦
해당 페이지 내 몇 byte 만 바뀌어도 전체 페이지를 기록해야 하는 오버헤드가 존재하기도 한다.
◦
일부 엔진은 전원 장애가 발생했을 때 일부만 갱신된 페이지로 끝나지 않게 두번 덮어 쓴다.(innoDB)
•
LSM
◦
SS테이블의 반복된 compaction, merge 로 여러번 다시쓴다.
이렇게 한번 쓸때 여러번 쓰는 작업을 쓰기 증폭(write amplification) 이라 하는데 SSD의 경우 블록에 덮어 쓰기 횟수가 정해져 있기 때문에 쓰기 증폭은 특별한 관심사 이다.
만약 application 에 쓰기가 많다면, 쓰기 증폭이 성능에 중요한 영향을 미친다.(저장소 엔진이 기록할수록 디스크 대역폭 내 처리량은 줄어든다)
1.
LSM은 B tree 보다 쓰기 처리량을 높게 유지할 수 있다.
•
compaction과 merge 작업 때문에 B tree 에 비해 쓰기 증폭이 낮다. 특히 HDD 라면 순차 쓰기가 임의 쓰기 보다 훨씬 더 빠르기 때문에 적합하다.
2.
LSM 트리는 압축률이 좋다.
•
B tree 보다 더 적은 파일을 생성한다.
•
B tree 는 파편화로 인해 디스크 공간 일부가 남는다. (일부 공간을 사용하지 않음)
•
SS테이블을 다시 기록하면서 저장소 오버헤드가 낮다.
•
이 장점은 SSD 에서도 유리하다(SSD는 임의 쓰기를 순차 쓰기로 전환할때 LSM 알고리즘을 사용한다)
LSM 트리의 단점 (Downsides of LSM-trees)
LSM 트리의 단점은 compaction 과정으로 인해 읽기와 쓰기의 성능에 영향을 준다.
disk가 가진 자원은 한계가 있다. 그래서 compaction 연산이 끝날 때까지 요청을이 대기해야 하는 상황이 발생하기 쉽다. 물론 처리량과 평균 응답 시간이 성능에 주는 영향은 작지만, 백분위로 비교하면 종종 매우 길어지는 시간이 존재한다.
하지만, B tree 의 성능은 상대적으로 예측하기 쉽다.
쓰기 처리량이 높다 하더라도 설정을 주의 깊게 하지 않으면 compaction 이 유입 속도를 따라가지 못하는 경우가 발생하는데, 유입 속도에 맞춰 compaction 이 줄어드는것이 아니기 때문에 명시적인 모니터링이 필요하다.
또한, 키의 다중 복사본이 여러 segment 에 존재할 수 있다. B tree 는 이것이 한 곳에 모여 있기 때문에 강력한 트랜잭션 semantic 을 제공하는 DB는 B tree 가 더 매력적일 수 밖에 없다.
요즘 나오는 저장소는 LSM 방식을 많이 채택하는데 그럼에도 불구하고 많은 작업 부하에 B tree 는 지속적으로 좋은 성능을 나타내기 때문에 사라질 가능성은 거의 없다.
기타 색인 구조 (Other Indexing Structures)
key-value 색인의 의 대표적인 예시는 PK 색인이다.
색인의 목적은 DB의 다른 row/document/vertex 를 참조로 찾아내기 위함이다.
보조 색인(secondary index)을 사용하기도 한다. 하지만, PK와의 차이점은 중복 유무이다.
색인의 각 값에 일치하는 row 식별자 목록을 만드는 방법과 row 식별자를 추가해서 각 키를 고유하게 만드는 방법이 있다.(대리키)
어느 쪽이든 LSM, B tree 색인 둘 다 사용할 수 있다.
색인 안에 값 저장하기 (Storing values within the index)
지금까지 key 에 대해 알아봤다. value 는 다음 두 가지 중에 하나에 속한다.
값은 질문의 실제 row(document, vertex) 거나 다른 곳에 저장된 row를 가리키는 reference 이다. 다른 곳을 가리키는 reference 가 가리키는 곳을 heap file 이라 하는데 특정 순서 없이 데이터를 저장한다.(tombstone 을 만들 수도 있다)
힙 파일 방식을 선택하는 이유는 여러 보조 색인이 존재할 때 데이터 중복을 피할 수 있다.
특히, key 는 변경하지 않고 value만 변경해야 한다면 heap file 은 좋은 방식이다.
변경 될 데이터의 크기가 기존보다 작거나 같다면 record 를 그 자리에 덮어 쓸 수 있다.
하지만, 크다면 새로운 곳으로 위치를 이동해야 하기 때문에 더 복잡하다. → record 의 새로운 heap 위치를 가리키게끔 갱신하거나 이전 heap 위치에 포인터를 남겨둬야 한다.
색인에서 heap file 로 이동하는 것은 읽기 성능에 불이익이 있기 때문에 색인 안에 바로 row 를 저장하는 편이 바람직 한데 이것을 clustered index 라 한다.
MySQL의 InnoDB의 경우 PK는 언제나 clustered index 이고 보조 색인은 PK를 참조한다.
clustered index 와 non-clustered index 사이의 절충안을 covering index(혹은 포괄열이 있는 색인이라 하여 index with included column) 라고 한다.
이 색인은 index 안에 table의 column 일부를 저장한다. 이렇게 하면 색인만 사용해 query 응답이 가능하다(색인이 질의를 cover 했다고 말함)
covering index 는 읽기 성능을 높일 수 있지만 추가적인 저장소가 필요하고 쓰기 과정에서 오버헤드가 발생한다.
다중 칼럼 색인 (Multi-column indexes)
다중 컬럼에 동시에 질의할 때 결합 색인(concatenated index)을 사용한다. 하나의 컬럼에 다른 컬럼을 추가하는 방식으로 하나의 키에 여러 필드를 결합하는 것이다.
만약 성 + 이름 으로 되어있을 경우 성, 성 + 이름 검색은 의미가 있지만, 이름만 검색하는 데는 의미가 없다.
이러한 다차원 색인은 지리 공간 데이터에 중요하게 사용되는데 경위도에 대해 다음과 같은 질의가 필요하다
select * from restaurants where latitude > 51.4946 and latitude < 51.5079
and longitude > -0.1162 and longitude < -0.1004;
SQL
복사
B tree 나 LSM 는 이러한 색인 유형에 효율적으로 응답할 수 없다.
한가지 방법은 2차원 위치를 공간 채움 곡선(space-filling curve)을 이용해 단일 숫자로 변환하여 B tree 색인을 하는것이고, PostGIS와 같은 지리 공간 색인을 사용하는 것이다.
전문 검색 색인과 퍼지 색인 (Full-text search and fuzzy indexes)
지금까지는 키의 정환한 값이나 정렬된 키의 값의 범위를 질의할 수 있다고 가정한다. 하지만, 철자가 틀린 단어와 같이 유사한 혹은 애매모호한(fuzzy) 질의에는 다른 기술이 필요하다.
예를 들어 전문 검색 엔진은 단어를 검색할 때 단어의 동의어로 질의를 확장한다
루씬은 문서나 질의의 오타에 대처하기 위해 특정 편집 거리(edit distance) 내 단어를 검색할 수 있는 기능이 있다. 앞서 설명 했듯 루씬은 SS테이블 같은 구조를 사용한다.
유한 상태 오토마톤 (finite state automation)
SS테이블은 인메모리 색인이 필요한데 루씬에서 인메모리 색인은 여러 키 내 문자에 대한 유한 상태 오토마톤으로 trie 와 유사한 메모리 색인을 사용한다.
모든 것을 메모리에 보관 (Keeping everything in memory)
지금까지는 디스크 한계에 대한 해결책이었다. 디스크는 메모리보다 사용이 어려운 것이 좋은 성능을 원한다면 주의해서 데이터를 디스크(HDD, SSD)에 배치해야 한다. 이러한 불편함에도 불구하고 디스크를 선택하는 이유는 지속성과 가격 때문이다.
요즘 ram 의 가격이 점점 저렴해지기 때문에 가격 논쟁은 약해졌다. 데이터셋 대부분은 충분히 크지 않기 때문에 메모리에 전체를 보관하는 방식도 꽤 현실적이고, 여러 장비간 분산해서 보관할 수도 있다.
이런 이유로 인메모리 데이터베이스가 개발되었다.
맴캐시드 같은 경우는 데이터 손실을 허용하는 캐시 용도로만 허용되지만, 다른 인메모리 DB는 지속성을 목표로 하여 배터리 전원을 공급 RAM 과 같은 특수 장비를 사용하거나 디스크를 함께 사용하여 주기적인 snapshot을 만드는 방식으로 지속성 문제를 해결한다.
인메모리 DB가 재시작 되는 경우 특수 장비를 사용하지 않는다면 지속성을 위한 append-only 로그와 함께 사용한다. 디스크 상의 파일은 쉽게 백업이 가능하고, 외부 유틸을 사용해 검사와 분석도 가능하다.
직관에 어긋나지만, 인메모리 DB의 성능 장점은 disk 에서 읽지 않아도 되기 때문이 아니다. 심지어 OS가 최근에 사용한 disk block을 메모리에 캐시하기 때문에 충분한 메모리를 가진 경우 disk 기반 저장소도 disk 에서 데이터를 읽지 않기도 한다.
오히려 메모리의 데이터 구조를 디스크에 기록하기 위해 부호화 하는 과정의 오버헤드를 피할 수 있기 때문에 더 빠를 수도 있다.
성능 이외에도 인메모리DB는 disk 기반의 색인이 제공하지 못하는 데이터 모델을 제공한다. 예를들어 queue, set 같은 자료구조를 DB의 interface로 제공하기 때문에 구현이 간단하다.(Redis)
최근 연구에서는 인메모리DB 아키텍쳐가 disk 중심 아키텍쳐에서 발생하는 오버헤드를 제거하고 가용한 메모리 보다 큰 dataset 을 지원하게끔 확장할 수 있다.
anti-caching은 메모리가 충분하지 않을 때 사용하는데 (위의 설명이 anti-caching을 의미하는듯) 최근에 사용하지 않는 데이터를 disk로 내보내고 나중에 다시 접근할 때 메모리에 적재하는 방식으로 동작한다.
가상 메모리와 swap 파일에서 수행하는 방식이 유사하다. 하지만 DB는 (메모리 페이지가 아닌) 개별 record 단위로 작업하기 때문에 OS 보다 더 효율적으로 메모리를 관리할 수 있다.
하지만 이 접근 방식은 여전히 전체 색인이 메모리에 있어야 한다.
트랜잭션 처리나 분석? (Transaction Processing or Analytics?)
초창기 비즈니스 모델은 논리 단위의 형태로 읽기와 쓰기 그룹을 나타내는 commercial transaction 에 해당한다. 이렇게 발생된 record 는 사용자 기반이기 때문에 온라인 트랜잭션 처리(Online Transaction Processing, OLTP) 라고 한다.
그러나, DB를 분석 용도로 점점 더 많이 사용하게 되었다. 지금까지 살펴본 모든 색인은 이러한 분석에 적합하지 않은 색인 방식이다.
이러한 분석용 질의는 의사결정을 돕고, 그 의사결정이 필요한 경영진이 참고하는데 이러한 DB 사용 패턴을 온라인 분석 처리(Online Analytic Processing, OLAP) 라고 한다.
Search
개별 DB에서 분석을 목적으로 수행하는 DB를 Data warehouse 라고 한다.
데이터 웨어하우징 (Data Warehousing)
기업은 수십가지의 트랜잭션 처리 시스템을 갖추고 있으며(고객 대면 웹사이트 강화, 매장 판매 관리, 시스템 관리, 창고 재고 이력, 운송 수단을 위한 경로 등등) 이러한 시스템은 OLTP 이다.
OLTP의 특징은 높은 가용성과 낮은 지연시간의 트랜잭션 처리를 기대하기 때문에 DB 관리자는 OLTP를 철저히 보호하려고 한다.
그래서 비즈니스 분석가의 OLAP 쿼리를 꺼려한다. 왜냐하면 dataset 의 많은 부분을 스캔해야 하는 쿼리와 비즈니스의 트랜잭션을 동시에 실행할 경우 DB에 성능 저하가 발생하기 때문이다.
Data Warehouse 는 이러한 OLAP 쿼리를 OLTP 에게 영향을 주지 않고 언제나 질의할 수 있는 DB 이다.
특징은 읽기 전용 복사본으로 OLTP 에서 추출하고 분석 친화적인 스키마로 변환하고 정제하여 Data warehouse 에 적재한다.
이렇게 Data Warehouse 로 데이터를 가져오는 과정을 ETL(Extract-Transform-Load) 라고 한다.
데이터 웨어하우스에 대한 ETL의 간략한 개요
분석을 위해 OLTP가 아닌 OLAP에 질의하면 분석 패턴에 맞게 최적화된 쿼리를 실행할 수 있다.
그래서 이전까지 다루던 색인 알고리즘은 OLTP 에 적합했고, 이제부터는 OLAP에 적합한 알고리즘을 다뤄본다.
OLTP 데이터베이스와 데이터 웨어하우스의 차이점 (The divergence between OLTP databases and data warehouses)
SQL이 분석 질의에 더 적합하기 때문에 Data warehouse 는 일반적으로 RDB 모델을 사용한다.
SQL 질의를 생성하고 결과를 시각화하고 분석가가 drill-down, slicing, dicing 같은 작업을 통해 데이터를 탐색할 수 있게 해주는 여러 그래픽 데이터 분석 도구가 있다.
여기까지 보면 OLTP와 OLAP 둘 다 SQL 질의 인터페이스를 지원하기 때문에 비슷해 보이지만 각각 매우 다른 질의 패턴에 맞게 최적화됐기 때문에 시스템의 내부는 완전히 다르다.
분석용 스키마: 별 모양 스키마와 눈꽃송이 모양 스키마
(Stars and Snowflakes: Schemas for Analytics)
많은 data warehouse 는 별 모양 스키마(star schema - 차원 모델링 dimensional modeling) 로 알려진 정형화된 방식을 사용한다.
데이터 웨어하우스에서 사용하는 별 모양 스키마 예제
이 그림은 식료품 소매업에서 사용하는 data warehouse 이다. 스키마 중심에 fact table(사실 테이블, 위 그림에서 fact_sales 을 말함)의 각 row는 특정 시각에 발생한 event 에 해당한다.
통상적으로 fact 는 개별 이벤트(페이지 뷰, 사용자 클릭)를 담는데 이는 fact table 이 매우 커질 수 있다는 의미이다. 이러한 fact table 의 column 은 외래 키 참조로 dimension table 의 pk를 가지고 있다.
각 테이블의 row 가 이벤트이면, column은 5w1h 육하원칙을 나타낸다.
이 예제에서는 하나의 상품이 판매되면, 상품의 정보, 날짜 시간 등을 모두 dimension table 을 통해 표현한다. 이러한 차원 테이블은 추가적인 정보를 부호화할 수 있고 휴일과 평일의 판매 차이를 질의할 수 있다.
이 템플릿의 변형을 눈꽃송이 모양 스키마(snowflake schema) 라고 하며 차원이 하위 차원으로 더 세분화 된다. 예를 들면 dim_product 테이블에 문자열로 브랜드와 범주를 저장했지만 FK로 분리하여 더 하위 테이블을 만들어낸다.
snowflake 가 더 정규화 되었지만, 작업은 star schema 가 더 편리하므로 분석가들은 star를 더 선호한다.
일반적인 data warehouse 는 테이블의 폭이 넓다고 표현하는데 column이 수백 개인 경우도 있기 때문이다.
컬럼 지향 저장소 (Column-Oriented Storage)
data warehouse는 페타바이트 데이터가 있고, 그 데이터의 row는 수백개의 column을 가진다면 효율적으로 저장하고 질의하기에는 어려운 문제가 있다.
일반적으로 data warehouse 에서 4, 5개의 컬럼만 접근한다 (* 를 사용하는 일은 거의 없다)
사람들이 요일에 따라 신선 과일을 사고싶어하는지 사탕을 더 사고싶어 하는지 분석하기
fact_sales 에서 3개의 column 에만 접근하는데 date_key, product_sk 둘 중하나에만 색인이 있다고 가정하자. 이 색인은 엔진에 특정 날짜나 특정 제품의 모든 판매 내용을 찾을 수 있는 위치를 알려준다.
하지만 위와 같은 질의를 처리하기 위해서는 disk 에서 100개 이상의 속성을 포함하는 row를 모두 메모리에 적재하고 구문을 분석하여 필요한 조건을 충족하는 row를 filtering 하는 방식으로 대응하는데 이것은 시간이 너무 오래걸린다.
column 지향 저장소의 개념은 모든 값을 하나의 row 에 저장하지 않고 모든 값(column)을 함께 저장한다. 각 column 은 개별 파일에 저장하면 질의에 필요한 칼럼만 읽고 구문 분석할 수 있다.
칼럼 저장소의 예시
칼럼 압축 (Column Compression)
데이터를 압축하면 디스크 처리량을 줄일 수 있는데 컬럼 저장소는 대개 압축에 적합하다.
위의 그림에서 보면 같은 값이 반복되는 것을 볼 수 있는데 이것은 압축을 하기에 매우 좋은 징조이다.
data warehouse 에 효과적인 압축 중 bitmap encoding 이 있다.
압축된 단일 칼럼의 비트맵 저장소
보통 컬럼에서 고유 값의 수는 row 에 비해 적다.(판매되는 제품의 고유한 수가 10만개, 판매 거래는 수십억)
그러면 n개의 고유 값을 가진 column(69,69,69,69,74,31,31...) 을 가져와 n개의 개별 비트맵으로 변환하는데(product_sk 별 비트맵을 따로 가짐) 만약 row가 해당 값을 가지면 비트는 1이고 그렇지 않으면 0 이다.
위와 같은 상황으로 보면 비트맵엔 0이 더 많은데 이것을 run-length 부호화를 통해 한번 더 압축이 가능하다.
•
where product_sk in (30, 68, 69)
◦
product_sk = 30, product_sk = 68, product_sk = 69 에 비트맵 3개를 적재하고 3개 비트맵의 비트를 or 로 계산한다.
•
where product_sk = 31 and store_sk = 3
◦
product_sk = 31, store_sk = 3 으로 bitmap 을 적재하고 and 계산한다.
◦
이 계산은 각 컬럼에 동일한 순서로 row 가 포함되기 때문에 가능하다.
