색인
색인의 필요성
기본적인 저장소 형식은 매 라인마다 쉼표로 구분된 키-값 형태로 저장된 텍스트 파일이다.
데이터를 추가 시 파일의 끝에 추가되고 이전 내용을 덮어쓰지 않는 간단한 방식으로 성능 차원에서는 좋은 부분을 보여준다.
하지만 레코드들이 쌓일 수록 매번 키를 찾을 때 전체 데이터 베이스 파일을 거쳐야하기 때문에 검색 비용이 O(n)으로, 적절치 않다.
이런 경우 효율적으로 키 값을 찾기 위해서는 효율적인 데이터 구조(색인)가 필요하게 되었다.
색인이란
사전적 정의
“색인(索引)은 책 속의 낱말이나 구절, 또 이에 관련한 지시자를 찾아보기 쉽도록 일정한 순서로 나열한 목록을 가리킨다.인덱스(index)라고도 한다.”
즉, 색인은 데이터의 이정표 역할을 하여 데이터 위치를 쉽게 찾을 수 있게 하는 구조를 의미한다.
색인은 새로운 데이터 구조를 만든다기보단 기존 데이터에서 파생된 데이터 구조이다.
색인을 사용함으로써 읽기 질의 속도가 향상되지만 쓰기 속도는 떨어트리기 때문에 애플리케이션에 맞는 색인 구조를 선택할 수 있어야 한다.
해시 색인
해시 색인은 키를 해시 함수로 변환하여 특정 위치(오프셋)을 저장하여 빠르게 검색하는 방식의 색인이다.
로그 구조화 색인 방식이다.
📂 로그 구조화 색인 방식이란?
데이터를 디스크에 순차적으로 쓰는 구조
기존 데이터를 직접 수정하지 않고 새로운 데이터로 덮어쓰는 방식
기존 데이터는 후에 컴팩션을 통해 처리된다.
-저장 과정-
- 인메모리 해시맵(Map<Key, Offset>) 형식으로 각 키가 데이터 파일의 어느 위치에 저장되어있는지 매핑한다.
- 바이트 오프셋을 통해서 특정 데이터의 위치로 Offset에 매핑하여 특정 값을 읽어온다.
- 새로운 키-값 데이터가 추가된다면 새로운 데이터의 위치를 기록하기 위해 해시맵을 갱신한다.
-조회 과정-
- 해시맵에서 해당 키의 오프셋을 찾는다.
- 해당 오프셋을 이용해 파일에서 값을 읽어온다.
해시 색인 방식은 비트캐스크(Bitcask)에서 사용하는 방식으로, 데이터를 빠르게 저장하고 키의 값이 자주 갱신되는 상황에 적합하다. (예. 비디오 재생 횟수)
→ 덮어쓰기 방식이 아니고 새로운 값을 파일 끝에 추가하는 방식이기 때문에 갱신 속도가 빠른 상황에 적합
→ 모든 키의 오프셋을 해시맵에 유지하기 때문에 키 기반 검색 속도가 빠름
하지만 계속 새로운 데이터를 추가하는 방식이다 보니 디스크 공간은 결국 부족해질 것이다.
이러한 문제를 해결하기 위한 방법은 특정 크기의 세그먼트(segment)로 로그를 나누는 방법이다.
세그먼트 적용
데이터가 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행한다.
이러한 과정에서 중복된 키를 버리고 각 키의 최신 값만 유지(컴팩션, Compaction)할 수 있도록 하여 세그먼트 크기를 더욱 작게 만들 수 있다.
더욱 작게 만들어진 세그먼트는 다른 세그먼트들과 병합할 수 있으며 해당 작업은 백그라운드 스레드에서 수행되어 컴팩션을 수행하는 동안에도 정상적인 읽기와 쓰기 처리는 가능하다.
-과정-
- 각 세그먼트는 키를 파일 오프셋에 매핑한 자체 인메모리 캐시 테이블을 갖는다.
- 키의 값을 찾기 위해 최신 세그먼트 해시 맵을 먼저 확인한다.
- 키가 없다면 다음 최신 세그먼트 등을 확인한다.
- 병합 과정을 통해 세그먼트 수를 적게 유지하여 조회 시 많은 세그먼트들을 찾을 필요가 없다.
해시 색인을 구현하기 위해 고려해야할 사항
- 파일 형식 : CSV는 사람이 읽기 쉽지만 로그에 가장 적합한 형식이 아니기 때문에 바이트 단위의 문자열을 부호화하여 저장하는 바이너리 형식 적합
- 레코드 삭제 : 키와 관련된 값을 삭제 시 데이터 파일에 특수한 삭제 레코드(=툼스톤(tombstone))를 추가해야 한다. 로그 세그먼트가 병합될 때 툼스톤은 병합 과정에서 삭제된 키의 이전 값을 무시하게 한다.
- 고장 복구 : 데이터 베이스가 재시작되면 인메모리 해시맵은 손실되기 때문에 복원 시 오랜 시간이 걸릴 수 있다. 비트캐스크 경우에는 스냅샷을 저장하여 복구 속도를 높였다.
- 부분적으로 레코드 쓰기 : 데이터베이스는 로그에 레코드를 추가하는 도중에 꺼질 수 있다. 그래서 일부 레코드만 기록이 될 수 있다. 비트캐스크는 체크섬을 포함하고 있어 로그의 손상된 부분을 탐지하여 무시할 수 있다.
- 동시성 제어 : 여러 개의 스레드가 동시에 데이터를 쓰면 충돌이 발생할 수 있다. 쓰기 작업을 단일 스레드에서 수행하고 로그에 순차적으로 추가하는 방식을 사용하여 동시성 문제를 피한다. 비트캐스크는 하나의 쓰기 스레드만 사용하여 쓰기 성능을 최적화하고 데이터 일관성을 유지한다.
제한 사항
해시 테이블은 메모리에 저장해야 하기 때문에 키가 너무 많아지면 문제가 될 수 있다.
디스크에도 해시 맵을 유지할 수 있지만 해시 맵의 장점인 좋은 성능은 기대할 수 없다. → 메모리보다 디스크는 속도 차원에서도 매우 떨어지기 때문에 그런듯 하다.
SS 테이블
해시 테이블의 제한 사항을 해결해주는 색인 구조이다.
SS 테이블(정렬된 문자열 테이블(Sorted String Table))은 이전 키-값 쌍으로 저장되는 세그먼트 파일 형식에서 데이터를 키로 정렬(sorted)하는 방식을 추가한 형식이다.
그리고 각 키는 병합된 세그먼트 파일 내에 한번만 나타나야 한다.
- 키가 정렬되어있기 때문에 키의 정확한 오프셋을 알지 못하더라도 전체 데이터를 살펴보지 않아도 위치를 알 수 있다.
- 메모리 부족 문제를 해결하기 위해 메모리에서 일정 크기로 정렬된 데이터를 디스크에 저장한다.
- 읽기 요청 시에는 요청 범위 내에서 키-값 쌍을 스캔해야 하기 때문에 해당 레코드들을 그룹화하고 디스크에 쓰기 전에 압축하여 I/O 사용도 줄인다.
SS 테이블 수행 과정
SS 테이블을 사용하면 데이터를 정렬된 상태로 유지하면서 저장할 수 있다.
하지만, 데이터가 유입되는 순서는 랜덤일 수 있어 균형 트리 구조(레드 블랙 트리, AVL 트리)를 사용하여 자동 정렬을 수행한다.
레드 블랙 트리를 적용시킨다면 다음과 같이 설계할 수 있다.
- 쓰기가 들어오면 인메모리 균형 트리 데이터 구조에 추가된다.
- 데이터가 저장소에 기록될 때, 우선적으로 인메모리 균형 트리(예. Red-Black Tree, AVL Tree)인 memtable에 저장된다.
- 이때 멤테이블은 데이터가 정렬된 상태로 유지된다.
- 멤테이블이 일정 크기를 초과하면 SS 테이블로 변환하여 디스크에 기록한다.
- SS 테이블은 이미 키 정렬이 되어있기 때문에 이후 읽기 요청 시에 빠르게 수행이 가능하다.
- 새로운 SS 테이블이 생성되면서 해당 파일은 가장 최신 세그먼트가 되고 이전 SS 테이블은 그대로 유지된다.
- 읽기가 들어오면 최신 데이터부터 검색한다.
- 멤테이블에서 키를 검색한다. 멤테이블에서 찾는다면 바로 반환한다.
- 찾지 못하면 가장 최신 SS 테이블에서 찾는다.
- 찾지 못하면 다음 SS 테이블에서 찾는다.
- 불필요한 데이터를 정리한다.
- SS 테이블 파일이 많아지면 병합과 컨벤션 작업을 수행한다.
제한 사항
디스크에 저장됨으로써 메모리 손실을 방지할 수 있고 정렬된 데이터 구조를 가지고 있기 때문에 디스크 성능도 최적화시킬 수 있지만!
하지만 데이터 베이스가 고장나면 디스크로 기록되지 않고 멤테이블에 있는 쓰기 데이터는 손실되는 문제가 있다.
해결 방안은!
해결하기 위해서는 매번 쓰기를 즉시 추가할 수 있는 분리된 로그를 갖고 있어야한다.
그리고 멤테이블이 SS 테이블로 기록하고 나면 해당 로그는 버린다.
SS 테이블에서 LSM 트리 만들기
LSM 트리란?
LSM 트리는 SS 테이블을 효율적으로 관리하는 로그 구조화 병합 트리(Log-Structure Merge Tree) 구조의 데이터 저장 방식이다.
기본적으로 메모리에서 처리하고 일정 크기가 되면 디스크로 플러시하여 저장하는 방식이다.
정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라 부른다.
성능 최적화
데이터 색인 구조 외에도 추가적으로 성능을 최적화하는 기술들도 있다.
- 블룸 필터(Bloom filter) 멤테이블에 키가 존재하지 않는 경우에는 가장 오래된 세그먼트까지 거슬러 올라가기 때문에 성능에 문제가 발생할 수 있다. 이때 블룸 필터는 키가 데이터 베이스에 존재하지 않음을 알려줘 불필요한 읽기를 하지 않을 수 있게 해준다.
- 계층 컴팩션(size-tiered compaction)과 레벨 컴펙션(leveled-compaction) 크기 계층 컴팩션은 상대적으로 좀 더 새롭고 작은 SS 테이블로 나누고 오래된 데이터는 개별 ‘레벨’로 이동하여 컴팩션을 점진적으로 진행하여 디스크 공간을 덜 사용할 수 있도록 한다.
B 트리
가장 널리 사용되고 있는 색인 구조중 하나인 B 트리 구조는 앞에서 봤던 로그 구조화 색인과는 다르다.
대부분의 관계형 데이터 베이스에서 표준 색인 구현으로 사용하며 비관계형 데이터 베이스에서도 많이 사용되고 있다.
특징
- 로그 구조화 색인은 일정 크기를 초과하면 세그먼트로 나누고 순차적으로 기록하지만, B 트리는 고정된 크기 블록이나 페이지로 나누고 한번에 하나의 페이지에 읽기 또는 쓰기를 한다.
- 각 페이지는 주소나 위치를 이용해 식별할 수 있고 하나의 페이지는 다른 페이지를 참조할 수 있다.
- 한 페이지는 B 트리의 루트로 지정되고 색인에서 키를 찾을 때는 루트부터 시작하여 개별 키를 포함하는 페이지(리프 페이지(leaf page))에 도달할 때까지 탐색 <B 트리에서 키 찾는 과정>
- 루트 페이지에서 검색 시작
- 해당 키의 범위를 포함하는 하위 페이지 이동
- 최종적으로 이프 페이지에 도달하면 키를 찾고 데이터를 반환(O(log n))
- B 트리의 한 페이지에서 하위 페이지를 참조하는 수를 분기 계수라고 부른다. <B 트리에 존재하는 키의 값을 갱신하는 과정>
- 키를 포함하고 있는 리프 페이지를 검색하고 페이지의 값을 바꾼 다음 페이지를 디스크에 다시 기록
- 새로운 키를 추가하려면 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가
- 새로운 키를 수용한 페이지에 충분한 여유 공간이 없다면 페이지 하나를 반쯤 채워진 페이지 둘로 나누고 상위 페이지가 새로운 키 범위의 하위 부분들을 알 수 있도록 갱신
신뢰도 개선 방법
- 쓰기 전 로그(write-ahead log, WAL)(재실행 로그(redo log)라고도 함) B 트리의 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓰는 방식이다. 만약 이 과정에서 데이터 베이스가 고장난다면 고아 페이지(어떤 페이지와도 부모 관계가 없는 페이지)가 발생할 수 있다. 데이터 베이스가 고장 상황에서 스스로 복구할 수 있게 만들려면 일반적으로 디스크 상에 쓰기 전 로그라고 하는 데이터 구조를 추가하여 고장 이후 복구될 때 일관성있는 상태로 복원하는데 사용된다.
- 래치(latch) 동시성 문제가 발생하는 경우 래치로 보호할 수 있다. 유입 질의의 간섭 없이 백그라운드에서 모든 병합을 수행하고 원자적으로 새로운 세그먼트를 이전 세그먼트로 바꾼다.
최적화 방법
- 복사 방식(copy-on-write schema) 페이지 덮어 쓰기와 고장 복구를 위해 사용되는 방식이다. 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키게 한다.
- 키 축약 페이지에 전체 키를 저장하는 것이 아닌 축약된 키를 사용하여 공간을 절약시킨다. 트리 내부 페이지에서 키가 키 범위 사이의 경계 역할을 하는데 필요한 역할만 하면 되기 때문에 가능하다. 키를 축약함으로써 페이지 하나에 키를 더 많이 채울 수 있기 때문에 트리 깊이 수준을 낮출 수 있다.
- 연속된 페이지 정렬 일반적으로 페이지는 디스크 상 어디에나 위치할 수 있기 때문에 정렬되지 않아 스캔 시 모든 페이지에 대해 디스크 찾기가 수행되어 비효율적이다. 그렇기 때문에 리프 페이지를 디스크 상에 연속된 순서로 나타나게 하려고 한다.
- 트리에 포인터 추가 각 리프 페이지가 양쪽 형제 페이지에 대한 참조를 가지면 순서대로 키를 스캔할 수 있다.
- 버퍼링 기법 B 트리 변형의 프랙탈 트리는 디스크 찾기를 줄이기 위해 로그 구조화 개념을 빌려 버퍼링 기법을 사용한다. 버퍼링 기법은 쓰기 성능을 높이기 위해 데이터를 즉시 디스크에 기록하지 않고 노드마다 버퍼를 두고 데이터를 쌓아둔 후 한꺼번에 기록하는 방식이다.
B 트리와 LSM 트리 비교
| LSM 트리 구조 | B 트리 구조 | |
|---|---|---|
| 장점 | - 순차 쓰기 방식과 컴팩션 활용으로 쓰기 성능이 더 빠름 - 쓰기 증폭이 상대적으로 낮아 높은 쓰기 처리량 가능 - 압축률이 더 좋아서 B 트리보다 디스크 공간 효율적으로 사용이 가능함 - 낮은 쓰기 증폭과 파편화 감소로 인해 SSD 환경에서 유리 | - 상대적으로 구현 성숙도가 더 높음 - 읽기 성능이 더 좋음 - 각 키가 한 색인에만 존재하기 때문에 데이터 관리가 용이함 |
| 단점 | - 컴팩션 단계별로 여러 데이터 구조와 SS 테이블을 조회해야하기 때문에 읽기 기능은 성능이 떨어짐 - 컴팩션이 많아질 수록 디스크 대역폭이 필요하여 성능 저하 발생 | - 모든 데이터 조각을 쓰기 전 로그 + 트리페이지로 최소한 두 번 기록해야 함 - 고정된 크기의 페이지를 사용하기 때문에 단위 쓰기 오버헤드가 발생할 수 있음 - 고정된 페이지 크기로 인해 일부 공간이 낭비될 수 있음 |
기타 색인 구조
기본 키 색인((primary key index)
기본키로 관계형 테이블에서 하나의 로우를, 문서 데이터베이스에서 하나의 문서를, 그래프 데이터베이스에서 하나의 정점을 식별할 수 있게 한다.
보조 색인(secondary index)
보조 색인은 기본키 이외에 컬럼에 대해 색인을 추가로 생성하는 방식이다. 기본키 색인과 다르게 키가 고유하지 않다.
보조 색인을 통해서 조인을 수월하게 할 수 있다.
힙 파일(Heap file)
힙 파일은 특정한 정렬이나 색인없이 데이터가 임의의 위치에 저장되는 방식이다.
- 색인에서 실제 데이터가 저장된 위치를 가리키는 구조이다.
- 데이터가 정렬되지 않으며 삽입되는 순서로 저장된다.
- 색인은 힙 파일에서의 데이터 위치를 참조하므로 중복 저장을 방지할 수 있다.
- 힙 파일은 값을 갱신할 때 효율적이다. -힙 파일 데이터 갱신 원리-
- 새로운 값이 이전 값보다 작은 경우에는 현재 위치에 레코드에 덮어쓸 수 있다.
- 새로운 값이 이전 값보다 큰 경우에는 힙에서 충분한 공간이 있는 새로운 위치로 이동해야한다.
이런 경우에는 모든 색인을 새로운 위치를 가리킬 수 있도록 갱신하거나 이전 위치에 대한 포인터를 남기는 방법이 있다.
색인 종류
- 클러스터드 색인(clustered index) : 색인 안에 색인된 로우 저장
- 커버링 색인(convering index)나 포괄열이 있는 색인(index with included column) : 색인 안에 테이블의 칼럼 일부를 저장하여 색인만 사용해 일부 질의의 응답이 가능하게 함
다중 컬럼 색인
다중 컬럼 색인은 여러 개의 컬럼을 조합하여 하나의 색인을 생성하는 방식이다.
단일 컬럼 색인보다 검색 성능을 최적화할 수 있다.
결합 색인(concatenated index)
다중 칼럼 색인의 가장 일반적인 유형으로 하나의 칼럼에 다른 칼럼을 추가하는 방식이다.
CREATE INDEX idx_users_name_age ON users (name, age);다채색 색인
한 번에 여러 칼럼에 질의하는 방식으로 지리 공간 데이터에 중요하게 사용된다.
- 지리 공간 데이터 사용 예시 레스토랑 검색 웹사이트에서 레스토랑의 위도와 경도 기준으로 검색해야하는 경우 B 트리는 1차원 값만 색인할 수 있어 위도/경도는 2차원이라 저장할 수 없다. 이런 경우 공간 채움 곡선(Space-Filling Curve)을 통해 2차원 데이터를 1차원 데이터 값으로 변환하고 변환된 값을 B 트리 색인에 적용한다.
CREATE INDEX idx_location ON restaurants USING gist (location);전문 검색과 퍼지 색인
데이터 베이스 색인은 정확한 값을 검색하거나 정렬된 범위에서 데이터를 찾는데 적합하다.
하지만 철자가 틀린 단어나 유사한 키 값을 검색하는 데는 한계가 있다.
이를 해결하기 위한 방법이 전문 검색 엔진이다.
전문 검색 엔진은 사용자의 질의를 자동으로 확장하여 동의어, 철자 오류, 형태소 분석 등을 적용하여 검색 결과를 제공한다.
예로는 Elasticsearch, Solr 등이 있다.
출처
데이터 중심 애플리케이션 설계
