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

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

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

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

Мотивация

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

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

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

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

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

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

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

Кейноутите

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

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

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

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

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

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

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

Майкъл Скот — професор по компютърни науки в университета в Рочестър, с който съдбата го свърза вече 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 доведе до десеткратен ръст на производителността на java.util.concurrent.ThreadPoolExecutor. Ако предварително ви интересува какво представляват тези «Dual data structures», то за това има съответна работа.

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

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

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

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

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

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

Leslie Lamport — Q & A

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

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

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

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

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

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

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

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

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

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

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

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

Pedro Ramalhete — Структури от данни без изчакване и транзакции без изчакване

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

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

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

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

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

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

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

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

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

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

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

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

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

В хода на доклада ще разгледаме Witness Replicas, схемата на репликация, използвана в Spanner и Megastore, и реализирането на тази концепция в Apache Cassandra под имената Транзиторна репликация & евтини кворуми.

Дмитрий Вюков — Горутини на повърхността

Дмитрий е разработчик в Google, работещ върху динамично тестване на C/C++ и Go — Address/Memory/ThreadSanitizer, и над подобни инструменти за ядрото на Linux. Той е contributed в 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 е проектирана за OLTP запитвания и отговаря на изискванията на ACID за транзакционни системи. В доклада ще разгледаме алгоритъма за планиране на транзакции, който лежи в основата на транзакционната система YDB. Ще анализираме какви единици участват в транзакциите, кой назначава глобалния ред на транзакциите, как се постига атомарност, надеждност и строгост на изолацията. На примера на разпространен проблем ще разгледаме реализациите на транзакции с прилагане на двуфазен комит и детерминистични транзакции. Ще обсъдим техните различия.

Какво следва?

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

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

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

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