Klaytn State Trie Cache Series #3:?计较State trie cache miss
Klaytn为了提高区块链平台的机能，做了很多方面的尽力。我们将通过下列文章先容?state trie cache机能改进进程。
???确认Cache问题的原因
???寻找最佳的Cache
???计较State trie cache miss
???举办?Cache Size Tuning
在上一篇，我们为了办理内存利用过多的问题，对多个cache举办了较量，并发明Fastcache是最符合Klaytn的cache。下面我们将探讨造成cache miss的各类因素，并列出数式后，通过测试举办验证。
Cachemiss计较前的假设
在举办Cache miss计较前，我们的假设如下：
首先，transaction计较工具是KLAY传输。由于发送和吸收的账户均需改变存储量，因此，1次KLAY传输生意业务，需要有2个账户变量。
不行生成或修改智能合约。在实际运作中，按照智能合约，state trie leaf上会生成sub-trie。而在本篇测试中，不会运作智能合约，因此也不会发生新的节点。
Trie的形态是complete tree。我们利用的trie key是账户地点的哈希值，而该哈希值的substring重叠频率每次城市纷歧样。因此在实际环境中，trie的大概会泛起多种形态。
本篇解除了反复选择的环境。简朴来说，我们假设在一个区块中，不会呈现?A对B、B对C传送事务(即B会呈现2次以上的变革)的环境。因此，本篇测试中，1次事务有2个账户，即拥有2个leaf变量。Klaytn估量会拥有1百万个以上的账户，当1百万个账户以1000 TPS生成区块时，误差上限为0.006%，因此我们认为，就算在测试中解除反复选择的环境，也不会存在太大的毛病。
Cache miss计较
存储在cache上的entry是state trie node。每个state trie泛起树状的形态，我们将其具象为三角形，如下图。
上图中浅灰色方框就是cache，内里的三角形就是每个区块生成的state trie。接下来，我们将凭据这个形态对cache miss计较举办说明。
对Cache miss造成影响的因素如上图。下面，我们将先容数值发生的道理和各数值之间的干系。
TotalAccounts是指trie内的所有account，会抉择Trie的巨细和深度。ActiveAccounts是指活泼账户，是TotalAccounts中随机选择的账户。用于生成生意业务的账户将从ActiveAccounts中选取。ActiveAccounts的数量不大于TotalAccounts的数量。在实际计较和测试中，我们将TotalAccounts的数量设定在1M ~ 50M，ActiveAccounts的数量占TotalAccounts的20%~100%。
[1]?之所以将TotalAccounts和ActiveAccounts分隔，是为了反应实际运行时的环境。在下面的数式中，我们将看到每个指标造成的影响各有差异。TotalAccounts会对trie的巨细和深度发生影响，ActiveAccounts会对用于生成transaction的account发生影响。
也会呈现ActiveAccounts和TotalAccounts造成沟通影响的环境。
[2] TPS是指每秒生成的生意业务。由于每次生意业务会有2个账户呈现变量，所以账户的实际变量为TPS???2。假如ActiveAccounts的数量小于可能便是TPS??2，每个区块所利用的账户将会保持同一个数值。这样一来，我们就可以在上一个trie里找到该account。在这样的环境下，呈现cache miss的几率为0。
[3]UpdatedAccounts是指每个区块里被修改的账户。UpdatedAccounts的数量小于可能便是ActiveAccounts的数量。我们将在Leaf数的计较中对UpdatedAccounts举办具体的先容。
Leaf数的计较
上图中，“第N个trie”是指新增区块的state trie，黄色的小圆圈代表leaf node。我们将新增区块的state trie称作UpdatedStateTrie，将该trie的巨细称作UpdatedStateTrieSize。
若在KLAY传输transaction中生成1000TPS，意味着随机选择2个账户(发送和吸收的account)的进程将反复1000次。换句话说，被选择的account有2000个，会新增2000个leaf。这时，我们将新增的账户数量称作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的计较要领如下表。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
