Результаты исследования пользователей показывают, что Raft легче осваивается учащимися, чем Paxos. Raft также включает в себя новый механизм изменения членства в кластере, который использует перекрывающееся большинство для обеспечения безопасности.
Raft используется etcd (14) и Influx DB (15) среди многих других.
18. «Paxos стал проще» (Paxos Made Simple).
Одна из многочисленных влиятельных работ Лесли Лэмпорта «Paxos стал проще» является жемчужиной, потому что объясняет общеизвестно сложный алгоритм Paxos, потому что даже в самом простом виде Paxos не так прост:
Алгоритм Paxos для реализации отказоустойчивой распределенной системы считался трудным для понимания, возможно, потому, что оригинальная презентация была абракадаброй для многих читателей. На самом деле, это один из самых простых и очевидных распределенных алгоритмов. В его основе лежит алгоритм консенсуса – «синода». В следующем разделе показано, что этот алгоритм почти неизбежно вытекает из того, какие свойства мы хотим, чтобы он удовлетворял. В последнем разделе объясняется полный алгоритм Paxos, который получается путем прямого применения консенсуса к методу, основанному на теории конечных автоматов, для построения распределенной системы. Этот подход должен быть хорошо известен, поскольку является предметом, вероятно, наиболее часто цитируемой статьи по теории распределенных систем.
Paxos сам по себе остается глубоко инновационной концепцией и является алгоритмом, лежащим в основе приложений Google Chubby и Apache Zookeeper (16), среди многих других.
19. «SWIM: Масштабируемый слабо согласованный протокол членства в группе процессов в стиле заражения» (SWIM: ScalableWeakly-Consistent Infection-Style Process Group Membership Protocol).
Большинство алгоритмов консенсуса сосредоточены на согласованности во время разделения, но SWIM идет в другом направлении и фокусируется на доступности:
Несколько распределенных одноранговых приложений требуют слабо согласованного знания информации о членстве в группе процессов во всех участвующих процессах. SWIM – это универсальный программный модуль, который предлагает эту услугу для крупномасштабных групп процессов. Сила SWIM мотивирована невозможностью масштабирования традиционных протоколов частоты обмена данными, которые либо накладывают нагрузку на сеть, растущую в геометрической прогрессии с размером группы, либо снижают время ответа или частоту ложных срабатываний при обнаружении сбоев. В этой статье рассказывается о проектировании, внедрении и производительности подсистемы SWIM на большом количестве обычных ПК.
SWIM используется в программном обеспечении Hashi Corp, а также в Ringpop от Uber.
20. «Проблема византийских генералов» (The Byzantine Generals Problem).
В другой классической статье Лесли Лэмпорта о консенсусе «Проблема византийских генералов» исследуется, как бороться с распределенными участниками, которые намеренно или случайно отправляют неверные сообщения:
Надежные компьютерные системы должны уметь работать с неисправными компонентами, которые передают противоречивую информацию различным частям системы. Эту ситуацию можно абстрактно изобразить в виде группы генералов византийской армии, расположившихся лагерем со своими войсками вокруг вражеского города. Общаясь только через посыльных, генералы должны согласовать общий план сражения. Однако один или несколько из них могут оказаться предателями, которые попытаются сбить с толку остальных. Проблема состоит в том, чтобы найти алгоритм, гарантирующий, что верные генералы придут к соглашению. Показано, что при использовании только устных сообщений эта проблема разрешима тогда и только тогда, когда более двух третей генералов верны. Таким образом, один предатель может поставить в тупик двух верных генералов. С неподделываемыми письменными сообщениями проблема разрешима для любого числа генералов и возможных предателей. Затем обсуждается применение этих решений в надежных компьютерных системах.
Статья в основном посвящена формальному доказательству, небольшой теме Лэмпорта, который разработал TLA+ (17), чтобы упростить формальное доказательство, но это также полезное напоминание о том, что мы все еще склонны предполагать, что наши компоненты будут вести себя надежно и честно, и, возможно, мы не должны так думать!
21. «Из смоляной ямы» (Out of the Tar Pit).
В статье «Из смоляной ямы» авторы сетуют на ненужную сложность программного обеспечения и предполагают, что функциональное программирование и лучшее моделирование данных могут помочь нам уменьшить случайную сложность. (Авторы утверждают, что большая часть ненужной сложности исходит от состояния системы.)
Выдержка из аннотации:
Сложность – это единственная серьезная трудность в успешной разработке крупномасштабных программных систем. Следуя за Бруксом, мы отличаем случайную сложность от существенной, но не согласны с его предпосылкой о том, что большая часть сложности, остающаяся в современных системах, является существенной. Мы выявляем общие причины сложности и обсуждаем общие подходы, которые можно использовать для их устранения там, где они носят случайный характер. Чтобы добавить конкретики, мы впоследствии дадим описание потенциального подхода к минимизации сложности, основанного на функциональном программировании и реляционной модели данных Кодда.
Статья, безусловно, отличная, хотя, читая ее десять лет спустя, интересно увидеть, что ни один из этих подходов не принес особого успеха. Вместо этого наиболее близким “универсальным” подходом к снижению сложности, по-видимому, является переход к многочисленным службам, в основном без фиксации состояния. Возможно, это скорее снижение локальной сложности за счет большей системной сложности, обслуживание которой затем делегируется более специализированным системным инженерам.
(Это еще одна статья, которая заставляет меня пожалеть, что TLA+ не кажется достаточно естественным и интуитивно понятным, чтобы стать общепринятым инструментом.)
22. «Служба полной блокировки Chubby для слабосвязанных распределенных систем» (The Chubby Lock Service for Loosely-Coupled Distributed Systems).
Распределенные системы достаточно сложны без необходимости частого повторного внедрения Paxos или Raft. Модель, предложенная Chubby, заключается в том, чтобы реализовать консенсус один раз в общей службе, что позволит системам, построенным на его основе, делиться устойчивостью распределения, следуя значительно упрощенным шаблонам.
Выдержка из аннотации:
Мы описываем наш опыт работы с сервисом блокировки Chubby, который предназначен для обеспечения детальной блокировки, а также надежного (хотя и малого по объему) хранилища для слабосвязанной распределенной системы. Chubby предоставляет интерфейс, очень похожий на распределенную файловую систему с консультативными блокировками, но при проектировании акцент делается на доступности и надежности, а не на высокой производительности. Многие версии сервиса используются уже более года, причем каждый из них обслуживает несколько десятков тысяч клиентов одновременно. В статье описывается первоначальный проект и ожидаемое использование, оно сравнивается с его фактическим применением и объясняется, как нужно изменить начальный дизайн, чтобы учесть различия.
В мире с открытым исходным кодом способ использования Zookeeper в таких проектах, как Kafka и Mesos, играет ту же роль, что и Chubby.
23. «Bigtable: Распределенная система хранения структурированных данных» (Bigtable: A Distributed Storage System for Structured Data).
Одной из выдающихся разработок и технологий Google является Bigtable, который был ранним (во всяком случае, в начале эры Интернета) хранилищем данных NoSQL, работающим в чрезвычайно больших масштабах и построенным на основе Chubby.
Bigtable – это распределенная система хранения для управления структурированными данными, которая предназначена для масштабирования до очень большого размера: петабайты данных на тысячах типовых серверов. Многие проекты Google хранят данные в Bigtable, включая веб-индексацию, Google Earth и Google Finance. Эти приложения предъявляют к Bigtable очень разные требования как с точки зрения размера данных (от URL-адресов до веб-страниц и спутниковых снимков), так и с точки зрения требований к задержке (от серверной массовой обработки до предоставления данных в режиме реального времени). Несмотря на эти разнообразные требования, Bigtable успешно предоставил гибкое и высокопроизводительное решение для всех этих продуктов Google. В этой статье мы описываем простую модель данных, предоставляемую Bigtable, которая дает клиентам динамический контроль над расположением и форматом данных, а также описываем проект и реализацию Bigtable.
Начиная с проекта SS Table и заканчивая фильтрами bloom, Cassandra в значительной степени основана на статье о Bigtable и, вероятно, по праву считается слиянием статей о Dynamo и Bigtable.
24. «Spanner: Глобально распределенная база данных Google» (Spanner: Google’s Globally-Distributed Database)
Многие ранние системы хранения данных NoSQL обменивали конечную согласованность на повышенную отказоустойчивость. Но построение на основе систем, которые в конечном итоге согласованы, может быть мучительным. Spanner представляет собой надежный подход, решающий эту проблему, частично основанный на новом методе управления временем.
Spanner – масштабируемая, многовариантная, глобально распределенная и синхронно реплицируемая база данных Google.Это первая система, которая распределяет данные в глобальном масштабе и поддерживает согласованные с внешним миром распределенные транзакции. В этой статье описывается структура Spanner, ее набор функций, обоснование, лежащее в основе различных проектных решений, и новый прикладной программный интерфейс для управления временем, который выявляет неопределенность часов. Этот прикладной программный интерфейс и его реализация имеют решающее значение для поддержки внешней согласованности и множества мощных функций: неблокирующее считывание данных в прошлом, транзакции только для считывания данных без блокировки и атомарные изменения схемы во всем Spanner.