간단한 데이터베이스를 생각해보자.
set 함수에 키와 값을 요청하면 차곡차곡 저장하고, get 함수에 키를 담아 요청하면 저장된 값을 반환하는 간단한 구조이다.
set 10 { "name": "noose" }
set 20 { "name": "google" }
set 30 { "name": "naver" }
10 { "name": "noose" }
20 { "name": "google" }
30 { "name": "naver" }get 30
# { "name": "naver" }
append-only 방식으로 간단하게 동작하기에 저장 시 큰 문제가 없다.
하지만, 특정 키의 값을 찾을 때 첫번째 라인에서 원하는 키가 나올 때 까지 탐색을 하므로 최악의 경우 검색 비용은 O(N)이다.
저장되는 레코드가 증가할 때 마다 검색도 오래걸리게 되므로, 다른 데이터 구조가 필요하다.
바로 그것이 색인이다.
색인
색인은 데이터의 위치를 찾는 데 도움을 주는 이정표 역할을 한다.
데이터베이스의 내용에는 영향을 미치지 않는 추가적인 구조이다.
이러한 색인은 내가 원하는 데이터의 위치를 빠르게 탐색할 수 있어 조회 성능을 증가시키지만, 쓰기 성능을 저하하게 만든다.
데이터를 쓸 때마다 매번 색인도 갱신해야 하기 때문인데 이러한 점은 저장소 시스템에서 중요한 트레이드오프이다.
해시색인
디스크에 저장되는 키의 위치(offset)을 인메모리에 저장하고 값을 읽는 구조이다.
대부분 프로그래밍 언어에서 볼 수 있는 맵(Map), 사전(dictionary type)과 유사하다.
조회수를 기록하는 시스템에서 키당 쓰기 수가 많은 것 처럼 키가 가진 값이 자주 갱신되는 상황에 적합하다.
1000게시글 1
1000게시글 2
2000게시글 501
1000게시글 3
2000게시글 502
2000게시글 503
1000게시글 4
...
그러나 모든 키를 계속해서 메모리에 보관할 수 없고, 파일에 항상 추가만 하는 것은 디스크 공간이 부족해지는 문제를 야기한다.
이 상황을 피하는 방법이 존재하는데
특정 크기의 세그먼트(segment)로 나누고, 최신 갱신 값만 유지하는 컴팩션(compaction)을 수행하는 것이다.
# segment-1 작업
1000: 1|1000: 2|2000: 501|1000: 3
# segment-2 작업
2000: 502|2000: 503|1000: 4|...
# segment 1, 2 컴팩션
1000: 4|2000: 503각 키의 최신 값만을 유지시켜 새로운 파일을 만든다.
병합 과정이 끝나 파일을 성공적으로 만들게되면 이전 세그먼트 파일들은 간단히 삭제하면 된다.
이러한 세그먼트가 지속적으로 생성되고, 값을 탐색할 때 세그먼트 단위로 찾게된다.
첫 번째 세그먼트에 값이 없으면 두 번째 세그먼트를 확인하는 비효율적인 문제는 있지만 일단은 넘어가자.
일단 주기적인 컴팩션 작업으로 인해 세그먼트들은 줄어들기 때문에 조회 시 많은 해시 맵을 확인할 필요는 없게된다.
실제로 위 방식을 구현하기 앞서 여러가지 고려해야 할 사항은 있다.
- 레코드 삭제: 데이터 삭제 시 데이터가 삭제되었음을 나타내는 마킹 처리(tombstone)를 하고 병합 과정에서 마킹된 값은 무시처리한다.
- 고장 복구: 데이터베이스가 재시작되면 메모리 맵은 손실된다. 스냅샷을 디스크에 저장시켜 복구할 수 있는 수단이 존재해야 한다.
- 부분적으로 레코드 쓰기: 레코드가 추가하는 도중 종료될 수 있으니, 로그의 손상 부분을 탐지해 무시해야 한다.
- 동시성 제어: 한 공간에 순차적으로 로그를 추가하기 때문에 하나의 쓰기 스레드만 사용하도록 제한해야 한다.
SS(Sorted String) 테이블 / LSM(Log-Structured Merge) 트리
위에서 설명한 방식에서 키로 정렬된 기능을 추가한다고 하자
키로 정렬된 형식을 정렬된 문자열 테이블인 SS(Sorted String) 테이블이라 부른다.
전 해시 맵 구조에서는 키가 정렬되어 있지 않아 범위 탐색에서 성능이 좋지 않지만,
SS 테이블은 키가 정렬되어 있어 범위 탐색이 가능한 큰 장점이 있다.
그렇다면 키를 정렬된 상태로 어떻게 유지하는지 알아보자
AVL로 잘 알려진 레드 블랙 트리, B 트리 같은 자료 구조로 정렬된 순서를 보장할 수 있다.
- 쓰기가 들어오면 인메모리 AVL 데이터 구조에 추가한다. 이런 데이터 구조를 멤테이블(memtable)이라고도 한다.
- 멤테이블이 커지면 SS 테이블 파일로 디스크에 기록한다. 이미 정렬된 상태로 저장했기 때문에 추가 정렬이 필요하지 않다.
- 새로운 SS 테이블은 가장 최신 세그먼트가 된다.
단, 아직까지 문제가 존재한다.
만약 DB가 고장나면 디스크에 기록되지 않는 멤테이블이 휘발되므로 최신 쓰기 데이터들은 손실된다.
이런 문제를 피하기 위해 멤테이블에 작성되기 전 로그를 디스크 상에 유지해야 한다.
이 로그파일은 멤테이블을 복원하기 위한 파일이므로 정렬해야 할 의무는 없고, SS 테이블로 잘 기록되었다면 해당 파일은 버려도 된다.
지금까지 기술한 내용은 Cassandra와 HBase에서 유사하게 사용하고 있다.
정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라고 부른다.
LSM 성능 최적화
LSM 트리 알고리즘은 존재하지 않는 키를 찾는 경우 느릴 수 있다.
- 멤테이블을 확인한다.
- 값이 없으므로 최신 세그먼트를 찾는다.
- 값이 없으므로 다음 세그먼트들을 찾는다.
이러면 모든 세그먼트를 찾으면서 결국 디스크를 탐색하게 될 수 있다.
이런 종류의 접근을 최적화하기 위해 블룸 필터(Bloom filter)를 추가적으로 사용하여, 불필요한 디스크 읽기를 많이 절약할 수 있다.
또한, SS 테이블을 압추갛고 병합하는 순서와 시기를 정하는 다양한 전략이 있다.
일반적으로 크기 계층 컴팩션과 레벨 컴팩션이다.
HBase는 크기 계층 컴팩션을 지원하고, Cassandra는 둘 다 지원한다.
- 크기 계층 컴팩션: 상대적으로 새롭고 작은 SS 테이블을 상대적으로 오래됐고 큰 SS 테이블에 병합시킨다.
- 레벨 컴팩션: 키 범위를 더 작은 SS 테이블로 나누고 오래된 데이터는 개별 '레벨'로 이동한다.
B 트리
가장 널리 사용되는 인덱스 구조이다. 거의 모든 관계형 데이터베이스에서 표준으로 사용하고 있을 만큼 검증이 되어있다.
LSM는 세그먼트를 나누고 세그먼트를 기록하는 반면,
B 트리는 고정 크기의 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 한다.
B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상 페이지에 덮어쓴다.
페이지가 너무 많아져 페이지를 나눠야 한다면 두 페이지를 기록하고 하위 페이지의 참조를 갱신하게 끔 상위 페이지를 덮어쓰기 해야 한다.
이렇게 페이지를 기록하는 과정에서 일부 페이지만 기록하고 데이터베이스가 고장 나다면 색인도 함께 고장나므로 위험한 동작이다.
여기서 고장 상황에서 스스로 복구할 수 있게 만들기 위해
디스크에 쓰기 전 로그인 WAL(wirte-ahead-log), redo-log라고 하는 데이터 구조를 사용하고 있다.
동시성 제어는 보통 래치(latch)로 데이터 구조를 보호한다.
B 트리와 LSM 트리 비교
LSM은 쓰기 구조가 상대적으로 간단하기 때문에 더 빠른 반면,
B 트리는 성숙도 높은 색인 알고리즘으로 읽기에서 더 빠르다고 여긴다.
LSM 트리가 더 느린 이유는 컴팩션 과정에서 발생하는 SS 테이블을 확인해야 하기 때문이다.
기타 색인 구조
- 클러스터드 색인: 색인 안에 색인된 로우를 저장
- 넌클러스터드 색인: 기본키를 참조하는 인덱스
- 커버링 색인: 색인만 사용해 응답이 가능하다(색인만으로 질의를 커버)
- 결합 색인: 다중 컬럼에 동시에 질의할 때 사용
- 다차원 색인: 지리에 사용되는 좌표, 색(RGB) 같은 3차원 색인에 사용한다.
- 퍼지(fuzzy) 색인: 철자가 틀린 단어와 같이 유사한 키에 대해서 질의를 가능하게 한다. 트라이(trie)와 유사
인메모리
지금까지 설명한 데이터 구조는 모두 디스크 한계에 대한 해결책이었다.
데이터 셋이 크지 않다면 메모리에 전체를 보관하는 방식도 검토하는 것이 좋다. (램이 저렴해진 시점에서 꽤나 현실적이다.)
메모리에만 저장했다고 하여 무조건 휘발되지는 않는다.
일부 인메모리 데이터베이스는 지속성을 목표로 한다.
지속성을 달성하는 방법은 다양하다.
- 배터리 전원 공급 RAM 같은 특수 하드웨어 사용
- 디스크에 변경 사항의 로그를 기록
- 디스크에 주기적인 스냅샷을 기록
- 다른 장비에 인메모리 상태를 복제
주로 사용되는 Redis, Couchbase는 비동기로 디스크에 기록하기 때문에 약한 지속성을 제공하고 있다.
성능 이외에도, 인메모리 데이터베이스는 디스크 기반 색인으로 구현하기 어려운 자료구조를 제공한다.
예로 레디스는 우선순위 큐, Set 같은 다양한 데이터 구조를 데이터베이스와 같은 인터페이스로 제공하고 있다.
디스크가 아닌 메모리에서 데이터를 유지하기 때문에 구현이 비교적 간단하다.
나아가 비휘발성 메모리(non-voliatile memory, NVM) 기술이 더 널리 채택되면 저장소 엔진 패러다임이 변할 수 있다고 믿는다.
