[Database] 인덱스 (Index) 6장 : 쓰기에 최적화된 인덱스

 

https://kghworks.tistory.com/153

[Database] 인덱스 (Index) 5장 : Multiple-key Access (다중 키)

 

 여기서부터는 심화 포스팅이다. B+-Tree index는 쓰기 성능이 떨어지므로 쓰기 성능에 특화되어 있는 인덱스 구조가 필요하다. 이번 포스팅에서는 쓰기 작업에 특화되어 있는 인덱스 구조를 설명한다.

 

목차

• B+-Tree 인덱스의 쓰기 성능
• LSM Trees
• Buffer Trees
• LSM Trees vs Buffer Trees

---

B+-Tree 인덱스의 쓰기 성능

 

B+-Tree 인덱스 예시

 

 B+-Tree 인덱스는 읽기 작업에 특화되어 있는 인덱스이다. root 노드로부터의 모든 탐색의 복잡도가 동일하기 때문이다.  그러나 쓰기 성능은 상대적으로 떨어진다. (random write) 

 

 leaf node를 제외한 level은 메모리에 있고, leaf level은 disk에 있는 B+-Tree 인덱스를 가정해 보자. 인덱스 순서와 무관한 순서로 wirte (insert)가 수행될 경우 각 write은 서로 다른 leaf node를 찾아가야 한다. 만약 leaf node의 수가 buffer size보다 아주 큰 경우 random read operation과 leaf node를 다시 disk에 쓰는 작업이 필요해진다.

 

 따라서 B+-Tree 인덱스의 경우 잦은 쓰기 작업의 비율이 상대적으로 높은 테이블에는 적절치 못한 것으로 보인다. 이에 대안으로 제시할 수 있는 인덱스 2가지 LSM tree, buffer Tree를 소개한다.

 

---

LSM Trees (log-strucutred merge tree, 로그 구조 합병 트리)

level 3 LSM Tree

 

 하나의 LSM tree는 n개의 B+-Tree로 구성된다. L0은 in-memory B+-Tree로 인덱스의 시작점이다. 상당히 많은 양의 메모리 공간이 L0트리에 할당된다. 그다음 L1부터는 Disk에 저장되는 on-disk B+-Tree이다. 탐색 시에는 각 계층별로 탐색을 수행해서, 결과를 병합하여 반환하는 식으로 진행한다. 

 

LSM Tree의 삽입/수정/삭제 과정은 아래 영상을 통해 보면 더 빨리파악할 수 있다.

https://www.youtube.com/watch?v=oUNjDHYFES8&ab_channel=GLTechTutorials

Youtube 채널 :  GL Tech Tutorials

 

Insertion

 인덱스 삽입시 제일 먼저 in-memory B+-Tree (L0 tree)에 삽입한다. 그 후 L0 tree가 가득 찰때까지 L0 tree에 인덱스를 삽입한다. L0 tree가 가득 차게 되면, L0 tree를 모두 on-disk B+-Tree로 이동해 L1 tree를 초기화 (생성)한다.

 이때 L1이 모두 비어있으면 L0을 모두 L1으로 복사하지만, L1이 비어있지 않으면 L0의 leaf level을 순차적으로 스캔해서 L1의 leaf level과 병합해서 새로운 L1 tree를 만든다. 새롭게 생성된 L1 tree가 기존의 L1 tree를 대체한다. 그 후 L0 tree를 삭제한다. 즉 L1부터 존재하는 테이블들은 모두 불변이다. (immutable)

 

 기존의 L1 tree를 수정하지 않고, L0 tree와 병합해서 새로운 L1 tree를 만드는 이유는 뭘까. 먼저 병합함으로서 새롭게 생성된 L1 tree의 leaf node는 순차적으로 위치해서 다음 병합 작업 시 random I/O를 피할 수 있다. 두 번째 장점으로 leaf node를 가득 채울 수 있다는 것이다. leaf node가 underfull일수록 공간 낭비가 심하다. (space overhead)

 

 장점만 있지 않다. 인덱스 삽입 시 LSM 구조를 구축하기위해 트리의 복사가 일어난다. 이 비용은 다음처럼 극복할 수 있다.

 

삽입시 발생하는 Tree 복사 작업의 비용을 줄이는 방법

L(i+1) 트리의 최대 크기는 L(i)의 최대 크기의 k배로 지정하면 각 레코드는 각 레벨에서 최대 k번 쓰기 작업이 일어날 수 있다. 

 stepped-merge index (단계병 합병 트리)를 이용하는 방법도 있다. stepped-merge index란 L0을 제외한 각 계층에는 최대 b개(1개 이상)의 트리가 존재할 수 있는 LSM 트리를 말한다. L0의 트리가 디스크 (L1)에 쓰일 때 기존의 L1과 합병하는 대신 새로운 L1트리를 만든다. (이때 L1 트리는 2개가 됨) L1 트리의 수가 b개에 도달하면 L2에 새롭게 합병해서 트리를 생성한다. 인덱스 삽입 비용을 줄일 수 있지만 각 계층별로 트리가 최대 b 개씩 있어, access Time (탐색)이 늘 수 있다. 

 stepped-merge index는 Google Bigtable, Apache HBase, Apache Cassandra, MongoDB 등 다수의 빅데이터 저장 시스템에서 지원한다. MySQL, SQlite4, LevelDB도 지원되고 있다.

 

Deletion

 인덱스에서 삭제할 엔트리를 제거하는 대신, deletion entry로 표시하여 삽입한다. (즉 동일한 Index Entry에 대해 deletion entry가 하나 더 생기는 상황) 이때 deletion entry는 Insertion 과정과 동일하게 진행된다. 삭제 작업 시 Insertion 작업이 동반되기 때문에 삭제 작업의 비용에 overhead가 있다. 탐색 시 Deletion entry를 포함해서 탐색하고, 탐색 결과에서 Deletion entry를 제거하는 식으로 수행된다. 트리가 병합될 때 한쪽 트리에는 index entry가 있고 동일한 entry에 대해 다른 쪽 트리에 deletion entry가 존재하면 두 index entry가 모두 제거된다. (드디어 디스크에서 인덱스가 제거된다!!!)

 

Update

 Deletion 과 유사하게 update entry를 삽입하는 방법으로 진행된다. 그 후 트리가 병합될 때 업데이트 되지 않은 하나의 엔트리는 제거된다. 탐색 시에는 같은 entry 중 가장 최근에 업데이트된 entry를 반환하게 한다. 트리가 병합될 때 한쪽 트리에 index entry가 있고 동일한 entry가 반대쪽 트리에도 있으면 더 최신 index entry를 살리고 나머지 하나를 제거한다. (드디어 업데이트 이전의 인덱스가 디스크에서 제거된다!!!)

 

LSD Tree와 SSD의 궁합

 앞서 설명했듯 LSD Tree는 쓰기 작업에 대한 최적화를 가지는 트리이다. 쓰기 작업 시 발생하는 disk random I/O 작업 overhead를 줄이기 위해 고안된 트리로, SSD의 경우 그 효과가 미미하다. 즉, LSD Tree는 SSD에서는 그 목적에 부합하지 않는 구조의 인덱스다. 플래시 기반의 SSD는 읽기 속도가 월등히 빠르기 때문이다.

 

---

 

Buffer Tree

Buffer Tree의 내부 노드 구조

LSM Tree의 대안으로 사용할 수 있는 트리이다. B+Tree의 내부 노드와 버퍼를 연결해 놓는 식이다. PostgreSQL의 Generalized Search Tree (GiST)가 해당된다. 

 

Insertion

인덱스 삽입 시 Tree를 탐색하지 않고 일단 Root node의 Buffer에 넣는다. Buffer가 가득 차면, Buffer의 모든 Index entry를 자식 노드로 내린다. 자식 노드가 내부노드 (단말노드 아님)라면, 자식 노드의 Buffer에 넣는다. 이때 자식 노드에 내려가기 전에 Idnex entry를 정렬한다. 계속 자식 노드로 내려가다 마침내 단말 노드를 만나면 일반 B+-Tree처렴 Index entry를 삽입한다. overfull이 발생하면 B+-Tree와 동일하게 Split을 발생시켜 상위 노드로 전파시킨다. 

 

Lookup

B+-Tree와 유사하게 진행되지만 각 노드에서 추가 작업이 필요하다. 각 노드의 Buffer에 찾으려는 search key가 있는지 검사해야 한다. 

 

 

Deletion, Update

LSM Tree와 유사하게 처리할 수 있다. (deletion entry / update entry를 추가) 아니면, 일반적인 B+-Tree처럼 수행할 수도 있는데, 이때는 LSM Tree 방식을 사용할 때보다 I/O 비용이 더 커질 수 있다. 

---

LSM Trees vs Buffer Trees

 

LSM Tree의 장점

쓰기 작업의 경우 stepped-merge index가 Buffer Trees 보다 더 우수하다. 또한 magnetic disk인 경우 LSM Tree가 더 유리하다. Buffer Tree의 높은 검색 비용 때문이다. SSD라면 검색 비용이 문제가 되지 않는 저장소이기 때문에, Buffer Tree가 미세하게 더 유리하다.  SSD 저장소를 위해 설계된 Buffer Tree도 있다.

 

 

Buffer Trees의 장점

 I/O 연산수에 대한 최악의 복잡도는 Buffer Treesr가 더 우수하다.  읽기 작업 또한 Buffer Trees가 더 빠르다. (LSM Trees는 각 계층을 모두 탐색한 뒤 결과를 병합하여 반환) 각 노드에 Buffer를 두는 아이디어는 다른 구조의 인덱스들에도 적용해 볼 수 있다. 이를테면 Spatial Index R-Tree의 bulk loading을 구현하는 방법이 될 수 있다. (PosgreSQL)

 

---

 

참고

 

https://youtu.be/I6jB0nM9SKU

 

https://www.youtube.com/watch?v=oUNjDHYFES8&ab_channel=GLTechTutorials 

https://d2.naver.com/helloworld/7005