search

ethereum / trin

An Ethereum portal client: a json-rpc server with nearly instant sync, and low CPU & storage usage
365 stars 113 forks source link

state-bridge: Census peer scoring #1501

Open morph-dev opened 3 days ago

morph-dev commented 3 days ago

Problem

The Census only keeps track of all available peers, and their liveness is checked once per hour.

When peers are requested for a given content id, census filters out all peers whose radius doesn't include provided content, and returns first X (4 at the moment of writing).

Ideally, we should have some reputation or scoring system for the peers and use it when selecting them.

High level idea

Firstly, we should still filter out peers that are not interested in the content (as we do now). Then, each peer will be assigned weight, and X peers will be selected randomly based on their weight.

The weight can be calculated as product of following: distance, reputation and recency weights

Note: All constants can be configurable parameters. Given values are picked by feeling and could be a good starting point (unless somebody has some other suggestions).

Distance weight

This is the main weigh: peers should be selected based on their distance to the content.

distance_weight = u16::MAX - distance(peer_id, content_id).as_u16()

The as_u16 function takes 16 most significant bits (2 bytes) of the U256 distance metric

Reputation weight

This is the main penalty weight: peers with recent failed attempts should be penalized.

reputation_weight = 1 / (2^recent_failed_attempts) as f64

The recent_failed_attempts is the number of recently failed OFFER requests to the peer. Only last 16 OFFER requests should be considered. Rejected offers shouldn't be counted as failures .

Each failed attempt lowers the weight by factor of 2.

Recency weight

This is the main recovery function: it "rewards" peers that weren't offered content in a long time. Peers that were failing requests in the past but have recovered in the meantime would have hard time being selected, and this weight should help with that.

recency_weight = 2 ^ ((now - last_offer_timestamp).as_seconds() / 300)

For every 5 minutes that we didn't offer content to the peer, their weight increases by factor of 2

Assuming all peers are healthy, this shouldn't play big factor because of the high volume and random distribution of content ids (meaning all peers should be selected before this weight grows too big).

This only starts playing important role for peers that are penalized by reputation_weight, in which case it takes 5 minutes to recover one failed attempt.

Future improvements

Some ideas omitted from the initial approach as I want to start with something simple and add more complexity afterwards if needed.

pipermerriam commented 3 days ago

I'll propose an alternate framework. Weights are all additive to avoid multipliers, making it much easier to reason about the ranges for different values.

Given the list of interested peers, a weighted random selection should be made from the calculated weights.

The main thing I'd like to augment this with would be data transfer rate which I think requires us to have an actual ongoing measurement of each individual peer's throughput in something like bytes/sec. With that we can award additional weight based on how they do in comparison with the other peers.

morph-dev commented 3 days ago

Since you didn't mention it, do you think it's important to prioritize / give higher weigh to nodes that are closer to the content?

  • Peers can have a maximum of 200 weight.
  • Peers can have a minimum of -200 weight.

... Given the list of interested peers, a weighted random selection should be made from the calculated weights.

Can you elaborate, from probability/algorithm point of view, how negative weights would be used? To my knowledge, most commonly used sampling uses positive weights for sampling where probability for element i being selected is: $p(i) = {w_i} / {\sum{w_i}}$ .

I guess your idea can be used in the same way as if starting weight is 200 and min-max range is 0-400, but I'm not sure if probability distribution you had in mind is different.

I'm also pretty sure we can implement multiple different "peer scoring" algorithms and compare performance (e.g. percentage of failed attempts).

pipermerriam commented 3 days ago

For the range, I imagined that implementations would treat this as a weight in the range 0-400. It felt awkward to define the algorithm with each node have a starting weight of 200. Also worth saying that the exact numbers here are utterly arbitrary and I'm totally open to suggestions for better numbers.

Since you didn't mention it, do you think it's important to prioritize / give higher weigh to nodes that are closer to the content?

No, I don't think distance should be apart of this. The neighborhood gossip should take care of getting content to the closest nodes and I don't think it is likely to improve our primary performance metric (rate-or-speed of gossip) to push it to the closest nodes, nor do I think it improves network health.

pipermerriam commented 3 days ago

If we were able to have throughput measurements, then I would suggest this modification.

I also think that we should add extra penalties for failed transfers. In theory we could do this by measuring wasted bandwidth and time. The MBR tells us how long a transfer should take on average. We should be able to combine this with the payload size to get a time T which would be the expected mean transfer time. Ideally we'd want to deduct additional weight for them taking extra long to fail and we'd want to deduct extra points for them using extra bandwidth beyond the base bandwidth that would have been needed for transfering the base payload.... I hope this makes sense.