Следующая конференция HighLoad++ пройдет 6 и 7 апреля 2020 года в Санкт-Петербурге.
Подробности и билеты по ссылке. HighLoad++ Siberia 2019. Зал «Красноярск». 25 июня, 12:00. Тезисы и презентация.
Бывает, что практические требования конфликтуют с теорией, где не учтены важные для коммерческого продукта аспекты. В этом докладе представлен процесс выбора и комбинирования различных подходов к созданию компонентов Causal consistency на основе академических исследований исходя из требований коммерческого продукта. Слушатели узнают о существующих теоретических подходах к logical clocks, dependency tracking, system security, clock synchronization, и почему MongoDB остановились на тех или иных решениях.
Михаил Тюленев (далее – МТ): – Я буду рассказывать о Causal consistency – это фича, над которой мы работали в MongoDB. Я работаю в группе распределённых систем, мы её сделали примерно два года назад.
В процессе пришлось ознакомиться с большим количеством академического Research, потому что эта фича достаточно хорошо изучена. Выяснилось, что ни одна статья не вписывается в то, что требуется в продакшне, базе данных в виду весьма специфических требований, которые есть, наверное, в любом production applications.
Я буду рассказывать о том, как мы, являясь потребителем академического Research, готовим из него что-то такое, что мы потом можем преподнести нашим пользователям в качестве готового блюда, которым удобно, безопасно пользоваться.
Для начала я хочу в общих чертах сказать, что же такое Causal consistency. Есть два персонажа – Леонард и Пенни (сериал «Теория большого взрыва»):
Предположим, что Пенни в Европе, а Леонард хочет сделать для неё какой-нибудь сюрприз, тусовку. И он ничего лучше не придумывает, чем выкинуть её из френд-листа, послать всем друзьям апдейт на feed: «Давайте порадуем Пенни!» (она в Европе, пока спит, не видит этого всего и не может увидеть, потому что она не там). В конечном моменте удаляет этот пост, стирает из «Фида» и восстанавливает access, чтобы она ничего не заметила и скандала не было.
Это всё прекрасно, но давайте предположим, что система распределённая, и события пошли не немного не так. Может, например, случится, что ограничение access Пенни произошло после того, как появился этот пост, если события не связаны между собой причинно-следственными связями. Собственно, это – пример того, когда требуется наличие Causal consistency для того, чтобы выполнить бизнес-функцию (в данном случае).
На самом деле это достаточно нетривиальные свойства базы данных – очень мало кто их поддерживает. Давайте перейдём к моделям.
Что такое вообще модель консистенции в базах данных? Это некоторые гарантии, которые распределённая система даёт по поводу того, какие данные и в какой последовательности клиент может получить.
В принципе все модели консистенции сводятся к тому, насколько распределённая система похожа на систему, которая работает, например, на одном nod’е на лэптопе. И вот насколько система, которая работает на тысячах геораспределённых «Нодов», похожа на лэптоп, в котором все эти свойства выполняются в принципе автоматически.
Поэтому модели консистенции только к распределённым системам и применяются. Все системы, которые раньше существовали и работали на одном вертикальном масштабировании, таких проблем не испытывали. Там был один Buffer Cache, и из него всё всегда вычитывалось.
Собственно, самая первая модель – это Strong (или линия rise ability, как её часто называют). Это модель консистенции, которая гарантирует, что каждое изменение, как только получается подтверждение о том, что оно произошло, становится видно всем пользователям системы.
Это создаёт глобальный порядок всех событий в БД. Это очень сильное свойство консистенции, и оно вообще очень дорогое. Тем не менее оно очень хорошо поддерживается. Оно просто очень дорогое и медленное – им просто редко пользуются. Это называется rise ability.
Есть ещё одно, более сильное свойство, которое поддерживается в «Спаннере» – называется External Consistency. Мы о нём поговорим чуть позже.
Следующее – это Causal, как раз то, о чём я говорил. Между Strong и Causal существует ещё несколько подуровней, о которых я не буду говорить, но они все сводятся к Causal. Это важная модель, потому что она – самая сильная из всех моделей, самая сильная консистенция при наличии сети или partitions.
Causals – это собственно ситуация, при которой события связаны причинно-следственной связью. Очень часто их воспринимают как Read your on rights с точки зрения клиента. Если клиент наблюдал какие-то значения, он не может увидеть значения, которые были в прошлом. Он уже начинает видеть префиксные чтения. Это всё сводится к одному и тому же.
Causals как модель консистенции – частичное упорядочивание событий на сервере, при котором события со всех клиентов наблюдаются в одной и той же последовательности. В данном случае – Леонард и Пенни.
Третья модель – это Eventual Consistency. Это то, что поддерживает абсолютно все распределённые системы, минимальная модель, которая вообще имеет смысл. Она означает следующее: когда у нас происходят некоторые изменения в данных, они в какой-то момент становятся консистентными.
В такой момент она ничего не говорит, иначе она превратилась бы в External Consistency – была бы совершенно другая история. Тем не менее это очень популярная модель, самая распространённая. По умолчанию все пользователи распределённых систем используют именно Eventual Consistency.
Я хочу привести некоторые сравнительные примеры:
Что эти стрелочки означают?
Когда вы видите слова consistency, availability – что вам приходит на ум? Правильно – CAP theorem! Я сейчас хочу развеять миф… Это не я – есть Мартин Клеппман, который написал прекрасную статью, прекрасную книжку.
Теорема CAP – это принцип, сформулированный в 2000-х годах, о том, что Consistency, Availability, Partitions: take any two, и нельзя выбрать три. Это был некий принцип. Он был доказан как теорема несколько лет спустя, это сделали Джилберт и Линч. Затем это стало использоваться, как мантра – системы стали делиться на CA, CP, AP и так далее.
Эта теорема была доказана на самом деле вот для каких случаев… Во-первых, Availability рассматривалась не как непрерывное значение от нуля до сотни (0 – система «мёртвая», 100 – отвечает быстро; мы её так привыкли рассматривать), а как свойство алгоритма, которое гарантирует, что при всех его executions он возвращает данные.
О времени ответа там вообще нет ни слова! Есть алгоритм, который возвращает данные через 100 лет – совершенно прекрасный available-алгоритм, которые является частью теоремы CAP.
Второе: доказывалась теорема для изменений в значениях одного и того же ключа, притом что эти изменения – линия resizable. Это означает то, что на самом деле они практически не используются, потому что модели другие Eventual Consistency, Strong Consistency (может быть).
К чему это всё? К тому, что теорема CAP именно в той форме, в которой она доказана, практически не применима, редко используется. В теоретической форме она каким-то образом всё ограничивает. Получается некий принцип, который интуитивно верен, но никак, в общем-то, не доказан.
То, что сейчас происходит – можно получить все три вещи: Consistency, Availability получить с помощью Partitions. В частности Causal consistency – самая сильная модель консистенции, которая при наличии Partitions (разрывов в сети) всё равно работает. Поэтому она и представляет такой большой интерес, поэтому мы ею и занялись.
Она, во-первых, упрощает труд разработчиков приложений. В частности, наличие большой поддержки со стороны сервера: когда все записи, которые происходят внутри о дного клиента, гарантировано придут в такой последовательности на другом клиенте. Во-вторых, она выдерживает partitions.
Помня о том, что ланч, мы перемещаемся на кухню. Я расскажу про модель системы, а именно – что такое MongoDB для тех, кто впервые слышит о такой базе данных.
MongoDB (далее – «МонгоБД») – это распределённая система, которая поддерживает горизонтальное масштабирование, то есть шардинг; и внутри каждого шарда она также поддерживает избыточность данных, то есть репликацию.
Шардинг в «МонгоБД» (не реляционная БД) выполняет автоматическую балансировку, то есть каждая коллекция документов (или «таблица» в терминах реляционных данных) на кусочки, и уже сервер автоматически двигает их между шардами.
Query Router, который распределяет запросы, для клиента является некоторым клиентом, через который он работает. Он уже знает, где и какие данные находятся, направляет все запросы к правильному шарду.
Ещё один важный момент: MongoDB – это single master. Есть один Primary – он может брать записи, поддерживающие те ключи, которые он в себе содержит. Нельзя сделать Multi-master write.
Мы сделали релиз 4.2 – там появились новые интересные вещи. В частности, вставили Lucene –поиск – именно executable java прямо в «Монго», и там стало возможным выполнять поиск через Lucene, такой же, как в «Эластике».
И сделали новый продукт – Charts, он тоже доступен на «Атласе» (собственный Cloud «Монго»). У них есть Free Tier – можно поиграться с этим. Charts мне очень понравился – визуализация данных, очень интуитивная.
Я насчитал порядка 230 статей, которые были опубликованы на эту тему – от Лесли Ламперта. Сейчас из памяти своей я вам их донесу какие-то части этих материалов.
Всё началось со статьи Лесли Ламперта, которая была написана в 1970-х годах. Как видите, до сих пор продолжаются какие-то исследования в этой теме. Сейчас Causal consistency переживает интерес в связи с развитием именно распределённых систем.
Какие ограничения есть? Это на самом деле один из главных моментов, потому ограничения, которые накладывает продакшн системы, сильно отличаются от ограничений, которые существуют в академических статьях. Часто они достаточно искусственны.
В общем, всё это накладывает ограничения.
Я сейчас расскажу о некоторых компонентах. Если рассматривать вообще Causal consistency, можно выделить блоки. Мы выбирали из работ, которые относятся к какому-то блоку: Dependency Tracking, выбор часов, как эти часы можно между собой синхронизировать, и как мы обеспечиваем безопасность – это примерный план того, о чём я буду говорить:
Зачем оно нужно? Для того чтобы, когда данные реплицируются – каждая запись, каждое изменение данных содержало в себе информацию о том, от каких изменений оно зависит. Самое первое и наивное изменение – это когда каждое сообщение, которое содержит в себе запись, содержит информацию о предыдущих сообщениях:
В данном примере номер в фигурных скобках – это номера записей. Иногда эти записи со значениями передаются даже целиком, иногда версии какие-то передаются. Суть заключается в том, что каждое изменение содержит в себе информацию о предыдущем (явно несёт это всё в себе).
Почему мы решили не пользоваться таким подходом (полный трекинг)? Очевидно, потому что этот подход непрактичен: любое изменение в социальной сети зависит от всех предыдущих изменений в этой соцсети, передавая, скажем, «Фейсбук» или «Вконтакте» в каждом обновлении. Тем не менее есть много исследований именно Full Dependency Tracking – это пресоциальные сети, для каких-то ситуаций это действительно работает.
Следующий – более ограниченный. Здесь тоже рассматривается передача информации, но только той, которая явно зависит. Что от чего зависит, как правило, определяет уже Application. Когда данные реплицируются, при запросе выдаются только ответы, когда предыдущие зависимости были удовлетворены, то есть показаны. В этом и суть того, как Causal consistency работает.
Она видит, что запись 5 зависит от записей 1, 2, 3, 4 – соответственно, она ждёт, прежде чем клиент получает доступ к изменениям, внесённым постановлением access’а Пенни, когда все предыдущие изменения уже прошли в базе данных.
Это тоже нас не устраивает, потому что всё равно информации слишком много, и это будет замедлять. Есть другой подход…
Они очень старые. Lamport Clock подразумевает то, что эти dependency сворачиваются в скалярную функцию, которая и называется Lamport Clock.
Скалярная функция – это некоторое абстрактное число. Часто его называют логическим временем. При каждом событии этот counter увеличивается. Counter, который в настоящий момент известен процессу, посылает каждое сообщение. Понятно, что процессы могут быть рассинхронизированны, у них может быть совершенно разное время. Тем не менее таким обменом сообщениями система как-то балансирует часы. Что происходит в этом случае?
Я разбил тот большой шард надвое, чтобы было понятно: Friends могут жить в одном ноде, который содержит кусок коллекции, а Feed – вообще в другом ноде, в котором содержится кусок этой коллекции. Понятно, как они могут попасть не в очередь? Сначала Feed скажет: «Реплицировался», а потом – Friends. Если система не обеспечивает каких-то гарантий, что Feed не будет показан, пока зависимости Friends в коллекции Friends тоже не будут доставлены, то у нас как раз возникнет ситуация, о которой я упомянул.
Вы видите, как увеличивается логически время counter на Feed’е:
Таким образом, основное свойство этого Lamport Clock и Causal consistency (объяснённого через Lamport Clock) заключается в следующем: если у нас есть события A и B, и событие B зависит от события A *, то из этого следует, что LogicalTime от Event A меньше, чем LogicalTime от Event B.
* Иногда ещё говорят, что A happened before B, то есть A случилось раньше B – это некое отношение, которое частично упорядочивает всё множество событий, которые вообще произошли.
В обратную сторону неверно. Это на самом деле один из основных минусов Lamport Clock – частичный порядок. Там есть понятие об одновременных событиях, то есть событий, в которых ни (A happened before B), ни (A happened before B). Примером может служить параллельное добавление Леонардом в друзья кого-нибудь ещё (даже не Леонардом, а Шелдоном, например).
Это и есть свойство, которым часто пользуются при работе Lamport-часами: смотрят именно на функцию и из этого делают вывод – может быть, эти события зависимы. Потому что в одну сторону это верно: если LogicalTime A меньше LogicalTime B, то B не может happened before A; а если больше, то может быть.
Логическое развитие часов Лэмпорта – это Векторные часы. Они отличаются тем, что каждый нод, который здесь есть, содержит в себе свои, отдельные часы, и они передаются как вектор.
В данном случае вы видите, что нулевой индекс вектора отвечает за Feed, а первый индекс вектора – за Friends (каждый из этих нодов). И вот они сейчас будут увеличиваться: нулевой индекс «Фида» увеличивается при записи – 1, 2, 3:
Чем Векторные часы лучше? Тем, что позволяют разобраться, какие события одновременны и когда они происходят на различных нодах. Это очень важно для системы шардирования, как «МонгоБД». Однако мы это не выбрали, хотя это и прекрасная штука, и замечательно работает, и нам подошла бы, наверное…
Если у нас 10 тысяч шардов, мы не можем передавать 10 тысяч компонентов, даже если сжимаем, ещё что-то придумываем – всё равно полезная нагрузка будет в разы меньше, чем объём всего этого вектора. Поэтому, скрипя сердцем и зубами, мы отказались от этого подхода и перешли к другому.
Я говорил, что будет рассказ о «Спаннере». Это крутая штука, прям XXI век: атомные часы, GPS-синхронизация.
Идея какая? «Спаннер» – это гугловская система, которая недавно даже стала доступна для людей (они приделали к ней SQL). Каждая транзакция там имеет некоторый time stamp. Поскольку время синхронизировано*, каждому событию можно назначить определённый times – у атомных часов есть время ожидания, после которого гарантированно «происходит» уже другое время.
Таким образом, просто записывая в БД и ожидая какой-то период времени, автоматически гарантируется Serializability события. У них самая сильная Consistency-модель, которую в принципе можно представить – она External Consistency.
* Это основная проблема часов Лэмпарта – они никогда не синхронны на распределённых системах. Они могут расходиться, даже при наличии NTP всё равно работают не очень хорошо. «Спаннер» имеет атомные часы и синхронизацию, кажется, то микросекунд.
Почему мы не выбрали? Мы не предполагаем, что у наших пользователей в наличии есть встроенные атомные часы. Когда они появятся, будучи встроенными в каждый лэптоп, будет какая-то суперкрутая GPS-синхронизация – тогда да… А пока что лучшее, что возможно – это «Амазон», Base Stations – для фанатиков… Поэтому мы использовали другие часы.
Это фактически то, что тикает в «МонгоБД» при обеспечении Causal consistency. Гибридные они в чём? Гибрид – это скалярное значение, но оно состоит из двух компонентов:
Это собственно, и всё. Есть такой подход: часть, которая отвечает за время, всё время синхронизируется с часами; каждый раз, когда происходит обновление, эта часть синхронизируется с часами и получается, что время всегда более-менее правильное, а increment позволяет различать события, которые произошли в один и тот же момент времени.
Почему это важно для «МонгоБД»? Потому что позволяет делать какие-то бэкап-ресторы на определённый момент времени, то есть событие индексируется временем. Это важно, когда нужны некоторые события; для БД события – это изменения в БД, которые произошли в определённые промежутки момент времени.
Самую главную причину я скажу только вам (пожалуйста, только никому не говорите)! Мы так сделали потому, что так выглядят упорядоченные, индексированные данные в MongoDB OpLog. OpLog – это структура данных, которая содержит в себе абсолютно все изменения в базе: они сначала попадают в OpLog, а потом уже применяются уже собственно к Storage в том случае, когда это реплицированная дата или шард.
Это была главная причина. Всё-таки существуют ещё и практические требования к разработке базы, а это значит, что должно быть просто – мало кода, как можно меньше сломанных вещей, которые нужно переписывать и тестировать. То, что у нас оплоги оказались проиндексированы гибридными часами, сильно помогло, и позволило сделать правильный выбор. Это действительно оправдало себя и как-то волшебно заработало, на первом же прототипе. Было очень круто!
Существует несколько способов синхронизации, описанных в научной литературе. Я говорю о синхронизации, когда у нас есть два различных шарда. Если одна реплика-сет – там никакой синхронизации не нужно: это «сингл-мастер»; у нас есть OpLog, в который все изменения попадают – в этом случае всё уже sequentially ordered в самом «Оплоге». Но если у нас есть два разных шарда, здесь синхронизация времени важна. Вот тут векторные часы больше помогли! Но у нас их нет.
Второй подходит – это «Хартбиты» (Heartbeats). Можно обмениваться некоторыми сигналами, которые происходит каждую единицу времени. Но «Хартбиты» – слишком медленные, мы не можем latency обеспечить нашему клиенту.
True time – конечно, прекрасная штука. Но, опять же, это, наверное, будущее… Хотя в «Атласе» уже можно сделать, уже есть быстрые «амазоновские» синхронизаторы времени. Но это не будет доступно для всех.
Gossiping – это когда все сообщения включают в себя время. Это примерно то, что мы и используем. Каждое сообщение между нодами, драйвер, роутер дата-ноды, абсолютно всё для «МонгоДБ» – это какие-то элементы, компоненты базы данных, которые содержат в себе часы, которые текут. У них везде есть значение гибридного времени, оно передаётся. 64 бита? Это позволяет, это можно.
Здесь я рассматриваю один реплика-сет, чтобы было чуть-чуть проще. Есть Primary и Secondary. Secondary делает репликацию и не всегда полностью синхронизирован с Primary.
Происходит вставка (insert) в «Праймери» с некоторым значением времени. Этот insert увеличивает внутренний каунтер на 11, если это максимально. Или он будет проверять значения часов и синхронизируется по часам, если значения часов больше. Это позволяет упорядочить по времени.
После того как он делает запись, происходит важный момент. Часы в «МонгоДБ» и инкрементируются только в случае записи в «Оплог». Это и является событием, которое меняет состояние системы. Абсолютно во всех классических статьях событием считается попадание сообщения в нод: сообщение пришло – значит, система изменила своё состояние.
Это связано с тем, что при исследовании не совсем можно понять, как это сообщение будет интерпретировано. Мы точно знаем, что если оно не отражено в «Оплоге», то оно никак не будет интерпретировано, и изменением состояния системы является только запись в «Оплог». Это нам всё упрощает: и модель упрощает, и позволяет вести упорядочивание в рамках одного реплика-сета, и много чего другого полезного.
Возвращается значение, которое уже записано в «Оплог» – мы знаем, что в «Оплоге» уже лежит это значение, и его время – 12. Теперь, скажем, начинается чтение с другого нода (Secondary), и он передаёт уже afterClusterTime в самом сообщении. Он говорит: «Мне нужно всё, что произошло как минимум после 12 или во время двенадцати» (см. рис. выше).
Это то, что называется Causal a consistent (CAT). Есть такое понятие в теории, что это некоторые срез времени, которое консистентно само по себе. В данном случае можно сказать, что это состояние системы, которое наблюдалось в момент времени 12.
Сейчас здесь пока ничего нет, потому что это как бы имитирует ситуацию, когда нужно, чтобы Secondary реплицировал данные с Primary. Он ждёт… И вот данные пришли – возвращает назад эти значения.
Вот так примерно всё и работает. Почти что.
Что значит «почти что»? Давайте предположим, что есть некоторый человек, который прочитал и понял, как это всё работает. Понял, что каждый раз происходит ClusterTime, он обновляет внутренние логические часы, и потом следующая запись увеличивает на единицу. Эта функция занимает 20 строк. Допустим, этот человек передаёт максимально большое 64-битное число, минус единица.
Почему «минус единица»? Потому что внутренние часы подставятся в это значение (очевидно, это самое большое возможное и больше текущего времени), потом произойдёт запись в «Оплог», и часы инкрементируются ещё на единицу – и уже будет вообще максимальное значение (там просто все единицы, дальше некуда, unsaint int’ы).
Понятно, что после этого система становится абсолютно недоступна ни для чего. Её можно только выгрузить, почистить – много ручной работы. Полный availability:
Причём, если это реплицируется ещё куда-то, то просто ложится весь кластер. Абсолютно неприемлемая ситуация, которую любой человек может организовать очень быстро и просто! Поэтому мы рассматривали этот момент как один из самых важных. Как его предотвратить?
Так оно передаётся в сообщении (до синего текста). Но мы стали ещё и генерировать подпись (синий текст):
Подпись генерируется ключом, который хранится внутри базы данных, внутри защищённого периметра; сам генерируется, обновляется (пользователи этого ничего не видят). Генерируется hash, и каждое сообщение при создании подписывается, а при получении – валидируется.
Наверное, возникает вопрос у людей: «Насколько это всё замедляет?» Я же говорил, что должно быстро работать, особенно при отсутствии этой фичи.
Что значит пользоваться Causal consistency в данном случае? Это показывать afterClusterTime-параметр. А без этого он просто будет передавать значения в любом случае. Gossiping, начиная с версии 3.6, работает всегда.
Если мы оставим постоянное генерирование подписей, то это будет замедлять систему даже при отсутствии фичи, что не соответствует нашим подходам и требованиям. И что мы сделали?
Достаточно простая вещь, но трюк интересный – поделюсь, может, кому-то будет интересно.
У нас есть хэш, в котором хранятся подписанные данные. Все данные идут через кэш. Кэш подписывает не конкретно время, а Range. Когда приходит некоторое значение, мы генерируем Range, маскируем последние 16 бит, и это значение мы подписываем:
Получая такую подпись, мы ускоряем систему (условно) в 65 тысяч раз. Оно прекрасно работает: когда поставили эксперименты – там реально в 10 тысяч раз сократилось время, когда у нас последовательный апдейт. Понятно, что когда они в разнобой, этого не получается. Но в большинстве практических случаев это работает. Комбинация подписи Range вместе с подписью позволила решить проблему безопасности.
Уроки, которые мы из этого извлекли:
На этом закончу. Спасибо!
Вопрос из зала (далее – В): – Спасибо, Михаил за доклад! Тема про время интересная. Вы используете Gossiping. Сказали, что у всех есть своё время, все знают своё локальное время. Я так понял, что у нас есть драйвер – клиентов с драйверами может быть много, query-planner’ов тоже, шардов тоже много… А к чему скатывается система, если у нас вдруг возникнет расхождение: кто-то решит, что он на минуту впереди, кто-то — на минуту позади? Где мы окажемся?
МТ: – Отличный вопрос на самом деле! Я как раз про шарды хотел сказать. Если я правильно понимаю вопрос, у нас такая ситуация: есть шард 1 и шард 2, чтение происходит с этих двух шардов – у них расхождение, они между собой не взаимодействуют, потому что время, которое они знают – разное, особенно время, которое у них существует в оплогах.
Допустим, шард 1 сделал миллион записей, шард 2 – вообще ничего, а запрос пришёл на два шарда. И у первого есть afterClusterTime более миллиона. В такой ситуации, как я объяснил, шард 2 вообще никогда не ответит.
В: – Я хотел узнать, как они синхронизируются и выберут одно логическое время?
МТ: – Очень просто синхронизируются. Шард, когда к нему приходит afterClusterTime, и он не находит времени в «Оплоге» – инициирует no approved. То есть он руками поднимает своё время до этого значения. Это означает, что у него нет событий, отвечающих этому запросу. Он создаёт это событие искусственно и становится таким образом Causal Consistent.
В: – А если к нему после этого ещё приедут какие-нибудь события, которые в сети где-то затерялись?
МТ: – Шард так устроен, что они уже не приедут, поскольку это single master. Если он уже записал, то они уже не приедут, а будут после. Не может так получиться, что где-то что-то застряло, потом он сделает no write, а потом эти события приехали – и нарушилась Causal consistency. Когда он делает no write, они все должны приехать дальше (он их подождёт).
В: – У меня есть несколько вопросов относительно очередей. Causal consistency предполагает, что есть определённая очередь действий, которые нужно выполнить. Что произойдёт, если у нас один пакет пропадает? Вот пошёл 10-й, 11… 12-й пропал, а все остальные ждут, когда он исполнится. И у нас вдруг машина умерла, мы ничего не можем сделать. Есть ли максимальная длина очереди, которая копится, прежде чем выполняется? Какой fatal failure происходит при потере какого-либо одного состояния? Тем более, если мы записываем, что есть какое-то состояние предыдущее, то от него же мы должны как-то отталкиваться? А от него не оттолкнулись!
МТ: – Тоже прекрасный вопрос! Что мы делаем? В MongoDB есть понятие кворумных записей, кворумного чтения. В каких случаях сообщение может пропасть? Когда запись некворумная или когда чтение не кворумное (тоже может пристать какой-то garbage).
Относительно Causal consistency выполнили большую экспериментальную проверку, результатом которой стало то, что в случае, когда записи и чтение – некворумные, возникают нарушения Causal consistency. Ровно то, что вы говорите!
Наш совет: использовать хотя бы кворумное чтение при использовании Causal consistency. В этом случае пропадать ничего не будет, даже если кворумная запись пропадёт… Это ортогональная ситуация: если пользователь не хочет чтобы пропали данные, нужно использовать кворумную запись. Causal consistency не даёт гарантии durability. Гарантию durability даёт replication и machinery, связанная с replication.
В: – Когда мы создаём instance, который у нас шардинг выполняет (не master, а slave соответственно), он опирается на unix-время собственной машины или на время «мастера»; синхронизируется в первый раз или периодически?
МТ: – Сейчас проясню. Шард (т. е. горизонтальная партиция) – там всегда есть Primary. А в шарде может быть «мастер» и могут быть реплики. Но шард всегда поддерживает запись, потому что он должен поддерживать некоторый домен (в шарде стоит Primary).
В: – То есть всё зависит сугубо от «мастера»? Всегда используется «мастер»-время?
МТ: – Да. Можно образно сказать: часы тикают, когда происходит запись в «мастер», в «Оплог».
В: – У нас есть клиент, который коннектится, и ему не нужно знать про время ничего?
МТ: – Вообще ничего не нужно знать! Если говорить о том, как это работает на клиенте: у клиента, когда он хочет пользоваться Causal consistency, ему нужно открыть сессию. Сейчас там всё: и транзакции в сессии, и retrieve a rights… Сессия – это упорядочение логических событий, происходящих с клиентом.
Если он открывает эту сессию и там говорит, что хочет Causal consistency (если по умолчанию сессия поддерживает Causal consistency), всё автоматически работает. Драйвер запоминает это время и увеличивает его, когда получает новое сообщение. Он запоминает, какой ответ вернуло предыдущее с сервера, который вернул данные. Следующий запрос будет содержать afterCluster («time больше этого»).
Клиенту не нужно знать ровным счётом ничего! Это абсолютно для него непрозрачно. Если люди используют эти фичи, что позволяет сделать? Во-первых, можно безопасно читать secondaries: можно писать на Primary, а читать с географически реплицированных secondaries и быть уверенным, что это работает. При этом сессии, которые записал на Primary, можно передать даже на Secondary, т. е. можно использовать не одну сессию, а несколько.
В: – С темой Eventual consistency сильно связан новый пласт Compute science –типы данных CRDT (Conflict-free Replicated Data Types). Рассматривали ли вы интеграцию этих типов данных в базу и что можете сказать об этом?
МТ: – Хороший вопрос! CRDT имеет смысл для конфликтов при записи: в MongoDB – single master.
В: – У меня вопрос от девопсов. В настоящем мире встречаются такие иезуитские ситуации, когда византийский Failure происходит, и злые люди внутри защищённого периметра начинают втыкаться в протокол, специальным образом крафтовые пакеты присылать?
МТ: – Злые люди внутри периметра – всё равно что троянский конь! Злые люди внутри периметра могут сделать много плохих вещей.
В: – Понятное дело, что оставлять в сервере, грубо говоря, дырочку, через которую можно зоопарк слонов просунуть и обвалить весь кластер навсегда… Потребуется время для ручного восстановления… Это, мягко говоря, неправильно. С другой стороны, любопытно вот что: в реальной жизни, в практике встречаются такие ситуации, когда натурально подобные внутренние атаки происходят?
МТ: – Поскольку я нечасто сталкиваюсь с security breach’ами в реальной жизни, не могу сказать – может, они и происходят. Но если говорить о девелоперской философии, то мы считаем так: у нас есть периметр, который обеспечивает ребят, которые делают security – это замок, стена; а внутри периметра можно делать всё, что угодно. Понятно, что есть пользователи с возможностью только посмотреть, а есть пользователи с возможностью стереть каталог.
В зависимости от прав, damage, который пользователи могут сделать, может быть мышью, а может быть и слоном. Понятно, что пользователь с полными правами может сделать вообще всё что угодно. Пользователь с не широкими правами вреда может причинить существенно меньше. В частности, он не может сломать систему.
В: – В защищённом периметре кто-то полез формировать неожиданные протоколы для сервера, чтобы раком поставить сервер, а если повезёт, то и весь кластер… Бывает ли настолько «хорошо»?
МТ: – Ни разу не слышал о таких вещах. То, что таким образом можно завалить сервер – это не секрет. Завалить внутри, находясь с протокола, будучи авторизованным пользователем, который может записать в сообщение что-то такое… На самом деле нельзя, потому что всё равно он будет верифицироваться. Есть возможность отключить эту аутентификацию для пользователей, которые не хотят – это тогда их проблемы; они, грубо говоря, сами разрушили стены и можно запихнуть туда слона, который растопчет… А вообще, можно одеться ремонтником, прийти и вытащить!
В: – Спасибо за доклад. Сергей («Яндекс»). В «Монге» есть константа, которая лимитирует количество голосующих членов в Replica Set’е, и эта константа равна 7 (семи). Почему это константа? Почему это не параметр какой-то?
МТ: – Replica Set у нас бывает и по 40 нодов. Там всегда majority. Я не знаю какая версия…
В: – В Replica Set’е можно не голосующих членов запускать, но голосующих – максимум 7. Как в этом случае переживать выключение, если у нас Replica Set стянут на 3 дата-центра? Один дата-центр может запросто выключиться, и ещё одна машинка выпасть.
МТ: – Это уже немного за пределами доклада. Это общий вопрос. Может, потом его могу рассказать.
Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).
Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?
Подробности и билеты по ссылке. HighLoad++ Siberia 2019. Зал «Красноярск». 25 июня, 12:00. Тезисы и презентация.
Бывает, что практические требования конфликтуют с теорией, где не учтены важные для коммерческого продукта аспекты. В этом докладе представлен процесс выбора и комбинирования различных подходов к созданию компонентов Causal consistency на основе академических исследований исходя из требований коммерческого продукта. Слушатели узнают о существующих теоретических подходах к logical clocks, dependency tracking, system security, clock synchronization, и почему MongoDB остановились на тех или иных решениях.
Михаил Тюленев (далее – МТ): – Я буду рассказывать о Causal consistency – это фича, над которой мы работали в MongoDB. Я работаю в группе распределённых систем, мы её сделали примерно два года назад.
В процессе пришлось ознакомиться с большим количеством академического Research, потому что эта фича достаточно хорошо изучена. Выяснилось, что ни одна статья не вписывается в то, что требуется в продакшне, базе данных в виду весьма специфических требований, которые есть, наверное, в любом production applications.
Я буду рассказывать о том, как мы, являясь потребителем академического Research, готовим из него что-то такое, что мы потом можем преподнести нашим пользователям в качестве готового блюда, которым удобно, безопасно пользоваться.
Причинная согласованность (Causal consistency). Определимся с понятиями
Для начала я хочу в общих чертах сказать, что же такое Causal consistency. Есть два персонажа – Леонард и Пенни (сериал «Теория большого взрыва»):
Предположим, что Пенни в Европе, а Леонард хочет сделать для неё какой-нибудь сюрприз, тусовку. И он ничего лучше не придумывает, чем выкинуть её из френд-листа, послать всем друзьям апдейт на feed: «Давайте порадуем Пенни!» (она в Европе, пока спит, не видит этого всего и не может увидеть, потому что она не там). В конечном моменте удаляет этот пост, стирает из «Фида» и восстанавливает access, чтобы она ничего не заметила и скандала не было.
Это всё прекрасно, но давайте предположим, что система распределённая, и события пошли не немного не так. Может, например, случится, что ограничение access Пенни произошло после того, как появился этот пост, если события не связаны между собой причинно-следственными связями. Собственно, это – пример того, когда требуется наличие Causal consistency для того, чтобы выполнить бизнес-функцию (в данном случае).
На самом деле это достаточно нетривиальные свойства базы данных – очень мало кто их поддерживает. Давайте перейдём к моделям.
Модели согласованности (Consistency Models)
Что такое вообще модель консистенции в базах данных? Это некоторые гарантии, которые распределённая система даёт по поводу того, какие данные и в какой последовательности клиент может получить.
В принципе все модели консистенции сводятся к тому, насколько распределённая система похожа на систему, которая работает, например, на одном nod’е на лэптопе. И вот насколько система, которая работает на тысячах геораспределённых «Нодов», похожа на лэптоп, в котором все эти свойства выполняются в принципе автоматически.
Поэтому модели консистенции только к распределённым системам и применяются. Все системы, которые раньше существовали и работали на одном вертикальном масштабировании, таких проблем не испытывали. Там был один Buffer Cache, и из него всё всегда вычитывалось.
Модель Strong
Собственно, самая первая модель – это Strong (или линия rise ability, как её часто называют). Это модель консистенции, которая гарантирует, что каждое изменение, как только получается подтверждение о том, что оно произошло, становится видно всем пользователям системы.
Это создаёт глобальный порядок всех событий в БД. Это очень сильное свойство консистенции, и оно вообще очень дорогое. Тем не менее оно очень хорошо поддерживается. Оно просто очень дорогое и медленное – им просто редко пользуются. Это называется rise ability.
Есть ещё одно, более сильное свойство, которое поддерживается в «Спаннере» – называется External Consistency. Мы о нём поговорим чуть позже.
Causal
Следующее – это Causal, как раз то, о чём я говорил. Между Strong и Causal существует ещё несколько подуровней, о которых я не буду говорить, но они все сводятся к Causal. Это важная модель, потому что она – самая сильная из всех моделей, самая сильная консистенция при наличии сети или partitions.
Causals – это собственно ситуация, при которой события связаны причинно-следственной связью. Очень часто их воспринимают как Read your on rights с точки зрения клиента. Если клиент наблюдал какие-то значения, он не может увидеть значения, которые были в прошлом. Он уже начинает видеть префиксные чтения. Это всё сводится к одному и тому же.
Causals как модель консистенции – частичное упорядочивание событий на сервере, при котором события со всех клиентов наблюдаются в одной и той же последовательности. В данном случае – Леонард и Пенни.
Eventual
Третья модель – это Eventual Consistency. Это то, что поддерживает абсолютно все распределённые системы, минимальная модель, которая вообще имеет смысл. Она означает следующее: когда у нас происходят некоторые изменения в данных, они в какой-то момент становятся консистентными.
В такой момент она ничего не говорит, иначе она превратилась бы в External Consistency – была бы совершенно другая история. Тем не менее это очень популярная модель, самая распространённая. По умолчанию все пользователи распределённых систем используют именно Eventual Consistency.
Я хочу привести некоторые сравнительные примеры:
Что эти стрелочки означают?
- Latency. При увеличении силы консистенции она становится больше по понятным причинам: нужно сделать больше записей, получить подтверждение от всех хостов и нодов, которые участвуют в кластере, что данные там уже есть. Соответственно в Eventual Consistency самый быстрый ответ, потому что там, как правило, можно даже в memory закоммитить и этого будет в принципе достаточно.
- Availability. Если это понимать как возможность системы ответить при наличии разрывов сети, partitions, или каких-то отказов – отказоустойчивость возрастает при уменьшении модели консистенции, поскольку нам достаточно того, чтобы один хост жил и при этом выдавал какие-то данные. Eventual Consistency вообще ничего не гарантирует по поводу данных – это может быть всё, что угодно.
- Anomalies. При этом, конечно, возрастает количество аномалий. В Strong Consistency их вообще почти что не должно быть, а Eventual Consistency они могут быть какие угодно. Возникает вопрос: почему же люди выбирают Eventual Consistency, если она содержит аномалии? Ответ в том заключается, что Eventual Consistency-модели применимы, а аномалии существуют, например, в короткий промежуток времени; существует возможность использовать мастер для чтения и более-менее читать консистентные данные; часто есть возможность использовать сильные модели консистенции. Практически это работает, и часто количество аномалий ограничено по времени.
Теорема CAP
Когда вы видите слова consistency, availability – что вам приходит на ум? Правильно – CAP theorem! Я сейчас хочу развеять миф… Это не я – есть Мартин Клеппман, который написал прекрасную статью, прекрасную книжку.
Теорема CAP – это принцип, сформулированный в 2000-х годах, о том, что Consistency, Availability, Partitions: take any two, и нельзя выбрать три. Это был некий принцип. Он был доказан как теорема несколько лет спустя, это сделали Джилберт и Линч. Затем это стало использоваться, как мантра – системы стали делиться на CA, CP, AP и так далее.
Эта теорема была доказана на самом деле вот для каких случаев… Во-первых, Availability рассматривалась не как непрерывное значение от нуля до сотни (0 – система «мёртвая», 100 – отвечает быстро; мы её так привыкли рассматривать), а как свойство алгоритма, которое гарантирует, что при всех его executions он возвращает данные.
О времени ответа там вообще нет ни слова! Есть алгоритм, который возвращает данные через 100 лет – совершенно прекрасный available-алгоритм, которые является частью теоремы CAP.
Второе: доказывалась теорема для изменений в значениях одного и того же ключа, притом что эти изменения – линия resizable. Это означает то, что на самом деле они практически не используются, потому что модели другие Eventual Consistency, Strong Consistency (может быть).
К чему это всё? К тому, что теорема CAP именно в той форме, в которой она доказана, практически не применима, редко используется. В теоретической форме она каким-то образом всё ограничивает. Получается некий принцип, который интуитивно верен, но никак, в общем-то, не доказан.
Causal consistency – самая сильная модель
То, что сейчас происходит – можно получить все три вещи: Consistency, Availability получить с помощью Partitions. В частности Causal consistency – самая сильная модель консистенции, которая при наличии Partitions (разрывов в сети) всё равно работает. Поэтому она и представляет такой большой интерес, поэтому мы ею и занялись.
Она, во-первых, упрощает труд разработчиков приложений. В частности, наличие большой поддержки со стороны сервера: когда все записи, которые происходят внутри о дного клиента, гарантировано придут в такой последовательности на другом клиенте. Во-вторых, она выдерживает partitions.
Внутренняя кухня MongoDB
Помня о том, что ланч, мы перемещаемся на кухню. Я расскажу про модель системы, а именно – что такое MongoDB для тех, кто впервые слышит о такой базе данных.
MongoDB (далее – «МонгоБД») – это распределённая система, которая поддерживает горизонтальное масштабирование, то есть шардинг; и внутри каждого шарда она также поддерживает избыточность данных, то есть репликацию.
Шардинг в «МонгоБД» (не реляционная БД) выполняет автоматическую балансировку, то есть каждая коллекция документов (или «таблица» в терминах реляционных данных) на кусочки, и уже сервер автоматически двигает их между шардами.
Query Router, который распределяет запросы, для клиента является некоторым клиентом, через который он работает. Он уже знает, где и какие данные находятся, направляет все запросы к правильному шарду.
Ещё один важный момент: MongoDB – это single master. Есть один Primary – он может брать записи, поддерживающие те ключи, которые он в себе содержит. Нельзя сделать Multi-master write.
Мы сделали релиз 4.2 – там появились новые интересные вещи. В частности, вставили Lucene –поиск – именно executable java прямо в «Монго», и там стало возможным выполнять поиск через Lucene, такой же, как в «Эластике».
И сделали новый продукт – Charts, он тоже доступен на «Атласе» (собственный Cloud «Монго»). У них есть Free Tier – можно поиграться с этим. Charts мне очень понравился – визуализация данных, очень интуитивная.
Ингредиенты Causal consistency
Я насчитал порядка 230 статей, которые были опубликованы на эту тему – от Лесли Ламперта. Сейчас из памяти своей я вам их донесу какие-то части этих материалов.
Всё началось со статьи Лесли Ламперта, которая была написана в 1970-х годах. Как видите, до сих пор продолжаются какие-то исследования в этой теме. Сейчас Causal consistency переживает интерес в связи с развитием именно распределённых систем.
Ограничения
Какие ограничения есть? Это на самом деле один из главных моментов, потому ограничения, которые накладывает продакшн системы, сильно отличаются от ограничений, которые существуют в академических статьях. Часто они достаточно искусственны.
- Во-первых, «МонгоДБ» – это single master, как я уже говорил (это сильно упрощает).
- Мы считаем, что порядка 10 тысяч шардов система должна поддерживать. Мы не можем принимать какие-то архитектурные решения, которые будут явно ограничивать это значение.
- Есть у нас облако, но мы предполагаем, что у человека должна оставаться возможность, когда он скачивает binary, запускает у себя на лэптопе, и всё прекрасно работает.
- Мы предполагаем то, что в Research редко используется: внешние клиенты могут делать что угодно. «МонгоДБ» – это опенсорс. Соответственно, клиенты могут быть такие умные, злые – могут хотеть всё сломать. Мы предполагаем, что византийские Фейлоры могут происходить.
- Для внешних клиентов, которые за пределами периметра – важное ограничение: если эта фича выключена, то никаких performance degradation не должно наблюдаться.
- Ещё один момент – вообще антиакадемический: совместимость предыдущих версий и будущих. Старые драйверы должны поддерживать новые апдейты, и БД должна поддерживать старые драйверы.
В общем, всё это накладывает ограничения.
Компоненты Causal consistency
Я сейчас расскажу о некоторых компонентах. Если рассматривать вообще Causal consistency, можно выделить блоки. Мы выбирали из работ, которые относятся к какому-то блоку: Dependency Tracking, выбор часов, как эти часы можно между собой синхронизировать, и как мы обеспечиваем безопасность – это примерный план того, о чём я буду говорить:
Полное отслеживание зависимостей (Full Dependency Tracking)
Зачем оно нужно? Для того чтобы, когда данные реплицируются – каждая запись, каждое изменение данных содержало в себе информацию о том, от каких изменений оно зависит. Самое первое и наивное изменение – это когда каждое сообщение, которое содержит в себе запись, содержит информацию о предыдущих сообщениях:
В данном примере номер в фигурных скобках – это номера записей. Иногда эти записи со значениями передаются даже целиком, иногда версии какие-то передаются. Суть заключается в том, что каждое изменение содержит в себе информацию о предыдущем (явно несёт это всё в себе).
Почему мы решили не пользоваться таким подходом (полный трекинг)? Очевидно, потому что этот подход непрактичен: любое изменение в социальной сети зависит от всех предыдущих изменений в этой соцсети, передавая, скажем, «Фейсбук» или «Вконтакте» в каждом обновлении. Тем не менее есть много исследований именно Full Dependency Tracking – это пресоциальные сети, для каких-то ситуаций это действительно работает.
Явное отслеживание зависимостей (Explicit Dependency Tracking)
Следующий – более ограниченный. Здесь тоже рассматривается передача информации, но только той, которая явно зависит. Что от чего зависит, как правило, определяет уже Application. Когда данные реплицируются, при запросе выдаются только ответы, когда предыдущие зависимости были удовлетворены, то есть показаны. В этом и суть того, как Causal consistency работает.
Она видит, что запись 5 зависит от записей 1, 2, 3, 4 – соответственно, она ждёт, прежде чем клиент получает доступ к изменениям, внесённым постановлением access’а Пенни, когда все предыдущие изменения уже прошли в базе данных.
Это тоже нас не устраивает, потому что всё равно информации слишком много, и это будет замедлять. Есть другой подход…
Часы Лэмпорта (Lamport Clock)
Они очень старые. Lamport Clock подразумевает то, что эти dependency сворачиваются в скалярную функцию, которая и называется Lamport Clock.
Скалярная функция – это некоторое абстрактное число. Часто его называют логическим временем. При каждом событии этот counter увеличивается. Counter, который в настоящий момент известен процессу, посылает каждое сообщение. Понятно, что процессы могут быть рассинхронизированны, у них может быть совершенно разное время. Тем не менее таким обменом сообщениями система как-то балансирует часы. Что происходит в этом случае?
Я разбил тот большой шард надвое, чтобы было понятно: Friends могут жить в одном ноде, который содержит кусок коллекции, а Feed – вообще в другом ноде, в котором содержится кусок этой коллекции. Понятно, как они могут попасть не в очередь? Сначала Feed скажет: «Реплицировался», а потом – Friends. Если система не обеспечивает каких-то гарантий, что Feed не будет показан, пока зависимости Friends в коллекции Friends тоже не будут доставлены, то у нас как раз возникнет ситуация, о которой я упомянул.
Вы видите, как увеличивается логически время counter на Feed’е:
Таким образом, основное свойство этого Lamport Clock и Causal consistency (объяснённого через Lamport Clock) заключается в следующем: если у нас есть события A и B, и событие B зависит от события A *, то из этого следует, что LogicalTime от Event A меньше, чем LogicalTime от Event B.
* Иногда ещё говорят, что A happened before B, то есть A случилось раньше B – это некое отношение, которое частично упорядочивает всё множество событий, которые вообще произошли.
В обратную сторону неверно. Это на самом деле один из основных минусов Lamport Clock – частичный порядок. Там есть понятие об одновременных событиях, то есть событий, в которых ни (A happened before B), ни (A happened before B). Примером может служить параллельное добавление Леонардом в друзья кого-нибудь ещё (даже не Леонардом, а Шелдоном, например).
Это и есть свойство, которым часто пользуются при работе Lamport-часами: смотрят именно на функцию и из этого делают вывод – может быть, эти события зависимы. Потому что в одну сторону это верно: если LogicalTime A меньше LogicalTime B, то B не может happened before A; а если больше, то может быть.
Векторные часы (Vector Clock)
Логическое развитие часов Лэмпорта – это Векторные часы. Они отличаются тем, что каждый нод, который здесь есть, содержит в себе свои, отдельные часы, и они передаются как вектор.
В данном случае вы видите, что нулевой индекс вектора отвечает за Feed, а первый индекс вектора – за Friends (каждый из этих нодов). И вот они сейчас будут увеличиваться: нулевой индекс «Фида» увеличивается при записи – 1, 2, 3:
Чем Векторные часы лучше? Тем, что позволяют разобраться, какие события одновременны и когда они происходят на различных нодах. Это очень важно для системы шардирования, как «МонгоБД». Однако мы это не выбрали, хотя это и прекрасная штука, и замечательно работает, и нам подошла бы, наверное…
Если у нас 10 тысяч шардов, мы не можем передавать 10 тысяч компонентов, даже если сжимаем, ещё что-то придумываем – всё равно полезная нагрузка будет в разы меньше, чем объём всего этого вектора. Поэтому, скрипя сердцем и зубами, мы отказались от этого подхода и перешли к другому.
Spanner TrueTime. Атомные часы
Я говорил, что будет рассказ о «Спаннере». Это крутая штука, прям XXI век: атомные часы, GPS-синхронизация.
Идея какая? «Спаннер» – это гугловская система, которая недавно даже стала доступна для людей (они приделали к ней SQL). Каждая транзакция там имеет некоторый time stamp. Поскольку время синхронизировано*, каждому событию можно назначить определённый times – у атомных часов есть время ожидания, после которого гарантированно «происходит» уже другое время.
Таким образом, просто записывая в БД и ожидая какой-то период времени, автоматически гарантируется Serializability события. У них самая сильная Consistency-модель, которую в принципе можно представить – она External Consistency.
* Это основная проблема часов Лэмпарта – они никогда не синхронны на распределённых системах. Они могут расходиться, даже при наличии NTP всё равно работают не очень хорошо. «Спаннер» имеет атомные часы и синхронизацию, кажется, то микросекунд.
Почему мы не выбрали? Мы не предполагаем, что у наших пользователей в наличии есть встроенные атомные часы. Когда они появятся, будучи встроенными в каждый лэптоп, будет какая-то суперкрутая GPS-синхронизация – тогда да… А пока что лучшее, что возможно – это «Амазон», Base Stations – для фанатиков… Поэтому мы использовали другие часы.
Гибридные часы (Hybrid Clock)
Это фактически то, что тикает в «МонгоБД» при обеспечении Causal consistency. Гибридные они в чём? Гибрид – это скалярное значение, но оно состоит из двух компонентов:
- Первое – это unix’вая эпоха (сколько секунд прошло с «начала компьютерного мира»).
- Второе – некоторый инкремент, тоже 32-битный unsigned int.
Это собственно, и всё. Есть такой подход: часть, которая отвечает за время, всё время синхронизируется с часами; каждый раз, когда происходит обновление, эта часть синхронизируется с часами и получается, что время всегда более-менее правильное, а increment позволяет различать события, которые произошли в один и тот же момент времени.
Почему это важно для «МонгоБД»? Потому что позволяет делать какие-то бэкап-ресторы на определённый момент времени, то есть событие индексируется временем. Это важно, когда нужны некоторые события; для БД события – это изменения в БД, которые произошли в определённые промежутки момент времени.
Самую главную причину я скажу только вам (пожалуйста, только никому не говорите)! Мы так сделали потому, что так выглядят упорядоченные, индексированные данные в MongoDB OpLog. OpLog – это структура данных, которая содержит в себе абсолютно все изменения в базе: они сначала попадают в OpLog, а потом уже применяются уже собственно к Storage в том случае, когда это реплицированная дата или шард.
Это была главная причина. Всё-таки существуют ещё и практические требования к разработке базы, а это значит, что должно быть просто – мало кода, как можно меньше сломанных вещей, которые нужно переписывать и тестировать. То, что у нас оплоги оказались проиндексированы гибридными часами, сильно помогло, и позволило сделать правильный выбор. Это действительно оправдало себя и как-то волшебно заработало, на первом же прототипе. Было очень круто!
Синхронизация часов
Существует несколько способов синхронизации, описанных в научной литературе. Я говорю о синхронизации, когда у нас есть два различных шарда. Если одна реплика-сет – там никакой синхронизации не нужно: это «сингл-мастер»; у нас есть OpLog, в который все изменения попадают – в этом случае всё уже sequentially ordered в самом «Оплоге». Но если у нас есть два разных шарда, здесь синхронизация времени важна. Вот тут векторные часы больше помогли! Но у нас их нет.
Второй подходит – это «Хартбиты» (Heartbeats). Можно обмениваться некоторыми сигналами, которые происходит каждую единицу времени. Но «Хартбиты» – слишком медленные, мы не можем latency обеспечить нашему клиенту.
True time – конечно, прекрасная штука. Но, опять же, это, наверное, будущее… Хотя в «Атласе» уже можно сделать, уже есть быстрые «амазоновские» синхронизаторы времени. Но это не будет доступно для всех.
Gossiping – это когда все сообщения включают в себя время. Это примерно то, что мы и используем. Каждое сообщение между нодами, драйвер, роутер дата-ноды, абсолютно всё для «МонгоДБ» – это какие-то элементы, компоненты базы данных, которые содержат в себе часы, которые текут. У них везде есть значение гибридного времени, оно передаётся. 64 бита? Это позволяет, это можно.
Как всё это работает вместе?
Здесь я рассматриваю один реплика-сет, чтобы было чуть-чуть проще. Есть Primary и Secondary. Secondary делает репликацию и не всегда полностью синхронизирован с Primary.
Происходит вставка (insert) в «Праймери» с некоторым значением времени. Этот insert увеличивает внутренний каунтер на 11, если это максимально. Или он будет проверять значения часов и синхронизируется по часам, если значения часов больше. Это позволяет упорядочить по времени.
После того как он делает запись, происходит важный момент. Часы в «МонгоДБ» и инкрементируются только в случае записи в «Оплог». Это и является событием, которое меняет состояние системы. Абсолютно во всех классических статьях событием считается попадание сообщения в нод: сообщение пришло – значит, система изменила своё состояние.
Это связано с тем, что при исследовании не совсем можно понять, как это сообщение будет интерпретировано. Мы точно знаем, что если оно не отражено в «Оплоге», то оно никак не будет интерпретировано, и изменением состояния системы является только запись в «Оплог». Это нам всё упрощает: и модель упрощает, и позволяет вести упорядочивание в рамках одного реплика-сета, и много чего другого полезного.
Возвращается значение, которое уже записано в «Оплог» – мы знаем, что в «Оплоге» уже лежит это значение, и его время – 12. Теперь, скажем, начинается чтение с другого нода (Secondary), и он передаёт уже afterClusterTime в самом сообщении. Он говорит: «Мне нужно всё, что произошло как минимум после 12 или во время двенадцати» (см. рис. выше).
Это то, что называется Causal a consistent (CAT). Есть такое понятие в теории, что это некоторые срез времени, которое консистентно само по себе. В данном случае можно сказать, что это состояние системы, которое наблюдалось в момент времени 12.
Сейчас здесь пока ничего нет, потому что это как бы имитирует ситуацию, когда нужно, чтобы Secondary реплицировал данные с Primary. Он ждёт… И вот данные пришли – возвращает назад эти значения.
Вот так примерно всё и работает. Почти что.
Что значит «почти что»? Давайте предположим, что есть некоторый человек, который прочитал и понял, как это всё работает. Понял, что каждый раз происходит ClusterTime, он обновляет внутренние логические часы, и потом следующая запись увеличивает на единицу. Эта функция занимает 20 строк. Допустим, этот человек передаёт максимально большое 64-битное число, минус единица.
Почему «минус единица»? Потому что внутренние часы подставятся в это значение (очевидно, это самое большое возможное и больше текущего времени), потом произойдёт запись в «Оплог», и часы инкрементируются ещё на единицу – и уже будет вообще максимальное значение (там просто все единицы, дальше некуда, unsaint int’ы).
Понятно, что после этого система становится абсолютно недоступна ни для чего. Её можно только выгрузить, почистить – много ручной работы. Полный availability:
Причём, если это реплицируется ещё куда-то, то просто ложится весь кластер. Абсолютно неприемлемая ситуация, которую любой человек может организовать очень быстро и просто! Поэтому мы рассматривали этот момент как один из самых важных. Как его предотвратить?
Наш путь – подписывать clusterTime
Так оно передаётся в сообщении (до синего текста). Но мы стали ещё и генерировать подпись (синий текст):
Подпись генерируется ключом, который хранится внутри базы данных, внутри защищённого периметра; сам генерируется, обновляется (пользователи этого ничего не видят). Генерируется hash, и каждое сообщение при создании подписывается, а при получении – валидируется.
Наверное, возникает вопрос у людей: «Насколько это всё замедляет?» Я же говорил, что должно быстро работать, особенно при отсутствии этой фичи.
Что значит пользоваться Causal consistency в данном случае? Это показывать afterClusterTime-параметр. А без этого он просто будет передавать значения в любом случае. Gossiping, начиная с версии 3.6, работает всегда.
Если мы оставим постоянное генерирование подписей, то это будет замедлять систему даже при отсутствии фичи, что не соответствует нашим подходам и требованиям. И что мы сделали?
Делай это быстро!
Достаточно простая вещь, но трюк интересный – поделюсь, может, кому-то будет интересно.
У нас есть хэш, в котором хранятся подписанные данные. Все данные идут через кэш. Кэш подписывает не конкретно время, а Range. Когда приходит некоторое значение, мы генерируем Range, маскируем последние 16 бит, и это значение мы подписываем:
Получая такую подпись, мы ускоряем систему (условно) в 65 тысяч раз. Оно прекрасно работает: когда поставили эксперименты – там реально в 10 тысяч раз сократилось время, когда у нас последовательный апдейт. Понятно, что когда они в разнобой, этого не получается. Но в большинстве практических случаев это работает. Комбинация подписи Range вместе с подписью позволила решить проблему безопасности.
Чему мы научились?
Уроки, которые мы из этого извлекли:
- Нужно читать материалы, истории, статьи, потому что нам много чего интересного есть. Когда мы работаем над какой-то фичей (особенно сейчас, когда мы транзакции делали и т. д.), надо читать, разбираться. Это отнимает время, но это на самом деле очень полезно, потому что становится понятно, где мы находимся. Мы ничего нового вроде и не придумали – просто взяли ингредиенты.
Вообще, наблюдается определённая разница в мышлении, когда имеет место академическая конференция («Сигмон», например) – там все фокусируются на новых идеях. В чём новизна нашего алгоритма? Здесь новизны особой нет. Новизна скорее заключается в том, как мы смешали вместе существующие подходы. Поэтому первое – нужно читать классиков, начиная с Лэмпарта. - В продакшне совершенно другие требования. Я уверен, что многие из вас сталкиваются не со «сферическими» базами данных в абстрактном вакууме, а с нормальными, реальными вещами, у которых существуют проблемы по availability, latency и отказоустойчивости.
- Последнее – это то, что нам пришлось рассмотреть разные идеи и скомбинировать несколько вообще разных статей в один подход, вместе. Идея про подписывание, например, вообще пришла из статьи, которая рассматривала Paxos-протокол, которые для невизантийских Фейлоров внутри авторизационного протокола, для византийских – за пределами авторизационного протокола… В общем, это ровно то, что мы в итоге и сделали.
Нового здесь абсолютно ничего нет! Но как только мы это всё вместе смешали… Всё равно что сказать, что рецепт салата Оливье – ерунда, потому что яйца, майонез и огурцы уже придумали… Это примерно та же самая история.
На этом закончу. Спасибо!
Вопросы
Вопрос из зала (далее – В): – Спасибо, Михаил за доклад! Тема про время интересная. Вы используете Gossiping. Сказали, что у всех есть своё время, все знают своё локальное время. Я так понял, что у нас есть драйвер – клиентов с драйверами может быть много, query-planner’ов тоже, шардов тоже много… А к чему скатывается система, если у нас вдруг возникнет расхождение: кто-то решит, что он на минуту впереди, кто-то — на минуту позади? Где мы окажемся?
МТ: – Отличный вопрос на самом деле! Я как раз про шарды хотел сказать. Если я правильно понимаю вопрос, у нас такая ситуация: есть шард 1 и шард 2, чтение происходит с этих двух шардов – у них расхождение, они между собой не взаимодействуют, потому что время, которое они знают – разное, особенно время, которое у них существует в оплогах.
Допустим, шард 1 сделал миллион записей, шард 2 – вообще ничего, а запрос пришёл на два шарда. И у первого есть afterClusterTime более миллиона. В такой ситуации, как я объяснил, шард 2 вообще никогда не ответит.
В: – Я хотел узнать, как они синхронизируются и выберут одно логическое время?
МТ: – Очень просто синхронизируются. Шард, когда к нему приходит afterClusterTime, и он не находит времени в «Оплоге» – инициирует no approved. То есть он руками поднимает своё время до этого значения. Это означает, что у него нет событий, отвечающих этому запросу. Он создаёт это событие искусственно и становится таким образом Causal Consistent.
В: – А если к нему после этого ещё приедут какие-нибудь события, которые в сети где-то затерялись?
МТ: – Шард так устроен, что они уже не приедут, поскольку это single master. Если он уже записал, то они уже не приедут, а будут после. Не может так получиться, что где-то что-то застряло, потом он сделает no write, а потом эти события приехали – и нарушилась Causal consistency. Когда он делает no write, они все должны приехать дальше (он их подождёт).
В: – У меня есть несколько вопросов относительно очередей. Causal consistency предполагает, что есть определённая очередь действий, которые нужно выполнить. Что произойдёт, если у нас один пакет пропадает? Вот пошёл 10-й, 11… 12-й пропал, а все остальные ждут, когда он исполнится. И у нас вдруг машина умерла, мы ничего не можем сделать. Есть ли максимальная длина очереди, которая копится, прежде чем выполняется? Какой fatal failure происходит при потере какого-либо одного состояния? Тем более, если мы записываем, что есть какое-то состояние предыдущее, то от него же мы должны как-то отталкиваться? А от него не оттолкнулись!
МТ: – Тоже прекрасный вопрос! Что мы делаем? В MongoDB есть понятие кворумных записей, кворумного чтения. В каких случаях сообщение может пропасть? Когда запись некворумная или когда чтение не кворумное (тоже может пристать какой-то garbage).
Относительно Causal consistency выполнили большую экспериментальную проверку, результатом которой стало то, что в случае, когда записи и чтение – некворумные, возникают нарушения Causal consistency. Ровно то, что вы говорите!
Наш совет: использовать хотя бы кворумное чтение при использовании Causal consistency. В этом случае пропадать ничего не будет, даже если кворумная запись пропадёт… Это ортогональная ситуация: если пользователь не хочет чтобы пропали данные, нужно использовать кворумную запись. Causal consistency не даёт гарантии durability. Гарантию durability даёт replication и machinery, связанная с replication.
В: – Когда мы создаём instance, который у нас шардинг выполняет (не master, а slave соответственно), он опирается на unix-время собственной машины или на время «мастера»; синхронизируется в первый раз или периодически?
МТ: – Сейчас проясню. Шард (т. е. горизонтальная партиция) – там всегда есть Primary. А в шарде может быть «мастер» и могут быть реплики. Но шард всегда поддерживает запись, потому что он должен поддерживать некоторый домен (в шарде стоит Primary).
В: – То есть всё зависит сугубо от «мастера»? Всегда используется «мастер»-время?
МТ: – Да. Можно образно сказать: часы тикают, когда происходит запись в «мастер», в «Оплог».
В: – У нас есть клиент, который коннектится, и ему не нужно знать про время ничего?
МТ: – Вообще ничего не нужно знать! Если говорить о том, как это работает на клиенте: у клиента, когда он хочет пользоваться Causal consistency, ему нужно открыть сессию. Сейчас там всё: и транзакции в сессии, и retrieve a rights… Сессия – это упорядочение логических событий, происходящих с клиентом.
Если он открывает эту сессию и там говорит, что хочет Causal consistency (если по умолчанию сессия поддерживает Causal consistency), всё автоматически работает. Драйвер запоминает это время и увеличивает его, когда получает новое сообщение. Он запоминает, какой ответ вернуло предыдущее с сервера, который вернул данные. Следующий запрос будет содержать afterCluster («time больше этого»).
Клиенту не нужно знать ровным счётом ничего! Это абсолютно для него непрозрачно. Если люди используют эти фичи, что позволяет сделать? Во-первых, можно безопасно читать secondaries: можно писать на Primary, а читать с географически реплицированных secondaries и быть уверенным, что это работает. При этом сессии, которые записал на Primary, можно передать даже на Secondary, т. е. можно использовать не одну сессию, а несколько.
В: – С темой Eventual consistency сильно связан новый пласт Compute science –типы данных CRDT (Conflict-free Replicated Data Types). Рассматривали ли вы интеграцию этих типов данных в базу и что можете сказать об этом?
МТ: – Хороший вопрос! CRDT имеет смысл для конфликтов при записи: в MongoDB – single master.
В: – У меня вопрос от девопсов. В настоящем мире встречаются такие иезуитские ситуации, когда византийский Failure происходит, и злые люди внутри защищённого периметра начинают втыкаться в протокол, специальным образом крафтовые пакеты присылать?
МТ: – Злые люди внутри периметра – всё равно что троянский конь! Злые люди внутри периметра могут сделать много плохих вещей.
В: – Понятное дело, что оставлять в сервере, грубо говоря, дырочку, через которую можно зоопарк слонов просунуть и обвалить весь кластер навсегда… Потребуется время для ручного восстановления… Это, мягко говоря, неправильно. С другой стороны, любопытно вот что: в реальной жизни, в практике встречаются такие ситуации, когда натурально подобные внутренние атаки происходят?
МТ: – Поскольку я нечасто сталкиваюсь с security breach’ами в реальной жизни, не могу сказать – может, они и происходят. Но если говорить о девелоперской философии, то мы считаем так: у нас есть периметр, который обеспечивает ребят, которые делают security – это замок, стена; а внутри периметра можно делать всё, что угодно. Понятно, что есть пользователи с возможностью только посмотреть, а есть пользователи с возможностью стереть каталог.
В зависимости от прав, damage, который пользователи могут сделать, может быть мышью, а может быть и слоном. Понятно, что пользователь с полными правами может сделать вообще всё что угодно. Пользователь с не широкими правами вреда может причинить существенно меньше. В частности, он не может сломать систему.
В: – В защищённом периметре кто-то полез формировать неожиданные протоколы для сервера, чтобы раком поставить сервер, а если повезёт, то и весь кластер… Бывает ли настолько «хорошо»?
МТ: – Ни разу не слышал о таких вещах. То, что таким образом можно завалить сервер – это не секрет. Завалить внутри, находясь с протокола, будучи авторизованным пользователем, который может записать в сообщение что-то такое… На самом деле нельзя, потому что всё равно он будет верифицироваться. Есть возможность отключить эту аутентификацию для пользователей, которые не хотят – это тогда их проблемы; они, грубо говоря, сами разрушили стены и можно запихнуть туда слона, который растопчет… А вообще, можно одеться ремонтником, прийти и вытащить!
В: – Спасибо за доклад. Сергей («Яндекс»). В «Монге» есть константа, которая лимитирует количество голосующих членов в Replica Set’е, и эта константа равна 7 (семи). Почему это константа? Почему это не параметр какой-то?
МТ: – Replica Set у нас бывает и по 40 нодов. Там всегда majority. Я не знаю какая версия…
В: – В Replica Set’е можно не голосующих членов запускать, но голосующих – максимум 7. Как в этом случае переживать выключение, если у нас Replica Set стянут на 3 дата-центра? Один дата-центр может запросто выключиться, и ещё одна машинка выпасть.
МТ: – Это уже немного за пределами доклада. Это общий вопрос. Может, потом его могу рассказать.
Немного рекламы :)
Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).
Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?
gecube
Спасибо, что простите расшифровки докладов!
Очень полезно и интересно!