Metrics-based bad token detector

[squadgazzz]

Description

Follow-up to #3156. This PR introduces an in-memory, ratio-based bad token detection strategy that complements the existing heuristics. Instead of relying on consecutive failures, it keeps track of both successful and failed settlement attempts for each token. The logic is as follows:

1. When a settlement encoding fails, every token involved in that attempt has its statistics updated: both total attempts and failed attempts are incremented.
2. Otherwise, every token involved has its total attempts incremented but not its failures.
3. Before marking a token as unsupported, the detector requires at least 20 recorded attempts. Once this threshold is met, if the token's failure ratio (fails / attempts) is at least 90%, it is considered unsupported.

This approach is more resilient than just counting consecutive failures. A highly utilized and generally reliable token that occasionally appears in failing trades with problematic tokens won't be prematurely flagged as unsupported because its overall success ratio remains high.

Due to the nature of the implementation, all the statistics get discarded on every restart. Implementing a persistence layer might make sense in the future, but problems with bad tokens are usually temporal.

How to test

A forked e2e test for the simulation-based detector is required first, and it is expected to be implemented in a separate PR.

[MartinquaXD]

I think we need to be less blunt with this heuristic. Let's say there is only 1 market order USDC <> SHITCOIN then the solver will try to solve that over and over and this detector will end up marking USDC as unsupported too.
A better approach might be to count how often a token could be encoded vs. how often it couldn't. That way the heuristic shouldn't flag USDC as unsupported because it will be involved in a ton of trades with "normal" tokens which increase its "goodness" ratio.
I believe the simplest implementation of this strategy needs just 2 variables:

• number of measurements you require at least per token
• ratio of failing encodings a token must have

E.g. at least 20 measurements and a at least 90% of good measurements.

[squadgazzz]

True, thanks.

[squadgazzz]

at least 90% of good measurements

Or 90% of failures?

[mstrug]

the detector requires at least 20 recorded attempts

Is it just an ordinary chosen number or is there a reason for the 20 attempts value?

[mstrug]

Rust standard is to pass slice references instead of vectors, so I'm proposing to change that to: &[(eth::TokenAddress, eth::TokenAddress)].

[squadgazzz]

I wanted to avoid redundant cloning when calling Map::entry function, which requires the owned type, and if that’s not sufficient, let’s adhere to the idiomatic approach that unnecessarily forces copying values.

[mstrug]

In current solution with Vec<> as function argument particular token is still copied in call to Map::entry. It is copied because ownership of vector item cannot be taken from Vec and moved to function or variable. This is because vector stores its data in continuous heap memory buffer and to pass any vector item by value to function requires copy of this item from heap to stack.
So changing to slice as argument will not introduce any additional copy.

[squadgazzz]

particular token is still copied in call to Map::entry. It is copied because ownership of vector item cannot be taken from Vec and moved to function or variable.

Wait, what? Ownership of vector items can be moved from a Vec to a function or variable when the Vec is consumed (e.g., via .into_iter()), and moving items does not involve copying unless explicitly cloned. Map::entry works with owned values, so no copying occurs when items are moved directly.

The suggested idiomatic approach works with references, so when passing a value to the Map::entry, it needs to be cloned/copied first. So I assume the redundant allocation still exists.

[mstrug]

Yes, you are right, into_iter() can move all items by direct iterating over the vector data buffer. I had on my mind case of moving one item from the vector (using index operator for instance) which is not possible.

I was playing a bit with sample code to check how passing by value and reference looks after compilation to see in which case memcpy is used, and it looks that for code without optimizations function parameters are passed by registers (if they fit) or copied by memcpy (if size is too large to use with registers) and it is valid for both pass-by value and pass-by reference. Basically the code for both functions looks similar. After enabling release level optimizations there is no memcpy for smaller and larger data size and direct memory access is used for iteration. Code of pass-by value and reference looks also very similar.
I think above is valid if we are using types which implements Copy trait, in other case this probably looks different (for instance for String type).
If you want to look at the asm here is the code which I was using: https://godbolt.org/z/ejGbYjcP4

Summarizing: In my opinion we should stick with idiomatic approach and compiler will do the optimal final result without any memory copy in this case.

[squadgazzz]

Is it just an ordinary chosen number or is there a reason for the 20 attempts value?

Followed this suggestion #3172 (comment)

[sunce86]

Code LG.

Marking all tokens in a solution as bad because maybe only one trade was bad can be problematic, but I assume this is how it worked before?

[squadgazzz]

Marking all tokens in a solution as bad because maybe only one trade was bad can be problematic, but I assume this is how it worked before?

This is the first implementation of this logic. Previously, a Grafana metric was used to analyze the data manually.