Новости

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

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

В этой книге вы углубитесь в:

• Механизмы хранения: классификация и таксономия хранилищ, механизмы хранения на основе B-дерева и неизменяемые лог-структуры.

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

• Распределенные системы: пошаговое руководство по подключению узлов и процессов и построение сложных схем взаимодействия.
• Кластеры баз данных: модели согласованности в современных базах данных и согласованность распределенных систем хранения.

Предисловие к русскому изданию

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

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

Обнаружение отказов

Слышен ли звук падающего дерева в лесу, если рядом никого нет?

Неизвестный автор

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

Обнаружить отказ в асинхронных распределенных системах (т. е. без каких-либо предположений о времени) чрезвычайно сложно, так как невозможно определить, произошло ли аварийное завершение процесса или он работает медленно, и для ответа требуется неопределенно много времени. Мы обсуждали эту проблему в разделе «Невозможность Фишера–Линча–Патерсона» на с. 207.

Такие определения, как «мертвый» (dead), «отказавший» (faulty) и «аварийно завершившийся» (crashed), обычно используются для описания процессов, которые полностью прекратили выполнение своих шагов. Такие определения, как «неотвечающий» (unresponsive), «неисправный» (faulty) и «медленный» (slow), используются для описания подозрительных процессов, которые на самом деле могут быть «мертвыми».

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

Детектор отказов (failure detector) — это локальная подсистема, отвечающая за выявление отказавших или недоступных процессов с целью исключить их из алгоритма и гарантировать его живучесть с сохранением безопасности.

Живучесть и безопасность — это свойства, которые отражают способность алгоритма решать конкретную проблему и корректность выдаваемых им результатов. Если выражаться более формально, свойство живучести (likeness) гарантирует, что произойдет конкретное предполагаемое событие. Например, в случае отказа одного из процессов детектор отказов должен обнаружить этот отказ. Свойство безопасности (safety) гарантирует, что не произойдут непредвиденные события. Например, если детектор отказов пометит процесс как «мертвый», этот процесс должен на самом деле быть «мертвым» [LAMPORT77] [RAYNAL99] [FREILING11].

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

Алгоритмы обнаружения отказов должны обладать несколькими неотъемлемыми свойствами. Прежде всего каждый свободный от неисправностей участник должен в конце концов заметить отказ процесса, а алгоритм должен быть в состоянии продолжить работу и в конечном итоге достичь своего целевого результата. Это свойство называется завершаемостью (completeness).

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

Мы можем рассматривать отношение между эффективностью и точностью как настраиваемый параметр: более эффективный алгоритм может быть менее точным, а более точный алгоритм обычно менее эффективен. Вероятно, невозможно создать детектор отказов, который будет и точным, и эффективным. В то же время детекторам отказов разрешается выдавать ложноположительные результаты (т. е. ложно идентифицировать активные процессы как отказавшие и наоборот) [CHANDRA96].

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

Многие распределенные системы реализуют детекторы отказов с применением контрольных пакетов (heartbeat). Этот подход довольно популярен из-за своей простоты и сильной завершаемости. Алгоритмы, которые мы здесь обсуждаем, предполагают отсутствие византийских ошибок: процессы не пытаются преднамеренно выдавать ложную информацию о своем состоянии или состояниях своих соседей.

Контрольные пакеты и эхо-запросы

Мы можем запрашивать состояние удаленных процессов, используя один из двух периодических процессов:

• Мы можем использовать эхо-запросы (ping), отправляя сообщения удаленным процессам и проверяя их активность путем ожидания ответа в течение определенного времени.

• Мы можем использовать контрольные пакеты: при этом процесс активно уведомляет одноранговые процессы о своей активности путем отправки им сообщений.

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

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

На рис. 9.1 показано нормальное функционирование системы: процесс P₁ запрашивает состояние соседнего узла P₂, который отвечает подтверждением.

На рис. 9.2 показан случай, когда подтверждения задерживаются, что может привести к отнесению активного процесса к числу неработающих.

Многие алгоритмы обнаружения отказов используют контрольные пакеты и время ожидания. Например, в популярном фреймворке для создания распределенных систем Akka реализован детектор отказов на основе лимита времени, который использует контрольные пакеты и уведомляет о сбое процесса, если тот не «отметился» в течение фиксированного интервала времени.

У этого подхода есть несколько потенциальных недостатков: его точность зависит от правильного выбора частоты отправки эхо-запросов и величины времени ожидания, и, кроме того, он не учитывает видимость процесса с точки зрения других процессов (см. подраздел «Сторонние контрольные пакеты» на с. 217).

Детектор отказов без времени ожидания

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

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

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

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

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

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

Сторонние контрольные пакеты

В протоколе SWIM [GUPTA01] используется альтернативный подход, который сводится к тому, чтобы использовать сторонние контрольные пакеты для повышения надежности за счет получения информации о жизнеспособности процесса с точки зрения его соседей. Этот подход не требует, чтобы процессы были осведомлены обо всех других процессах в сети, — достаточно иметь информацию лишь о некотором подмножестве подключенных одноранговых узлов.

Как показано на рис. 9.3, процесс P₁ отправляет сообщение эхо-запроса процессу P₂. Процесс P₂ не отвечает на сообщение, поэтому процесс P₁ продолжает, выбрав нескольких случайных участников (P₃ и P₄). Эти случайные участники пытаются отправить сообщения контрольных пакетов процессу P₂ и, если он отвечает, направляют подтверждения обратно процессу P₁.

Этот подход позволяет учитывать как прямую, так и опосредованную доступность. Например, если у нас есть процессы P₁, P₂ и P₃, мы можем проверить состояние процесса P₃ и со стороны процесса P₁, и со стороны процесса P₂.

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

Детектор отказа с накопленным уровнем подозрительности

Вместо того чтобы рассматривать отказ узла как бинарную задачу, где процесс может быть только в двух состояниях: работоспособном или неработоспособном, детектор отказа с накопленным фи (φ) (phi accrual failure detector) [HAYASHIBARA04] использует непрерывную шкалу, отражающую вероятность аварийного завершения отслеживаемого процесса. Такой детектор использует скользящее окно, собирая данные о времени поступления самых последних контрольных пакетов от других процессов. Эта информация используется для вычисления приблизительного времени поступления следующего контрольного пакета, дальнейшего сравнения этого значения с фактическим временем поступления и вычисления уровня подозрительности φ — степени уверенности детектора отказа в наличии отказа с учетом текущего состояния сети.

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

С точки зрения архитектуры детектор отказа с накопленным уровнем подозрительности можно рассматривать как комбинацию трех подсистем:

Мониторинг
Сбор информации о живучести с помощью эхо-запросов (ping), контрольных пакетов или выборочных данных о запросах и ответах.

Интерпретация
Принятие решения о том, должен ли процесс быть помечен как подозрительный.

Действие
Ответный вызов, выполняемый всякий раз, когда процесс помечается как подозрительный.

Процесс мониторинга собирает и сохраняет выборки данных (которые, как предполагается, следуют нормальному распределению) в фиксированного размера окне времен поступления контрольных пакетов. Новые поступления добавляются в окно, а самые старые элементы данных о контрольных пакетах отбрасываются.

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

Этот подход разработан исследователями из Японского передового института науки и техники (JAIST) и в настоящее время используется во многих распределенных системах, например в системах Cassandra и Акка (как и вышеупомянутый детектор отказов на основе лимита времени).

С полным содержанием статьи можно ознакомиться на сайте "Хабрахабр":

https://habr.com/ru/company/piter/blog/570132/