Обзор докладов с конференции Hydra 2021

На ютубе опубликовали записи с конференции Hydra 2021. Я смотрел конференцию онлайн и написал abstract самых полезных и интересных докладов. Возможно, вам они тоже пригодятся и помогут в работе.

Distributed systems showdown — TLA+ vs real code — Jack Vanlightly, работает над Apache Pulsar и BookKeeper

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

TLA+ можно и нужно применять для проверки протоколов взаимодействия. За счёт полного перебора всех возможных состояний системы он позволяет относительно небольшим объёмом декларативного кода убедиться в том, что не допущено ошибок в самой модели взаимодействия компонент.

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

Джек рекомендует следовать следующему пайплайну разработки:

1. Валидируем идею с помощью TLA+.

2. Инкрементально пишем реализацию системы — сначала даже без репликации, система может состоять из одного узла, — и сразу же тесты для неё в Maelstrom. На каждом шаге убеждаемся, что пока ничего не сломали с помощью стресс-тестов.

В контексте TLA+ не могу не упомянуть про PlusCal, более высокоуровневый язык, транспилируемый в TLA+. Он позволяет писать спецификацию на псевдокоде, что сильно облегчает её понимание. По нему существует неплохая книга "Practical TLA+".

Serverless nature of Yandex Database — Андрей Фомичев, занимается разработкой YDB

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

Андрей утверждает, что YDB умеет масштабироваться до миллионов RPS и не имеет ограничений по объёму хранимой информации.

Data parallelism from a multicore perspective — Maurice Herlihy, Brown University

Доклад посвящён MapReduce как подходу. Морис дал обзор нескольких классических задач, которые можно решать его с помощью: Word Count, Word Frequency, Document Fingerprint, K-Means. Оказывается, MapReduce можно применять не только для распределённых вычислений, но и локально для вычислений параллельных, поскольку сам подход обладает приятным для нас свойством — возможностью использовать много параллельных map-ов без синхронизации.

Впрочем закон Амдала никто не отменял.

Algorithms for practical distributed agreement — Naama Ben-David, VMware

Доклад о борьбе с latency в задаче репликации конечных автоматов — консенсусы и иже с ними.

Наама предложила решение на основе RDMA (Remote Direct Memory Access). Если кратко, то подход опирается на прямую запись из буфера сетевого адаптера в память другой машины, в обход её CPU. Кроме того, heartbeat лидера вместо push-модели переводится на pull со стороны остальных членов группы — поскольку мы знаем, что CPU лидера в этом процессе не участвует, то тормозить можем или мы, или сеть. 

Если так сделать, то можно получить latency репликации порядка 1 микросекунды в лучшем случае и 1 миллисекунды в худшем случае, когда нужно делать leader election. Правда, вам понадобится RDMA-сеть между машинами.

Также были упомянуты предыдущие SOTA алгоритмы для задачи SMR, с которыми я раньше не сталкивался: APUS и DARE. Оба тоже опираются на RDMA, предложенное Наамой решение быстрее в 3 раза на базовом сценарии и в 12 раз в при leader election.

What we talk about when we talk about distributed systems — Alvaro Videla, в прошлом один из ключевых разработчиков RabbitMQ

Отличный обзорный доклад про то, как вообще начинать изучать распределённые системы — "Computing Science where Science is Still a Thing".

Вкратце пробежались по топикам: timing models, failure models, failure detectors, liveness & safety properties. Затем разобрали, о чём же собственно статья FLP и почему невозможность консенсуса в асинхронной модели не мешает реализовать его в жизни.

В конце доклада Альваро выдал отличные рекомендации по книгам, с которых можно начать погружение:

• Introduction to Reliable and Secure Distributed Programming.

• Distributed Algorithms.

• Guide to Reliable Distributed Systems.

• Distributed Algorithms for Message-Passing Systems.

• Replication.

• Fault-tolerant Agreement in Synchronous Message-passing Systems.

• Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems.

Посмотреть презентацию к докладу. 

Theoretical and practical worlds of failure detectors — Lena Hall, работает над Microsoft Azure

Первая «теоретическая» часть доклада посвящена обзору теоретических моделей Failure Detectors, рассмотрены свойства Completeness и Accuracy. Практическая часть в основном про то, как это сделано в Azure, если вкратце, то хартбиты и таймауты — наше всё.

Общее впечатление — воды многовато, ознакомиться с текстовой версией доклада можно на InfoQ.

Designing fast lock-free algorithms by understanding cache coherence dynamics — Adam Morrison, Tel Aviv University

Доклад можно описать как плавное подведение к проблеме, которую Адам с коллегами решили в 2013 году — проектированию более быстрой MP/MC lock-free очереди. На основе нескольких FAA CRQ, уложенных в связный список, им удалось сделать очередь, которая быстрее имеющихся lock-free альтернатив до 2,5 раз и производительность которой существенно меньше страдает от роста числа потоков — LCRQ.

Доклад состоял из трёх крупных частей.

Погружение в проблематику — здесь Адам рассказал про теоретическую модель, используемую для проектирования конкурентных алгоритмов, sequential model. Достаточно подробно разобрали реализацию классической lock-free очереди на основе связного списка и CAS-операций, затем сравнили её производительность с обычной блокирующей реализацией и увидели, что на большом числе конкурирующих потоков (>10) она сильно медленнее синхронной очереди.

Вторая часть доклада была посвящена выяснению причин такого поведения. Для этого был дан обзор протокола когерентности кэшей MSI, причина предсказуемо оказалась в cache contention на CAS-операциях. Для того чтобы её решить, было предложено перейти от CAS к FAA — третья часть была посвящена как раз этому.

Для начала Адам предложил спроектировать теоретическую модель очереди на основе FAA. Очередь спроектировали, но есть нюанс — модель опирается на бесконечный массив. В реальной жизни этого можно достичь, например, применив циклический буффер — практическая реализация носит имя CRQ (Cyclic Ring Queue). Если затем уложить такие очереди в связный список, то получится как раз LCRQ.

Simplifying global-scale strong consistency — Andras Gerlits, DianemoDB

Андрес поделился дизайном системы, разработкой которой он занимается последние 6 лет. Основные свойства хранилища: поддержка ANSI SQL, total ordering, линеаризуемость на уровне записей, возможность масштабирования на весь мир.

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

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

Описание всей системы целиком можно прочитать в pdf на сайте DianemoDB.

CAP Theorem — two decades and few clouds later — Mike Kowalski, Sii Poland

Отличный доклад про то, почему одной CAP-теоремы недостаточно для полного понимания гарантий, которые даёт вам система хранения данных.

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

Когда люди пишут, что Amazon S3 поддерживает strong consistency, что именно они имеют ввиду? Мы можем рассчитывать на read-your-own-writes на объектах, но только на eventual consistency на бакетах, а время репликации в другую локацию может достигать 15 минут. Что это? AP или AC?

Про Google Spanner говорят, что он опровергает CAP, беря от жизни всё. Однако в реальности у него не полная доступность всегда, а «всего лишь» 99.999%. Технически это CP-система, но на самом деле CA.

Kafka позволяет нам определять гарантии консистентности тонкой настройкой клиентов, а Cassandra и того пуще даёт возможность выбрать независимые гарантии для каждой операции. К какому классу их отнести?

Выбирая систему хранения данных для нашего проекта, мы должны принимать всё это во внимание. SLA is the new CAP!

Рекомендованные Майком ссылки:

• Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services.

• CAP Twelve Years Later: How the “Rules” Have Changed.

• A Critique of the CAP Theorem.

• Spanner, TrueTime & The CAP Theorem.

Ещё один взгляд на эту проблему — PIE.

Посмотреть презентацию к докладу.

Fearless global transactions with CockroachDB — Nathan VanBenschoten, Cockroach Labs

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

В качестве таковых Натан перечислил: 

• Consistency — ссылочная целостность между различными таблицами.

• Scalability — способность держать нагрузку 100k RPS+

• High Availability — умение переживать отказы от отдельного узла до целого региона.

• Low Latency — end2end time < 20 ms.

Дальше был рассказ про то, какая это непростая задача и как они этого добивались в CockroachDB, но всё общими словами. Если интересно как это всё устроено, то рекомендую почитать Architecture Overview, а так же можно пройти их курсы, ну или посмотреть доклад Натана от 2019 года, который, на мой взгляд, куда информативнее.

Co-designing Raft + thread-per-core execution model for the Kafka-API — Alex Gallego, RedPanda

Доклад был посвящён RedPanda — Kafka drop-in-replacement продукту, при разработке которого в первую очередь ставилась цель оптимизации хвостового latency за счёт полного использования возможностей современного железа.

Ребятам это явно удалось: ~3 ms average latency и 99.999% < 100 ms против 15 ms и 3 секунд соответственно у Kafka.

В основе архитектуры RedPanda лежат три кита: 

1. Thread-per-core, то есть на каждое ядро процессора запускается и пинится единственный поток. 

2. Отказ от использования виртуальной памяти — вся память преаллоцируется на старте. 

3. Полностью асинхронный input/output.

Если вам когда-нибудь понадобится система передачи сообщений с сильными гарантиями низкого latency — присмотритесь к RedPanda, она того явно стоит.

Презентация Алекса, где расписаны основные трюки и решения.

The hitchhiker's guide to distributed transactions — Irfan Sharif, Cockroach Labs

Ирфан рассказал о различных подходах к распределённым транзакциям. Если оставить за скобками описание самих механизмов, то весь доклад можно свести к табличке:

В презентации можно найти названия соответствующих статей и коротенькое описание свойств механизма на пальцах.

The official ten-year retrospective of NewSQL databases — Andy Pavlo, Carnegie Mellon University

NewSQL базы сочетают в себе возможности масштабирования, присущие NoSQL, но также обеспечивают и ACID-гарантии, свойственные классическим реляционным базам. Сам термин NewSQL скорее мёртв чем жив — теперь все говорят, что они Distributed SQL.

Большинство компаний, разрабатывавших NewSQL базы данных, канули в небытие. Из относительно устойчивых и доступных для использования можно вспомнить Cockroach, Yugabyte и TiDB. Энди считает, что будущее таких баз скорее в облаках.

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

Посмотреть презентацию к докладу.