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

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

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

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

Мотивиране

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

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

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

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

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

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

Измина доста време от първото съобщение за конференцията Hydra на Habré. През това време беше свършена много работа - и сега имаме списък на почти всички доклади. Без бавни еднонишкови алгоритми, просто чист разпределен хардкор! Нека завършим с общи думи и да видим какво имаме в ръцете си сега.

Ключови бележки

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

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

Клиф е легенда в света на Java. В края на 90-те години, за своята докторска дисертация, той написва доклад, озаглавен „Комбиниране на анализи, комбиниране на оптимизации“, който известно време по-късно стана основата на HotSpot JVM Server Compiler. Две години по-късно той вече работеше в Sun Microsystems върху JVM и показа на целия свят, че JIT има право на съществуване. Цялата тази история за това как Java е едно от най-бързите съвременни времена за изпълнение с най-умните и най-бързи оптимизации дойде от Cliff Click. В самото начало се смяташе, че ако нещо е достъпно за статичен компилатор, дори не е нужно да се опитвате да го изтриете. Благодарение на работата на Cliff и екипа, всички нови езици започнаха да се създават с идеята за JIT компилация по подразбиране. Разбира се, това не беше работа на един човек, но Клиф изигра много важна роля в нея.

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

Друг доклад, който Клиф ще даде е... Изживяването на Azul Hardware Transactional Memory. Друга част от биографията му - десет години работа в Azul, където той актуализира и подобри много неща в хардуерния и технологичния стек на Azul: JIT компилатори, време за изпълнение, модел на нишка, обработка на грешки, обработка на стек, хардуерни прекъсвания, зареждане на класове и така нататък и така нататък - добре, получавате идея.

Най-интересната част започна, когато направиха хардуер за голям бизнес - суперкомпютър, който да работи с Java. Беше доста иновативно нещо, пригодено специално за Java, която има специални изисквания - бариери за четене на паметта за събиране на отпадъци с ниска пауза, масиви с проверка на граници, виртуални разговори... Една от най-готините технологии е хардуерната транзакционна памет. Целият L1 на което и да е от 864-те ядра може да участва в писането на транзакции, което е особено важно за работа с ключалки в Java (синхронизираните блокове могат да работят паралелно, стига да няма реален конфликт на паметта). Но красивата идея беше смазана от суровата реалност - и в този разговор Клиф ще ви каже защо HTM и STM не са много подходящи за практическите нужди на многонишковите изчисления.

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

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

Целият свят познава Майкъл благодарение на учебника "Прагматика на езика за програмиране", чието последно издание беше публикувано сравнително наскоро - през 2015 г. Неговата работа „Алгоритми за мащабируема синхронизация на мултипроцесори със споделена памет“ получих Награда Дейкстра като един от най-известните в областта на разпределените изчисления и лъже открито в онлайн библиотеката на университета в Рочестър. Може да го познавате и като автор на самия алгоритъм на Майкъл-Скот от „Прости, бързи и практични неблокиращи и блокиращи паралелни алгоритми за опашка“.

Що се отнася до света на Java, това е специален случай: заедно с Дъг Леа той разработи неблокиращи алгоритми и синхронни опашки, върху които работят библиотеките на Java. Това е точно това, за което ще бъде основната бележка „Двойни структури от данни“ - въвеждането на тези структури в Java SE 6 подобри производителността с 10 пъти java.util.concurrent.ThreadPoolExecutor. Ако се чудите предварително какво представляват тези „Двойни структури от данни“, значи има информация за това свързани с тях дейности.

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

Морис Херлихи - носител на две награди Дейкстра. Първият е за работа „Синхронизация без изчакване“ (Университет Браун), а вторият, по-скорошен - „Транзакционна памет: Архитектурна поддръжка за структури от данни без заключване“ (Технологически университет на Вирджиния). Наградата Dijkstra отличава работа, чието значение и въздействие са видими от поне десет години, а Морис очевидно е един от най-известните експерти в тази област. В момента работи като професор в университета Браун и има дълъг списък с постижения.

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

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

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

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

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

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

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

Идеята е проста - гледате два репортажа в YouTube: „Програмирането трябва да е нещо повече от кодиране“ и „Ако не пишете програма, не използвайте език за програмиране“ и подготви поне един въпрос, а Лесли отговаря.

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

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

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

Мартин Клепман е изследовател в университета в Кеймбридж, работещ върху CRDT и формална проверка на алгоритми. Книгата на Мартин „Проектиране на приложения с интензивно използване на данни“, издаден през 2017 г., се оказа много успешен и попадна в списъците на бестселъри в областта на съхранението и обработката на данни. Кевин Скот, технически директор в Microsoft, веднъж каза: „Тази книга трябва да бъде задължителна за софтуерните инженери. Това е рядък ресурс, който съчетава теория и практика, за да помогне на разработчиците да бъдат по-умни при проектирането и внедряването на инфраструктура и системи за данни.“ Създателят на Kafka и технически директор на Confluent, Джей Крепс, каза нещо подобно.

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

• Rapportive, посветен на показването на социалния профил на контакти от вашия имейл, който LinkedIn закупи през 2012 г.;
• Go Test It, услуга за автоматично тестване на уебсайтове в различни браузъри, която RedGate закупи през 2009 г.

Като цяло, Мартин, макар и по-малко известен от нашите ключови бележки, вече успя да даде известен принос за развитието на разпределените изчисления и за индустрията.

В тази лекция Мартин ще говори за тема, по-близка до неговите академични изследвания. В Google Документи и подобни дивани за съвместно редактиране на документи „съвместното редактиране“ се отнася до задача за репликация: всеки потребител има своя собствена реплика на споделения документ, който след това модифицира, и всички промени се изпращат през мрежата до останалата част от участници. Промените в документите офлайн водят до временна несъответствие на документа по отношение на други участници и повторното синхронизиране изисква обработка на конфликти. Точно за това съществуват Безконфликтни репликирани типове данни (CRDT) всъщност е сравнително ново нещо, чиято същност е формулирана едва през 2011 г. Този разговор обсъжда какво се е случило оттогава в света на CRDT, какви са най-новите постижения, подхода за създаване на локални приложения като цяло и използването на библиотека с отворен код Автоматично обединяване по-специално.

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

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

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

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

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

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

Хайди Хауърд - Освобождаващ разпределен консенсус

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

Спомнете си това Паксос е семейство от протоколи за решаване на проблема с консенсуса в мрежа от ненадеждни компютри, базирано на работата на Лесли Лампорт. Така някои от нашите лектори работят по задачи, които първоначално са били предложени от другите ни лектори - и това е прекрасно.

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

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

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

Алекс е специалист по бази данни и системи за съхранение и, което е по-важно за нас, комитер в Касандра. В момента той работи върху книга, Database Internals, с O'Reilly.

За системи с евентуална последователност (в руската терминология - „крайна последователност“), след срив на възел или разделяне на мрежата, трябва да разрешите следната дилема: или да продължите да изпълнявате заявки, жертвайки последователност, или да откажете да ги изпълните и да пожертвате наличността. В такава система кворумите, припокриващите се подмножества от възли и гарантирането, че поне един възел съдържа най-новата стойност, могат да бъдат добро крайно решение. Можете да преживеете повреди и загуба на връзка с някои възли, докато продължавате да отговаряте с най-новите стойности.

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

В хода на доклада ще разгледаме Реплики на свидетели, схемата за репликация, използвана в гаечен ключ и Мегастор, и реализацията на тази концепция в Apache Cassandra, наречена Преходна репликация и евтини кворуми.

Дмитрий Вюков - Goroutines изложени

Дмитрий е разработчик в Google, който работи върху динамично тестване за C/C++ и Go - Address/Memory/ThreadSanitizer и подобни инструменти за ядрото на Linux. Допринесе за Go мащабируем планировчик на goroutine, мрежов анкетьор и паралелен събирач на отпадъци. Той е експерт по многопоточност, автор на дузина нови неблокиращи алгоритми и е собственик на Черен колан Intel.

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

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

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

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

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

Денис - разработчик Космос DB, експерт по проверка на модели за съгласуваност, консенсусни алгоритми и разпределени транзакции. В момента работи в Microsoft, а преди това е работил върху разпределени системи в Amazon и Yandex.

В този разговор ще разгледаме протоколите за разпределени транзакции, които бяха изобретени през последните няколко години, които могат да бъдат внедрени от страна на клиента върху всяко хранилище на данни, което поддържа условно актуализиране (сравняване и настройка). Изводът е, че животът не завършва с двуфазов комит, транзакциите могат да се добавят върху всякакви бази данни - на ниво приложение, но различните протоколи (2PC, Percolator, RAMP) имат различни компромиси и не ни се дават безплатно.

Алексей Зиновиев - Не всички ML алгоритми достигат до разпределения рай

Алексей (залеслав) е дългогодишен лектор и член на програмни комитети на други конференции. Практикуващ обучител в EPAM Systems и е приятел с Hadoop/Spark и други големи данни от 2012 г.

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

И накрая, два доклада от Yandex за базата данни на Yandex.

Владислав Кузнецов - Yandex Database - как гарантираме устойчивост на грешки

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

Семьон Чечеринда - Разпределени транзакции в YDB

Семьон е разработчик в групата за разпределени платформи в Yandex, работещ върху възможността за използване на множество клиенти на инсталацията на YDB.

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

Каква е следващата?

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

Конференцията Hydra ще се проведе на 11-12 юли в Санкт Петербург. Билети са налични покупка на официалния уебсайт. Моля, обърнете внимание на наличието на онлайн билети - ако по някаква причина не можете да стигнете до Санкт Петербург тези дни.

Ще се видим в Hydra!

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