Collator Protocol Revamp: reputation database

[alindima]

Implement a reputation database which supports (at least) the following basic operations:

trait Db {
    fn query(PeerId, ParaId) -> Option<Score>;
    fn modify_reputation(PeerId, ParaId, Score);
}

Properties:

• Persistent, but allows for occasional data loss (due to unexpected exits). Persistence is only needed so that data is not lost across validator restarts and so that validators don't hold too much useless data in memory.
• Single-threaded access
• The set of allowed paraids is predefined (as the set of registered paraids). When a para is unregistered, their reputations can be dropped.
• Each paraid has a maximum predefined capacity for peers (maybe 100). Once capacity is reached, use an LRU approach.

Conceptually, it should work like a BTreeMap<ParaId, LruMap<PeerId, Score>>. Using the parachains db is probably the best option.

Start with a simple implementation that doesn't do premature optimisations. See if they are needed through testing and benchmarking.

Some ideas for improving performance:

• have an in-memory write overlay that supports a flush operation every X amount of time
• pre-load in memory the values for the scheduled paraids
• the per-para LRU is tricky to implement efficiently in the parachains key-value DB. Start simple with a naive O(N) lookup for the oldest item when inserting while at capacity. N is at most 100 and it should rarely be reached, so this could be ok. An idea for improving the algorithmic complexity would be to encode a heap in the key-value DB over the 0..N keys , achieving O(logN) operations.