Skip to content
wannacode

Trade-offs

In short: The CAP theorem says that when the link between nodes breaks, a system chooses between consistency (CP, it refuses) and availability (AP, it accepts and reconciles later).

Problem

The last coffee machine and two buyers

The shop now has two warehouses, in Sofia and in Varna. Each keeps its own copy of the stock: the pages answer fast, and one warehouse keeps working when the other one is slow. One coffee machine for 349 € is left.

On Friday evening the link between the two warehouses goes down for ten minutes. In those minutes Maria orders the machine and her order reaches Varna. Ivan orders the same machine and his reaches Sofia.

What should the shop do? Whatever you choose, somebody loses. Either both are refused while the machine sits on the shelf. Or both pay for one machine. There is no third option, and that is what this lesson is about.

The idea

CAP in practice

When the network splits the system into parts (a partition, P), each part answers on its own. Then it chooses one of two:

  • consistency (C): every answer is the latest truth. If the part cannot be sure, it refuses;
  • availability (A): every request gets an answer, even from a copy that may be old.

You do not choose a partition: networks fail, whether it is the network between two warehouses or between two zones in the cloud. The only choice is what you do when it happens. This is the trade-off between consistency and availability, known as the CAP theorem. You saw it from the side of databases in the lesson "Replication, sharding and CAP". Here it is from the side of the shop: who loses and how much.

In the programs a warehouse is an object, the link is a flag linkUp, and time is a tick. That way the two choices run side by side, without a network.

class Warehouse(string name, int stock)
{
    public string Name { get; } = name;
    public int Stock { get; set; } = stock;
    public List<Sale> Sales { get; } = [];
}


record Sale(string Buyer, int Tick);

See it

CP: better a refusal than a lie

A CP warehouse sells only if the other one confirms too. Without the link it cannot check, so it refuses:

// CP: sells only if the other warehouse confirms
static string SellCP(Warehouse here, Warehouse other,
                     bool linkUp, string buyer)
{
    if (!linkUp)
        return $"{buyer}: refused, {here.Name}"
            + $" cannot see {other.Name}";
    if (here.Stock == 0) return buyer + ": sold out";
    here.Stock--;
    other.Stock--;
    return buyer + ": sold";
}
var sofia = new Warehouse("Sofia", 1);
var varna = new Warehouse("Varna", 1);
bool linkUp = false; // the link is down
Console.WriteLine(SellCP(varna, sofia, linkUp, "Maria"));
Console.WriteLine(SellCP(sofia, varna, linkUp, "Ivan"));
linkUp = true; // the link is back
Console.WriteLine(SellCP(varna, sofia, linkUp, "Maria"));
Console.WriteLine($"in stock: {sofia.Name} {sofia.Stock}, {varna.Name} {varna.Stock}");
Output
Maria: refused, Varna cannot see Sofia
Ivan: refused, Sofia cannot see Varna
Maria: sold
in stock: Sofia 0, Varna 0

While the link is down, nobody buys. As soon as it is back, Maria buys and both warehouses say 0. The data is right all the time. The price is in the other quality: in those ten minutes the shop sells nothing and customers see an error.

See it

AP: sell now, reconcile later

An AP warehouse sells from its own copy and records the sale. When the link is back, reconciliation gathers the sales of both warehouses, orders them by time and hands out the real items:

// AP: sells from its own copy without asking
static string SellAP(Warehouse here, string buyer,
                     int tick)
{
    if (here.Stock == 0) return buyer + ": sold out";
    here.Stock--;
    here.Sales.Add(new Sale(buyer, tick));
    return $"{buyer}: sold ({here.Name})";
}


// reconciliation: the sales of both, in time order
static void Reconcile(int real, Warehouse a, Warehouse b)
{
    var all = a.Sales.Concat(b.Sales).OrderBy(s => s.Tick);
    foreach (var s in all)
    {
        bool ok = real > 0;
        if (ok) real--;
        string result = ok ? "confirmed" : "20 € voucher";
        Console.WriteLine(
            $"{s.Buyer} (tick {s.Tick}): {result}");
    }
    a.Stock = real;
    b.Stock = real;
}
var sofia = new Warehouse("Sofia", 1);
var varna = new Warehouse("Varna", 1);
// the link is down: each warehouse sells from its own copy
Console.WriteLine(SellAP(varna, "Maria", 3));
Console.WriteLine(SellAP(sofia, "Ivan", 5));
// the link is back
Reconcile(1, sofia, varna);
Console.WriteLine("in stock: " + sofia.Stock);
Output
Maria: sold (Varna)
Ivan: sold (Sofia)
Maria (tick 3): confirmed
Ivan (tick 5): 20 € voucher
in stock: 0

Both hear "sold". Later it turns out there is one machine. Maria came first and gets it. Ivan gets an apology and a 20 € voucher. AP pays with a compensation and with code for reconciling.

The two copies differed for ten minutes and met again as soon as the link was back. This is eventual consistency: the copies may differ for a while, but when new changes stop, they arrive at the same state. The promise is that they meet, not when.

See it

The two choices one under the other

// AP: sells from its own copy without asking
static string SellAP(Warehouse here, string buyer,
                     int tick)
{
    if (here.Stock == 0) return buyer + ": sold out";
    here.Stock--;
    here.Sales.Add(new Sale(buyer, tick));
    return $"{buyer}: sold ({here.Name})";
}


// reconciliation: the sales of both, in time order
static void Reconcile(int real, Warehouse a, Warehouse b)
{
    var all = a.Sales.Concat(b.Sales).OrderBy(s => s.Tick);
    foreach (var s in all)
    {
        bool ok = real > 0;
        if (ok) real--;
        string result = ok ? "confirmed" : "20 € voucher";
        Console.WriteLine(
            $"{s.Buyer} (tick {s.Tick}): {result}");
    }
    a.Stock = real;
    b.Stock = real;
}
Step by step, in words
  1. The last coffee machine for 349 €. Two warehouses each keep a copy of the stock: 1 and 1. Two shops side by side: the top one chooses CP, the bottom one AP.
  2. The link between Sofia and Varna goes down. Maria is in Varna, Ivan in Sofia. Each warehouse must decide on its own.
  3. CP sells only if the other warehouse confirms. There is no link, so both are refused. The data stays right, but the shop sells nothing.
  4. AP sells from its own copy. Maria buys on tick 3, Ivan on tick 5. Both copies say 0, yet two were sold of one.
  5. The link is back. Reconciliation gathers the sales, not the numbers, and orders them by time.
  6. Maria came first and gets the machine. Ivan gets an apology and a 20 € voucher. CP paid with lost sales, AP with a compensation.

The top shop is CP, the bottom one is AP. The same partition, the same buyers. At the top the shop loses (sales); at the bottom one customer loses (the item), and the shop pays with a voucher and support time.

Try it

Predict the output

There are two items. The link is down and the warehouses sell AP: Ivan in Sofia on tick 1, Maria in Varna on tick 4, Elena in Sofia on tick 2. What does reconciliation print?

var sofia = new Warehouse("Sofia", 2);
var varna = new Warehouse("Varna", 2);
SellAP(sofia, "Ivan", 1);
SellAP(varna, "Maria", 4);
SellAP(sofia, "Elena", 2);
Reconcile(2, sofia, varna);
Answer

Try it

Fill in

What are the sales ordered by during reconciliation?

var all = a.Sales.Concat(b.Sales).OrderBy(s => s.);

Try it

Find the bug

A colleague writes a shorter reconciliation: each warehouse takes the smaller of the two numbers. After the partition both warehouses say 0, nobody gets a voucher, and Ivan waits for a machine that does not exist. Which line has the bug?

Pick the line with the bug.

The idea

Every quality is paid for in another quality

CAP is the best-known trade-off, but not the only one. Architecture is the choice of which quality pays for which:

  • consistency against availability during a partition, as you saw;
  • consistency against latency even without a partition: the confirmation from the other warehouse is one more trip over the network for every sale;
  • availability against correctness: AP needs compensations, a reconciliation process and people in support;
  • security against speed and convenience: one more check is more time, one more step at login;
  • scale against simplicity: two warehouses with copies are more complex than one database.

The choice is not one for the whole shop but one for each kind of data. The cart is good for AP: if you lose an item, the customer adds it again, and the cart is always there. The last items, the payment and the accounts are for CP: a sold item that does not exist or a double payment cost money and trust. The catalogue with its descriptions tolerates data that is minutes old.

The business decides, and the architect gives it the price of each option in numbers: how many minutes without sales a year with CP, how many vouchers with AP. The decision and its consequences go into an ADR.

The idea

When it hurts

  • Eventual consistency when users do not see their own action. The customer pays, the page reads from a copy that does not know yet and says "you have no orders". They pay again. You saw the same with replicas in the lesson on scaling. Where a person reads what they just wrote, read from where it was written.
  • When there is no compensation. Money already taken twice, a medicine with a limited count, a ticket for a seat on a plane. Here AP is not a choice but a mistake.
  • Reconciliation more complex than its benefit. If a partition happens once a year for a minute, a refusal is cheaper than reconciliation code that somebody has to understand.
  • Distributed data when you do not need it. One database with transactions does not ask this question at all (the lesson on transactions). A copy in another warehouse or another country is made when an NFR asks for it with a number.
More precisely, if you are curious

CAP more precisely. The theorem (Brewer, proved by Gilbert and Lynch) talks about one value, many copies and a partition. "Pick 2 of 3" misleads: P is not a choice. Put more precisely: during a partition you choose C or A. PACELC adds the second half: Else, you choose between Latency and Consistency.

Time. Here everybody sees the same tick counter. The clocks of real machines drift apart, so "who was first" is decided with logical clocks: Lamport clocks, vector clocks, hybrid logical clocks. Google's Spanner uses clocks with atomic references and GPS and waits until the uncertainty has passed.

CRDTs (conflict-free replicated data types) are structures that always merge into the same result without coordination: counters, sets, lists. Amazon's cart in the Dynamo paper is an example of AP where adding never loses items.

Quorums. With N copies, writing to W and reading from R, if W + R > N a read always sees the latest write. You met them in the lesson on replication. Cassandra and DynamoDB let you choose the consistency level for each request.

Several services. The reconciliation here is for one item in two warehouses. When one business operation goes through several services and, on failure, must be undone step by step, it becomes a pattern with its own name. It comes later in this module.

OrderBy is a stable sort from LINQ and returns a new sequence; the warehouses' lists are not changed.

Exercise

CP for the last items, AP for the rest

Solve the task in your own editor.

The two warehouses sell coffee machines (1 each) and coffee filters (500 each). Write Sell, which sells coffee machines only with a confirmation from the other warehouse (CP), and filters from its own copy (AP). The link is down. Maria in Varna wants a machine and filters, Ivan in Sofia wants filters.

Output
Maria, coffee machine: refused, Varna cannot see Sofia
Maria, filters: sold (Varna)
Ivan, filters: sold (Sofia)

More tasks

  • A threshold. Instead of a list of "important" products, use a threshold: AP while the copy has more than 3 items, CP for the last 3. What happens if both warehouses sell 3 each during the partition?
  • The cart. The cart has two copies. In one the customer added cups, in the other they removed the filters. Write a reconciliation of the operations "add" and "remove", ordered by tick.

Test

Check yourself

1. The link between the two warehouses is down. What can each warehouse choose?
2. What does "eventual consistency" mean?
3. Why does reconciliation gather the sales and not the stock numbers?
4. Which is sensible for the online shop?
5. When does eventual consistency hurt most?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·