Simplify Eviction Scan Logic

[SirTyson]

We would like to simplify the eviction scan process such that we evict entries in order of (liveUntilLedgerSeq, LedgerKey), where we evict entries with the lowest liveUntilLedgerSeq (i.e. the oldest expired entries) first. This will not only make eviction scans more performant, as we can leverage the in-memory soroban state and remove disk reads from eviction scans, but we will also be able to simplify the process significantly.

[dmkozh]

The initial CAP PR suggests that we have a set index of live until ledgers+keys.

While the memory overhead of this list is fairly small, there may be some runtime issues with O(log n) operations on TTL bumps, eviction, entry creation, etc.

I agree that memory overhead is small, the time overhead might be problematic:

• we need to compare key XDR by value O(log n) times per lookup
• we also need to do 2 set updates for every TTL change (once to remove the old pair, one to insert a new pair)
• ordered sets/maps with millions of elements (which we will end up having) are not very fast.
• there is no explicit per-ledger limit on the number of TTL updates. The implicit limit (max txs * max footprint size) can be rather high.

This could still be fine in the absolute terms, but I think it's worth at least spending some time considering other potential options or optimizations.

[SirTyson]

Since it's not relevant to the protocol and I want to experiment with the simplest set implementation first, I didn't talk about this too much. But I think we have a couple options:

1. Keep the set and just update it in parallel to disk writes. This should be easy from an implementation standpoint, since it can be a very short lived task that is started and joined within the commit path. Even with large sets, it seems like the cost of in-memory updates would be dominated by the cost of the disk write (though thread overhead may be an issue), given that we have to write the same set of entries to disk that we're modifying in the set + classic entries. This may not be the case though for very large sets. I don't think the memory overhead is significant, even for large sets at 16 bytes / live entry.

2. Maintain unordered buckets of LedgerKey (or pointers) for given ranges of TTLs. For example, we could have buckets that cover 16 ledgers each. Whenever a TTL is bumped, we add the entry to the corresponding bucket. We could have the cache itself hold a pointer to its slot in the eviction buckets for invalidation, or we could just allow stale entries to be in buckets and check the up-to-date TTL before eviction. Whenever a given bucket of candidates is about to become expired, we sort the bucket at that time, or just before. Given that TTLs can't decrease, we only have to worry about "skipping" entries in the bucket (if we allow stale entries). We never have the case where a bucket is sorted, then that sort order becomes invalidated because a TTL decreased. We do need to consider the case where a temp entry with the minimum TTL is created, but we can set our bucket sizes small enough such that that is not an issue. It's theoretically possible for an arbitrary number of entries to expire in the same bucket and form a large set, but I think given that the "DOS" angle here is still just an in-memory sorted set, it seems unlikely that this could actually be exploited harmfully in practice.

[dmkozh]

I understand that implementation details may be adjusted, but we also should make sure we don't make protocol design choices that make efficient implementation impossible, so we should at least have a general idea if the performance is going to cut it.

I think option 1 is likely reasonable. I just was wondering if there is maybe another deterministic eviction order that requires less effort to maintain.

[SirTyson]

Ya I think we can put together a prototype pretty easily to see how bad it is, but I think this is our best ordering. I thought about using a similar iterator based approach, but move the iterator to the in-memory state and not the BucketList. The problem with this is we use an unordered_map as our in-memory cache implementation, so we'd either need to switch over to some sort of ordered container with less performance, or use a fixed seed, which could possibly be gamed for collisions. I think ordering on TTL makes the most sense, as it isn't implementation specific to our cache container, and since we know when an entry will be "eligible" for eviction, we can just maintain a subset of sorted entries (like in the unsorted bucket approach above). I also just want to keep the protocol as simple as possible in light of p23, and ordering on TTL let's us avoid iterating over "eviction candidates", since the scan order itself tells us exactly what we need to evict.