etcd-io / raft

Raft library for maintaining a replicated state machine
Apache License 2.0
630 stars 160 forks source link

optimization:add preTermLastlog index to accelerate the find hintIndex #180

Open 1797818494 opened 6 months ago

1797818494 commented 6 months ago

Now etcd raft find hintindex slowly

func (l *raftLog) findConflictByTerm(index uint64, term uint64) (uint64, uint64) {
    for ; index > 0; index-- {
        // If there is an error (likely ErrCompacted or ErrUnavailable), we don't
        // know whether it's a match or not, so assume a possible match and return
        // the index, with 0 term indicating an unknown term.
        if ourTerm, err := l.term(index); err != nil {
            return index, 0
        } else if ourTerm <= term {
            return index, ourTerm
        }
    }
    return 0, 0
}

But when PreVote and checkQuorum is enable, one electionTimeout's log may be the stale log When partition happened.This is common.And When network recover, the follower will search many logs. And When PreVote and CheckQuorum is enable, there is only one term logs will be stale in the most cases. So I think there is a need to add preTermLastLog to accelerate this.For example:

func (l *raftLog) findConflictByTerm(index uint64, term uint64) (uint64, uint64) {
    if l.preTermLastIndex > 0 {
        return l.preTermLastIndex, l.preTerm 
    }
    for ; index > 0; index-- {
        // If there is an error (likely ErrCompacted or ErrUnavailable), we don't
        // know whether it's a match or not, so assume a possible match and return
        // the index, with 0 term indicating an unknown term.
        if ourTerm, err := l.term(index); err != nil {
            return index, 0
        } else if ourTerm <= term {
            return index, ourTerm
        }
    }
    return 0, 0
}