데이터베이스를 지탱하는 기술 챕터 1, 2
데이터베이스가 없으면 무엇이 곤란한가?
빠른 검색
그냥 텍스트 파일이나 엑셀 파일을 쓰면 안되나? 일반 파일에서 원하는 데이터를 찾는 방법은 선형 검색 뿐이다. 선형 검색은 O(n)의 시간 복잡도를 가진다. 이런 애플리케이션은 데이터가 많아질 수록 요구사항을 만족하기 어려울 것이다. 이 문제를 해결하기 위해서 데이터베이스는 인덱스라는 고속 검색 방법을 사용한다.
영속성
데이터베이스를 사용하는 이유가 단지 인덱스를 이용하기 위해서라면, 프로그래밍 언어가 지원하는 해쉬 테이블 같은 자료구조를 이용할 수도 있을 것이다. 그러나 프로그래밍 언어는 기본적으로 메모리에서 작업을 진행한다. 메모리는 시스템에 이상이 생겼을 때 데이터를 보존하기 어렵다. 데이터베이스는 기본적으로 디스크에 쓰는 것을 기본으로 설계되어있으므로 이런 문제로부터 자유롭다.
장애 대응
그렇다면 메모리에 있는 데이터를 정기적으로 디스크에 쓰면 어떨까?
- 그래도 기록과 기록 사이의 데이터는 여전히 장애가 발생하면 사라진다.
- 게다가 기본적으로 디스크의 성능은 매우 낮고 심지어 데이터가 클 경우, 백업과 복구에 많은 시간이 걸리게 되고, 이는 다운 타임을 늘린다.
- 또, 백업이나 복구 중에 데이터 업데이트가 일어날 경우, 데이터에 손상이 가지 않도록 고려해야 한다.
데이터베이스는 1, 2번 문제의 경우 실시간 복제(replication) 기능을, 3번 문제의 경우는 트랜잭션 개념을 이용해서 처리해준다.
동시성
애플리케이션을 여러 사람이 사용하면, 동시에 같은 데이터를 덮어 써서 데이터가 원하는 대로 기록되지 않을 위험이 있다. 이런 문제는 파일에 쓰기 잠금을 걸면 해결 되고, 이는 애플리케이션 레벨에서도 적용이 가능하다. 그러나 잠금을 이용하는 방법은 애플리케이션의 성능을 급격히 저하시킨다. 데이터베이스는 잠금의 범위를 상황에 따라 늘리거나 줄여서 성능 저하 문제를 해결한다.
무결성
위의 문제를 해결하기 위한 방법 중 많은 부분이 데이터 무결성을 지키기 위한 방법이기도 하다. 추가로 데이터 접근 권한 같은 요구사항도 데이터베이스의 참조 무결성 제약 조건 기능으로 해결이 가능하다.
인덱스로 고속 액세스 실현하기
접근 과정
전체 검색
전체 검색은 곧 선형 검색이고, 이는 O(n)의 시간 복잡도를 가진다. 데이터가 커질 경우 이는 매우 비효율적이다.
데이터를 고정값으로
데이터를 고정 길이로 관리하면, ID * 고정 길이를 계산하여 원하는 데이터의 위치를 바로 알 수 있다. 이럴 경우 특정 데이터가 고정 길이를 넘어가는 예외가 항상 생길 수 있는데, 그렇다고 고정 길이를 처음부터 크게 잡으면 디스크의 낭비가 극도로 심해진다.
인덱스 구조 도입
인덱스를 이용하면 가변 길이 데이터를 이용하면서도 빠른 접근이 가능하다. 인덱스란 데이터의 ID마다 시작 위치를 기록해놓은 별도의 공간이다. 이런 기본적인 인덱스의 경우, ID와 데이터 위치만으로 구성하기 때문에 고정 길이를 사용할 수 있다. 즉, ID * 인덱스의 고정 길이를 이용해서 먼저 인덱스에 빠르게 접근한 뒤, 알아낸 데이터의 위치를 가지고 실제 데이터에 곧바로 접근하는 2단계를 거친다.
대신, 인덱스를 도입하면 기존 데이터를 업데이트 할 때마다 인덱스를 별도로 업데이트해야 하므로, 업데이트 비용은 증가하지만 가변 데이터의 검색을 고속화 할 수 있다.
해시 인덱스
위의 기본적인 인덱스는 ID와 데이터 위치로 구성했다. 그러나 언제나 ID를 키로 사용할 수 있는 것은 아니다. 문자열, 날짜/시간 등 여러 데이터 포맷이 인덱스의 키가 될 수 있어야 한다. 특히 문자열을 키로 하려면 가장 긴 경우를 기준으로 폭을 고정해야 하므로 범용성이 낮아진다.
이 경우, 키로 하려는 값을 해시 함수에 넣어, 해시 값과 기존 값의 쌍으로 키를 관리하는 해시 인덱스를 사용해서 문제를 해결할 수 있다. 해시 인덱스를 사용하면 접근 계산량도 여전히 O(n)이다. 다만 해시 인덱스를 사용하려면 해시 충돌을 관리해줘야 하는데, 데이터베이스 제품에서는 당연히 이 문제도 관리해주고 있다. 물론 데이터가 늘어날 수록 충돌 횟수가 많아지므로 속도가 느려지겠지만, 범용적인 인덱스를 구성하면서도 전체 검색에 비하면 엄청난 속도 증가가 있다.
B+Tree 인덱스
해시 인덱스는 부등호 연산이나 문자열 포함을 나타내는 범위 검색, 순서가 있는 정렬 등의 연산을 고속으로 처리할 수 없다. 이를 해결하기 위해서는 B+Tree 인덱스를 도입할 필요가 있다. B+Tree 인덱스는 다음과 같은 구조를 가지고 있다.
루트, 브랜치 블록은 실제로 데이터가 어디에 있는지에 대한 정보를 가지고 있고 실제 데이터는 모두 리프 블록에 저장되어 있다. 따라서 루트 -> 브랜치 -> 리프 순으로 어려번의 엑세스가 필요하다. 데이터의 양에 따라 브랜치 블록이 없을 수도, 다수의 Depth를 가질 수도 있다. 단 두번의 접근으로 끝나는 해시 인덱스에 비해서 접근 수가 많아지기는 한다.
B+Tree는 루트나 리프의 분기 개수가 여러개인 다분기 트리다. 분기 수를 줄이면 줄일 수록 Depth가 깊어지므로 브랜치 블록에 엑세스하는 횟수가 늘어나 비효율적이다.
- 이진 트리: 엑세스에
O(log2N)시간이 필요 - m개의 다분기 트리:
O(logmN)시간이 필요
B-Tree
실제 데이터를 리프 블록에만 저장하는 B+Tree에 비해, B-Tree는 실제 데이터를 브랜치 블록에도 저장한다. 이것은 어떤 경우 리프 블록까지 엑세스 할 필요가 없으므로 효율성을 증가시켜준다. 그러나 범위 검색이 필요한 경우에는 이야기가 다르다.
- B-Tree: 리프 블록에 접근했다가 다시 상위 브랜치 블록으로 이동해서 데이터를 찾거나 다른 리프 블록으로 엑세스하는 과정을 반복한다.
- B+Tree: 인접한 옆에 있는 리프 블록으로 바로 접근한다.
B+Tree의 이 장점 때문에 B+Tree는 RDBMS의 표준이 되었다.
RDBMS의 최적화 방법
고유성 보장
인덱스를 사용하면 중복 체크도 빠르게 가능하다. 텍스트 파일의 경우 중복 체크를 하려면 전체 검색을 반드시 해야 한다. 그러나 해시 인덱스를 사용하면 같은 해시 값이 나오는지만 확인하면 되고, B+Tree 인덱스를 사용하면 동일한 리프 블록의 동일한 키 값이 나오는지만 확인하면 된다.
인덱스만 검색
실제 데이터가 필요한 경우에는 인덱스 검색 -> 데이터 검색의 단계를 반드시 거쳐야 한다. 그러나 만약 데이터의 갯수 같은 값만 필요한 경우, 인덱스의 갯수만 세어도 결과를 얻을 수 있기 때문에 실제 데이터를 검색할 필요가 없어 속도가 향상된다.
멀티컬럼 인덱스
두 개 이상의 컬럼으로 하나의 인덱스를 만들면 AND 조건 검색을 빠르게 할 수 있다.
인덱스 병합
두 개 이상의 인덱스를 동시에 한 번의 검색에 이용하면 OR 조건 검색을 빠르게 할 수 있다.
모아서 디스크에 기록
실제 데이터를 업데이트 할 경우 B+Tree 인덱스에도 업데이트가 필요하다. 이 때 순서가 없는 데이터로 인덱스의 키를 만든 경우, 인덱스를 업데이트 할 때마다 하드 디스크에 랜덤 쓰기가 일어나게 되는데, 이는 이는 하드 디스크 병목을 만들어 성능을 크게 저하시킨다. MySQL은 업데이트된 정보를 메모리나 전용 파일에 임시로 기록했다가 모아서 한번에 리프 블록을 갱신할 때 하드 디스크에 시퀀셜 쓰기를 하게 되는데 이 것으로 성능을 향상 시킬 수 있다.
- 이건 그냥 참고: [RDBMS의 성능 향상을 위해 SSD는 가성비 있는 선택인가?](https://prezi.com/bpnptth_x3lm/dbms-ssd/%29
인덱스 업데이트의 동시성
B+Tree 인덱스를 업데이트 할 경우, 리프 블록의 내용을 이동시킬 필요가 생긴다. 이를 리프 분할이라고 한다. MySQL은 리프 분할이 일어날 경우, 데이터 일관성을 위해서 인덱스의 재편성이 끝나기 전 까지는 참조/갱신을 차단한다. 재편성 작업이 오래 걸리는 것은 아니지만, 이 Lock으로 인해 업데이트의 동시성은 별로 높지 않다.
MySQL의 경우 이런 문제를 해결하기 위해서 파티션 테이블을 사용할 수 있다. 논리적으로는 하나의 테이블이 물리적으로 두 개의 테이블로 관리되고 있기 때문에 인덱스 업데이트의 동시성을 늘릴 수 있다.
qodot