HaeUlNam
commented
6 months ago - Application 개발자는 performance 관점에서 데이터베이스 내부 로직을 이해해야 한다
Simple database with Bash
- Bash로 간단한 데이터베이스를 만들어볼 수 있다
1) Create bash script file
#!/bin/bash
# File appending with "first argument, second argument" format
db_set() {
echo "$1,$2" >> database
}
# grep : Search first argument on the database file
# s command : Replace first pattern to second. (‘s/regexp/replacement/flags’)
# tail : prints only the last line of the result.
db_get() {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}2) source simple_database.sh
3) Execute db_set or db_get
db_set 123456 '{"name":"London"}'
db_set 42 '{"name":"San Francisco"}'
db_get 42-
일반적으로 파일 추가 작업은 매우 효율적이기 때문에 db_set 함수는 매우 간단한 작업의 경우에는 꽤 좋은 성능을 보여준다. 하지만, 많은 레코드가 있을 경우 성능이 매우 좋지 않다. 검색 비용이 O(n)
#!/bin/bash # comment: data backfill db_set() { echo "$1,$2" >> database } for number in {1..10000}; do db_set "$number" "dummy" done- 1만
./data_backfill.sh 0.34s user 0.53s system 95% cpu 0.913 total db_set 0s db_get 0s- 100만
./data_backfill.sh 31.01s user 46.52s system 94% cpu 1:21.68 total db_set 0s db_get 0.40s- 1000만
./data_backfill.sh 330.20s user 509.48s system 89% cpu 15:42.91 total db_set 0s db_get 3.64s -
레코드 수가 두 배로 늘면 검색도 두 배 오래 걸린다. 바람직하지 않다. 특정 키의 값을 효율적으로 찾기 위해서는 다른 데이터 구조가 필요하다.
-
Index의 트레이드 오프: index를 잘 선택했다면, 읽기 질의 속도가 증가한다. 하지만 모든 색인은 쓰기 속도를 증가시킨다.
Hash indexing
- Key-value 저장소는 대부분 dictionary type과 유사한데, 보통 hash map으로 구현한다.
- 디스크 상의 데이터를 색인하기 위해 메모리 상에 Hashmap 구조로 모든 데이터를 올려둔다. 이와 같은 방식으로 구현한 것이 Bitcask
- Bitcask 인메모리 해시 맵: “Key, byte offset” format
- https://docs.riak.com/riak/kv/2.2.3/setup/planning/backend/bitcask/index.html
- Bitcask 같은 저장소 엔진은 각 키의 값이 많지 않지만, 자주 갱신되는 상황에 적합하다
- 파일에 항상 Append만 한다면, 디스크 공간은 부족해진다.
- 특정 크기의 Segment로 로그를 나누는 방식이 좋은 해결책
- 특정 크기에 도달하면 세그먼트 파일을 닫고, 새로운 세그먼트 파일에 이후 쓰기를 수행. 그동안, 이전 파일은 Compaction을 진행해서 최적화(항상 최신 데이터만 남기도록)
BitCask
- Bitcask 간단한 구조
- KeyDir → Datafiles
- KeyDir는 인메모리 Hash table로서 Datafiles를 lookup하는 용도로 사용된다.
- Operation
- Putting new key-value: one disk write and a few in-memory access and updates. Disk write 작업은 디스크 탐색을 수행할 필요가 없기에 높은 쓰기 처리량을 제공
- Crash 복구: 각 세그먼트 해시 맵을 메모리를 조금 더 빠르게 로딩할 수 있게 스냅숏을 디스크에 저장해 복구 속도를 높인다.
- 동시성 제어: 하나의 쓰기 스레드만 사용하고, 다중 스레드로 동시 읽기를 할 수 있다.
- https://arpitbhayani.me/blogs/bitcask/
Hash table 방식의 제약사항
- 해시 테이블을 메모리에 저장해야 하므로, 키가 너무 많을 경우 문제가 된다. 또한, 해시 충돌 경우도 신경써야 한다.
- 키의 개수는 RAM과 키의 사이즈에 의존적일 듯
- Range query에 효율적이지 않다.
SS테이블과 LSM 트리
- SS Table: Sorted String Table의 약자로 키로 정렬된 형식을 말한다. 각 키는 각 병합된 세그먼트 파일 내에 한번만 나타나야 한다.
- SS Table이 Hash table log segment보다 좋은점
- MergeSort 알고리즘에서 사용하는 방식과 유사하다
- 각 파일의 첫번째 키를 보고 가장 낮은 키를 출력 파일로 복사한 뒤 이 과정을 반복
- 새로운 병합 세그먼트 파일도 키로 정렬되어 있다.
- 다중 세그먼트가 동일한 키를 포함하는 경우 가장 최근 세그먼트 값만 유지
- 파일에서 특정 키를 찾기 위해 더는 메모리에 모든 키의 색인을 유지할 필요가 없다.
- 정렬되어있기에 색인에 존재하는 key들 중 target key과 가까운 key를 골라서 스캔하면 된다.
- Block 단위로 색인을 하기에 Block은 압축을 진행할 수 있어, 디스크 공간을 절약할 수 있다.
- MergeSort 알고리즘에서 사용하는 방식과 유사하다
- SS Table 생성과 유지
- 쓰기가 들어오면 레드 블랙 트리/AVL 트리와 같은 인메모리 balanced tree 데이터 구조에 추가. 이 인메모리 트리는 memtable이라고도 한다.
- memtable이 임계값보다 커지면 SS Table 파일로 디스크에 기록
- 위 과정의 문제점은 아직 디스크로 기록되지 않고 Memtable에 있는 가장 최신 쓰기는 손실된다. 이런 문제를 피하기 위해서 즉시 추가할 수 있는 분리된 로그를 디스크 상에 유지해야 한다. 복원에만 필요한 것이기에 정렬되지 않아도 괜찮
- SS Table 알고리즘은 LevelDB, RocksDB와 같은 라이브러리에서 사용된다.
- Riak에서는 Bitcask 뿐만 아니라 LevelDB 사용 가능
- 카산드라와 HBase에서도 유사한 저장소 엔진을 사용
- 이 색인 구조는 LSM(Log Structured Merge Tree) 트리라는 이름으로 사용되기도 한다.
- 루씬(Lucene) 엘라스틱서치나 솔라에서 사용하는 전문 검색 색인 엔진이다. 루씬은 용어 사전을 저장하기 위해 유사한 방법을 사용한다.
- TODO) What is the Lucene index? https://www.youtube.com/watch?v=T5RmMNDR5XI
- 성능 최적화
- 데이터 베이스에 존재하지 않는 키에 대해서 바로 알려주기 위해 Bloom filter를 추가적으로 사용한다.
- Bloom filter는 집합 내에 특정 원소가 존재하는지를 확인할 때 사용하는 자료구조. 존재하는 데이터에 대해서는 여러 Hash function을 이용해서 결과 Array에 1로 표시하게 된다. Input에 대해 모든 hash function의 결과가 1인 경우, 존재하는 키로 인지
- False positive 가능성이 존재하는데, 확률을 아래 사이트에서 구할수도 있다.
- Redis에서 bloom filter 기능을 제공하고 있어서 필요하다면 사용해볼 수도 있을 듯.
- 데이터 베이스에 존재하지 않는 키에 대해서 바로 알려주기 위해 Bloom filter를 추가적으로 사용한다.
- https://gngsn.tistory.com/201
- Bloom filter는 ip 필터링, 블랙리스트 등에 쓰일 수 있을 것 같다.B 트리
- LSM는 수 메가바이트 이상의 세그먼트 단위로 나누고 순차적으로 세그먼트를 기록하는 반면, B 트리는 4KB의 페이지로 나누고 한번에 하나의 페이지에 읽기 또는 쓰기를 한다.
- B 트리의 Root로부터 범위를 탐색해서 리프 페이지까지 찾아나간다.
- B 트리의 한 페이지에서 하위 페이지를 참조하는 수를 Branching factor라고 한다.
- B 트리는 균형을 유지하는 것을 보장하기에 깊이는 항상 Log(n)이다.
- B 트리 insert/delete를 visualize - https://www.cs.usfca.edu/~galles/visualization/BTree.html
- B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓴다
- 데이터베이스가 고장 상황에서 스스로 복구할 수 있게 만드려면 WAL(Write-ahead log)라는 데이터 구조를 추가해 B 트리를 구현한다 (re-do log라고도 함)
Question
- Q. index 추가에 따라 쓰기 속도에는 얼마나 영향을 미치게 될까?
Reference
- [https://losskatsu.github.io/os-kernel/bash/#리눅스-bash의-모든-것-binbash의-의미](https://losskatsu.github.io/os-kernel/bash/#%EB%A6%AC%EB%88%85%EC%8A%A4-bash%EC%9D%98-%EB%AA%A8%EB%93%A0-%EA%B2%83-binbash%EC%9D%98-%EC%9D%98%EB%AF%B8)
- https://blog.gaerae.com/2015/01/bash-hello-world.html
- https://wiki.kldp.org/HOWTO/html/Adv-Bash-Scr-HOWTO/
- https://www.gnu.org/software/sed/manual/html_node/The-_0022s_0022-Command.html`
2rohyun
minkukjo
LOG-INFO
참고
정리
- `DB가 데이터를 저장하는 방법`과 `데이터를 다시 찾을 수 있는 방법` ## 데이터 구조 - 많은 데이터베이스는 내부적으로 추가 전용(Append-only) 데이터 파일 로그(Log)를 사용함 - MySQL에선 대략 5가지 정도의 로그 파일을 운용 - 에러 로그 - 제너럴 로그 - 슬로우 쿼리 로그 - 바이너리 로그 - 릴레이 로그 - 실제 로그 파일을 확인할 수도 있음 - 데이터를 빠르게 찾기 위해 색인(Index)를 사용함 - 색인은 기본 데이터에 파생되는 추가적인 구조 - 데이터 크기에 더불어 색인에 사용할 추가적인 공간이 요구됨 ### 세그먼트(Segment) - 로그 방식으로 데이터를 계속 추가함 - 그러면 데이터를 항상 추가만 하게되면 공간이 부족해질 텐데 어떻게 할 수 있을까? - ⇒ 세그먼트 별로 파일을 나눔 - 세그먼트 크기에 도달한 파일은 새로운 세그먼트 파일을 열고 기존 데이터를 close함 - close한 세그먼트는 컴팩션(중복된 키를 제거) 작업을 수행 - 또한, 여러 개의 세그먼트를 하나로 병합하는 과정도 수행 - **세그먼트가 쓰여진 후에는 절대 변경할 수 없음** - 따라서, 병합할 세그먼트는 새로운 파일로 만듦 - 기존 세그먼트의 데이터를 복사하는 방식 - 덕분에 세그먼트 병합되는 과정에서 기존 세그먼트로 데이터를 볼 수 있음 - 세그먼트 병합 완료 후에는 기존 세그먼트를 삭제함 ### 해시 색인(Hash Index) - 해시 맵을 사용하여 인덱스를 관리 - 예시) `키` - `데이터의 바이트 오프셋`을 매핑해서 해시 맵을 유지하는 전략 - 장점 - 키의 값이 자주 갱신되는 상황에 적합함 - 키당 쓰기 수가 많지만 메모리에 모든 키를 보관할 수 있음 - 키를 파일 오프셋에 매핑한 세그먼트 자체 해시 테이블을 갖게됨 - 실제 구현에서 중요한 문제 - **파일 형식** *(CSV는 로그에 적합한 방식이 아님)* - 바이트 단위의 문자열 길이를 인코딩한 다음 원시 문자열을 인코딩한 바이너리 형식을 사용하는 편이 빠르고 간단함 (이스케이핑을 사용하지 않아도됨) - **레코드 삭제** - 키와 관련된 값을 삭제하려면 데이터 파일에 특수한 삭제 레코드(tombstone)을 추가해야함 - 로그 세그먼트가 병합될 때 삭제된 키의 이전 값을 무시하게 해야함 - **고장(Crash) 복구** - 데이터베이스가 재시작되면 인메모리 해시 맵이 손실됨 - 모든 세그먼트를 처음부터 끝까지 읽어서 다시 만들 수 있지만 오래걸릴 수 있음 - 해시맵 스냅샷을 디스크에 저장해서 복구 속도를 높일 수 있음 (비트캐스트에서 쓰는 방식) - 부분적으로 레코드 쓰기 - 로그에 레코드를 추가하는 도중에 죽을 수 있음 - 비트캐스크 파일은 체크섬을 포함하고 있어서 로그의 손상된 부분을 탐지해 무시할 수 있음 - 동시성 제어 - 쓰기를 엄격하게 순차적으로 추가할 때 일반적인 구현 방법은 하나의 스레드만 쓰는 것 - 세그먼트를 쓰게되면 추가 전용이거나 불변이므로 다중 스레드로 동시에 읽기를 할 수 있다. ### 추가 전용 로그가 **파일 갱신보다 좋은 이유** > **파일 갱신 : 지정된 자리의 값을 덮어쓰는 방식** > - 추가와 세그먼트 병합은 순차적인 쓰기 작업이기 때문에 무작위 쓰기보다 훨씬 빠름 - 특히 HDD에서는 헤드를 조정하는 비용이 절약되어 빠름 - 크래시 파일 복구에 훨씬 간단함 - 값을 덮어 쓰는 동안 DB가 죽는 경우를 걱정할 필요가 없음 - 이전 값과 새로운 값 모두 저장하기 때문 - 오래된 세그먼트 병합은 시간이 지남에 따라 파편화되는 문제를 피할 수 있음 ### 해시 테이블의 한계 - 메모리에 저장해야하므로 키가 너무 많으면 문제가 됨 - 디스크에 유지할 수 있지만 성능 이득이 크지 않음 - 디스크가 가득 찼을 때, 해시 충돌의 경우 등을 고려해서 추가적인 로직이 필요함 - 해시 테이블은 범위 질의에 효율적이지 않음 - 범위가 주어지면 개별 키를 모두 조회해야함 ## SS테이블과 LSM 트리 - 세그먼트 파일(키-값 쌍)을 키로 정렬한다면? ⇒ **SS테이블(Sorted String Table)** - 각 키는 병합된 세그먼트 파일 내에 한 번만 나타나야함 (컴팩션 불필요) **로그 세그먼트보다 SS 테이블이 갖는 장점** - 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적 - Merge Sort 알고리즘과 유사함 1. 각 파일 별 첫번째 키를 봄(정렬된 순서) 2. 가장 낮은 키를 뽑아서 새로운 세그먼트 파일에 씀 3. 세그먼트에 쓰인 키는 다음 키를 읽음 4. 2~3 반복 - 결과적으로 새로운 세그먼트 파일은 키 순서가 보장됨 - 여러 세그먼트에서 동일한 키가 존재한다면? - 가장 최근 세그먼트의 값을 유지하고 오래된 세그먼트의 값을 제거 - **Why?) 세그먼트는 일정 기간 동안 DB에 쓰여진 모든 값을 저장하므로 최신 세그먼트가 최신 값이라는 것이 보장됨** - 파일에서 특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없음 - 메모리에 몇 개의 인덱스(Sparse Index)만 올려두고 모든 키가 어디에 있을지 유추할 수 있음 - 예시) `handbag` 과 `handsome` 인덱스가 이미 메모리상에 존재할 때, `handiwork`을 찾으려면? - `handbag` 과 `handsome` 사이에 있다는 걸 유추하여 `handbag` 키의 오프셋을 조정하여 스캔 가능  - 읽기 요청은 요청 범위 내에서 여러 키-값 쌍을 스캔해야 하기 때문에 해당 레코드들을 블록으로 그룹화하고 디스크에 쓰기 전에 압축함 - 인메모리 색인의 각 항목은 압축된 블록의 시작을 가리키게 됨 ### SS테이블 생성과 유지 - 쓰기 작업은 임의 순서로 발생하게 됨 - 정렬된 구조를 유지하는 일은 디스크보다 메모리에 유지하는 편이 쉬움 - AVL 트리, Red-black 트리 등을 쓰면 임의 순서로 키를 삽입하고 정렬된 순서로 키를 다시 읽을 수 있음 - 쓰기가 들어오면 AVL 트리, Red-Black 트리에 추가함. **⇒ 멤테이블(memtable)** - 멤테이블이 임계값(Threshold) 보다 커지면 SS테이블 파일로 디스크에 기록함 (가장 최신 세그먼트 트리) - 디스크에 저장하는 동안은 새로운 멤테이블 인스턴스를 만들어 사용함 - 읽기 요청을 제공하려면 1) 먼저 멤테이블을 찾고, 2) 없으면 디스크 상 세그먼트를 최신에서 오래된 순으로 읽어서 찾음 - 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 Merge + Compaction 과정을 수행함 (백그라운드) - 문제) 갑자기 DB가 고장나면, 디스크에 기록되지 않고 멤테이블에 저장되어있던 내용들은 손실됨 - 해결) 분리된 쓰기용 로그를 디스크상에 유지시킴 **⇒ 멤테이블 복원 시에만 사용하기 위해** - 순서가 정렬되지 않아도 상관 없음 - 멤테이블을 세그먼트(SS테이블)로 저장한 이후 로그를 파기할 수 있음 ### SS테이블에서 LSM 트리 만들기 - LSM 트리 : Log-Structed Merge-Tree - LSM 트리는 많은 DB들이 사용하고 있는 알고리즘 및 자료구조 - LevelDB : 구글의 유일한 시니어 펠로우 2명(제프 딘과 산자이 게마왓)이 개발한 온디스크 키-값 스토어 - RocksDB, 카산드라, HBase 등등.. - 엘라스틱서치에서 사용하는 Lucene도 용어 사전을 저장하기 위해 비슷한 방법을 씀 - SS 테이블 같은 정렬파일에 유지하고 백그라운드에서 병합함 ### 성능 최적화 - LSM 트리 알고리즘은 DB에 존재하지 않는 키를 찾는 경우 느릴 수 있음 - 저장소 엔진은 보통 **블룸 필터(Bloom filter)** 를 추가적으로 써서 존재하지 않는 키 접근을 최적화함 - 필터가 DB에 존재하지 않음을 알려줌 **⇒ 디스크 Read 비용 절약** > 블룸 필터 위키 : [[https://ko.wikipedia.org/wiki/블룸_필터](https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0)](https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0) > > - m비트에 대해 k개의 해시 함수를 돌려서 결과로 나온 비트를 1로 변경하는 방법 > - 특징 > - 요청값이 필터상으로 존재하는 케이스지만 실제로는 없는 경우 **(False-Positive)가 있음** > - 없는데 있다고하는 경우 **(False-Negative)는 존재하지 않음** - SS 테이블을 압축하고 병합하는 순서, 시기를 결정하는 전략들이 다양함 - 일반적으로 사용하는 전략 : 크기 계층(Size-tiered)과 레벨 컴팩션(Leveled Compaction) - 크기 계층 컴팩션 - 상대적으로 좀 더 새롭고 작은 SS테이블을 상대적으로 오래되고 큰 SS테이블에 연이어 병합함 - 레벨 컴팩션 - LevelDB 및 RocksDB에서 사용함 - LevelDB 구현 문서 : https://github.com/google/leveldb/blob/main/doc/impl.md) - 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 레벨로 이동하기 때문에 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용함 ## B-Tree - 가장 널리 사용되는 색인 구조 - 로그 구조화 색인과는 상당히 다름 - 고정 크기 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 함 - 디스크가 고정 크기 블록으로 배열되기 때문에 근본적으로 하드웨어에 적합 - 각 페이지는 주소나 위치를 이용해서 식별이 가능함 - 덕분에 페이지가 다른 페이지를 참조할 수 있음(메모리 대신 디스크에 있음) - 키를 찾으려면 Root 페이지를 통해 하위 페이지를 타고타고 들어가서 Leaf 페이지까지 도달하여 데이터를 찾을 수 있음 - 한 페이지가 다른 페이지를 참조하는 수를 **분기 계수(Branching factor)** 라고 부름 - 한 페이지가 6개 페이지를 참조하면 분기계수 6 (보통 수 백개) - B 트리에 존재하는 키 값을 갱신하려면 키를 포함하고 있는 모든 페이지를 검색하고 페이지 값을 바꾼 다음 페이지를 디스크에 다시 기록함 - 새로운 키를 추가하려면 새로운 키를 포함하는 페이지를 찾아서 키와값을 추가함 - 페이지 크기가 꽉 찼다면 페이지를 둘로 나누어 여유공간을 만들어냄 - B 트리가 계속 균형을 유지하는 것을 보장함 ### 신뢰할 수 있는 B 트리 - B 트리의 쓰기 동작은 새로운 데이터를 디스크 상 페이지에 덮어씀 - 덮어써도 페이지 위치가 변경되지 않으므로 참조가 올바름 - DB가 고장 상황에서 스스로 복구할 수 있게 하려면? - 보통 쓰기 전 로그(Write-ahead log, WAL, redo log)를 추가함 - B 트리 변경사항을 기록하는 추가 전용 파일 - DB 복구 시 WAL를 보고 B 트리를 복구함 - 다중 스레드가 같은 페이지를 수정하면? - Latch로 가벼운 잠금을 사용해 트리의 데이터 구조를 보호함 - 이 부분은 LSM 트리가 더 간단함 - 새로운 세그먼트로 바꿔버리면 되기 때문 ### B 트리 최적화 - 오랫동안 사용되었기 때문에 수많은 최적화 기법들이 존재함 - 페이지 덮어쓰기, WAL 유지 대신 쓰기 시 복사 방식(Copy-on-write scheme) 사용 - 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어서 새로운 위치를 가리키게 하는 방식 - 페이지에 전체 키를 저장하지 않고 키를 축약해서 공간 절약 - 키가 키 범위 사이의 경계 역할을 하기만 하면 되므로 이를 최적화하는 방식 - 장점) 같은 페이지 크기에 더 많은 분기 계수를 사용할 수 있으므로 깊이를 절약 - 페이지를 디스크 상에 무작위로 배치 가능 - 키 범위가 가깝다고 디스크 상에서 인접할 필요는 없음 - 트리에 포인터를 추가 - 리프 페이지가 양쪽 형제 페이지에 대한 참조를 가지면 상위 페이지에서 다시 질의할 필요가 없음 - B+ 트리 : 리프 노드가 양쪽 형제 페이지에 대해 포인터를 가짐 - 프랙탈 트리 - 디스크 찾기를 줄이기 위해 로그 구조화 개념을 일부 빌림 ## B 트리와 LSM 트리 비교 **LSM 트리** - 장점 - 쓰기에 더 빠름 - 읽기는 각 컴팩션 단계이 있는 데이터 구조와 SS 테이블을 확인해야하기 때문 - 쓰기 처리량이 B트리에 비해 높음 - 쓰기 증폭이 낮고, 순차적으로 페이지를 컴팩션하기 때문 - 압축률이 더 좋음 - B 트리보다 디스크에 더 적은 파일을 생성함 - 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하므로 저장소 오버헤드가 더 낮음 - 단점 - SS테이블의 반복된 컴팩션과 병합으로 데이터를 여러번 다시 씀 - 컴팩션 과정이 읽기 쓰기 성능에 영향 - 컴팩션 과정이 비싸기 때문에 이 과정에 들어오는 요청들은 하드웨어에서 처리되지 못해서 느려질 수 있음 - 대부분 빠르지만 극소수 응답들에는 성능을 미칠 수 있음 - 또한, 컴팩션으로 인해 쓰기 과정(로깅 및 멤테이블 디스크 flushing)이 느려질 수 있음 - 보통 유입 쓰기 속도를 조절하지 않으므로 상황을 감지하기 위해 명시적 모니터링이 필요함 - 같은 키가 여러 세그먼트에 존재할 수 있음 **B 트리** - 장점 - 읽기에 더 빠름 - 각 키가 색인의 한 곳에만 정확하게 존재함 - 단점 - 모든 데이터 조각을 최소 2번 기록해야함 (WAL, 트리 페이지) - 쓰기 한번이 디스크에 여러번의 쓰기를 야기하는 효과 **⇒ 쓰기 증폭(Write amplification)** - SSD는 블록 덮어쓰기 횟수가 제한되기 때문에 주의해야함 - 쓰기 증폭으로 인해 디스크에 기록할 수 있는 대역폭이 줄어들 수 있음 - 페이지 내 작은 수정사항도 전체 페이지를 한 번에 기록해야함 ## 기타 색인 구조 - 지금까지 본 키-값 쌍 색인은 Primary Key 인덱스 - 이 외에 보조 색인도 존재할 수 있음 - 키가 고유하지 않다는 특징이 있음 - 보조 색인을 만드는 방법 2가지 - 색인의 각 값에 일치하는 Row 식별자 목록을 만드는 방법 - Row 식별자를 추가해 각 키를 고유하게 만드는 방법 ### 색인 안에 값 저장하기 - 키는 질의가 검색하는 대상 - 값은? - 질문의 실제 Row(문서, 정점) - 다른 곳에 저장된 Row를 가리키는 참조 - Row가 저장된 곳을 힙 파일(Heap file)이라고 하고 특정 순서 없이 데이터를 저장함 - 추가 전용인 파일, 나중에 새로운 데이터로 덮어 쓰기 위해 삭제된 로우를 기록 - 힙파일을 사용하면 키를 변경하지 않고 값을 갱신할 때 효율적 - 하지만, 색인에서 힙 파일로 다시 이동하는 일은 읽기 성능이 안좋음 - ⇒ 색인 안에 바로 색인된 로우를 저장하는 편이 좋음 **(Clustered Index)** - MySQL의 InnoDB 엔진은 테이블의 기본키가 Clustered Index고, 보조 색인은 PK를 참조함 - 클러스터드 인덱스와 비클러스터드 인덱스 사이의 절충안 - Covering Index - Index with included column - 클러스터드 인덱스는 읽기 성능을 높일 수 있지만, 추가적인 저장소가 필요함 - 게다가, 쓰기 과정에 오버헤드도 발생함 - 복제로 인한 불일치를 파악할 수 없기 때문에 트랜잭션 보장을 강화하기 위해 데이터베이스에 추가적인 로직이 필요함 ### 다중 컬럼 색인 - 결합 색인(Concatenated Index) - 하나의 컬럼에 다른 컬럼을 추가하는 방식 - 다차원 색인은 구현하는 방법이 여러가지 있음 - 다차원 위치를 공간 채움 곡선(space-filling curve)을 사용해 단일 숫자로 변환하여 일반 B트리 색인을 쓰는 방법 - R트리 처럼 전문 공간 색인(Specialized spatial index)을 쓰는 방법 ### 전문 검색과 퍼지 색인 - 지금까지의 인덱스들은 철자가 틀린 단어 같은 유사한 키에 대해서는 검색할 수 없음 - 전문 검색은 특정 단어를 검색할 때 해당 단어의 동의어로 질의를 확장함 - 루씬은 특정 단어 몇개가 추가되거나 빠지는 것에 대해서 효율적인 단어 검색이 가능 - 유한 상태 오토마톤(Trie와 비슷함) ### 모든 것을 메모리에 보관 - RAM이 점점 저렴해져서 인메모리 DB가 개발됨 - 여러 장비 간에 메모리를 분산해서 보관할 수도 있음 - 보통 메모리상에만 존재하므로 재시작 시 메모리에 있는 데이터에 대한 지속성은 보장하지 않음 - 하지만, 몇몇 인메모리 DB는 비동기로 디스크에 기록하는 작업을 넣어서 약한 지속성을 제공함 - **인메모리 DB를 사용하는 것이 읽기 성능 때문만은 아님** - 요즘은 디스크에서 읽어온 블록을 메모리에 캐시해두기 때문에 디스크 기반 저장소 엔진도 빠를 수 있음 - 성능 외에도 디스크 기반 색인으로 구현하기 어려운 데이터 모델을 제공하기 때문에 사용함 - e.g.) Redis의 우선순위 큐와 셋(set) 같은 다양한 데이터 구조를 DB같은 인터페이스로 제공함 ## 트랜잭션 처리나 분석? - 보통 앱은 인덱스를 사용해 일부 키에 대한 레코드를 찾게됨. - 찾은 레코드에 사용자 입력을 기반으로 삽입되거나 갱신됨 - 이런 패턴은 대화식이기 때문에 **온라인 트랜잭션 처리(Online transaction processing, OLTP)** 라고 함 - 하지만, DB를 데이터 분석에도 점점 더 많이 사용하기 시작함 - 분석을 위한 질의는 집계, 통계를 계산해야함 - 이런 패턴은 분석을 위함 처리이기 때문에 온라인 분석 처리(Online analytic processing, OLAP)라고 함 ### 분석을 위한 데이터 웨어하우스 - 분석용 질의는 대부분 비용이 비싼 쿼리이기 때문에 OLTP DB에서 하기를 권장하지 않음 - 데이터 웨어하우스는 분석가들이 분석용 쿼리를 할 수 있는 **OLTP와 별개의 데이터베이스** - 데이터는 OLTP 데이터베이스에서 주기적으로 추출하고 분석 친화적인 스키마로 변환하여 적재함 (Extract-Transform-Load, ETL) ### OLTP 데이터베이스와 데이터 웨어하우스의 차이점 - 데이터 웨어하우스의 데이터 모델은 일반적으로 관계형 모델을 사용함. (SQL 사용가능) - 분석용 스키마 - 별 모양 스키마(Star schema) (차원 모델링) - 눈꽃송이 모양 스키마(Snowflake schema) ## 칼럼 지향 저장소 - 테이블 칼럼은 보통 100개 이상이지만, 실제 분석용 질의는 4, 5개 컬럼만 씀 - 하지만, 대부분의 OLTP 데이터베이스는 Row 지향 방식으로 데이터를 배치함 - 한 Row의 모든 값은 서로 인접하게 저장함 - 컬럼 지향 저장소는 각 컬럼 파일에 포함된 로우가 모두 같은 순서임 ### 컬럼 압축 - 컬럼 별로 보면 많은 값이 반복해서 나타남 ⇒ 압축을 하기 좋음 - 비트맵 부호화(bitmap encoding) - 각 값에 대해 비트맵으로 만들어서 저장함 - 데이터 웨어하우스에서 일반적으로 사용되는 질의 종류에 매우 적합함 - 비트맵을 OR하거나 AND해서 해당하는 레코드를 추려내기 쉬움 ### 메모리 대역폭과 벡터화 처리 - 수백만 로우를 메모리로 가져오는 대역폭이 가장 큰 병목임 - 컬럼 저장소 배치는 CPU 주기를 효율적으로 사용하기 적합함 - 압축된 컬럼 데이터를 CPU 캐시에 맞게 가져오고 함수호출이 없는 루프에서 반복할 수 있음 - 이를 벡터화 처리(Vectorized processing)라고함 ### 컬럼 저장소의 순서 정렬 - 로우가 저장되는 순서는 반드시 중요하지 않음 ⇒ 삽입된 순서로 저장하는 방식이 가장 쉬움 - 각 컬럼을 독립적으로 정렬할 수 없음. 한번에 전체 로우를 정렬해야함 - 정렬된 순서는 컬럼 압축에 도움이 됨 ### 컬럼 지향 저장소에 쓰기 - 압축, 정렬은 모두 읽기 질의를 더 빠르게 하지만 쓰기를 어렵게함 - B 트리 사용과 같은 제자리 갱신(update-in-place) 접근 방식은 압축된 컬럼에서 불가능함 - 테이블 중간에 로우를 삽입하려면 모든 컬럼 파일을 재작성해야함 - 모든 쓰기는 먼저 인메모리 저장소로 이동해 정렬된 구조에 추가하고 디스크에 씀 - 충분한 쓰기를 모으면 디스크의 컬럼 파일에 병합하고 대량으로 새로운 파일에 기록함