IAVL 트리 특징
IAVL은 스냅샷을 찍을 수 있는 트리이다. IAVL 트리는 AVL 트리 알고리즘을 응용해서 언제나 균형을 유지한다. 복잡도는 O(log(n))이다. IAVL 트리는 동시에 머클트리로서의 역할도 한다.
패트리샤 트라이와의 차이점
패트리샤 트라이는 이더리움에서 사용된다. 패트리샤 트라이는 공격자가 트라이의 높이를 의도적으로 증가시켜서 read, write에서 부하를 주는 공격을 방지하기 위해서 write 전에 key를 해쉬한다. 그래서 iteration이 느리다. IAVL 트리는 균형을 알아서 유지하기 때문에 저런 공격에 노출되지 않는다. 그래서 key를 그냥 저장하기 때문에 iteration에서 더 유리하다. IAVL 트리는 값을 쓰는 순서에 따라 노드의 배치가 달라질 수 있다. 하지만 블록체인에서 딱히 문제되진 않을 것이다.
균형
IAVL 트리는 AVL 트리와는 다르게 값은 오직 잎 노드만이 가지고 있다.
처음 키가 3인 값을 넣었을 때
그후 키가 4인 값을 넣었을 때
잎 노드만 키와 값을 가지기 때문에 새로운 값이 들어오면 새로운 이너 노드를 만들고 작은 키값을 왼쪽, 큰 키값을 오른쪽 노드로 한다.
그후 키가 1인 값을 넣었을 때
그후 키가 2인 값을 넣었을 때
이 때 균형이 무너졌다. 루트 노드에서 높이가 2 이상 차이나는 서브트리가 생겼다.
Left Left
이 경우 LL이다. 이때 서브트리에서 불균형이 발생한 노드를 오른쪽으로 회전시킨다. 오른쪽으로 회전시키면 왼쪽 노드가 루트 노드를 대체하고 루트 노드는 대체된 노드의 오른쪽 노드가 된다. 대체된 노드의 원래 왼쪽 노드는 루트 노드의 오른쪽 노드가 된다. 이렇게 하고 나면 균형이 맞춰진다.
Left Right
LR의 경우를 살펴보기 위해서 일단 LR을 만들어야한다. 1,4,2,3 순으로 넣는다. 그러면 이렇게 불균형이 발생한다.
이 경우 불균형이 발생하기 시작한 노드의 왼쪽 노드를 왼쪽으로 회전시킨다. 그러면 이런 모양이 나온다.
위의 LL의 경우와 같아졌다. LL의 경우처럼 불균형이 발생한 노드를 오른쪽으로 회전시킨다. 이렇게 하고 나면 균형이 맞춰진다.
Right Right
Right Left
위의 경우와 정확히 반대이기 때문에 생략한다.
참조:https://github.com/tendermint/iavl/blob/master/mutable_tree.go#L416
스냅샷
SaveVersion을 사용하면 현재의 루트 노드와 이번 버전에서 발생한 고아 노드들을 저장한다. 그리고 머클 루트 해쉬를 반환한다.
LoadVersion을 통해서 이전의 스냅샷으로 돌아갈 수 있다. 이 경우 현재 트리의 루트 노드를 버전에 맞춰서 바꾼다. 이전의 고아노드들은 삭제되지 않고 저장되어 있기 때문에 괜찮다.
DeleteVersion을 통해서 스냅샷을 삭제할 수 있다. 해당하는 루트 노드와 쓸모없어진 고아노드들을 삭제한다.
프루닝
IAVL 트리는 공간 낭비가 심하기 때문에 필요없어진 스냅샷은 적절히 삭제해야한다. Cosmos-sdk에는 관련 옵션이 있다. 적절한 정책으로 스냅샷을 관리하면 된다.
PS...
이더리움은 유명해서 패트리샤 트라이에 대한 한국어 정보도 있는데 텐더민트의 iavl 트리는 한국어 정보가 없어서 정리해봤습니다. 어쩌면 이 사이트에서 최초의 블록체인 관련 글일지도...
