19 головы на хидрата. Голям преглед на програмата

Конференция ще се проведе в Санкт Петербург на 11-12 юли Хидра, посветена на разработването на паралелни и разпределени системи. Уникалността на Хидра е, че обединява страхотни учени (които обикновено могат да бъдат намерени само на чуждестранни научни конференции) и известни практикуващи инженери в една голяма програма на кръстопътя между науката и практиката.

Хидра е една от най-важните ни конференции през последните няколко години. На нея предшествува много сериозна подготовка, подбор на говорители и доклади. Миналата седмица по този въпрос излезе хаброинтервю с директора на компанията JUG.ru Group, Алексей Фьодоров (23derevo).

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

Мотивация

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

Съществуват много конференции, които разглеждат определени аспекти на приложното програмиране. От другата страна на спектъра имаме специализирани научни школи, които в лекционен формат разкриват огромни обеми сложна теория. Например, паралелно с Хидра в Питър се провежда школа SPTDC. На конференцията Хидра се опитахме да съберем заедно строгата практика, науката и всичко, което е на техния кръстопът.

Помислете за това: живеем в удивително време, когато можем на живо да срещнем основателите на областта на науката и инженерството, с които се занимаваме. Физиците не могат да се срещнат с Нютон или Айнщайн — влакът е тръгнал. Но все още имаме хора, които създадоха основите на теорията за разпределени системи, измислиха популярни програмни езици и първи реализираха всичко това в работещи прототипи. Тези хора не са оставили работата си наполовина, в момента те работят по актуални задачи в световноизвестни университети и компании и са най-великите източници на знания и опит в днешно време.

От друга страна, възможността да се срещнем с тях обикновено остава чисто теоретична: малко от нас могат да следят публичните събития в някой университет в Рочестър, за да могат след това да се метнат в САЩ и обратно на лекция при Майкъл Скот. Посещение на всички участници в Hydra би струвало цяло състояние, да не говорим за бездната на загубеното време (въпреки че това звучи като интересен квест).

От друга страна, имаме много топ инженери, които в момента работят по актуални проблеми на разпределените системи и те със сигурност имат какво да споделят. Но проблемът е — те работят, и времето им е скъпо. Да, ако си служител на Microsoft, Google или JetBrains, вероятността да срещнеш един от известните говорители на вътрешно събитие — рязко се увеличава, а иначе — не става всеки ден.

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

От първия анонс на конференцията Hydra на Хабр премина доста време. През това време е направена огромна работа — и ето, имаме списък почти на всички доклади. Никакви слаби однопоточни алгоритми, само чист разпределен хардкор! Нека да приключим с общите думи и да видим какво имаме сега.

Кейноутите

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

Cliff Click — Алгоритъмът H2O за разпределено K/V

Клиф е легенда в света на Java. В края на 90-те години за докторската си дисертация той написа работа със заглавие «Съчетаване на анализи, съчетаване на оптимизации», който след време стана основа за 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 не са много подходящи за практическите нужди на многопоточните изчисления.

Майкъл Скот — Двойни структури от данни

Майкъл Скот — професор по Компютърни науки в Рочестърския университет, с който съдбата го свързва от цели 34 години, а в родния си университет Уисконсин–Мадисън, той е бил декан за пет години. Той извършва изследвания в областта на паралелното и разпределено програмиране и дизайна на езици и обучава студенти в това.

Целият свят познава Майкъл благодарение на учебника «Programming Language Pragmatics», последното издание на който излезе съвсем наскоро — през 2015 година. Неговата работа «Algorithms for scalable synchronization on shared-memory multiprocessors» п получи награда Дейкстра като една от най-известните в областта на разпределените изчисления и открито лежи в онлайн библиотеката на Рочестърския университет. Можете също да го познавате като автора на алгоритма на Майкъл Скот от «Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms».

Що се отнася до света на Java, тук случаят е особен: заедно с Дъг Ля той разработи онези неблокиращи алгоритми и синхронни опашки, върху които работят библиотеките на Java. Именно за това ще говори в кейноута «Двойни структури от данни» — внедряването на тези структури в Java SE 6 позволи десетократно подобряване на производителността java.util.concurrent.ThreadPoolExecutor. Ако вече сте любопитни какво представляват тези «Двойни структури от данни», за това има съответна работа.

Морис Херлихи — Блокчейни и бъдещето на разпределеното компютърно изчисление

Морис Херлихи — носител на цели две награди Дейкстра. Първата — за работа по «Wait-Free Synchronization» (Университет Браун), и втората, по-нова — «Transactional Memory: Architectural Support for Lock-Free Data Structures» (Университет Вирджиния Тек). Наградата Дейкстра се дава за работи, значимостта и влиянието на които са били забележими в продължение на поне десет години, и очевидно, Морис — един от най-известните специалисти в областта. В момента той работи като професор в Университета на Браун и има множество постижения, водещи до цял абзац.

В този заключителен кейноут Морис ще разкаже за теорията и практиката на блокчейн разпределени системи от гледна точка на класическите разпределени изчисления и как това опростява множество свързани проблеми. Това е доклад изцяло по темата на конференцията — съвсем не за майнинг хипа, а по-скоро за това как нашите знания могат да бъдат изумително ефективно и подходящо използвани за различни задачи.

През юли 2017 г. Морис вече беше идвал в Русия за училище SPTDC, участва в митапа JUG.ru, а записът може да се види в YouTube:

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

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

Лесли Лампорт — Въпроси и отговори

Лесли Ламперт е автор на основополагаещи работи в разпределените изчисления. «LaTeX» означава «Lamport TeX». Той за пръв път, още през 1979 г., въведе понятието последователна последователност, а статията му «Как да направим мултипроцесорен компютър, който правилно изпълнява мултипроцесорни програми» получи наградата Дейкстра.

Това е най-необичайната част от програмата по формат, защото това не е дори доклад, а сесия с въпроси и отговори. Когато значителна част от аудиторията е вече запозната (или може да се запознае) с различни работи, свързани с «теорията на Лампорта», неговите собствени статии и доклади, е много важно да се използва цялото налично време за директна комуникация.

Идеята е проста — гледате в YouTube два доклада: «Програмирането трябва да е повече от кодиране» и «Ако не пишете програма, не използвайте език за програмиране» и подготвяте поне един въпрос, а Лесли отговаря.

Първото от тези две видео вече го превърнахме в хабро статия. Ако нямате час време да гледате видеото, можете бързо да прочетете всичко това под формата на текст.

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

Мартин Клеппман — Синхронизиране на данни между потребителски устройства за разпределено сътрудничество

Мартин Клеппман е изследовател в Кеймбриджкия университет, който работи върху CRDT и формална верификация на алгоритми. Книгата на Мартина «Проектиране на данни-интензивни приложения», публикувана през 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 в частност.

Следващата седмица ще публикуваме в Хабра голямо интервю с Мартин, със сигурност ще е интересно.

Педро Рамалете — Структури от данни без изчакване и транзакции без изчакване

Педро работи в Cisco и разработва паралелни алгоритми вече около десет години, включително механизми за синхронизация, lock-free и wait-free структури от данни и всичко, което можете да си представите по темата. Текущите му научни и инженерни интереси са фокусирани върху Универсалните конструкции, Софтверна транзакционна памет, Персистентна памет и подобни технологии, които позволяват реализирането на коректни, мащабируеми и отказоустойчиви приложения. Освен това той е автор на широко известен блог в тесни кръгове. Concurrency Freaks.

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

Най-простият начин за реализиране на паралелна структура от данни е последователната (еднопоточна) реализация, при която методите са защитени с мютекси. Това е достъпно за всеки джун, но има очевидни проблеми с мащабирането и производителността. В същото време, lock-free и wait-free структури от данни не само, че по-добре се справят с грешките, но и имат по-успешен профил на производителност – обаче, за тяхното разработване е необходима дълбока експертиза и адаптация към конкретния начин на приложение. Една неправилна линия код е достатъчна, за да се счупи всичко.

Как да направим така, че дори неексперт да може да проектира и реализира такива структури от данни? Известно е, че всеки последователен алгоритъм може да бъде направен потокобезопасен чрез или универсална конструкция, или транзакционна памет. И двете могат да понижат прага на входа за решаване на тази задача. Въпреки това, и двете решения обикновено водят до неефективна реализация. Педро ще разкаже как успяха да направят тези конструкции по-ефективни и как могат да ги използват за своите алгоритми.

Хайди Хауърд – Либериращо разпределено съгласие

Хайди Говард - подобно на Мартин, е изследовател на разпределени системи в Кеймбриджкия университет. Нейната специализация е консистентност, отказоустойчивост, производителност и разпределено съгласие. Тя е най-известна с обобщението на алгоритъма Paxos, наречено Гъвкав Paxos.

Напомняме, че Paxos — набор от протоколи за решаване на консенсус в мрежа от ненадеждни изчислители, основаващи се на работата на Лесли Лампорта. По този начин, нашите докладчици работят по задачи, първоначално предложени от други наши докладчици — и това е прекрасно.

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

В този доклад ще преразгледаме теоретичната основа на Paxos, отслабвайки първоначалните изисквания и обобщавайки алгоритъма. Ще видим, че Paxos всъщност е само един от вариантите в огромния спектър от подходи за консенсус, и че други точки в спектъра също могат да бъдат много полезни за изграждане на добри разпределени системи.

Алекс Петров — Намалете разходите за съхранение с Преходна репликация и евтини кворуми

Алекс е специалист по бази данни и системи за съхранение, и най-важното за нас — комитър в Cassandra. С O’Reilly той в момента работи върху книга за Вътрешностите на базите данни.

За системи с 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 за мащабируем планировчик на горутини, мрежов пулер и паралелен сборник на боклука. Той е експерт в многопоточността, автор на дузина нови неблокиращи алгоритми и притежател на Черния пояс Intel.

Сега малко за самия доклад. В езика Go има вградена поддръжка за многопоточност под формата на горутини (леки нишки) и канали (FIFO опашки). Благодарение на тези механизми, на потребителите е много лесно и приятно да пишат съвременни многопоточни приложения и то изглежда като магия. Както разбираме, в това няма никаква магия. В този доклад Дмитрий ще задълбочи детайлите на работата на планировчика на Go и ще покаже тайните на реализирането на тази „магия“. В началото той ще даде преглед на основните компоненти на планировчика, ще разкаже как работи. След това ще се запознаем по-отблизо с отделни аспекти, като стратегии за паркиране/разпаркиране и обработка на блокиращи системни повиквания. Накрая Дмитрий ще разкаже малко за възможните подобрения в планировчика.

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

Дмитрий е работил почти 9 години в аутсорсинг, без да губи контакт с университета и научната среда. Анализът на големи данни в Однокласниците му предостави уникален шанс да комбинира теоретичната подготовка и научната основа с разработването на реални, търсени продукти.

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

Денис Рысцов — Намалете разходите за съхранение с Преходна репликация и евтини кворуми

Денис — разработчик 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 юли в Санкт Петербург. Билети могат да бъдат закупени от официалния сайт. Обращаме внимание на наличието на онлайн билети — ако поради някаква причина не можете лично да се доберете до Питър в тези дни.

Ще се срещнем на Hydra!

Източник: habr.com