> For the complete documentation index, see [llms.txt](https://chloe-codes1.gitbook.io/book-reviews/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chloe-codes1.gitbook.io/book-reviews/designing-data-intensive-applications/03_-_.md). # Chapter 3: 저장소와 검색
## Intro * 데이터베이스가 저장과 검색을 내부적으로 처리하는 방법을 애플리케이션 개발자가 주의해야 하는 이유 * 대개 애플리케이션 개발자가 처음부터 자신의 저장소 엔진을 구현하기보다는, 사용 가능한 여러 저장소 엔진 중에 `애플리케이션에 적합한 엔진`을 선택하는 작업이 필요하다 * 특정 작업 부하(workload) 유형에서 좋은 성능을 내게끔 저장소 엔진을 조정하려면, `저장소 엔진 내부 에서 수행되는 작업`에 대해 대략적인 개념을 이해할 필요가 있다 ## 데이터베이스를 강력하게 만드는 데이터 구조 ### 색인 * 색인의 일반적인 개념은 어떤 부가적인 `메타데이터`를 유지하는 것이다 * 이 메타데이터는 `이정표` 역할을 해서 원하는 데이터의 위치를 찾는 데 도움을 준다 * 동일한 데이터를 여러 가지 다양한 방법으로 검색하고자 한다면 데이터의 각 부분에 여러 가지 다양한 색인이 필요하다 * 색인은 기본 데이터(primary data)에서 파생된 추가적인 구조다 * 많은 데이터베이스는 색인의 추가와 삭제를 허용한다 * 이 작업은 데이터베이스의 내용에는 영향을 미치지 않는다 * 단지 `질의 성능`에만 영향을 준다 * 추가적인 구조의 유지보수는 특히 `쓰기 과정`에서 `오버헤드`가 발생한다 * 쓰기의 경우 단순히 파일에 추가할 때의 성능을 앞서기 어렵다 * 왜냐하면 단순히 파일에 추가하는 작업이 제일 간단한 쓰기 작업이기 때문이다 * 어떤 종류의 색인이라도 대개 `쓰기 속도를 느리게` 만든다 * 데이터를 쓸 때마다 매번 `색인도 갱신`해야 하기 때문! * 이것은 저장소 시스템에서 중요한 `트레이드오프`다 * 색인을 잘 선택했다면 읽기 질의 속도가 향상된다 * but, 모든 색인은 쓰기 속도를 떨어뜨린다 * 이런 이유로 데이터베이스는 보통 자동으로 모든 것을 색인하지 않는다 * 애플리케이션 개발자나 데이터베이스 관리자가 애플리케이션의 전형적인 질의 패턴에 대한 지식을 활용해 수동으로 `색인을 선택`해야 한다 * 그래야 필요 이상으로 `오버헤드`를 발생시키지 않으면서 애플리케이션에 가장 `큰 이익을 안겨주는 색인`을 `선택`할 수 있다 ### 해시 색인 * 키를 데이터 파일의 `바이트 오프셋`에 매핑해 `인메모리 해시 맵`을 유지하는 전략 * 파일에 새로운 키-값 쌍을 추가할 때마다 방금 기록한 데이터의 오프셋을 반영하기 위해 해시 맵도 갱신해야 한다 * 값을 조회 하려면 해시 맵을 사용해 데이터 파일에서 `오프셋`을 찾아 해당 위치를 구하고 값을 읽는다 * `비트캐스크 (Bitcask)` * 비트캐스크는 해시 맵을 전부 `메모리에 유지`하기 때문에 사용 가능한 램(RAM)에 모든 키가 저장된다는 조건을 전제로 고성능으로 읽기, 쓰기를 보장한다 * 값은 한 번의 `디스크 탐색`으로 디스크에서 적재할 수 있기 때문에 사용 가능한 메모리보다 더 많은 공간을 사용할 수 있다 * 만약 데이터 파일의 일부가 이미 `파일 시스템 캐시`에 있다면 읽기에 디스크 입출력이 필요하지 않다 * 비트캐스크 같은 저장소 엔진은 각 `키의 값이 자주 갱신되는 상황`에 매우 적합하다 * `세그먼트 (segment)` * 파일에 항상 추가만 한다면 결국 디스크 공간이 부족해지므로, 특정 크기의 `세그먼트(segment)로 로그를 나누는 방식`으로 해결할 수 있다 * 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행한다 * 세그먼트 파일들에 대해 `컴팩션(compaction)`을 수행할 수 있다 * 컴팩션은 로그에서 `중복된 키`를 버리고 각 키의 `최신 갱신 값만 유지`하는 것을 의미한다 * 컴팩션은 보통 세그먼트를 더 `작게 만들기` 때문에 (하나의 키는 세그먼트 내에서 대체로 여러번 덮어쓰기 된 것을 가정함) 컴팩션을 수행할 때 동시에 여러 `세그먼트`들을 `병합`할 수 있다 * 세그먼트가 `쓰여진 후에는 절대 변경할 수 없기 때문에` 병합할 세그먼트 는 새로운 파일로 만든다 * 고정된 세그먼트의 병합과 컴팩션은 `백그라운드 스레드`에서 수행할 수 있다 * 컴팩션을 수행하는 동안 `이전 세그먼트 파일`을 사용해 읽기와 쓰기 요청의 처리를 정상적으로 계속 수행할수 있다 * 병합 과정이 끝난 이후에는, 읽기 요청은 이전 세그먼트 대신 새로 병합한 세그먼트를 사용하게끔 전환한다 * 전환 후에는 이전 세그먼트 파일을 삭제하면 된다 * 각 세그먼트는 키를 파일 오프셋에 매핑한 `자체 인메모리 해시 테이블` 을 갖는다 * 키의 값을 찾으려면 `최신 세그먼트 해시 맵`을 먼저 확인한다 * 만약 키가 없다면 두 번째 최신 세그먼트를 확인한다 * `병합 과정`을 통해 세그먼트 수를 적게 유지하기 때문에 조회할 때 많은 해시 맵을 확인할 필요가 없다 * `고려해야 할 사항` * 파일 형식 * csv는 로그에 가장 적합한 형식이 아니다 * `바이트 단위`의 문자열 길이를 `부호화`한 다음, `원시 문자열`(이스케이핑할 필요 없이)을 부호화하는 바이너리 형식을 사용하는 편이 더 빠르고 간단하다 * 레코드 삭제 * 키와 관련된 값을 삭제하려면 데이터 파일에 `특수한 삭제 레코드`(tombstone이라 불림) 를 추가해야 한다 * 로그 세그먼트가 병합될 때 톰스톤은 병합 과정에서 `삭제된 키의 이전 값`을 `무시`하게 된다 * Crash 복구 * 데이터베이스가 `재시작` 되면 인메모리 해시 맵은 `손실`된다 * 원칙적으로는 전체 세그먼트 파일을 처음부터 끝까지 읽고, 각 키에 대한 `최신 값의 오프셋`을 확인해서 각 세그먼트 해시 맵을 `복원`할 수 있다 * but, 세그먼트 파일이 크면 해시맵 복원은 오랜 시간이 걸릴 수 있고, 이는 서버 재시작을 어렵게 만든다 * 비트캐스크는 각 세그먼트 해시 맵을 메모리로 조금 더 빠르게 로딩할 수 있게 `snapshot을 디스크에 저장`해 `복구 속도`를 높인다 * 부분적으로 레코드 쓰기 * 데이터베이스는 로그에 레코드를 추가하는 도중에도 죽을 수 있다 * 비프캐스크 파일은 `checksum`을 포함하고 있어 로그의 손상된 부분을 탐지해 무시할 수 있다 * 동시성 제어 * 쓰기를 엄격하게 순차적으로 로그에 추가할 때, 일반적인 구현 방법은 `하나의 쓰기 thread만 사용` 하는 것이다 * 데이터 파일 세그먼트는 `추가 전용`이거나 `불변`이므로, `multi-thread`로 동시에 읽기를 할 수 있다 * `추가 전용 설계의 장점` 1. 추가와 세그먼트 병합은 `순차적인 쓰기 작업` 이기 때문에 보통 무작위 쓰기보다 훨씬 `빠르다` 2. 세그먼트 파일이 `추가 전용`이나 `불변`이면 `동시성`과 `고장 복구`는 훨씬 간단하다 * 값을 덮어 쓰는 동안 데이터베이스가 죽는 경우에 대해 걱정할 필요가 없다 * 이전 값 부분과 새로운 값 부분을 포함한 파일을 나누어 함께 남겨두기 때문! 3. 오래된 세그먼트 병합은 시간이 지남에 따라 `조각화` 되는 데이터 파일 문제를 피할 수 있다 * `해시 테이블 색인의 제한 사항` 1. 해시 테이블은 `메모리`에 저장해야 하므로 `키가 너무 많으면 문제`가 된다 * 원칙적으로는 디스크에 해시 맵을 유지할 수 있지만, 디스크 상의 해시 맵에 좋은 성능을 기대하기는 어렵다 * 무작위 접근 I/O가 많이 필요하고, 디스크가 가득 찼을 때 확장하는 비용이 비싸며, `해시 충돌` 해소를 위해 복잡한 로직이 필요하다 2. 해시 테이블은 `범위 질의(range query)` 에 효율적이지 않다 * 모든 키를 쉽게 스캔할 수는 없다 * 해시 맵에서 모든 개별 키를 조회해야 한다 ### SS 테이블과 LSM 트리 * `SS 테이블이란?` * 키로 정렬된 형식을 `정렬된 문자열 테이블 (Sorted String Table)` 또는 짧게 `SS 테이블` 이라 부른다 * 각 키는 각 병합된 세그먼트 파일 내에 한 번만 나타나야 한다 * 컴팩션 과정은 이렇게 한 번만 나타는 특성을 보장한다! * `SS 테이블이 해시 색인을 가진 세그먼트보다 나은점` 1. 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적이다 * 이 접근법은 `병합 정렬 (merge sort)` 알고리즘이 사용하는 방식과 유사하다 * 먼저 입력 파일을 함께 읽고, 각 파일의 `첫 번째 키`를 본다 (정렬된 순서에 따라) * 그리고 `가장 낮은 키`를 출력 파일로 `복사`한 뒤 이 과정을 반복한다 * 이 과정에서 새로운 병합 세그먼트 파일이 생성된다 * 새로 만든 세그먼트 파일도 키로 정렬되어 있다 * 이렇게 여러 SS테이블 세그먼트를 병합하고 각 키의 최신 값만 유지한다 * 여러 입력 세그먼트에 동일한 키가 있으면, 가장 최근 세그먼트의 값은 유지하고 오래된 세그먼트의 값은 버린다 * why? * 각 세그먼트에는 일정 기간 동안 데이터베이스에 쓰여진 모든 값이 포함되고, * 이것은 `입력 세그먼트 하나의 모든 값`이 `다른 세그먼트의 모든 값`보다 `최신 값`이라는 점을 의미한다 2. 파일에서 `특정 키`를 찾기 위해 메모리에 `모든 키의 색인을 유지`할 필요가 없다 * 찾으려는 키의 `오프셋` 을 알고 있고, 정렬돼 있으면 어느 범위 안에 특정 키가 있는지 알 수 있다 * 즉, 오프셋으로 이동해 찾으려는 키가 나올 때까지 스캔하면 된다 3. 읽기 요청은 요청 범위 내에서 여러 key-value 쌍을 스캔해야 하기 때문에, 해당 레코드들을 `블록`으로 `그룹화`하고, 디스크에 쓰기 전에 `압축` 한다 * 그러면 희소 인메모리 색인의 각 항목은 압축된 블록의 시작을 가리키게 된다 * 디스크 공간을 절약한다는 점 외에도 압축은 `I/O 대역폭` 사용도 줄인다 * `LSM 트리란?` * **Log-Structured Merge-Tree** * SS 테이블의 형식으로 디스크에 key-value 데이터를 저장하는 색인 방식 ### SS 테이블 생성과 유지 * 데이터를 `키로 정렬`할 때 디스크 상에 정렬된 구조를 유지하는 일은 가능하지만, `메모리` 에 유지하는 편이 훨씬 쉽다 * `레드 블랙 트리(red-black tree)`나 `AVL 트리`와 같이 잘 알려졌고 사용 가능한 트리 데이터 구조는 많이 있다 * 이런 데이터 구조를 이용하면 `임의 순서`로 키를 `삽입`하고, `정렬된 순서`로 해당 키를 다시 `읽을` 수 있다 * `저장소 엔진 만들기` * 쓰기가 들어오면 인메모리 `균형 트리(balanced tree)` 데이터 구조(ex. 레드 블랙 트리)에 추가한다 * 이 인메모리 트리는 `멤테이블(memtable)`이라고도 한다 * 멤테이블이 보통 수 메가바이트 정도의 임곗값보다 커지면, `SS테이블 파일`로 `디스크`에 기록한다 * SS테이블을 디스크에 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록한다 * 읽기 요청을 제공하려면 먼저 멤테이블에서 키를 찾아야 한다 * 그 다음 디스크 상의 가장 최신 세그먼트에서 찾는다 * 그 다음으로 두 번째 오래된 세그먼트 세 번째 오래된 세그먼트 등에서 찾는다 * 위의 저장소 엔진 만들기의 `문제점` * 만약 데이터베이스가 고장나면, 아직 디스크로 기록되지 않고 멤테이블(인메모리 트리)에 있는 가장 최신 쓰기는 손실된다 * 이런 문제를 피하기 위해서는 이매번 쓰기를 즉시 추가할 수 있게 `분리된 로그`를 `디스크 상에 유지`해야 한다 * 이 `로그`는 손 상 후 멤테이블을 `복원할 때만 필요`하기 때문에 순서가 정렬되지 않아도 된다! ### SS 테이블에서 LSM 트리 만들기 * 여기에 기술된 알고리즘은 기본적으로 `레벨DB(LevelDB)`와 `록스DB(RocksDB)`, 그리고 다른 애플리케이션에 내장하기 위해 설계된 키-값 저장소 엔진 라이브러리에서 사용한다 * `정렬된 파일 병합`과 `컴팩션` 원리를 기반으로 하는 저장소 엔진을 `LSM 저장소 엔진`이라 부른다 * `루씬(Lucene)`은 엘라스틱서치나 솔라에서 사용하는 `전문 검색 색인 엔진`이다 * 루씬은 `용어 사전 (term dictionary)`을 저장하기 위해 유사한 방법을 사용한다 * `전문 색인`은 키-값 색인보다 훨씬 더 복잡하지만 이와 유사한 개념을 기반으로 한다 * 검색 질의로 단어가 들어오면 단어가 언급된 모든 문서(웹 페이지, 제품 설명 등)를 찾는다 * 이 접근법은 키를 `단어(용어)`로, 값은 단어를 포함한 모든 문서의 `ID 목록(포스팅 목록(postings list))`으로 하는 키-값 구조로 구현한다 * 루씬에서 용어와 포스팅 목록의 매핑은 SS테이블 같은 정렬 파일에 유지하고 필요에 따라 백그라운드에서 병합한다 ### 성능 최적화 * `LSM 트리 알고리즘`은 데이터베이스에 `존재하지 않는 키`를 찾는 경우 느릴 수 있다 * 멤테이블을 확인한 다음 키가 존재하지 않는다는 사실을 확인하기 전에는, 가장 오래된 세그먼트까지 거슬러 올라가야 한다 * LSM 트리의 최적화 - `블룸 필터 (Bloom Filter)` * 블룸 필터는 집합 내용을 `근사`한(approximating), `메모리 효율적 데이터 구조`다! * 블룸 필터는 `키가 데이터베이스에 존재하지 않음`을 알려주므로 존재하지 않는 키를 위한 불필요한 디스크 읽기를 많이 절약할 수 있다 * SS테이블을 압축하고 병합하는 순서 & 시기를 결정하는 전략 * `크기 계층 (sized-tiered)` * 사이즈 계층 컴팩션은 상대적으로 좀 더 `새롭고 작은` SS테이블을 상대적으로 `오래됐고 큰` SS테이블에 연이어 병합한다 * `레벨 컴팩션 (leveled compaction)` * 레벨 컴팩션은 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 ‘'레벨”로 이동하기 때문에 `컴팩션을 점진적으로 진행`해 디스크 공간을 덜 사용한다 * LSM 트리 정리 * LSM 트리의 기본 개념은 `백그라운드`에서 `연쇄적`으로 `SS테이블`을 지속적으로 `병합`하는 것이다 * 이 개념은 데이터셋이 메모리보다 훨씬 더 크더라도 효과적이다 * 데이터가 `정렬된 순서`로 저장돼 있다면 범위 질의를 효율적으로 실행할 수 있다 * 이 접근법의 디스크 쓰기는 `순차적`이기 때문에 LSM 트리가 매우 높은 쓰기 처리량을 보장할 수 있다 ### B 트리 > B Tree (Balanced Tree) * 가장 널리 사용되는 색인 구조 * 구조가 로그 구조화 색인과는 상당히 다르다 * SS테이블과 같이 `키로 정렬된 키-값 쌍`을 유지하기 때문에 키—값 검색과 범위 질의에 효율적이다 * but, 비슷한 점은 이 정도이고, B 트리는 설계 철학이 매우 다르다 * 전통적으로 `4KB` 크기(때로는 더 큰)의 `고정 크기 블록`이나 `페이지`로 나누고, `한 번에 하나의 페이지`에 읽기 또는 쓰기 를 한다 * 각 페이지는 `주소`나 `위치`를 이용해 식별할 수 있다 * 이 방식으로 하나의 페이지가 다른 페이지를 참조할 수 있다 * 포인터와 비슷하지만 메모리 대신 `디스크에 있음` * 한 페이지는 B 트리의 루트(root)로 지정된다 * 색인에서 키를 찾으려면 루트에서 시작한다 * 페이지는 여러 키와 하위 페이지의 참조를 포함한다 * 각 하위 페이지는 키가 계속 이어지는 범위를 담당하고, 참조 사이의 키는 `해당 범위 경계`가 어디인지 나타낸다 * 최종적으로는 `개별 키(리프 페이지(leaf page))`를 포함하는 페이지에 도달한다 * 이 페이지는 각 키 의 값을 포함하거나 값을 찾을 수 있는 페이지의 참조를 포함한다 * B 트리의 한 페이지에서 하위 페이지를 참조하는 수를 `분기 계수(branching factor)` 라고 부른다 * B 트리에 존재하는 키의 값을 `갱신`하려면, * 키를 포함하고 있는 `리프 페이지`를 검색하고, * 페이지의 값을 바꾼 다음, * 페이지를 디스크에 다시 기록한다 * 페이지에 대한 모든 `참조는 계속 유효`하다 * 새로운 키를 `추가`하려면, * 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가한다 * 새로운 키를 수용한 페이지에 `충분한 여유 공간`이 없다면, * 페이지 하나를 반쯤 채워진 페이지 둘로 나누고, * 상위 페이지가 새로운 키 범위의 하위 부분들을 알 수 있게 갱신한다 * 이 알고리즘은 트리가 계속 `균형을 유지`하는 것을 보장한다 * n개의 키를 가진 B 트리는 깊이가 항상 `O(log n)` 이다 * 대부분의 데이터베이스는 B 트리의 깊이가 3이나 4단계 정도면 충분하므로, 검색하려는 페이지를 찾기 위해 많은 페이지 참조를 따라가지 않아도 된다 ### 신뢰할 수 있는 B 트리 만들기 * B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 `덮어쓴다` * 이 동작은 덮어쓰기가 페이지 위치를 변경하지 않는다고 가정한다 * 즉, 페이지를 덮어쓰더라도 페이지를 가리키는 모든 `참조`는 온전하게 `남는다` * 이 부분은 LSM 트리와 같은 `로그 구조화 색인`과는 아주 대조적이다! * `로그 구조화 색인`은 파일에 `추가`만 할 뿐(결국 더 이상 쓸모 없는 파일은 삭제됨) 같은 위치의 파일은 `변경하지 않는다` * 데이터베이스가 고장 상황에서 스스로 복구할 수 있게 만들려면, 일반적으로 디스크 상에 `쓰기 전 로그(write-ahead log, WAL)`(재실행 로그(redo log)라고도 함)라고 하는 데이터 구조를 추가해 B트리를 구현한다 * `동시성 제어`는 보통 `래치(latch)`(가벼운 잠금(lock))로 트리의 데이터 구조를 보호한다 * 유입 질의의 `간섭` 없이 `백그라운드`에서 모든 병합을 수행하고, 이따금 `원자적`으로 새로운 세그먼트를 이전 세그먼트로 바꾸는 방식으로 로그 구조화 접근을 수행한다 ### B 트리 최적화 * 페이지 덮어 쓰기와 고장 복구를 위한 WAL(쓰기 전 로그) 유지 대신, (LMDB 같은) 일부 데이터베이스는 `쓰기 시 복사 방식(copy-on-write scheme)` 사용 * 페이지에 전체 키를 저장하는 게 아니라 키를 `축약`해 쓰면 `공간 절약` 가능 * `리프(leaf) 페이지`를 디스크 상에 `연속된 순서`로 나타나게끔 트리를 배치하기 * but, 트리가 커지면 순서를 유지하기가 어렵다 * 반면에 LSM 트리는 병합하는 과정에서 저장소의 `큰 세그먼트`를 한 번에 다시 쓰기 때문에 디스크에서 `연속된 키`를 서로 `가깝게 유지`하기가 더 쉽다 * 트리에 `포인터` 추가하기 * 각 리프 페이지가 양쪽 형제 페이지에 대한 참조를 가지면, 상위 페이지로 다시 이동하지 않아도 순서대로 키를 스캔할 수 있다 * `프랙탈 트리 (fractal tree)` 같은 B트리 변형은 디스크 찾기를 줄이기 위해 `로그 구조화` 개념을 일부 빌렸다 ### B 트리와 LSM 트리 비교 * B 트리가 LSM 트리보다 일반적으로 `구현 성숙도` 가 더 높지만, LSM 트리도 성능 특성 때문에 관심을 받고 있다 * LSM트리는 보통 쓰기에서 더 빠른 반면, B 트리는 읽기에서 더 빠르다고 여긴다 * 읽기가 보통 LSM 트리에서 더 느린 이유는 각 `컴팩션` 단계에 있는 여러 가지 데이터 구조와 `SS테이블` 을 확인해야 하기 때문이다 ### LSM 트리의 장점 * B 트리 색인은 모든 데이터 조각을 최소한 두 번 기록해야 한다 * 쓰기전 로그 1번 & 트리 페이지에 1번 * B 트리 색인은 해당 페이지 내 몇 바이트만 바뀌어도 한 번에 `전체 페이지`를 `기록`해야 하는 `오버헤드` 도 있다 * 일부 저장소 엔진은 전원 장애가 발생했을 때 `일부만 갱신된 페이지`로 끝나지 않게 동일한 페이지를 `두 번 덮어쓴다` * `로그 구조화 색인` 또한 SS테이블의 반복된 컴팩션과 병합으로 인해 여러 번 데이터를 다시 쓴다 * 데이터베이스에 쓰기 한 번이 데이터베이스 수명 동안 디스크에 여러 번의 쓰기를 일으키는 효과를 `쓰기 증폭 (write amplification)` 이라 한다 * SSD는 수명이 다할 때까지 `블록 덮어쓰기` 횟수가 제한되기 때문에, 쓰기 증폭은 SSD가 유의해야할 부분이다 * `쓰기`가 많은 애플리케이션에서 `성능 병목`은 DB가 디스크에 쓰는 속도일 수 있다 * 이 경우 `쓰기 증폭`은 곧 `성능 비용`이다 * 저장소 엔진이 디스크에 기록할수록, 디스크 대역폭 내 처리할 수 있는 초당 쓰기는 점점 줄어든다 * LSM 트리는 보통 B 트리보다 `쓰기 처리량`을 높게 유지할 수 있다 * LSM 트리가 상대적으로 `쓰기 증폭`이 더 낮고, 트리에서 여러 페이지를 덮어쓰는 것이 아니라 `순차적` 으로 컴팩션된 SS테이블 파일을 쓰기 때문이다 * 이런 차이는 자기 하드드라이브에서 특히 중요한데, 자기 하드드라이브는 순차 쓰기가 임의 쓰기보다 훨씬 빠르기 때문이다 * LSM 트리는 `압축률` 이 더 좋다 * 보통 B 트리보다 디스크에 더 적은 파일을 생성한다 * B 트리 저장소 엔진은 `파편화` 로 인해 사용하지 않는 디스크 공간 일부가 남는다 * 페이지를 나누거나, 로우가 기존 페이지에 맞지 않을 때 페이지의 일부 공간은 사용하지 않게 된다 * LSM 트리는 페이지 지향적이지 않고, `주기적` 으로 `파편화` 를 없애기 위해 SS테이블을 다시 기록하기 때문에 `저장소 오버헤드` 가 더 낮다 * `leveled compaction` 을 사용하면 특히 그렇다 * leveled compaction은 키 범위를 `더 작은 SS테이블로 나누고,` 오래된 데이터는 개별 `레벨`로 이동하는 것! ### LSM 트리의 단점 * 로그 구조화 저장소의 단점은 `컴팩션` 과정이 때로는 `진행 중인 읽기와 쓰기의 성능`에 영향을 준다는 것이다 * 저장소 엔진은 컴팩션을 `점진적` 으로 수행하고, 동시 접근의 영향이 없게 수행하려 한다 * But, 디스크가 가진 자원은 한계가 있다 * 디스크에서 비싼 컴팩션 연산이 끝날 때까지 요청이 대기해야 하는 상황이 발생하기 쉽다 * 반면 B 트리의 성능은 로그 구조화 저장소 엔진보다 예측하기 쉽다 * 또 다른 컴팩션 문제는 `높은 쓰기 처리량` 에서 발생한다 * 디스크의 `쓰기 대역폭`은 `유한`하다 * 초기 쓰기 (logging과 멤테이블을 디스크로 flush)와 백그라운드에서 수행되는 컴팩션 thread가 이 대역폭을 공유해야 한다 * 데이터베이스가 점점 커질수록 컴팩션을 위해 더 많은 대역폭이 필요한 문제가 있다 * B 트리의 장점은 각 키가 `색인의 한 곳`에만 정확하게 `존재`한다는 점이다 * 반면 로그 구조화 저장소 엔진은 다른 세그먼트에 `같은 키의 다중 복사본`이 존재할 수 있다 * 이런 측면 때문에 강력한 트랜잭션 시멘틱을 제공하는 데이터베이스에는 B 트리가 더 좋다 * 많은 RDBMS에서 `트랜잭션 격리` 는 키 범위의 잠금을 사용해 구현한 반면, B트리 색인에서는 `트리에 직접 잠금`을 포함한다 ### 색인 안에 값 저장하기 * 색인에서 `키`는 질의가 검색하는 대상이다 * 색인에서 `값`은 * 질문의 실제 로우(문서, 정점)거나 * 다른 곳에 저장된 로우를 가리키는 `참조`다 * 로우가 저장된 곳을 `힙 파일(heap file)` 이라 하고, 특정 순서 없이 데이터를 저장한다 * 추가 전용이거나 나중에 새로운 데이터로 덮어 쓰기 위해 `삭제된 로우`를 기록할 수도 있다 * `힙 파일 접근` * 여러 보조 색인이 존재할 때, `데이터 중복`을 피할 수 있게 한다 * 각 색인은 힙 파일에서 위치만 참조하고, 실제 데이터는 ㅇ리정한 곳에 유지한다 * 키를 변경하지 않고 값을 갱신할 때 효율적이다 * 새로운 값이 이전 값보다 많은 공간을 필요로 하지 않으면, 레코드를 제자리에 `덮어쓸 수 있다` * 새로운 값이 많은 공간을 필요로 하면, 힙에서 충분한 공간이 있는 새로운 위치로 `이동`해야 한다 * 이 경우 모든 색인이 레코드의 새로운 힙 위치를 가리키게끔 갱신하거나, * 이전 힙 위치에 `전방향 포인터` 를 남겨둬야 한다 * 색인에서 힙 파일로 다시 이동하면 `읽기 성능` 이 안 좋아져서, 어떤 상황에서는 색인 안에 색인된 로우를 저장하는게 좋다 * 이것을 `클러스터드 색인(clustered index)` 라고 한다 * `클러스터드 색인` * 색인 안에 모든 로우 데이터를 저장 * `비클러스터드 색인` * 색인 안에 데이터의 참조만 저장 * `커버링 색인 (covering index)` or `포괄열이 있는 색인 (index with included column)` * 색인 안에 테이블의 칼럼 일부를 저장 * 이렇게 하면 색인만 사용해 일부 질의에 응답 가능 * 이런 경우를 색인이 질의를 `커버` 했다고 말함! ### 다중 칼럼 색인 * 테이블의 다중 칼럼 or 문서의 다중 필드에 동시에 질의를 해야할 때 사용 * `결합 색인 (concatenated index)` * 다중 칼럼 색인의 가장 일반적인 유형 * 하나의 칼럼에 다른 칼럼을 `추가`하는 방식으로 하나의 키에 여러 필드를 단순히 `결합` 한다 * 필드가 연결되는 순서는 색인 정의에 명시! * 이 방식은 (성, 이름) 을 키로 전화번호를 값으로 하는 색인을 제공하는 종이 전화번호부와 유사하다 * 순서가 정렬돼 있기 때문에 특정 성을 가진 모든 사람을 찾거나, 특정 성-이름 조합을 가진 모든 사람을 찾을 때도 이 색인을 사용할 수 있다 * but, 특정 이름을 가진 모든 사람을 찾을 때는 쓸모가 없다 * `다차원 색인` * 한 번에 여러 칼럼에 질의하는 조금 더 일반적인 방법 * 지리 공간 데이터에 중요하게 사용됨 * ex) * 지도에서 레스토랑 찾을 때, 사용자의 현재 위치 기반으로 네모난 지도 내 레스토랑 찾기 * 이를 위한 이차원 범위 질의 ```sql SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079 AND longitude > -0.1162 AND longitude < -0,1004; ``` * 표준 B트리나 LSM 트리 색인은 이런 유형의 질의에 효율적으로 응답할 수 없다 * 위도 범위 안의 모든 레스토랑 or 경도 범위 안의 모든 레스토랑을 줄 순 있지만, 둘을 동시에 주진 못한다 * 이차원 위치를 `공간 채움 곡선(space-filling curve)`을 이용해 단일 숫자로 변환한 다음, 일반 B 트리 색인을 사용하여 해결 할 수 있다 * 또는, R 트리처럼 `전문 공간 색인(specialized spatial index)` 를 사용할 수 있다 * 다차원 색인의 활용은 지리학적인 위치에만 국한되지 않는다 * ex) * 커머스 웹 사이트에서 특정 색상 범위의 제품을 검색하기 위해 (빨강, 초록, 파랑)의 3차원 색인 사용 ### 모든 것을 메모리에 보관 * 지금까지 다룬 데이터 구조는 디스크 한계에 대한 해결책이다 * 디스크는 메인 메모리와 비교해 다루기 어렵다 * 디스크의 장점 * `지속성` * 디스크 내용은 전원이 꺼져도 손실되지 않음 * `가격` * RAM 보다 기가바이트당 가격이 더 저렴 * `인메모리 데이터베이스`의 등장 * RAM이 더 저렴해지고 있고, 데이터셋 대부분 그다지 크지 않기 때문에 메모리에 전체를 보관하는 방식도 적절 * 여러 장비 간 분산해서 보관할 수도 있음 * `맴캐시드` 같은 일부 인메모리 키-값 저장소는 장비가 재시작되면 데이터 손실을 허용하는 `캐시` 용도로만 사용된다 * but, 다른 인메모리 데이터베이스는 `지속성` 을 목표로 한다 * 인메모리 데이터베이스의 `지속성` * 지속성을 위해 (배터리 전원 공급 RAM과 같은) `특수 하드웨어`를 사용하거나, * 디스크에 변경 사항의 `로그`를 기록하거나, * 디스크에 주기적인 `스냅샷`을 기록하거나, * 다른 장비에 인메모리 상태를 `복제` 하는 방법이 있다 * `레디스(Redis)`와 `카우치베이스(Couchbase)`는 `비동기`로 디스크에 기록하기 때문에 약한 지속성을 제공한다 * `디스크 기반 색인`으로 구현하기 어려운 `데이터 모델`을 제공하는 인메모리 데이터베이스 * `레디스` * 우선순위 큐와 셋(set) 같은 데이터 구조를 데이터베이스 같은 인터페이스로 제공 * 메모리에 모든 데이터를 유지하기 때문에 구현이 비교적 간단 * `안티 캐싱(anti-caching)` 접근 방식 * 메모리가 충분하지 않을 때 가장 최근에 사용하지 않은 데이터를 메모리에서 디스크로 내보내고, * 나중에 다시 접근할 때 메모리에 적재하는 방식으로 동작 * 운영체제가 `가상 메모리` 와 `스왑 파일` 에서 수행하는 방식과 유사하지만, 데이터베이스는 전체 메모리 페이지보다 개별 레코드 단위로 작업할 수 있기 때문에 OS보다 더 효율적으로 메모리를 관리할 수 있다 * but, 전체 색인이 메모리에 있어야만 한다 ## 트랜잭션 처리나 분석? * 트랜잭션이 반드시 `ACID` 속성을 가질 필요는 없다 * 원자성(atomicity) * 일관성(consistency) * 격리성(isolation) * 지속성 (durability) * 트랜잭션 처리는 주기적으로 수행되는 `일괄 처리` 작업과 달리, 클라이언트가 지연 시간(low-latency) 이 낮은 읽기와 쓰기를 가능하게 한다는 의미다 * `온라인 트랜잭션 (online transaction processing, OLTP)` * 보통 애플리케이션은 색인을 사용해 일부 키에 대한 적은 수의 레코드를 찾는다 * 레코드는 사용자 입력을 기반으로 삽입되거나, 갱신된다 * 이런 애플리케이션은 대화식이기 때문이 이 접근 패턴을 OLTP라고 한다 * `비즈니스 인텔리전스 (business intelligence)` * 보통 비즈니스 분석가가 작성하며, 회사 경영진이 더 나은 의사 결정을 하게끔 돕는 보고서 * `온라인 분석 처리 (online analystic processing, OLAP)` * BI를 위한 데이터베이스 사용 패턴을 트랜잭션 처리와 구분하기 위해 OLAP라고 부른다 * OLTP vs OLAP | 특성 | 트랜잭션 처리 시스템 (OLTP) | 분석 시스템 (OLAP) | | -------- | ---------------------------- | -------------------------------------- | | 주요 읽기 패턴 | 질의당 적은 수의 레코드, 키 순으로 가져옴 | 많은 레코드에 대한 집계 | | 주요 쓰기 패턴 | 임의 접근, 사용자 입력을 낮은 지연 시간으로 등록 | 대규모 불러오기 (bulk import, ETL) or 이벤트 스트림 | | 주요 사용처 | 웹 애플리케이션을 통한 최종 사용자/소비자 | 의사결정 지원을 위한 내부 분석가 | | 데이터 표현 | 데이터의 최신 상태 (현재 시점) | 시간이 지나며 일어난 이벤트 이력 | | 데이터셋 크기 | 기가바이트 \~ 테라바이트 | 테라바이트 \~ 페타바이트 | ### 데이터 웨어하우징 * `데이터 웨어하우스 (data warehouse)` * 분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스 * 회사 내의 모든 다양한 OLTP 시스템에 있는 데이터의 `읽기 전용 복사본` * 데이터는 OLTP 데이터베이스에서 * (주기적인 `데이터 덤프`나 지속적인 `갱신 스트림`을 사용해) `추출`(extract) 하고, * 분석 친화적인 스키마로 `변환`(transform) 하고, * 깨끗하게 정리한 다음 데이터웨어하우스에 `적재`(load) 한다 * 데이터 웨어하우스로 데이터를 가져오는 이 과정을 `ETL (Extract - Transform - Load)` 이라 한다 * `데이터 웨어하우스의 장점` * 분석을 위해 OLTP 시스템에 직접 질의하지 않고, 개별 데이터 웨어하우스를 사용하는 큰 장점은 `분석 접근 패턴` 에 맞게 `최적화` 할 수 있다는 점이다 ### OLTP 데이터베이스와 데이터 웨어하우스의 차이점 * SQL은 일반적으로 `분석 질의`에 적합하기 때문에 데이터 웨어하우스의 데이터 모델은 `관계형 모델`을 사용한다 * SQL 질의를 생성하고, 결과를 시각화하고, 분석가가 `drill-down`, `slicing`, `dicing` 같은 작업을 통해 데이터를 탐색할 수 있게 해주는 여러 그래픽 데이터 분석 도구가 있다 * `drill-down` * 요약된 정보에서 상세 정보까지 계층을 나눠 점점 구체적으로 분석하는 작업 * `slicing` & `dicing` * 상세한 분석을 위해 주어진 큰 규모의 데이터를 작은 단위로 나누고, * 원하는 세부 분석 결과를 얻을 때까지 반복한다는 뜻 * 각각 매우 다른 `질의 패턴`에 맞게 최적화됐기 때문에 `시스템의 내부`는 완전히 다르다 ### 분석용 스키마: 별 모양 스키마와 눈꽃송이 모양 스키마 * `별 모양 스키마 (star schema)` * 많은 데이터 웨어하우스는 별 모양 스키마로 알려진 상당히 정형화된 방식을 사용한다 * `사실 테이블 (fact table)` * 사실 테이블의 각 로우는 특정 시각에 발생한 이벤트에 해당한다 * 보통 사실은 개별 이벤트를 담는다 * 이는 나중에 분석의 유연성을 극대화할 수 있기 때문이다 * 하지만 이것은 사실 테이블이 매우 커질 수 있다는 의미다 * 사실 테이블의 일부 칼럼은 제품이 판매된 가격과 공급자로부터 구매한 비용(이익 마진을 계산할 수 있음)과 같은 속성이다 * 사실 테이블의 다른 칼럼은 차원 테이블(dimension table) 이라 부르는 다른 테이블을 가리키는 외래 키 참조다 * 사실 테이블의 각 로우는 이벤트를 나타내고 차원은 이벤트의 속성인 누가(who), 언제(when), 어디서(where), 무엇을(what), 어떻게(how), 왜(why) 를 나타낸다 * `눈꽃송이 모양 스키마(snowflake schema)` * 차원이 하위차원으로 더 세분화된다 * 눈꽃송이 스키마는 별 모양 스키마보다 더 정규화됐지만 분석가들이 별 모양 스키마를 작업하 기 더 쉽다는 이유로 선호한다 ### 칼럼 지향 저장소 * 모든 값을 하나의 로우에 함께 저장하지 않는 대신 각 칼 럼별로 모든 값을 함께 저장한다 * 각 칼럼을 개별 파일에 저장하면 질의에 사용되는 칼럼만 읽고 구분 분석하면 된다 * 이 방식을 사용하면 작업량이 많이 줄어든다 ## 정리 * 고수준에서 저장소 엔진은 트랜잭션 처리 최적화(OLTP)와 분석 최적화(OLAP)라는 큰 두 가지 범주로 나뉜다. * OLTP와 OLAP의 사용 사례에서 보면 접근 패턴 간 큰 차이가 있다 * `OLTP 시스템` * 사용자 대면이기 때문에 대량의 요청을 받을 수 있다 * 부하를 처리하기 위해 보통 애플리케이션이 각 질의마다 작은 수의 레코드만 다룬다 * 애플리케이션은 키의 일부만 사용하는 레코드를 요청하고 저장소 엔진은 요청한 키의 데이터를 찾기 위해 색인을 사용한다 * 이 경우는 대개 디스크 탐색이 병목이다 * `데이터 웨어하우스와 유사한 분석 시스템 (OLAP)` * 최종 사용자가 아닌 비즈니스 분석가가 주로 사용하기 때문에 덜 알려져 있다 * OLTP 시스템보다 훨씬 더 적은 수의 질의를 다루지만 각 질의는 대개 매우 다루기 어렵고 짧은 시간에 수백만 개의 레코드를 스캔해야 한다 * 이 경우는 일반적으로 디스크 대역폭( 디스크 탐색이 아닌)이 병목이다 * 칼럼 지향 저장소는 이런 종류의 작업부하를 처리할 때 사용 가능한 날로 인기가 높아지고 있는 솔루션이다 * OLTP 측면에서 두 가지 주요한 관점 * 로그 구조화 관점에서 파일에 추가와 오래된 파일의 삭제만 허용하고, 한 번 쓰여진 파일은 절대 갱신하지 않는다 * 비트캐스크, SS테이블, LSM 트리, 레벨DB, 카산드라, HBase, 루씬 등이 이 그룹에 속한다 * 제자리 갱신 관점에서 덮어쓰기 할 수 있는 고정 크기 페이지의 셋으로 디스크를 다룬다 * 이 관점에서 가장 큰 예가 `B트리`다 * B 트리는 모든 주요 관계형 데이터베이스와 많은 비정형 데이터베이스에서도 사용한다