[Data-Intensive] Ch3. 저장소와 검색

저장소와 검색

‘데이터 중심 애플리케이션 설계’를 읽고 정리하고자함

• 데이터베이스가 데이터를 저장하는 방법과 데이터를 요청했을 때 다시 찾을 수 있는 방법에 대해 설명
• 특정 workload 유형에서 좋은 성능을 내게끔 저장소 엔진을 선택하려면 저장소 엔진이 내부에서 수행되는 작업에 대한 개념을 이해해야함
• 관계형 데이터베이스와 NoSQL 계열 저장소 엔진에 대해 설명함
• 또 로그 구조(Log-Structed)계열 저장소 엔진과 B-Tree 같은 페이지 지향(Page-Oriented)계열 저장소 엔진을 검토

데이터베이스를 강력하게 만드는 구조 - 색인!

#!/bin/bash

db_set(){
    echo "$1,$2" >> database
}

db_get(){
    grep "^$1," database | sed -e "s/^$1,//" | tail -n1
}

• 키-값 저장소를 두 함수로 구현할 수 있음

  • db_set key value 데이터베이스에 key value를 저장함
  • 최신 값을 찾기 위해 tail -n1 처리
  • db_set처럼 많은 데이터베이스는 내부적으로 append-only 데이터 파일인 ‘로그(log)’를 활용
  • 로그는 일반적으로 애플리케이션에서 무슨 일이 일어났는지 기술한 텍스트를 출력하지만, 여기서는 그냥 ‘연속된 추가 전용 레코드’로 정의

• 문제 : 많은 레코드가 있으면 성능이 좋지않음 (키를 찾을 때 마다 처음부터 끝까지 스캔해야함 O(n))

• 데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서는 다른 데이터 구조가 필요하고 이것이 바로 ‘색인(index)’
• 색인은 어떤 부가적인 메타정보를 유지하는 것으로, 이 메타데이터가 이정표 역할을 해서 원하는 데이터를 찾는데 도움을 줌
• 색인은 primary data에서 파생된 추가적인 구조로, 질의 성능에만 영향을 줌
• 추가적인 구조를 가지고 있어 쓰기 과정에서 오버헤드 발생함 , 데이터를 쓸 때마다 매번 색인도 갱신해야하기 때문

해시 색인

• 키-값 저장소는 대부분 사전 타입과 유사하고, HashMap(HashTable)로 구현함
• 인메모리 데이터 구조를 위한 해시맵은 이미 있으니, 디스크 상의 데이터를 색인하기 위해 인메모리 구조를 사용하는 것은 어떨까?
• 앞의 문제에 대한 해결법 : 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵 유지

  • 값을 조회할 때, 해시맵을 사용해 데이터파일에서 오프셋을 찾아 해당 위치를 구하고 값을 읽어옴

• 간단하지만, 비트캐스트(Bitcask - Riak의 기본 저장소 엔진)가 근본적으로 사용하는 방법
• 이 방법은 ‘각 키의 값이 자주 갱신되는 상황에 적합’

  e.g) 키가 동영상 url이 값이 재생된 횟수

• 그런데 파일에 항상 추가만 한다면 디스크 공간이 부족해지겠지..?
• 이런 상황에서는 특정 크기의 세그먼트(segment)로 로그를 나누어, 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트에 쓰기 진행
• 또한, 세그먼트 파일들에 대해 컴팩션(compaction)을 수행해, 로그에서 중복된 키를 버리고 각 키의 최신 갱신값만 유지함
• 이 방법이 간단하지만. 구현하려면 다음과 같은 중요한 문제가 있음

1. 레코드 삭제

   • 키와 관련된 값을 삭제하려면, 데이터 파일에 특수한 삭제 레코드를 추가해야함 (툼스톤(tombstone)이라고 함)
   • 로그 세그먼트가 병합할 때, 툼스톤은 병합과정에서 삭제된 키의 이전 값을 무시함

2. 고장 복구

   • 데이터베이스가 재시작되면 인메모리 해시맵은 손실
   • 다시 세그먼트 파일을 처음부터 읽고 각 키에 대한 최신값의 오프셋을 확인해서 각 세그먼트 해시맵을 복원해야함
   • 세그먼트 파일이 크면 오래걸리기 때문에, 비트캐스크는 각 세그먼트 해시맵의 스냅샷을 디스크에 저장해 복구 속도를 높임

3. 부분적 레코드 쓰기

   • 로그에 레코드를 추가하는 도중에 죽을 수 있음
   • 비트캐스크 파일은 체크섬을 포함해 로그의 손상된 부분을 탐지해 무시할 수 있음

4. 동시성 제어

   • 순차적으로 로그에 추가할 때, 하나의 쓰기 쓰레드 사용하는 것이 좋음
   • 데이터 파일 세그먼트는 추가 전용, immutable이므로 다중 쓰레드로 읽을 수 있음

• 추가 전용 로그는 낭비같아. 그냥 예전 값을 새로값으로 갱신하는게 좋지 않아?
• 하지만, 추가 전용 설계는 여러 측면에서 좋은 설계임

  1. 추가와 세그먼트 병합은 순차적인 쓰기 작업이기 때문에 무작위 쓰기보다 훨씬 빠름
  2. 세그먼트 파일이 추가전용이나 불변이면 동시성과 고장 복구는 훨씬 간단함
  3. 오래된 세그먼트 병합은 시간이 지남에 따라 조각화되는 데이터 파일 문제를 피할 수 있음

• 해시 테이블 색인의 제약사항
  1. 메모리에 저장해하므로, 키가 너무 많으면 문제가 될 수 있음

     • 원칙적으로 해시맵을 유지하지만, 디스크 상의 해시맵에 좋은 성능은 기대하기 어려움

  2. 범위 질의(range query)가 비효율적임

     • 해시맵은 모든 개별 키를 조회해야함

SS테이블과 LSM트리

• 해시색인이 가지는 제약이 없은 색인구조
• 세그먼트 파일에 ‘키-값 쌍을 키로 정렬’하는 것으로, 이렇게 키로 정렬된 형식을 정렬된 문자열 테이블(Sorted String Table == SSTable)

해시 색인을 가진 로그 세그멘트에 비해 SSTable이 가지는 장점

1. 세그먼트 병합은 파일이 사용 가능한 메모리보다 크러다도 간단하고 효율적

   • mergesort 알고리즘과 유사함

2. 파일에서 특정 키를 찾기 위해 더는 메모리에 모든 키를 색인을 유지할 필요 없음

   • 키의 정확한 오프셋을 모르더라도, 정렬이 되어 있어 특정 두개의 키 사이에 찾고자하는 키가 있다는 것을 알 수 있음
   • 일부 키에 대한 오프셋을 알려주는 인메모리 색인이 필요하지만, 사이즈가 작음

3. 읽기 요청은 요청 범위 내에서 여러 키-값 쌍을 스캔해야하므로 해당 레코드들을 블록으로 그룹화하고 디스크에 쓰기 전에 압축함

   • 이렇게 되면 인메모리 색인의 각 항목은 압축된 블록의 시작을 가리키고, 디스크 공간 절약 및 I/O bandwidth 사용량도 줄 수 있음

SS테이블 생성과 유지

• 데이터를 키로 정렬하려면 어떻게 해야할까?

• red-black tree나 AVL 트리와 같은 데이터 구조를 이용하면 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 읽을 수 있음

• 쓰기가 들어오면 인메모리 균형 트리 데이터 구조에 추가함( AVL or red-black etc..)

• 이 인메모리 트리를 ‘멤테이블(memtable)’이라고 함

• 멤테이블이 특정값보다 커지면 SS테이블 파일로 디스크에 기록함
• 새로운 SS테이블은 데이터베이스의 가장 최신 세그먼트가 되고, 디스크에 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록
• 읽기 요청은 멤테이블 -> 최신 세그먼트-> 다음 세그먼트 -> .. 이 순서로 찾음

• 가끔 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 병합과 컴팩션 작업을 수행 ( 백그라운드에서 )

• 오케이, 좋아 근데 문제가 하나 더 있음
• 데이터베이스가 고장나면 아직 디스크로 기록되지 않은 멤테이블에 있는 데이터는 유실됌
• 해결하려면, 매번 쓰기를 즉시 추가하는 분리된 로그를 디스크 상에 유지하고, 복구시에만 사용되므로 정렬이 되지 않아도 괜찮음

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

• Log-Structured Merge-Tree (LSM Tree)

  • 정렬된 파일 병합과 컴팩션 원리르 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라고도 함

성능 최적화

1. 블룸필터(Bloom Filter)
   • LSM 트리 알고리즘은 데이터베이스에 존재하지 않은 키를 찾는 경우 느릴 수 있음
   • 멤테이블을 확인한 다음 , 오래된 세그먼트까지 다 찾아, 즉 디스크에서 읽어야할 수 있음
   • 이 문제를 최적화하기 위해 저장소 엔진은 ‘블룸필터(Bloom Filter)’을 사용함

     • 집합 내용을 근사한 메모리 효율적 데이터 구조
     • 키가 존재하지 않음을 알려주므로, 없다면 불필요한 디스크 읽기를 절약할 수 있음

2. 사이즈 계층(size-tiered)과 레벨 컴팩션(leveled compaction)
   • SS테이블을 압축하고 병합하는 순서와 시기를 결정하는 전략
   • LevelDB/RocksDB은 레벨 컴팩션을 사용함
   • HBase는 사이즈 계층, 카산드라는 둘 다 지원

사이즈 계층 컴팩션

• 상대적으로 좀 더 새롭고 작은 SS테이블을 상대적으로 오래됐고 큰 SS테이블에 연이어 병합

레벨 컴팩션

• 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 레벨로 이동하기 때문에 점진적으로 진행해 디스크 공간을 덜 사용함

• LSM 트리의 기본 개념은 ‘백그라운드에서 연쇄적으로 SS테이블을 지속적으로 병합하는 것’
• 데이터가 정렬된 순서로 저장돼 있으면 범위 질의를 효율적으로 수행할 수 잇고, 디스크 쓰기는 순차적이기 때문에 LSM트리가 매우 높은 처리량 보장

B 트리

• SS테이블과 같이 키로 정렬된 키-값 쌍을 유지하기 때문에, 키-값 검색과 범위 질의에 효율적

• 앞서 살핀 로그 구조화 색인은 데이터베이스를 수 MB 이상의 가변 크기를 가진 세그먼트로 나누고 항상 순차적으로 세그먼트를 기록

• 반면, B트리는 4KB 크기의 고정 크기의 블록이나 ‘페이지(page)’로 나누고 한번에 하나의 페이지에 읽기 또는 쓰기를 함
• 각 페이지는 주소나 위치를 이용해 식별할 수 있고, 하나의 페이지가 다른 페이지를 참조할 수 있음

  • 포인터와 비슷하지만 메모리 대신 디스크에 있음

• 한 페이지는 B트리의 root로 지정되고, 색인에서 키를 찾으면 루트부터 시작하고, 페이지는 여러 키와 하위 페이지 참조롤 포함
• 각 하위 페이지는 키가 계속 이어지는 범위를 담당하고 참조 사이의 키는 해당 범위 경계가 어딘지 나타냄
• 최종적으로는 개별 키(leaf page)를 포함한 페이지에 도달하고 이는 각 키의 값을 포함하거나 값을 찾을 수 있는 페이지의 참조를 포함함

• B 트리의 한 페이지에서 하위 페이지를 참조하는 수를 분기 계수 (branching factor)

• 키의 값 갱신

  1. 키를 포함하고 있는 리프 페이지를 검색
  2. 페이지의 값을 바꾼 다음 페이지를 디스크에 다시 기록 ( 페이지에 대한 모든 참조는 계속 유효)

• 키 추가

  1. 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가

     • 새로운 키를 수용한 페이지가 충분한 여유공간이 없다면 페이지를 나눔

• 이 알고리즘은 트리가 계속 균형을 유지하는 것을 보장
• n개의 키를 가진 B 트리의 깊이는 항상 O(logN)
• 대부분 데이터베이스는 깊이가 3,4먼 검색하려는 페이지를 찾기 위해 많은 페이지 참조를 따라가지 않아도 될 정도로 충분함

  • 분기 계수가 500의 4KB 페이지의 4단계 트리는 256TB 까지 저장할 수 있

신뢰할 수 있는 B 트리 만들기

• 새로운 데이터를 디스크 상의 페이지에 덮어쓰는 것으로 쓰기를함

  • 덮어쓰기기가 페이지 위치를 변경하지 않는다고 가정
  • 즉, 페이지가 덮어쓰더라도 페이지를 가르키는 모든 참조는 그대로 남음

• LSM 트리와 같은 로그 구조화 색인과는 대조되는 점

  • 로그 구조화 색인은 파일에 추가만 할 뿐 같은 위치의 파일은 변경하지 않음

• WAL(write-ahead alog == redo log == 재실행 로그)

  • 데이터베이스가 고장 상황에서 스스로 복구할 수 있게 하는 방법
  • 디스크 상에 쓰기 전 로그(WAL) 데이터 구조를 추가해 B트리 구현

• WAL은 트리 페이지에 변경된 내용을 적용하기 전에 모든 B트리의 변경사항을 기록하는 추가 전용 파일

  • 데이터베이스가 고장 이후 복구 될 때 일관성 있는 상태로 B트리 복구하는데 사용

• 동시성 제어

  • 같은 자리의 페이지를 갱신하는 작업시, 래치(latch - 가벼운 lock)로 트리의 데이토 구조를 보호함

B 트리 최적화

1. 페이지 덮어 쓰기와 고장 복구를 위한 WAL 유지 대신 일부 데이터베이스는 ‘copy-on-write schema’ 사용

   • 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가르킴

2. 페이지에 전체 키를 저장하는 것이아닌 키를 축약해 공간 절약

   • 트리 내부에서 키가 키 범위 사이의 경계 역할을 하는데 충분한 정보만 제공하면 됌
   • 페이지 하나에 키를 많이 채우면, 더 높은 분기 계수를 얻어 , 트리의 깊이를 낮출 수 있음

3. 리프 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리를 배치하도록 시도

   • 일반적으로 페이지는 디스크 상 어디에나 위치 할 수 있고 키 범위가 가까운 페이지들이 디스크 상에 가까이 있어야할 필요가 없음
   • 하지만 질의가 정렬된 순서로 키 범위의 상당 부분을 스캔해야한다면, 모든 페이지에 대해 디스크를 찾기를 하면 페이지 단위 배치는 비효율적

4. 트리에 포인터 추가

   • 각 리프 페이지가 양 쪽 형제 페이지에 대한 참조를 가지고 있다면 상위 페이지로 다시 이동하지 않아도 순서대로 키 스캔이 가능

5. 프랙탈 트리(fractal tree)

   • B트리 변형으로 디스크 찾기를 줄이기 위해 로그 구조화 개념을 빌림

B 트리와 LSM 트리 비교

• LSM 트리는 보통 쓰기에서 빠른 반면, B 트리는 읽기에서 빠름

  • LSM 트리에서 읽기가 느린 이유는 컴팩션 단계에 있는 여러 데이터 구조와 SS테이블을 확인해야하기 때문

LSM 트리의 장점

• B트리 색인은 모든 데이터 조각을 최소한 두 번 기록해야함

  • wal 한번, 트리 페이지에 한번
  • 그래서, 페이지 내 몇 바이트만 바껴도 한번에 전체 페이지를 기록해야하는 오버헤드가 있음

• 로그 구조화 색인 또한 SS테이블의 반복된 컴팩션과 병합으로 인해 여러번 데이터를 다시 씀

  • 데이터베이스에 쓰기 한번이 데이터베이스 수명 동안 디스크에 여러번의 쓰기를 야기하는 효과를 ‘쓰기 증폭(write amplification)’
  • SSD는 수명이 다할 때까지 블록덮어쓰기 횟수가 제한되기 때문에 쓰기 증폭은 SSD 경우 특별한 관심사라고함

• LSM 트리는 B 트리보다 쓰기 처리량을 높게 유지할 수 있음

  • 상대적으로 쓰기 증폭이 더 낮고 트리에서 여러 페이지를 덮어쓰는 것이 아니라, 순차적 컴팩션된 SS테이블 파일 쓰기 때문
  • 이는 HDD의 순차쓰기가 랜덤쓰기보다 빠른 점에서 유용한 장점이 될 수 있음

• 압축률이 더 좋음

  • B 트리는 파편화로 사용하지 않은 디스크 공간이 있음
  • 페이지를 나누거나 로우가 기존 페이지에 맞지 않을 때 페이지 일부 공간을 사용하지 않음
  • 하지만, LSM은 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하기 때문에 저장소 오버헤드가 낮음

LSM 트리의 단점

• 컴팩션 과정이 때로는 진행중인 읽기와 쓰기의 성능에 영향을 줌

  • 저장소 엔진은 컴팩션을 점진적으로 수행하고 동시 접근의 영향이 없게 수행하려함
  • 하지만 디스크가 가진 자원의 한계로 비싼 컴팩션 연산이 끝날 때까지 요청이 대기애햐하는 상황이 발생함

• 디스크 쓰기 대역폭의 한계

  • 디스크 쓰기 대역폭은 유한하고, 초기에 로깅,멤테이블을 디스크로 flush하는 것과 백그라운드에서 수행하는 컴팩션 스레드는 이 대역폭을 공유함
  • 빈 데이터베이스는 전체 디스크 대역폭을 초기 쓰기만을 위해 사용할 수 있지만, 커질수록 컴팩션을 위해 더 많은 디스크 대역폭이 필요함

• 컴팩션이 늦어져 디스크 공간 부족해질 수 있음

• B트리의 장점은 각 키가 색인의 한곳에만 정확하게 있다는 점
• 반면, 로그 구조화 저장소 엔진은 다른 세크먼트에 같은 키의 다중 복사본이 존재할 수 있음

  • 그래서 강력한 트랙잭션이 요구되는 상황에서는 B트리가 더 유용함