[performance improvement] cache votes and link to block

akichidis commented 11 months ago

Under circumstances the commit rule on a 150 validator network could take 10s of miliseconds per commit to execute. That could be proven particularly slow especially when experiencing some asynchrony. Also a slow commit rule wouldn't allow us to execute it more frequently as well given that is part of the block processing path.

This PR is:

caching the votes when trying to figure out whether a block is a certificate. That would make all the other checks of the quorum much faster as it would reduce the iterations hopefully from an NxNxM to NxN
replace the linked method with a linked_to_round to avoid iterating and checking the link path for every single certificate
quickly return from enough_leader_support when there isn't enough stake

the above with some additional improvements which will be added on a follow up PR manage to reduce the commit latency to ~3.7ms per try_commit run.

asonnino commented 11 months ago

Let's test this, the committer code is very delicate. (I know, I sound like a broken record)

asonnino commented 11 months ago

https://github.com/MystenLabs/mysticeti/pull/57#discussion_r1418143049

I think it's not a total stake here, but just stake of all decision_blocks

Good catch!

MystenLabs / mysticeti

[performance improvement] cache votes and link to block #57