State Archival Persistent Entry Eviction

[SirTyson]

This document proposes a design to allow for the eviction and restoration of PERSISTENT Soroban entries. Following feedback from the previous proposal, this design no longer introduces a new downstream system (previously known as the Archived State Store) and instead stores all information required to generate restoration proofs in the History Archive. RPC can then use the History Archive to produce proofs required for a given transaction during preflight.

CAP-57: https://github.com/stellar/stellar-protocol/blob/master/core/cap-0057.md

[anupsdf]

How about adding a section around performance implication of inserting into hot archive (which is mutable) since its a sorted, balanced, binary Merkle tree? Like, if it blocks main thread and a lot of entries are evicted on a ledger close. Similarly, when entries are restored from the hot archive triggering rebalance of the tree.

[SirTyson]

The Hot Archive is not a merkle tree, just a plain old BucketList, so writes are in-memory and very fast. In the abstract I should clarify this sentence:

The AST is made up of a collection of immutable Merkle trees stored on top of the BucketList, called “Archival Snapshots”, plus a single mutable store called the “Hot Archive”

What I meant by this was the AST is immutable Merkle trees (Archival Snapshots) + a non-merkle, mutable store called the Hot Archive. I'll make this more clear in the abstract, but for now the "Hot Archive" section goes into more detail. Since it's just a standard BucketList, both inserting archived entries as well as removing restored entries is a single in-memory, very efficient operation.

[anupsdf]

I see. That makes sense. Thanks!

[anupsdf]

When converting Pending Archival Snapshot state to Archival Snapshot and entries are condensed into a single bottom level, do we mean to take the latest entry in case the same entry exists with multiple types? Since prior entries are overwritten we can clarify that.
Also, how about adding a note on entries of type RESTORED will be dropped step to clarify that its for entries that expired and got restored from hot archive so they don't have to be in the snapshot.

[SirTyson]

Yeah, the conversion is just merging the Pending Archival Snapshot BucketList all into a single Bucket, and mostly follows the normal BucketList merge logic where newer version of entries overwrite older versions. I'll expand on this section with the specific merge logic.

[anupsdf]

When verifying the proof of nonexistence, shouldn't we also look into Pending Archival Snapshot for archived entries that are in transit right before creating the archive snapshot? Sounds like thats the cold archive waiting to be condensed while a new hot archive is being used.

[anupsdf]

In the pseudo code for InvokeHostFunctionOpV2, I see that we look into allBucketListsStoredOnDisk. So, if a user submits a tx where footprint has an entry thats in either pending archival snapshot or Merkle Production Queue, we will fail the tx. That means user has to wait until snapshot is created to generate the proof of existence.

[SirTyson]

When verifying the proof of nonexistence, shouldn't we also look into Pending Archival Snapshot for archived entries that are in transit right before creating the archive snapshot? Sounds like thats the cold archive waiting to be condensed while a new hot archive is being used.

Yes. In the verifyProofOfNonexistence pseudo code, I only cover validating the actual proof itself. The actual nonexistence check is covered in the InvokeHostFunctionOpV2 "archival phase", where we check for existence in allBucketListsStoredOnDisk, which includes the hot archive, pending archival snapshot, and every snapshot in Merkle Production Queue.

In the pseudo code for InvokeHostFunctionOpV2, I see that we look into allBucketListsStoredOnDisk. So, if a user submits a tx where footprint has an entry thats in either pending archival snapshot or Merkle Production Queue, we will fail the tx. That means user has to wait until snapshot is created to generate the proof of existence.

While it's true that the transaction will fail, it is not true that the user must wait until the snapshot is created. RestoreFootprintOp is capable of restoring an entry (and adding it back to the Live Bucket List) at any point. This includes an expired entry still on the Live BucketList, and entry in the Hot Archive, Pending Archive, on-disk archival snapshot merkle queue, or off-disk archival snapshot. However, only off-disk archival snapshot restoration will actually require a proof, but the entry can be restored without a proof at any other stage. So in the case of the InvokeHostFunctionOpV2 check, it's true that an entry in a pending snapshot or queue will not yet be able to have proofs generated, but these entries can be restored without a proof. I briefly touch on this in the RestoreFootprintOp section but will make it more clear.