Алгоритм реплицированного регистра, известный в литературе как ABD, в самой лекции по имени не называется — на доске он записан как Atomic Register, и здесь сохранены формулировки лектора.
Зачем нужен регистр: слои хранилища и абстракция
Сначала немного меты про устройство курса. Возможно, вы помните, как проходил весенний курс: были лекции, и периодически в них всплывали совершенно разные неожиданные темы — я говорил про потоки, а потом внезапно про модели памяти, а потом внезапно про планировщики. В этот раз будет иначе: у нас есть магистральная сюжетная линия, и мы будем развивать её постепенно. Поэтому каждый раз я буду начинать с того, что напомню, чего мы к этому моменту достигли и что накопили.
Накопили мы пока очень немного — мы построили модель, в которой будем решать наши задачи. Напомню, мы решили, что работаем в асинхронной модели, где не делаем предположений ни о том, насколько быстро доставляются сообщения, ни о том, насколько быстро работают узлы, ни о том, насколько сильно могут дрейфовать часы на разных узлах. И мы договорились, что значительную часть курса — первые две трети — будем жить в модели, где узлы отказывают, просто выключаясь навсегда или же рестартуя. Мы не предполагаем, что космическая частица упадёт в планку памяти, перевернёт там битик, этот битик окажется в адресе, принадлежащем таблице страниц, и каскадный эффект что-нибудь нам взорвёт. То есть узлы ведут себя в рамках протокола, в планках есть коррекция ошибок, византийских отказов у нас пока тоже нет, и злоумышленников нет.
И сегодня мы наконец добрались до какой-то задачи. В прошлый раз я сказал, что мы будем решать задачи, мотивированные реальностью, какими-то промышленными системами, — и сегодня мы такую систему выберем. Это будет key-value хранилище. Мы хотим в нашем асинхронном мире построить распределённую систему, которая умеет выполнять две операции: — записать значение по ключу — и — прочитать по ключу. Природа ключей и значений нам не важна: будем считать, что это просто строчки, а если нужен какой-то тип, мы его закодируем, сериализуем в строчку. На самом деле для полезной системы этого, конечно, недостаточно: скорее всего, мы хотим ещё читать диапазоны, наверное, хотим транзакции или какие-то более сложные операции. К этому мы постепенно придём, но не сегодня.
Прежде чем говорить именно про эту задачу, нужно мотивировать, почему мы начинаем именно с такого класса систем. Сначала причина историческая. Если посмотреть, как системы развивались — а это случалось в начале 2000-х годов, — то сначала компания Google написала статью про MapReduce и про распределённую файловую систему (про файловые системы поговорим чуть позже), а в 2005, 2006 и 2007 годах вышли статьи про Google Bigtable и Amazon Dynamo. Это были как раз две key-value системы, написанные соответственно в Google и в Amazon; они реализовывали интерфейс key-value хранилища. Почему именно key-value? Ответ довольно странный: потому что ничего лучше сделать не получалось.
Бизнесу, конечно же, нужны базы данных, таблицы, колонки, транзакции, декларативный язык запросов. Другое дело, что если вы находитесь в начале 2000-х, то сделать это очень сложно. База данных у вас, конечно, есть, а распределённых баз данных нет. Вы пытаетесь научить ваши системы масштабироваться и быть отказоустойчивыми, у вас это не получается — задача трудная, — и вы начинаете постепенно выбрасывать из них фичи: таблицы, транзакции, запросы. И у вас остаётся такая hash-таблица — точнее, не hash-таблица, а отображение. Вот его-то вы уже научились делать.
Но непонятно, почему мы в 2021 году говорим, что мы ничего не умеем, хотя люди к этому моменту уже научились: в прошлый раз я упоминал Google Spanner. Ответ такой. Если посмотреть на современные базы данных, то окажется, что да, они дают пользователю табличную модель, декларативный язык запросов, транзакции — всё, чего мы ожидаем, — но под капотом они реализованы поверх key-value хранилищ. То есть можно выделить слой, условно , и он опирается на слой . Мы умеем закодировать табличную модель в ключах key-value хранилища: пользователь видит таблицы и работает с декларативным языком запросов, а вся распределённость и отказоустойчивость находятся вот на этом нижнем слое. В частности, так устроен Spanner, да и другие open source клоны Spanner.
Но и сам по себе key-value — очень сложная задача, в ней тоже много архитектурных слоёв. Вот вы хотите сделать key-value хранилище: оно должно масштабироваться и быть отказоустойчивым. Но задачу вы начинаете решать на совсем другом уровне — на уровне одной машины. У вас есть всего одна машина, и вы должны хранить на ней ключи и значения, пусть они там помещаются. В чём сложность? В том, что машина должна переживать рестарты, а значит, хранить ключи не в памяти, а на жёстком диске.
Про жёсткие диски мы подробно поговорим на одном из семинаров — как они устроены, какие у них гарантии и свойства. Но вы, наверное, понимаете, что это довольно механическое устройство, где блины вращаются с большой скоростью — большой, но не слишком, чтобы всё это не взорвалось. Отсюда проблема: API, которое вы хотите реализовать, — это API с произвольным доступом, у вас есть произвольные ключи, по которым вы пишете или читаете. А диск так не умеет: эффективно он умеет читать и писать только последовательно. Поэтому первая задача, которая возникает уже в пределах одной машины, — это слой : на самом низком уровне, в пределах одного узла, построить эффективную систему с произвольным доступом поверх диска, который эффективен только на последовательном доступе. Это системы типа LevelDB и RocksDB; про них мы тоже поговорим, но не на лекции.
В пределах одного узла задачу вы решили. Что вы хотите сделать дальше? Наверное, добавить отказоустойчивости: машина перезагрузится и данные не потеряет, но она может просто разломаться, у неё может умереть диск. Поэтому вы начинаете данные реплицировать — это слой . На этом уровне у вас по-прежнему все данные вмещаются в одну машину, но вы размещаете их уже на трёх, пяти или каком-то другом количестве реплик, чтобы переживать смерть конкретной машины, конкретного диска.
Следующий уровень проблем — когда данные перестают умещаться на одну машину и вам нужно заниматься их распределением по кластеру; это слой . У вас теперь много машин и очень большой диапазон ключей. Нарисуем его так: это пространство всех ключей (). Как мы поступим? Разделим его на отрезки, и каждый из них назовём range — например, range , ключи от до . И скажем, что каждый такой диапазон будет реплицироваться независимо: для каждого диапазона есть несколько машин, которые его реплицируют.
Давайте раскрасим картинку, чтобы было нагляднее. Вот у нас есть синий диапазон, и есть три машины в кластере, которые его хранят. Но есть и другие диапазоны, и, возможно, какие-то из этих машин хранят ещё и красный диапазон — у красного диапазона свой набор реплик. То есть на этом уровне мы скажем, что наши данные шардированы. Теперь в системе много таких диапазонов, каждый из них — как будто самостоятельное реплицированное key-value хранилище, и есть какой-то слой, который распределяет эти диапазоны между наборами машин в кластере.
И, наконец, последний интересный нам уровень — уровень транзакций, : без транзакций в key-value хранилище мы не получим транзакции на уровне . Это абсолютно классическая архитектура — примерно так key-value хранилище и строят, а поверх добавляют ещё слой с распределённым выполнением запросов, который реализует как раз , и получается что-то более-менее современное. Конечно, это безумно сложная задача, поэтому сегодня мы не планируем рассматривать все эти слои: про это у нас будет семинар и даже не одна лекция.
А сегодня мы решаем именно задачу репликации. Мы хотим разобраться, как отказоустойчиво хранить данные, которые помещаются в одну машину. Более того, мы совсем упростим себе задачу и скажем, что храним даже не диапазон ключей, а просто одну ячейку памяти — потому что очевидно, что и этого мы пока делать не умеем. Если мы научимся решать чистую задачу репликации, а потом добавим к ней локальное хранилище, то получим два нижних уровня нашей архитектуры.
Так что сегодня мы говорим даже не про key-value хранилище, а про гораздо более простую задачу, которую назовём репликацией регистра. У нас будет объект, который в академии называется , и у него есть две операции: — записать некоторое значение — и — это значение потом прочитать. Можно сказать, что мы будем заниматься репликацией ячейки памяти или же моделировать разделяемую память в распределённой системе.
Почему последняя аналогия кажется мне сейчас полезной? Нужно вспомнить прошлый семестр, где мы тоже занимались моделированием ячейки памяти: у нас была тема про модели памяти, и вы, наверное, помните, что темы это были довольно сложные. Мы разбирались, как ячейка памяти в вашем одном компьютере ведёт себя, когда с ней работают разные потоки, или как ведут себя много ячеек памяти. Ответ был довольно сложен. Почему он был сложен и, главное, как это соотносится с распределёнными системами? На самом деле аналогия здесь совершенно прямая: процессор — это распределённая система, потому что там есть ядра, у них есть свои кэши, и они общаются через некоторую шину. Конечно, там всё гораздо менее асинхронно и ничего не ломается — точнее, если сломается, то можно просто выкинуть компьютер, поэтому не страшно. Но суть проблемы та же: есть разные ядра, у каждого своё понимание, в каком состоянии находится ячейка памяти, и им нужно общаться друг с другом по процессорной шине. Так что то, о чём мы говорили в прошлом семестре вот с этими моделями памяти, мы сейчас собираемся обобщить в понятие модели согласованности. Только у нас дело ещё сложнее: есть отказы, есть асинхронность.
Итак, мы собираемся что-то реплицировать: одной машины нам мало, мы будем обходиться несколькими, и эти несколько машин должны хранить значение нашего регистра, нашей ячейки памяти. Сложность в том, что машины соединены проводами, по которым сигнал доставляется не слишком быстро — есть очевидная нижняя граница, скорость света в оптоволокне. Поэтому мы не рассчитываем, что три копии нашей ячейки памяти в каждый момент времени будут абсолютно синхронны: они будут отличаться. А как я уже сказал в прошлый раз, у нас будут клиенты, которые общаются с этой ячейкой памяти через разные машины. Первый клиент делает и получает , а второй клиент делает с другой машины. Это странно.
Мы, конечно, ожидаем, что система попытается скрыть свою распределённость и внутреннюю несинхронность. Мы не хотим, чтобы пользователь наблюдал, что у нас есть разные копии ячейки и они в разные моменты времени на самом деле содержат разные значения. Пользователь хочет получить простую абстракцию. Давайте подумаем, какого поведения мы могли бы ожидать от распределённой ячейки памяти. Пусть есть идеальный регистр — идея регистра, которую мы хорошо понимаем, — и есть какая-то реализация, распределённая и отказоустойчивая. Пользователь начинает задавать в неё запросы. Что эта реализация () ему генерирует? Она генерирует истории ().
Например, первый пользователь сделал запись значения — обозначим эту операцию ; второй пользователь примерно в то же время, но чуть позже начав и чуть позже закончив, сделал запись значения — операция ; а дальше идёт чтение , которое начинается уже после того, как завершилась, и пересекается с . Историей мы назовём, с одной стороны, вот такую картинку — но картинка, конечно, не математический объект, — а с другой стороны, последовательность событий: начало вызова, завершение вызова и его результат.
— Ну и что мне написать здесь, что это чтение вернуло пользователю? Единицу? Двойку? Тройку? Есть у нас какие-то ожидания по этому поводу?
— Единицу.
— А можно какую-то интуицию дать, почему мы ожидаем единицу или двойку?
— Двойку, потому что запись двойки была позже, чем запись единицы, и, видимо, это более свежее значение.
Есть такое мнение, что мы должны прочесть , поскольку запись двойки была позже. Вопрос непростой — вот к чему я клоню. Гарантии тут можно давать разные. Например, можно было бы дать такую минимальную гарантию: если мы что-то записали, а потом читаем, то свою запись мы прочтём, она хотя бы не потеряется. Можно вспомнить и другие известные вам гарантии. Смотрите: с одной стороны, мы читаем свои записи, и они не теряются. С другой стороны, если был клиент один, он записал значение , получил подтверждение от системы, а потом как-то пообщался с клиентом два, и клиент два после этого прочитал, то он обязательно должен увидеть запись первого клиента. Потому что это чтение упорядочено в отношении happens-before, упорядочено причинностью с этой записью.
Можно каким-то образом заставить систему эту причинность учитывать. Наверное, это было бы разумно, правда ведь? А как это сделать, когда коммуникация находится за пределами системы? Забегая немного вперёд и говоря не про гарантии, а про алгоритмы: можно было бы заставить систему возвращать какой-то токен, который первый клиент передал бы второму, тот отправил бы его вместе со своим чтением, и система поняла бы, что причинность есть. Действительно, так можно было бы поступить. Но мы сейчас хотим сформулировать свои ожидания от системы, не вдаваясь в подробности её реализации. Мы хотим именно простой API и никаких дополнительных деталей вроде токенов, которые возвращаются из системы и двигаются через коммуникацию клиентов.
Пока ответ не ясен: как же система должна себя вести? На самом деле некоторые интуиции есть, и к ним я сейчас клоню. Если даже забыть про concurrency, мы все хорошо понимаем, как ведёт себя просто ячейка памяти, когда с ней работают последовательно в одном потоке. Пусть я выписываю операции: сначала пишу в ячейку значение , потом пишу значение , потом читаю из ячейки, потом пишу значение , потом снова читаю — то есть .
Если нам дадут такую цепочку операций, то для каждого чтения мы очевидным образом можем сказать, что ячейка памяти должна вернуть: просто последнюю предшествующую запись. Здесь всё упорядочено, последняя предшествующая определена однозначно, и мы ни в чём не сомневаемся. Такую цепочку мы назовём последовательной историей: вот это — конкурентная история, а это — последовательная. И мы скажем, что у нашего объекта, конкретно здесь регистра, есть…
Линеаризуемость: определение и линеаризации истории
Итак, спецификация — это набор допустимых последовательных историй. Немного формализма, но, думаю, понятно, о чём речь. Теперь предположим, что у нас есть спецификация и есть конкретная реализация, причём конкретная реализация порождает некоторый набор конкурентных историй. Введём понятие модели согласованности. Модель согласованности даёт ответ на такой вопрос: какие конкурентные истории может порождать реализация для заданной спецификации? Пока я ввожу дополнительные термины, не очень содержательные сами по себе, но мы движемся к определению.
Посмотрим на иерархию моделей согласованности — это целое дерево, и кое-что в нём мы можем узнать. Где-то в основании диаграммы находится самая слабая гарантия — read your writes: если мы что-то записали, то ожидаем, что прочтём. Есть здесь и другая знакомая гарантия, она называется sequential consistency. Если у вас есть ячейка памяти и много клиентов, которые с ней работают, то мы скажем, что ваша реализация sequentially consistent, когда она порождает только такие истории, у каждой из которых есть линейное объяснение: в нём те же самые чтения возвращают те же самые результаты, что и в исходной истории, и при этом сохраняется порядок операций внутри каждого клиента. Sequential consistency в модели памяти (memory model) было ровно об этом. И sequential consistency — это просто частный случай модели согласованности.
От нашего распределённого регистра мы хотим требовать не этого, а другой гарантии. Эта модель согласованности называется линеаризуемость. Видно по диаграмме: она сильнее — она даёт больше гарантий; всякая линеаризуемая история будет sequentially consistent. Что же эта гарантия нам говорит? Формально: — для любой конкурентной истории , которая порождается реализацией некоторого объекта (в данном случае регистра), существует последовательная история , принадлежащая спецификации этого объекта, такая, что она построена из тех же самых операций и все операции возвращают те же самые результаты. И самое важное: если в исходной конкурентной истории есть две операции и такие, что завершилась в физическом времени до того, как началась , то мы потребуем, чтобы в линейной истории эти две операции шли в таком же порядке: . Это условие называется real-time ordering.
Я не знаю, насколько это интуитивно. Практика показывает, что нет, не интуитивно. Но на самом деле это самое естественное требование, которое только можно задать, и сейчас я попытаюсь это объяснить. Гарантия выглядит довольно странной, поэтому начнём с вопроса: что такое и как об этом интуитивно думать? Что такое , понятно: это та история, которая сгенерировалась в нашей реализации — мы написали какой-то код, и вот что получилось. А — это некоторое объяснение. С одной стороны, это внутренний логический порядок, в котором система принимает и обрабатывает ваши операции; но не буквально, конечно, а скорее порядок, которым мы объясним себе и другим, что произошло.
Посмотрим на конкретную историю. Две записи и перекрываются во времени, запись перекрывается с чтением, а успевает завершиться до начала чтения — это единственная пара операций, упорядоченная в физическом времени, хотя на картинке это, может быть, и не бросается в глаза. Пусть чтение вернуло единицу: . Тогда последовательная история, которую мы назовём линеаризацией, будет выглядеть так, как будто бы сначала случилась запись 2, потом случилась запись 1, а потом случилось чтение — и оно, конечно, вернуло результат последней записи: . Вот такую конкурентную историю мы можем объяснить такой последовательной. И она будет линеаризацией, потому что удовлетворяет нашему ограничению: единственную упорядоченную во времени пару операций мы сохранили в том же относительном порядке.
— То есть мы выбираем, что первой произошла запись?
— Да, сначала произошла запись значения 2.
— А почему?
— Почему так случилось — это деталь реализации. Мы сейчас говорим не про реализацию, а про наблюдаемое поведение. Смотрите: в определении написано «существует» — вот она и существует. Не «почему».
— А можно было иначе?
— Можно, да. Есть другая линеаризация: сначала записали 1, потом прочитали 1, потом записали 2, то есть . Это ещё одно объяснение такой же реакции системы на наши запросы.
Мы сейчас не пытаемся сказать, в каком именно порядке эти операции случились внутри системы. Система распределённая, там вообще может не быть линейного порядка — там, в конце концов, не лежит один mutex, который всё упорядочивает. Но мы можем объяснить себе, что система выполнила эти три операции либо в одном порядке, либо в другом, и оба объяснения устраивают нас одинаково. Могли ли мы здесь прочесть 2? Почему бы и нет: до тех пор, пока выполняется наше ограничение, мы никого не обманываем.
Итак, мы говорим, что наша реализация регистра линеаризуема, если она порождает только линеаризуемые истории: любая история, порождённая нашей реализацией, линеаризуема, то есть для любой истории найдётся такое объяснение. Для любой — в этом и состоит смысл гарантии. Если мы даём пользователю линеаризуемую систему, то он может не думать про то, что она распределённая: он может думать, что она действует атомарно, что операции в ней случаются как будто бы одна за другой и конкуренция не важна. Ещё раз, развёрнуто: любая конкурентная история, порождаемая нашей реализацией, допускает последовательную историю, соответствующую поведению однопоточного регистра, такую, что если две операции в конкурентной истории были упорядочены во времени, то и в нашем линейном объяснении они будут идти в том же порядке. Если эта формулировка тяжела, то для регистра употребляют синоним — атомарный регистр.
Но выглядит странным, что мы формулируем гарантию в терминах физического времени, — ведь в прошлый раз мы говорили, что узлы к нему доступа не имеют: часы у них есть, но эти часы несовершенные, и синхронизировать их тоже нельзя. Кто же тогда может понять, что одна операция завершилась до другой? Сами клиенты не могут, система не может. Почему же определение такое?
На самом деле ответ очень естественный. Чего на самом деле ожидают от системы пользователи — разве они ждут именно такой гарантии? Точное время операции они сами узнать не могут. Но они знают, например, что если внутри одного клиента сначала выполняется операция , а потом операция , то они, конечно же, упорядочены во времени — в этот момент пользователь знает, что предшествование есть. А когда ещё он знает, что одна операция предшествует другой? Например, здесь мы записали значение, сказали об этом другому клиенту, а тот прочитал. То есть иногда пользователи знают, что две операции упорядочены относительно друг друга, — но знают они об этом не потому, что часы у них очень точные и синхронизированные, а потому что они выстроили между этими операциями отношение happens before, причинность. Пользователи думают не про время, а про happens before, и ожидают, что наша система будет его учитывать.
А что про всё это знает система? Про happens before она не знает, и, как я уже говорил, узнать не может. Я, собственно, поэтому на первой лекции рисовал клиентов вне системы, за пределами модели: коммуникация между ними, порождающая happens before, происходит за пределами системы. Но упорядочивать записи внутри себя системе всё равно нужно. Вспомните прошлый пример — я говорил, что так делать не стоит, но пусть. Скажем, этот клиент не читает, а пишет: тогда в системе возникают две записи, и возникают они на разных узлах в разное время. Видимо, система должна сама внутри себя понять, какая запись более свежая, а какая более старая, то есть выстроить внутри себя некоторый порядок — например, снабдить записи версиями: вот запись более старой версии, вот запись более новой. Версии, временные метки — как угодно; будем считать, что внутри системы timestamp’ы и версии — синонимы.
Итак, есть два взгляда на порядок: у клиентов есть happens before, а внутри системы есть некоторый глобальный порядок на версиях. Фактически нам нужно эти два порядка согласовать: система и клиенты должны сходиться в том, в каком порядке выстраивать операции. Нужно каким-то образом добиться, чтобы timestamp’ы были согласованы с тем happens before, которого мы не наблюдаем. Клиенты не знают про timestamp’ы, timestamp’ы не знают про happens before клиентов, но у всех у них есть общее физическое время посередине. И вот ключевое наблюдение: если операции упорядочены отношением happens before, то они безусловно упорядочены и во времени, . Значит, если мы будем соблюдать требование real-time ordering внутри системы, то мы, конечно же, учтём и happens before пользователей: про него мы ничего не знаем и дадим чуть более сильные гарантии, чем пользователю на самом деле нужно. Ну и ладно — зато мы его порадуем.
Клиенты могут общаться друг с другом по сети как угодно: ты можешь отправить мне сообщение по мессенджеру. Что такое happens before? У двух операций в пределах одного узла happens before есть, если одна произошла до другой: ты сделал сначала одно, потом другое. И отправка сообщения предшествует его получению. Нет, я не говорю, что мы по времени что-то понимаем, — я объясняю, почему требование сформулировано через физическое время. Я не утверждаю, что мы знаем это физическое время, не утверждаю, что мы знаем границы отрезков: мы их не знаем. Но если мы выполним такое требование, то тем самым учтём и happens before, который пользователи организуют между собой снаружи системы. Поэтому я предлагаю про happens before забыть — мы всё равно его не знаем — и думать только про время.
У линеаризуемости есть и другие синонимы. Я сказал, что для регистра это атомарность, а разработчики Google Spanner, например, пишут external consistency: Linearizability External Consistency. Видимо, как раз намекая на эту самую гарантию: коммуникация может происходить снаружи системы, и она всё равно будет учтена. Выглядит ли гарантия линеаризуемости естественной, очевидной? Вообще должна. Это самая естественная и при этом самая сильная гарантия, которую можно потребовать: если мы ожидаем от системы атомарности, то вот формализация этой самой атомарности.
Можно огрубить всё это двумя способами. Первый: сказать, что внутри системы есть mutex — узел берёт этот mutex, выполняет операцию, и этот mutex как раз выстраивает нам линеаризацию. Это условность, потому что на самом деле никакого mutex может и не быть. Второй способ, тоже не слишком строгий: считать, что внутри каждого из отрезков можно выбрать точку, в которой операция случается как будто бы атомарно. Для нашей истории, где чтение вернуло 1, можно было бы сказать, что вот здесь выполнилась запись 2, вот здесь — запись 1, а вот здесь — чтение, вернувшее 1. Это интуиция, с которой можно подходить к определениям; но думать про точки не нужно — в определении никаких точек нет.
— Получается, для данной истории эта гарантия не говорит, что мы прочитаем либо единицу, либо двойку?
— История дана, ты в ней ничего не меняешь: история порождается реализацией. Реализация уже есть, она порождает какую-то историю, и ты либо можешь её объяснить, либо не можешь. Если можешь объяснить — всё хорошо, твоя система линеаризуема. Если не можешь объяснить — значит, не линеаризуема. Всё очень естественно: тебе дали код, ты его запустил, начал задавать запросы, система как-то себя ведёт, ты смотришь и понимаешь, хорошо она себя ведёт или плохо, допустимо или нет. А допустимо — если выполняется вот это условие.
Давайте покончим с определением и перейдём к реализации — тогда всё, наверное, станет естественнее. Итак, мы хотим построить линеаризуемую ячейку памяти, то есть атомарный регистр. Операции выпишу ещё раз: запись значения и чтение . Мы работаем в асинхронной модели, а сбои узлов такие: узлы либо падают навсегда, либо падают и рестартуют — но поначалу пусть они только падают. Что ж, начнём: мы хотим регистр реплицировать.
Репликация регистра: кворумы и отказоустойчивость
Теперь нужно решить, сколько машин будет хранить копии регистра. Здесь нужна какая-то интуиция: мы хотим отказоустойчивости, мы хотим пока только одного — переживать отказы. Понятно, что число машин будет зависеть от числа отказов, которые мы собираемся переживать, но как именно оно зависит, мы ещё не знаем, а потому разумно выбрать это число не можем. Так что выбор мы сделаем так, как диктует нам коллективное бессознательное, и скажем, что машин у нас три: три — очень естественное число. Итак, у нас три реплики, и я рисую их таймлайны .
Прежде чем думать, как выполнять операции, задачу нужно немного ограничить и упростить — иначе мы её всё-таки не решим. Во-первых, эти три реплики нам даны и не меняются: мы живём в статической конфигурации. Это довольно странно, потому что в реальности машины отказывают, ломаются, их нужно заменять на новые, но мы так делать не умеем и сегодня научиться не планируем: забегая вперёд, задача переконфигурации выглядит посложнее той, которую мы решаем сейчас. Будем считать, что этих узлов нам хватит.
Во-вторых, клиент, который выполняет операции чтения и записи, будет знать про эти машины: знать, сколько их, знать их адреса и коммуницировать с ними напрямую. Это вообще похоже на обман, потому что на прошлой лекции про модель я обещал вам, что клиент отправляет свой запрос на какую-то одну машину, а она уже дальше как-то обращается с этим запросом, с этой командой. Обман действительно есть, но на семинаре я объясню, как вернуть всё в ту модель; пока же я буду считать, что клиент знает про машины и общается с ними напрямую, потому что это драматически упрощает мои картинки. Иначе я просто взорвусь рисовать всё происходящее. То есть никакого обмана нет, это упрощение, которое я прокомментирую позже.
Третье допущение выглядит супер-странно и просто нелепо: скажем, что у нас пока только один клиент, который пишет. Это полная чепуха: если он действительно один и он умрёт, то больше никто никогда не будет писать в систему, и на что-то разумное это не похоже. Но мы увидим, что даже с таким ограничением задача не является тривиальной, а потом мы всё равно это починим. Прямую коммуникацию с узлами починим на семинаре, от единственного писателя скоро избавимся; переконфигурацию чинить не будем. Так что цепляться к этому не стоит: пока писатель ровно один — один узел, один клиент, выбранный заранее.
Итак, у нас появляется писатель, и он пишет какое-то значение — операция . Он должен пойти на реплики и сказать, что хочет записать это значение, и, наверное, он хочет записать его на все три реплики. Вопрос только в том, когда операция завершится для клиента: видимо, он ожидает подтверждений от реплик. Так сколько же подтверждений он должен получить, чтобы его операция состоялась? Одного точно недостаточно, потому что это не отказоустойчиво: мы получим одно подтверждение, машина взорвётся, два других сообщения потеряются, пока она рестартует. Синхронно писать только на одну машину не стоит.
С другой стороны, дожидаться подтверждения от всех трёх машин — тоже не отказоустойчиво, ведь мы хотим переживать сбои, хотим, чтобы система обрабатывала запросы даже тогда, когда какая-то реплика недоступна. То есть писать мы хотим на все машины, но синхронно дожидаться ответа — не от одной и не от трёх. Остаётся единственный вариант: дождаться двух подтверждений. Третье сообщение тоже летит, но лететь оно будет ещё долго. Вот первая запись и состоялась.
Дальше мы начинаем новую запись, . Что происходит? Мы снова пишем на все три реплики и снова дожидаемся двух подтверждений — в этот раз, скажем, записали на первую и на третью. Каждая реплика при этом хранит копию ячейки памяти, то есть то значение, в которое она верит. Сначала там лежит ; с некоторого момента хранит , затем ; хранит ; хранит . А в более поздний момент времени на третью реплику наконец долетает команда записи, принадлежащая первой записи клиента.
О чём тут нужно подумать? У нас есть три реплики, они не синхронны — собственно, это было заявлено ещё давно — и в один и тот же момент времени могут хранить разные значения: здесь реплика хранит , здесь , здесь снова . В системе на разных репликах лежат разные версии значения, и нужно, чтобы сама система понимала, какая из них более новая, а какая более старая. Это важно, потому что реплике нужно решить, что делать с прилетевшей к ней записью: выбросить её или, наоборот, стереть то, что у неё было, и заменить на . Чтобы это понять, внутри системы записи нужно упорядочить.
Поэтому клиент будет снабжать свои записи временными метками, версиями. Ему это делать несложно, потому что он один — собственно, поэтому он пока и один. Перед каждой записью он просто увеличивает у себя в голове счётчик, прикладывает его к своей команде и отправляет её на машины. Так что на самом деле писатель выполняет операции и , а реплики хранят пары и .
Что же делает реплика в этот момент? Она получает команду записи , а у неё уже лежит . Она сравнивает своё локальное значение с тем, что получила: если timestamp пришедшей записи меньше того, который она уже хранит, запись выбрасывается, иначе значение перезаписывается. Но что важно, клиенту мы всегда отвечаем подтверждением. Здесь запись будет проигнорирована — и всё равно мы говорим клиенту: «окей, я подтверждаю твою запись», даже если я её проигнорировала. Правда, конкретно этому ответу уже никто не рад, потому что запись давно завершилась. Отказ применить запись для нас тоже нормальный исход; мы даже не требуем, чтобы нам сообщили, отказ это или нет.
Хорошо, а теперь мы должны научиться читать. Вопрос: где же хранится правильное, где же хранится свежее значение, если три реплики вообще-то хранят разные? Откуда клиент знает, у кого больший , то есть более свежая версия? Ответ такой: правильное значение хранится на любой паре реплик. Каждая конкретная реплика может хранить старое значение, но среди любых двух уже обязательно есть более свежая версия.
Так что чтение мы делаем так. Мы снова, конечно, отправляем запрос всем трём репликам и снова, по тем же самым причинам и неизбежно для данной конфигурации, дожидаемся двух ответов. Скажем, нам ответили и . От второй реплики мы получили ответ, что у неё хранится , от третьей — что у неё уже . И мы, клиент-читатель, выбираем значение, у которого timestamp больше, и отвечаем на наше чтение значением — просто потому, что это максимальный timestamp. Временные метки у нас попарно различны, потому что писатель один и он генерирует их, увеличивая на единицу; они не повторяются.
Третьего ответа мы не дожидаемся: два ответа получили, из них уже выбрали максимум и сразу ответили. Если уж вам повезло и вы каким-то образом очень быстро получили три — окей, выберите максимум из трёх. Но наша цель — переживать отказ хотя бы одного узла, поэтому дожидаться третьего всегда мы не можем. Итак, и в записи, и в чтении схема одна и та же: отправляем команду на три реплики и дожидаемся двух ответов; на чтении из двух полученных пар выбираем максимум и отвечаем этим значением.
— А почему, если мы умеем жить без одной машины, просто не отправлять ей запрос?
— Так ты же не знаешь, какая из них умерла. Собственно, прямо сейчас мы про это и поговорим.
Числа у нас пока выбраны случайно: мы взяли произвольное число три и как-то неизбежно получили из него три адресата записи и два подтверждения. Похоже на произвол — так и было на самом деле. Но даже в такой конфигурации: сколько отказов мы способны переживать без потери доступности системы? Видимо, один отказ. Отказы мы обозначаем буквой и пишем, что . Такие конкретные значения, впрочем, нам не очень полезны — хочется куда-то это обобщить: не три и два, а понять общую схему, общую конструкцию.
Чего мы на самом деле хотели, когда подбирали количество подтверждений на чтение и на запись? Вывод очень скромный. Напоминаю, чего мы добиваемся: если запись состоялась, а потом мы читаем, то чтение непременно должно эту запись увидеть. Как мы этого добивались на картинке, как были связаны числа три и два? Нам важно, чтобы множество узлов, подтвердивших клиенту запись, пересекалось с множеством узлов, ответивших на чтение этого клиента.
Эту несложную интуицию можно обобщить в понятие, которое называется системой кворумов. Пусть — множество всех узлов, всех реплик, а — семейство подмножеств этого множества. Мы называем системой кворумов, если любые два множества этого семейства пересекаются: . То есть любые два кворума пересекаются хотя бы по одной реплике.
— А чем узел отличается от реплики?
— Узел — это машина в сети, которая общается с другими машинами. В данном случае у наших узлов есть конкретная роль: они реплики, потому что хранят копию одного и того же регистра, а не пытаются заменить друг друга. Слова разные, но я употребляю и одно, и другое, оба годятся; просто когда мы говорим про кворумы, естественнее говорить про реплики.
Какую очень естественную систему кворумов можно себе придумать? Ею мы, собственно, и пользовались: это минимальные строгие большинства, Majorities. И если мы пользуемся такой системой кворумов, то, сколько бы у нас ни было узлов, при записи мы дожидаемся ответа с любого кворума — говорим «собираем кворум», — а когда читаем, снова собираем кворум, выбирая максимум. Слово «кворум» вообще означает минимальное количество голосов, необходимое для принятия решения, — собственно, так у нас и есть.
Если мы пользуемся такой системой кворумов и узлов у нас , то можно прикинуть, сколько отказов мы переживаем: .
Теперь, когда у нас есть такое знание — есть система кворумов и есть формула отказоустойчивости нашего алгоритма, — мы можем прикинуть, какое число реплик нам нужно выбирать. Рассуждаем так: мы хотим пережить в своей системе какое-то количество отказов, сколько реплик нам для этого нужно? Тут есть нюансы: есть числа чётные, есть нечётные. Пусть сначала у нас узел, а потом узлов. Каков размер кворума? Если узлов , кворум равен , а если узлов — то . Когда система становится недоступной? Когда заблокирован любой кворум. Сколько же отказов, наоборот, можно пережить? В обоих случаях .
Отсюда простой вывод: не нужно выбирать чётное количество реплик. Если мы к трём добавляем четвёртую, то кворумы у нас растут на единицу и всё становится медленнее, потому что нужно ждать ещё один ответ, — а отказоустойчивость при этом не повышается.
— Замечание очень разумное. Вообще говоря, если у нас есть две операции — запись и чтение, — они упорядочены, и мы хотим, чтобы чтение увидело запись, то рассуждаем мы так. Эта запись собрала некоторый кворум: клиент отправил её на все машины, дождался подтверждения некоторого кворума — вот этого, красненького, — и свою запись завершил. А потом у нас было чтение, оно собрало какой-то свой кворум, и мы требуем, чтобы в пересечении был хотя бы один узел — собственно, об этом и есть система кворумов. И этот узел из пересечения даст чтению узнать об этой записи.
В этих рассуждениях мы нигде не говорили ни про какие большинства. Нам достаточно, чтобы кворум на запись пересекался с кворумом на чтение. Скажем, если у нас пять реплик, мы можем всегда писать на четыре, а читать с двух — и это тоже будет работать. То есть в том, как мы выбираем кворумы, у нас вообще-то есть гибкость. Но подумай, что в этом случае будет с отказоустойчивостью.
Чтение станет быстрее: ты дожидаешься двух подтверждений, а не трёх. И ты, конечно, ожидаешь, что в реальной системе, в промышленной, чтений будет гораздо больше, чем записей, — так устроен мир. Но при этом на пяти репликах ты теперь переживаешь не два отказа, как переживал бы в системе кворумов из большинств, когда все кворумы равнялись трём, а только один, потому что кворум на запись равен четырём. Чтение быстрее, но где-то в другом месте ты потерял.
Почему одного кворума мало: контрпример и фаза write-back
Вообще, есть целая забавная задача — как выбирать системы кворумов. По ней есть довольно странные статьи: там выбирают какие-то сложные сетки, строят пересекающиеся пути.
— А можно ли варьировать кворумы так, чтобы одну операцию делать медленнее, а другую быстрее?
— Да, можно. Чтобы ускорять чтение, мы можем увеличить кворум на запись и уменьшить кворум на чтение. Мне казалось, ты как раз об этом и спрашиваешь.
Но смотрите: кворумы с гарантиями напрямую пока не связаны. Кворумы — это инструмент, с помощью которого мы хотим достичь линеаризуемости. Правильно думать об этом так: гарантия, которая даётся пользователю, — это линеаризуемость; ему же даётся и граница на , то есть сколько отказов мы способны пережить. А кворумы — это механизм, главный наш инструмент, который позволяет скрывать отказ от пользователя. Пусть у нас пять узлов, два из них недоступны — они взорвались, у них меняют диски, — но три узла доступны, из них можно собрать кворум, и значит, операция завершится.
Но ведь никогда ни узлы системы, ни клиенты не знают, сколько узлов сейчас отказало. Текущее значение на самом деле не известно никому. Поэтому полезно подумать, что происходит с системой и с её поведением, когда превышает допустимую границу.
— Гарантия?
— Подожди, мы как раз и пытаемся это выяснить: гарантия у нас — линеаризуемость. Мы пытаемся понять, что именно мы говорим пользователю. Смотрите, мы могли бы поступить по-разному. Пусть у нас три узла и мы переживаем один отказ: вот три реплики, если одна из них умрёт, мы продолжим работать. А если умрёт вторая? Мы не хотим говорить, что тогда начнём вести себя безответственно и отвечать произвольным образом. Нет. Мы, наоборот, скажем так: у нас кворумы, ни один кворум не соберётся, поэтому система просто перестанет отвечать.
И это на самом деле хорошо. Конечно, это может огорчить — но не то чтобы система всегда висела; зато она точно не будет отвечать неправильно, нелинеаризуемо, потому что она вообще не будет отвечать.
Это же полезно при разговоре о partition, о сетевых разделах. Помните, я говорил вам, что есть такое явление, когда сеть раскалывается — не пополам, а на две части. Что происходит с нашим алгоритмом тогда? Мы уже выяснили, что число узлов у нас нечётное, поэтому ровно пополам сеть не расколется: есть большая часть и меньшая часть, и, к счастью, есть клиенты, которые работают с разными половинами.
Так вот, split-brain — ситуации, когда два осколка системы работают независимо друг от друга, — не возникает. Почему? Потому что в большей части кворумы собираются, и она продолжает работать, а меньшая часть не собирает ни одного кворума и поэтому пользователю не отвечает. Меньшая половина этого мозга отмирает, а большая продолжает функционировать.
Смотрите: если мы пишем на четыре узла, а читаем с двух, то чтение мы сможем обслуживать из обеих частей, но не сможем сделать ни одной записи — и к счастью. Потому что если бы мы могли читать с обеих сторон, а писать только с одной, то это добром бы не закончилось. Так что кворумы снова победили. Вроде бы всё разумно, да?
— Но ведь split-brain случился?
— Нет, split-brain не случился, наоборот, это успех. Partition случился, а split-brain — это когда ты при partition работаешь независимо.
— А правда ли, что при partition верхняя часть будет работать?
— Она вообще не будет работать. Хотя это зависит от системы кворумов, как мы только что выяснили. Если система кворумов — это большинства, то здесь будут работать и чтения, и записи, а здесь не будут работать ни чтения, ни записи. Если же у нас система кворумов — четыре на запись и два на чтение, то с этой стороны будут работать чтения, и с этой стороны будут работать чтения, и нигде не будут работать записи. То есть система сможет читать то, что в ней уже было, но не сможет записать ничего нового.
Мне кажется, что partition — это такое явление в сети, когда связность внутри частей сохраняется, а сообщения между этими долями не проходят. То есть вот эти узлы могут общаться между собой, и эти могут общаться между собой, клиенты могут работать со своей половиной, но пересечь эту границу нельзя. Иначе было бы невозможно работать, поэтому система этого и не допускает: она либо обслуживает чтение с обеих сторон без записи, либо… Если кворумы перевернуть и сказать, что у нас два на запись и четыре на чтение, то будет наоборот — но по-прежнему нормально, по-прежнему допустимо.
Ладно, с этим мы вроде бы разобрались. Теперь мы понимаем, что речь уже не про три узла и два, а про произвольное количество: пять узлов и кворумы по три, семь узлов и кворумы по четыре. Всё это можно тюнить.
Но верно ли, что мы получили линеаризуемость? Вот эта картинка пытается вас в этом убедить: есть одна запись, она предшествует вот этому чтению, и чтение, конечно же, увидит эту запись, значит, в истории они пойдут в правильном порядке. Есть система, которая называется Cassandra, — про неё я даже расскажу вам в другом курсе, — она работает именно так, и в ней есть эти самые кворумы, которые как раз можно тюнить.
Но рассмотрим пример. Читает кто угодно: читателей произвольное количество, мы их не ограничиваем, а писатель один. Вот же, кружочки пересеклись: вот эта реплика расскажет вот этому чтению об этой записи.
— А почему она обязательно расскажет?
— Смотри, у тебя есть много записей, у них есть timestamp, есть какая-то самая свежая запись. Если она завершилась, то на этой реплике запись с этим timestamp лежит; ты обязательно пересечёшься с какой-то из реплик, подтвердивших запись, узнаешь про это значение с этим timestamp и выберешь его, потому что оно максимальное. Видишь, оно на доске подчёркнуто — ты даже спрашивал уже об этом. Ладно, хорошо, но ты продолжай спрашивать, ты всё правильно делаешь.
Однако я анонсирую некоторый подвох. Мы же пока ничего не доказали. Линеаризуемость — это довольно строгая гарантия, поэтому если мы хотим кого-то в ней убедить, мы должны всё это доказать, а я пока только картинки рисую. И рисую неспроста.
Действительно, если у вас запись завершилась, а потом вы читаете, то кворумы дадут вам гарантию, что вы эту запись увидите. Но может быть и другая ситуация: запись затянулась. Давайте считать, что сначала на всех репликах хранится значение , и мы пишем в нашу систему : первая компонента — значение, вторая — версия, то есть timestamp. Так получилось, что сюда мы записали очень быстро, а других подтверждений пока не получили. Они летят, рано или поздно долетят — система же асинхронная, в конце концов.
И дальше появляется чтение, первое. Как оно работает?
— А это тот же самый клиент?
— Нет. У нас здесь один writer, он прямо сейчас пишет, и он синхронный: он не начинает новую запись, пока не завершил старую. Я забыл об этом сказать, а наверное, стоило. И ещё про обозначения: горизонтальные отрезки-скобки — это операции разных клиентов, а линии — это реплики. Я так по умолчанию считаю, наверное, это было неочевидно.
Вот какой-то клиент, который читает, и читает он, скажем, с третьей реплики и со второй, после чего своё чтение завершает. Что он прочтёт, что он вернёт из своей операции? Реплика ответила ему , а ответила . И мы выбрали значение с максимальным timestamp: .
Что случилось дальше? Дальше появилось ещё одно чтение, давайте оно будет зелёным. Надеюсь, камера хорошо снимает зелёный цвет. Зря я маркер положил.
— Но это же плохо: первое чтение пересекается с записью.
— Нет, это неплохо, и я сейчас объясню почему. Плохо не это. Линеаризуемость требует, чтобы в случае, когда две операции упорядочены во времени, одна и в объяснении шла после другой. Но линеаризуемость ничего не требует про операции, пересекающиеся во времени. Почему? Потому что если они пересекаются во времени, значит, между ними точно нет happens-before, а значит, пользователь ничего и не должен ожидать от таких операций. Так что никакого обмана сейчас нет.
Зато есть другой клиент, который тоже читает. Откуда он читает? Вот отсюда и отсюда. Видимо, он читает нули — и он читает ноль, . По-моему, вышло не очень клёво. А мы ведь ещё и единицу не записали — но это нас сейчас не заботит.
Я могу эту картинку удалить, как вы думаете? Вроде мы взяли от неё всё, что хотели. На ней был неправильный алгоритм, поэтому не жалко его стереть. Почему же он был неправильный? Не то чтобы он был безнадёжно плох, но он сгенерировал нам вот такую историю. Есть запись, она где-нибудь завершится — где именно, не важно, не хочется это рисовать. А здесь было два чтения: первое чтение случилось вот здесь и прочло единицу, а потом было другое чтение, которое случилось чуть позже и прочло ноль.
Эта история уж точно не будет линеаризуемой. Что говорит требование линеаризуемости? Что должна быть линейная, последовательная история, которая всё объясняет; и если в истории были два вызова, которые не пересекались, то они должны идти в том же порядке. То есть мы обязаны сохранить порядок вот этого чтения и вот этого чтения. А запись пересекалась со всеми, поэтому её можно было бы поставить либо сюда, либо сюда, либо сюда. Если мы поставим запись раньше обоих чтений, то оба чтения должны вернуть единицу — но второе вернуло ноль. Если мы поставим её между чтениями, то первое чтение должно вернуть ноль, а второе — единицу, то есть ровно наоборот тому, что произошло. А если мы поставим её после обоих чтений, то оба должны вернуть ноль — но первое вернуло единицу.
В итоге эта история не является линеаризуемой, она не похожа на поведение атомарной ячейки памяти, и, видимо, наша реализация не является линеаризуемой. Согласны со мной? Ну вот беда.
При этом, скажем, Cassandra это не мешает работать так, как было объявлено раньше, — видимо, потому что отсутствие линеаризуемости они способны пережить. В том смысле, что задачи, которые решаются в Cassandra, могут жить без такой сильной гарантии. Но мы не хотим.
На всякий случай: наш алгоритм не был безнадёжен, потому что случай завершившейся записи он учитывал. Но он не учитывал случай, когда запись ещё не завершилась. Если запись завершилась, то всё хорошо, чтение её увидит. А если запись ещё не завершилась, то клиент не понимает, пересёкся ли он с кворумом уже состоявшейся записи или просто увидел незавершённую запись. Эти две ситуации он не различает, потому что он маленький и смотрит только на какие-то локальные ответы, а что происходит глобально, он понять не в состоянии.
Что ж, нужно починить. Вообще, такую ситуацию мы с вами уже встречали — когда вы приходите, что-то делаете и не понимаете, в каком именно состоянии находится мир. Помните, бывало с вами такое? Возможно, не помните, но я напомню. Приходите вы как-то в lock-free очередь вставлять узел в конец, читаете указатель tail и хотите подвесить к нему новый узел — а к нему уже что-то подвесили. И вы понимаете, что tail указывает не на последний узел, значит, возможно, какая-то другая операция сейчас in progress. А возможно, она сейчас зависла — в этом и была суть lock-free, мы не хотим её дожидаться. Что мы делали тогда? Мы помогали ей передвинуть tail.
Что мы сделаем здесь? Смотрите: у нас есть чтение, оно читает единицу, но оно неуверенно. Может быть, на этом кворуме уже написана единица и запись состоялась, а может быть, запись написана только здесь и кворум для неё ещё не собран — и тогда чтение после этого кворума может прочесть более старое значение. Как же добиться того, чтобы чтение, которое началось после нас, непременно прочитало ту же самую единицу — не младше, не старше, по крайней мере единицу? Давайте мы поможем закончить запись вот этому парню.
И здесь важный момент. Мы уже знаем, что вернём единицу, мы это решили: у нас есть ответ , и мы его зафиксировали. Ровно его мы и дозапишем на кворум. Причём можно выбрать странные кворумы, можно для верности записать и туда же — это не важно. Главное, что мы снова должны получить два подтверждения на запись.
Ведь сами мы ничего не знаем, мы просто прочли два разных значения. Если бы мы прочли два одинаковых значения, то можно было бы не волноваться: мы бы знали, что эта запись уже точно состоялась. А если мы прочли разные значения, то мы не уверены насчёт статуса этой единицы: может быть, она уже записалась, а может быть, запись ещё тянется. Вот мы и дописываем её для верности. Давайте скажем, что у нас есть такие фазы: в фазе мы читаем, а в фазе мы пишем.
— Так ведь никакой гарантии нет.
— В смысле, что значит «нет гарантии»? Кворум может не собраться, потому что превысится число отказов, — такое может быть. Или вот эта запись затянется, потому что какое-то сообщение летит очень медленно: оно блуждает, блуждает и где-то потом приземлится, и тогда запись там закончится.
— А что будет с чтением?
— Значит, это чтение затянется. Но дело же не в этом: ты, кажется, неправильно на это смотришь. Ты говоришь о том, медленно или быстро, а мы сейчас не про медленно или быстро — мы про линеаризуемость. Конечно, такие фазы нам ничего не ускоряют, но мы их делаем не от хорошей жизни, а потому что нам нужно соблюсти гарантию. Ячейка памяти у нас получилась не атомарная — пока не атомарная. Возможно, сейчас она станет более атомарной.
— Не может быть более атомарной: либо атомарная, либо нет.
Кворум мы при этом не выбираем: мы пишем на все реплики и дожидаемся, пока кворум соберётся. Какой соберётся, такой нас и устроит. То есть мы не подгадываем, на какие реплики отправлять. Наверное, на вторую реплику слать не стоит, потому что там это значение уже есть и лучше не станет, — но об этом мы сейчас не думаем.
На самом деле нас это может и не спасти: пока мы пишем, второе чтение может просочиться раньше и прочесть ноль. Но в этом случае это означает, что наша запись в первом чтении затянулась и мы пересеклись с этим чтением, — а тут уже никакие гарантии для нас не важны, потому что про пересекающиеся операции мы ничего не обещали. Смотри: если вот этот красный хвостик, красная фаза записи, завершится раньше начала чтения, то чтение уже обязано прочесть нашу запись, единицу. А если красный хвостик затянулся, то чтение может увидеть, а может и не увидеть то, что мы дописываем. Но в этом случае у нас просто нет никаких обязательств перед пользователем, потому что операции пересеклись, значит, пользователь их не упорядочил, значит, он ничего и не ожидает.
— А разве это не одно и то же?
— Да нет, конечно, совершенно другое, разница колоссальная. Ещё раз: гарантия линеаризуемости про то, что если операции не пересекались, то между ними могла быть причинность, и мы должны её учесть. А здесь мы что-то настолько задержали, что никаких гарантий уже быть не могло: эта операция не могла зависеть от той у пользователя, значит, мы можем гарантии не соблюдать. Но если мы завершились раньше, то зависимость могла быть, и мы её обязательно учли.
Ладно, это нам ничего не доказывает — нужно что-то объяснить строго. Смотрите.
Доказательство линеаризуемости и несколько писателей
Теперь мы хотим показать, что полученный алгоритм линеаризуем. Каким образом это можно показать? Нужно предъявить линеаризацию для любой истории: взяли наш алгоритм, запустили его, сгенерировалась какая-то история — и все операции, которые в этой истории были, нужно выстроить в некотором порядке. Давайте этот порядок выберем и явно его сейчас построим. Это несложно, потому что все записи уже упорядочены самим писателем — он у нас единственный. У нас была первая запись, вторая, третья и так далее: . А ещё у нас были чтения — куда мы их поставим?
Мы говорим не про картинку, мы строим линеаризацию — ту историю, которая объясняет любое конкурентное исполнение. Мы наконец придумали алгоритм, он нагенерировал нам историй, а теперь мы должны сказать, что для любой истории, которую он сгенерировал, есть некоторое объяснение, где все операции идут друг за другом, они возвращают то же самое, что и в исполнении, и при этом если две операции не пересекались по времени, то и в нашем объяснении они идут в том же порядке. И это объяснение называется линеаризацией. Вот мы его сейчас и строим.
Я просто написал, что значат индексы у . Это timestamp, который выбрал писатель; timestamp и версию я использую взаимозаменяемо. Записи мы упорядочиваем легко — их упорядочивает сам пишущий клиент, он у нас один. А вот чтения нужно где-то расположить так, чтобы, если выполнять операции в этом порядке, забыв про реализацию, они вернули бы то же самое.
У чтения тоже есть timestamp. Чтение выбирает максимум из тех временных меток, которые оно увидело на кворуме, — давайте этот максимум и возьмём и скажем, что это timestamp чтения. В итоге у нас теперь много чтений: , затем , затем — и мы их поставим после соответствующих записей. Если два чтения с одним timestamp были упорядочены во времени, мы их в таком же порядке и поставим между записями; если не были упорядочены, то в произвольном порядке. Главное — после записи: если в исполнении чтение прочитало эту запись, то в линеаризации мы поставим это чтение после этой записи.
Поэтому если мы прогоним всё слева направо, то чтение, разумеется, вернёт то же самое, что и в исполнении. Здесь происходит очень несложный формализм, никакого глубокого содержательного смысла в нём нет. Если следующее чтение произошло позже первого, но прочитало меньший timestamp, то в линеаризации оно уйдёт ближе к началу. Про время я пока почти ничего не говорил: я сказал только, что чтения, которые прочли значение с timestamp 2, мы в линеаризации поставим после записи с timestamp 2.
— То есть само чтение ничем таким не обладает, но мы его ставим туда, где…
— Оно в исполнении связалось с этой записью. Вот мы в линеаризации после этой записи его и поставили.
— То есть нам не важно, как это было в реальном времени?
— Важно, конечно, но мы просто про это ещё не поговорили.
Итак, это линейный порядок, который претендует на то, чтобы быть линеаризацией. А чтобы быть линеаризацией, нужно следующее: если есть две операции и , между которыми был какой-то временной зазор, то в порядке timestamp’ов эти операции идут так же, то есть . Сейчас это сформулировано не совсем строго — если вы понимаете, почему, здорово; если не понимаете, то и не важно. Но хотим мы примерно этого. Интуиция вот в чём: записи в системе на каждой реплике упорядочены по timestamp, а мы требуем гарантию относительно реального времени, и сейчас мы показываем, что наши timestamp’ы с временем согласованы.
Случаев более-менее два. Что если — это запись? Тогда у неё timestamp больше, потому что писатель выбрал новый timestamp, которого в системе вообще не было: только он генерирует новые timestamp’ы. Значит, у timestamp больше, и она точно стоит правее и в линеаризации. Операции при этом совершенно произвольные: если это была запись, то timestamp больше, значит, и в истории она стоит правее.
Теперь пусть — чтение. Чем может быть ? На самом деле неважно: это может быть или чтение, или запись, но чем бы оно ни было, у этой операции есть фаза записи — либо это её единственная фаза, либо это её вторая фаза. И смотрим на картинку: на второй фазе чтения или на единственной фазе записи мы записали что-то на кворум со своим timestamp, потом в операции чтения мы пересеклись с этим кворумом на запись, получили этот timestamp, и значит, он у нас не меньше. То есть в линеаризации мы выстроили все операции в порядке timestamp’ов, и этот порядок согласован с реальным временем. Значения здесь вообще не важны, я их не рисовал.
Разберём второй случай подробнее — тот, где чтение. Чем определили это чтение? — это какая-то операция: если это запись, то это просто запись; если это чтение, то в ней есть фаза записи. А в фазе записи мы собираем кворум на запись, то есть пишем на все реплики и получаем подтверждение с большинства. И на большинстве остаётся запись по крайней мере с нашим timestamp’ом, а может быть, даже с большим. Так что когда мы здесь читаем, кворум чтения пересекается с кворумом записи, в пересечении есть хотя бы одна реплика, и на этой реплике написан либо timestamp этой записи, либо ещё больший — поэтому нас это устраивает.
— Но если у нас вторая фаза произошла до…
— Нет, смотрите, это дано. Гарантия линеаризуемости: если одна операция предшествует другой во времени, то они выстроены в таком же порядке в линеаризации. Вот этим я и пользуюсь. У нас операция упорядочена во времени — это любая операция: если это чтение, то всё справедливо; если это запись, то тоже справедливо. Всё, случаи кончились.
— Значит, запись… порождает предшествование?
— Это дано, ещё раз: мы доказываем, что это выполняется.
— Окей, я доказываю, что…
— Да. Это же требование линеаризуемости: существует порядок этих операций такой, что он уважает реальное время. И он уважает.
— Но в реальном случае, если у нас ack’и ещё не дошли? То есть у нас второе чтение происходит — зелёное, — а красная фаза ещё не произошла.
— Так у нас тогда линеаризуемость никаких требований на это не накладывает. Если две операции пересекаются во времени, мы ничего от такого порядка не требуем.
— А как мы берём…
— Когда мы читаем что-то, то перед тем как вернуть значение пользователю, мы записываем. Записываем с максимальным timestamp’ом, который мы увидели: мы же читаем не просто значение, мы читаем пары «значение плюс timestamp». Значение мы здесь уже выбрали себе, то, которое вернём пользователю, а потом запишем эту пару — и вот эту единицу сделаем timestamp’ом этого чтения.
— То есть чтение всё время записывает?
— Да. Тут можно придумать оптимизацию: если ты прочёл одно и то же, то записывать не нужно, но это мелочь. И операция всё равно одна — просто у неё есть фаза и фаза , логически это одна операция.
Это корректно, потому что две операции пересекаются во времени, а на такие операции ограничений нет. Обозначим операции на картинке: , , . Тогда вся эта история линеаризуется так: сначала идёт чтение 3, и оно вернуло 0; потом запись 1; а потом чтение 2, и оно вернуло 1. Вот это линеаризация, которая объясняет такое исполнение. Никакого обмана вроде нет.
Остался небольшой хвостик. Итак, мы придумали алгоритм, который при записи собирает кворум, а при чтении собирает кворум, а потом ещё дописывает на кворум — чтобы уж наверняка. Это довольно странно, потому что у нас чтение дороже записи, а это ненормальная ситуация. Но как получилось, так получилось: зато это теперь наконец линеаризуемо.
Однако мы решили очень странную задачу, абсолютно бесполезную: писатель у нас только один. Конечно же, такие системы нас не интересуют, не бывает таких случаев, чтобы писатель был только один и никогда не умирал. Поэтому теперь у нас писателей много. В чём сложность перехода, зачем я ограничил задачу одним писателем? Потому что единственный писатель выполнял свои операции одну за другой и просто увеличивал счётчик в голове — ему timestamp было легко выбирать. А теперь мы хотим выбирать timestamp’ы распределённо, на разных писателях. И чтобы все прежние рассуждения работали, нужно, чтобы timestamp’ы выбирались распределённо и монотонно: если две записи упорядочены во времени, то и timestamp’ы находятся в таком же соотношении, .
Как можно было бы попробовать этого добиться? Кассандра делает так: вы пишете — то есть пишете какое-то значение и в качестве timestamp отдаёте текущее время. Это разумно? Оговорюсь: время не клиентское. В лекции есть некоторый обман, как будто бы клиенты сами всё пишут на узлы. В реальности клиент отправляет свою команду write, эта команда приземляется на какой-то узел, который мы называем координатором, и уже он выбирает timestamp, собирает кворумы, а потом подтверждает операцию нам, клиенту.
Но координаторы для разных записей могут быть разными, и часы у них могут быть не синхронизированы. Запросто может получиться так, что узел, который генерирует timestamp для записи , выберет себе 12:01, потому что его часы немного спешат, а узел, который выбирает timestamp для операции — позже в физическом времени, — выберет себе 11:59, потому что его часы отставали. И в итоге мы гарантию нарушили. А чего вы смеётесь? Звучит крайне разумно, на самом деле.
Смотрите, мы хотим, чтобы если запись состоялась, то следующая запись получила бы строго больший timestamp. Но если эта запись состоялась, значит, она уже записалась на кворум. Так что же мы сделаем? Мы писатель, и у нас есть три наши реплики. Мы начали запись — и давайте сначала прочитаем что-нибудь с кворума и выберем себе timestamp. Каким образом? Можно выбрать максимум плюс один. Это не будет работать — в домашке увидите, — но пока сойдёт.
Что такое временные метки, я ведь не говорил. Временные метки могут быть чем угодно, это линейно упорядоченное множество; пусть пока это будут целые числа. А дальше мы, собственно, сделали запись. Происходят две фазы: фаза (чтение) и фаза (запись), а вся операция — это глобальная запись. В фазе мы выбрали себе timestamp, в фазе мы с ним записали. Эта лишняя фаза нужна нам для того, чтобы обеспечить нужное свойство.
И, кажется, мы его сейчас добились, потому что синий кворум чтения этой операции пересечётся с кворумом записи предыдущей операции. У нас снова кворум на чтение пересёкся с кворумом на запись. И так будет всегда: у нас будут кворумы, которые что-то читают, и кворумы, которые что-то пишут, то есть разные фазы, и, как правило, нам важно, чтобы пересекались именно разные фазы, а не одна и та же.
— А почему нужно брать именно максимум?
— Потому что у нас было много записей. Какая-то наша запись должна получить timestamp больше, чем любая запись, которая завершилась до неё. Поэтому мы собрали кворум, пересекли его с кворумом каждой предшествующей записи и выбрали timestamp «максимум плюс один», то есть перекрыли timestamp каждой предшествующей записи.
На самом деле у вас могла быть другая конкурентная операция записи, и будет плохо, если, скажем, она выберет тот же самый максимум плюс один — мы об этом не подумали. Может быть, даже это один узел, который обрабатывает две конкурирующие операции записи; в общем, всякое бывает. Но суть, наверное, ясна.
— А который умирает?
— Это неинтересно: мы вроде бы договорились с самого начала, что узлы умирают, так что ничего не выйдет. Узлы умирают, и кворумы нам нужны как раз потому, что мы не ожидаем, что кто-то конкретный будет жить. Кворумы ровно эту проблему для нас и решали.
Теперь у нас восстановилась симметрия: и чтение, и запись устроены одинаково — они сначала читают, потом пишут, немножко по-разному, но по крайней мере они одинаковые по цене. И задача, в общем, решена. Строго доказывать я сейчас не буду, но идея понятна: вы снова строите линеаризацию, и если у вас есть две операции, которые не пересекаются во времени, то опять нужно показать, что timestamp согласован с реальным временем, и вы говорите, что здесь есть фаза записи, а здесь есть фаза чтения, поэтому все будут довольны.
А теперь TrueTime. Помните, я говорил вам про TrueTime? Я говорил, что есть вот такие правильные волшебные часы, которые возвращают вам интервал времени, отрезок, в котором реальное время точно содержится. И если вы Google, то вы такие часы строить умеете: у вас есть сервис TrueTime и функция , которая возвращает отрезок, содержащий настоящее реальное время. Так вот, в первой домашке вы сможете воспользоваться этим сервисом в симуляции.
Зачем он нужен Google и зачем он нужен нам? Зачем он нужен Google, объяснить сложно, потому что это детали протокола транзакций, но в принципе можно объяснить на генерации распределённых монотонных timestamp’ов. Смотрите: чтобы две операции выбрали себе timestamp, им нужно сделать лишнюю фазу коммуникации, пообщаться с другими узлами, чтобы узнать их прошлое. Так вот, TrueTime нужен как раз для того, чтобы, если у вас реплики далеко и коммуникация между ними дорогая, потому что они физически находятся далеко, вы могли эту коммуникацию заменить на ожидание. Вы можете выбрать timestamp, просто подождав и ничего не сделав, вместо того чтобы общаться по сети.
— А как именно это сделать?
— Так это же домашняя работа, сам придумаешь потом. В смысле, можно будет написать и так, а можно будет написать с TrueTime; кажется, что разумно написать обоими способами. Нужно немножко подумать. Тогда ты изобретёшь правило, которое называется commit wait. Никакого commit’а здесь, конечно, нет, это странно, но в Spanner’е это называется commit wait, и в Spanner’е им пользуются точно так же, как мы можем воспользоваться здесь.
Переходим к заключительной части и подведём итоги. Чего мы добились? На самом деле очень многого. Мы решили задачу в асинхронной модели — может быть, вы этого не заметили, но мы этого добились: мы нигде не ожидали какого-то поведения от часов, от скорости доставки в сети, от узлов. Рано или поздно сообщение долетает, рано или поздно собирается кворум, рано или поздно операция завершается; то есть если отказов меньше половины, , то любая операция завершится. Это довольно неплохо. И мы получили линеаризуемость — тоже очень сильную гарантию. Но мы ничего не сказали про эффективность и вообще не объяснили, как мы собираемся её измерять и от чего она зависит.
Стоимость операции и итоги
Понятно, что алгоритмы бывают менее эффективные и более эффективные, и нужно в каких-то терминах оценить, насколько наш алгоритм хорош. То есть нам нужна метрика стоимости — нам нужны какие-то статьи расхода, понимание того, на что именно мы расходуем. Эффективность мы измеряем в смысле latency: сколько времени пользователь выполняет операцию, насколько долго она длилась. От чего это зависит? Пока вы не можете ответить на этот вопрос, потому что мы ещё не поговорили о том, что мы делаем с рестартами узлов.
Узлы у нас падают — и хорошо, это не проблема, мы с этим научились жить. А что если они рестартуют? Как это учесть в алгоритме? Смотрите: если мы собрали кворум на запись, то мы ожидаем, что чтение обязательно эту запись увидит — собственно, на этом и строились все наши рассуждения. Поэтому если мы что-то пишем на реплику и она подтверждает запись, то перед подтверждением она должна надёжно сохранить данные на диск, чтобы потом это обещание не потерять. Так что рестарты поддерживаются очень просто: мы всего лишь сохраняем на диск все свои записи.
Теперь можно подумать, на что мы тратим время — какие у нас есть статьи расхода. Величин у нас более-менее две: время round trip’а и диск.
Round trip time — это время, чтобы сходить по сети туда и обратно. И непонятно, что из этого доминирует. Смотрите: если вы живёте в ДЦ на жёстких дисках, то время round trip у вас меньше миллисекунды, а время записи на диск с флашем — если вы зовёте — это сколько? Это миллисекунд. То есть меньше миллисекунды на сеть и миллисекунд на то, чтобы положить что-то на диск. А если вы работаете в geo-distributed инсталляции, где round trip требует сотен миллисекунд, но при этом живёте на SSD, то получается наоборот: round trip — это сотни миллисекунд, а запись на диск, на SSD, — это микросекунды, десятки микросекунд.
Так что в зависимости от того, какие у вас диски и как далеко вы расположили реплики, больше может оказаться либо одно, либо другое — поэтому минимизировать нужно стараться всё. И вообще вся эта операция у нас называется кворумным флашем: когда мы что-то пишем, мы должны собрать подтверждение с кворума, а для каждого подтверждения нужна запись на диск. Кворумный флаш — это и есть наша статья расхода в случае, когда мы живём с рестартами.
И совсем конец. Мы построили ячейку памяти, мы решили задачу репликации вот такого регистра — модель данных у нас очень простая. Да, мы, конечно, не умеем переконфигурировать систему, и у нас есть какой-то обман с конфигурацией: клиент знает про всех. Но это мы рано или поздно решим.
А вот что нас действительно беспокоит — это то, что в нашей архитектуре баз данных поверх слоя key-value и распределённости мы хотим построить транзакции. А чтобы построить транзакции, нужно уметь делать что-то сложнее, чем чтение и запись. Грубо говоря, вы, надеюсь, видели в своей жизни атомики и знаете, что там есть не только и — там есть всякие операции . Так вот, можно ли взять этот алгоритм и ввернуть в него, скажем, операцию ? Нам этого захочется. Можно подумать об этом самим, а можно подумать в следующий раз — с этого мы и начнём.