TechatKlaytn技术系列：性能改善过程

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的计算方法如下表。

通过以上计算，我们可以得出不同的Trie depth可容纳的节点数量。例如，1M的账户最少可生成6th depth的trie。这时，若存在1000 TPS，将会生成?2000个leaf，6th depth上的每个区块上就会出现2000个node。由于Leaf node(6th depth的node)有2000个，5th depth最多为2000，4th depth为2000，3th depth最多为256，以此类推。总的来说，每个区块会生成共6273个node，节点的平均大小(200B)乘以key长度(16B)，就可得出新增量，即6273 * (200 + 16) =1.29MB (UpdatedStateTrieSize)。

在下面链接

(https://docs.google.com/spreadsheets/d/1QHk6b9W_UyYTKpxR0zjvt9AQrTAxbigITumvTDjX_P8/edit#gid=478607548)中，可确认分别按照TotalAccounts和TPS计算UpdatedStateTrieSize的结果(链接里的计算中，反映了重复组合及header size)。

Cache Miss的计算

若第n个trie和第n-1个trie各自随意选择1个?account，两者相同的几率为1/AcgtiveAccounts。相反，两者不同的几率则为1–(1/ActiveAccounts)。

第n个?trie中的某个账户不会出现在第n-1个trie内的几率等于第n-1个trie中生成的

UpdatedAccounts(leaf数)对上述数式结果的乘方。该数式如下：

同样，第n个?trie的某个account?不会出现在cache内所有trie的几率则为：

该数式等于第n个?trie的某个账户不会出现在cache的几率，即某个entry出现cache miss的几率。

最后，若要计算第n个trie内的所有账户没有存储在cache的几率，得先按照下列公式进行计算后，

再乘以UpdatedAccounts，因此该数式为：

(注：???为韩语的语气结尾词，相当于中文的“是”或“为”，由于上面的句子中已反映了这个意思，所以这个部分没有可对应的句子或单词)

测试结果

我们为了验证Cache miss计算公式，进行了多种条件的测试。

我们分别对ActiveAccounts、TPS或TotalAccounts进行调整，计算出每个情况下的CacheMiss，并通过测试进行确认。每轮测试的具体数式和结果可参考Spreadsheet。下表是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，也需要根据物理存储规模进行再次调整。因此，我们将继续致力于研究和开发动态调整最佳cache size的方法。

在下一篇，我们将探讨如何基于既定的物理存储设定cache size。

关于Klaytn

项目名称: Klaytn

英文缩写: KLAY

官方网站: https://www.klaytn.com/

项目简介：Klaytn是以服务为中心的企业级分布式信任区块链平台，通过高效的“混合”设计，结合了公有链（分布式数据和控制、分布式治理）和私有链（低延迟、高可扩展性）的最优功能。Klaytn与全球众多知名品牌的参与合作，通过共同的不懈努力，创建可靠的去中心化业务平台。Klaytn治理委员会是一个由跨国企业和组织组成的联盟，负责运营共识节点网络，推动生态系统发展。Kakao 的区块链开发部门「Ground X」已正式推出 Klaytn，并可用于商业用途。

—-

编译者/作者：Klaytn爱好者

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。