Към съдържанието
wannacode

Компромиси

Накратко: CAP теоремата казва, че при прекъсната връзка между възлите системата избира между съгласуваност (CP, отказва) и наличност (AP, приема и после помирява).

Проблем

Последната кафемашина и двама купувачи

Магазинът вече има два склада, в София и във Варна. Всеки пази свое копие на наличността: страниците отговарят бързо, а единият склад работи и когато другият е бавен. Остава последната кафемашина за 349 €.

В петък вечер връзката между двата склада пада за десет минути. В същите минути Мария поръчва машината и поръчката ѝ стига до Варна. Иван поръчва същата машина и неговата стига до София.

Какво трябва да направи магазинът? Каквото и да избереш, някой губи. Или и двамата получават отказ, докато машината стои на рафта. Или и двамата плащат за една машина. Трети вариант няма, и точно за това е урокът.

Идеята

CAP на практика

Когато мрежата раздели системата на части (partition, P), всяка част отговаря сама. Тогава тя избира едно от двете:

  • съгласуваност (consistency, C): всеки отговор е последната истина. Ако не може да е сигурна, частта отказва;
  • наличност (availability, A): всяка заявка получава отговор, дори от копие, което може да е старо.

Разделяне не избираш: мрежите падат, а това е и мрежата между два склада, и между две зони в облака. Изборът е само какво правиш, когато стане. Това е компромисът между съгласуваност и наличност, известен като теоремата CAP. Видя я от страната на базите в урока „Репликация, шардинг и CAP“. Тук е от страната на магазина: кой губи и колко.

В програмите складът е обект, връзката е флаг linkUp, а времето е тик. Така двата избора се пускат един до друг, без мрежа.

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);

Виж го

CP: по-добре отказ, отколкото лъжа

CP складът продава само ако и другият потвърди. Без връзка не може да провери, затова отказва:

// CP: продава само ако и другият склад потвърди
static string SellCP(Warehouse here, Warehouse other,
                     bool linkUp, string buyer)
{
    if (!linkUp)
        return $"{buyer}: отказ, {here.Name}"
            + $" не вижда {other.Name}";
    if (here.Stock == 0) return buyer + ": изчерпано";
    here.Stock--;
    other.Stock--;
    return buyer + ": продадено";
}
var sofia = new Warehouse("София", 1);
var varna = new Warehouse("Варна", 1);
bool linkUp = false; // връзката е паднала
Console.WriteLine(SellCP(varna, sofia, linkUp, "Мария"));
Console.WriteLine(SellCP(sofia, varna, linkUp, "Иван"));
linkUp = true; // връзката се връща
Console.WriteLine(SellCP(varna, sofia, linkUp, "Мария"));
Console.WriteLine($"наличност: {sofia.Name} {sofia.Stock}, {varna.Name} {varna.Stock}");
Изход
Мария: отказ, Варна не вижда София
Иван: отказ, София не вижда Варна
Мария: продадено
наличност: София 0, Варна 0

Докато връзката я няма, никой не купува. Щом се върне, Мария купува, и двата склада казват 0. Данните са верни през цялото време. Цената е в другото качество: в тези десет минути магазинът не продава, а клиентите виждат грешка.

Виж го

AP: продай сега, помири после

AP складът продава от своето копие и записва продажбата. Когато връзката се върне, помиряването (reconciliation) събира продажбите от двата склада, подрежда ги по време и раздава истинските бройки:

// AP: продава от своето копие, без да пита
static string SellAP(Warehouse here, string buyer,
                     int tick)
{
    if (here.Stock == 0) return buyer + ": изчерпано";
    here.Stock--;
    here.Sales.Add(new Sale(buyer, tick));
    return $"{buyer}: продадено ({here.Name})";
}


// помиряване: продажбите от двата склада, по време
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 ? "потвърдено" : "ваучер 20 €";
        Console.WriteLine(
            $"{s.Buyer} (тик {s.Tick}): {result}");
    }
    a.Stock = real;
    b.Stock = real;
}
var sofia = new Warehouse("София", 1);
var varna = new Warehouse("Варна", 1);
// връзката е паднала: всеки склад продава от своето копие
Console.WriteLine(SellAP(varna, "Мария", 3));
Console.WriteLine(SellAP(sofia, "Иван", 5));
// връзката се връща
Reconcile(1, sofia, varna);
Console.WriteLine("наличност: " + sofia.Stock);
Изход
Мария: продадено (Варна)
Иван: продадено (София)
Мария (тик 3): потвърдено
Иван (тик 5): ваучер 20 €
наличност: 0

Двамата чуват „продадено“. После се оказва, че машината е една. Мария е била първа и я получава. Иван получава извинение и ваучер за 20 €. AP плаща с обезщетение и с код за помиряване.

Двете копия се разминаваха десет минути и се срещнаха, щом връзката се върна. Това е евентуална съгласуваност (eventual consistency): копията може да се различават известно време, но когато спрат новите промени, стигат до едно и също. Обещанието е, че се срещат, а не кога.

Виж го

Двата избора един под друг

// AP: продава от своето копие, без да пита
static string SellAP(Warehouse here, string buyer,
                     int tick)
{
    if (here.Stock == 0) return buyer + ": изчерпано";
    here.Stock--;
    here.Sales.Add(new Sale(buyer, tick));
    return $"{buyer}: продадено ({here.Name})";
}


// помиряване: продажбите от двата склада, по време
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 ? "потвърдено" : "ваучер 20 €";
        Console.WriteLine(
            $"{s.Buyer} (тик {s.Tick}): {result}");
    }
    a.Stock = real;
    b.Stock = real;
}
Стъпка по стъпка, с думи
  1. Последната кафемашина за 349 €. Два склада пазят по копие на наличността: 1 и 1. Два магазина един под друг: горният избира CP, долният AP.
  2. Връзката между София и Варна пада. Мария е във Варна, Иван в София. Всеки склад трябва да реши сам.
  3. CP продава само ако другият склад потвърди. Връзка няма, затова и двамата получават отказ. Данните остават верни, но магазинът не продава.
  4. AP продава от своето копие. Мария купува на тик 3, Иван на тик 5. И двете копия казват 0, а продадени са две от една.
  5. Връзката се връща. Помиряването събира продажбите, а не числата, и ги подрежда по време.
  6. Мария е първа и получава машината. Иван получава извинение и ваучер 20 €. CP плати с изгубени продажби, AP с обезщетение.

Горният магазин е CP, долният е AP. Едно и също разделяне, едни и същи купувачи. Горе губи магазинът (продажби), долу губи един клиент (стоката), а магазинът плаща ваучер и време в поддръжката.

Пробвай

Предвиди изхода

Бройките са две. Връзката е паднала, а складовете продават по AP: Иван в София на тик 1, Мария във Варна на тик 4, Елена в София на тик 2. Какво печата помиряването?

var sofia = new Warehouse("София", 2);
var varna = new Warehouse("Варна", 2);
SellAP(sofia, "Иван", 1);
SellAP(varna, "Мария", 4);
SellAP(sofia, "Елена", 2);
Reconcile(2, sofia, varna);
Отговор

Пробвай

Попълни

По какво се подреждат продажбите при помиряването?

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

Пробвай

Намери грешката

Колегата пише по-кратко помиряване: всеки склад взима по-малкото от двете числа. След разделянето и двата склада казват 0, никой не получава ваучер, а Иван чака машина, която я няма. На кой ред е грешката?

Избери реда с грешката.

Идеята

Цената на всяко качество е в друго качество

CAP е най-известният компромис, но не единственият. Архитектурата е избор кое качество плаща за кое:

  • съгласуваност срещу наличност при разделяне, както видя;
  • съгласуваност срещу закъснение и без разделяне: потвърждението от другия склад е още едно пътуване по мрежата при всяка продажба;
  • наличност срещу коректност: AP иска обезщетения, процес по помиряване и хора в поддръжката;
  • сигурност срещу скорост и удобство: още една проверка е още време, още една стъпка при вход;
  • мащаб срещу простота: два склада с копия са по-сложни от една база.

Изборът не е един за целия магазин, а за всеки вид данни. Количката е добра за AP: ако изгубиш артикул, клиентът го добавя пак, а количката е там винаги. Последните бройки, плащането и сметките са за CP: продадена несъществуваща стока или двойно платена сума струват пари и доверие. Каталогът с описанията търпи стари данни с минути.

Който решава, е бизнесът, а архитектът му дава цената на всеки вариант с числа: колко минути без продажби в годината при CP, колко ваучера при AP. Решението и последиците му отиват в ADR.

Идеята

Кога вреди

  • Евентуална съгласуваност, когато потребителят не вижда своето действие. Клиентът плаща, страницата чете от копие, което още не знае, и казва „нямаш поръчки“. Той плаща пак. Видя същото с репликите в урока за мащабирането. Там, където човекът чете току-що написаното, чети от мястото, където е написано.
  • Когато обезщетение няма. Пари, които вече са изтеглени два пъти, лекарство с ограничен брой, билет за място в самолета. Тук AP не е избор, а грешка.
  • Помиряване, по-сложно от ползата. Ако разделянето се случва веднъж в годината за минута, отказът е по-евтин от код за помиряване, който някой трябва да разбира.
  • Разпределени данни, без да трябват. Една база с транзакции изобщо не задава този въпрос (урокът за транзакциите). Копие в друг склад или друга държава се прави, когато NFR го иска с число.
По-точно, за любопитните

CAP по-точно. Теоремата (Brewer, доказана от Gilbert и Lynch) говори за една стойност, много копия и разделяне. „Избери 2 от 3“ подвежда: P не е избор. Казва се по-точно така: при разделяне избираш C или A. PACELC добавя втората половина: иначе (Else) избираш между закъснение (Latency) и съгласуваност (Consistency).

Времето. Тук всички виждат един и същ брояч на тикове. Часовниците на истинските машини се разминават, затова „кой е първи“ се решава с логически часовници: Lamport, векторни часовници, hybrid logical clocks. Spanner на Google ползва часовници с атомни еталони и GPS и чака, докато несигурността мине.

CRDT (conflict-free replicated data types) са структури, които се сливат винаги в един и същ резултат, без координация: броячи, множества, списъци. Количката на Amazon в статията за Dynamo е пример за AP с добавяне, което не губи артикули.

Кворуми. С N копия, запис в W и четене от R, при W + R > N четенето винаги вижда последния запис. Видя ги в урока за репликацията. Cassandra и DynamoDB дават избор на нивото на съгласуваност за всяка заявка.

Няколко услуги. Помиряването тук е за една стока в два склада. Когато една бизнес операция минава през няколко услуги и при отказ трябва да се върне назад стъпка по стъпка, това става шаблон със свое име. Той идва по-нататък в модула.

OrderBy е стабилно сортиране от LINQ и връща нова последователност; списъците на складовете не се променят.

Упражнение

CP за последните бройки, AP за останалото

Реши задачата в редактора си.

Двата склада продават кафемашини (по 1 бройка) и филтри за кафе (по 500). Напиши Sell, който продава кафемашини само с потвърждение от другия склад (CP), а филтри от своето копие (AP). Връзката е паднала. Мария във Варна иска машина и филтри, Иван в София иска филтри.

Изход
Мария, кафемашина: отказ, Варна не вижда София
Мария, филтри: продадено (Варна)
Иван, филтри: продадено (София)

Още задачи

  • Праг. Вместо списък с „важни“ стоки сложи праг: AP, докато в копието има повече от 3 бройки, CP за последните 3. Какво става, ако и двата склада продадат по 3 по време на разделянето?
  • Количката. Количката е в две копия. В едното клиентът е добавил чаши, в другото е махнал филтрите. Напиши помиряване на операциите „добави“ и „махни“, подредени по тик.

Тест

Провери се

1. Връзката между двата склада е паднала. Какво може да избере всеки склад?
2. Какво значи „евентуална съгласуваност“?
3. Защо помиряването събира продажбите, а не числата на наличността?
4. Кое е разумно за онлайн магазина?
5. Кога евентуалната съгласуваност вреди най-много?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·