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)

    • 지도에서 레스토랑 찾을 때, 사용자의 현재 위치 기반으로 네모난 지도 내 레스토랑 찾기

      • 이를 위한 이차원 범위 질의

        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 트리는 모든 주요 관계형 데이터베이스와 많은 비정형 데이터베이스에서도 사용한다