데이터베이스에서 저장과 검색의 내부 구조

 

이 글은 데이터 중심 애플리케이션 설계 서적(마틴 클레프만 저)를 읽고 정리한 내용입니다.

데이터 중심 애플리케이션 설계 : 네이버 도서

 

 

 

데이터베이스의 트레이드오프

 

데이터베이스가 하는 일을 단순히 하면 데이터 저장과 그 데이터를 요청 시 반환하는 일이다.

특정 workload 유형에 좋은 성능이 나게끔 조정하려면 저장소 엔진의 대략적인 이해가 필요하다.

특히 트랜잭션 workload 최적화와 분석 workload최적화 엔진은 차이가 크다.

예를 들어 동영상 데이터에서의 재생 횟수와 같이, 키당 쓰기 수가 많다면 쓰기에 느린 설계는 좋지 않을 것이다.

 

일반적으로 파일 추가 작업은 매우 효율적이라서,

데이터베이스들의 log들은 append-only인 데이터 파일로 만들어진다.

 

데이터 베이스에서 수많은 레코드를 하나하나 스캔하는 것의 복잡도는 O(n)으로 당연히 비효율적이다.

이를 해결하기 위해 데이터베이스는 index를 사용한다.

이는 메타데이터로서 이정표의 역할을 한다.

많은 데이터베이스들이 추가적인 index의 추가와 삭제를 가능하게 한다.

이는 내용에는 변화가 없어도, 질의의 성능향상에 도움을 준다.

하지만 추가적인 구조들이 유지보수와 쓰기 과정에서 오버헤드를 발생시킨다.

 

이는 데이터베이스의 중요한 트레이드오프이다.

따라서 DB들이 모든 데이터에 색인을 붙이지는 않고, 관리자가 수동으로 설정을 해주어야 한다.

 

 

LSM(Log-Structured Merge) tree

Log-Structured Merge-Trees는 Update를 위치를 찾아 수행하지 않고 append 방식으로 진행한다.

이후 중복 쓰기 된 데이터를 한 번에 제거해 컴팩션 시켜서 write 성능이 빠르다.

로그 데이터에 write 정보들을 append로 빠르게 작성하고, 일정 크기를 넘어서면 이 변경사항들을 컴팩션 시켜주어 높은 쓰기 처리량을 자랑한다.

읽어오는 데에는 기본적으로 SS(Sorted String)와 같이 정렬된 인덱싱을 사용해서 빠르게 질의할 수 있다.

즉, 백그라운드에서 연쇄적으로 SS 테이블을 지속적으로 병합하는 방식이다.

 

 

B-Tree

가장 널리 사용되는 것은 사실 B트리 구조로 거의 대부분의 RDB와 비관계형 데이터베이스에서도 사용된다.

B-Tree는 C언어의 다중 포인터로 구현한 이진트리와 같이 범위를 빠르게 따라가서 최종적인 페이지 위치에 도달할 수 있다.

B-Tree는 균형을 항상 유지하기 때문 탐색의 시간복잡도는 O(logN)이다.

하지만 데이터를 덮어쓰는 형식이기 때문에 디스크 위치로 이동해야 하고 , SSD는 칩의 상당한 블록을 한 번에 지우고 다시 쓰기 때문에 더 복잡하다.

 

물론 범위에 대한 질의는 효율적이다.

 

 

 

어떤 것이 더 좋은가?

 

경험적으로는  LSM tree는 보통 쓰기에 빠르고 B-tree는 읽기에서 더 빠르다.

 

쓰기 작업이 많다면, 애플리케이션의 성능 병목지점은 데이터베이스 엔진이 디스크에 쓰는 속도일 것이다.

LSM이 이 부분에서는 B트리보다 쓰기 처리량을 높게 유지할 수 있다.

 

B트리는 데이터를 파편화하여 저장하기 때문에 남는 공간이 존재한다.

LSM은 컴팩션을 통해 파편화로 낭비되는 공간이 적다. 즉 압출률이 높다.

 

하지만, B트리는 포인터로 가리키는 색인의 한 곳에만 데이터가 정확히 존재한다. 따라서 강력한 트랙잭션 semantic을 제공한다.

 

 

 

인메모리

 

인메모리 데이터베이스들은 I/O의 오버헤드뿐만 아니라, 우선순위 큐와 같은 데이터 구조로 유지시킬 수 있다.

특히, 안티 캐싱을 통해서 메모리가 부족하면, 가장 오래된 메모리를 디스크에 적재시키는 방식으로 OS처럼 효율적으로 관리시킬 수 있다.

 

 

 

결국 엔지니어는 데이터베이스마다의 설계를 이해하고 workload에 적합한 데이터베이스를 선택해야한다.