geth 구현체의 패트리샤 트리 테스트

안녕하세요, 이더리움 코드보는 sigmoid 입니다.
오늘은 이더리움 패트리샤 트리의 가장 유명한 버전인 아래 그림이 geth에서 어떻게 구현되었는지 살펴 보려고 합니다.

전에 트라이 패키지 분석글에서 언급되었듯, 그림상의 용어와 geth에서 사용하는 용어가 다르기 때문에 다시한번 싱크를 맞추고 가는것이 좋을 듯 합니다.

extension -> short
branch -> full
leaf -> value

+wiki data로 직접 그려보기

+코드로 확인하기
위 그림을 확인하기 위해서 트리를 새로 만들고, 키값을 그대로 사용하여 업데이트 해보는 프로그램을 작성해보았습니다. value는 알아보기 편하게 1,2,3,4로 하지요.

Update함수가 trie/trie.go에 위치한 insert함수를 호출하기 때문에 해당 함수에 로그를 다수 추가하였습니다.
실행 결과를 살펴보며 이해해 나가도록 하지요.

// 첫번째 데이터 삽입
Insert [10 7 1 1 3 5 5], [1]
000a00070001000100030005000510 //변환된 키값

// 최초 루트가 nil이기 때문에 숏노드를 먼저 생성한다
// Short node의 키와 값
[N] Create [S]
key 000a00070001000100030005000510, Value 01

// 두번째 데이터 삽입
Insert [10 7 7 13 3 3 7], [2]
000a00070007000d00030003000710

// 매칭된 길이가 5가 나왔다. 키값을 니블로 처리하기 때문
// 결국은 a,7이 같다는 뜻이다
// 그리고 현재는 숏노드상태
[S] matchlen = 5

// 현재 숏노드 이므로 분기를 위해 풀노드를 생성한다
CreateFullNode

// 맨처음에 넣은 데이터는 a,7 다음에 1이니까 1번 항목에 값을 넣어야 한다
try insert 1
[N] Create [S] // 비어있네? 숏노드 하나 새로 만들어서 달아줌
// 해당 숏노드의 키값은 이제 a,7,1을 제외한 [1,3,5,5]
key 000100030005000510, Value 01

// 두번째 넣은 데이터는 a,7 다음에 7이니까 7번 항목에 값을 넣어야 한다
try insert 7
[N] Create [S] // 역시 비어있으므로 숏노드 생성
// 새롭게 생긴 숏노드의 키값은 a,7,7을 제외한 d,4,4,7
key 000d00030003000710, Value 02

// 위에서 새롭게 만들었던 브랜치노드(풀노드)를 맨처음 생성한 숏노드의 값으로 달아둔다
// a,7을 가진 숏노드의 값은 어떤 풀노드인데,
// 해당 풀노드의 1번과 7번에 각각 숏노드가 붙어있는 상태가 되었다
short node key 000a000700, Value branch

// 세번째 데이터 삽입
Insert [10 7 15 9 3 6 5], [3]
000a0007000f000900030006000510
[S] matchlen = 5
key matched // 얘도 a,7은 겹치네
[F] // 이미 풀노드이므로 분기처리가 가능
[N] Create [S] // 15가 비어있으니 숏노드 생성]
key 000900030006000510, Value 03
// 새로만든 숏노드를 풀노드의 15번에 설정
set new node @ 15

// 네번째 데이터 삽입
Insert [10 7 7 13 3 9 7], [4]
000a00070007000d00030009000710
[S] matchlen = 5 // a,7은 여전히 겹침
key matched
[F] // 이미 분기가능한 풀노드인데 7자리가 비어있지 않다.
// 7자리에 해당하는 숏노드에서 추가로 몇자리가 겹치는지 확인
[S] matchlen = 5 // 뒤에 두자리가 추가로 겹침 d,3
CreateFullNode // 분기를 위한 풀노드 생성
// 3자리 비었음
// 숏노드이 값은 7
try insert 3
[N] Create [S]
key 000710, Value 02
// 9자리 비었음, 숏노드의 값은 7
try insert 9
[N] Create [S]
key 000710, Value 04
// 새로만든 풀노드의 값은 숏노드 d3의 값으로 설정되며
short node key 000d000300, Value branch
// 숏노드 d3을 풀노드의 7번에 설정
set new node @ 7

드디어 윗그림과 비슷해 졌습니다.

만약 5번째 키값이 a,7,7,d,3 인 경우엔 어떻게 될까요?
Insert [10 7 7 13 3], [5]
000a00070007000d000310
[S] matchlen = 5
key matched
[F]
[S] matchlen = 4
CreateFullNode // 풀노드 생성하여 분기 준비
// 신규 풀노드엔 0번엔 기존에 연결되었던 풀노드를
try insert 0 &{[<> <> <> 842351051952 <> <> <> <> <> 842351052032 <> <> <> <> <> <> <>] {[] 0 %!d(bool=true)}}
key len = 0 value
// 신규 풀노드의 16번째 값 필드에 05를 쓰게 됩니다.
try insert 16 05
key len = 0 value
short node key 000d0003, Value branch
set new node @ 7

그리고 최종출력!! (새로만든 풀노드에 0번에 insert를 하는 행위가 replace였습니다.)

입력마다 트라이의 내용이 어떻게 되는지 출력해본 결과도 함께 첨부합니다.