系統設計

1type Entry = { term: number; cmd: string };
2type Msg = { type: string; from: number; to: number; term: number; [field: string]: any };
3 
4class RaftNode {
5  role = "follower";
6  term = 0;
7  votedFor: number | null = null;
8  log: Entry[] = [];
9  commitIndex = 0;
10  votes = new Set<number>();
11  nextIndex: number[];
12  matchIndex: number[];
13 
14  constructor(public id: number, public n: number) {
15    this.nextIndex = new Array(n).fill(1);
16    this.matchIndex = new Array(n).fill(0);
17  }
18 
19  lastIndex() { return this.log.length; }
20  lastTerm() { return this.log.length ? this.log[this.log.length - 1].term : 0; }
21 
22  stepDown(term: number) {
23    if (term <= this.term) return;
24    this.term = term;
25    this.role = "follower";
26    this.votedFor = null;
27  }
28 
29  // The election timer ran out without hearing from a leader.
30  startElection(): Msg[] {
31    this.term += 1;
32    this.role = "candidate";
33    this.votedFor = this.id;
34    this.votes = new Set([this.id]);
35    const out: Msg[] = [];
36    for (let p = 0; p < this.n; p++) {
37      if (p !== this.id) out.push({ type: "vote", from: this.id, to: p, term: this.term,
38        lastIndex: this.lastIndex(), lastTerm: this.lastTerm() });
39    }
40    return out;
41  }
42 
43  onRequestVote(m: Msg): Msg {
44    this.stepDown(m.term);
45    const upToDate = m.lastTerm > this.lastTerm() ||
46      (m.lastTerm === this.lastTerm() && m.lastIndex >= this.lastIndex());
47    const granted = m.term === this.term &&
48      (this.votedFor === null || this.votedFor === m.from) && upToDate;
49    if (granted) this.votedFor = m.from;
50    return { type: "voteReply", from: this.id, to: m.from, term: this.term, granted };
51  }
52 
53  onVoteReply(m: Msg): Msg[] {
54    this.stepDown(m.term);
55    if (this.role !== "candidate" || m.term !== this.term || !m.granted) return [];
56    this.votes.add(m.from);
57    if (this.votes.size * 2 <= this.n) return [];
58    this.role = "leader";
59    this.nextIndex.fill(this.lastIndex() + 1);
60    this.matchIndex.fill(0);
61    this.matchIndex[this.id] = this.lastIndex();
62    return this.heartbeat();
63  }
64 
65  propose(cmd: string): Msg[] | null {
66    if (this.role !== "leader") return null;            // only a leader takes writes
67    this.log.push({ term: this.term, cmd });
68    this.matchIndex[this.id] = this.lastIndex();
69    return this.heartbeat();
70  }
71 
72  heartbeat(): Msg[] {
73    const out: Msg[] = [];
74    for (let p = 0; p < this.n; p++) if (p !== this.id) out.push(this.appendFor(p));
75    return out;
76  }
77 
78  appendFor(p: number): Msg {
79    const prevIndex = this.nextIndex[p] - 1;
80    const prevTerm = prevIndex > 0 ? this.log[prevIndex - 1].term : 0;
81    return { type: "append", from: this.id, to: p, term: this.term, prevIndex, prevTerm,
82      entries: this.log.slice(prevIndex), leaderCommit: this.commitIndex };
83  }
84 
85  onAppendEntries(m: Msg): Msg {
86    this.stepDown(m.term);
87    const reply = (success: boolean, matchIndex: number) =>
88      ({ type: "appendReply", from: this.id, to: m.from, term: this.term, success, matchIndex });
89    if (m.term < this.term) return reply(false, 0);    // a deposed leader
90    this.role = "follower";
91    if (m.prevIndex > this.lastIndex() ||
92        (m.prevIndex > 0 && this.log[m.prevIndex - 1].term !== m.prevTerm)) {
93      return reply(false, 0);
94    }
95    for (let k = 0; k < m.entries.length; k++) {
96      const index = m.prevIndex + 1 + k;
97      if (index <= this.lastIndex() && this.log[index - 1].term !== m.entries[k].term) {
98        this.log.length = index - 1;
99      }
100      if (index > this.lastIndex()) this.log.push(m.entries[k]);
101    }
102    const match = m.prevIndex + m.entries.length;
103    if (m.leaderCommit > this.commitIndex) {
104      this.commitIndex = Math.max(this.commitIndex, Math.min(m.leaderCommit, match));
105    }
106    return reply(true, match);
107  }
108 
109  onAppendReply(m: Msg): Msg[] {
110    this.stepDown(m.term);
111    if (this.role !== "leader" || m.term !== this.term) return [];
112    if (!m.success) {
113      this.nextIndex[m.from] = Math.max(1, this.nextIndex[m.from] - 1); // back up and retry
114      return [this.appendFor(m.from)];
115    }
116    this.matchIndex[m.from] = Math.max(this.matchIndex[m.from], m.matchIndex);
117    this.nextIndex[m.from] = this.matchIndex[m.from] + 1;
118    // Commit the newest entry of this term that a majority holds.
119    for (let index = this.lastIndex(); index > this.commitIndex; index--) {
120      if (this.log[index - 1].term !== this.term) break;
121      const holders = this.matchIndex.filter((x) => x >= index).length;
122      if (holders * 2 > this.n) { this.commitIndex = index; break; }
123    }
124    return [];
125  }
126 
127  restart() {                                           // term, vote and log were on disk
128    this.role = "follower";
129    this.votes = new Set();
130  }
131 
132  handle(m: Msg): Msg[] {
133    if (m.type === "vote") return [this.onRequestVote(m)];
134    if (m.type === "voteReply") return this.onVoteReply(m);
135    if (m.type === "append") return [this.onAppendEntries(m)];
136    return this.onAppendReply(m);
137  }
138}