На ютубе опубликовали записи с конференции omg 2021. Я смотрел конференцию онлайн и написал abstract самых полезных и интересных докладов. Возможно, вам они тоже пригодятся и помогут в работе.Distributed systems showdown —
спрут TLA+ vs real code — Jack Vanlightly, работает над Apache Pulsar и BookKeeperОбзорный доклад про плюсы и минусы, а также реальное применение моделирования при разработке распределённых систем.TLA+ можно и нужно применять для проверки протоколов взаимодействия. За счёт полного перебора всех возможных состояний системы он позволяет относительно небольшим объёмом декларативного кода убедиться в том, что не допущено ошибок в самой модели взаимодействия компонент.Maelstrom применяется для стресс-тестирования модели системы на произвольном языке, позволяя отложить в сторону необходимость полноценной работы с сетью. С помощью Maelstrom можно протестировать, что система ведёт себя ожидаемым образом, то есть соблюдает гарантии целостности в том числе и в случае проблем с сетью. Maelstrom как раз заведует поломками: он рвёт линки между тестируемыми компонентами, увеличивает latency, теряет сообщения и вообще всячески пытается гадить, что приводит к «ускорению времени» с точки зрения проявления ошибок.Джек рекомендует следовать следующему пайплайну разработки:Валидируем идею с помощью TLA+.Инкрементально пишем реализацию системы — сначала даже без репликации, система может состоять из одного узла, — и сразу же тесты для неё в 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
sprutnet микросекунды в лучшем случае и 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 и почему невозможность консенсуса в асинхронной модели не мешает реализовать его в жизни.В конце доклада Альваро выдал отличные рекомендации по книгам, с которых можно начать погружение:Посмотреть презентацию к докладу. 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 очереди
com на основе связного списка и 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!Рекомендованные Майком ссылки:Ещё один взгляд на эту проблему — 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 лежат три кита: Thread-per-core, то есть на каждое ядро процессора запускается и пинится единственный поток. Отказ от использования виртуальной памяти — вся память преаллоцируется на старте. Полностью асинхронный input/output.Если вам когда-нибудь понадобится система передачи сообщений с сильными гарантиями низкого latency — присмотритесь к RedPanda, она того явно стоит.Презентация Алекса, где расписаны основные трюки и решения.The hitchhiker's guide to distributed transactions — Irfan Sharif, Cockroach LabsИрфан рассказал о различных подходах к распределённым транзакциям. Если оставить за скобками описание самих механизмов, то весь доклад можно свести к табличке:Spanner/Pipelined Transactions2 WAN RTTParallel Commits 1 WAN RTTReplicated Commit 1 WAN + LAN RTTCarousel 1 WAN RTTMDCC 1 WAN RTTSLOG/OceanVista 1 WAN + LAN RTTTAPIR 1 WAN RTTВ презентации можно найти названия соответствующих статей и коротенькое описание свойств механизма на пальцах.The official ten-year retrospective of NewSQL databases — Andy Pavlo, Carnegie Mellon UniversityNewSQL базы сочетают в себе возможности масштабирования, присущие NoSQL, но также обеспечивают и ACID-гарантии, свойственные классическим реляционным базам. Сам термин NewSQL скорее мёртв чем жив — теперь все говорят, что они Distributed SQL.Большинство компаний, разрабатывавших NewSQL базы данных, канули в небытие. Из относительно устойчивых и доступных для использования можно вспомнить Cockroach, Yugabyte и TiDB. Энди считает, что будущее таких баз скорее в облаках. В целом доклад — исторический обзор мира баз данных, напоминающий чтение учебника истории, когда короли сменяют друг друга, а жизнь вокруг них продолжала идти своим чередом.Посмотреть презентацию к докладу.
