Geth Trie insert

Trie insert 테스트

trie_test.go 의 insert를 통하여 이더리움의 머클 페트리시아가 어떻게 데이터를 Insert하는 디버그 과정

trie := newEmpty()

updateString(trie, "doe", "reindeer")

updateString(trie, "dog", "puppy")

updateString(trie, "dogglesworth", "cat")

trie_test.go

위 코드를 따라가면

trie.go 의 trie.Update(key,value) 메소를 따라 간다

func (t *Trie) Update(key, value []byte) {

   //트라이에 변경을 시도하려는 함수 호출

   if err := t.TryUpdate(key, value); err != nil {

      log.Error(fmt.Sprintf("Unhandled trie error: %v", err))

   }

}

trie.go의 Update메소드

다시 trie_test.go로 돌아가서 Key: "doe"와 value: "reindeer"를 삽입하는 과정을 디버그 한다.

Trie.go Update 메소드 -> inset 메소드 -> inset메소드를 재귀적으로 호출하는 로직으로 트라이에 데이터를 입력시킨다.

먼저 머클 페트리시아의 데이터 구조 도식을 확인

머클 페트리시아 트리는 이더리움 계정의 상태 정보를 담고 있는 자료구조이다.

세개의 노드로 구성 되어 있으며

각 노드는

1. 확장 노드
2. 브렌치 노드
3. 리프 노드로 구성

로 구성 되어 있으면 그림에서 Simplified World State를 인풋으로 트라이를 구성한다.

다시 소스 분석으로 돌아와서 Geth의 소스 코드에서 각 노드에 대한 정보를 살펴 보자

확장 노드와 리프 노드는 ShortNode라는 구조체로 정의 돼 있고, 브렌치 노드는 fullNode로 구성 되어 있다.

shortNode struct {

   Key   []byte

   Val   node

   flags nodeFlag

}

shortNode

fullNode struct {

   Children [17]node // Actual trie node data to encode/decode (needs custom encoder)

   flags    nodeFlag

}

fullNode

trie.go 에서 Update메소드를 실행 시키고 tryUpdate에서 key값을 바이트에서 16진수로 변환 시킨 후 Value 값의 길이가 0이 아니면 트라이에 인서트를 시도한다

func (t *Trie) TryUpdate(key, value []byte) error {

   //key를 16진수로 바꾸는 함수 실행

   k := keybytesToHex(key)

   // value가 존재하면 트라이에 데이터를 삽입

   if len(value) != 0 {

      _, n, err := t.insert(t.root, nil, k, valueNode(value))

      if err != nil {

         return err

      }

      t.root = n

   } else {

      _, n, err := t.delete(t.root, nil, k)

      if err != nil {

         return err

      }

      t.root = n

   }

   return nil

}

trie.go의 TryUpdate메소드

16진수로 변환시키는 이유는 위 그림에서 확장노드에 nibble이라고 되어 있는 부분을 볼 수 있다 nibble은 4bits를 나타내므로 로직에 따라 16진수로 변환한다. 잘 모르겠다면 16진수 변환 하는 방법 참조

key 에 doe value에 reinder를 입력하때

Trie에 아무런노드가 없으므로

case nil:

   

   return true, &shortNode{key, value, t.newFlag()}, nil

trie.go 의 insert메소드 중 일부

새로은 shortNode를 리턴하고 이 노드가 루트로 된다

다음 key: dog value: puppy가 들어가는 경우

위에서updateString(trie, "doe", "reindeer")가 실행 된 상태에서 다른 값을 삽입 하는 경우

case *shortNode:

   //prefix를 구한다.

   matchlen := prefixLen(key, n.Key)

   // If the whole key matches, keep this short node as is

   // and only update the value.

   //prefix가 모두 일치 할 경우

   if matchlen == len(n.Key) {

      dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)

      if !dirty || err != nil {

         return false, n, err

      }

      return true, &shortNode{n.Key, nn, t.newFlag()}, nil

   }

   // Otherwise branch out at the index where they differ.

   //prefix를 제외한 나머지 부분을 처리하는 부분

   branch := &fullNode{flags: t.newFlag()}

   var err error

   //부모 노드였던 데이터의 불일치 부분을 브렌치 노드를 통해 연결시키는 부분

   _, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)

   if err != nil {

      return false, nil, err

   }

   //현재 입력으로 전달받은 데이터의 불일치 부분을 브렌치 노드를 통해 연결시키는 부분

   _, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)

   if err != nil {

      return false, nil, err

   }

   // Replace this shortNode with the branch if it occurs at index 0.

   //일치하는 부분이 없다면 리프노드가 된다.

   if matchlen == 0 {

      return true, branch, nil

   }

   // Otherwise, replace it with a short node leading up to the branch.

   //현재 노드의 prefix를 갱신 시키고 브렌치 노드를 연결 시키는 부분

   return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil

trie.go 의 insert메소드의 일부

첫번째로 일치하는 prefix를 구한다.

func prefixLen(a, b []byte) int {

   var i, length = 0, len(a)

   if len(b) < length {

      length = len(b)

   }

   for ; i < length; i++ {

      if a[i] != b[i] {

         break

      }

   }

   return i

}

encoding.go의 prefixLen메소드

코드에서 볼수 있듯이 바이트로 된 코드가 불일치하는 인덱스를 리턴한다.

다시 inset메소드로 돌아와서 일치하는 부분을 제외한 현재 노드의 value와 입력하려는 value를 가지고 브렌치 노드를 경유해 리프 노드를 구성한다.(파란색 부분)

유심히 보아야할 부분은 값을 리턴할 때 확장 노드를 변경 시키는 부분을 유심히 보아야하는데 Key값이 prefix가 되고 branch노드를 자식으로 가지고 있는 것을 볼 수 있다.

즉 확장노드는 리프 노드 중에 가장긴 prefix를 키값으로 가지고 있는 구조라 보면 된다.

다음 

updateString(trie, "dogglesworth", "cat") 을 삽입 하는 방법에 대해 설명

위에서 키가 doe와 dog인 키를 삽입해서 prefix가 do인 부분을 가지고 있는 루트를 생성 했다 정확히 do를 헥사 코드로 가지고 있다

입력하려는 키 dogglesworth는 루트가 가지고 있는 prefix와 정확히 일치한다는 것을 알 수 있다.

case *shortNode:

   //prefix를 구한다.

   matchlen := prefixLen(key, n.Key)

   // If the whole key matches, keep this short node as is

   // and only update the value.

   //prefix가 모두 일치 할 경우

   if matchlen == len(n.Key) {

      dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)

      if !dirty || err != nil {

         return false, n, err

      }

      return true, &shortNode{n.Key, nn, t.newFlag()}, nil

   }

   // Otherwise branch out at the index where they differ.

   //prefix를 제외한 나머지 부분을 처리하는 부분

   branch := &fullNode{flags: t.newFlag()}

   var err error

   //부모 노드였던 데이터의 불일치 부분을 브렌치 노드를 통해 연결시키는 부분

   _, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)

   if err != nil {

      return false, nil, err

   }

   //현재 입력으로 전달받은 데이터의 불일치 부분을 브렌치 노드를 통해 연결시키는 부분

   _, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)

   if err != nil {

      return false, nil, err

   }

   // Replace this shortNode with the branch if it occurs at index 0.

   //일치하는 부분이 없다면 리프노드가 된다.

   if matchlen == 0 {

      return true, branch, nil

   }

   // Otherwise, replace it with a short node leading up to the branch.

   //현재 노드의 prefix를 갱신 시키고 브렌치 노드를 연결 시키는 부분

   return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil

정확히 일치 함으로 빨간색으로 칠해진 코드를 수행한다.

코드를 간략히 설명하면 일치하지 않은 부분과 현재 노드의 val값 여기서는 자식인 브렌치 노드가 된다.

위 코드를 따라 삽입을 시키면

case *fullNode:

   //prefix가 모두 일치 할 경우

   dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)

   if !dirty || err != nil {

      return false, n, err

   }

   //리프 노드 구하는 부분

   n = n.copy()

   n.flags = t.newFlag()

   n.Children[key[0]] = nn

   return true, n, nil

trie.go insert매소드의 일부

브랜치 노드의 타입은 fullNode이므로 위의 코드가 실행 되고

prefix matched index +1비트 노드에 새로운 노드를 추가한다

위의 그림에서 브랜치 노드가 자식을 가지고 있는 부분을 참조 하면 이해가 쉽다

위 그림은 이해를 쉽게 돕기 위해 대략적으로 돌아가는 모습을 그린 그림 입니다.