Klaytn State Trie Cache Series #3: State trie cache miss 계산하기

전체 포스팅 목록은 여기에서 확인하세요.

Klaytn은 블록체인 플랫폼의 성능을 개선하기 위해 다양한 노력들을 했습니다. 아래의 포스팅을 통해 state trie cache 성능 개선 과정을 살펴보고자 합니다.

1. Cache 문제 원인 파악하기
2. 최적의 cache 찾기
3. State trie cache miss 계산하기
4. Cache Size Tuning 하기

전 포스트에서 메모리 과사용 문제를 해결하기 위해 다양한 cache들을 비교하였고, Fastcache가 Klaytn에는 가장 적합한 캐시임을 확인했습니다. 이번 포스트에서 cache miss에 영향을 미치는 요인들을 살펴보고, 수학적으로 식을 정의하고, 그 식이 맞는지 테스트를 통해 검증합니다.

Cache miss 계산을 위한 가정

Cache miss의 계산은 다음과 같은 사항들을 가정하여 계산하였습니다.

[1] 먼저, 계산하는 transaction 대상은 KLAY 전송입니다. 보내는 account와 받는 account 모두 보유량이 바뀌어야 하기 때문에, KLAY 전송 transaction 1개에 2개의 account 값이 바뀌어야 합니다.

[2] contract가 생성/수정되지 않습니다. 실제 네트워크는 contract에 의해 state trie leaf에 sub-trie가 추가됩니다. contract에 대한 호출이 발생하지 않고, 따라서 추가적인 노드가 생성되지 않는다는 가정 하에 계산됩니다.

[3] trie는 complete tree 형태입니다. Account address의 hash를 trie의 키로 사용하고 있는데, 이 hash의 substring이 겹치는 빈도는 매번 다르게 나타납니다 . 따라서, 실제 네트워크에서는 trie의 형태가 다양하게 생성될 수 있습니다.

[4] 중복 선택은 제외하였습니다. 예를 들어, 한 블록 안에 A가 B에게, B가 C에게 보내는 transaction (B가 두 번 이상 바뀌는 일)은 발생하지 않는다고 가정합니다. 그렇다면 항상 하나의 transaction에 2개의 account, 즉 2개의 leaf가 바뀝니다. Klaytn에서는 1백만 이상의 account에 대해 고려하고 있고, 1백만의 account에서 1000 TPS(Transactions per second)로 블록이 생성되는 경우 최대 0.006%의 오차가 발생할 수 있기 때문에, 중복 선택을 제외하고 계산하여도 오차가 크지 않을 것이라고 추측 가능합니다.

Cache miss 계산하기

캐시에 저장되는 entry는 state trie node입니다. 각 state trie는 tree 모양을 하고 있는데, 이를 다음과 같이 삼각형으로 표현하고자 합니다.

위 그림의 연회색 사각형이 cache를 의미하고, 안의 삼각형들이 각 block에서 추가된 state trie를 의미합니다. 이런 모형을 바탕으로 cache miss 계산에 대해 설명 드리고자 합니다.

Cache miss는 위와 같은 요소에 영향을 받습니다. 각 값이 어떻게 설정되고 어떤 관계를 가지는지 알아보겠습니다.

Total Accounts, Active Accounts, Updated Accounts

TotalAccounts는 trie에 존재하는 전체 account 를 의미합니다. Trie의 크기와 깊이에 영향을 줍니다. ActiveAccounts는 활성 사용자들을 나타내며, TotalAccounts 중 임의로 선택된 account들입니다. 트랜잭션 생성에 사용하는 account는 ActiveAccounts 중에서 선택됩니다. ActiveAccounts의 수는 TotalAccounts의 수보다 작거나 같은 값을 가질 수 있습니다. 실제 계산과 테스트에서 TotalAccounts의 수는 1M ~ 50M의 값을, ActiveAccounts의 수는 TotalAccounts 수의 20%~100%되는 값을 선택하였습니다.

[1] TotalAccounts와 ActiveAccounts를 분리시킨 이유는 현실 네트워크를 반영하기 위해서 입니다. 또한, 하위 계산식에서 볼 수 있듯 각 지표가 영향을 미치는 요소가 다릅니다. TotalAccounts는 trie의 크기와 depth에, ActiveAccounts는 트랜잭션를 생성할 때 사용하는 account에 영향을 미칩니다. ActiveAccounts가 TotalAccounts와 같은 경우도 생길 수 있습니다.

[2] TPS는 초당 발생하는 트랜잭션을 의미합니다. 트랜잭션 마다 두 개의 account에 변경사항이 발생하기 때문에 실제로 변경되는 account는TPS ྾ 2가 됩니다. 만약, ActiveAccounts 수가 TPS ྾ 2보다 작거나 같으면, 매 블록에서 사용하는 account는 항상 동일한 값이 됩니다. 따라서, 바로 전 trie에서 해당 account를 찾을 수 있게 됩니다. 이럴 경우 cache miss가 날 확률은 0이 됩니다.

[3] UpdatedAccounts는 매 블록에서 수정된 account를 의미합니다. UpdatedAccounts의 수는 ActiveAccounts의 수보다 작거나 같은 값을 가질 수 있습니다. UpdatedAccounts에 대한 자세한 설명은 Leaf 수 계산하기에서 하겠습니다.

Leaf 수 계산하기

그림의 ‘N번째 trie’는 새로 추가되는 block의 state trie를 나타냅니다. 여기서 노란색 동그라미가 leaf node를 의미합니다. 이 때, 새로 추가되는 block의 state trie를 UpdatedStateTrie, 이 trie의 크기를 UpdatedStateTrieSize라고 하겠습니다.

KLAY 전송 transaction으로 1000TPS가 생성된다면, 2개의 account (보내는 account와 받는 account)를 임의로 선택하는 과정 1000번이 필요합니다. 즉, account 2000개가 선택되기 때문에 2000개의 leaf가 새로 생성된다고 할 수 있습니다. 이 때, 새로 추가된 account 수를 UpdatedAccounts라고 하며, 1000TPS가 발생할 때 UpdatedAccounts(혹은 Leaf 수)은 2000입니다.

Cache에 저장 가능한 Trie 수 계산하기

Cache에 저장 가능한 trie 수는 cache size에 trie size를 나눈 값(CacheSize / UpdatedStateTrieSize)입니다. 이 값을 다음 계산부터 r이라고 표시하겠습니다.

CacheSize는 가용한 메모리 용량에 따라 사용자가 정의할 수 있는 파라미터이며, UpdatedStateTrieSize는 TotalAccounts와 TPS에 의해 계산될 수 있습니다. TotalAccounts가 1M 이면서 1000 TPS로 트랜잭션이 실행될 경우에 필요한 UpdatedStateTrieSize의 값은 아래의 표와 같이 계산할 수 있습니다.

위와 같은 계산을 통해 Trie의 depth 별로 허용할 수 있는 노드 수를 알 수 있습니다. 예를 들어 1M의 account가 있다면, 최소 6th depth의 trie가 생성됩니다. 이 때 1000 TPS가 발생하였다면, 2000개의 leaf가 생성되며 6th depth에 2000개의 노드가 매 블록 생성됩니다. Leaf 노드 (6th depth의 노드)가 2000개 생성 되었기 때문에 5th depth에는 최대 2000, 4th depth에는 2000, 3th depth에는 최대 256, … 이 생성됩니다. 이를 모두 더하면 총 6273개의 노드가 매 블럭마다 생성되며, 평균 node 크기(200B)와 key 길이(16B)를 곱하면 6273 * (200 + 16) = 1.29MB (UpdatedStateTrieSize)가 새로 생성되는 것을 알 수 있습니다.

TotalAccounts와 TPS 별로 UpdatedStateTrieSize계산은 다음 링크에서 확인할 수 있습니다. (링크의 계산은 중복 조합과 header size가 고려되었습니다.)

Cache Miss 계산하기

n번째 trie와 n-1번째 trie에서 account 하나씩 랜덤하게 선택했을 때, 이 둘이 같을 확률은 1/AcgtiveAccounts입니다. 반대로, 이 둘이 다를 확률은 1–(1/ActiveAccounts) 입니다.

n번째 trie에 있는 account 1개가 n-1번째 trie에 있지 않을 확률은 앞에서 구한 식에 n-1번째 trie에서 생성된 UpdatedAccounts(leaf 수) 만큼 제곱 해주면 됩니다. 따라서 식은

입니다. 똑같은 방식으로, n번째 trie에 있는 account 1개가 cache에 있는 모든 trie에 있지 않을 확률은

입니다. 이 식은 n번째 trie에 있는 account 1개가 cache에 있지 않을 확률, 즉 1개의 entry가 cache miss날 확률과 같습니다.

마지막으로, n번째 trie의 모든 account가 cache에 저장되어 있지 않을 확률은 앞의 식을 구하기 위해서

을 UpdatedAccounts만큼 시행하면 됩니다. 따라서,

입니다.

테스트 결과

Cache miss 계산식을 확인하기 위해 여러 조건에 따라 테스트를 진행하였습니다. ActiveAccounts, TPS, 또는 TotalAccounts만 변화시켰을 때의 CacheMiss를 계산하고 테스트를 통해 이를 확인하였습니다. 각 테스트의 자세한 계산식과 결과는 스프레드시트에서 확인하실 수 있습니다. 다음 표는 Active Accounts를 변화시켰을 때 cache miss를 계산한 것입니다.

CacheSize가 512MB, 1024MB, 2048MB, 4096MB, 8192MB일 때, 그리고 ActiveAccounts가 1M, 0.8M, 0.5M, 0.3M, 0.2M일 때 확인하였습니다. 이 경우들에 대한 계산값과 측정값의 오차 평균은 2.86으로 비슷한 값을 나타내고 있는것을 확인할 수 있습니다.

이 포스팅을 통해, 변경되는 state trie의 크기를 결정짓는 요소는 TotalAccounts, ActiveAccounts, TPS, Trie node size인 것을 알 수 있었습니다. Cache size가 주어졌을 때, 위 요소를 기반으로 cache miss가 얼마나 발생할 수 있는지 예측할 수 있으며, 또한 위 요소들을 기반으로 최적의 cache size를 도출할 수 있습니다. 하지만 TotalAccounts, ActiveAccounts, UpdatedAccount를 계속 추적하면서 최적의 cache size를 동적으로 찾는 것은 아주 어려운 문제이며, 최적의 cache size를 찾더라도 physical memory size를 고려하여 재조정하여야 합니다. 최적의 cache size를 동적으로 조절하는 방법은 계속하여 고민하고 발전시켜 나갈 예정입니다.

다음 포스팅에서는 주어진 physical memory를 기반으로 어떻게 cache size를 설정할 수 있는지 알아보겠습니다.