Авторы Саджид Сайед Бахт и Говинд Мохан

В мире баз данных может быть сложно ориентироваться, будь вы студент, выпускник или опытный разработчик. За последнее десятилетие появилось несколько парадигм, воплощенных в различных крупных проектах с эксцентричными названиями, такими как Cockroach DB и Voldemort. Мы также переживаем новую волну инноваций в распределенных системах с технологией распределенной бухгалтерской книги, которая была популяризирована ростом криптовалют, таких как Биткойн и Эфириум.

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

Необходимость репликации

База данных, работающая на одном сервере, может удовлетворить все эти случаи, но по мере увеличения трафика (естественный побочный эффект роста) она теряет способность быть отказоустойчивой, то есть работать без ошибок. Могут быть проблемы с ограничениями памяти / диска / процессора, а апгрейды оборудования (вертикальное масштабирование) только сбивают с толку. Кроме того, сбои в сети могут полностью перекрыть доступ к базе данных. Таким образом, крайне важно поддерживать базу данных на разных машинах (горизонтальное масштабирование), чтобы обеспечить беспрепятственный доступ, даже если сеть ненадежна. Сохранение копий базы данных или репликация приводит к распределенной базе данных. Репликация связана со своим набором вопросов: как обеспечить постоянное соответствие этих копий друг другу?

Измерение производительности базы данных

Прежде чем мы продолжим, стоит обсудить, как мы можем сравнивать базы данных на основе их желаемых свойств. Исходя из теории распределенных систем, теорема CAP определяет ландшафт производительности базы данных. В нем говорится, что ни одно распределенное хранилище данных не может обеспечить все три следующих свойства: Согласованность, Доступность, и Допуск раздела . Согласованность (C) - это гарантия того, что запросы к распределенной базе данных всегда выполняются в определенном порядке. Таким образом, все записи во всех копиях базы данных должны состоять из одного и того же набора операций. Например, все копии распределенной базы данных MySQL должны всегда иметь одни и те же таблицы, и эти таблицы должны быть построены с использованием одних и тех же операторов INSERT, UPDATE и т. Д. Доступность (A) означает, что любой запрос к любому узлу в базе данных всегда возвращает какой-либо ответ, не связанный с ошибкой. Это включает в себя сценарии, в которых узлы в распределенной системе имеют отказы, и ответ будет иметь неопределенную задержку. Допуск на разделение (P) относится к способности системы работать после потери / задержки произвольного количества сообщений между узлами. В частности, когда сеть сегментирована на группы узлов или разделена на разделы, некоторые разделы не смогут надежно взаимодействовать с другими. Таким образом, распределенная система не может иметь CAP, поскольку в системе могут быть два раздела, G1 и G2, узлов, которые не взаимодействуют друг с другом, и запрос записи в G1, за которым сразу следует запрос чтения в G2, будет иметь несовместимый значения, поскольку G2 не будет отображать запрос записи в G1.

Этой проблемы можно избежать в системе переменного тока, поскольку запросы всегда могут передаваться между узлами. Этого также избегают в системах AP, поскольку не требуется устранять несогласованность из вышеупомянутой ситуации, а в системах CP запросы к базе данных не будут успешными, поскольку доступность не требуется. В реальной сети отказы оборудования в значительной степени непредсказуемы, поэтому обычно предполагается разделение. В результате системы AP и CP предпочтительнее систем переменного тока. Важно отметить, что CAP - это довольно упрощенная количественная оценка производительности базы данных, но она служит хорошей отправной точкой для понимания других показателей.

Парадигма лидер-последователь

При работе с кластером узлов наша цель - обеспечить правильную репликацию данных на нескольких узлах. Следовательно, если узел выходит из строя, данные не «исчезают». Кластер может просто заглянуть в другой узел в поисках соответствующих данных.

Наиболее распространенным и традиционным подходом к репликации в распределенных системах является подход «лидер-последователь». Каждый узел в кластере разделен на две группы: лидеры, которые принимают запросы на запись и отправляют данные в другую группу, и последователи, которые могут принимать только запросы на чтение. Общая идея состоит в том, чтобы лидеры принимали записи, а затем отправляли изменения данных, содержащиеся в записи, последователям для копирования. Запросы на чтение в основном обрабатываются последователями, чтобы снять нагрузку с лидера, в то время как его ресурсы сосредоточены на приеме записи.

I. Система с одним лидером

В системе этого типа один экземпляр в кластере назначается лидером, а остальные реплики - последователями. Эта парадигма часто бывает полезна, когда запись должна выполняться в последовательном порядке. Один лидер может последовательно обрабатывать каждую происходящую запись. Например, три записи могут быть запрошены для умножения, затем деления и вычитания из значения. Поскольку эти записи не являются коммутативными, важно, чтобы они обрабатывались последовательно. Запись происходит следующим образом: лидер получает запрос на запись, затем записывает данные в свое собственное хранилище и затем отправляет ту же запись последователям, чтобы также изменить данные. Запись может быть принята при двух разных условиях. Во-первых, репликация от лидера к подчиненному может выполняться асинхронно; запись может быть принята после того, как лидер запишет данные в свое собственное хранилище и реплицирует хотя бы на один другой узел. Или запись может быть принята синхронно; после того, как лидер убедится, что каждый из последователей также реплицирует изменение данных в свой собственный магазин. Эта тонкая дифференциация влияет на согласованность и доступность.

Асинхронная и синхронная репликация

Синхронная репликация работает следующим образом. Запись отправляется в базу данных. Лидер обрабатывает запись, обновляя собственное хранилище данных. Затем лидеры отправляют данные последователям, чтобы они воспроизвели их. Каждый ведомый отправляет обратно статус, в котором говорится, что данные были успешно реплицированы в их хранилище данных. Лидер ждет, пока каждый ведомый отправит подтверждающий ответ. Убедившись, что каждый ведомый успешно скопировал данные, лидер сообщает клиенту, что запись была успешной. Это гарантирует единообразие данных на всех узлах. Следовательно, когда запрашивается чтение, кластер отправляет запрос в любое хранилище данных. Однако такой уровень согласованности требует компромисса; более скрытая и, следовательно, менее доступная система.

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

Асинхронная репликация, напротив, позволяет лидеру обрабатывать запросы на запись, не беспокоясь о том, что каждый последователь реплицирует изменение данных. Лидер принимает записи, вносит изменения в собственное хранилище данных, а затем отправляет уведомление последователям для репликации данных от лидера. Затем лидер начинает принимать новые запросы на запись. Однако, поскольку согласованность данных не гарантируется, это может иметь неприятные последствия. Представьте, что человек хочет обновить изображение профиля в своей учетной записи в социальной сети. Это изменение можно рассматривать как «запрос на запись». Т.е.

UPDATE Profile
SET Picture = ‘newpic.jpeg’
WHERE ProfileID = 1;

Последователь принимает запись и обрабатывает запись асинхронно. Затем человек проверяет свой профиль, чтобы убедиться, что изменение было внесено. Этот запрос отправит кластеру запрос на «чтение». Человек рад видеть, что его фотография изменилась. Это может быть случай, когда запрос чтения направляется ведомому, который успешно реплицирует изменение данных от ведущего. Затем человек просит друга прокомментировать картинку. Друг заходит в профиль этого человека, но замечает, что изображение профиля не изменилось. Это может быть случай, когда запрос на чтение направляется ведомому, который не смог успешно реплицировать изменение данных от ведущего.

Подход, сочетающий эти два подхода, является подходом с минимальной несинхронной репликой. Система данных устанавливает число n, обозначающее минимальное количество несинхронных реплик. Когда лидер имеет дело с записью, он только ждет, пока n последователей успешно реплицируют данные. Таким образом, лидер не увяз в ожидании, пока все подчиненные реплицируют данные, и, таким образом, система с меньшей вероятностью станет недоступной из-за ожидания успешных запросов на запись.

Сбои в работе узла

В распределенной системе может возникнуть одна ошибка - отток узлов, когда узлы отключаются произвольно. Поэтому, если узел выходит из строя, наша система все еще может работать, принимая запросы на запись и чтение. Чтобы справиться с простоями узла, важно знать, какой тип узла вышел из строя. Если ведомый узел выходит из строя, но возвращается обратно, то как он сможет догнать все произошедшие изменения данных? Если лидер выходит из строя, как система продолжает принимать записи?

Отключение последователя

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

Лидер отключен

Когда лидер выходит из строя, появляется больше сложности. Чтобы система продолжала принимать записи, один из последователей в системе должен быть избран лидером. Затем каждый последователь должен знать об этом изменении, чтобы он мог копировать данные от новоизбранного лидера. Этот процесс называется отработкой отказа.

Отказоустойчивость может выполняться администратором вручную или автоматически.

Автоматические шаги обычно следующие.

  1. Определить лидера не удалось. Лидеры могут потерпеть неудачу по нескольким причинам. Сбои в работе сети, сбои в подаче электроэнергии, сбои и многое другое. Не существует надежного способа проверить, упал ли лидер, но обычно это делается с помощью тайм-аутов. Если узел не отвечает в течение определенного времени, то есть 20 секунд, можно понять, что лидер потерпел неудачу.
  2. Следующим шагом будет выбор нового лидера. Лучшим кандидатом обычно является подписчик с самыми свежими данными. Это гарантирует минимальную потерю данных. Получение узлов для избрания лидера считается проблемой консенсуса, которая будет исследована в следующих блогах.
  3. Последний шаг - перенастроить систему, чтобы клиенты теперь отправляли данные новому лидеру. Кроме того, он должен гарантировать, что если более старый лидер вернется, тогда он будет знать, что он больше не лидер, а его последователь.

Есть много распространенных ошибок при отказе. Например, при асинхронной репликации более старый лидер может вернуться. Однако на нем могут быть записанные данные, которые есть у других подписчиков. Как система должна обрабатывать эти данные? Еще одна проблема - понять, когда ушел лидер. Какова правильная продолжительность тайм-аута? Более длительный тайм-аут приведет к увеличению времени восстановления системы в случае отказа лидера. Более короткий тайм-аут может привести к ненужному переключению при отказе. Например, если в системе возникают задержки в сети из-за всплеска активности, то выполнение процесса аварийного переключения приведет к увеличению нагрузки на систему, что еще больше замедлит ее.

Задержка репликации

Архитектура с одним лидером хорошо подходит для рабочих нагрузок приложений, которые состоят в основном из операций чтения и небольшого процента операций записи. Представьте себе простой блог-сайт. Большая часть трафика - это пользователи, читающие блоги, в то время как запись осуществляется только авторами или пользователями, которые хотят прокомментировать. Один из способов масштабирования этого веб-сайта - добавить больше узлов, то есть больше подписчиков для обработки запросов только для чтения. Однако, как отмечалось ранее, чем больше последователей добавляется к кластерам, тем больше времени на репликацию данных между ними. Поэтому более реалистичным становится асинхронный подход или минимальное количество бессинхронных реплик. Как указывалось ранее, асинхронные подходы несовместимы. Вместо этого они считаются «в конечном итоге» непротиворечивыми. Что в конечном итоге все реплики догонят и скопируют данные. Однако нет никакой гарантии, сколько времени это займет. Это может быть от нескольких секунд до нескольких часов. Это известно как задержка репликации; время, необходимое для репликации данных между всеми репликами. Есть много неожиданных проблем, которые могут произойти из-за задержки репликации. Мы подробно рассмотрим одну из них и ее решение, а именно монотонное чтение.

Монотонное чтение:

Представьте себе следующую ситуацию. Вы читаете только что опубликованный новый блог. Вы идете комментировать страницу, но у вас отключается Wi-Fi. После повторного подключения к Wi-Fi через несколько секунд вы снова переходите в блог, чтобы оставить комментарий. Однако блога, который можно было бы прокомментировать, нет. Кажется, что сайт уходит в прошлое. Произошло то, что изначально вы прочитали с актуальной реплики. Но затем последующий запрос на чтение отправляется на устаревший узел.

Монотонное чтение [ссылка] является гарантией того, что вышеуказанное не произойдет. А именно, пользователь не увидит старую реплику после того, как он просмотрел данные из более современной реплики. Один из способов достижения этого - чтение пользователем одной и той же реплики. Это можно сделать, выбрав реплику на основе некоторой функции личности пользователя. Однако, если выбранная реплика выйдет из строя, запрос пользователя должен быть перенаправлен на другую реплику.

II. Система с несколькими лидерами

Самым большим недостатком подхода с одним лидером является то, что лидером является только один экземпляр. Например, сетевое прерывание между лидером и клиентом может эффективно остановить этот клиент от записи в базу данных. Расширение подхода с одним лидером состоит в том, чтобы иметь несколько лидеров в системе. Представьте, что у вас есть несколько центров обработки данных, разделенных географически. При подходе с одним лидером одна реплика должна быть лидером всех этих центров обработки данных. В подходе с несколькими лидерами у вас может быть по одному руководителю для каждого центра обработки данных. Остальные узлы являются последователями лидера в своем центре обработки данных. Лидеры, в свою очередь, следуют за другими лидерами.

Подход с несколькими лидерами имеет больше смысла по следующим причинам. Во-первых, такая система работает лучше. В системе с одним лидером каждый последователь должен будет направиться к одному лидеру, который может находиться за пределами его центра обработки данных. В подходе с несколькими лидерами последователи должны смотреть только на лидера в своем локальном центре обработки данных. Во-вторых, в случае выхода дата-центра из строя; При подходе с одним лидером необходимо было бы избрать нового лидера, если бы этот центр обработки данных содержал лидера. Однако в подходе с несколькими лидерами записи могут быть приняты, поскольку есть несколько лидеров. Самая очевидная проблема подхода с несколькими лидерами заключается в том, что некоторые данные могут одновременно изменяться в двух разных центрах обработки данных.

Конфликты записи в системах с несколькими лидерами

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

В конфигурации с несколькими выносками нет определенного порядка записи, поэтому неясно, каким должно быть окончательное значение. Таким образом, каждая схема репликации должна гарантировать, что данные в конечном итоге будут одинаковыми на всех репликах. Один из популярных способов добиться этого - победа при последней записи (LWW). Кратко рассмотрим его общую структуру.

  1. Дайте каждой записи уникальный идентификатор (используя функцию, которая гарантирует уникальный идентификатор).
  2. Выберите запись с наивысшим UID в качестве победителя и выбросьте остальные.

Однако этот подход склонен к потере данных, поскольку другие записи отбрасываются. Более того, могут быть записи, которые отбрасываются, но не являются параллельными.

Разрешение конфликта записи в подходе с несколькими лидерами можно решить и минимизировать с помощью различных стратегий. Есть много стратегий, на которые стоит обратить внимание, но мы не будем вдаваться в подробности. Некоторые известные стратегии разрешения конфликтов включают победу при последней записи (LWW), операционное преобразование, объединяемые постоянные структуры данных и типы реплицируемых данных без конфликтов.

Заключение

Спасибо, что зашли так далеко. В этой статье мы рассказали о необходимости распределенной системы как средства безопасного хранения и извлечения данных. Мы рассмотрели парадигму «лидер-последователь» как способ взаимодействия узлов и обмена данными между собой при предположении, что сеть может быть ненадежной и могут произойти сбои узлов. Парадигма «лидер-последователь» помогает базе данных достичь согласованного состояния между узлами, однако это связано с затратами, поскольку система всегда должна согласовывать лидера и что лидер всегда должен присутствовать. Это приводит к тому, что наша система в некоторых случаях становится менее доступной. Для решения этих проблем появились новые парадигмы. А именно, парадигма без лидера, где ни один узел не является лидером и, следовательно, нет необходимости в дорогостоящих операциях, таких как переключение при отказе в случае выхода из строя лидера. В следующей статье мы представим парадигму без лидера и подробно рассмотрим, как системы без лидера становятся более доступными и как они поддерживают согласованность системы.

использованная литература

  1. Клеппманн, М. (2019). Разработка приложений с интенсивным использованием данных - важнейшие идеи, лежащие в основе надежных, масштабируемых и легко обслуживаемых систем. Пекин: О’Рейли.
  2. Https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
  3. Сет Гилберт и Нэнси Линч. 2002. Гипотеза Брюэра и возможность создания согласованных, доступных, устойчивых к разделам веб-сервисов. SIGACT News 33, 2 (июнь 2002 г.), 51–59. DOI: https: //doi.org/10.1145/564585.564601