AP и CP: пытаемся усидеть на двух стульях и боремся с последствиями

Многие системы, стараясь описать свое поведение в ненадежной сети, прибегают к терминам CAP-теоремы и описывают себя либо как AP, либо как CP.

Алгоритм Raft является классическим примером CP — обеспечивает линеаризуемость в случае разделения сети, но это в определенных случаях приводит к временной потере доступности и на запись, и на чтение до восстановления связности.

Да, на бумаге всё хорошо. Берём нечётное количество узлов и наслаждаемся работоспособностью кластера и консистентностью данных до тех пор, пока большая часть узлов работает. Однако, эта схема использования идёт вразрез с самой популярной схемой установки БД: равное число узлов в двух ЦОД-ах. Для Raft это значит, что потеря одного ЦОД-а сразу приведёт к недоступности кластера на запись.

Отсюда возникает необходимость переключения между надёжностью и доступностью: если пользователь видит, что один из двух ЦОД-ов неработоспособен, он может решить продолжить обслуживать запросы в живом ЦОД-е без участия второго ЦОД-а, то есть превратить CP-систему в AP. Мы дали пользователю такую возможность в реализации Raft в Tarantool и столкнулись с условиями потери консистентности данных, с которыми бы никогда не встретился канонический Raft.

Такой режим работы не дает гарантий Raft, поскольку человеческая ошибка может привести к тому, что этот режим будет включен в двух ЦОД-ах одновременно. Это уже приведет к возникновению двух противоречащих друг другу версий наборов данных. Значит, разрешая такое понижение надежности, мы должны научиться обнаруживать различия в наборах данных и предупреждать пользователя об этих различиях, не давая репликации соединить два противоречащих набора.

Нам удалось сделать это благодаря маркерам лидерства в журнале. Во время нормальной работы маркеры лидерства выстраиваются в согласованную цепочку, позволяя проследить историю смены лидеров до самого начала журнала.

Если же во время разделения сети человеческая ошибка приводит к возникновению двух независимых наборов данных, маркеры лидерства в двух наборах, начиная с какого-то общего предка, составляют две разделившиеся цепочки.

Если мы умеем находить расхождения в цепочках маркеров лидерства, мы умеем находить противоречащие участки журналов. Это позволяет отклонять репликацию конфликтующего набора данных и эскалировать проблему до пользователя.

В этом докладе поговорим о методах, которые мы применили, чтобы обнаруживать такие расхождения и обеспечивать консистентность данных после периода работы в разделенной сети.