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

데이터 중심 애플리케이션 설계를 독파하며 정리하는 글입니다.

---

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

세상에서 제일 간단한 데이터베이스를 구현해 보자.

#!/bin/bash

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

db_get () {
	grep "л$1," database | sed -e "s/A$1,//" | tail -n 1
}

키-값 저장소를 함수 두 개로 구현한 예시이다.

 

이런 방식으로 데이터베이스를 구성할 경우 db_set()은 좋은 성능을 보인다.

단순히 파일의 끝에 데이터를 추가해 주기만 하기 때문이다.

실제로 많은 데이터베이스의 로그는 이런 append-only 방식의 데이터 파일을 사용한다.

 

다만, db_get()의 경우 문제가 있다.

데이터베이스에 많은 레코드가 존재할 경우 키를 찾을 때 걸리는 비용이 O(n)이다.

데이터베이스의 레코드 수가 두 배로 늘면 검색도 두 배 오래 걸린다는 소리이다.

따라서, 이는 바람직하지 않은 구조이다.

 

이를 효율적으로 개선하기 위해서는 다른 데이터 구조가 필요하며, 그것이 바로 색인이다.

색인의 일반적인 개념은 부가적인 메타데이터를 유지하는 것이며, 이것이 이정표역할을 함으로써 데이터의 위치를 찾는데 도움을 준다.

그러나 색인에도 트레이드오프가 존재하는데 색인을 잘 선택한다면 읽기 속도가 향상되겠지만, 반대로 쓰기 속도는 떨어지게 된다.

이런 이유로 인해 데이터베이스는 보통 자동으로 모든 것을 색인하지 않으며 우리 같은 애플리케이션 개발자나 데이터베이스 관리자가 수동으로 색인을 선택한다. (색인으로 인한 오버헤드를 방지하기 위해)

 

해시 색인

키-값 저장소는 대부분의 프로그래밍 언어에서 볼 수 있는 사전 타입(dictionary type)과 유사하다.

보통 해시 맵(hash map), 해시 테이블(hash table)로 구현한다.

 

키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 유지할 수 있다.

값을 조회할 시 해시 맵을 이용 해 데이터 파일에서 오프셋을 찾아 해당 위치를 구하고 값을 읽는다.

참조 : https://ebrary.net/64644/computer_science/hash_indexes#101

이 방식은 단순하지만 실제로 많이 사용하는 접근법이지만, 파일에 항상 추가만 하게 되면 결국 디스크 공간이 부족해진다.

이는 특정 크기의 세그먼트로 로그를 나누는 방식을 사용하며, 특정 크기에 도달할 시 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행한다.

또한, 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 컴팩션(compaction) 작업을 수행한다.

 

이러한 해시 색인도 물론 제한 사항이 있다.

• 해시 테이블을 메모리에 저장해야 하므로 키가 너무 많으면 문제가 발생한다. 디스크에 해시 맵을 유지할 수 있긴 하지만 성능이 좋지 않고, 무작위 접근 I/O가 많이 필요하며 디스크가 가득 찼을 때 확장하는 비용이 비싸다. 또한 해시 충돌을 막기 위해 별도의 로직이 필요하다.
• 범위 질의(range query)에 효율적이지 않다. 예를 들어 member0001 ~~ member0100 사이의 모든 키를 쉽게 스캔할 수 없다.

 

SS테이블과 LSM 트리

각 로그 구조화 저장소 세그먼트는 키-값쌍의 연속이며, 순차적으로 데이터가 생성되므로 뒤늦게 들어온 값이 최신 값이다.

이 세그먼트 파일의 형식에 키-값 쌍을 키로 정렬하게 되면 정렬된 문자열 테이블(Sorted String Table, SS테이블)이라 부른다.

 

순차적으로 로그를 쌓기 때문에 정렬이 불가능할 것 같지만 가능하며, 이 SS테이블은 해시 인덱싱을 가진 로그 세그먼트보다 키가 존재할 범위를 예상하고 해당 영역에서만 값을 조회하여 찾을 수 있다는 큰 장점이 있다.

 

SS테이블 생성과 유지

유입되는 쓰기는 임의 순서로 들어오는데 데이터를 키로 정렬하려면 어떻게 해야 할까?

디스크에 정렬된 구조를 유지하는 일은 가능하지만(B-tree), 메모리에 유지하는 편이 훨씬 쉬우며(레드 블랙 트리, AVL 트리) 이런 데이터 구조를 이용하면 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 다시 조회할 수 있다.

 

저장소 엔진의 동작 방식은 다음과 같다.

• 쓰기 요청이 들어오면 인메모리 균형트리 데이터 구조(레드 블랙트리, AVL 트리)에 추가한다. (멤테이블, Memtable이라고도 함.)
• 새로운 SS테이블 파일은 DB에서 가장 최신 세그먼트가 되고 SS테이블을 디스크에 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록한다.
• 읽기 요청을 제공하려면 먼저 멤테이블에서 키를 찾는다. 그다음 디스크 상의 가장 최신 세그먼트 -> 두 번째 -> N 번째 세그먼트 순서로 찾는다.
• 그리고 중간중간 백그라운드로 병합과 컴팩션을 수행한다.

 

허나 한 가지 문제가 있는데, 만약 DB가 고장 나면 아직 디스크에 기록되지 않고 멤테이블에 존재하는 가장 최신의 쓰기가 손실된다.

이러한 문제를 피하기 위해 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지해야 한다.

(이 로그는 손상 후 멤테이블을 복원할 때만 필요하기 때문에 순서가 정렬되지 않아도 문제 되지 않으며, 멤테이블을 SS테이블로 기록하고 난 후 해당 로그를 삭제한다.)

 

또한 위 알고리즘으로 동작하는 색인 구조를 로그 구조화 병합 트리(Log-Structured Merge-Tree, LSM트리)라고 한다.

 

성능 최적화

LSM 트리 알고리즘은 DB에 존재하지 않는 키를 찾는 경우 느릴 수 있는데, 만약 키가 존재하지 않으면 멤테이블을 확인한 후 가장 오래된 세그먼트까지 거슬러 올라가야 하기 때문이다.

이런 종류의 접근을 최적화하기 위해 보통 블룸 필터(Bloom Filter)를 추가로 사용한다.

이 블룸 필터는 키가 DB에 존재하지 않음을 알려줘서 불필요한 디스크 읽기를 절약할 수 있다.

 

B 트리

LSM 트리가 점점 보편화되고 있지만, 가장 널리 사용되는 색인 구조는 B 트리(B-tree)이다.

1970년대에 등장해 거의 대부분의 관계형 데이터베이스에서 표준 색인 구현으로 B 트리를 사용할 뿐 아니라 많은 비관계형 데이터베이스에서도 사용한다.

 

B 트리는 SS테이블처럼 키로 정렬된 키-값 쌍을 유지하므로, 검색과 범위 질의에 효율적이지만 이 점을 제외하곤 비슷한 점이 없으며 설계철학이 매우 다르다.

B 트리는 고정 크기 블록으로 배열된 디스크에 전통적으로 4KB의 고정 크기 페이지로 나누고 한 번에 하나의 페이지에 읽기 쓰기 작업을 한다. (근본적으로 하드웨어와 밀접한 관계가 있다.)

참조 : https://ebrary.net/64649/computer_science/trees#689

각 페이지는 주소나 위치를 이용해 식별이 가능하며, 하나의 페이지가 다른 페이지를 참조한다.

그중 맨 위 페이지가 루트(root)로 지정되고, 여러 키와 하위 페이지의 주소 값을 포함한다.

B 트리는 계속 균형을 유지함을 보장하며, n개의 키를 가진 B 트리는 깊이가 항상 O(log n)이다.

대부분의 데이터베이스는 깊이가 3이나 4단계 정도면 충분하므로 많은 페이지 참조를 따라가지 않아도 된다.

(분기계수가 500인 4KB 페이지의 4단계 트리는 256TB까지 저장할 수 있다.)

 

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

B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓴다.

이 동작은 덮어쓰기가 페이지 위치를 변경하지 않는다고 가정하며, 페이지를 덮어쓰더라도 페이지를 가리키는 모든 참조가 유지된다.

(LSM 트리와는 대조적으로, LSM 트리는 파일에 추가만 할 뿐 같은 위치의 파일은 변경하지 않는다. 또한 합병과 컴팩션을 거치며 특정 키의 주소가 지속적으로 변경될 수 있다.)

 

B 트리 구조의 DB가 고장 난 상황에서 스스로 복구할 수 있게 만들려면, 일반적으로 디스크 상에 쓰기 전 로그(Write-ahead log, WAL)라고 하는 데이터 구조를 추가해 B 트리를 구현한다.

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

그래서 DB가 고장 난 이후 복구할 시 일관성 있는 B 트리로 복원하는 데 사용한다.

 

복구 시 주의 사항이 몇 가지 있는데, 같은 자리의 페이지를 갱신하는 작업은 쉽지가 않다. 특히, 다중 스레드 접근이 가능하다면 동시성 제어까지 해야 한다. (그렇지 않으면 일관성이 깨진 상태의 데이터를 가진 B 트리에 접근되므로)

그래서 동시성 제어는 래치(latch)로 데이터 구조를 보호한다.

이에 반해 로그 구조화 접근 방식은 훨씬 간단한데, 유입 질의의 간섭 없이 백그라운드에서 모든 병합을 수행한 후 새로운 세그먼트를 이전 세그먼트로 바꾸면 그만이기 때문이다.

 

B 트리와 LSM 트리 비교

읽기 속도 : B 트리 > LSM 트리
쓰기 속도 : B 트리 < LSM 트리

B 트리가 LSM 트리에 비해 읽기가 빠른 이유는 LSM 트리는 컴팩션 단계에 있는 여러 데이터 구조와 SS 테이블을 확인하는데 비용이 들기 때문이다. (하지만 실제 다루는 데이터마다 성능이 달라질 수 있으므로 시스템 부하 테스트 후 선정하는 것이 좋다.)

 

LSM 트리의 장점은 다음과 같다.

• 쓰기 증폭 (DB 쓰기 요청 1번을 수행할 때 디스크에 N번 작업이 수행되는 효과)
  • B 트리 인덱스는 모든 데이터 조작을 최소 2번 기록해야 한다. (쓰기 전 로그 1번 + 트리 페이지에 1번)
  • 또한, 페이지 내 몇 바이트만 변경이 일어나더라도 한 번에 전체 페이지를 기록해야 하는 오버헤드도 존재한다.
  • SSD의 경우 수명이 다할 때까지 블록 덮어쓰기 횟수가 제한되므로 이 쓰기 증폭이 큰 관심사이다.
  • 쓰기가 많은 어플리케이션에 성능 병목은 DB가 디스크에 쓰는 속도 일 수도 있으며 이 경우 쓰기 증폭이 성능 비용이 된다.
  • LSM 트리 또한 SS테이블의 반복된 컴팩션과 병합으로 인해 N번 데이터를 다시 쓰긴 한다.
• 쓰기 처리량
  • LSM 트리가 B 트리에 비해 상대적으로 쓰기 증폭이 더 낮고, 트리에서 페이지를 덮어쓰는 것이 아닌 순차적으로 컴팩션된 SS테이블을 쓰기 때문이다.
  • HDD에서 특히 중요한데 HDD에 데이터를 기록할 때 순차 쓰기가 임의 쓰기보다 훨씬 빠르다
• 압축률
  • LSM 트리는 페이지 지향적이지 않고 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하므로 저장소 오버헤드가 더 낮다.

 

LSM 트리의 단점은 다음과 같다.

• 컴팩션 과정
  • 컴팩션 과정이 때로는 진행 중인 읽기 쓰기 작업의 성능에 영향을 준다. (디스크에서 컴팩션 연산이 끝날 때까지 요청을 기다려야 하는 상황이 발생하기 쉬움)
• 높은 쓰기 처리량
  • 디스크의 쓰기 대역폭은 유한한데, 쓰기 처리량이 높아 DB가 점점 커질수록 컴팩션을 위해 더 많은 디스크 대역폭이 필요하게 된다.
• 컴팩션 설정
  • 컴팩션 설정을 주의 깊게 하지 않으면 컴팩션이 쓰기 요청 속도를 못 따라간다.
  • 보통 SS테이블 기반 저장소 엔진은 컴팩션이 유입 속도를 따라가지 못해도 유입 쓰기의 속도를 조절하지 않기에, 이런 상황을 감지하기 위한 명시적 모니터링이  필요하다.

 

기타 색인 구조

키-값 색인의 대표적인 예는 관계형 모델의 기본키(primary key) 색인이다.

기본키로 관계형 테이블에서 하나의 로우를, 문서 데이터베이스에서 하나의 문서를, 그래프 데이터베이스에서 하나의 정점을 고유하게 식별할 수 있다.

 

보조 색인(secondary index)을 사용하는 방식도 일반적이다.

보조 색인은 보통 효율적인 조인을 수행하는데 도움을 주며, 기본키 색인과의 주요 차이점은 키가 고유하지 않다는 점이다.

 

인덱스 안에 값 저장하기

인덱스에서 키는 검색하려는 대상이지만 값은 둘 중 하나인데,

실제 데이터이거나 실제 데이터가 위치한 로우를 가리키는 참조 값이다.

후자의 경우 로우가 저장된 곳을 힙 파일(heap file)이라고 한다.

 

힙 파일의 접근 방식은 키를 변경하지 않고 값을 갱신할 때 효율적이며, 새로운 값이 많은 공간을 필요로 하지 않으면 제자리에 덮어쓰고 그렇지 않다면 힙에서 충분한 공간이 있는 새로운 곳으로 위치를 이동시킨 후 변경된 값과 관련이 있는 참조 값들을 모두 새로운 위치를 가리키도록 수정한다.

 

• Clusterd Index : 인덱스의 값을 읽고 다시 힙 파일로 가는 것은 읽기 성능이 떨어진다. 그래서 인덱스 값으로 찾고자 하는 로우 자체를 저장하기도 하며 이를 클러스터드 색인(Clustered Index)이라고 한다. (MySQL의 InnoDB 저장소 엔진에서는 테이블의 기본키가 Clustered Index이다.)
• Covering Index : 클러스터드 색인과 비클러스터드 색인 사이의 절충안으로 색인 안에 테이블의 컬럼 일부를 저장한다. 이렇게 하면 색인만 사용해 일부 질의를 처리할 수 있어지고 이런 경우를 "인덱스가 질의를 커버했다"라고 표현한다.

 

다중 컬럼 색인

하나의 키만 가진 색인이 아닌 여러 개의 키를 가진 색인이다.

 

• Concatenated Index : 가장 일반적인 유형인 결합 색인이다. 하나의 컬럼에 다른 컬럼을 추가하는 방식으로 하나의 키에 여러 필드를 결합한다.  이 방법은 키를 성과 이름값을 전화번호로 하는 색인을 제공하는 전화번호부와 비슷하다. (특정 성 이름 조합을 가진 사람을 찾을 때 유용하지만, 특정 이름을 가진 모든 사람을 찾을 때는 쓸모가 없다.)
• Fuzzy Index : 여타 다른 색인들처럼 정확한 데이터를 대상으로 질의하는 것이 아닌 철자가 틀린 단어처럼 애매모호한(fuzzy) 질의를 하는 색인이다. 트라이(Trie) 자료구조와 유사하다.

 

모든 것을 메모리에 보관(인메모리)

지금껏 언급한 데이터 구조는 디스크의 한계에 대한 해결책이었다.

디스크는 메인 메모리와 비교해 다루기 어려우며 HDD 혹은 SSD 사용 시 읽기/쓰기 작업에서 좋은 성능을 위해 디스크에 데이터를 잘 배치해야 한다.

이렇게 까다로운데도 불구하고 디스크를 사용하는 이유로는 다음과 같다.

1. 지속성 (전원이 꺼져도 손실되지 않음)
2. 저렴한 가격

그러나, 요즘 들어 램 가격이 저렴해지면서 메모리에 데이터를 저장하는 방식도 현실적으로 가능해졌고, 인메모리 DB가 개발되기 시작했다.

 

인메모리 DB의 장점은 다음과 같다.

• 디스크에서 데이터를 읽지 않아도 된다. (하지만 디스크 기반 저장소 엔진도 OS가 최근에 사용한 디스크 블록을 메모리에 캐시 하며, 오히려 인메모리 데이터 구조를 디스크에 기록하기 위한 형태로 부호화하는 오버헤드를 피할 수 있어 더 빠를 수도 있다.)
•  Priority Queue, Set과 같이 디스크 기반 색인으로 구현하기 어려운 데이터 모델을 제공한다. (Redis)

 

인메모리 DB의 단점은 다음과 같다.

• DB가 재시작되는 경우 특수한 하드웨어를 사용하지 않는다면 디스크나 복제본에서 데이터를 다시 인메모리에 적재해야 한다.