diff options
Diffstat (limited to 'src/test/mon/test_election.cc')
| -rw-r--r-- | src/test/mon/test_election.cc | 1003 |
1 files changed, 1003 insertions, 0 deletions
diff --git a/src/test/mon/test_election.cc b/src/test/mon/test_election.cc new file mode 100644 index 000000000..a232d7355 --- /dev/null +++ b/src/test/mon/test_election.cc @@ -0,0 +1,1003 @@ +// -*- mode:C; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include "gtest/gtest.h" +#include "mon/ElectionLogic.h" +#include "mon/ConnectionTracker.h" +#include "common/dout.h" + +#include "global/global_context.h" +#include "global/global_init.h" +#include "common/common_init.h" +#include "common/ceph_argparse.h" + +using namespace std; + +#define dout_subsys ceph_subsys_test +#undef dout_prefix +#define dout_prefix _prefix(_dout, prefix_name(), timestep_count()) +static ostream& _prefix(std::ostream *_dout, const char *prefix, int timesteps) { + return *_dout << prefix << timesteps << " "; +} + +const char* prefix_name() { return "test_election: "; } +int timestep_count() { return -1; } + +int main(int argc, char **argv) { + vector<const char*> args(argv, argv+argc); + bool user_set_debug = false; + for (auto& arg : args) { + if (strncmp("--debug_mon", arg, 11) == 0) user_set_debug = true; + } + auto cct = global_init(NULL, args, CEPH_ENTITY_TYPE_CLIENT, + CODE_ENVIRONMENT_UTILITY, + CINIT_FLAG_NO_DEFAULT_CONFIG_FILE); + common_init_finish(g_ceph_context); + if (!user_set_debug) g_ceph_context->_conf.set_val("debug mon", "0/20"); + + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} + + +class Owner; +struct Election { + map<int, Owner*> electors; + map<int, set<int> > blocked_messages; + int count; + ElectionLogic::election_strategy election_strategy; + int ping_interval; + set<int> disallowed_leaders; + + vector< function<void()> > messages; + int pending_election_messages; + int timesteps_run = 0; + int last_quorum_change = 0; + int last_quorum_formed = -1; + set<int> last_quorum_reported; + int last_leader = -1; + + Election(int c, ElectionLogic::election_strategy es, int pingi=1, double tracker_halflife=5); + ~Election(); + // ElectionOwner interfaces + int get_paxos_size() { return count; } + const set<int>& get_disallowed_leaders() const { return disallowed_leaders; } + void propose_to(int from, int to, epoch_t e, bufferlist& cbl); + void defer_to(int from, int to, epoch_t e); + void claim_victory(int from, int to, epoch_t e, const set<int>& members); + void accept_victory(int from, int to, epoch_t e); + void report_quorum(const set<int>& quorum); + void queue_stable_message(int from, int to, function<void()> m); + void queue_timeout_message(int from, int to, function<void()> m); + void queue_stable_or_timeout(int from, int to, + function<void()> m, function<void()> t); + void queue_election_message(int from, int to, function<void()> m); + + // test runner interfaces + int run_timesteps(int max); + void start_one(int who); + void start_all(); + bool election_stable() const; + bool quorum_stable(int timesteps_stable) const; + bool all_agree_on_leader() const; + bool check_epoch_agreement() const; + void block_messages(int from, int to); + void block_bidirectional_messages(int a, int b); + void unblock_messages(int from, int to); + void unblock_bidirectional_messages(int a, int b); + void add_disallowed_leader(int disallowed) { disallowed_leaders.insert(disallowed); } + void remove_elector(int rank); + const char* prefix_name() const { return "Election: "; } + int timestep_count() const { return timesteps_run; } +}; +struct Owner : public ElectionOwner, RankProvider { + Election *parent; + int rank; + epoch_t persisted_epoch; + bool ever_joined; + ConnectionTracker peer_tracker; + ElectionLogic logic; + set<int> quorum; + int victory_accepters; + int timer_steps; // timesteps until we trigger timeout + bool timer_election; // the timeout is for normal election, or victory + bool rank_deleted = false; + string prefix_str; + Owner(int r, ElectionLogic::election_strategy es, double tracker_halflife, + Election *p) : parent(p), rank(r), persisted_epoch(0), + ever_joined(false), + peer_tracker(this, rank, tracker_halflife, 5, g_ceph_context), + logic(this, es, &peer_tracker, 0.0005, g_ceph_context), + victory_accepters(0), + timer_steps(-1), timer_election(true) { + std::stringstream str; + str << "Owner" << rank << " "; + prefix_str = str.str(); + } + + // in-memory store: just save to variable + void persist_epoch(epoch_t e) { persisted_epoch = e; } + // in-memory store: just return variable + epoch_t read_persisted_epoch() const { return persisted_epoch; } + // in-memory store: don't need to validate + void validate_store() { return; } + // don't need to do anything with our state right now + void notify_bump_epoch() {} + void notify_rank_removed(int removed_rank) { + ldout(g_ceph_context, 1) << "removed_rank: " << removed_rank << dendl; + ldout(g_ceph_context, 1) << "rank before: " << rank << dendl; + if (removed_rank < rank) { + --rank; + } + peer_tracker.notify_rank_removed(removed_rank, rank); + ldout(g_ceph_context, 1) << "rank after: " << rank << dendl; + } + void notify_deleted() { rank_deleted = true; rank = -1; cancel_timer(); } + // pass back to ElectionLogic; we don't need this redirect ourselves + void trigger_new_election() { ceph_assert (!rank_deleted); logic.start(); } + int get_my_rank() const { return rank; } + // we don't need to persist scores as we don't reset and lose memory state + void persist_connectivity_scores() {} + void propose_to_peers(epoch_t e, bufferlist& bl) { + ceph_assert (!rank_deleted); + for (int i = 0; i < parent->get_paxos_size(); ++i) { + if (i == rank) continue; + parent->propose_to(rank, i, e, bl); + } + } + void reset_election() { + ceph_assert (!rank_deleted); + _start(); + logic.start(); + } + bool ever_participated() const { return ever_joined; } + unsigned paxos_size() const { return parent->get_paxos_size(); } + const set<int>& get_disallowed_leaders() const { + return parent->get_disallowed_leaders(); + } + void cancel_timer() { + timer_steps = -1; + } + void reset_timer(int steps) { + cancel_timer(); + timer_steps = 3 + steps; // FIXME? magic number, current step + roundtrip + timer_election = true; + } + void start_victory_timer() { + cancel_timer(); + timer_election = false; + timer_steps = 3; // FIXME? current step + roundtrip + } + void _start() { + reset_timer(0); + quorum.clear(); + } + void _defer_to(int who) { + ceph_assert (!rank_deleted); + parent->defer_to(rank, who, logic.get_epoch()); + reset_timer(0); // wtf does changing this 0->1 cause breakage? + } + void message_victory(const std::set<int>& members) { + ceph_assert (!rank_deleted); + for (auto i : members) { + if (i == rank) continue; + parent->claim_victory(rank, i, logic.get_epoch(), members); + } + start_victory_timer(); + quorum = members; + victory_accepters = 1; + } + bool is_current_member(int r) const { return quorum.count(r) != 0; } + void receive_propose(int from, epoch_t e, ConnectionTracker *oct) { + if (rank_deleted) return; + logic.receive_propose(from, e, oct); + delete oct; + } + void receive_ack(int from, epoch_t e) { + if (rank_deleted) return; + if (e < logic.get_epoch()) + return; + logic.receive_ack(from, e); + } + void receive_victory_claim(int from, epoch_t e, const set<int>& members) { + if (rank_deleted) return; + if (e < logic.get_epoch()) + return; + if (logic.receive_victory_claim(from, e)) { + quorum = members; + cancel_timer(); + parent->accept_victory(rank, from, e); + } + } + void receive_victory_ack(int from, epoch_t e) { + if (rank_deleted) return; + if (e < logic.get_epoch()) + return; + ++victory_accepters; + if (victory_accepters == static_cast<int>(quorum.size())) { + cancel_timer(); + parent->report_quorum(quorum); + } + } + void receive_scores(bufferlist bl) { + ConnectionTracker oct(bl, g_ceph_context); + peer_tracker.receive_peer_report(oct); + ldout(g_ceph_context, 10) << "received scores " << oct << dendl; + } + void receive_ping(int from_rank, bufferlist bl) { + ldout(g_ceph_context, 6) << "receive ping from " << from_rank << dendl; + peer_tracker.report_live_connection(from_rank, parent->ping_interval); + receive_scores(bl); + } + void receive_ping_timeout(int from_rank) { + ldout(g_ceph_context, 6) << "timeout ping from " << from_rank << dendl; + peer_tracker.report_dead_connection(from_rank, parent->ping_interval); + } + void election_timeout() { + ldout(g_ceph_context, 2) << "election epoch " << logic.get_epoch() + << " timed out for " << rank + << ", electing me:" << logic.electing_me + << ", acked_me:" << logic.acked_me << dendl; + ceph_assert (!rank_deleted); + logic.end_election_period(); + } + void victory_timeout() { + ldout(g_ceph_context, 2) << "victory epoch " << logic.get_epoch() + << " timed out for " << rank + << ", electing me:" << logic.electing_me + << ", acked_me:" << logic.acked_me << dendl; + ceph_assert (!rank_deleted); + reset_election(); + } + void encode_scores(bufferlist& bl) { + encode(peer_tracker, bl); + } + void send_pings() { + ceph_assert (!rank_deleted); + if (!parent->ping_interval || + parent->timesteps_run % parent->ping_interval != 0) { + return; + } + + bufferlist bl; + encode_scores(bl); + for (int i = 0; i < parent->get_paxos_size(); ++i) { + if (i == rank) + continue; + Owner *o = parent->electors[i]; + parent->queue_stable_or_timeout(rank, i, + [o, r=rank, bl] { o->receive_ping(r, bl); }, + [o, r=rank] { o->receive_ping_timeout(r); } + ); + } + } + void notify_timestep() { + ceph_assert (!rank_deleted); + assert(timer_steps != 0); + if (timer_steps > 0) { + --timer_steps; + } + if (timer_steps == 0) { + if (timer_election) { + election_timeout(); + } else { + victory_timeout(); + } + } + send_pings(); + } + const char *prefix_name() const { + return prefix_str.c_str(); + } + int timestep_count() const { return parent->timesteps_run; } +}; + +Election::Election(int c, ElectionLogic::election_strategy es, int pingi, + double tracker_halflife) : count(c), election_strategy(es), ping_interval(pingi), + pending_election_messages(0), timesteps_run(0), last_quorum_change(0), last_quorum_formed(-1) +{ + for (int i = 0; i < count; ++i) { + electors[i] = new Owner(i, election_strategy, tracker_halflife, this); + } +} + +Election::~Election() +{ + { + for (auto i : electors) { + delete i.second; + } + } +} + +void Election::queue_stable_message(int from, int to, function<void()> m) +{ + if (!blocked_messages[from].count(to)) { + messages.push_back(m); + } +} + +void Election::queue_election_message(int from, int to, function<void()> m) +{ + if (last_quorum_reported.count(from)) { + last_quorum_change = timesteps_run; + last_quorum_reported.clear(); + last_leader = -1; + } + if (!blocked_messages[from].count(to)) { + bufferlist bl; + electors[from]->encode_scores(bl); + Owner *o = electors[to]; + messages.push_back([this,m,o,bl] { + --this->pending_election_messages; + o->receive_scores(bl); + m(); + }); + ++pending_election_messages; + } +} + +void Election::queue_timeout_message(int from, int to, function<void()> m) +{ + ceph_assert(blocked_messages[from].count(to)); + messages.push_back(m); +} + +void Election::queue_stable_or_timeout(int from, int to, + function<void()> m, function<void()> t) +{ + if (blocked_messages[from].count(to)) { + queue_timeout_message(from, to, t); + } else { + queue_stable_message(from, to, m); + } +} + +void Election::defer_to(int from, int to, epoch_t e) +{ + Owner *o = electors[to]; + queue_election_message(from, to, [o, from, e] { + o->receive_ack(from, e); + }); +} + +void Election::propose_to(int from, int to, epoch_t e, bufferlist& cbl) +{ + Owner *o = electors[to]; + ConnectionTracker *oct = NULL; + if (cbl.length()) { + oct = new ConnectionTracker(cbl, g_ceph_context); // we leak these on blocked cons, meh + } + queue_election_message(from, to, [o, from, e, oct] { + o->receive_propose(from, e, oct); + }); +} + +void Election::claim_victory(int from, int to, epoch_t e, const set<int>& members) +{ + Owner *o = electors[to]; + queue_election_message(from, to, [o, from, e, members] { + o->receive_victory_claim(from, e, members); + }); +} + +void Election::accept_victory(int from, int to, epoch_t e) +{ + Owner *o = electors[to]; + queue_election_message(from, to, [o, from, e] { + o->receive_victory_ack(from, e); + }); +} + +void Election::report_quorum(const set<int>& quorum) +{ + for (int i : quorum) { + electors[i]->ever_joined = true; + } + last_quorum_formed = last_quorum_change = timesteps_run; + last_quorum_reported = quorum; + last_leader = electors[*(quorum.begin())]->logic.get_election_winner(); +} + +int Election::run_timesteps(int max) +{ + vector< function<void()> > current_m; + int steps = 0; + for (; (!max || steps < max) && // we have timesteps left AND ONE OF + (pending_election_messages || // there are messages pending. + !election_stable()); // somebody's not happy and will act in future + ++steps) { + current_m.clear(); + current_m.swap(messages); + ++timesteps_run; + for (auto& m : current_m) { + m(); + } + for (auto o : electors) { + o.second->notify_timestep(); + } + } + + return steps; +} + +void Election::start_one(int who) +{ + assert(who < static_cast<int>(electors.size())); + electors[who]->logic.start(); +} + +void Election::start_all() { + for (auto e : electors) { + e.second->logic.start(); + } +} + +bool Election::election_stable() const +{ + // see if anybody has a timer running + for (auto i : electors) { + if (i.second->timer_steps != -1) { + ldout(g_ceph_context, 30) << "rank " << i.first << " has timer value " << i.second->timer_steps << dendl; + return false; + } + } + return (pending_election_messages == 0); +} + +bool Election::quorum_stable(int timesteps_stable) const +{ + ldout(g_ceph_context, 1) << "quorum_stable? last formed:" << last_quorum_formed + << ", last changed " << last_quorum_change + << ", last reported members " << last_quorum_reported << dendl; + if (last_quorum_reported.empty()) { + return false; + } + if (last_quorum_formed < last_quorum_change) { + return false; + } + for (auto i : last_quorum_reported) { + if (electors.find(i)->second->timer_steps != -1) { + return false; + } + } + if (timesteps_run - timesteps_stable > last_quorum_change) + return true; + return election_stable(); +} + +bool Election::all_agree_on_leader() const +{ + int leader = electors.find(0)->second->logic.get_election_winner(); + ldout(g_ceph_context, 10) << "all_agree_on_leader on " << leader << dendl; + for (auto& i: electors) { + if (leader != i.second->logic.get_election_winner()) { + ldout(g_ceph_context, 10) << "rank " << i.first << " has different leader " + << i.second->logic.get_election_winner() << dendl; + return false; + } + } + if (disallowed_leaders.count(leader)) { + ldout(g_ceph_context, 10) << "that leader is disallowed! member of " + << disallowed_leaders << dendl; + return false; + } + return true; +} + +bool Election::check_epoch_agreement() const +{ + epoch_t epoch = electors.find(0)->second->logic.get_epoch(); + for (auto& i : electors) { + if (epoch != i.second->logic.get_epoch()) { + return false; + } + } + return true; +} + +void Election::block_messages(int from, int to) +{ + blocked_messages[from].insert(to); +} +void Election::block_bidirectional_messages(int a, int b) +{ + block_messages(a, b); + block_messages(b, a); +} +void Election::unblock_messages(int from, int to) +{ + blocked_messages[from].erase(to); +} +void Election::unblock_bidirectional_messages(int a, int b) +{ + unblock_messages(a, b); + unblock_messages(b, a); +} + +void Election::remove_elector(int rank) +{ + for (auto ei = electors.begin(); ei != electors.end(); ) { + if (ei->first == rank) { + ei->second->notify_deleted(); + electors.erase(ei++); + continue; + } + ei->second->notify_rank_removed(rank); + if (ei->first > rank) { + electors[ei->first - 1] = ei->second; + electors.erase(ei++); + continue; + } + ++ei; + } + for (auto bi = blocked_messages.begin(); bi != blocked_messages.end(); ) { + if (bi->first == rank) { + blocked_messages.erase(bi++); + continue; + } + bi->second.erase(rank); + for (auto i = bi->second.upper_bound(rank); + i != bi->second.end();) { + bi->second.insert(*i - 1); + bi->second.erase(*(i++)); + } + ++bi; + } + --count; +} + +void single_startup_election_completes(ElectionLogic::election_strategy strategy) +{ + for (int starter = 0; starter < 5; ++starter) { + Election election(5, strategy); + election.start_one(starter); + // This test is not actually legit since you should start + // all the ElectionLogics, but it seems to work + int steps = election.run_timesteps(0); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + } +} + +void everybody_starts_completes(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy); + election.start_all(); + int steps = election.run_timesteps(0); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void blocked_connection_continues_election(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy); + election.block_bidirectional_messages(0, 1); + election.start_all(); + int steps = election.run_timesteps(100); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + // This is a failure mode! + ASSERT_FALSE(election.election_stable()); + ASSERT_FALSE(election.quorum_stable(6)); // double the timer_steps we use + election.unblock_bidirectional_messages(0, 1); + steps = election.run_timesteps(100); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void blocked_connection_converges_election(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy); + election.block_bidirectional_messages(0, 1); + election.start_all(); + int steps = election.run_timesteps(100); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + election.unblock_bidirectional_messages(0, 1); + steps = election.run_timesteps(100); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void disallowed_doesnt_win(ElectionLogic::election_strategy strategy) +{ + int MON_COUNT = 5; + for (int i = 0; i < MON_COUNT - 1; ++i) { + Election election(MON_COUNT, strategy); + for (int j = 0; j <= i; ++j) { + election.add_disallowed_leader(j); + } + election.start_all(); + int steps = election.run_timesteps(0); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + int leader = election.electors[0]->logic.get_election_winner(); + for (int j = 0; j <= i; ++j) { + ASSERT_NE(j, leader); + } + } + for (int i = MON_COUNT - 1; i > 0; --i) { + Election election(MON_COUNT, strategy); + for (int j = i; j <= MON_COUNT - 1; ++j) { + election.add_disallowed_leader(j); + } + election.start_all(); + int steps = election.run_timesteps(0); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + int leader = election.electors[0]->logic.get_election_winner(); + for (int j = i; j < MON_COUNT; ++j) { + ASSERT_NE(j, leader); + } + } +} + +void converges_after_flapping(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy); + auto block_cons = [&] { + auto& e = election; + // leave 4 connected to both sides so it will trigger but not trivially win + e.block_bidirectional_messages(0, 2); + e.block_bidirectional_messages(0, 3); + e.block_bidirectional_messages(1, 2); + e.block_bidirectional_messages(1, 3); + }; + auto unblock_cons = [&] { + auto& e = election; + e.unblock_bidirectional_messages(0, 2); + e.unblock_bidirectional_messages(0, 3); + e.unblock_bidirectional_messages(1, 2); + e.unblock_bidirectional_messages(1, 3); + }; + block_cons(); + election.start_all(); + for (int i = 0; i < 5; ++i) { + election.run_timesteps(5); + unblock_cons(); + election.run_timesteps(5); + block_cons(); + } + unblock_cons(); + election.run_timesteps(100); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void converges_while_flapping(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy); + auto block_cons = [&] { + auto& e = election; + // leave 4 connected to both sides so it will trigger but not trivially win + e.block_bidirectional_messages(0, 2); + e.block_bidirectional_messages(0, 3); + e.block_bidirectional_messages(1, 2); + e.block_bidirectional_messages(1, 3); + }; + auto unblock_cons = [&] { + auto& e = election; + e.unblock_bidirectional_messages(0, 2); + e.unblock_bidirectional_messages(0, 3); + e.unblock_bidirectional_messages(1, 2); + e.unblock_bidirectional_messages(1, 3); + }; + block_cons(); + election.start_all(); + for (int i = 0; i < 5; ++i) { + election.run_timesteps(10); + ASSERT_TRUE(election.quorum_stable(6)); + unblock_cons(); + election.run_timesteps(5); + block_cons(); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + } + unblock_cons(); + election.run_timesteps(100); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void netsplit_with_disallowed_tiebreaker_converges(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy); + election.add_disallowed_leader(4); + auto netsplit = [&] { + auto& e = election; + e.block_bidirectional_messages(0, 2); + e.block_bidirectional_messages(0, 3); + e.block_bidirectional_messages(1, 2); + e.block_bidirectional_messages(1, 3); + }; + auto unsplit = [&] { + auto& e = election; + e.unblock_bidirectional_messages(0, 2); + e.unblock_bidirectional_messages(0, 3); + e.unblock_bidirectional_messages(1, 2); + e.unblock_bidirectional_messages(1, 3); + }; + // hmm, we don't have timeouts to call elections automatically yet + auto call_elections = [&] { + for (auto i : election.electors) { + i.second->trigger_new_election(); + } + }; + // turn everybody on, run happy for a while + election.start_all(); + election.run_timesteps(0); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + int starting_leader = election.last_leader; + // do some netsplits, but leave disallowed tiebreaker alive + for (int i = 0; i < 5; ++i) { + netsplit(); + call_elections(); + election.run_timesteps(15); // tests fail when I run 10 because 0 and 1 time out on same timestamp for some reason, why? + // this ASSERT_EQ only holds while we bias for ranks + ASSERT_EQ(starting_leader, election.last_leader); + ASSERT_TRUE(election.quorum_stable(6)); + ASSERT_FALSE(election.election_stable()); + unsplit(); + call_elections(); + election.run_timesteps(10); + ASSERT_EQ(starting_leader, election.last_leader); + ASSERT_TRUE(election.quorum_stable(6)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + } + + // now disconnect the tiebreaker and make sure nobody can win + int presplit_quorum_time = election.last_quorum_formed; + netsplit(); + election.block_bidirectional_messages(4, 0); + election.block_bidirectional_messages(4, 1); + election.block_bidirectional_messages(4, 2); + election.block_bidirectional_messages(4, 3); + call_elections(); + election.run_timesteps(100); + ASSERT_EQ(election.last_quorum_formed, presplit_quorum_time); + + // now let in the previously-losing side + election.unblock_bidirectional_messages(4, 2); + election.unblock_bidirectional_messages(4, 3); + call_elections(); + election.run_timesteps(100); + ASSERT_TRUE(election.quorum_stable(50)); + ASSERT_FALSE(election.election_stable()); + + // now reconnect everybody + unsplit(); + election.unblock_bidirectional_messages(4, 0); + election.unblock_bidirectional_messages(4, 1); + call_elections(); + election.run_timesteps(100); + ASSERT_TRUE(election.quorum_stable(50)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void handles_singly_connected_peon(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy); + election.block_bidirectional_messages(0, 1); + election.block_bidirectional_messages(0, 2); + election.block_bidirectional_messages(0, 3); + election.block_bidirectional_messages(0, 4); + + election.start_all(); + election.run_timesteps(20); + ASSERT_TRUE(election.quorum_stable(5)); + ASSERT_FALSE(election.election_stable()); + + election.unblock_bidirectional_messages(0, 1); + election.run_timesteps(100); + ASSERT_TRUE(election.quorum_stable(50)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + + election.block_bidirectional_messages(0, 1); + election.unblock_bidirectional_messages(0, 4); + for (auto i : election.electors) { + i.second->trigger_new_election(); + } + election.run_timesteps(15); + ASSERT_TRUE(election.quorum_stable(50)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +ConnectionReport *get_connection_reports(ConnectionTracker& ct) { + return &ct.my_reports; +} +map<int,ConnectionReport> *get_peer_reports(ConnectionTracker& ct) { + return &ct.peer_reports; +} +void handles_outdated_scoring(ElectionLogic::election_strategy strategy) +{ + Election election(3, strategy, 5); // ping every 5 timesteps so they start elections before settling scores! + + // start everybody up and run for a bit + election.start_all(); + election.run_timesteps(20); + ASSERT_TRUE(election.quorum_stable(5)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + + // now mess up the scores to disagree + ConnectionTracker& ct0 = election.electors[0]->peer_tracker; + ConnectionReport& cr0 = *get_connection_reports(ct0); + cr0.history[1] = 0.5; + cr0.history[2] = 0.5; + ct0.increase_version(); + ConnectionTracker& ct1 = election.electors[1]->peer_tracker; + ConnectionReport& cr1 = *get_connection_reports(ct1); + cr1.history[0] = 0.5; + cr1.history[2] = 0.5; + ct1.increase_version(); + ConnectionTracker& ct2 = election.electors[2]->peer_tracker; + ConnectionReport& cr2 = *get_connection_reports(ct2); + cr2.history[0] = 0.5; + map<int,ConnectionReport>&cp2 = *get_peer_reports(ct2); + cp2[0].history[2] = 0; + cp2[1].history[2] = 0; + ct2.increase_version(); + election.ping_interval = 0; // disable pinging to update the scores + ldout(g_ceph_context, 5) << "mangled the scores to be different" << dendl; + + election.start_all(); + election.run_timesteps(50); + ASSERT_TRUE(election.quorum_stable(30)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void handles_disagreeing_connectivity(ElectionLogic::election_strategy strategy) +{ + Election election(5, strategy, 5); // ping every 5 timesteps so they start elections before settling scores! + + // start everybody up and run for a bit + election.start_all(); + election.run_timesteps(20); + ASSERT_TRUE(election.quorum_stable(5)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + + // block all the connections + for (int i = 0; i < 5; ++i) { + for (int j = i+1; j < 5; ++j) { + election.block_bidirectional_messages(i, j); + } + } + + // now start them electing, which will obviously fail + election.start_all(); + election.run_timesteps(50); // let them all demote scores of their peers + ASSERT_FALSE(election.quorum_stable(10)); + ASSERT_FALSE(election.election_stable()); + + // now reconnect them, at which point they should start running an election before exchanging scores + for (int i = 0; i < 5; ++i) { + for (int j = i+1; j < 5; ++j) { + election.unblock_bidirectional_messages(i, j); + } + } + election.run_timesteps(100); + + // these will pass if the nodes managed to converge on scores, but I expect failure + ASSERT_TRUE(election.quorum_stable(5)); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); +} + +void handles_removing_ranks(ElectionLogic::election_strategy strategy) +{ + ceph_assert(strategy == ElectionLogic::CONNECTIVITY); + for (int deletee = 0; deletee < 5; ++deletee) { + Election election(5, strategy); + election.start_all(); + int steps = election.run_timesteps(0); + ldout(g_ceph_context, 10) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + election.remove_elector(deletee); + ldout(g_ceph_context, 1) << "removed rank " << deletee << " from set" << dendl; + election.start_all(); + steps = election.run_timesteps(0); + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + } + { + Election election(7, strategy); + for (int i = 0; i < (7 - 3); ++i) { + election.start_all(); + election.remove_elector(0); + int steps = election.run_timesteps(0); + ldout(g_ceph_context, 1) << "ran in " << steps << " timesteps" << dendl; + ASSERT_TRUE(election.election_stable()); + ASSERT_TRUE(election.quorum_stable(6)); // double the timer_steps we use + ASSERT_TRUE(election.all_agree_on_leader()); + ASSERT_TRUE(election.check_epoch_agreement()); + } + } +} + +// TODO: write a test with more complicated connectivity graphs and make sure +// they are stable with multiple disconnected ranks pinging peons + +// TODO: Write a test that disallowing and disconnecting 0 is otherwise stable? + +// TODO: figure out how to test for bumping election epochs with changing scores, +// a la what happened in run +// http://pulpito.ceph.com/gregf-2019-11-26_10:50:50-rados:monthrash-wip-elector-distro-basic-mira/ + +#define test_classic(utest) TEST(classic, utest) { utest(ElectionLogic::CLASSIC); } + +#define test_disallowed(utest) TEST(disallowed, utest) { utest(ElectionLogic::DISALLOW); } + +#define test_connectivity(utest) TEST(connectivity, utest) { utest(ElectionLogic::CONNECTIVITY); } + + +// TODO: test for expected failures; gtest probably supports that? +test_classic(single_startup_election_completes) +test_classic(everybody_starts_completes) +test_classic(blocked_connection_continues_election) +test_classic(converges_after_flapping) + +test_disallowed(single_startup_election_completes) +test_disallowed(everybody_starts_completes) +test_disallowed(blocked_connection_continues_election) +test_disallowed(disallowed_doesnt_win) +test_disallowed(converges_after_flapping) + +/* skip single_startup_election_completes because we crash + on init conditions. That's fine since as noted above it's not + quite following the rules anyway. */ +test_connectivity(everybody_starts_completes) +test_connectivity(blocked_connection_converges_election) +test_connectivity(disallowed_doesnt_win) +test_connectivity(converges_after_flapping) +test_connectivity(converges_while_flapping) +test_connectivity(netsplit_with_disallowed_tiebreaker_converges) +test_connectivity(handles_singly_connected_peon) +test_connectivity(handles_disagreeing_connectivity) +test_connectivity(handles_outdated_scoring) +test_connectivity(handles_removing_ranks) |