CAP Theorem and
Why You Can't Have It All

1 · Written problem

Your shortener runs in two regions, East and West. A network partition cuts them off from each other for ten minutes. During that time the service also counts clicks on every short link, and it lets people create custom aliases that must belong to exactly one owner. (This is an imagined scenario made for the exercise, not a real incident.)

1. For the click counter, should each region keep counting during the partition, or refuse to count until the connection is back? Pick one and explain briefly.
2. For custom alias creation, should each region keep accepting new aliases during the partition? Pick one and say what could go wrong with the other choice.
3. Now imagine there is no partition. A developer suggests waiting for both regions to confirm every alias creation before replying to the user. Using PACELC, explain what this gives you and what it costs.

2 · Coding exercise - refuse or answer stale

~20–30 minutes · JavaScript

You will build a tiny alias store that runs in two regions, "east" and "west". It can run in two modes:

• CP mode: while the regions are cut off from each other, West refuses to create or look up aliases and throws Unavailable. East keeps working. When the connection is back, West catches up to East.
• AP mode: while the regions are cut off, both keep answering from their own table, even though the data may be out of date. When the connection is back, the two tables are merged. If the same alias points to different URLs on the two sides, the one created later wins, and heal() returns the list of aliases that conflicted.

Fill in the Cluster class below. Four tests run against your implementation. You can't see or edit the tests themselves, but their names tell you what they check.

class Unavailable extends Error {
  constructor(message) { super(message); this.name = "Unavailable"; }
}

class Cluster {
  constructor(mode) {
    this.mode = mode;
    this.partitioned = false;
    this.data = { east: new Map(), west: new Map() }; // alias -> { url, seq }
    this.seq = 0;
  }

  partition() {
    this.partitioned = true;
  }

  check(region) {
    // only CP mode refuses, and only on the west side
    if (this.mode === "CP" && this.partitioned && region === "west") {
      throw new Unavailable(region);
    }
  }

  create(region, alias, url) {
    this.check(region);
    if (this.data[region].has(alias)) return false;
    const entry = { url, seq: ++this.seq };
    this.data[region].set(alias, entry);
    if (!this.partitioned) {
      const other = region === "east" ? "west" : "east";
      this.data[other].set(alias, entry); // copied straight away
    }
    return true;
  }

  resolve(region, alias) {
    this.check(region);
    const entry = this.data[region].get(alias);
    return entry ? entry.url : undefined;
  }

  heal() {
    this.partitioned = false;
    const { east, west } = this.data;
    const conflicts = [];
    const aliases = [...new Set([...east.keys(), ...west.keys()])].sort();
    for (const alias of aliases) {
      const a = east.get(alias), b = west.get(alias);
      if (a && b && a.url !== b.url) conflicts.push(alias);
      const winner = !a ? b : !b ? a : a.seq > b.seq ? a : b; // later create wins
      east.set(alias, winner);
      west.set(alias, winner);
    }
    return conflicts;
  }
}

3 · Quiz

1. In the CAP theorem, what does the word “consistency” mean?
   1. The database checks its rules, such as foreign keys and constraints
   2. Every read sees the most recent completed write, as if there were only one copy of the data
   3. The system is up and running most of the time
   4. The copies of the data will agree with each other eventually
   Answer

   B.In CAP, consistency means every read sees the latest write. It is not the “C” from ACID, and it is not the same as copies agreeing “eventually”.

2. Why is “pick any two of C, A and P” misleading?
   1. Consistency and availability can never exist together
   2. Partition tolerance is always optional
   3. You can't choose whether partitions happen on a real network, so the real choice is between C and A while one is happening
   4. Only two of the three exist in real systems
   Answer

   C.Partitions happen to you. So the decision is what to give up while one is happening. When there is no partition, you can have both.

3. During a partition, a region refuses to create custom aliases because it can't check with the other region. Which property is it giving up?
   1. Consistency
   2. Partition tolerance
   3. Availability
   4. Durability
   Answer

   C.It returns an error to keep each alias owned by just one person. That protects consistency and gives up availability.

4. What does PACELC add that CAP alone doesn't cover?
   1. It proves that CAP is wrong
   2. It describes what happens when there is no partition: a trade-off between speed (latency) and consistency
   3. It adds a fourth letter for security
   4. It only applies to relational databases
   Answer

   B.The “else” half of PACELC covers normal days, when waiting for other copies to confirm makes every request slower.

5. The shortener keeps answering redirects (possibly with old data) but refuses to create aliases during a partition. What does that show?
   1. The system is broken
   2. Redirects don't need a network
   3. CAP doesn't apply to link shorteners
   4. The choice between C and A can be made for each operation, not once for the whole system
   Answer

   D.Eric Brewer made this point in 2012: the choice can be different for each kind of operation, each kind of data, or even each user.

Verify answers