Versions Compared

Old Version 10

changes.mady.by.user Dominik Zajkowski

Saved on

compared with

New Version Current

changes.mady.by.user Dominik Zajkowski

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

  1. Work through checkpoint creation (1 step instead of 13 steps) which would reduce the amount of stored tries (less data) 
    Jira Legacy
    serverSystem JIRA
    serverId50130123-f232-3df4-bccb-c16e7d83cd3e
    keyRCHAIN-3415
    1. estimated gain:
      1. store of top level pointerblock (4416 + 4512 + 128) instead of 44992 (80%)
      2. note: this calculation is very imprecise as the change will happen (is possible) in next rspace
    2. Address EmptyPointer stored in Node pointer block. 
      Jira Legacy
      serverSystem JIRA
      serverId50130123-f232-3df4-bccb-c16e7d83cd3e
      keyRCHAIN-3226
      1. encode pointer type in 2 bits, not in 8 bits
      2. explore gain from storing sparse vectorsvectors https://rchain.atlassian.net/projects/RCHAIN/issues/RCHAIN-3227
  2. Continue analysis of rholang AST
    1. we can address the source size (which is constant but it constitutes a 10% or 15% of the data stored)
    2. there is no way of addressing the random state

Trie Merging in RSpace Next

Transfer from A → B, existing wallets.

The experiment was performed on a clean rnode instance with genesis and 

  • vault_demo/0.create_genesis_vault.rho
  • vault_demo/2.check_balance.rho
  • vault_demo/3.transfer_funds.rho

run to prime the data.

What is gathered in the sheet is the result of a second vault_demo/3.transfer_funds.rho run.

https://docs.google.com/spreadsheets/d/1v5MJhKyzu1WgzAQo51rHt0TNXeBOffbQ9bUgldxHeUw/edit?usp=sharing

The trie structure weighs 7020 bytes.

It's easy to observe that there is one central PointerBlock which weighs 4929 bytes.

This cost seems to be very close to the lower bound for any change to the trie. This would dictate that any actions on a block should focus on performing as much actions in memory and committing (checkpointing) as seldom as possible.

This also points to work done in 

Jira Legacy
serverSystem JIRA
serverId50130123-f232-3df4-bccb-c16e7d83cd3e
keyRCHAIN-3453

On a side note: RSpace Next does not hold a separate data bag for replay, so the data is not duplicated.

Thought

One could make a case that the highest level PointerBlocks (let's say 3 levels) will change constantly and will be heavily populated (256 * 32 bytes).

Maybe it would make sense to differentiate them from the pointer blocks that will live lower in the trie and invest in some sort of structure sharing.

But at the time of writing no such structure (that would save space) comes to mind.

At the same time if the deployments passed to trie creation are diverse enough this will become a mute point as the structure will be shared in a limited fashion.

This needs further investigation to merit any further code changes.

Data usage in RSpace Next

ticket: 

Jira Legacy
serverSystem JIRA
serverId50130123-f232-3df4-bccb-c16e7d83cd3e
keyRCHAIN-3484

data referenced:

https://docs.google.com/spreadsheets/d/1MHEWeha6zOhEV39fye-3trZlg50R13jRAjbjvgE2OSw/edit?usp=sharing

typesize
insert-continuation

5043

insert-data

3634
insert-join280
sum8957

Comparing the RSpace Next to original RSpace we can observe: 

  • the data is not doubled as replay runs of the same store
  • there is a new type of data "joins"
  • the original structure took up around 9 565 bytes (GNAT in Leaf) (times two for replay)

Diving deeper into what the data itself is we observe

Datums:

Code Block
collapsetrue
20190606-15:50:17.840;642122de191479453604d09e92f8864d6527b526861493b50126f8356adf8a49;insert-data;1167;1;[{"11112ChXfi25ByoKouxaiUKRSrVXjdQzTUoJBtkw71JVvYNL2NgMDi" : bundle+ {   Unforgeable(0x4d17a5e7e7d1098774b9b9460392d25cd9127a64ecbaec87b99cf4ef79eb5d51) }, "11112SGU8f1D7DfkS98MzadvCPzHKzuiUjukHH8c7RqnffPhVP3Ws9" : bundle+ {   Unforgeable(0x96019b21498dcd36a18e720cc8efd5847edee6ba28ff5c853e836dd95f6f2464) }, "11112pbz6HqE2Lc2T7ojH116U7LkepSewDemoPnf56voiRMpDzVyhe" : bundle+ {   Unforgeable(0xa39baf11a39a13cee1e90f6ccdbaa783b134625d96c9576ced0e74e422ca585a) }, "11112pwq4ZQ634rvTSJqZ4SmWYBWyHv98U46jF9pgmB5LHozWLzJXu" : bundle+ {   Unforgeable(0x73d27b713c2c8466686b9f285b18c2b92329851fbe0a5729b7720b58c3186269) }, "1111GcGEJX6me9vVN5cPGbFHSXepo8BvQ9r9CFcNmYSemHDvdpPZB" : bundle+ {   Unforgeable(0xf25f98897615ae7602bdecb3163bda2808200039bdf1ce1934dc852cf0393c14) }, "1111Ggp3miC6ULewtjtoCw4mB1WywmoU35QNw7z6JUfVqZdxRFxBn" : bundle+ {   Unforgeable(0xbe9f997b0d2aa987cac1b43f21d04c6928cde3c9e669b27f72d2f4ab8f1ba5ff) }, "1111hcuCGNhYcjZ2PHbyRLiZTGY9M1CwgXZDxrABADiLmoXyW2RZT" : bundle+ {   Unforgeable(0xba0e1ec9d909842334650361ec2e7b3da1f14e0058e902998bffec4ddfd8cd15) }, "1111iZYyhMm2tZtAEUevwFTyw9SgwnSCf9Vc3Qk39Gio1k9sHxWUK" : bundle+ {   Unforgeable(0xca5c1739042042c36cf1d422dc815e920810aa7a3cd62115753941357fceb67f) }, "1111sc15PERLugDRdfPHkSfYPpar8i1NcwM5hKsE64HVUG2zCF5sy" : bundle+ {   Unforgeable(0x31caa7b4f5cd32794fc65d12b9bd0a79d033a5754ececc6bf50068077a1161a2) }}]
20190606-15:50:17.840;dbbfa78ff7d7bdfc9f674a5bc78a71350f5140007630846e3e4a3c08e44e55a2;insert-data;198;1;[8600]
20190606-15:50:17.840;999f2cebea94b041378fc9838a7784d8e9b48b3280e4b62cee4769e13f935ef2;insert-data;1876;1;[{54 : (0, 36ed509b74f58de9801175ae055de06f8a371a73ea6bc3a464b7d225dca4e1, (9223372036854775807, bundle+ {   Unforgeable(0xeb58132e9b06ccc10a037ec292c37b76c39841f8b9a25dcc0ad76c592fa78b7f) })), 5a : (0, 5a7c333756a4d02bdac7b44f69b0ee2ec668ccc69fbb3b3da8b3aa92cf70d2, (9223372036854775807, bundle+ {   Unforgeable(0x0483e8263c258cb1daabdd8b5ee19ea4f34f61573ca72b1c9c5f0ce277d9e3f7) })), 5e : (0, 5eaef0e4de87174696209eebf10790716a201ef0af4f2f79c8803d6db10400, (9223372036854775807, bundle+ {   Unforgeable(0xa32c1649f1700469f125ea85f9c2a220072e593ae617213782d738e389639d3b) })), 71 : (0, 39e598adddfd02199c35ae078a7016057ef299c2cc4691d1656b8f62d18fbc, (9223372036854775807, bundle+ {   Unforgeable(0xcaad4e983dedd6c5ae42384b6d87ba6f77997cdf6bb75b8e5f3ffa2133e6b45d) })), dd : (0, ac4303f2a5943d78c94c3cec2dfc31cf19140b0ed0a35caab1808984cec8a6, (9223372036854775807, bundle+ {   Unforgeable(0x4ca8ca1cff2656b3a1f7765bf3819416ce6f9f9e44102229a2622c98cd65de22) })), f5 : (0, d8570a82c39946a013059f222f4710c9eb1ac109933a175baec50266b0e8c9, (9223372036854775807, bundle+ {   Unforgeable(0x263f45f2ca50669ef4011a57d3a10270c1250d52ed99f212a6332d8ffe57d3be) })), c5 : (0, 816250a6b94e12f6cf556146e8398b2c0d14f0586b9a7fc0b41fa9e5c358a5, (9223372036854775807, bundle+ {   Unforgeable(0x10d4824180800daef356857cffca4f51471960b92711df0fd3c3425401149e11) })), ae : (0, a4389cc059a43ce09d1d629a3d7113a33a799cb8b8f6573effa2528083cb5a, (9223372036854775807, bundle+ {   Unforgeable(0x6cd75a683533af49eb9d8cd1d71fc24577cfa6099502eef95668d7a0a9887686) })), e3 : (0, c181f245281a4c6ba407d6af04e495739c1254fd13645f4ae151fe4ee42b01, (9223372036854775807, bundle+ {   Unforgeable(0x61657f51076320deb7358dfcfc1f703be818ee08876c8b8efbfdf6e9d3020bcd) })), f1 : (0, 6f02556e119081a1aa256e6ab976f5d31efae9432aa8c648a950e98350b5f3, (9223372036854775807, bundle+ {   Unforgeable(0x95fcdae5d4db7cf5aa0022bf6dba3f7c21b506fed8f3f4698a570d048ea758bd) })), a6 : (0, ee541718b13689de727ef72a5026144f093359d6c9961994c48d301488cf8b, (9223372036854775807, bundle+ {   Unforgeable(0x61a47068f8b14054beb31fd7b7f580623ff90104c04f7e4dac105ec52f379688) })), 93 : (0, a9b4716e93f5f1a01a460649734262f3e9533bcfb16e43a3264f50420aa32c, (9223372036854775807, bundle+ {   Unforgeable(0x741f6ee13b54ca29cd6e3340e24a781e8cc2739bc4ab5fd1650de54e11040955) })), ca : (0, fd5a3c1d53b541f29ae597b71b837b1439be2515cc93fae092f91ce3a3b01e, (9223372036854775807, bundle+ {   Unforgeable(0xc274979cec5d4e0f9f6ef7b7c1236254b1eeb8869f0dad6df87649a9660c58f9) }))}]
20190606-15:50:17.841;4e30f330755d6b6dc8f54ca16be004db87d88893f5f49d7b3165fa259e248240;insert-data;197;1;[400]
20190606-15:50:17.841;25cbf27ecfc0f25a1d6c81c1be4616a00bb45a0d3509467008d880e82b302a6c;insert-data;196;1;[0]

Continuations:

Code Block
linenumberstrue
collapsetrue
20190606-15:50:17.836;3c1316e73f94b3044f97954d190292e11b5cf88bd871adef29dcde0fc96b2556;insert-continuation;1760;3;match (x-2 >= 0) {
  true => {
    for( @{x0} <- @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)} ) {
      match ((x0 + x-2) >= x0) {
        true => {
          @{x-1}!(true) |
          @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)}!((x0 + x-2))
        }
        false => {
          @{x-1}!(false) |
          @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)}!(x0)
        }
      }
    }
  }
  false => {
    @{x-1}!(false)
  }
};match (x-2 >= 0) {
  true => {
    for( @{x0} <- @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)} ) {
      match (x-2 <= x0) {
        true => {
          @{x-1}!(true) |
          @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)}!((x0 - x-2))
        }
        false => {
          @{x-1}!(false) |
          @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)}!(x0)
        }
      }
    }
  }
  false => {
    @{x-1}!(false)
  }
};for( @{x0} <- @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)} ) {
  @{x-1}!(x0) |
  @{Unforgeable(0x09e1534416a0a03cc0680a50a7a8116b674005316b3d325f3cbafd9bb33d123c)}!(x0)
}
20190606-15:50:17.838;10aab7ee3a588895868250d442f29f60a160944c0bb009298150644a101d4224;insert-continuation;353;1;@{Unforgeable(0xe29fc7b0349439bb273c36a0f719607aa53858a246b788e2d0f248ce5a23c0ca)}!("1111sc15PERLugDRdfPHkSfYPpar8i1NcwM5hKsE64HVUG2zCF5sy", 0, x-1)
20190606-15:50:17.839;002aaf52b691c44c91af2b9d068020ecac6100b20e480a9d660e0099ef00bc60;insert-continuation;427;1;@{x-1}!(bundle0 {   (Unforgeable(0x7e9d36337ccbbab727a21f6c2ed273b0f1142e0eb3427eab5cf50333f0071322), (Unforgeable(0xf43babf465fe04a0be8d1ef3b543f2203fd287a1d6a9fb290c2ca13127210219), "1111sc15PERLugDRdfPHkSfYPpar8i1NcwM5hKsE64HVUG2zCF5sy")) })
20190606-15:50:17.839;1002f77a40953a11781cc0b0bf714ecb8f363a5f46e533e09fbf8f8f9fa6a6a9;insert-continuation;2503;5;new x0 in {
  @{bundle+ {   Unforgeable(0xd8b16a8c4e343834d6491668458ac6ee8f4f85e70e604ce370c6621d275a93a5) }}!("sub", x-2, *x0) |
  for( @{x1} <- x0 ) {
    @{x-1}!(x1, Unforgeable(0xa114647fa0587e970884cafc259ffc7f088cb3e6a51427a5751b742639887c47))
  }
};new x0, x1 in {
  @{Unforgeable(0xd4363a6448e79ca3043294d86906546eb0c3cb642c0beea40c9fea64a6e4fc57)}!("sprout", *x0) |
  for( @{x2} <- x0 ) {
    @{x2}!("deposit", x-2, Unforgeable(0xd4363a6448e79ca3043294d86906546eb0c3cb642c0beea40c9fea64a6e4fc57), *x1) |
    for( @{x3} <- x1 ) {
      match x3 {
        true => {
          @{x-1}!([x2])
        }
        false => {
          @{x-1}!([])
        }
      }
    }
  }
};new x0 in {
  @{x-2}!(bundle0 {   bundle0 {     x-2 } |
  Unforgeable(0xa114647fa0587e970884cafc259ffc7f088cb3e6a51427a5751b742639887c47) }, x-3, *x0) |
  for( @{x1}, @{x2} <- x0 ) {
    match (x1 && (x2 == Unforgeable(0xa114647fa0587e970884cafc259ffc7f088cb3e6a51427a5751b742639887c47))) {
      true => {
        @{bundle+ {   Unforgeable(0xd8b16a8c4e343834d6491668458ac6ee8f4f85e70e604ce370c6621d275a93a5) }}!("add", x-3, x-1)
      }
      false => {
        @{x-1}!(false)
      }
    }
  }
};@{Unforgeable(0xd93eb64c221e94ed10b3c97291af187fe189f851125affe75a63a096cf9a5558)}!("makePurse", 0, x-1);@{bundle+ {   Unforgeable(0xd8b16a8c4e343834d6491668458ac6ee8f4f85e70e604ce370c6621d275a93a5) }}!("value", x-1)

Findings:

  • it's easy to observe that the Datums are divided into two types
    • the interesting part "balances", they take up 196 + 197 + 198 bytes
    • the boring part of maps of revvaults 1167 + 1876
      • Jira Legacy
        serverSystem JIRA
        serverId50130123-f232-3df4-bccb-c16e7d83cd3e
        keyRCHAIN-3535
      • Jira Legacy
        serverSystem JIRA
        serverId50130123-f232-3df4-bccb-c16e7d83cd3e
        keyRCHAIN-3534
    • in this case (rev transfer) the map does not change, so storing it again is just a consequence of not having enough introspection into the data in RSpace 
      Jira Legacy
      serverSystem JIRA
      serverId50130123-f232-3df4-bccb-c16e7d83cd3e
      keyRCHAIN-3528
    • the potential saving by having Datums share data should be of the size of the registry (2900 bytes in this case)
    • in theory this can be achieved by providing peek semantics
  • Continuations consist of the purse contract being created (persisted)
    • it seems that all these pieces should not make it to the tuplespace at all since they will go out of scope post the purse being empty
      • a proposal of making this go away is to introduce a one-time-use purse that will be consumed when money is drained 
        Jira Legacy
        serverSystem JIRA
        serverId50130123-f232-3df4-bccb-c16e7d83cd3e
        keyRCHAIN-3536
      • Jira Legacy
        serverSystem JIRA
        serverId50130123-f232-3df4-bccb-c16e7d83cd3e
        keyRCHAIN-3539
    • it seems that there is a possibility to not persist the continuations over and over but simply point to them with data 
      Jira Legacy
      serverSystem JIRA
      serverId50130123-f232-3df4-bccb-c16e7d83cd3e
      keyRCHAIN-3529
      • this would boil down to a one time cost of the contract in a schematic form ~ 2500 bytes + 1760
      • and a reference with indexes and values stored on each transfer with 7 unforgeable names
      • the gain here is not obvious and needs further inspection

Trie vs data in RSpace Next

In the above example it looks like the data and the trie are taking up roughly the same amount of data but that is misleading. There is an initial cost to making a new trie but its growth will not be linear to the amount of data put into the tuplespace (TODO this should be shown).

It looks like the next steps is to make the data take up as little space as possible.