8000 [CINFRA-162] Supervision for Replicated State Machines (#15349) · strogo/arangodb@56bdeb2 · GitHub
[go: up one dir, main page]
Skip to content

Commit 56bdeb2

Browse files
markuspfaMahannampoeterLars Maier
authored
[CINFRA-162] Supervision for Replicated State Machines (arangodb#15349)
* Setup leader state machine functions * Datastructure and test setup * Skeletonizign * First test code passes * Implement Leadership election * Implement some tests for running a leaderelection campaign * velocyPackHell * add forgotten file * Split work up * ... * Fix compiler complaints * Address linter complaints * temp: update clang-format.yml attempting to fix bad git diff * Revert "temp: update clang-format.yml" This reverts commit 02cda31. * some light refactoring * Fix bug in runElectionCampaign * Add a test for leadership election terms * Fix test comments and name * Handle a corner case differently * Remove rendundant comment * Move to unified representation of Agency * Rename files to make clearer what is supposed to to what * Remove some no longer used files * Lol windows lol. * Fix Windows build. Co-authored-by: aMahanna <anthony.mahanna@gmail.com> Co-authored-by: mpoeter <manuel@arangodb.com> Co-authored-by: Lars Maier <lars@arangodb.com>
1 parent 3d70777 commit 56bdeb2

File tree

6 files changed

+850
-0
lines changed

6 files changed

+850
-0
lines changed

‎arangod/CMakeLists.txt

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -565,6 +565,8 @@ set(LIB_ARANGO_REPLICATION2_SOURCES
565565
Replication2/ReplicatedState/ReplicatedStateFeature.cpp
566566
Replication2/ReplicatedState/StateCommon.cpp
567567
Replication2/ReplicatedState/StateStatus.cpp
568+
Replication2/ReplicatedState/Supervision.cpp
569+
Replication2/ReplicatedState/SupervisionVelocyPackHell.cpp
568570
Replication2/Version.cpp
569571
RestHandler/RestLogHandler.cpp
570572
RestHandler/RestLogInternalHandler.cpp

‎arangod/Replication2/ReplicatedState/Supervision.cpp

Lines changed: 253 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,253 @@
1+
////////////////////////////////////////////////////////////////////////////////
2+
/// DISCLAIMER
3+
///
4+
/// Copyright 2021-2022 ArangoDB GmbH, Cologne, Germany
5+
///
6+
/// Licensed under the Apache License, Version 2.0 (the "License");
7+
/// you may not use this file except in compliance with the License.
8+
/// You may obtain a copy of the License at
9+
///
10+
/// http://www.apache.org/licenses/LICENSE-2.0
11+
///
12+
/// Unless required by applicable law or agreed to in writing, software
13+
/// distributed under the License is distributed on an "AS IS" BASIS,
14+
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15+
/// See the License for the specific language governing permissions and
16+
/// limitations under the License.
17+
///
18+
/// Copyright holder is ArangoDB GmbH, Cologne, Germany
19+
///
20+
/// @author Markus Pfeiffer
21+
////////////////////////////////////////////////////////////////////////////////
22+
23+
#include "Supervision.h"
24+
25+
#include "Basics/Exceptions.h"
26+
#include "Basics/StringUtils.h"
27+
#include "Basics/application-exit.h"
28+
#include "Logger/LogMacros.h"
29+
#include "Random/RandomGenerator.h"
30+
#include "velocypack/Builder.h"
31+
#include "velocypack/Value.h"
32+
33+
#include <cstdint>
34+
#include <limits>
35+
#include <memory>
36+
37+
namespace arangodb::replication2::replicated_state {
38+
39+
auto to_string(LeaderElectionCampaign::Reason reason) -> std::string_view {
40+
switch (reason) {
41+
case LeaderElectionCampaign::Reason::OK: {
42+
return "OK";
43+
} break;
44+
case LeaderElectionCampaign::Reason::ServerIll: {
45+
return "ServerIll";
46+
} break;
47+
case LeaderElectionCampaign::Reason::TermNotConfirmed: {
48+
return "TermNotConfirmed";
49+
} break;
50+
}
51+
return "this-value-is-here-to-shut-up-the-compiler-if-this-is-reached-that-"
52+
"is-a-bug";
53+
}
54+
55+
auto operator<<(std::ostream& os, LeaderElectionCampaign::Reason reason)
56+
-> std::ostream& {
57+
return os << to_string(reason);
58+
}
59+
60+
void LeaderElectionCampaign::toVelocyPack(VPackBuilder& builder) const {
61+
auto ob = VPackObjectBuilder(&builder);
62+
builder.add("numberOKParticipants", VPackValue(numberOKParticipants));
63+
64+
builder.add(VPackValue("bestTermIndex"));
65+
bestTermIndex.toVelocyPack(builder);
66+
67+
{
68+
auto rb = VPackObjectBuilder(&builder, "reasons");
69+
for (auto const& [participant, reason] : reasons) {
70+
builder.add(VPackValue(participant));
71+
builder.add(VPackValue(to_string(reason)));
72+
}
73+
}
74+
75+
{
76+
auto eb = VPackArrayBuilder(&builder, "electibleLeaderSet");
77+
for (auto const& participant : electibleLeaderSet) {
78+
builder.add(VPackValue(participant));
79+
}
80+
}
81+
}
82+
83+
auto to_string(LeaderElectionCampaign const& campaign) -> std::string {
84+
auto bb = VPackBuilder{};
85+
campaign.toVelocyPack(bb);
86+
return bb.toString();
87+
}
88+
89+
auto operator<<(std::ostream& os, Action::ActionType const& action)
90+
-> std::ostream&;
91+
92+
auto to_string(Action::ActionType action) -> std::string_view {
93+
switch (action) {
94+
case Action::ActionType::FailedLeaderElectionAction: {
95+
return "FailedLeaderElection";
96+
} break;
97+
case Action::ActionType::SuccessfulLeaderElectionAction: {
98+
return "SuccessfulLeaderElection";
99+
} break;
100+
case Action::ActionType::UpdateTermAction: {
101+
return "UpdateTermAction";
102+
} break;
103+
case Action::ActionType::ImpossibleCampaignAction: {
104+
return "ImpossibleCampaignAction";
105+
} break;
106+
}
107+
return "this-value-is-here-to-shut-up-the-compiler-if-this-is-reached-that-"
108+
"is-a-bug";
109+
}
110+
111+
auto operator<<(std::ostream& os, Action::ActionType const& action)
112+
-> std::ostream& {
113+
return os << to_string(action);
114+
}
115+
116+
auto computeReason(LogCurrentLocalState const& status, bool healthy,
117+
LogTerm term) -> LeaderElectionCampaign::Reason {
118+
if (!healthy) {
119+
return LeaderElectionCampaign::Reason::ServerIll;
120+
} else if (term != status.term) {
121+
return LeaderElectionCampaign::Reason::TermNotConfirmed;
122+
} else {
123+
return LeaderElectionCampaign::Reason::OK;
124+
}
125+
}
126+
127+
auto runElectionCampaign(LogCurrentLocalStates const& states,
128+
ParticipantsHealth const& health, LogTerm term)
129+
-> LeaderElectionCampaign {
130+
auto campaign = LeaderElectionCampaign{};
131+
132+
for (auto const& [participant, status] : states) {
133+
auto reason = computeReason(status, health.isHealthy(participant), term);
134+
campaign.reasons.emplace(participant, reason);
135+
136+
if (reason == LeaderElectionCampaign::Reason::OK) {
137+
campaign.numberOKParticipants += 1;
138+
139+
if (status.spearhead >= campaign.bestTermIndex) {
140+
if (status.spearhead != campaign.bestTermIndex) {
141+
campaign.electibleLeaderSet.clear();
142+
}
143+
campaign.electibleLeaderSet.push_back(participant);
144+
campaign.bestTermIndex = status.spearhead;
145+
}
146+
}
147+
}
148+
return campaign;
149+
}
150+
151+
auto checkLeaderHealth(Log const& log, ParticipantsHealth const& health)
152+
-> std::unique_ptr<Action> {
153+
if (health.isHealthy(log.plan.currentTerm->leader->serverId) &&
154+
health.validRebootId(log.plan.currentTerm->leader->serverId,
155+
log.plan.currentTerm->leader->rebootId)) {
156+
// Current leader is all healthy so nothing to do.
157+
return nullptr;
158+
} else {
159+
// Leader is not healthy; start a new term
160+
auto newTerm = *log.plan.currentTerm;
161+
162+
newTerm.leader.reset();
163+
newTerm.term = LogTerm{log.plan.currentTerm->term.value + 1};
164+
165+
return std::make_unique<UpdateTermAction>(newTerm);
166+
}
167+
}
168+
169+
auto tryLeadershipElection(Log const& log, ParticipantsHealth const& health)
170+
-> std::unique_ptr<Action> {
171+
// Check whether there are enough participants to reach a quorum
172+
if (log.plan.participantsConfig.participants.size() + 1 <=
173+
log.plan.currentTerm->config.writeConcern) {
174+
return std::make_unique<ImpossibleCampaignAction>(
175+
/* TODO: should we have an error message? */);
176+
}
177+
178+
TRI_ASSERT(log.plan.participantsConfig.participants.size() + 1 >
179+
log.plan.currentTerm->config.writeConcern);
180+
181+
auto const requiredNumberOfOKParticipants =
182+
log.plan.participantsConfig.participants.size() + 1 -
183+
log.plan.currentTerm->config.writeConcern;
184+
185+
// Find the participants that are healthy and that have the best LogTerm
186+
auto const campaign = runElectionCampaign(log.current.localState, health,
187+
log.plan.currentTerm->term);
188+
189+
auto const numElectible = campaign.electibleLeaderSet.size();
190+
191+
// Something went really wrong: we have enough ok participants, but none
192+
// of them is electible, or too many of them are (we only support
193+
// uint16_t::max participants at the moment)
194+
//
195+
// TODO: should this really be throwing or just erroring?
196+
if (ADB_UNLIKELY(numElectible == 0 ||
197+
numElectible > std::numeric_limits<uint16_t>::max())) {
198+
abortOrThrow(TRI_ERROR_NUMERIC_OVERFLOW,
199+
basics::StringUtils::concatT(
200+
"Number of participants electible for leadership out "
201+
"of range, should be between ",
202+
1, " and ", std::numeric_limits<uint16_t>::max(),
203+
", but is ", numElectible),
204+
ADB_HERE);
205+
}
206+
207+
if (campaign.numberOKParticipants >= requiredNumberOfOKParticipants) {
208+
// We randomly elect on of the electible leaders
209+
auto const maxIdx = static_cast<uint16_t>(numElectible - 1);
210+
auto const& newLeader =
211+
campaign.electibleLeaderSet.at(RandomGenerator::interval(maxIdx));
212+
auto const& newLeaderRebootId = health._health.at(newLeader).rebootId;
213+
214+
auto action = std::make_unique<SuccessfulLeaderElectionAction>();
215+
216+
action->_campaign = campaign;
217+
action->_newTerm = LogPlanTermSpecification(
218+
LogTerm{log.plan.currentTerm->term.value + 1},
219+
log.plan.currentTerm->config,
220+
LogPlanTermSpecification::Leader{.serverId = newLeader,
221+
.rebootId = newLeaderRebootId},
222+
log.plan.currentTerm->participants);
223+
action->_newLeader = newLeader;
224+
225+
return action;
226+
} else {
227+
// Not enough participants were available to form a quorum, so
228+
// we can't elect a leader
229+
auto action = std::make_unique<FailedLeaderElectionAction>();
230+
action->_campaign = campaign;
231+
return action;
232+
}
233+
}
234+
235+
auto replicatedLogAction(Log const& log, ParticipantsHealth const& health)
236+
-> std::unique_ptr<Action> {
237+
if (log.plan.currentTerm->leader) {
238+
// We have a leader; we check that the leader is
239+
// healthy; if it is, there is nothing to do,
240+
// if it isn't we
241+
return checkLeaderHealth(log, health);
242+
} else {
243+
// New leader required; we try running an election
244+
// TODO: Why are we duplicating this in replicated state
245+
return tryLeadershipElection(log, health);
246+
}
247+
248+
// This is only here to make the compiler happy; we should never end up here;
249+
TRI_ASSERT(false);
250+
return nullptr;
251+
}
252+
253+
} // namespace arangodb::replication2::replicated_state

0 commit comments

Comments
 (0)
0