[Tarantool-patches] [PATCH 4/8] test: introduce raft unit tests
Serge Petrenko
sergepetrenko at tarantool.org
Wed Dec 16 16:03:04 MSK 2020
13.12.2020 20:15, Vladislav Shpilevoy пишет:
> Raft algorithm was tested only by functional Lua tests, as a part
> of the Tarantool executable.
>
> Functional testing of something like raft algorithm has drawbacks:
>
> - Not possible or too hard to cover some cases without error
> injections and/or good stability. Such as invalid messages, or
> small time durations, or a complex case which needs multiple
> steps to be reproduced. For instance, start WAL write, receive a
> message, finish the WAL write, and see if an expected thing
> happens.
>
> - Too long time to run when need to test not tiny timeouts. On the
> other hand, with tiny timeouts the test would become unstable.
>
> - Poor reproducibility due to random used in raft, due to system
> load, and number of other tests running in parallel.
>
> - Hard to debug, because for raft it is necessary to start one
> Tarantool process per raft instance.
>
> - Involves too much other systems, such as threads, real journal,
> relays, appliers, and so on. They can affect the process on the
> whole and reduce reproducibility and debug simplicity even more.
>
> Exactly the same problem existed for SWIM algorithm implemented as
> a module 'swim'. In order to test it, swim was moved to a separate
> library, refactored to be able to start many swims in the process
> (no global variables), its functions talking to other systems
> were virtualized (swim_ev, swim_transport), and substituted in the
> unit tests with fake analogue systems.
>
> In the unit tests these virtual functions were implemented
> differently, but the core swim algorithm was left intact and
> properly tested.
>
> The same is done for raft. This patch implements a set of helper
> functions and objects to unit test raft in raft_test_utils.c/.h
> files, and uses it to cover almost all the raft algorithm code.
>
> During implementation of the tests some bugs were found, which are
> not covered here, but fixed and covered in next commits.
>
> Part of #5303
> ---
Hi! Thanks for the patch!
Please find my 6 comments below.
I've dropped the hunks where I have no comments so that the
letter is easier to follow.
> test/unit/CMakeLists.txt | 3 +
> test/unit/raft.c | 1199 +++++++++++++++++++++++++++++++++++
> test/unit/raft.result | 207 ++++++
> test/unit/raft_test_utils.c | 557 ++++++++++++++++
> test/unit/raft_test_utils.h | 287 +++++++++
> 5 files changed, 2253 insertions(+)
> create mode 100644 test/unit/raft.c
> create mode 100644 test/unit/raft.result
> create mode 100644 test/unit/raft_test_utils.c
> create mode 100644 test/unit/raft_test_utils.h
>
>
> diff --git a/test/unit/raft.c b/test/unit/raft.c
> new file mode 100644
> index 000000000..dfb5f8e43
> --- /dev/null
> +++ b/test/unit/raft.c
<stripped>
> +
> +static void
> +raft_test_vote_skip(void)
> +{
> + raft_start_test(33);
> + struct raft_node node;
> + raft_node_create(&node);
> +
> + /* Everything is skipped if the term is outdated. */
1. Let's also test a case when vote response has greater term than the
candidate itself.
> +
> + raft_run_next_event();
> + is(node.raft.state, RAFT_STATE_CANDIDATE, "became candidate");
> + is(node.raft.term, 2, "term is bumped");
> +
> + is(raft_node_send_vote_response(&node,
> + 1 /* Term. */,
> + 1 /* Vote. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote_count, 1, "but ignored - too old term");
> +
> + /* Competing vote requests are skipped. */
> +
> + is(raft_node_send_vote_response(&node,
> + 2 /* Term. */,
> + 3 /* Vote. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote_count, 1, "but ignored - vote not for this node");
> + is(node.raft.state, RAFT_STATE_CANDIDATE, "this node does not give up");
> +
> + /* Vote requests are ignored when node is disabled. */
> +
> + raft_node_cfg_is_enabled(&node, false);
> +
> + is(raft_node_send_follower(&node,
> + 3 /* Term. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_FOLLOWER /* State. */,
> + 0 /* Leader. */,
> + 3 /* Term. */,
> + 0 /* Vote. */,
> + 3 /* Volatile term. */,
> + 0 /* Volatile vote. */,
> + "{0: 2}" /* Vclock. */
> + ), "term bump to be able to vote again");
> + is(raft_node_send_vote_request(&node,
> + 3 /* Term. */,
> + "{}" /* Vclock. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 0, "but ignored - node is disabled");
> +
> + /* Disabled node still takes term from the vote request. */
> +
> + is(raft_node_send_vote_request(&node,
> + 4 /* Term. */,
> + "{}" /* Vclock. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_FOLLOWER /* State. */,
> + 0 /* Leader. */,
> + 4 /* Term. */,
> + 0 /* Vote. */,
> + 4 /* Volatile term. */,
> + 0 /* Volatile vote. */,
> + "{0: 3}" /* Vclock. */
> + ), "term is bumped, but vote request is ignored");
> +
> + raft_node_cfg_is_enabled(&node, true);
> +
> + /* Not a candidate won't accept vote request for self. */
> +
> + is(raft_node_send_vote_response(&node,
> + 4 /* Term. */,
> + 1 /* Vote. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 0, "but ignored - vote works only on a candidate");
> +
> + /* Ignore vote response for some third node. */
> +
> + is(raft_node_send_vote_response(&node,
> + 4 /* Term. */,
> + 3 /* Vote. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 0, "but ignored - sender != vote, so it is not a "
> + "request");
> +
> + /* Ignore if leader is already known. */
> +
> + is(raft_node_send_leader(&node,
> + 4 /* Term. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.leader, 2, "leader is accepted");
> +
> + is(raft_node_send_vote_request(&node,
> + 4 /* Term. */,
> + "{}" /* Vclock. */,
> + 3 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 0, "but ignored - leader is already known");
> + is(node.raft.leader, 2, "leader is not changed");
> +
> + /* Ignore too small vclock. */
> +
> + /*
> + * Need to turn off the candidate role to bump the term and not become
> + * a candidate.
> + */
> + raft_node_cfg_is_candidate(&node, false);
> +
> + raft_node_journal_follow(&node, 1, 5);
> + raft_node_journal_follow(&node, 2, 5);
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_FOLLOWER /* State. */,
> + 2 /* Leader. */,
> + 4 /* Term. */,
> + 0 /* Vote. */,
> + 4 /* Volatile term. */,
> + 0 /* Volatile vote. */,
> + "{0: 3, 1: 5, 2: 5}" /* Vclock. */
> + ), "vclock is bumped");
> +
> + is(raft_node_send_vote_request(&node,
> + 5 /* Term. */,
> + "{1: 4}" /* Vclock. */,
> + 3 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 0, "but ignored - vclock is too small");
> + is(node.raft.term, 5, "new term");
> + is(node.raft.leader, 0, "leader is dropped in the new term");
> +
> + /* Ignore incomparable vclock. */
> +
> + is(raft_node_send_vote_request(&node,
> + 5 /* Term. */,
> + "{1: 4, 2: 6}" /* Vclock. */,
> + 3 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 0, "but ignored - vclock is incomparable");
> +
> + /* Ignore if voted in the current term. */
> +
> + is(raft_node_send_vote_request(&node,
> + 6 /* Term. */,
> + "{1: 5, 2: 5}" /* Vclock. */,
> + 2 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 2, "voted");
> +
> + is(raft_node_send_vote_request(&node,
> + 6 /* Term. */,
> + "{1: 5, 2: 5}" /* Vclock. */,
> + 3 /* Source. */
> + ), 0, "message is accepted");
> + is(node.raft.vote, 2, "but ignored - already voted in the term");
2. I'd also check the case that the node ignores vote request after restart.
> +
> + raft_node_cfg_is_candidate(&node, true);
> +
> + raft_node_destroy(&node);
> + raft_finish_test();
> +}
<stripped>
> +
> +static void
> +raft_test_heartbeat(void)
> +{
> + raft_start_test(12);
> + struct raft_node node;
> + raft_node_create(&node);
> +
> + /* Let the node know there is a leader somewhere. */
> +
> + is(raft_node_send_leader(&node,
> + 2 /* Term. */,
> + 2 /* Source. */
> + ), 0, "leader notification");
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_FOLLOWER /* State. */,
> + 2 /* Leader. */,
> + 2 /* Term. */,
> + 0 /* Vote. */,
> + 2 /* Volatile term. */,
> + 0 /* Volatile vote. */,
> + "{0: 1}" /* Vclock. */
> + ), "follow the leader after notification");
> +
> + /* Leader can send the same message many times. */
> +
> + is(raft_node_send_leader(&node,
> + 2 /* Term. */,
> + 2 /* Source. */
> + ), 0, "leader notification");
> +
> + /* The node won't do anything if it is not a candidate. */
> +
> + raft_node_cfg_is_candidate(&node, false);
> + raft_run_for(node.cfg_death_timeout * 2);
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_FOLLOWER /* State. */,
> + 2 /* Leader. */,
> + 2 /* Term. */,
> + 0 /* Vote. */,
> + 2 /* Volatile term. */,
> + 0 /* Volatile vote. */,
> + "{0: 1}" /* Vclock. */
> + ), "follow the leader because no candidate");
3. Shouldn't the node reset the leader to 0 even if if it isn't a
candidate itself?
> + raft_node_cfg_is_candidate(&node, true);
> +
> + /* Heartbeats from the leader are accepted. */
> +
> + for (int i = 0; i < 5; ++i) {
> + raft_run_for(node.cfg_death_timeout / 2);
> + raft_node_send_heartbeat(&node, 2);
> + }
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_FOLLOWER /* State. */,
> + 2 /* Leader. */,
> + 2 /* Term. */,
> + 0 /* Vote. */,
> + 2 /* Volatile term. */,
> + 0 /* Volatile vote. */,
> + "{0: 1}" /* Vclock. */
> + ), "follow the leader because had heartbeats");
> +
> + /* Heartbeats not from the leader won't do anything. */
> +
> + double start = raft_time();
> + raft_run_for(node.cfg_death_timeout / 3);
> + raft_node_send_heartbeat(&node, 3);
> + raft_run_for(node.cfg_death_timeout / 3);
> + raft_node_send_heartbeat(&node, 0);
> + raft_run_next_event();
> + ok(raft_time() >= start + node.cfg_death_timeout, "death timeout "
> + "passed");
4. Looks like this test would succeed even if heartbeats from other
instances were counted as leader heartbeats. You simply say
`raft_run_next_event()` which'll make the death timeout fire sooner
or later anyway. I think it's better to add another
`raft_run_for(node.cfg_death_timeout / 2)` to make sure the node
times out exactly when it should.
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_CANDIDATE /* State. */,
> + 0 /* Leader. */,
> + 3 /* Term. */,
> + 1 /* Vote. */,
> + 3 /* Volatile term. */,
> + 1 /* Volatile vote. */,
> + "{0: 2}" /* Vclock. */
> + ), "enter candidate state when no heartbeats from the leader");
> +
> + /* Non-candidate ignores heartbeats. */
> +
> + raft_node_cfg_is_candidate(&node, false);
> + raft_node_send_heartbeat(&node, 2);
> + raft_node_cfg_is_candidate(&node, true);
> +
> + /* Leader ignores all heartbeats - nothing to wait for. */
> +
> + raft_node_new_term(&node);
> + is(raft_node_send_vote_response(&node,
> + 4 /* Term. */,
> + 1 /* Vote. */,
> + 2 /* Source. */
> + ), 0, "vote from 2");
> + is(raft_node_send_vote_response(&node,
> + 4 /* Term. */,
> + 1 /* Vote. */,
> + 3 /* Source. */
> + ), 0, "vote from 3");
> + is(node.raft.state, RAFT_STATE_LEADER, "became leader");
> + /* From self. */
> + raft_node_send_heartbeat(&node, 1);
> + /* From somebody else. */
> + raft_node_send_heartbeat(&node, 2);
> +
> + /* Heartbeats are ignored during WAL write. */
> +
> + raft_node_block(&node);
> + is(raft_node_send_leader(&node,
> + 5 /* Term. */,
> + 2 /* Source. */
> + ), 0, "message from leader");
> + raft_node_send_heartbeat(&node, 2);
> + ok(raft_node_check_full_state(&node,
> + RAFT_STATE_FOLLOWER /* State. */,
> + 2 /* Leader. */,
> + 4 /* Term. */,
> + 1 /* Vote. */,
> + 5 /* Volatile term. */,
> + 0 /* Volatile vote. */,
> + "{0: 4}" /* Vclock. */
> + ), "nothing changed - waiting for WAL write");
> + raft_node_unblock(&node);
> +
> + raft_node_destroy(&node);
> + raft_finish_test();
> +}
> +
<stripped>
> diff --git a/test/unit/raft_test_utils.c b/test/unit/raft_test_utils.c
> new file mode 100644
> index 000000000..4acd74e8f
> --- /dev/null
> +++ b/test/unit/raft_test_utils.c
<stripped>
> +
> +static void
> +raft_method_node_broadcast(struct raft *raft, const struct raft_msg *msg);
> +
> +static void
> +raft_method_node_write(struct raft *raft, const struct raft_msg *msg);
> +
> +static void
> +raft_method_node_schedule_async(struct raft *raft);
> +
5. Why such a long prefix? Why not simply raft_node_broadcast?
Ok, raft_node_broadcast may sound too general and referring more
to a raft test node rather than the raft core itself.
What about raft_node_broadcast_f then?
> +static struct raft_vtab raft_vtab = {
> + .broadcast = raft_method_node_broadcast,
> + .write = raft_method_node_write,
> + .schedule_async = raft_method_node_schedule_async,
> +};
> +
> +static int
> +raft_node_on_update(struct trigger *t, void *event)
> +{
> + struct raft_node *n = t->data;
> + assert(&n->on_update == t);
> + assert(&n->raft == event);
6. `(void) event` for building in release?
> + ++n->update_count;
> + return 0;
> +}
> +
<stripped>
--
Serge Petrenko
More information about the Tarantool-patches
mailing list