11-12 июля в Санкт-Петербурге состоится конференция Hydra, посвященная разработке параллельных и распределенных систем. Фишка Гидры в том, что она объединяет крутых учёных (которых обычно можно найти только на зарубежных научных конференциях) и известных практикующих инженеров, в одну большую программу на стыке науки и практики.

Hydra — одна из самых важных наших конференций за последние несколько лет. Ей предшествовала очень серьёзная подготовка, отбор спикеров и докладов. На прошлой неделе об этом вышло хаброинтервью с директором компании JUG.ru Group, Алексеем Федоровым (23derevo).

Мы уже рассказывали о трёх важных участниках, основоположниках теории распределенных систем — Лесли Лэмпорте, Морисе Херлихи и Майкле Скотте. Настало время более подробно поговорить о всей программе!

Мотивация

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

Существует множество конференций, раскрывающих те или иные аспекты прикладного программирования. На другой стороне спектра у нас специальные научные школы, в формате лекций раскрывающие огромные объемы сложной теории. Например, параллельно с Hydra в Питере проходит школа SPTDC. На конференции Hydra мы постарались свести вместе и суровую практику, и науку, и всё, что на их стыке.

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

С другой стороны, возможность встретиться с ними обычно остаётся чисто теоретической: мало кто из нас может постоянно мониторить публичные события в каком-нибудь Рочестерском университете, чтобы потом метнуться в США и обратно на лекцию к Майклу Скотту. Посетить вообще всех участников Hydra вышло бы в небольшое состояние, не считая бездны потраченного времени (хотя это звучит как интересный квест).

С другой стороны, у нас есть множество топовых инженеров, которые прямо сейчас работают над актуальными проблемами распределённых систем, и им точно есть что рассказать. Но вот проблема — они работают, и их время дорого. Да, если ты сотрудник Microsoft, Google или JetBrains, вероятность встретить одного из известных спикеров на внутреннем мероприятии — резко возрастает, а вообще — нет, не каждый день это бывает.

Таким образом конференция Hydra выполняет важную задачу, которую большинство из нас не могут сделать сами — в одном месте и в одно время объединяет людей, идеи которых или общение с которыми может изменить вашу жизнь. Допускаю, что совершенно не всем нужны распределённые системы, какие-то сложные фундаментальные вещи. Можно до конца жизни программировать CRUD-ы на PHP и оставаться вполне счастливым. Но кому нужны — это ваш шанс.

С первого анонса конференции Hydra на Хабре прошло уже довольно много времени. За это время, проделана огромная работа — и вот, у нас есть список почти всех докладов. Никаких вяленьких однопоточных алгоритмов, только чистый распределённый хардкор! Давайте заканчивать с общими словами, и посмотрим, что у нас теперь на руках.

Кейноуты

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

Cliff Click — The H2O distributed K/V algorithm

Клифф — легенда Java-мира. В конце 90-х годов для PhD-тезиса он написал работу под названием «Combining Analyses, Combining Optimizations», которая через некоторое время стала основой для HotSpot JVM Server Compiler. Через два года он уже работал в Sun Microsystems над JVM и показал всему миру, что JIT имеет право на существование. Вся эта история о том, что Java — один из быстрейших современных рантаймов с самыми умными и быстрыми оптимизациями пошла именно с Клиффа Клика. В самом начале считалось, что, если что-то доступно статическому компилятору — это можно даже не пытаться джитить. Благодаря работам Клиффа и команды, все новые языки начали создаваться с идеей о JIT-компиляции по умолчанию. Безусловно, это была работа не для одного человека, но Клифф сыграл в ней очень важную роль.

В открывающем кейноуте Клифф расскажет о другом своём начинании — H20, in-memory платформе для распределённого и масштабируемого машинного обучения для промышленного применения. А точней — о распределённом хранилище пар «ключ-значение» внутри неё. Это очень быстрое хранилище с массой интересных свойств (точный список есть в описании), которые позволяют использовать подобные решения в математике стриминга больших данных.

Ещё один доклад, с которым выступит Клифф — The Azul Hardware Transactional Memory experience. Другая часть его биографии — десять лет работы в Azul, где он обновил и улучшил много всего в железе и стеке технологий Azul: JIT-компиляторы, рантайм, тредовую модель, обработку ошибок, работу со стеком, аппаратные прерывания, загрузку классов и так далее и тому подобное — ну, вы поняли.

Самая интересная часть началась, когда они сделали железо для большого бизнеса — суперкомпьютер для запуска Java. Это была довольно инновационная штука, заточенная именно под Java, у которой есть специальные требования — барьеры памяти на чтение для низкопаузной сборки мусора, массивы с проверкой границ, виртуальные вызовы… Одна из наиболее крутых технологий — аппаратная транзакционная память. Весь L1 любого из 864 ядер мог участвовать в транзакционной записи, что особенно важно для работы с блокировками в Java (synchronized-блоки могут работать параллельно, до тех пор, пока нет реального конфликта по памяти). Но красивая идея разбилась о суровую реальность — и в этом докладе Клифф расскажет, почему HTM и STM не очень хорошо подходят для практических нужд многопоточных вычислений.

Michael Scott — Dual data structures

Майкл Скотт — профессор Computer Science в Рочестерском университете, с которым судьба связала его уже на 34 года, а в родном универститете Wisconsin–Madison, был деканом в течение пяти лет. Он занимается исследованиям в области параллельного и распределённого программирования и дизайна языков и обучает этому студентов.

Весь мир знает Майкла благодаря учебнику «Programming Language Pragmatics», последнее издание которого вышло сравнительно недавно — в 2015 году. Его работа «Algorithms for scalable synchronization on shared-memory multiprocessors» получила премию Дейкстры как одна из наиболее известных в области распределённых вычислений и открыто лежит в онлайн-библиотеке Рочестерского Университета. Также вы можете знать его как автора того самого алгоритма Майкла-Скотта из «Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms».

Что касается Java-мира, то тут случай особый: вместе с Doug Lea он разработал те неблокирующие алгоритмы и синхронные очереди, на которых работают библиотеки Java. Именно об этом и будет кейноут «Dual data structures» — внедрение этих структур в Java SE 6 позволило в 10 раз улучшить производительность java.util.concurrent.ThreadPoolExecutor. Если вам заранее интересно, что такое эти самые «Dual data structures», то про это есть соответствующая работа.

Maurice Herlihy — Blockchains and the future of distributed computing

Морис Херлихи — обладатель целых двух премий Дейкстры. Первая — за работу по «Wait-Free Synchronization» (Brown University), и вторая, более свежая — «Transactional Memory: Architectural Support for Lock-Free Data Structures» (Virginia Tech University). Премию Дейкстры дают за работы, значимость и влияние которых были заметны на протяжении не менее десяти лет, и очевидно, Морис — один из самых известных специалистов в области. В данный момент он работает профессором в Брауновском университете и имеет множество достижений на целый абзац длиной.

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

В июле 2017 года Морис уже приезжал в Россию на школу SPTDC, участвовал в митапе JUG.ru, и запись можно посмотреть на YouTube:

Основная программа

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

Leslie Lamport — Q & A

Лесли Лэмпорт — автор основополагающих работ в распределённых вычислениях. «LaTeX» расшифровывается как «Lamport TeX». Это он впервые, ещё в 1979 году, ввёл понятие последовательной согласованности, а его статья «How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs» получила премию Дейкстры.

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

Идея простая — вы смотрите на YouTube два доклада: «Programming Should Be More Than Coding» и «If You're Not Writing a Program, Don't Use a Programming Language» и готовите хотя бы один вопрос, а Лесли отвечает.

Первое из этих двух видео мы уже превратили в хабростатью. Если у вас нет часа времени на просмотр видео, можно быстренько прочитать всё это в виде текста.

На заметку: на YouTube есть куда больше видео с Лесли Лэмпортом. Например, есть отличный курс по TLA+. Оффлайн-версия всего этого курса есть на домашней страничке автора, а на YouTube он его перелил для более удобного просмотра на мобильных девайсах.

Martin Kleppmann — Syncing data across user devices for distributed collaboration

Мартин Клеппманн — исследователь в Кембриджском университете, работающий над CRDT и формальной верификацией алгоритмов. Книга Мартина «Designing Data-Intensive Applications», опубликованная в 2017 году, оказалась очень успешной и попала в списки бестселлеров в области хранения и обработки данных. Кевин Скотт, CTO в Microsoft, однажды сказал: «Эта книга должна быть обязательной для инженеров-разработчиков. Это редкий ресурс, объединяющий теорию и практику, помогающий разработчикам умнее дизайнить и реализовывать инфраструктуру и системы обработки данных». Что-то похожее говорил и создатель Kafka и CTO Confluent, Джей Крепс.

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

• Rapportive, посвященный отображению социального профиля контактов из вашей электронной почты, который LinkedIn купили в 2012 году;
• Go Test It, сервис для автоматической проверки веб-сайтов в различных браузерах, который RedGate купили в 2009 году.

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

В этом докладе Мартин будет рассказывать о теме, более близкой к его академическим исследованиям. В Google Docs и похожем софе для совместного редактирования документов, «совместное редактирование» означает задачу репликации: каждый пользователь имеет собственную реплику общего документа, которую они потом изменяют, и все изменения рассылаются по сети остальным участникам. Изменения документов в оффлайне приводит ко временной неконсистентности документа по отношению к остальным участникам, и пере-синхронизация требует обработки конфликтов. Как раз для этого существуют Conflict-free Replicated Data Types (CRDT), по сути — довольно новая штука, суть которой сформулировали всего лишь в 2011 году. В этом докладе обсуждается, что произошло с тех пор в мире CRDT, каковы самые последние достижения, обсуждается подход к созданию local-first приложений вообще и использование опенсорсной библиотеки Automerge в частности.

На следующей неделе мы опубликуем на Хабре большое интервью с Мартином, будет интересно.

Pedro Ramalhete — Wait-free data structures and wait-free transactions

Педро работает в Cisco и разрабатывает параллельные алгоритмы последние лет эдак десять, включая механизмы синхронизации, lock-free и wait-free структуры данных и всё, что вы можете представить на эту тему. Его текущие научные и инженерные интересы сфокусированы на Universal Constructions, Software Transactional Memory, Persistent Memory и подобных технологиях, позволяющих реализовывать корректные, масштабируемые и отказоустойчивые приложения. А ещё он — автор широко известного в узких кругах блога Concurrency Freaks.

На параллельных структурах данных сейчас работает большинство многопоточных приложений, начиная с использований очередей сообщений между акторами и заканчивая индексированными структурами данных в key-value хранилищах. В Java JDK они успешно работают в течение многих лет, да и в C++ потихоньку добавляются.

Простейший способ реализовать параллельную структуру данных — последовательная (однопоточная) реализация, в которой методы защищены мьютексами. Это доступно любому джуну, но имеет очевидные проблемы с масштабированием и производительностью. В то же время, lock-free и wait-free структуры данных не только лучше справляются с ошибками, но и имеют более удачный профиль производительности — однако, для их разработки требуется глубокая экспертиза и адаптация под конкретный способ применения. Одной неправильной строчки кода хватит, чтобы всё сломать.

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

Heidi Howard — Liberating distributed consensus

Хайди Говард — как и Мартин, исследователь распределённых систем в Кембриджском университете. Её специализация — консистентность, отказоустойчивость, производительность и распределённый консенсус. Она наиболее известна обобщением алгоритма Paxos под названием Flexible Paxos.

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

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

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

Alex Petrov — Reduce your storage costs with Transient Replication and Cheap Quorums

Алекс — специалист по базам данных и системам хранения, и что важней для нас — коммитер в Cassandra. Вместе с O'Reilly он прямо сейчас работает над книгой Database Internals.

Для систем с eventual consistency (в русскоязычной терминологии — «согласованностью в конечном счёте»), после падения узла или разделения сети, нужно решить следующую дилемму: то ли продолжать выполнять запросы, пожертвовав консистентностью, то ли отказать в их выполнении и пожертвовать доступностью. В такой системе кворумы, перекрывающиеся подмножества узлов и гарантирующие, что по крайней мере один узел будет содержать самое последнее значение, могут стать хорошим пограничным решением. Можно пережить сбои и потерю соединения до некоторых узлов, продолжая отвечать самыми свежими значениями.

Тем не менее, всё имеет свою цену. Кворумная схема репликации означает повышенную стоимость хранения: необходимо хранить избыточные данные на нескольких узлах сразу, чтобы гарантировать достаточное количество доступных копий на момент возникновения проблемы. Оказывается, можно не хранить все данные на всех репликах. Можно уменьшить нагрузку на хранилище, если держать данные только на части узлов, а для сценариев обработки сбоев использовать специальные ноды (Transient Replica).

По ходу доклада мы рассмотрим Witness Replicas, схему репликации используемую в Spanner и Megastore, и реализацию данной концепции в Apache Cassandra под названиями Transient Replication & Cheap Quorums.

Дмитрий Вьюков — Goroutines exposed

Дмитрий — разработчик в Google, работающий над динамическим тестированием C/C++ и Go — Address/Memory/ThreadSanitizer, и над похожими инструментами для ядра Linux. Законтрибьютил в Go масштабируемый планировщик горутин, network poller и параллельный сборщик мусора. Является экспертом в многопоточности, автором дюжины новых неблокирующих алгоритмов и является обладателем Черного Пояса Intel.

Теперь немного о самом докладе. В языке Go присутствует нативная поддержка многопоточности в форме горутин (легких тредов) и каналов (очередей FIFO). Благодаря этим механизмам пользователям очень легко и приятно писать современные многопоточные приложения, и это выглядит как магия. Как мы понимаем, никакой магии здесь нет. В этом докладе Дмитрий углубится в тонкости работы планировщика Go и покажет секреты реализации этой «магии». Вначале он даст обзор основных компонентов планировщика, расскажет, как оно работает. Дальше мы ближе познакомимся с отдельными аспектами вроде стратегии парковки/распарковки и обработки блокирующих системных вызовов. Наконец, Дмитрий немного расскажет о возможных улучшениях в планировщике.

Дмитрий Бугайченко — Ускоряем распределенный анализ графов с помощью вероятностных скетчей и не только

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

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

Денис Рысцов — Reduce your storage costs with Transient Replication and Cheap Quorums

Денис — разработчик Cosmos DB, эксперт в области проверки моделей консистентности, в алгоритмах консенсуса и в распределённых транзакциях. Сейчас он работает в Microsoft, а до этого занимался распределёнными системами в Amazon и Yandex.

В этом докладе мы познакомимся с протоколами распределенных транзакций, придуманными за последние несколько лет, которые возможно реализовать на клиентской стороне поверх любого хранилища данных, поддерживающего условное обновление (compare and set). Суть в том, что жизнь не заканчивается двухфазным коммитом, транзакции можно добавить поверх любых баз данных — на уровне приложения, но разные протоколы (2PC, Percolator, RAMP) имеют разные трейдоффы и не даются нам бесплатно.

Алексей Зиновьев — Не все ML-алгоритмы попадают в распределенный рай

Алексей (zaleslaw) — наш давний спикер и член программных комитетов на других конференциях. Практикующий тренер в компании EPAM Systems, и с Hadoop/Spark и прочей бигдатой дружит с 2012 года.

В этом докладе Алексей расскажет о проблемах адаптации классических алгоритмов машинного обучения для выполнения в распределенном режиме на основе своего опыта работы с Apache Spark ML, Apache Mahout, Apache Flink ML и опыта создания Apache Ignite ML. Также Алексей расскажет о реализации распределенных ML-алгоритмов в этих фреймворках.

И в завершение — два доклада от компании Yandex про Yandex Database.

Владислав Кузнецов — Yandex Database — как мы обеспечиваем отказоустойчивость

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

Семен Чечеринда — Распределенные транзакции в YDB

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

Yandex Database рассчитана на OLTP-запросы и соответствует требованиям ACID к транзакционной системе. В докладе рассмотрим алгоритм планирования транзакций, лежащий в основе транзакционной системы YDB. Разберем, какие сущности участвуют в транзакциях, кто назначает транзакциям глобальный порядок, как достигается атомарность транзакций, надежность и строгий уровень изоляции. На примере распространенной задачи рассмотрим реализации транзакций с применением двухфазного коммита и детерминистических транзакций. Обсудим их различия.

Что дальше?

Программа конференции продолжает наполняться новыми докладами. В частности, мы ожидаем доклад от Никиты Коваля (ndkoval) из JetBrains и Олега Анастасьева (m0nstermind) из компании Одноклассники. Никита занимается алгоритмами для корутин в команде Kotlin, а Олег разрабатывает архитектуру и решения для высоконагруженных систем в платформе компании Одноклассники. Кроме того, есть ещё 1 условно пустой слот, с кандидатами на который прямо сейчас работает программный комитет.

Конференция Hydra состоится в 11-12 июля в Санкт-Петербурге. Билеты можно приобрести на официальном сайте. Обращаем внимание на наличие Online-билетов — если вы почему-то не можете вживую добраться до Питера в эти дни.

Встретимся на Hydra!