---
title: 'Split Brain Problem'
source: 'https://academia.sh/en/courses/search-engines/split-brain-problem'
course: 'Search Engines and Text Retrieval'
language: en
updated: '2026-08-23T07:00:51+00:00'
license: 'CC BY-SA 4.0'
---

# Split Brain Problem

Splitting a five-replica index into a three-node and a two-node half: counting the indexing operations that are accepted in the minority half while the majority requirement is off and lost on repair, measuring that the same query returns a different document set and different top five in each half, comparing the cost of the minority rejecting writes and answering queries short — under the majority requirement on — in write messages and missing documents, and comparing the post-repair index with the index that would exist had the split never happened.

The previous lesson assumed replicas carry the same documents, and measured on that
assumption that a replica brings back a lost set. The assumption holds only as long as
replicas can see each other. When the network splits in two, a five-replica index turns into
two separate indexes: each half keeps growing its own inverted index, the two halves'
posting lists diverge, and the same query starts returning two different orders. This is
called **split brain**. The same phenomenon was measured in the leader election narrative
under the name **two-leader round**; the election mechanics and automatic failover were
built there and are not repeated here. The question here is on the search side: what is left
of an indexing operation accepted in the minority, and which documents a query fails to
return while the split lasts.

## Setup

The index has five replicas, and the network splits into a three-node A half and a two-node
B half. While the split lasts, 600 new records arrive at the catalog — a single-topic
donation batch, meaning documents that fall squarely inside the query. How many replicas
must approve a write for it to be accepted is a setting: with the **majority requirement
off**, one approval is enough; **on**, three approvals — a majority of five replicas — are
required.

The baseline is the response the 4600-document index would give to the same query had the
split never happened. The cluster is again modeled in process here: the halves are separate
inverted indexes in the same process, and a routing rule stands in for the network.

**CO5 — of the 600 records arriving during the split, 65 percent reach the three-node half
and 35 percent reach the two-node half.** Rationale: if clients are distributed across
nodes, the split divides them by node count. The effect is linear. **CO6 — once the split is
repaired, the majority half's index is taken as canonical.** One side has to win; whichever
side wins, the writes the other side accepted are lost.

```js
// cluster/corpus.mjs — library catalog corpus and inverted index (same generator and seed as the
// earlier lessons; this lesson carries only the parts it uses). The index holds a dictionary:
// term -> posting list; a posting here is a document entry (document id + term frequency).
const COMMON = ["book", "author", "work", "text", "chapter", "edition", "page", "language", "volume", "publication"];
const SPECIAL = {
  child: ["tale", "illustrated", "school", "play", "animal", "cartoon"], story: ["short", "narrative", "collection", "diary", "loneliness", "village"],
  novel: ["hero", "borough", "generation", "house", "journey", "letter"], history: ["empire", "document", "archive", "war", "century", "chronicle"],
  travel: ["sea", "road", "map", "city", "harbor", "ship"], poetry: ["verse", "meter", "image", "sound", "silence", "rhyme"],
  essay: ["thought", "critique", "reading", "time", "note", "conversation"], science: ["measurement", "experiment", "theory", "data", "observation", "equation"],
};
const RARE = ["lighthouse", "well", "silk", "tower", "garden", "snow", "island", "grove", "stone", "sycamore", "swallow", "blacksmith", "compass", "amber"];
const TOPIC = Object.keys(SPECIAL);

export function corpus({ count = 4000, seed = 20260731 } = {}) {
  let s = seed % 2147483647;
  const r = () => (s = (s * 48271) % 2147483647) / 2147483647;
  const pick = (a) => a[Math.floor(r() * a.length)], docs = [];
  for (let i = 1; i <= count; i += 1) {
    const topic = pick(TOPIC), sp = SPECIAL[topic], terms = [pick(sp), pick(RARE)];
    if (r() < 0.5) terms.push(pick(COMMON));
    for (let j = 0, n = 10 + Math.floor(r() * 7); j < n; j += 1)
      terms.push(r() < 0.45 ? pick(COMMON) : r() < 0.85 ? pick(sp) : pick(RARE));
    docs.push({ id: i, topic, year: 1990 + Math.floor(r() * 36), text: [terms[0], terms[1], topic, ...terms.slice(2)].join(" ") });
  }
  return docs;
}

export function buildIndex(docs) {
  const postings = new Map(), lengths = new Map();
  let bytes = 0;
  for (const d of docs) {
    const t = d.text.split(" "), counts = new Map();
    for (const x of t) counts.set(x, (counts.get(x) ?? 0) + 1);
    lengths.set(d.id, t.length);
    for (const [x, n] of counts) {
      if (!postings.has(x)) { postings.set(x, []); bytes += x.length + 4; }
      postings.get(x).push([d.id, n]); bytes += 8;                        // id + frequency
    }
  }
  const avg = [...lengths.values()].reduce((a, b) => a + b, 0) / (docs.length || 1);
  return { postings, lengths, N: docs.length, avg, bytes };
}

// Scoring: term frequency, inverse document frequency, and document length; statistics are read
// from this index.
export function search(ix, terms, k) {
  const N = ix.N, avg = ix.avg, scores = new Map();
  let scanned = 0;
  for (const t of terms) {
    const g = ix.postings.get(t) ?? [], df = g.length;
    const idf = Math.log(1 + (N - df + 0.5) / (df + 0.5));
    for (const [id, tf] of g) {
      scanned += 1;
      const norm = tf + 1.2 * (0.25 + 0.75 * ix.lengths.get(id) / avg);
      scores.set(id, (scores.get(id) ?? 0) + idf * tf * 2.2 / norm);
    }
  }
  const sorted = [...scores].sort((a, b) => b[1] - a[1] || a[0] - b[0]).slice(0, k);
  return { candidates: sorted.map(([id, p]) => ({ id, p })), scanned, matched: scores.size };
}
```

```js
// cluster/split.mjs — a five-replica index split into a three-node and a two-node half. The
// cluster is modeled IN-PROCESS: the halves are separate inverted indexes in the same process,
// and a routing rule stands in for the network. The baseline is the top ten result the index
// would return had the split never happened.
import { corpus, buildIndex, search } from "./corpus.mjs";

const N0 = 4000, NEW = 600, REPLICAS = 5, A_NODES = 3, B_NODES = 2, K = 10;
const QUERY = ["short", "story", "loneliness"];
const pad = (x, n) => String(x).padStart(n);

const base = corpus({ count: N0 });
// The batch cataloged during the split: a single-topic donation. Generated with a separate
// seed, ids moved past N0; its content is left untouched.
const batch = corpus({ count: 9000, seed: 20260801 }).filter((d) => d.topic === "story")
  .slice(0, NEW).map((d, i) => ({ ...d, id: N0 + i + 1 }));
const aNew = batch.filter((d) => d.id % 20 < 13);   // 65% of clients reach the three-node half
const bNew = batch.filter((d) => d.id % 20 >= 13);  // 35% reach the two-node half
const baseline = buildIndex([...base, ...batch]), baseResult = search(baseline, QUERY, K);
const baseTop = baseResult.candidates.map((x) => x.id), target = baseResult.matched;

const look = (docs) => {                        // the set and order one index returns for this query
  const ix = buildIndex(docs), r = search(ix, QUERY, K);
  const top = r.candidates.map((x) => x.id);
  return { count: docs.length, matched: r.matched, top, shared: top.filter((x) => baseTop.includes(x)).length };
};

console.log(`${N0} documents in the index, ${NEW} new records arrive during the split. ${REPLICAS} replicas,`);
console.log(`halves ${A_NODES} and ${B_NODES} nodes. Seed 20260731. Baseline: the ${N0 + NEW}-document index had the split`);
console.log(`never happened, query "short story loneliness", matched ${target} documents.\n`);

console.log("majority | W | A accepted | B accepted | B rejected | lost on repair | write messages | post-repair documents");
console.log("---------|---|------------|------------|------------|-----------------|----------------|----------------------");
const result = {};
for (const majority of [false, true]) {
  const W = majority ? Math.floor(REPLICAS / 2) + 1 : 1;
  const bAccepted = majority && B_NODES < W ? 0 : bNew.length;
  const bRejected = bNew.length - bAccepted;
  const lost = majority ? 0 : bAccepted;                 // on repair the majority half's index is canonical
  const messages = aNew.length * Math.min(W, A_NODES) + bAccepted * Math.min(W, B_NODES) + bRejected * B_NODES;
  const after = base.length + aNew.length + (majority ? bRejected : 0);   // rejected writes are resubmitted
  result[majority] = { W, bAccepted, after };
  console.log(`${(majority ? "on" : "off").padEnd(8)} | ${pad(W, 1)} | ${pad(aNew.length, 10)} | ${pad(bAccepted, 10)} | ` +
    `${pad(bRejected, 10)} | ${pad(lost, 15)} | ${pad(messages, 14)} | ${pad(after, 22)}`);
}

console.log("\nsame query while the split lasts (baseline: the top 10 that would return had the split never happened):");
console.log("majority | half | nodes | documents in index | matched | missing | top 10 shared | top 5 result");
for (const majority of [false, true]) {
  for (const [name, nodes, add] of [["A", A_NODES, aNew], ["B", B_NODES, result[majority].bAccepted ? bNew : []]]) {
    const r = look([...base, ...add]);
    console.log(`${(majority ? "on" : "off").padEnd(8)} | ${name.padEnd(4)} | ${pad(nodes, 5)} | ${pad(r.count, 19)} | ` +
      `${pad(r.matched, 7)} | ${pad(target - r.matched, 7)} | ${pad(r.shared + "/10", 14)} | ${r.top.slice(0, 5).join(" ")}`);
  }
}

console.log("\nafter repair:");
console.log("majority | documents in index | matched | top 10 shared | top 5 result");
for (const majority of [false, true]) {
  const add = majority ? [...aNew, ...bNew] : aNew;
  const r = look([...base, ...add]);
  console.log(`${(majority ? "on" : "off").padEnd(8)} | ${pad(r.count, 19)} | ${pad(r.matched, 7)} | ` +
    `${pad(r.shared + "/10", 14)} | ${r.top.slice(0, 5).join(" ")}`);
}
console.log(`baseline | ${pad(baseline.N, 19)} | ${pad(target, 7)} | ${pad("10/10", 14)} | ${baseTop.slice(0, 5).join(" ")}`);
console.log(`\nrun-independent: at ${REPLICAS} replicas the majority is ${Math.floor(REPLICAS / 2) + 1}, and two disjoint halves` +
  ` cannot both hold a majority at once, because ${Math.floor(REPLICAS / 2) + 1} + ${Math.floor(REPLICAS / 2) + 1} > ${REPLICAS}.`);
```

```
4000 documents in the index, 600 new records arrive during the split. 5 replicas,
halves 3 and 2 nodes. Seed 20260731. Baseline: the 4600-document index had the split
never happened, query "short story loneliness", matched 1115 documents.

majority | W | A accepted | B accepted | B rejected | lost on repair | write messages | post-repair documents
---------|---|------------|------------|------------|-----------------|----------------|----------------------
off      | 1 |        390 |        210 |          0 |             210 |            600 |                   4390
on       | 3 |        390 |          0 |        210 |               0 |           1590 |                   4600

same query while the split lasts (baseline: the top 10 that would return had the split never happened):
majority | half | nodes | documents in index | matched | missing | top 10 shared | top 5 result
off      | A    |     3 |                4390 |     905 |     210 |           8/10 | 4544 3159 3544 2689 2362
off      | B    |     2 |                4210 |     725 |     390 |           8/10 | 4457 4534 3159 3544 2689
on       | A    |     3 |                4390 |     905 |     210 |           8/10 | 4544 3159 3544 2689 2362
on       | B    |     2 |                4000 |     515 |     600 |           6/10 | 3159 3544 2689 2362 3370

after repair:
majority | documents in index | matched | top 10 shared | top 5 result
off      |                4390 |     905 |           8/10 | 4544 3159 3544 2689 2362
on       |                4600 |    1115 |          10/10 | 4457 4534 4544 3159 3544
baseline |                4600 |    1115 |          10/10 | 4457 4534 4544 3159 3544

run-independent: at 5 replicas the majority is 3, and two disjoint halves cannot both hold a majority at once, because 3 + 3 > 5.
```

## Writes Accepted in the Minority

The first table shows the write side of the two settings. With the majority requirement
off, both halves accept writes: A takes 390, B takes 210. From the librarian's view, all 600
of these records were cataloged successfully — each one received an acknowledgment. On
repair, CO6 takes effect and the **210 records the minority half accepted are lost**. These
records did not return an error, are not waiting in a queue, and are not on a list to be
resubmitted; they were acknowledged and then ceased to exist.

With the majority requirement on, the same 210 requests are rejected from the start. The
difference is where the loss falls: a rejected request stays in the client's hands and can
be resubmitted once the split is repaired. The lost column reads 0, and the post-repair
index holds 4600 documents. Both settings lived through the same network fault; one
swallowed 210 records silently, the other rejected them 210 times, visibly.

The cost is in the write-message column: from 600 messages to 1590. The majority
requirement asks for three approvals for every accepted write, and even the rejected
requests fail only after touching two nodes in the minority half. That is roughly a
2.65-fold increase in messages per write, and it feeds straight into latency.

The run-independent number on the last line says why this setting works at all: at five
replicas the majority is three, and two disjoint halves cannot both hold a majority at once,
because 3 + 3 is greater than five. This is not a setting; it is arithmetic.

## The Query While the Split Lasts

The second table counts what the same query returns while the split lasts. Had the split
never happened, 1115 documents would have matched.

With the majority requirement off, both halves answer, and **both fall short**: A returns
905 documents (210 short), B returns 725 (390 short). Their top five orders diverge too.
Half A opens with 4544; half B opens with 4457 and 4534. All three of these records come
from the donation batch, and each exists only in its own half. Two librarians asking the
same catalog question from two different ends, at the same time, get two contradicting
lists. This is the search-side counterpart of split brain: not a wrong answer, but **two
separate right ones**.

With the majority requirement on, half B's index freezes at 4000 documents: 515 matches, 600
missing documents, and only 6 documents shared with the baseline's top ten. The minority
half keeps answering, but it answers from a **stale index**. This setting does not
guarantee a complete returned set; it guarantees that the minority does not carry its index
forward.

## After Repair

The third table compares the final state with the baseline. With the majority requirement
off, the index stays at 4390 documents: 905 matches, 8/10 in the top ten, and the baseline's
first two records (4457, 4534) missing entirely from the top five. These two records do not
come back; the only way to reindex them is to return to the donation batch's source and
recatalog the 210 records by hand.

With the majority requirement on, the post-repair index holds 4600 documents, 1115 matches,
and a top ten identical to the baseline's. Because the 210 rejected requests are
resubmitted, the result looks as if the split never happened. The majority requirement did
not prevent the fault — the network still split, and the minority half answered short for
all 600 records. What it prevented was the fault becoming **permanent**.

## Summary

- With the majority requirement off, both halves accepted writes (390 and 210) and on repair
  the 210 records the minority accepted were lost; these are records the client had already
  been acknowledged for.
- With the majority requirement on, the same 210 requests were rejected, the lost count was
  0, and resubmitting them after repair brought the index to 4600 documents.
- The majority requirement's cost is write messages: from 600 to 1590, roughly a 2.65-fold
  increase per write.
- While the split lasted, with the majority requirement off, half A returned 905 documents
  and half B 725, and their top five lists diverged: A opened with 4544, B with 4457. The
  same question got two contradicting answers.
- With the majority requirement on, the minority half returned 515 matches from its
  4000-document stale index: 600 missing documents and 6/10 in the top ten. The guarantee is
  not a complete answer but that the minority does not advance its index.
- After repair, the majority-off setting stayed at 905 matches and 8/10; the majority-on
  setting produced a result as if the split never happened — 1115 matches and 10/10.

## Next Step

This lesson counted the 600 records one by one, as if each were a separate request and
became searchable the moment it was accepted. Neither assumption was measured. A catalog
batch actually arrives in bulk, not one record at a time, and sending each record as its own
request is not the same as sending all of them in one request: request count, the number of
segments produced, and total time all change. A document entering the index does not become
searchable instantly either; it is first written to a buffer and becomes visible to queries
only once a **refresh** operation runs. The next lesson indexes the same 4000-document
corpus one record at a time and in bulk, compares request count against segment count, then
varies the refresh interval and counts the trade-off between visibility lag and write
throughput.