1/* @ajax/mesh-fleet-core: the election and commit core (fleet.rs Core), sans-IO.
2 *
3 * Election (Raft's rules, no log). The replicated state is one small document, sent whole, so the
4 * log is a single (term, version) pair.
5 * - Each member persists its term, its vote and two documents: the last it accepted from a leader
6 * and the last it knows committed (mesh-fleet-persist).
7 * - A follower that hears no leader for dead_ms (or whose link to the leader closed) waits
8 * 150 ms x its id + 0..100 ms, then asks for pre-votes (Raft's PreVote): a member grants one only
9 * if it does not hear a leader itself and the candidate's accepted (term, version) is at least its
10 * own. A majority of pre-votes starts a real election: term + 1, one vote per term (persisted
11 * before it is sent), the same up-to-date rule. A majority of the configured N makes a leader.
12 * - A leader that does not hear a majority within dead_ms steps down (CheckQuorum).
13 * - A change: the leader builds the next document from its committed one (version + 1, its term),
14 * persists it, sends it to every linked member (State), commits once a majority persisted it
15 * (StateAck), and tells everyone (Commit). One change is in flight at a time. A member that was
16 * away gets the document when its beat shows it behind.
17 * - N = 2 has no majority after a loss, so a pair keeps a fixed coordinator: system 0 leads (term 1)
18 * and commits alone; system 1 never leads.
19 *
20 * The shell feeds it link changes, ticks and received messages, and carries out the outputs in
21 * order: every Persist is written before anything after it is sent (mfc_durable). */
22#ifndef MESH_FLEET_CORE_H
23#define MESH_FLEET_CORE_H
2425#include "mesh/abi/base.h"
26#include "mesh/fleet_doc.h"
27#include "mesh/fleet_persist.h"
2829#include <stdbool.h>
30#include <stdint.h>
3132/* A document id: (term, version). */
33typedef struct {
34 uint64_t term, version;
35} mfc_id;
3637static inline int mfc_id_cmp(mfc_id a, mfc_id b) { return mfd_id_cmp(a.term, a.version, b.term, b.version); }
38static inline mfc_id mfc_doc_id(const mfd_doc *d) { return (mfc_id){d->term, d->version}; }
3940typedef enum { MFC_BEAT, MFC_VOTE_REQ, MFC_VOTE, MFC_STATE, MFC_STATE_ACK, MFC_COMMIT } mfc_msg_kind;
4142/* The core's wire messages (the peer link encodes them; `from` is the link's member). */
43typedef struct {
44 mfc_msg_kind kind;
45 uint64_t term;
46 bool leader; /* Beat */
47 mfc_id commit, acc; /* Beat: committed and accepted; VoteReq: acc */
48 bool pre; /* VoteReq, Vote */
49 bool granted; /* Vote */
50 mfd_doc doc; /* State */
51 mfc_id ver; /* StateAck, Commit */
52} mfc_msg;
5354mfc_msg mfc_msg_clone(const mfc_msg *m);
55void mfc_msg_free(mfc_msg *m);
5657typedef enum { MFC_FOLLOWER, MFC_PRE_CANDIDATE, MFC_CANDIDATE, MFC_LEADER } mfc_role;
58const char *mfc_role_word(mfc_role r);
59uint32_t mfc_role_code(mfc_role r);
6061typedef struct {
62 uint32_t me, n;
63 uint64_t dead_ms; /* a member silent this long is gone; the election timeout's base */
64 uint64_t seed;
65} mfc_config;
6667uint32_t mfc_quorum(const mfc_config *c); /* a majority of n; 1 for the fixed pair */
68bool mfc_fixed(const mfc_config *c); /* n == 2 */
6970typedef enum { MFC_OUT_PERSIST, MFC_OUT_SEND, MFC_OUT_COMMITTED, MFC_OUT_LEADER, MFC_OUT_DONE, MFC_OUT_LOG } mfc_out_kind;
7172/* What the shell must do after an input, in order. */
73typedef struct {
74 mfc_out_kind kind;
75 uint32_t to; /* Send */
76 mfc_msg msg; /* Send */
77 bool has_leader; /* Leader */
78 uint32_t leader;
79 uint64_t version; /* Done */
80 bool ok; /* Done */
81 char *text; /* Done's error, Log's line */
82} mfc_out;
8384typedef struct {
85 mfc_out *v;
86 size_t n, cap;
87} mfc_outs;
8889void mfc_outs_free(mfc_outs *o);
9091/* A core's outputs made durable, in order: every Persist is written (by persist) before the outputs
92 * after it are carried out. The first write that fails stops it (fail-stop): out keeps the outputs
93 * before it, and false is returned with *err; nothing after it -- no vote, acknowledgement or commit
94 * the disk does not hold -- ever comes out. Persist entries are removed. Takes outs. */
95typedef bool (*mfc_persist_fn)(void *ctx, char **err);
96bool mfc_durable(mfc_outs *outs, mfc_persist_fn persist, void *ctx, char **err);
9798typedef struct mfc_core mfc_core;
99100mfc_core *mfc_new(mfc_config cfg, mfp_persist p, uint64_t now); /* takes p */
101void mfc_free(mfc_core *c);
102103const mfc_config *mfc_cfg(const mfc_core *c);
104const mfp_persist *mfc_persist(const mfc_core *c);
105uint64_t mfc_term(const mfc_core *c);
106mfc_role mfc_role_of(const mfc_core *c);
107bool mfc_leader(const mfc_core *c, uint32_t *leader);
108const mfd_doc *mfc_committed(const mfc_core *c);
109const mfd_doc *mfc_accepted(const mfc_core *c);
110bool mfc_busy(const mfc_core *c);
111/* This leadership committed a document of its own term (until then committed may be behind). */
112bool mfc_term_committed(const mfc_core *c);
113uint64_t mfc_next_version(const mfc_core *c);
114/* The leader's first document of its term: the accepted one; false for a fresh fleet. */
115bool mfc_first_doc(const mfc_core *c, mfd_doc *out);
116uint32_t mfc_linked(const mfc_core *c);
117bool mfc_voted(const mfc_core *c, uint32_t *voted);
118/* Members heard from within dead_ms (this one included). */
119uint32_t mfc_alive(const mfc_core *c, uint64_t now);
120bool mfc_has_quorum(const mfc_core *c, uint64_t now);
121122mfc_outs mfc_link(mfc_core *c, uint32_t k, bool up, uint64_t now);
123mfc_outs mfc_tick(mfc_core *c, uint64_t now);
124/* Takes m. */
125mfc_outs mfc_recv(mfc_core *c, uint32_t from, mfc_msg m, uint64_t now);
126/* This member's beat. */
127mfc_msg mfc_beat(const mfc_core *c);
128/* The leader proposes doc (its version and term are set here; takes doc): true with *version in
129 * flight and *outs, or false with *err why not. */
130bool mfc_propose(mfc_core *c, mfd_doc doc, uint64_t now, uint64_t *version, mfc_outs *outs, char **err);
131132#endif