Van 11 tot en met 12 juli zal er een conferentie plaatsvinden in St. Petersburg , gewijd aan de ontwikkeling van parallelle en gedistribueerde systemen. De truc van Hydra is dat het coole wetenschappers (die doorgaans alleen op buitenlandse wetenschappelijke conferenties te vinden zijn) en beroemde praktiserende ingenieurs verenigt in één groot programma op het snijvlak van wetenschap en praktijk.
Hydra is een van onze belangrijkste conferenties van de afgelopen jaren. Er ging een zeer serieuze voorbereiding, selectie van sprekers en verslagen aan vooraf. Vorige week hierover met de directeur van JUG.ru Group, Alexey Fedorov ().
Wij over drie belangrijke deelnemers, de grondleggers van de theorie van gedistribueerde systemen: Leslie Lamport, Maurice Herlihy en Michael Scott. Het is tijd om meer in detail over het hele programma te praten!
Motivatie
Als je bezig bent met programmeren, dan heb je op de een of andere manier te maken met multithreading en gedistribueerd computergebruik. Deskundigen op de relevante gebieden werken rechtstreeks met hen samen, maar impliciet kijkt de distributie overal naar ons: in elke multi-core computer of gedistribueerde dienst is er iets dat parallel berekeningen uitvoert.
Er zijn veel conferenties die verschillende aspecten van applicatieprogrammering behandelen. Aan de andere kant van het spectrum hebben we gespecialiseerde wetenschappelijke scholen die enorme hoeveelheden complexe theorie in de vorm van lezingen onthullen. Parallel met Hydra in St. Petersburg is dat bijvoorbeeld het geval . Op de Hydra-conferentie probeerden we harde praktijken, wetenschap en alles wat zich op hun kruispunt bevond samen te brengen.
Denk hier eens over na: we leven in een geweldige tijd waarin je de grondleggers van het vakgebied van de wetenschap en techniek dat we bestuderen persoonlijk kunt ontmoeten. Natuurkundigen zullen Newton noch Einstein ontmoeten - de trein is vertrokken. Maar naast ons leven nog steeds degenen die de basis hebben gelegd voor de theorie van gedistribueerde systemen, populaire programmeertalen hebben uitgevonden en dit alles voor het eerst hebben belichaamd in werkende prototypes. Deze mensen hebben hun baan niet halverwege opgezegd, maar werken nu aan urgente kwesties bij wereldberoemde universiteiten en bedrijven, en zijn vandaag de dag de grootste bronnen van kennis en ervaring.
Aan de andere kant blijft de mogelijkheid om hen te ontmoeten meestal puur theoretisch: weinigen van ons kunnen voortdurend openbare evenementen aan een of andere universiteit van Rochester volgen, en zich dan naar de VS haasten en terug voor een lezing met Michael Scott. Het bezoeken van alle Hydra-leden zou een klein fortuin kosten, afgezien van de afgrond van verspilde tijd (hoewel het klinkt als een interessante zoektocht).
Aan de andere kant hebben we veel topingenieurs die momenteel aan urgente problemen in gedistribueerde systemen werken, en ze hebben zeker veel te vertellen. Maar hier is het probleem: zij werken, en hun tijd is waardevol. Ja, als je een medewerker bent van Microsoft, Google of JetBrains, neemt de kans dat je een van de beroemde sprekers op een intern evenement tegenkomt sterk toe, maar over het algemeen nee, dit gebeurt niet elke dag.
Op deze manier volbrengt de Hydra Conferentie een belangrijke taak die de meesten van ons niet alleen kunnen uitvoeren: op één plaats en op één moment brengt het mensen samen wier ideeën of interacties met wie uw leven kan veranderen. Ik geef toe dat niet iedereen gedistribueerde systemen of een aantal complexe fundamentele zaken nodig heeft. Je kunt CRUDs de rest van je leven in PHP programmeren en helemaal gelukkig blijven. Maar wie het ook nodig heeft, dit is je kans.
Er is nogal wat tijd verstreken sinds de eerste aankondiging van de Hydra-conferentie over Habré. Gedurende deze tijd is er veel werk verricht - en nu hebben we een lijst met bijna alle rapporten. Geen trage single-threaded algoritmen, maar pure gedistribueerde hardcore! Laten we eindigen met algemene woorden en kijken wat we nu in handen hebben.
Keynotes
Keynotes beginnen en eindigen de dagen van de conferentie. Meestal is het doel van een openingstoespraak het bepalen van de algemene geest en richting van de conferentie. De afsluitende keynote trekt een grens en legt uit hoe we kunnen leven met de kennis en vaardigheden die we tijdens de conferentie hebben verworven. Het begin en het einde: wat het beste wordt herinnerd, en in het algemeen, heeft een grotere betekenis gekregen.
Klif Klik
Cliff is een legende in de Java-wereld. Eind jaren negentig schreef hij voor zijn proefschrift een artikel met de titel , dat enige tijd later de basis werd voor HotSpot JVM Server Compiler. Twee jaar later werkte hij al bij Sun Microsystems aan de JVM en liet hij de hele wereld zien dat JIT bestaansrecht heeft. Dit hele verhaal over hoe Java een van de snelste moderne runtimes is met de slimste en snelste optimalisaties kwam van Cliff Click. Helemaal in het begin geloofde men dat als iets toegankelijk is voor een statische compiler, je niet eens hoeft te proberen het te jiten. Dankzij het werk van Cliff en zijn team werden alle nieuwe talen gemaakt met het idee van standaard JIT-compilatie. Dit was uiteraard geen eenmanszaak, maar Cliff speelde daarin een heel belangrijke rol.
In de openingstoespraak zal Cliff praten over zijn andere onderneming: , een in-memory platform voor gedistribueerde en schaalbare machine learning voor industriële toepassingen. Of preciezer: over de gedistribueerde opslag van sleutel-waardeparen daarin. Dit is een zeer snelle opslag met veel interessante eigenschappen (de exacte lijst staat in ), die het gebruik van vergelijkbare oplossingen in de wiskunde van big data-streaming mogelijk maken.
Een ander rapport dat Cliff zal geven is: . Een ander deel van zijn biografie - tien jaar , waar hij veel dingen in de Azul-hardware en -technologiestack heeft bijgewerkt en verbeterd: JIT-compilers, runtime, threadmodel, foutafhandeling, stapelafhandeling, hardware-interrupts, het laden van klassen, enzovoort, enzovoort - nou ja, je krijgt de idee.
Het meest interessante deel begon toen ze hardware maakten voor een groot bedrijf: een supercomputer om Java te draaien. Het was een nogal innovatief ding, specifiek op maat gemaakt voor Java, dat speciale vereisten heeft: lees geheugenbarrières voor het verzamelen van afval met lage pauzes, arrays met grenscontrole, virtuele oproepen... Een van de coolste technologieën is hardware-transactioneel geheugen. De volledige L1 van elk van de 864 cores zou kunnen deelnemen aan transactioneel schrijven, wat vooral belangrijk is voor het werken met vergrendelingen in Java (gesynchroniseerde blokken kunnen parallel werken zolang er geen echt geheugenconflict is). Maar het mooie idee werd verpletterd door de harde realiteit - en in deze lezing zal Cliff je vertellen waarom HTM en STM niet erg geschikt zijn voor de praktische behoeften van multi-threaded computing.
Michaël Scott-
- Professor computerwetenschappen aan de Universiteit van Rochester, met wie het lot hem verbond , en aan de Universiteit van Wisconsin-Madison, thuis, was hij vijf jaar decaan. Hij onderzoekt en onderwijst studenten over parallelle en gedistribueerde programmering en taalontwerp.
De hele wereld kent Michael dankzij het leerboek , waarvan de nieuwste editie relatief recent is gepubliceerd - in 2015. Zijn werk ik kreeg als een van de bekendste op het gebied van gedistribueerd computergebruik en in de onlinebibliotheek van de Universiteit van Rochester. Je kent hem misschien ook als de auteur van het Michael-Scott-algoritme .
Wat de Java-wereld betreft, dit is een speciaal geval: samen met Doug Lea ontwikkelde hij de niet-blokkerende algoritmen en synchrone wachtrijen waarop Java-bibliotheken werken. Dit is precies waar de keynote “Dual datastructuren” over zal gaan: de introductie van deze structuren in Java SE 6 heeft de prestaties met een factor 10 verbeterd java.util.concurrent.ThreadPoolExecutor. Als je je van tevoren afvraagt wat deze “Dual datastructuren” zijn, dan is er informatie over .
Maurice Herlihy -
- winnaar van twee Dijkstraprijzen. De eerste is om aan te werken (Brown University), en de tweede, recentere - (Virginia Tech Universiteit). De Dijkstraprijs beloont werk waarvan de betekenis en impact al minstens tien jaar zichtbaar zijn, en Maurice is duidelijk een van de meest gerenommeerde experts op dit gebied. Hij werkt momenteel als professor aan de Brown University en heeft een lange lijst met prestaties.
In deze afsluitende keynote zal Maurice spreken over de theorie en praktijk van gedistribueerde blockchain-systemen vanuit het standpunt van de klassiekers van gedistribueerd computergebruik en hoe het veel gerelateerde problemen vereenvoudigt. Dit is een rapport dat uitsluitend over het onderwerp van de conferentie gaat - helemaal niet over de mijnbouwhype, maar eerder over hoe onze kennis verbazingwekkend effectief en passend kan worden gebruikt in relatie tot een verscheidenheid aan taken.
In juli 2017 kwam Maurice al naar Rusland om naar de SPTDC-school te gaan, nam deel aan de JUG.ru-meetup en de opname is te bekijken op YouTube:
Hoofdprogramma
Vervolgens volgt een kort overzicht van de rapporten die in het programma zijn opgenomen. Sommige rapporten worden hier gedetailleerd beschreven, andere korter. Lange beschrijvingen gingen vooral naar Engelstalige rapporten, waarvoor links naar wetenschappelijke artikelen, termen op Wikipedia, enzovoort nodig waren. De volledige lijst is beschikbaar . De lijst op de website wordt bijgewerkt en aangevuld.
Leslie Lamport-
Leslie Lamport is de auteur van baanbrekende werken op het gebied van gedistribueerd computergebruik. staat voor "Lamport TeX". Hij was het die het concept voor het eerst introduceerde, in 1979 , en zijn artikel ontving de Dijkstraprijs.
Qua format is dit het meest bijzondere deel van het programma, omdat het niet eens een verslag is, maar een vraag-en-antwoordsessie. Wanneer een aanzienlijk deel van het publiek al bekend is (of bekend kan worden) met allerlei werken gebaseerd op “Lamport's theorie”, zijn eigen artikelen en rapporten, is het belangrijker om alle beschikbare tijd aan directe communicatie te besteden.
Het idee is simpel: je bekijkt twee reportages op YouTube: и en bereid ten minste één vraag voor, en Leslie antwoordt.
De eerste van deze twee video's hebben we al . Als je geen uur tijd hebt om de video te bekijken, kun je hem snel allemaal in tekstvorm lezen.
Opmerking: er zijn nog veel meer Leslie Lamport-video's op YouTube. Er is bijvoorbeeld een grote . Een offline versie van deze hele cursus is beschikbaar op , en hij uploadde het naar YouTube zodat het gemakkelijker op mobiele apparaten kon worden bekeken.
Martin Kleppmann-
Martin Kleppmann is een onderzoeker aan de Universiteit van Cambridge die zich bezighoudt met CRDT en formele verificatie van algoritmen. Martins boek , gepubliceerd in 2017, bleek zeer succesvol en haalde een plek in bestsellerlijsten op het gebied van dataopslag en -verwerking. Kevin Scott, CTO bij Microsoft, : “Dit boek zou een must-have moeten zijn voor software-ingenieurs. Dit is een zeldzame hulpbron die theorie en praktijk combineert om ontwikkelaars te helpen slimmer te ontwerpen en implementeren van infrastructuur en datasystemen.” De maker van Kafka en CTO van Confluent, Jay Kreps, zei iets soortgelijks.
Voordat hij zich in het academisch onderzoek begaf, werkte Martin in de industrie en was hij medeoprichter van twee succesvolle start-ups:
- Rapportief, gewijd aan het weergeven van het sociale profiel van contacten uit uw e-mail, die LinkedIn in 2012 heeft gekocht;
- Go Test It, een dienst voor het automatisch testen van websites in verschillende browsers, die RedGate in 2009 heeft gekocht.
Over het algemeen heeft Martin, hoewel minder beroemd dan onze keynotes, al een bijdrage kunnen leveren aan de ontwikkeling van gedistribueerd computergebruik en aan de industrie.
In deze lezing zal Martin praten over een onderwerp dat dichter bij zijn academisch onderzoek ligt. In Google Documenten en vergelijkbare systemen voor het gezamenlijk bewerken van documenten verwijst 'gezamenlijk bewerken' naar een replicatietaak: elke gebruiker heeft zijn eigen replica van het gedeelde document, die hij of zij vervolgens wijzigt, en alle wijzigingen worden via het netwerk naar de rest van het document verzonden. deelnemers. Wijzigingen in documenten offline leiden tot tijdelijke inconsistentie van het document in relatie tot andere deelnemers, en hersynchronisatie vereist conflicthantering. Dat is precies waar ze voor bestaan (CRDT) is in feite een vrij nieuw ding, waarvan de essentie pas in 2011 werd geformuleerd. Deze lezing bespreekt wat er sindsdien is gebeurd in de wereld van CRDT, wat de meest recente ontwikkelingen zijn, de aanpak voor het creëren van local-first-applicaties in het algemeen en het gebruik van een open source-bibliotheek. in het bijzonder.
Volgende week publiceren we een lang interview met Martin op Habré, het wordt interessant.
Pedro Ramalhete -
Pedro werkt bij Cisco en heeft de afgelopen tien jaar parallelle algoritmen ontwikkeld, waaronder synchronisatiemechanismen, lock-free en wait-free datastructuren en alles wat je maar kunt bedenken over dit onderwerp. Zijn huidige onderzoeks- en technische interesses richten zich op universele constructies, software transactioneel geheugen, persistent geheugen en soortgelijke technologieën die correcte, schaalbare en fouttolerante toepassingen mogelijk maken. Hij is ook de auteur van een blog die algemeen bekend is in kleine kringen .
De meeste multithreaded applicaties draaien nu op parallelle datastructuren, van het gebruik van berichtenwachtrijen tussen actoren tot geïndexeerde datastructuren in sleutelwaardeopslagplaatsen. Ze werken al vele jaren met succes in de Java JDK en worden langzaam toegevoegd aan C++.
De eenvoudigste manier om een parallelle datastructuur te implementeren is een sequentiële (single-threaded) implementatie waarbij methoden worden beschermd door mutexen. Dit is toegankelijk voor elke juni, maar heeft duidelijke problemen met schaling en prestaties. Tegelijkertijd kunnen lock-free en wait-free datastructuren niet alleen beter omgaan met fouten, maar hebben ze ook een beter prestatieprofiel. Hun ontwikkeling vereist echter diepgaande expertise en aanpassing aan een specifieke toepassing. Eén verkeerde regel code is genoeg om alles kapot te maken.
Hoe kunnen we ervoor zorgen dat zelfs een niet-expert dergelijke datastructuren kan ontwerpen en implementeren? Het is bekend dat elk sequentieel algoritme met behulp van beide thread-safe kan worden gemaakt of transactioneel geheugen. In de eerste plaats kunnen ze de drempel verlagen om dit probleem op te lossen. Beide oplossingen leiden echter doorgaans tot een ineffectieve implementatie. Pedro zal vertellen hoe ze deze ontwerpen efficiënter hebben gemaakt en hoe je ze kunt gebruiken voor je algoritmen.
Heidi Howard-
Heidi Howard is, net als Martin, onderzoeker op het gebied van gedistribueerde systemen aan de Universiteit van Cambridge. Haar specialiteiten zijn consistentie, fouttolerantie, prestatie en gedistribueerde consensus. Ze is vooral bekend vanwege haar generalisatie van het zogenaamde Paxos-algoritme .
Bedenk dat is een familie van protocollen voor het oplossen van het probleem van consensus in een netwerk van onbetrouwbare computers, gebaseerd op het werk van Leslie Lamport. Sommige van onze sprekers werken dus aan problemen die oorspronkelijk door onze andere sprekers werden voorgesteld – en dat is geweldig.
Het vermogen om consensus te vinden tussen meerdere hosts – voor het aanspreken, het kiezen van leiders, het blokkeren of coördineren – is een fundamenteel probleem in moderne gedistribueerde systemen. Paxos is nu de belangrijkste manier om consensusproblemen op te lossen, en er wordt veel onderzoek gedaan om het algoritme uit te breiden en te optimaliseren voor verschillende praktische behoeften.
In deze lezing zullen we de theoretische basis van Paxos opnieuw bekijken, de oorspronkelijke vereisten versoepelen en het algoritme generaliseren. We zullen zien dat Paxos in wezen slechts één optie is uit een enorme reeks consensusbenaderingen, en dat andere punten op het spectrum ook erg nuttig zijn voor het bouwen van goede gedistribueerde systemen.
Alex Petrov —
Alex is een specialist in database- en opslagsystemen, en nog belangrijker voor ons, een committer in . Momenteel werkt hij samen met O'Reilly aan een boek, Database Internals.
Voor systemen met (in Russische terminologie - "ultieme consistentie"), nadat een knooppunt is gecrasht of een netwerk is gesplitst, moet je het volgende dilemma oplossen: óf doorgaan met het uitvoeren van verzoeken, waarbij de consistentie wordt opgeofferd, óf weiger ze uit te voeren en de beschikbaarheid op te offeren. In een dergelijk systeem kunnen quorums, overlappende subsets van knooppunten en ervoor zorgen dat ten minste één knooppunt de meest recente waarde bevat, een goede randoplossing zijn. U kunt storingen en verlies van connectiviteit met sommige knooppunten overleven terwijl u nog steeds reageert met de nieuwste waarden.
Alles heeft echter zijn prijs. Een quorumreplicatieschema betekent hogere opslagkosten: redundante gegevens moeten op meerdere knooppunten tegelijk worden opgeslagen om ervoor te zorgen dat er voldoende kopieën beschikbaar zijn als er zich een probleem voordoet. Het blijkt dat je niet alle gegevens op alle replica's hoeft op te slaan. U kunt de belasting van de opslag verminderen als u gegevens slechts op een deel van de knooppunten opslaat, en speciale knooppunten (Transient Replica) gebruikt voor scenario's voor het afhandelen van fouten.
In de loop van het rapport zullen we erover nadenken , het replicatieschema dat wordt gebruikt in и , en de implementatie van dit concept in Apache Cassandra genoemd .
Dmitri Vjoekov -
Dmitry is een ontwikkelaar bij Google en werkt aan dynamisch testen voor C/C++ en Go - Address/Memory/ThreadSanitizer, en soortgelijke tools voor de Linux-kernel. Bijgedragen aan Go, een schaalbare goroutine-planner, een netwerkpoller en een parallelle garbage collector. Hij is een expert in multithreading, de auteur van een tiental nieuwe niet-blokkerende algoritmen en is de eigenaar van Intel.
Nu iets over het rapport zelf. De Go-taal heeft native ondersteuning voor multithreading in de vorm van goroutines (lichte threads) en kanalen (FIFO-wachtrijen). Deze mechanismen maken het voor gebruikers heel gemakkelijk en plezierig om moderne multi-threaded applicaties te schrijven, en het lijkt op magie. Zoals we begrijpen, is er hier geen sprake van magie. In deze lezing zal Dmitry zich verdiepen in de fijne kneepjes van de Go-planner en de geheimen tonen van het implementeren van deze “magie”. Eerst zal hij een overzicht geven van de belangrijkste componenten van de planner en vertellen hoe deze werkt. Vervolgens gaan we dieper in op individuele aspecten, zoals de parkeer-/uitparkeerstrategie en het afhandelen van blokkeersysteemoproepen. Ten slotte zal Dmitry iets vertellen over mogelijke verbeteringen aan de planner.
Dmitry Bugaichenko -
Dmitry heeft bijna negen jaar in de outsourcing gewerkt zonder het contact met de universiteit en de wetenschappelijke gemeenschap te verliezen. Big data-analyse in Odnoklassniki werd voor hem een unieke kans om theoretische training en wetenschappelijke basis te combineren met de ontwikkeling van echte, veelgevraagde producten.
Gedistribueerde grafiekanalyse was en blijft een moeilijke taak: wanneer het nodig wordt om informatie te verkrijgen over de verbindingen van een naburig hoekpunt, moeten de gegevens vaak tussen machines worden overgedragen, wat leidt tot een langere uitvoeringstijd en belasting van de netwerkinfrastructuur. In deze lezing zullen we zien hoe je aanzienlijke verwerkingssnelheden kunt bereiken door gebruik te maken van probabilistische datastructuren of feiten zoals de symmetrie van de vriendschapsgrafiek in een sociaal netwerk. Dit alles wordt geïllustreerd met codevoorbeelden in Apache Spark.
Denis Rystsov -
Dennis - ontwikkelaar , een expert in het controleren van consistentiemodellen, consensusalgoritmen en gedistribueerde transacties. Momenteel werkt hij bij Microsoft en daarvoor werkte hij aan gedistribueerde systemen bij Amazon en Yandex.
In deze lezing kijken we naar de gedistribueerde transactieprotocollen die de afgelopen jaren zijn uitgevonden en die aan de clientzijde kunnen worden geïmplementeerd bovenop elke dataopslag die voorwaardelijke updates ondersteunt (vergelijken en instellen). Het komt erop neer dat het leven niet eindigt met een commit in twee fasen; transacties kunnen bovenop elke database worden toegevoegd - op applicatieniveau, maar verschillende protocollen (2PC, Percolator, RAMP) hebben verschillende afwegingen en worden niet aan ons gegeven gratis.
Alexey Zinovjev -
Alexei () is al jarenlang spreker en lid van programmacommissies op andere conferenties. Oefentrainer bij EPAM Systems en sinds 2012 bevriend met Hadoop/Spark en andere big data.
In deze lezing zal Alexey praten over de problemen bij het aanpassen van klassieke machine learning-algoritmen voor uitvoering in de gedistribueerde modus, gebaseerd op zijn ervaring met het werken met Apache Spark ML, Apache Mahout, Apache Flink ML en de ervaring met het creëren van Apache Ignite ML. Alexey zal ook praten over de implementatie van gedistribueerde ML-algoritmen in deze raamwerken.
En tot slot twee rapporten van Yandex over Yandex Database.
Vladislav Kuznetsov -
Vladislav is een ontwikkelaar bij Yandex in de gedistribueerde platformgroep. Yandex Database is een horizontaal schaalbaar, geogedistribueerd, fouttolerant DBMS dat bestand is tegen het falen van schijven, servers, racks en datacenters zonder de consistentie te verliezen. Om fouttolerantie te garanderen, wordt een eigen algoritme gebruikt om gedistribueerde consensus te bereiken, evenals een aantal technische oplossingen, die in het rapport gedetailleerd worden besproken. Het rapport kan interessant zijn voor zowel DBMS-ontwikkelaars als ontwikkelaars van applicatieoplossingen op basis van DBMS.
Semjon Checherinda -
Semyon is ontwikkelaar in de gedistribueerde platformgroep bij Yandex en werkt aan de mogelijkheid van multi-tenant gebruik van de YDB-installatie.
Yandex Database is ontworpen voor OLTP-query's en voldoet aan de ACID-vereisten voor een transactiesysteem. In dit rapport zullen we het transactieplanningsalgoritme bekijken dat ten grondslag ligt aan het YDB-transactiesysteem. Laten we eens kijken welke entiteiten deelnemen aan transacties, wie de mondiale orde aan transacties toekent, hoe atomiciteit, betrouwbaarheid en een strikt niveau van isolatie van transacties worden bereikt. Laten we, met een veelvoorkomend probleem als voorbeeld, kijken naar transactie-implementaties met behulp van tweefasige commits en deterministische transacties. Laten we hun verschillen bespreken.
Wat is het volgende?
Het conferentieprogramma wordt nog steeds gevuld met nieuwe rapporten. In het bijzonder verwachten wij een rapport van Nikita Koval () van JetBrains en Oleg Anastasjev () van het bedrijf Odnoklassniki. Nikita werkt aan algoritmen voor coroutines in het Kotlin-team, en Oleg ontwikkelt architectuur en oplossingen voor systemen met hoge belasting op het Odnoklassniki-platform. Daarnaast is er nog 1 voorwaardelijk vrije plek, de programmacommissie werkt daar op dit moment met kandidaten voor.
De Hydra-conferentie vindt plaats van 11 tot en met 12 juli in St. Petersburg. Kaartjes zijn beschikbaar . Let op de beschikbaarheid van online tickets - als u om welke reden dan ook vandaag niet naar St. Petersburg kunt komen.
Tot ziens bij Hydra!
Bron: www.habr.com