책너두 (데이터 중심 애플리케이션 설계) 6일차 (~84p)

요약

• 데이터베이스에서 수행되는 저장소 엔진의 내부 수행 작업을 이해하게 됨.
• 가장 간단한 데이터 베이스의 구조, 데이터 구조를 이해함.
  • 데이터가 많을 수록 읽기 성능이 안좋음. → 색인이 필요
• 해시 색인을 이용한 저장소 엔진의 원리를 이해함
  • 로그 추가 방식
• SS테이블, LSM 트리를 이용한 저장소 엔진 원리를 이해함.
  • 로그 추가 방식, 키 값은 정렬
• B 트리를 이용한 저장소 엔진 원리를 이해함.
  • 고정 페이지 이용, 페이지 참조를 이용하여 키 를 이용한 질의 & 키 값 추가 가능
  • B 트리 깊이가 O(log n) 이므로 많은 페이지 참조 없이 색인을 이용하여 값 조회 가능

메모

3장. 저장소와 검색

• 애플리케이션 개발자는 애플리케이션에 적합한 저장소 엔진을 선택하는 작업이 필요함.
  • 저장소 엔진이 내부에서 수행되는 작업에 대해 대략적인 개념을 이해할 필요가 있음.
• 이번 장은 저장소 엔진 , 로그 구조(log-structured) 저장소 엔진 , 페이지 지향(page-oriented) 계열 저장소 엔진 을 살펴본다.

데이터베이스를 강력하게 만드는 데이터 구조

• 가장 간단하게 데이터베이스를 만들기 위해서는 하나의 파일에 key-value 쌍을 파일 끝에 계속해서 집어 넣는 것이다.
  • db_set() : key,value 쌍 저장
  • db_get() : key 에 해당하는 value 조회
• 일반적으로, 파일 추가 작업은 매우 효율적임. (즉, db_set은 매우 간단한 작업에서 꽤 좋은 성능을 보여줌)
  • 많은 데이터베이스는 내부적으로 추가 전용(append-only) 데이터 파일인 로그(log)를 사용한다
• db_get 함수는 데이터베이스에 레코드가 많으면 성능이 매우 안좋아짐.
  • 데이터베이스 파일을 처음부터 끝까지 스캔해야 하기 때문 → O(n)
  • 즉, 다른 데이터 구조가 필요함. → 색인
• 색인은 부가적인 메타데이터를 유지하는 것임.
  • 메타데이터는 이정표 역할을 하고, 원하는 데이터의 위치를 찾는데 도움을 줌.
  • 색인은 기본 데이터(primary data)에서 파생된 추가적인 구조임.
  • 색인은 데이터를 쓸 때마다 갱신해야 하므로 쓰기 속도를 느리게 만듬
  • 대신, 읽기 질의 속도가 향상됨.
    • 이는 저장소 시스템의 중요 트레이드 오프임.
    • 이러한 이유로 데이터베이스가 자동으로 모든 것을 색인하지 않음.
      • 애플리케이션 개발자 or 데이터베이스 관리자가 질의 패턴에 대한 지식을 이용하여 수동으로 색인해야 함. → 그래야 필요 이상의 오버헤드를 발생시키지 않고 애플리케이션에 가장 이익을 주는 색인을 선택할 수 있음.

해시 색인

• 키-값 저장소는 사전 타입(dictionary type)과 매우 유사함.
  • Hash Map 으로 구현함.
  • 인메모리 데이터 구조를 위한 해시 맵이 이미 있으니, 디스크 상의 데이터를 색인하기 위해 인 메모리 데이터 구조를 사용하는 방법을 고민할 수 있을 것이다.
• 만약, 단순히 데이터를 파일에 추가하는 방식이라면, 가장 간단한 색인 전략은 키를 데이터 파일의 바이트 오프셋 에 매핑하여 디스크에서 인메모리 해시맵을 유지할 수 있다. (p75. 그림 참고)
  • 바이트 오프셋은 값을 바로 찾을 수 있는 위치를 의미함.
  • 이 방식은 실제로 많이 사용하는 접근법임.
  • ex) 비트 캐스크(BitCask)
    • 해시 맵을 전부 메모리에 유지하므로 사용 가능한 램에 모든 키가 저장된다는 조건을 전제로, 고성능 읽기 쓰기를 보장함.
    • 데이터 파일 일부가 이미 파일 시스템 캐시에 있으면 읽기에 디스크 입출력이 필요하지도 않음.
• 하지만, 데이터에 파일을 항상 추가만 하면 결국 디스크 공간이 부족해짐.
  • 특정 크기의 세그먼트(segment)로 로그를 나누는 방식이 좋은 해결책임
  • 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행함.
  • 세그먼트 파일들이 모이면, 그에 대한 컴팩션을 수행하면 됨.
    • 컴팩션은 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것을 의미함. (p76 그림 참고)
  • 각 세그먼트는 키를 파일 오프셋에 매핑한 자체 인메모리 해시 테이블을 가짐.
• 추가 전용 로그를 쌓는 것은 여러 측면에서 좋은 설계임.
  • 덮어쓰기를 하다 데이터베이스가 죽는 경우에 대해 걱정할 필요가 없음.
  • 추가, 세그먼트 병합은 수차 쓰기 작업이므로 무작위 쓰기보다 훨씬 빠름
  • 오래된 세그먼트의 병합을 통해, 조각화되는 데이터 파일 문제를 피할 수 있다.
• 대신, 해시 테이블 색인에도 제약사항은 있음.
  • 어쨋든 해시 테이블은 메모리에 저장해야 하므로 키가 너무 많으면 안됨. (디스크 해시 맵을 유지할 수 있지만, 무작위 접근 I/O가 많이 필요하며, 디스크가 꽉 찼을때 확장 비용도 비쌈. 또, 충돌 해소를 위한 성가신 로직까지 필요함..)
  • 해시 테이블은 범위 질의에 효율적이지 않음. (모든 키를 쉽게 스캔할 수 없음.)

SS테이블과 LSM 트리

• 세그먼트 파일 형식에 만약, 키로 정렬하는 요구사항이 추가됐다고 해보자.
  • 이처럼 키로 정렬된 형식을 정렬된 문자열 테이블(Sorted String Table) 또는 짧게 SS테이블 이라고 부름
• SS테이블은 해시 색인을 가진 로그 세그먼트보다 몇 가지 큰 장점이 있음.
  • 키 파일이 정렬된 세그먼트 파일을 가지므로 특정 키를 찾기 위해 모든 키의 색인을 유지할 필요가 없음.
    • 키 값이 정렬되어 있기에 세그먼트 파일에서 특정 키의 정확한 오프셋을 알지 못하더라도, 우리가 알고 있는 키의 오프셋을 안다면, 키는 정렬되어 있기 때문에 특정 키가 우리가 알고있는 키의 오프셋 사이에 있는 부분만 스캔하면 된다.

SS테이블 생성과 유지

• 데이터를 키로 정렬하기 위한 방법
  • 디스크 상에 정렬된 구조를 유지하는 일은 가능하지만, (ex, B 트리) 메모리에 유지하는 편이 훨씬 쉬움
    • 레드 블랙트리, AVL 트리 데이터 구조를 이용하여 임의 순서로 키를 삽입하여도 정렬된 순서로 해당 키를 다시 읽을 수 있음.
• 위 방식을 이용한 저장소 엔진을 다음과 같이 만들 수 있음.
  • 쓰기가 들어오면, 균형 트리 데이터 구조를 이용하여 인메모리 트리(멤테이블, memtable)에 추가한다.
  • 멤테이블이 임곗값보다 커지면 SS테이블 파일로 디스크에 기록한다.
  • 읽기 요청시 먼저 멤테이블 → 디스크 상 최신 세그먼트 → 두 번째 세그먼트 → … 로 찾는다.
  • 세그먼트가 합치고 덮어지는 병합, 컴팩션 과정이 수행되는데, 이는 백그라운드에서 수행됨.
• 위 저장소 엔진은 데이터베이스가 고장나면 아직 디스크에 기록되지 않은 멤테이블에 있는 최신 쓰기가 손실됨.
  • 이 문제를 피하려면 매번 쓰기를 즉시 추가할 수 있는 분리된 로그를 디스크 상에 유지해야 함.

SS테이블에서 LSM 트리 만들기

• 위에 기술한 알고리즘과 색인 구조는 로그 구조화 병합 트리(Log-Structured Merge-Tree), 또는 LSM 트리 라는 이름으로 패트릭 오닐이 발표함.
• 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진은 LSM 저장소 엔진이라 부름.

성능 최적화

• 실제로 많은 세부 사항이 저장소 엔진을 잘 동작하게 만든다.
  • ex) LMS 트리 알고리즘은 데이터베이스에 존재하지 않는 키를 찾을 때 느릴 수 있음.
  • 멤테이블 → 오래된 세그먼트를 거슬러 올라가는 과정때문
  • 이 종류의 접근을 최적화하기 위해 저장소 엔진은 블룸 필터(Bloom filter)를 추가적으로 사용함.
    • 블룸 필터는 집합 내용을 근사한(approximating) 메모리 효율적 데이터 구조임.
    • 즉, 키가 데이터베이스에 존재하지 않음을 알려주기에 불필요한 디스크 읽기 절약 가능.
• SS테이블 압축 & 병합하는 순서, 시기를 결정하는 다양한 전략도 있음.
  • 크기 계층(size-tiered)
    • 새롭고 작은 SS테이블을 오래됐고 큰 SS테이블에 병합한다.
  • 레벨 컴팩션(leveled compaction)
    • 키 범위를 더 작은 SS테이블로 나누고, 오래된 데이터는 개별 “레벨”로 이동함
    • 따라서, 컴팩션을 점진적으로 진행해서 디스크 공간을 덜 사용한다.

B 트리

• 위의 로그 구조화 색인은 보편화되고 있지만, 일반적인 색인 유형은 아님
• 가장 널리 사용되는 색인 구조는 B 트리(B-Tree)임.
• 관계형 데이터베이스에서 표준 색인 구현으로 사용중임.
  • 비관계형 데이터베이스에서도 사용함.
• B 트리 또한 SS테이블과 같이 키로 정렬된 키-값 쌍을 유지하기에 키-값 검색과 범위 질의에 효율적임.
  • 하지만 이점만 비슷할 뿐, B 트리 설계 철학은 매우 다름.
• 로그 구조화 색인은 데이터베이스를 수 메가바이트 이상의 가변 크기를 가진 세그먼트로 나누고, 항상 순차적으로 세그먼트를 기록했음.
• B 트리는 전통적으로 4KB 크기의 고정 크기 블록 or 페이지로 나누고 한 번에 하나의 페이지에 읽기, 쓰기를 함.
  • 디스크가 고정 크기 블록으로 배열되는데, 이 설계는 하드웨어에 더 밀접한 관련이 있음.
  • 각 페이지는 주소, 위치를 이용하여 식별할 수 있음.
  • 포인터와 비슷하지만, 메모리 대신에 디스크에 존재함.
• 하나의 페이지가 B 트리의 루트(root) 로 지정됨.
  • 색인에서 키를 찾기 위해 루트에서 시작함.
  • 그 과정에서 여러 키, 하위 페이지를 참조함. → 키가 있는 범위 경계를 찾음.
  • 최종적으로, 개별 키(리프 페이지(leaf page))를 참조하는 페이지에 도달함.
    • 이 페이지는 각 키의 값을 포함하거나, 값을 찾을 수 있는 페이지의 참조를 포함함.
  • B 트리가 한 페이지에서 하위 페이지를 참조하는 수를 분기 계수(branching factor) 라고 부름
    • 보통 수백 백에 달함.
• B 트리에 존재하는 키 값을 갱신하려면 키를 포함하고 있는 리프 페이지를 검색하고, 페이지의 값을 바꾼 다음, 페이지를 디스크에 다시 기록해야 함.
• B 트리에 키를 새로 추가하려면 키를 포함하는 범위의 페이지를 찾아서 해당 페이지에 키와 값을 추가한다.
  • 만약, 새로운 키를 수용할 페이지가 여유 공간이 없다면, 페이지 하나를 반쯤 채워진 페이지 둘로 나눠서, 상위 페이지가 새로운 키 범위의 하위 부분을 알 수 있게 갱신한다.
• 이 방식(알고리즘)을 통해 트리가 계속 균형을 유지해나가는 것을 보장함.
• n 개의 키를 가진 B 트리 깊이는 항상 O(log n) 이다.