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 7554A6ECE3; Fri, 21 Jan 2022 02:02:37 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 7554A6ECE3 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1642719757; bh=0OIZ0PLQ02iDiD70qSctJksvXZWsufQn8YY3KoR2Mc8=; 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=COsbQcoa081uadby3PySr/dgci/Arf0lt7HyXrJln+2jObvubQ2P6RhblMbvaVa9B 8hpFQHf/j7spVX8jiVHRNUHsVaL7xFKTFO9sGRZTVFhZaKOEKHR+CgGaQI+A7ZxjYP WPrjm486cVaEFyTewQHQBRa3fVUOOv6uNBC+H4bM= Received: from smtpng3.i.mail.ru (smtpng3.i.mail.ru [94.100.177.149]) (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 6E27C6ECE4 for ; Fri, 21 Jan 2022 02:02:07 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 6E27C6ECE4 Received: by smtpng3.m.smailru.net with esmtpa (envelope-from ) id 1nAgRS-0003DM-N1; Fri, 21 Jan 2022 02:02:07 +0300 Message-ID: <6dbef00a-6c57-934f-49de-89bd50ca2308@tarantool.org> Date: Fri, 21 Jan 2022 00:02:06 +0100 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-US To: Serge Petrenko , 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> <9a4265d4-cc66-ad1f-5478-ebcc10eef5a8@tarantool.org> In-Reply-To: <9a4265d4-cc66-ad1f-5478-ebcc10eef5a8@tarantool.org> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-4EC0790: 10 X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD9AA78FDF62ECAE61F574C814AB3F23F4AA01FB0D4144D4AE0182A05F538085040158250153EF7C35BCB0D1B0146ACA84E016AD6688CF72D2DB8F17E7D0A126AF3 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE7EA4B66823129EB3CEA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F79006378F6D32451C4A3CAA8638F802B75D45FF36EB9D2243A4F8B5A6FCA7DBDB1FC311F39EFFDF887939037866D6147AF826D8EC732586EC1290F633350F28D73303D9117882F4460429724CE54428C33FAD305F5C1EE8F4F765FCF1175FABE1C0F9B6A471835C12D1D9774AD6D5ED66289B52BA9C0B312567BB23117882F446042972877693876707352033AC447995A7AD18E5D25F19253116ADD2E47CDBA5A96583BA9C0B312567BB231DD303D21008E29813377AFFFEAFD269A417C69337E82CC2E827F84554CEF50127C277FBC8AE2E8BA83251EDC214901ED5E8D9A59859A8B6B1CFA6D474D4A6A4089D37D7C0E48F6C5571747095F342E88FB05168BE4CE3AF X-B7AD71C0: 1B70FBA5C9BEEE72C9761FC34675ADEB871C96603B655635EE9D5CB6078CC77C8EB096CD8661970871B50B874F048A7C X-C1DE0DAB: 0D63561A33F958A5FC7FDCC8FB331AB3E4F0D1F5747BD03F571EC30B17E05690D59269BC5F550898D99A6476B3ADF6B47008B74DF8BB9EF7333BD3B22AA88B938A852937E12ACA75B7BFB303F1C7DB4D8E8E86DC7131B365E7726E8460B7C23C X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D3457FA942CB4462B4C90AEEBA90EED21591B931216737FA2EAAD92028A1B275A48EFC008C2DAF5D1321D7E09C32AA3244CCFECDFEACC04AF995C6117EDCD7FB29C33C9DC155518937F729B2BEF169E0186 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojeO2NaHb0kQuNgtVITQofuQ== X-Mailru-Sender: 689FA8AB762F739339CABD9B3CA9A7D60B2DE2E76869A61100FF2B1F0A108B443841015FED1DE5223CC9A89AB576DD93FB559BB5D741EB963CF37A108A312F5C27E8A8C3839CE0E25FEEDEB644C299C0ED14614B50AE0675 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: Vladislav Shpilevoy via Tarantool-patches Reply-To: Vladislav Shpilevoy Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" >>>> 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. I applied this diff: ==================== diff --git a/src/lib/raft/raft.c b/src/lib/raft/raft.c index 5dcc5beaf..90ed01ca4 100644 --- a/src/lib/raft/raft.c +++ b/src/lib/raft/raft.c @@ -159,36 +159,29 @@ 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) + raft->max_vote = 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; /* * Quorum > cluster is either a misconfiguration or some instances * didn't register yet. Anyway, speeding the elections up won't help. + * The same when more nodes voted than there are nodes configured. */ if (vote_vac < quorum) return false; - for (int i = 0; i < VCLOCK_MAX; ++i) { - int count = raft->votes[i].count; - vote_vac -= count; - if (count > max_vote) - max_vote = count; - } - /* - * More nodes voted than there are nodes configured. The reason is the - * the same as with quorum > cluster. The action is also the same - - * faster term bumps won't help. - */ + vote_vac -= raft->voted_count; if (vote_vac < 0) return false; - return max_vote + vote_vac < quorum; + return raft->max_vote + vote_vac < quorum; } static int @@ -743,6 +736,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->voted_count = 0; + raft->max_vote = 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..05e373254 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; /** Number of votes necessary for successful election. */ int election_quorum; /**