Improve ADT diffing logic used to track actor state chages

[frrist]

Description

Currently, Visor uses HAMT & AMT Diffing logic implemented in Lotus to determine what changed within actor states. The ADT diffing logic all lives here. There are two performance-related issues I see with the current diffing logic:

1. It requires the state contained within the ADT to be deserialized to perform the diff.
2. It will iterate over each entry in the ADT regardless if there has been a change or not. Needless serialization can be avoided by comparing the ADT Root CID before performing the Diff. Unfortunately, the ADT Root methods require a write to their underlying blockstore, which is not allowed in the current lotus implementation. I've described the issue in greater detail here
   • This also carries the side-effect of making the actor interfaces presented by lotus unimplementable due to their unexported interface methods.

ADT diffing is one of the largest bottlenecks of Visors chain state processing and must be improved for Visor to watch and process the chain in real-time.

We can address (1) in two parts:

1. When diffing AMT's, use faster AMT diffing logic. code here.
2. Implement and use fast HAMT diffing logic. issue here.

Addressing (2) requires some decisions/discussion. A couple of ideas on how to address this (open to more):

1. Modify the ADT Root method to avoid writing to their underlying blockstore. Unclear if this is even possible.
2. Make the blockstore used by lotus for ADT diffing writeable. Probably a bad idea since diffing should be read-only
3. Extract the actor interfaces and diffing logic from lotus to a new repository or into Visor. This will allow the ADT to be backed by a blockstore that allows Root to be called. This will also make landing code changes easier as we won't be tied to the lotus review cycle but will become a repo we need to maintain as new actor versions are added.

Acceptance Criteria

• Land AMT diffing change that allows it to work with nondefault bit widths. polish(diff): add diff method accepting options for diffing AMTs with nondefault options go-amt-ipld#49
• Allow the AMT diffing logic to the operator over AMT's with varying sized bit widths: Diff method fails to diff two AMT's with differeing Bitwidths go-amt-ipld#54
• Tag AMT version and update specs-actors v1, v2, v3, and v4 with the tagged version
• Implement HAMT diffing logic with support for variable-sized bit widths. Implement logic for diffing two HAMTs go-hamt-ipld#88
• Tag HAMT version (once diffing added) and update specs-actors v1, v2, v3, v4 with tagged version
• Determine if we want the actor diffing logic to continue living in lotus or if we want to extract it and maintain it ourselves.

[iand]

Is there an option 4: use the native actor states and not the lotus style actor interfaces

[frrist]

I think there is a lot over overlap between option 3 and 4. I assume we'd end up implementing something similar to the lotus shims if we choose to operate over the native actor states.

The largest drawback I see with this aproach is it adds more code for us to maintain and could slow out ability to release new versions of Visor when there is a network/specs-actors upgrade since we will need to update our shims.

[frrist]

After some synchronous discussion, we're left with a couple of options:

1. Modify the HAMT (usage in specs-actors) and AMT (go-amt-ipld) code to work with a read-only IPLD store. We need to understand:
   a. Who would own this work?
   b. What would it require to implement?

2. Implement visor-specific actor shim. This will sidestep the read-only store requirement but will add more code to maintain and update when there is a specs-actors release.

[frrist]

via #519 and #530