Klaytn State Trie Cache Series #3: Calculating State Trie Cache Misses

See the list of articles here.
🇰🇷: Klaytn State Trie Cache Series #3: State trie cache miss 계산하기

Improving the blockchain platform has been one of Klaytn’s top priorities. In this series of articles, we would like to walk you through the journey of improving the performance of the state trie cache.

1. Identifying the Cache Problem
2. Searching for the Optimal Cache
3. Calculating State Trie Cache Misses
4. Tuning Cache Size

In our previous post, we compared various caches to come to the conclusion that Fastcache is the most optimal choice for Klaytn. In this post, we will look at some of the factors that determine the occurrence of cache misses, define some formulas and test them out.

Assumptions

Before we calculate cache misses, we will first make the following assumptions:

[1] First, in this article, we will be limiting our focus to KLAY transfer. Since the balances of both the sender and the recipient change, the state of two accounts change per one KLAY transfer transaction.

[2] No contract is created nor modified. On a real network, sub-tries can be added on the state trie leaf through a contract execution. But here, the assumption is that no calls for a contract will be made, hence no extra nodes.

[3] Trie is in the form of a complete tree. The hash of the account address is used as the trie’s key, and the common hash substrings occur at different frequencies each time. Therefore, the trie may appear in diverse forms in the actual network.

[4] Duplicated accounts in a block have been excluded. For example, we rule out the possibility that transactions from A to B, and B to C can take place within a single block (B’s state won’t change more than once). Then, for each transaction, two accounts (two leaves), will always undergo changes. With Klaytn, we are talking about more than a million accounts, and when blocks are created at 1000 TPS, the percentage difference is 0.006%. (We are considering 1000~4000 TPS, so 0.006% is the maximum difference.) It can therefore be safely assumed that excluding the duplicates will not significantly affect the calculation.

Calculating Cache Misses

State trie node is the base unit that gets stored in the cache. Each state trie takes the form of a tree, and is simplified as a triangle in the picture below:

The gray colored rectangle represents the cache, and each triangle represents the state trie of each block. This is the starting point for us to look at how to calculate cache misses.

Factors influencing cache misses are shown in the above image. Let’s look at how they are determined and how they are related to one another.

Total Accounts, Active Accounts, Updated Accounts

The TotalAccounts variable refers to the number of all accounts that exist in the trie. They affect the size and depth of the trie. ActiveAccounts simply represents the number of active users, randomly selected among the total accounts. The account used for generating transactions is chosen among the active accounts. Active accounts may be less than or equal to total accounts. In this post, the value for TotalAccounts was chosen between 1M ~ 50M, and ActiveAccounts between 20~100% of the former, reflecting the main network.

[1] The reason why TotalAccounts and ActiveAccounts are separated is to stay true to reality. And as the formulas below demonstrate, each factor is linked to different elements: TotalAccounts the size and depth of the trie, ActiveAccounts the pool of the account used for transaction. ActiveAccounts could have the same value as TotalAccounts.

[2] Since a couple of accounts are selected for every transaction, the number of the changed accounts have TPS ྾ 2. If ActiveAccounts is less than or equal to TPS ྾ 2, the account used for each block always have the same value. Therefore, it is possible to find that account in the preceding trie. In this case, the possibility of a cache miss is 0.

[3] UpdatedAccounts represents the modified accounts in each block. The value for UpdatedAccounts is smaller than or equal to that of ActiveAccounts. More details on UpdatedAccounts will be dealt with in Counting Leaves.

Counting Leaves

Trie #n in the picture represents the state trie of the latest block and the yellow circles are the newly created leaf nodes. We will refer to the new block’s state trie as UpdatedStateTrie and its size as UpdatedStateTrieSize.

If value transfer transactions are created at 1,000 TPS, two accounts ( the sender and the receiver) have to be randomly selected 1,000 times. A total of 2,000 accounts will be selected, which will henceforth be referred to as UpdatedAccounts. When 1000 TPS are being processed, the UpdatedAccounts stand at 2000.

Calculating the Number of Tries Stored in Cache

The number of tries that can be stored in the cache is found by dividing the trie size by cache size (CacheSize / UpdatedStateTrieSize). This value will be referred to as r.

CacheSize is a parameter that can be defined by the users depending on the available memory. UpdatedStateTrieSize can be calculated with TotalAccounts and TPS. The UpdatedStateTrieSize for transactions to be executed with a million TotalAccounts and 1000TPS can be calculated in the following table:

From seeing the above calculation, we can calculate the number of permitted nodes for each Trie’s depth. For example, for a million accounts, a trie whose depth is at least six is created for a block. And if 1,000 TPS took place, 2,000 leaves would be generated with 2,000 new nodes for every block at a depth of 6. Since 2,000 leaf nodes (6-block-deep state trie nodes) were created, there would be a maximum of 2,000 nodes at a depth of 5, 2,000 nodes at a depth of 4, and a maximum of 256 nodes for a depth of 3, … and so on. With that, a total of 6,273 nodes will be created for each block. Average node size (200B) multiplied by the average key length (16B) can be written as 6,273 * (200 + 16) = 1.29 MB (UpdatedStateTrieSize).

The calculation of UpdatedStateTrieSize for TotalAccounts and TPS can be found in this link. (Repetitive combinations and header size have been included in the calculations in the link.)

Calculating Cache Miss Rate

If we were to randomly select one account from trie #n and trie #n-1 respectively, the probability of these two being the identical can be expressed as 1/ActiveAccounts. On the other hand, the probability that they will be different is 1–(1/ActiveAccounts).

The probability that an account in the trie #n is not included in trie #n-1 can be found by raising the above formula to the number of UpdatedAccounts created in trie #n-1, which looks like this:

Similarly, the probability of an account in trie #n not being included in all tries in the cache can be found using this formula:

This formula represents the probability of an account in trie #n not being stored in the cache, that is, the probability of cache miss for one entry.

Lastly, we want to find the probability that all accounts in trie #n are not stored in the cache. To do that, we multiply the following with UpdatedAccounts.

And there we have it.

Test Results

To verify the cache miss calculation formula, we ran various tests under different circumstances. We calculated the CacheMiss with diverse ActiveAccounts, TPS, and TotalAccounts values. You can find the detailed calculation as well as results in this spreadsheet. The following table shows the cache misses with the different number of Active Accounts.

We have the results for 512MB, 1,024MB, 2,048MB, 4,096MB and 8,192MB of CacheSize, as well as for 1M, 0.8M, 0.5M, 0.3M, 0.2M of ActiveAccounts. The average cache miss error for the estimated and measured values is 2.86, which is relatively subtle.

In this post, we learned that the factors for the changing state trie size were TotalAccounts, ActiveAccounts, TPS, and Trie node size. We calculated cache misses for a given cache size, and also derive the optimal cache size based on the above factors. But dynamically finding an optimal cache size while tracking TotalAccounts, ActiveAccounts, and UpdatedAccounts is a very tricky issue. It requires continuous readjustment considering the physical memory size, even if an optimal cache size is found. Dynamic readjustment of the cache size is one of the areas that we will be continuing to improve in the future.

In our next post, we will demonstrate how to determine cache size based on a given physical memory.