[데이터 중심 애플리케이션 설계] 3장 - 저장소와 검색

• 데이터베이스가 데이터를 저장하는 방법과 데이터를 요청했을 때 다시 찾는 방법을 알아보자.
• 애플리케이션에 적합한 엔진을 선택하려면 저장소 엔진 내부에서 일어나는 일을 대략적으로라도 알아야한다.

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

• 로그(log) : append-only 데이터 파일. 일반적으로 파일 추가 작업은 매우 효율적이다.
• 로그에서 데이터를 찾으려면 모든 데이터를 뒤져야하므로 검색 비용은 O(n)이다. 데이터가 많아질수록 검색도 오래 걸리므로 바람직 하지 않다. 그래서 필요한 것이 색인이다.
• 색인(index) : 특정 키의 값을 효율적으로 찾기 위한 데이터 구조
• 색인은 읽기 질의 속도를 향상시키지만 쓰기 속도를 떨어뜨린다. (trade-off) 그래서 데이터베이스가 모든 데이터를 자동으로 색인하지 않고 사람이 질의 패턴을 파악해서 수동으로 가장 효율적인 색인을 지정한다.

해시 색인

• 키-값 데이터를 색인하기 위함
• 인메모리에 디스크 상의 데이터를 색인한 데이터 구조를 저장
  • 가장 간단한 전략 : 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리에 해시 맵을 유지하는 방법
    • 매우 단순해 보이지만 실제로 많이 사용. (Bitcask)
    • Bitcask는 RAM에 모든 키가 저장된다는 조건을 전제로 고성능으로 읽기, 쓰기를 보장함
    • 각 키의 값이 자주 갱신되는 상황에 매우 적합 (ex. key가 동영상URL, value가 동영상 재생된 횟수인 경우)
• log에 append만 하면 결국 디스크 공간이 부족해지지 않나?
  • 해결 방법 : 로그를 특정 크기의 세그먼트로 나누는 방식
    • 세그먼트가 특정 크기에 도달하면 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행한다.
    • 파일이 닫힌 세그먼트 파일들에 대해 컴팩션을 수행한다. (중복된 키를 버리고 키의 최신 값만 유지하는 것)
    • 컴팩션을 통해 세그먼트 파일이 작아지면 여러 세그먼트 파일을 하나의 세그먼트로 병합도 가능함 (세그먼트 크기는 가변적이게 됨)
    • 컴팩션과 병합은 백그라운드 스레드에서 수행할 수 있음
• 이제 각 세그먼트는 키와 바이트 오프셋이 매핑된 자체 인메모리 해시 테이블을 갖는다.
  • 키에 값을 찾을 때 가장 최신 세그먼트 해시 맵을 뒤지고 없으면 그 다음 최신 세그먼트의 해시 맵을 뒤진다. 이것을 키가 발견될 때까지 반복한다.
  • 컴팩션와 병합에 의해 세그먼트 수는 적게 유지되므로 뒤져야할 해시 맵도 많지 않다.
  • 이를 실제 구현할 때 고려해야될 사항 중에 일부 중요한 점들
    • 파일 형식 : 텍스트 형식보다 바이너리 형식이 낫다
    • 레코드 삭제 : tombstone이 필요함
    • 고장(crash) 복구 : 데이터베이스가 재시작되면 인메모리 해시 맵은 날라가는데 이를 어떻게 복구할 것인가? 다시 해시 맵을 만들려면 오랜 시간이 걸릴 수도 있다. Bitcask는 해시 맵의 스냅숏을 디스크에 저장해 복구 속도를 높인다.
    • 부분적으로 레코드 쓰기 : ?
    • 동시성 제어 : 쓰기는 하나의 스레드만 사용 (순차적으로 로그를 추가해야하므로). 읽기는 다중 스레드 사용 가능 (세그먼트는 추가 전용이거나 불변이므로).
• ‘추가 전용 로그’의 이점
  • 순차 쓰기 작업이 무작위 쓰기 작업보다 훨씬 빠름
  • 동시성과 고장 복구 간단함 : 세그먼트가 추가 전용이거나 불변이고, 이전 값과 새로운 값을 둘다 가지고 있기 때문
  • 세그먼트 병합을 통해 데이터 파일의 조각화 문제를 피할 수 있음
• ‘해시 색인’의 제한 사항
  • 메모리 크기 이상으로 키가 너무 많으면 문제
    • 메모리가 부족해서 디스크에 해시 맵을 저장하게되면 성능이 매우 떨어지게 된다.
  • 해시 테이블은 range query에 효율적이지 않음 : range 내의 모든 키를 조회해야함

SS테이블과 LSM 트리

• 위에서 얘기한 해시 색인의 제한 사항을 극복해보자.
• 세그먼트 파일에 기록된 키-값 쌍을 키로 정렬하자. 키로 정렬된 형식을 SS테이블 (Sorted String Table) 이라고 한다.
• SS테이블은 순차 쓰기를 사용할 수 없게 만드는 것 같지만 아니다! 여전히 순차 쓰기를 유지할 수 있다. (뒤에서 살펴보자)
• 해시 색인을 가진 로그 세그먼트보다 SS테이블이 나은 점
  • 세그먼트 병합이 효율적 : 머지 소트 알고리즘과 유사
  • 해시 테이블에 모든 키를 유지하지 않아도 됨 : 세그먼트 파일 내부는 정렬되어 있으므로 몇몇 키의 오프셋만 알면 약간의 탐색만으로 키-값을 찾을 수 있다.
  • 세그먼트 내의 레코드들을 블록으로 그룹화하고 디스크에 쓰기 전에 압축할 수 있음. 해시 색인에서는 이 블록의 시작 오프셋을 가리키게 됨. 압축을 통해 디스크 공간 절약이 절약되고 I/O 대역폭 사용도 줄임

여러 SS테이블 세그먼트를 병합해서 각 키의 최신 값만을 유지

인메모리 색인을 가진 SS테이블

• 순차 쓰기를 사용하면서 SS테이블을 유지하려면 어떻게 해야할까?
  • 쓰기가 들어오면 세그먼트 파일에 기록하는 것이 아니라 인메모리 균형트리 데이터 구조에 추가. 이 인메모리 트리는 멤테이블(memtable)이라고도 함
  • 멤테이블의 크기가 임계값보다 커지면 SS테이블 파일로 디스크에 기록
  • 읽기 요청이 들어오면 먼저 멤테이블에서 키를 찾고 없으면 디스크 상의 가장 최근 세그먼트부터 찾는다.
  • 백그라운드에서는 세그먼트 파일의 컴팩션과 병합이 수행된다.
  • 갑자기 데이터베이스가 고장났을 때 멤테이블이 날아갈 수도 있지 않나? -> 쓰기 요청을 별도의 로그로 디스크에 저장해야함
• 위의 알고리즘은 LevelDB, RocksDB, 카산드라, HBase 등에서 사용된다.
• LSM 트리 (Log-structured Merge-tree) : “로그 구조화 병합 트리”. 정렬된 파일 형합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라고 부름
• Lucene에서 term dictionary를 저장하기 위해 유사한 방법을 사용함. key=term, value=term을 포함한 모든 문서의 ID 목록
• LSM 저장소 엔진의 성능 최적화
  • 존재하지 않는 키를 찾기 위해 가장 오래된 세그먼트까지 조회해야하는 문제 : 블룸 필터 적용하여 최적화
  • SS테이블을 컴팩션하고 병합하는 전략 : 1) 크기 계층, 2) 레벨 컴팩션
• LSM 트리의 장점
  • 범위 질의를 효율적으로 할 수 있음
  • 여전히 디스크 순차 쓰기 가능하여 높은 쓰기 성능

여기까지 내 나름대로 정리를 다시 해보자.

• 버전1) 세그먼트 단위의 로그 파일 (키 기준으로 정렬되어있지 않음) + 각 세그먼트 별로 인메모리 해시 색인 (세그먼트의 모든 키를 저장) + 백그라운드 컴팩션 및 병합
  • 버전1의 문제점은 메모리에 모든 키에 대한 해시 색인을 올려야한다는 점. 또한 범위 질의에 비효율적이라는 점이 있다. 이를 극복하기 위해 버전2인 LSM 트리가 나왔다.
• 버전2 = LSM 트리) 멤테이블 (세그먼트를 디스크에 쓰기 전에 정렬된 순서로 담아두는 자료구조) + 세그먼트 단위의 로그 파일 (= SS테이블, 키 기준으로 정렬되어 있음) + 각 세그먼트 별로 인메모리 해시 색인 (세그먼트의 모든 키를 저장하지 않고 블록 단위의 시작점이 저장된다)
  • 읽기는 멤테이블 -> 세그먼트 인메모리 해시 색인 -> 세그먼트 파일 읽기 순으로 이루어짐
• SS테이블은 디스크에 저장되는 파일일 뿐이다.
  • key-value 데이터가 key 기준으로 정렬되어 저장됨
  • index도 포함하고 있음 (key:offset)
• LSM 트리에서 디스크 컴포넌트 구현체 중에 하나가 SS테이블인 것이다.

B 트리

B 트리 색인을 이용한 키 검색

• 가장 널리 쓰이는 보편적인 색인 구조임
• LSM 트리와 설계 철학이 매우 다름
• LSM과 달리 고정 크기의 블록이나 페이지 단위로 읽고 쓴다. 디스크도 고정 크기 블록으로 배열되어 있기 때문에 하드웨어와 좀더 밀접하다고 할 수 있음
• 개념들 : root, leaf page, branching factor
• 신뢰할 수 있는 B 트리 만들기
  • LSM 트리와 다르게 새로운 데이터를 디스크 상의 페이지에 덮어 쓴다. (덮어 쓰기를 하면 이 페이지를 참조하는 위치 값을 바꿀 필요 없음)
  • 덮어쓰기하다가 데이터베이스가 고장나면? 고아 페이지가 생길 수도 있다. (부모가 없는 페이지)
    • 쓰기 전 로그(write-ahead log, WAL) 혹은 재실행 로그(redo log)를 유지하여 해결한다. 이를 이용해 고장 이후 복구한다.
  • 동시성 제어 : LSM 트리보다 까다롭다. 같은 자리의 페이지를 갱신하는 작업이 다중 스레드로 동시에 이루어질 수 있는 위험이 있다. 보통 latch로 트리의 데이터 구조를 보호한다.
• B 트리 최적화 하기
  • WAL 대신에 copy-on-write 사용
  • 페이지에 키 전체를 저장하는 대신 키를 추적해서 저장 (B+ 트리)
  • 리프 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리를 배치 -> 하지만 트리가 커지면 순서를 유지하기 어려움
  • 리프 페이지가 양쪽 형제 페이지의 참조를 가지게 하기 (상위 페이지로 다시 이동하지 않아도 순서대로 키를 스캔할 수 있음)
  • 프랙탈 트리 같은 B 트리 변형 사용

B 트리와 LSM 트리 비교

• 경험적으로 LSM 트리는 보통 쓰기에서 더 빠르고, B 트리는 읽기에서 더 빠르다고 여김
• 경험적으로 그렇다는 것이고 실제 작업 부하를 가지고 테스트하는게 제일 정확하다.
• LSM 트리 장점 (B 트리 단점)
  • “쓰기 증폭” 개념 : 데이터베이스에 쓰기 한 번에 데이터베이스 수명 동안 여러 번의 쓰기를 야기하는 효과
  • B 트리는 한 번 쓰기 작업에 최소한 두 번 기록해야함 (WAL에 한번, 트리 페이지에 한번). 또한 페이지 내에 몇 바이트만 바뀌어도 페이지 전체를 덮어써야함
  • LSM 트리가 상대적으로 쓰기 증폭이 더 낮고 디스크에 순차적으로 쓰기 때문에 보통 B 트리보다 쓰기 처리량이 높음
  • LSM 트리는 압축률도 더 좋음. 파편화도 덜 발생함
  • 낮은 쓰기 증폭과 파편화 감소는 SSD의 경우 훨씬 유리함
• LSM 트리 단점 (B 트리 장점)
  • 컴팩션 과정이 때로 읽기와 쓰기 성능에 영향을 줌
    • 컴팩션이 끝날 때까지 요청을 대기해야 하는 상황이 발생하기 쉬움
    • 반면 B 트리의 성능은 예측하기 쉽다
    • 컴팩션의 높은 쓰기 처리량 때문에 로깅이나 멤테이블을 디스크로 쓰는 작업에 영향을 준다.
    • 컴팩션이 유입 쓰기 속도를 따라가지 못하는 상황이 발생할 수 있음
      • 이런 상황을 감지하기 위한 명시적 모니터링이 필요함
  • B 트리의 장점
    • 키가 색인의 한 곳에만 정확하게 존재함
      • 덕분에 강력한 트랜잭션 시멘틱을 제공할 수 있게 됨 (트리에 직접 잠금)
    • 역사가 이미 깊고 많은 작업 부하에 대해 지속적으로 좋은 성능을 제공해왔으므로 곧 사라질 가능성은 거의 없음

느낀 점

• 데이터베이스 엔진의 내부 구조를 이렇게 깊게 공부해본 것이 처음이어서 흥미로웠다. 그리고 이러한 내부 구조도 모르고 여태까지 데이터베이스를 써온 것이 민망해졌다.
• 내부 데이터 구조의 발상 자체는 심플하지만 신경 써야할 세부 구현이 엄청 많은 것을 알게 되었다. (동시성, 장애 복구, 디스크 I/O 성능 등)
• 로그 하면 애플리케이션 로그만 떠올렸는데 로그가 데이터베이스의 핵심이라는 것을 알게 되었고, 로그의 강력함을 알게 되었다.
• RDB를 쓰든 NoSQL을 쓰든 내부 동작 방식을 이해하는 것이 매우 중요함을 알게 되었다. 내부 동작 방식을 이해해야만 작업 부하에 적합한 데이터베이스를 선택할 수 있기 때문이다. 역시 기초가 제일 중요하다!