From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id CECA86ECE3; Thu, 20 Jan 2022 13:21:15 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org CECA86ECE3 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1642674075; bh=J1++vDJbcoXiM5lNujFK5ce/DR/IEomQH/q3rI1QMGU=; h=Date:To:References:In-Reply-To:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=nZ0GR5P+iF1fdiFcPyinb+SuAOpe3b3OSqNZB8YAm102X3lrf9LJb1hxpCHeSJYRt 81CX6TNBNBCHyGgszs0cVekkzpQ2Q1NomCZxBsjqOt8sQ3QpmhSwgln/g5ibI5qHZv Ns/RL6I3sD4qzTjqSjLRscv/z3b+7XwMrEJE2WyU= Received: from smtp33.i.mail.ru (smtp33.i.mail.ru [94.100.177.93]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 506386ECE3 for ; Thu, 20 Jan 2022 13:21:14 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 506386ECE3 Received: by smtp33.i.mail.ru with esmtpa (envelope-from ) id 1nAUZ7-0005WC-L7; Thu, 20 Jan 2022 13:21:14 +0300 Message-ID: <9a4265d4-cc66-ad1f-5478-ebcc10eef5a8@tarantool.org> Date: Thu, 20 Jan 2022 13:21:12 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.5.0 Content-Language: en-GB To: Vladislav Shpilevoy , tarantool-patches@dev.tarantool.org References: <8ce7d7d2ff3c79f11f73272ad08e43838689681a.1642207647.git.v.shpilevoy@tarantool.org> <0d65c52d-c42f-7271-d4d2-a997268138a7@tarantool.org> <10be2844-066e-e7fc-735a-5322fd52700e@tarantool.org> In-Reply-To: <10be2844-066e-e7fc-735a-5322fd52700e@tarantool.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-4EC0790: 10 X-7564579A: EEAE043A70213CC8 X-77F55803: 4F1203BC0FB41BD98A33503A0B8627DB0CFFC844246A0A7026C351614E063809182A05F538085040EEE9C473D57A2524BDB89C8255723EEB5A5DC53002A6222199C1F36966C1135F X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE710FC7AC39A8009ECEA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F7900637B84F9009663064BD8638F802B75D45FF36EB9D2243A4F8B5A6FCA7DBDB1FC311F39EFFDF887939037866D6147AF826D81D4CEA7534552518B3A90946BB602B3E117882F4460429724CE54428C33FAD305F5C1EE8F4F765FCF1175FABE1C0F9B6A471835C12D1D9774AD6D5ED66289B52BA9C0B312567BB23117882F446042972877693876707352033AC447995A7AD182CC0D3CB04F14752D2E47CDBA5A96583BA9C0B312567BB2376E601842F6C81A19E625A9149C048EE437C869540D2AB0FC766E17BBE5724E9D8FC6C240DEA7642DBF02ECDB25306B2B78CF848AE20165D0A6AB1C7CE11FEE3A7DFDF579AB090EF302FCEF25BFAB345C4224003CC836476EA7A3FFF5B025636E2021AF6380DFAD1A18204E546F3947CB11811A4A51E3B096D1867E19FE1407959CC434672EE6371089D37D7C0E48F6C8AA50765F7900637B8F435DEDE9E76EBEFF80C71ABB335746BA297DBC24807EABDAD6C7F3747799A X-C1DE0DAB: 0D63561A33F958A5D5E9505A904F4B3C2195270D1CAD100FAA898143E4E0F1C8D59269BC5F550898D99A6476B3ADF6B47008B74DF8BB9EF7333BD3B22AA88B938A852937E12ACA75B7BFB303F1C7DB4D8E8E86DC7131B365E7726E8460B7C23C X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D34E229BE567979C940108537DE6080BFA8425E80D719C5A2420CA167BD9CFABC4277A3B3A63A22A6851D7E09C32AA3244C0703EA2E4DC94F86FE9CF5CA4BD4550EF94338140B71B8EE729B2BEF169E0186 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojPeoZbWa28mzBTGjrBucXHg== X-Mailru-Sender: 583F1D7ACE8F49BDA1AB7BAC9906293EA9912FE2A80A5AF675A655C17FFDF75B89E81C32B342DA0B424AE0EB1F3D1D21E2978F233C3FAE6EE63DB1732555E4A8EE80603BA4A5B0BCB0DAF586E7D11B3E67EA787935ED9F1B X-Mras: Ok Subject: Re: [Tarantool-patches] [PATCH 3/4] raft: introduce split vote detection X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Serge Petrenko via Tarantool-patches Reply-To: Serge Petrenko Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" 20.01.2022 03:44, Vladislav Shpilevoy пишет: > Hi! Thanks for the review! > >>> diff --git a/src/lib/raft/raft.c b/src/lib/raft/raft.c >>> index 289d53fd5..5dcbc7821 100644 >>> --- a/src/lib/raft/raft.c >>> +++ b/src/lib/raft/raft.c >>> @@ -152,20 +152,69 @@ raft_can_vote_for(const struct raft *raft, const struct vclock *v) >>>       return cmp == 0 || cmp == 1; >>>   } >>>   -static inline void >>> +static inline bool >>>   raft_add_vote(struct raft *raft, int src, int dst) >>>   { >>>       struct raft_vote *v = &raft->votes[src]; >>>       if (v->did_vote) >>> -        return; >>> +        return false; >>>       v->did_vote = true; >>>       ++raft->votes[dst].count; >>> +    return true; >>> +} >>> + >> You may check split_vote right in raft_add_vote: >> simply track number of votes given in this term and >> max votes given for one instance. >> >> This way you won't have to run over all 32 nodes each time a vote >> is casted. > I did the fullscan intentionally. Otherwise I need to introduce 2 > new members to struct raft, keep them up to date, clear on term > bump. Too easy to miss something and introduce a bug. While in > the current version all the split-vote-specific details are in a > single function except for 'raft.votes' member. This thing I couldn't > get rid of. > > As for perf, a couple of ifs or a loop over 32 structs - both would > take order of nanoseconds anyway. Here I wouldn't bother. Simplicity > matters most. > > I did the proposal to see how it looks but then discarded as more > complex than necessary. However if you think it is still worth doing, > tell me and I will re-apply the diff. Thanks for trying this out! TBH, this diff is exactly what I wanted and it still looks better (not only preformance-wise, but simpler as well) in my opinion. I understand your point about having to update 2 extra members every now and then, so feel free to choose any option you like. > > ==================== > diff --git a/src/lib/raft/raft.c b/src/lib/raft/raft.c > index c4f5fb059..fcce3126a 100644 > --- a/src/lib/raft/raft.c > +++ b/src/lib/raft/raft.c > @@ -159,23 +159,20 @@ raft_add_vote(struct raft *raft, int src, int dst) > if (v->did_vote) > return false; > v->did_vote = true; > - ++raft->votes[dst].count; > + ++raft->voted_count; > + int count = ++raft->votes[dst].count; > + if (count > raft->max_vote_count) > + raft->max_vote_count = count; > return true; > } > > static bool > raft_has_split_vote(const struct raft *raft) > { > - int max_vote = 0; > - int vote_vac = raft->cluster_size; > - int quorum = raft->election_quorum; > - for (int i = 0; i < VCLOCK_MAX; ++i) { > - int count = raft->votes[i].count; > - vote_vac -= count; > - if (count > max_vote) > - max_vote = count; > - } > - return max_vote + vote_vac < quorum; > + int vote_vac = raft->cluster_size - raft->voted_count; > + if (vote_vac < 0) > + vote_vac = 0; > + return raft->max_vote_count + vote_vac < raft->election_quorum; > } > > static int > @@ -730,6 +727,8 @@ raft_sm_schedule_new_term(struct raft *raft, uint64_t new_term) > raft->leader = 0; > raft->state = RAFT_STATE_FOLLOWER; > memset(raft->votes, 0, sizeof(raft->votes)); > + raft->max_vote_count = 0; > + raft->voted_count = 0; > /* > * The instance could be promoted for the previous term. But promotion > * has no effect on following terms. > diff --git a/src/lib/raft/raft.h b/src/lib/raft/raft.h > index 817148792..7115f658f 100644 > --- a/src/lib/raft/raft.h > +++ b/src/lib/raft/raft.h > @@ -199,6 +199,10 @@ struct raft { > uint32_t vote; > /** Statistics which node voted for who. */ > struct raft_vote votes[VCLOCK_MAX]; > + /** How many nodes voted in the current term. */ > + int voted_count; > + /** Max vote count given to any node in the current term. */ > + int max_vote_count; > /** Number of votes necessary for successful election. */ > int election_quorum; > /** > ==================== > >>> +static bool >>> +raft_has_split_vote(const struct raft *raft) >>> +{ >>> +    int max_vote = 0; >>> +    int vote_vac = raft->cluster_size; >>> +    int quorum = raft->election_quorum; >>> +    for (int i = 0; i < VCLOCK_MAX; ++i) { >>> +        int count = raft->votes[i].count; >>> +        vote_vac -= count; >>> +        if (count > max_vote) >>> +            max_vote = count; >>> +    } >>> +    return max_vote < quorum && max_vote + vote_vac < quorum; >> This is equal to `return max_vote + vote_vac < quorum` > Ouch, that was stupid indeed. I honestly did multiple self-reviews > and still missed it. Don't bother. Could happen to anyone. > ==================== > @@ -175,7 +175,7 @@ raft_has_split_vote(const struct raft *raft) > if (count > max_vote) > max_vote = count; > } > - return max_vote < quorum && max_vote + vote_vac < quorum; > + return max_vote + vote_vac < quorum; > } > ==================== > ... -- Serge Petrenko