Atree Register Inlining and Data Deduplication

[fxamacker]

Updates epics #292 https://github.com/onflow/flow-go/issues/1744 Updates #296 #297 #347 #348 https://github.com/onflow/cadence/issues/1854 Required by Cadence Integration with Atree https://github.com/onflow/cadence/issues/2809 Required by Atree Storage Migration:

• https://github.com/onflow/flow-go/issues/4576 lists migration TODOs.
• https://github.com/onflow/flow-go/pull/4633. Dry-runs can begin migration tests and optimizations without Atree Inlining but will eventually need to include this PR before spork.

NOTE: some of the above updated issues will be closed by this PR:

• after integration with Cadence (in onflow/cadence repo) and
• after long-running smoke tests run longer (some have been running locally since Oct 5 and Oct 6).

Problem

Memory use on execution nodes, register count, and growth rate can be improved.

Currently, every array or map are stored in its own slab and parent slab refers to child array or map by SlabID.

The current approach can lead to many small slabs, especially for Cadence data structures with multiple nested levels.

Another aspect is duplicate data, especially when encoding nested Cadence composites. The design of atree inlining already requries changing the encoding format, so use this opportunity to also deduplicate data when encoding nested composites.

Changes

Reduce register count by inlining and optimize encoding size by deduplicating Cadence composite types within slabs.

1. Inlining. This commit inlines child array/map in parent slab when:

   • child array/map fits in one slab (root slab is data slab)
   • encoded size of inlined child array/map is less than the max inline size limit enforced by parent

2. Data deduplication. This commit optimizes encoding size by:

   • reusing inlined array types
   • reusing seed, digests, and field names of inlined composite types

Also update debugging code to handle inlined array/map element.

TODO

In this PR

• [x] add more tests
• [x] cleanup some of the tests

Atree Inlining Part 2

Open new PR to add support for inlinability of child values returned by iterator (requires PR #329)

Cadence Integration

Open new PR in onflow/cadence to integrate with Cadence.

---

• [x] Targeted PR against main branch
• [x] Linked to Github issue with discussion and accepted design OR link to spec that describes this work
• [x] Code follows the standards mentioned here
• [x] Updated relevant documentation
• [x] Re-reviewed Files changed in the Github PR explorer
• [x] Added appropriate labels

[codecov-commenter]

Codecov Report

Attention: 1110 lines in your changes are missing coverage. Please review.

Comparison is base (1e6ec55) 64.93% compared to head (5f1de0a) 62.62%.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #342 +/- ## ========================================== - Coverage 64.93% 62.62% -2.31% ========================================== Files 14 15 +1 Lines 8811 10559 +1748 ========================================== + Hits 5721 6613 +892 - Misses 2356 3004 +648 - Partials 734 942 +208 ``` | [Files](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow) | Coverage Δ | | |---|---|---| | [encode.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-ZW5jb2RlLmdv) | `80.72% <100.00%> (+4.25%)` | :arrow_up: | | [storable.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-c3RvcmFibGUuZ28=) | `59.37% <ø> (ø)` | | | [basicarray.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-YmFzaWNhcnJheS5nbw==) | `49.38% <70.00%> (+0.01%)` | :arrow_up: | | [storage.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-c3RvcmFnZS5nbw==) | `73.09% <52.00%> (-0.60%)` | :arrow_down: | | [typeinfo.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-dHlwZWluZm8uZ28=) | `60.32% <60.32%> (ø)` | | | [map\_debug.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-bWFwX2RlYnVnLmdv) | `43.65% <49.34%> (-8.51%)` | :arrow_down: | | [array\_debug.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-YXJyYXlfZGVidWcuZ28=) | `47.44% <49.04%> (-4.67%)` | :arrow_down: | | [array.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-YXJyYXkuZ28=) | `68.10% <62.09%> (-1.97%)` | :arrow_down: | | [map.go](https://app.codecov.io/gh/onflow/atree/pull/342?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow#diff-bWFwLmdv) | `65.30% <58.52%> (-1.78%)` | :arrow_down: | ... and [1 file with indirect coverage changes](https://app.codecov.io/gh/onflow/atree/pull/342/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=onflow)

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[turbolent]

Fantastic work Faye! 👏

Some notes from the first review session:

• It would be good to document that the "parent pointers" are not stored physically, but are actually functions, in memory (and when they are set). Maybe add some high-level comment to the code and indicate it in the diagrams; they usually show "stored" physical pointers ("storage IDs" (now "slab ID" / "value ID", right?))
• Maybe document (if not already) that the inlining approach is to not inline all slabs that are "inlinable" in the sense of fitting inside of the parent, but that inlinability is determined "as a whole" for a whole value. The example was that, a small array is inlinable if it is just a single data slab, but a larger array consisting of a meta slab and some data slabs is not inlinable, even when the meta slab could fit into the parent
• Maybe document (if not already), that "slab ID" == "value ID", i.e. they share a namespace, and an ID might be used for a slab, but it might also not. Currently, a slab ID could be checked to exist
• As discussed, we might also want to update the child' parent callback when the child is inserted into the container (array and map), e.g. in the Set and Insert operations.

I'll do a proper code review after the next review session. So far the work looks great, well done! 👏

[fxamacker]

@ramtinms @turbolent thanks for the fast PR reviews! I resolved all feedback that may require coding changes.

Ramtin, thanks for suggestions and approval! I will open separate PR to update smoke tests.

Bastian, can you please take another look?

UPDATE: I addressed all feedback including comments. I will open separate PR to update smoke tests and extra linting in CI.

[fxamacker]

@turbolent I found and resolved edge case found while adding comments about how inlining works on Sunday.

While at it, I also refactored, added more checks, and added no-op to parentUpdater we discussed last week. Thanks again for good discussions last week. :+1:

[turbolent]

Fantastic work Faye! 👏

Here are the cleaned up notes I took from the last review session last Thursday. They might not be up-to-date anymore, as you might already have addressed some points since then, so please feel free to disregard if that is the case.

• Maybe add some general/conceptual comments/explanations of how the inlining works, and what operations/cases need to be supported.

  • For example, children need to notify their parent on any mutation.
  • For example, for maps, there are two operations that mutate, set and remove
  • After a mutation, a receiver/container needs to:
  • Notify its parent (if any), because the receiver/container might be itself a child of another container (with notifyParentIfNeeded)
  • Update the child's parent callback, so that the inserted/removed child can notify the receiver/container (with setCallbackwithChild) when that child gets mutated

• In the array/map remove operations, only a storable is returned. Similar, the set operations returns a potentially existing existing storable for the given key.

  However, there might be values for the storable which have parent callbacks. Those callbacks should theoretically be unset. Loading the value for the storable does not make much sense, as current implementations will allocate another, new value.

  I don't quite remember the plan for resolving this. Was the plan to leave the parent callback happening, detect the "invalid" child callback to the "previous" parent, and reject it?

• Sometimes "value" is used in a variable name, even though it refers to a just a storable. For example, there was a case for extistingValue, which was only a Storable. Maybe check naming of such variables and update accordingly to avoid confusion.

• We walked through the example case of inserting a child into a parent, mutating it, removing the child from that parent, mutating it, and then inserting the child into another container, and mutating it.

  • It would be good to have an integration test for this in both atree and Cadence.

  • We noticed that a mutation after the removal (or set operation), atree needs to uninline the child

  • A callback of a child to a previous parent was a fatal error. However, this is likely not an invalid case: The child value is mutated, so notifies its parent (parent callback was not unset, but also could not, see above). Instead of a fatal error, this callback should be a "no-op". Further, when the parent detects such a callback from a previous child, it should now use this opportunity to unset the parent callback from the child.

• We talked through the "singleton value" case: StoredValue might return same, existing value, and might not return a new value. It might be good to not make any assumptions about the nature of the returned value (e.g. that an implementation is required to always return a new value), or at least document the assumptions properly.

  This prevents regressions in the future, where such assumptions might be broken by the user of the library, i.e. Cadence.

• On the Cadence side, there is the implicit invariant that all values stored in an account always reference values in the same account, and never across accounts. We should add defensive assertions for this invariant, i.e. check that the container and child addresses match.

• Finally, we discussed the encoding, in particular, the deduplication of type information.

  When types are dedupliated, there seeds are normalized.

  In atree comments/docstring, in Cadence comments/docstrings, and in the Cadence user documentation, we should emphasize that iteration order is undefined (but deterministic of course), and no assumptions should be made during execution or across transactions. For example, just because iteration over the keys of a dictionary has a particular order in one transaction does not mean that it will be the same in the next transaction.

  The deduplication optimization will change the current behavior, which some users might rely on (but should (have) not).

I will have another look over the changes of the PR today and will open issues for the TODOs on the Cadence side mentioned above.

[turbolent]

@fxamacker Would be good to sync on remaining work, see the (sorry, long) comment above. If there isn't really anything left to be addressed, this should be good to go 🎉

Additional tests and adjustments (if needed) can be done in follow-up PRs, this one is already very large

[turbolent]

I had a look at adding the container/child address matching checks to Cadence: Just before performing a mutating operation on a container (array/map), we already transfer the child, so checking the invariant does not really help much: if we insert the assertion we can also check the transfer.

On the atree side, it's not easy to check this invariant: children are values at first, and getting the storable (which is needed to get the potential storage ID) is delayed until the very "end", e.g. deep down when the container/parent is not available anymore.

Maybe there isn't much we can do here

[fxamacker]

@turbolent Thanks for detailed review and meeting notes!

I think everything discussed so far have been addressed in this PR. :tada:

• More comments were added about how atree inlining works in commit a75e3886e2987a452487a5ed02559c284a4b096c

• Commit 63ea7a74dd58db15fc871c40f4c3c47772dc8c81 handles values with outdated parent callbacks (value was removed or overwritten in parent container):

  • the callback is no-op when callback detects value is no longer a child in its old parent.
  • value unsets outdated parent callback

• Commit 8d02bbcd024cf77a14b6feb31ca7a4aadec330c7 renamed existingValue.

• Commit 042eb686fc19f48fe3e78a69b3cbe6de979a4001 unlined removed or overwritten child (if it is inlined)

• I double-checked that atree doesn't make assumption about value returned from StoredValue().

• About "invariant that all values stored in an account always reference values in the same account"

  • it isn't easy to check in code as you mentioned. However, we check this in tests, for example, atree.CheckStorageHealth() checks that all child or referenced slabs have the same address and atree validation functions also checks inlined slabs in memory have the same address as its parent.

• I opened these issues to add more integration tests:

  • https://github.com/onflow/atree/issues/346
  • https://github.com/onflow/cadence/issues/2837

BTW, can you please take a look at PR #345? That is the 2nd of 2 atree inlining PRs.