Maurice Herlichi ist der Gewinner von zwei Dijkstra-Preisen . Die erste betrifft Arbeiten zur wartungsfreien Synchronisation (Brown University) und die zweite, neuere, ist Transaktionsspeicher: Architekturunterstützung für sperrenfreie Datenstrukturen (Virginia Tech University). Der Dijkstra-Preis wird für Werke vergeben, deren Bedeutung und Einfluss seit mindestens zehn Jahren spürbar sind, und Maurice ist offensichtlich einer der bekanntesten Spezialisten auf diesem Gebiet. Derzeit arbeitet er als Professor an der Brown University und hat viele Erfolge für einen ganzen Absatz in der Länge. Derzeit beschäftigt er sich mit Blockchain-Forschung im Kontext des klassischen verteilten Rechnens.

Zuvor war Maurice bei SPTCC ( Video ) nach Russland gekommen und hatte ein hervorragendes Treffen der Java-Entwicklergemeinde JUG.ru in St. Petersburg ( Video ).

Dieser Habrapost ist ein großartiges Interview mit Maurice Herlihy. Es werden folgende Themen behandelt:

Das Zusammenspiel von Wissenschaft und Industrie;
Die Grundlage für die Blockchain-Forschung;
Woher kommen bahnbrechende Ideen? Einfluss der Popularität;
Promotion unter der Leitung von Barbara Liskov;
Die Welt wartet auf Multicore;
In die neue Welt - neue Probleme. NVM-, NUMA- und Hacking-Architektur;
Compiler gegen Prozessoren, RISC gegen CISC, Shared Memory gegen Message Passing;
Die Kunst, fragilen Multithread-Code zu schreiben;
Wie man den Schülern beibringt, komplexen Multithread-Code zu schreiben;
Neue Ausgabe von The Art of Multiprocessor Programming;
Wie das Transaktionsgedächtnis erfunden wurde;
Warum es sich lohnt, auf dem Gebiet des verteilten Rechnens zu forschen?
Hat die Entwicklung von Algorithmen aufgehört und wie man davon lebt?
Arbeit an der Brown University;
Der Unterschied zwischen Forschung an der Universität und innerhalb des Unternehmens;
Hydra und SPTDC.

Interviews durchgeführt von:

Vitaly Aksyonov ist derzeit Post-Dock bei IST Austria und Mitarbeiter des Instituts für Computertechnologie an der ITMO-Universität. Forschung in Theorie und Praxis wettbewerbsfähiger Datenstrukturen. Bevor er zu IST kam, promovierte er an der Universität Paris Didro und der Universität ITMO unter der Leitung von Professor Peter Kuznetsov.

Alexey Fedorov ist Produzent bei der JUG Ru Group, einem russischen Unternehmen, das Konferenzen für Entwickler organisiert. Alexey war an der Vorbereitung von mehr als 50 Konferenzen beteiligt, und in seinem Lebenslauf gibt es alles, was von der Position eines Entwicklungsingenieurs bei Oracle (JCK, Java Platform Group) bis zur Position von devrell bei Odnoklassniki reicht.

Vladimir Sitnikov ist Ingenieur bei Netcracker. Seit zehn Jahren arbeitet er an der Leistung und Skalierbarkeit von NetCracker OS, einer Software, die von Telekommunikationsbetreibern zur Automatisierung von Verwaltungsprozessen für Netzwerke und Netzwerkgeräte verwendet wird. Er interessiert sich für Leistungsprobleme bei Java- und Oracle-Datenbanken. Der Autor von mehr als einem Dutzend Leistungsverbesserungen im offiziellen PostgreSQL JDBC-Treiber.

Das Zusammenspiel von Wissenschaft und Industrie

Alexei: Moris, Sie haben sehr lange im akademischen Umfeld gearbeitet und die erste Frage ist die Interaktion zwischen dem akademischen und dem industriellen Bereich. Können Sie uns sagen, wie sich die Interaktionen zwischen ihnen in letzter Zeit verändert haben? Was ist vor 20-30 Jahren passiert und was passiert jetzt?

Maurice: Ich habe immer versucht, eng mit Handelsunternehmen zusammenzuarbeiten, weil sie interessante Aufgaben haben. Sie sind in der Regel nicht sehr daran interessiert, die erzielten Ergebnisse zu veröffentlichen oder der Weltgemeinschaft ihre Probleme ausführlich zu erklären. Sie sind nur daran interessiert, diese Probleme zu lösen. Ich habe einige Zeit in solchen Unternehmen gearbeitet. Ich habe fünf Jahre in Vollzeit in einem Forschungslabor der Digital Equipment Corporation gearbeitet, die früher eine große Computerfirma war. Ich habe einen Tag in der Woche bei Sun, bei Microsoft, bei Oracle und ein bisschen bei Facebook gearbeitet. Jetzt mache ich einen kreativen Urlaub (Sabbaturlaub, ein Professor an einer amerikanischen Universität darf in sechs Jahren ein Jahr lang Urlaub nehmen) und arbeite bei Algorand , einem solchen Kryptowährungsunternehmen in Boston. Die enge Zusammenarbeit mit Unternehmen war schon immer eine Freude, denn so lernen Sie neue und interessante Dinge kennen. Sie können die erste oder zweite Person sein, die einen Artikel zu einem Thema Ihrer Wahl veröffentlicht, anstatt die Lösungen für Probleme, an denen alle anderen bereits arbeiten, schrittweise zu verbessern.

Alexei: Kannst du uns mehr darüber erzählen, wie das passiert?

Maurice: Natürlich. Wissen Sie, als ich bei Digital Equipment Corporation, I und Elliot Moss gearbeitet habe, haben wir das Transaktionsgedächtnis erfunden. Es war eine sehr fruchtbare Zeit, in der sich alle für Informationstechnologie interessierten. Parallelität einschließlich, obwohl Multi-Core-Systeme noch nicht existierten. In den Tagen von Sun und Oracle habe ich viel an parallelen Datenstrukturen gearbeitet. Auf Facebook war ich an ihrem Blockchain-Projekt beteiligt, über das ich nicht sprechen kann, aber ich hoffe, dass es bald veröffentlicht wird. Nächstes Jahr werde ich in Algorand in einer Forschungsgruppe arbeiten und intelligente Verträge studieren.

Alexei: In den letzten Jahren ist Blockchain ein sehr beliebtes Thema geworden. Hilft dies Ihrer Forschung? Vielleicht wird es den Erhalt von Zuschüssen erleichtern oder den Zugang zu den Ressourcen von Unternehmen ermöglichen, die in der Branche tätig sind?

Maurice: Ich habe bereits ein kleines Stipendium von der Ethereum Foundation erhalten. Die Popularität der Blockchain ist sehr nützlich, um Studenten zu inspirieren, auf diesem Gebiet zu arbeiten. Sie sind sehr daran interessiert und nehmen gerne daran teil, aber manchmal verstehen sie nicht, dass Studien, die von außen verlockend klingen, wirklich harte Arbeit beinhalten. Trotzdem bin ich sehr glücklich, all diese Mystik rund um die Blockchain zu nutzen, es hilft, Studenten anzulocken.

Das ist aber noch nicht alles. Ich bin im Beirat mehrerer Blockchain-Startups. Einige von ihnen mögen Erfolg haben, andere nicht, aber es ist immer sehr interessant, ihre Ideen zu sehen, sie zu studieren und Menschen zu beraten. Das Aufregendste ist, wenn Sie die Leute davor warnen, etwas zu tun. Vieles scheint zunächst eine gute Idee zu sein, aber ist es wirklich so?

Blockchain Research Foundation

Vitaliy: Jemand glaubt, dass die Blockchain und ihre Algorithmen eine Zukunft haben. Und andere Leute sagen, dass dies nur eine weitere Blase ist. Können Sie Ihre Meinung dazu teilen?

Maurice: Vieles, was in der Welt der Blockchains passiert, funktioniert nicht richtig, etwas ist nur ein Betrug, vieles wird überbewertet. Dennoch denke ich, dass es eine solide wissenschaftliche Grundlage für diese Studien gibt. Die Tatsache, dass die Welt der Blockchains voller ideologischer Unterschiede ist, zeigt das Maß an Aufregung und Engagement. Andererseits ist es für die wissenschaftliche Forschung nicht besonders vorteilhaft. Wenn Sie nun einen Artikel veröffentlichen, der sich mit den Mängeln eines bestimmten Algorithmus befasst, ist die resultierende Reaktion nicht immer vollständig wissenschaftlich. Oft werfen Menschen ihre Gefühle aus. Ich denke, dass eine solche Aufregung in diesem Bereich für manche attraktiv erscheint, aber am Ende gibt es echte wissenschaftliche und technische Probleme, die noch angegangen werden müssen. Es gibt viel Informatik.

Vitaliy: Das heißt, Sie versuchen, den Grundstein für die Blockchain-Forschung zu legen, oder?

Maurice: Ich versuche, den Grundstein für eine solide, wissenschaftlich und mathematisch fundierte Disziplin zu legen. Und teilweise ist das Problem, dass man manchmal einigen übermäßig harten Positionen anderer Menschen widersprechen und sie ignorieren muss. Manchmal fragen die Leute, warum ich in einem Bereich arbeite, an dem nur Terroristen und Drogenhändler interessiert sind. Eine solche Reaktion ist ebenso bedeutungslos wie das Verhalten von Anhängern, die Ihre Worte blind wiederholen. Ich denke, dass die Wahrheit irgendwo dazwischen liegt. Blockchain wird weiterhin tiefgreifende Auswirkungen auf die Gesellschaft und die Weltwirtschaft haben. Aber wahrscheinlich wird dies dank moderner Technologien nicht passieren. Moderne Technologien werden sich entwickeln und das, was in Zukunft als Blockchain bezeichnet wird, wird sehr wichtig werden. Vielleicht sieht es nicht einmal wie moderne Blockchains aus, das ist eine offene Frage.

Wenn Menschen neue Technologien erfinden, werden sie es weiterhin Blockchain nennen. Ich meine, genau wie das heutige Fortran nichts mit der Fortran-Sprache aus den 1960er Jahren zu tun hat, aber jeder nennt es Fortran. Gleiches gilt für UNIX. Was als "Blockchain" bezeichnet wird, wird immer noch seine Revolution machen. Ich bezweifle jedoch, dass diese neue Blockchain dem ähnelt, was heute jeder gerne benutzt.

Woher kommen bahnbrechende Ideen? Auswirkungen auf die Popularität

Alexei: Hat die Popularität der Blockchain aus wissenschaftlicher Sicht zu neuen Ergebnissen geführt? Mehr Interaktion, mehr Studenten, mehr Unternehmen in der Region. Gibt es Ergebnisse dieses Anstiegs der Popularität?

Maurice: Das hat mich interessiert, als mir jemand die offizielle Broschüre eines Unternehmens überreichte, das gerade eine Menge Geld gesammelt hatte. Es schrieb über die Aufgabe der byzantinischen Generäle , mit denen ich mehr als vertraut bin. In der Packungsbeilage stand, war technisch eindeutig falsch. Die Leute, die das alles geschrieben haben, haben das Modell hinter dem Problem nicht wirklich verstanden ... und dennoch hat diese Firma viel Geld gesammelt. In der Folge ersetzte das Unternehmen diese Broschüre stillschweigend durch eine viel korrektere Option - und ich werde nicht sagen, wie dieses Unternehmen genannt wurde. Sie existieren immer noch und es geht ihnen sehr gut. Dieser Fall hat mich überzeugt, dass die Blockchain erstens nur eine Form des verteilten Rechnens ist. Zweitens war die Eintrittsschwelle (vor mindestens vier Jahren) eher niedrig. Die Leute, die auf diesem Gebiet arbeiteten, waren sehr energisch und klug, lasen aber keine wissenschaftlichen Arbeiten. Sie haben versucht, berühmte Dinge neu zu erfinden und haben es falsch gemacht. Heute hat sich das Drama verringert.

Alexei: Das ist sehr interessant, weil wir vor einigen Jahren einen anderen Trend hatten. Dies ist ein bisschen wie bei der Front-End-Entwicklung, als Entwickler von Browser-Schnittstellen ganze Technologien neu erfanden, die zu diesem Zeitpunkt bereits im Backend beliebt waren: Build-Systeme, kontinuierliche Integration und all das.

Maurice: Ich stimme zu. Dies ist jedoch nicht überraschend, da wirklich bahnbrechende Ideen immer von außerhalb der bestehenden Gemeinschaft kommen. Anerkannte Forscher, insbesondere Behörden im akademischen Umfeld, werden wahrscheinlich keinen wirklichen Durchbruch erzielen. Es ist einfach, einen Bericht für die nächste Konferenz darüber zu schreiben, wie Sie die Ergebnisse Ihrer bisherigen Arbeit leicht verbessert haben. Gehen Sie zur Konferenz, treffen Sie sich mit Freunden, sprechen Sie über das Gleiche. Und Menschen, die in bahnbrechende Ideen einbrechen, kommen fast immer von außen. Sie kennen die Regeln nicht, sie kennen die Sprache nicht, aber trotzdem ... Wenn Sie sich in einer bestehenden Community befinden, rate ich Ihnen, auf neue Dinge zu achten, auf etwas, das nicht in das Gesamtbild passt. In gewissem Sinne kann versucht werden, externe, flüssigere Entwicklungen mit Methoden zu kombinieren, die wir bereits verstehen. Versuchen Sie als ersten Schritt, eine wissenschaftliche Basis zu schaffen, und ändern Sie sie dann, damit sie auf neue bahnbrechende Ideen angewendet werden kann. Ich denke, dass Blockchain perfekt für die Rolle einer neuen Durchbruchsidee ist.

Alexei: Warum denkst du passiert das? Weil Menschen "außerhalb" keine spezifischen Hindernisse in der Gemeinschaft haben?

Maurice: Es gibt eine Art Muster. Wenn Sie die Geschichte der Impressionisten in Malerei und Kunst im Allgemeinen lesen, dann lehnten berühmte Künstler einst den Impressionismus ab. Sie sagten, es sei eine Art Kindlichkeit. Eine Generation später wurde diese zuvor abgelehnte Kunstform zum Standard. Was ich in meiner Gegend sehe: Blockchain-Erfinder waren nicht an Macht interessiert, an der Auflösung von Veröffentlichungen und Zitierindex, sie wollten nur etwas Gutes tun. Und so setzten sie sich und begannen es zu tun. Ihnen fehlte eine gewisse technische Tiefe, die jedoch behoben werden kann. Es ist viel schwieriger, neue kreative Ideen zu entwickeln, als unzureichend reife zu korrigieren und zu stärken. Dank dieser Erfinder habe ich jetzt etwas zu tun!

Alexei: Dies ähnelt dem Unterschied zwischen Startups und Legacy-Projekten. Wir haben viele Einschränkungen des Denkens, Barrieren, spezielle Anforderungen usw. geerbt.

Maurice: Eine gute Analogie ist das verteilte Rechnen. Stellen Sie sich die Blockchain als Startup und verteiltes Computing vor - ein großes etabliertes Unternehmen. Distributed Computing wird derzeit gekauft und mit der Blockchain zusammengeführt.

Promotion unter der Leitung von Barbara Liskov

Vitaliy: Wir haben noch viele Fragen! Wir haben Ihre Biografie studiert und sind auf eine merkwürdige Tatsache über Ihre Promotion gestoßen. Ja, es ist lange her, aber das Thema scheint wichtig zu sein. Sie haben unter der Leitung von Barbara Liskov selbst promoviert! Barbara ist in der Community der Entwickler von Programmiersprachen sehr berühmt und im Allgemeinen eine sehr berühmte Person. Es ist logisch, dass Ihre Forschung auf dem Gebiet der Programmiersprachen war. Wie sind Sie zum Parallel Computing übergegangen? Warum haben Sie sich entschieden, das Thema zu wechseln?

Maurice: Zu dieser Zeit haben Barbara und ihre Gruppe nur verteiltes Rechnen betrachtet, es war eine sehr neue Idee. Es gab auch diejenigen, die sagten, verteiltes Rechnen sei Unsinn, Kommunikation zwischen Computern sei bedeutungslos. Eines der Probleme beim verteilten Rechnen, das sie vom zentralisierten Rechnen unterscheidet, ist die Fehlertoleranz. Nach langem Suchen haben wir entschieden, dass Sie in einer Programmiersprache für verteiltes Computing so etwas wie atomare Transaktionen benötigen, da Sie nie sicher sein können, ob ein Remote-Anruf erfolgreich ist. Sobald Sie Transaktionen haben, tritt das Problem der Parallelitätskontrolle auf. Dann gab es viel Arbeit, um hochparallele Transaktionsdatenstrukturen zu erhalten. Als ich meinen Abschluss machte, ging ich zu Carnegie Mellon und suchte nach einem Arbeitsthema. Mir fiel auf, dass die Berechnungen von einzelnen Computern in Computernetzwerke verschoben wurden. Multiprozessoren würden eine natürliche Fortsetzung des Fortschritts werden - das Wort "Multi-Core" gab es noch nicht. Ich dachte: Was entspricht atomaren Transaktionen für ein Multi-Core-System? Auf keinen Fall gewöhnliche Transaktionen, weil sie zu groß und zu schwer sind. Und so kam ich auf die Idee der Linearisierbarkeit und so kam ich zu all der wartungsfreien Synchronisation. Dies war ein Versuch, die Frage zu beantworten, was ein Analogon von Atomtransaktionen für ein Multiprozessorsystem mit gemeinsamem Speicher ist. Auf den ersten Blick mag diese Arbeit ganz anders aussehen, aber tatsächlich ist sie eine Fortsetzung des gleichen Themas.

Die Welt in Erwartung von Multicore

Vitaliy: Sie haben erwähnt, dass es zu dieser Zeit nur sehr wenige Multicore-Computer gab, oder?

Maurice: Sie waren einfach nicht da. Es gab mehrere sogenannte symmetrische Multiprozessoren, die grundsätzlich an denselben Bus angeschlossen waren. Dies funktionierte nicht sehr gut, da Intel jedes Mal, wenn ein neues Unternehmen etwas Ähnliches entwickelte, einen einzelnen Prozessor herausbrachte, der dem Multiprozessor überlegen war.

Alexei: Bedeutet das, dass es früher eher eine theoretische Studie war?

Maurice: Dies war keine theoretische, sondern eine spekulative Forschung. Bei all dem ging es nicht darum, mit vielen Theoremen zu arbeiten, sondern wir stellten Hypothesen über die Architektur auf, die zu dieser Zeit noch nicht existierten. Dafür ist Forschung nötig! Kein Unternehmen hätte so etwas getan, all dies war etwas aus der fernen Zukunft. Tatsächlich war dies bis 2004, als echte Multi-Core-Prozessoren auftauchten. Aufgrund der Tatsache, dass die Prozessoren überhitzt sind, können Sie den Prozessor noch kleiner machen, aber nicht schneller. Aus diesem Grund gab es einen Übergang zu Mehrkernarchitekturen. Und dann bedeutete dies, dass plötzlich eine Anwendung für alle Konzepte vorhanden war, die wir in der Vergangenheit entwickelt hatten.

Alexei: Warum sind Multi-Core-Prozessoren Ihrer Meinung nach erst in den 2000er Jahren aufgetaucht? Warum also so spät?

Maurice: Dies liegt an Hardwareeinschränkungen. Intel, AMD und andere Unternehmen sind sehr gut darin, die Prozessorgeschwindigkeit zu steigern. Irgendwann wurden die Prozessoren klein genug und konnten die Taktfrequenz nicht mehr erhöhen, da die Prozessoren anfingen zu brennen. Sie können sie kleiner machen, aber nicht schneller. Was in ihrer Macht steht - statt eines sehr kleinen Prozessors passen acht, sechzehn oder zweiunddreißig Prozessoren in das gleiche Volumen des Gehäuses, in dem zuvor nur einer platziert war. Jetzt haben Sie Multithreading und eine schnelle Kommunikation zwischen ihnen, da sie Caches gemeinsam nutzen. Sie können sie jedoch nicht schneller arbeiten lassen - es gibt eine ganz bestimmte Geschwindigkeitsbegrenzung. Sie verbessern sich weiter ein wenig, aber nicht so sehr. Die Gesetze der Physik standen Verbesserungen im Wege.

In die neue Welt - neue Probleme. NUMA-, NVM- und Hacking-Architektur

Alexey: Das klingt sehr vernünftig. Mit den neuen Multi-Core-Prozessoren sind neue Probleme aufgetreten. Haben Sie und Ihre Kollegen diese Probleme erwartet? Vielleicht hast du sie im Voraus studiert? In theoretischen Studien ist es oft nicht einfach, solche Dinge vorherzusagen. Wie haben Probleme Ihre Erwartungen und die Ihrer Kollegen erfüllt? Oder waren sie völlig neu und Sie und Ihre Kollegen mussten viel Zeit damit verbringen, Probleme zu lösen, als sie auftauchten?

Vitaliy: Ich möchte die Frage von Alexei ergänzen: Haben Sie die Architektur von Prozessoren während Ihres Studiums der Theorie richtig vorhergesagt?

Maurice: Nicht alle sind 100%. Aber ich denke, dass meine Kollegen und ich gute Arbeit geleistet haben, um Multi-Core mit gemeinsamem Speicher vorherzusagen. Ich denke, wir haben die Schwierigkeiten bei der Entwicklung paralleler Datenstrukturen, die ohne Sperren funktionieren, richtig vorhergesagt. Solche Datenstrukturen waren für viele Anwendungen wichtig, obwohl nicht für alle, aber oft benötigen Sie wirklich eine Datenstruktur ohne Blockierung. Als wir sie erfanden, behaupteten viele, dass dies Unsinn sei und dass mit Schlössern alles gut funktioniert. Wir haben gut vorausgesagt, dass es vorgefertigte Lösungen für viele Programmierprobleme und Datenstrukturprobleme geben wird. Es gab komplexere Probleme wie NUMA - ungleichmäßiger Zugriff auf den Speicher. Tatsächlich wurden sie vor der Erfindung von Mehrkernprozessoren nicht einmal berücksichtigt, da sie zu spezifisch waren. Die Forschungsgemeinschaft arbeitete an Themen, die allgemein vorhersehbar waren. Einige Hardwareprobleme, die mit bestimmten Architekturen verbunden waren, mussten in den Startlöchern warten - tatsächlich das Erscheinungsbild dieser Architekturen. Zum Beispiel hat niemand wirklich an GPU-spezifischen Datenstrukturen gearbeitet, weil die GPU damals nicht existierte. Obwohl viel Arbeit an SIMD geleistet wurde, waren diese Algorithmen sofort einsatzbereit, sobald geeignete Hardware verfügbar war. Es ist jedoch unmöglich, alles vorherzusehen.

Alexei: Wenn ich das richtig verstehe, ist NUMA eine Art Kompromiss zwischen Kosten, Leistung und einigen anderen Dingen. Irgendeine Idee, warum NUMA so spät kam?

Maurice: Ich denke, dass NUMA aufgrund von Problemen mit der Hardware zur Herstellung von Speicher existiert: Je weiter die Komponenten entfernt sind, desto langsamer ist der Zugriff auf sie. Andererseits ist der zweite Wert dieser Abstraktion die Einheitlichkeit des Gedächtnisses. Daher ist eines der Merkmale des parallelen Rechnens, dass alle Abstraktionen leicht gebrochen sind. Wenn der Zugriff idealerweise einheitlich wäre, wäre der gesamte Speicher gleich weit entfernt, aber dies ist wirtschaftlich und möglicherweise sogar physikalisch unmöglich. Daher entsteht dieser Konflikt. Wenn Sie Ihr Programm so schreiben, als ob der Speicher einheitlich wäre, ist es höchstwahrscheinlich korrekt. In dem Sinne, dass sie nicht die falschen Antworten geben wird. Aber die Leistung ihrer Sterne vom Himmel wird nicht greifen. Wenn Sie Spinlocks schreiben, ohne die Cache-Hierarchie zu verstehen, ist die Sperre selbst korrekt, aber Sie können die Leistung vergessen. - , , , , : , , , . , , .

: ? , ? , . , - .

: . , – , . , , NUMA -, , . – , . - , . , , . , , , . . , . , , , . , - 2000- . , - – , .

. , , . : , . near memory computing . , L1-, TPU – . – . , .

: ( non-volatile memory )?

: , ! NVM , , , . , , . , , . , , . , NVM – , . , , , .

, RISC vs CISC, shared memory vs message passing

: « » ? , : - , , . : . ?

: . . , . - RISC- , Intel , , . , , . , . , , , - , .

: , ? ?

: , , . . - , . , – , , , . - , : «, , - , , , – !». , , . , , , .

: . , , , , . - , - . , .

: , – , . , , , - . , . : , . , -. : , , . , . , , – , . , java.util.concurrent . , – . ( : , Java, ConcurrentSkipListMap, API c ). , , , . , . , , . , : ! - , , .

: , , , java.util.concurrent , , , . : , , - , -. ? , ? ?

: , : , , , . , . , . : , , , , . : , . , , : : , – , . , . , . , , . , , , . . , , , . , , . , .

: , : – , – ?

: . , . , , . : , , , . , .

: , ?

: , . . . - : «, » — , - , . , , : « , ?». . , , , . , - , . - : , . : , .

: , , , , , . , ?

: . , , , – . , Facebook . , , , , . . , , . , : , , – . . , - : , , , , , – . , , , . , – . , .

: . , . , , . - , ?

Maurice: Ich höre oft auf und stelle klassische Fragen. Wird eine Aussage richtig sein oder wie würden sie das diskutierte Problem lösen? Dies ist eine Schlüsselaktion, insbesondere zu Beginn des Unterrichts, wenn es den Leuten peinlich ist, auch nur ein wenig zu sagen. Sie stellen den Schülern eine Frage und sagen nichts weiter. Die Stille setzt ein, jeder spannt sich ein wenig an, die Spannung steigt, dann kann es plötzlich niemand mehr aushalten, bricht zusammen und sagt die Antwort. Sie wenden sich also der Situation zu: Schweigen wird schwieriger und unbequemer als zu antworten! Dies ist ein pädagogischer Standardtrick. Jeder Lehrer auf der Welt muss wissen, wie das geht.

Alexei: Jetzt haben wir einen guten Namen für dieses Interview: "Es ist einfacher zu antworten als zu schweigen."

Vitaliy: Lass mich dich noch einen fragen. Sie arbeiten an topologischen Beweisen. Wie können Sie sich darauf einlassen, denn verteiltes Rechnen und Topologie sind zwei verschiedene Dinge!

Maurice: Es gibt eine versteckte Beziehung. Als ich Student war und Mathematik studierte, studierte ich reine Mathematik. Ich hatte kein wirkliches Interesse an Computern, bis die Ausbildung beendet war, und ich sah mich mit der dringenden Notwendigkeit konfrontiert, nach Arbeit zu suchen. Als Student habe ich algebraische Topologie studiert. Viele Jahre später, als ich an einer Aufgabe namens „k-Set Agreement Problem“ arbeitete , verwendete ich Diagramme, um das Problem zu modellieren, und fand anscheinend eine Lösung. Sie mussten sich nur hinsetzen und die Zählung umgehen. Versuchen Sie, in dieser Spalte eine passende Antwort zu finden. Aber mein Algorithmus funktionierte nicht: Es stellte sich heraus, dass er für immer im Kreis laufen würde. Leider konnte dies alles nicht durch die formale Sprache der Graphentheorie erklärt werden - die alle Experten auf dem Gebiet der Informatik kennen. Und dann erinnerte ich mich daran, dass wir vor vielen Jahren, als wir noch im Topologieunterricht waren, das Konzept des „simplizialen Komplexes“ verwendeten , bei dem es sich um eine Verallgemeinerung von Graphen auf höhere Dimensionen handelt. Dann fragte ich mich: Was wird passieren, wenn wir das Problem in Form von einfachen Komplexen umformulieren? Dies ist zu einem wichtigen Punkt geworden. Bei Verwendung eines stärkeren Formalismus wird das Problem plötzlich viel einfacher. Die Leute hatten lange Zeit damit zu kämpfen, Grafiken zu verwenden, konnten aber nichts tun. Und selbst jetzt können sie nicht - die richtige Antwort war nicht der Algorithmus, sondern der Beweis für die Unmöglichkeit, das Problem zu lösen. Das heißt, ein solcher Algorithmus existiert einfach nicht. Aber jeder Beweis der Unmöglichkeit basiert entweder auf einfachen Komplexen oder auf Dingen, von denen die Leute vorgaben, einfache Komplexe nicht zu berücksichtigen. Durch die Tatsache, dass Sie etwas einen neuen Namen genannt haben, verliert es nicht seine Essenz.

Vitaly: Also hattest du einfach Glück?

Maurice: Neben dem Glück ist es auch die Bereitschaft . Dies bedeutet, dass Sie die zuvor untersuchten „nutzlosen“ Dinge nicht vergessen sollten. Je mehr nutzlose Dinge Sie lernen, desto mehr Ideen können Sie extrahieren, wenn Sie mit einem neuen Problem konfrontiert werden. Solch ein intuitiver Mustervergleich ist wichtig, weil ... Lass es uns tun, das ist die Kette: Zuerst stellte ich fest, dass die Graphen überhaupt nicht oder überhaupt nicht funktionieren. Es erinnerte mich an einige Ereignisse vor acht Jahren und an meine Studentenjahre, als wir all diese einfachen Komplexe studierten . Dies wiederum ermöglichte es mir, mein altes Topologie-Lehrbuch zu finden und es wieder in meinen Kopf zu laden. Ohne dieses alte Wissen wäre ich bei der Lösung des ursprünglichen Problems niemals vorangekommen.

Neue Ausgabe von The Art of Multiprocessor Programming

Alexei: Du hast ein paar Worte über dein Buch gesagt. Dies ist wahrscheinlich nicht das schlimmste Rätsel, dass Sie das berühmteste Multithreading-Buch der Welt, The Art of Multiprocessor Programming, geschrieben haben . Sie ist bereits ungefähr 11 Jahre alt und seitdem wurde nur ein überarbeiteter Nachdruck veröffentlicht . Wird es eine zweite Ausgabe geben?

Maurice: Schön, dass du gefragt hast! Es wird sehr bald sein, in ungefähr drei Monaten. Es gibt zwei weitere Autoren, wir haben viel mehr Material hinzugefügt, den Abschnitt über Fork / Join-Parallelität verbessert, einen Abschnitt über MapReduce geschrieben, viele neue Dinge hinzugefügt und das Unnötige weggeworfen - dass zum Zeitpunkt des Schreibens die erste Ausgabe sehr interessant war, aber heute nicht mehr da ist. Das Ergebnis war ein sehr ernsthaft überarbeitetes Buch.

Alexei: Alles ist bereits erledigt, bleibt es nur noch zu veröffentlichen?

Maurice: Einige Kapitel müssen noch fertiggestellt werden. Unser Verlag (ich glaube, er hasst uns bereits) versucht immer noch zu vermitteln, dass wir schneller arbeiten sollten. Wir sind weit hinter dem Zeitplan. Theoretisch hätten wir dieses Buch ein paar Jahre früher machen können.

Alexei: Gibt es Chancen, vor Weihnachten eine neue Version des Buches zu bekommen?

Maurice: Das ist unser Ziel! Aber ich habe den Sieg so oft vorhergesagt, dass mir sonst niemand glaubt. Du solltest mir wahrscheinlich auch in dieser Angelegenheit nicht vertrauen.

Alexei: Auf jeden Fall sind das fantastische Neuigkeiten. Die erste Ausgabe des Buches hat mir sehr gut gefallen. Man könnte sagen, ich bin ein Fan.

Maurice: Ich hoffe, die neue Ausgabe verdient Ihre Begeisterung, danke!

Wie wurde das Transaktionsgedächtnis erfunden?

Vitaliy: Die nächste Frage betrifft das Transaktionsgedächtnis. So wie ich es verstehe, sind Sie ein Pionier auf diesem Gebiet, Sie haben es zu einer Zeit erfunden, als niemand über solche Dinge nachdachte. Warum haben Sie sich entschieden, in dieses Gebiet zu ziehen? Warum erschienen Ihnen Transaktionen wichtig? Haben Sie jemals gedacht, dass sie in Eisen verkörpert sein werden?

Maurice: Ich kenne Transaktionen seit meinem Abschluss.

Vitaliy: Ja, aber das sind andere Transaktionen!

Maurice: Ich habe mit Elliott Moss an einer nicht blockierenden Müllabfuhr gearbeitet. Unser Problem war, dass wir ein paar Wörter im Speicher atomar ändern wollten, und dann würden die Algorithmen sehr einfach und zumindest einige davon effizienter. Die Verwendung von Compare-and-Swap für Load-Link / Store-Bedingungen, die von der parallelen Architektur bereitgestellt werden, kann etwas bewirken, ist jedoch sehr ineffizient und hässlich, da Sie sich mit Indirektionsebenen befassen müssten. Ich möchte die Speicherwörter ändern und muss wechseln, da ich nur einen Zeiger ändern kann, also muss ich sie auf eine verzeichnisähnliche Struktur verweisen. Wir sprachen darüber, wie wunderbar es wäre, wenn wir das Eisen so wechseln könnten, dass es gleichzeitig aufnehmen könnte. Elliot scheint dies bemerkt zu haben: Wenn Sie sich die Cache-Kohärenzprotokolle ansehen, bieten sie bereits die meisten erforderlichen Funktionen. Bei einer optimistischen Transaktion bemerkt das Cache-Kohärenzprotokoll einen Synchronisationskonflikt und der Cache wird ungültig . Was passiert, wenn Sie spekulativ eine Transaktion in Ihrem Cache starten und die Kohärenzprotokollmechanismen verwenden, um Konflikte zu erkennen? Die spekulative Hardwarearchitektur war einfach zu entwerfen. Also haben wir die allererste Veröffentlichung über das Transaktionsgedächtnis geschrieben. Zur gleichen Zeit entwickelte die Firma Digital Equipment Corporation, für die ich arbeitete, einen neuen 64-Bit-Prozessor namens Alpha. Also machte ich eine Präsentation vor dem Alpha-Entwicklungsteam über unser wunderbares Transaktionsgedächtnis und sie fragten: Welche zusätzlichen Einnahmen erhält unser Unternehmen, wenn wir all dies direkt dem Prozessor hinzufügen? Und darauf hatte ich absolut keine Antwort, weil ich Technologe und kein Marketing-Spezialist bin. Ich hatte wirklich nichts zu beantworten. Sie waren nicht sehr beeindruckt, dass ich nichts wusste.

Vitaliy: Milliarden! Sagen Sie einfach "Milliarden"!

Maurice: Ja, das hätte ich sagen sollen. Jetzt, im Zeitalter von Startups und all dem, weiß ich, wie man einen Geschäftsplan schreibt. Was können Sie ein wenig über die Höhe des potenziellen Gewinns lügen. Aber damals schien es naiv, also sagte ich nur: "Ich weiß es nicht." Wenn Sie sich die Publikationshistorie zum Transaktionsgedächtnis ansehen, werden Sie feststellen, dass es nach einem Jahr mehrere Links dazu gab, und dann hat dieser Artikel etwa zehn Jahre lang überhaupt nicht zitiert. Zitate erschienen um 2004, als echte Multicore erschienen. Als die Leute entdeckten, dass das Schreiben von parallelem Code Geld verdienen kann, begannen neue Forschungen. Ravi Rajwar schrieb einen Artikel , der den Mainstream auf irgendeine Weise in das Konzept des Transaktionsgedächtnisses einführte. (Anmerkung der Redaktion: Der Artikel hat eine zweite Version, die 2010 veröffentlicht wurde und als PDF frei verfügbar ist.) Plötzlich wurde den Leuten klar, wie genau all dies genutzt werden kann und wie herkömmliche beschleunigte Blockierungsalgorithmen beschleunigt werden können. Ein gutes Beispiel für etwas, das in der Vergangenheit als interessantes akademisches Problem erschien. Und ja, wenn Sie mich damals gefragt haben, ob ich denke, dass all dies in Zukunft wichtig sein wird, würde ich sagen: Natürlich, aber wann genau ist es nicht klar. Vielleicht in 50 Jahren? In der Praxis war dies nur ein Jahrzehnt. Es ist sehr schön, wenn man etwas macht, und nach nur zehn Jahren merken es die Leute.

Warum es sich lohnt, auf dem Gebiet des verteilten Rechnens zu forschen

Vitaliy: Wenn wir über neue Forschungsergebnisse sprechen, was würden Sie den Lesern raten - verteiltes Computing oder Multicore und warum?

Maurice: Heutzutage ist es einfach, einen Multi-Core-Prozessor zu bekommen, aber es ist schwieriger, ein echtes verteiltes System einzurichten. Ich habe angefangen, daran zu arbeiten, weil ich etwas anderes als meine Doktorarbeit machen wollte. Dies ist der Rat, den ich Anfängern immer gebe: Schreiben Sie keine Fortsetzung der Dissertation - versuchen Sie, in eine neue Richtung zu gehen. Und doch ist Multithreading einfach. Ich kann mit meiner eigenen Gabel experimentieren, die auf einem Laptop läuft, ohne aus dem Bett zu kommen. Aber wenn ich plötzlich ein wirklich verteiltes System schaffen wollte, musste ich viel arbeiten, Studenten anziehen und so weiter. Ich bin eine faule Person und würde es vorziehen, an Multicore zu arbeiten. Experimente mit Multicore-Systemen sind ebenfalls einfacher als mit verteilten Systemen, da selbst in einem dummen verteilten System zu viele Faktoren gesteuert werden müssen.

Vitaliy: Was machst du jetzt, um die Blockchain zu erkunden? Auf welche Artikel sollten Sie zuerst achten?

Maurice: Kürzlich erschien ein sehr guter Artikel , den ich mit meinem Schüler Vikram Saraf geschrieben habe, speziell, weil ich vor drei Wochen auf der Tokenomcs-Konferenz in Paris gesprochen habe. In diesem Artikel geht es um praktische verteilte Systeme, in denen wir vorschlagen, Ethereum multithreaded zu machen. Jetzt werden intelligente Verträge (Code, der in der Blockchain ausgeführt wird) nacheinander ausgeführt. Wir haben vorhin einen Artikel geschrieben, in dem es darum ging, spekulative Transaktionen zu verwenden, um den Prozess zu beschleunigen. Wir haben viele Ideen aus dem Transaktionssoftware-Speicher übernommen und gesagt, dass alles schneller funktioniert, wenn Sie diese Ideen in die virtuelle Etherium-Maschine integrieren. Dafür ist es jedoch erforderlich, dass es in den Verträgen nach den Daten keine Konflikte gibt. Und dann haben wir vorgeschlagen, dass es im wirklichen Leben wirklich keine solchen Konflikte gibt. Aber wir hatten keine Gelegenheit, es herauszufinden. Dann kam uns der Gedanke, dass wir fast zehn Jahre Geschichte mit echten Verträgen zur Hand hatten, also luden wir die Etherium-Blockchain aus und fragten uns: Was würde passieren, wenn diese historischen Aufzeichnungen parallel durchgeführt würden? Wir haben eine deutliche Geschwindigkeitssteigerung festgestellt. In den frühen Tagen von Etherium hat die Geschwindigkeit sehr stark zugenommen, aber heute ist es etwas komplizierter, da es weniger Verträge gibt und die Wahrscheinlichkeit von Konflikten um Daten, die eine Serialisierung erfordern, höher ist. Aber all dies ist experimentelle Arbeit mit realen historischen Daten. Das Schöne an der Blockchain ist, dass sie sich für immer an alles erinnert, sodass Sie in die Vergangenheit reisen und untersuchen können, was passieren würde, wenn wir andere Algorithmen zum Ausführen des Codes verwenden würden. Wie die Menschen dort in der Vergangenheit unsere neue Idee mögen würden. Solche Recherchen sind viel einfacher und unterhaltsamer, weil es eine Sache gibt, die alles überwacht und alles aufzeichnet. Dies ist der Soziologie bereits etwas ähnlicher als der Entwicklung von Algorithmen.

Hat die Entwicklung von Algorithmen aufgehört und wie man weiterlebt

Vitaliy: Die Zeit der letzten theoretischen Frage! Haben Sie das Gefühl, dass die Veränderungen in den wettbewerbsorientierten Datenstrukturen von Jahr zu Jahr kleiner werden? Denken Sie, wir haben ein Plateau in unserem Verständnis von Datenstrukturen erreicht, oder wird es wesentliche Verbesserungen geben? Vielleicht gibt es einige knifflige Ideen, die alles komplett verändern können?

Maurice: Möglicherweise haben wir ein Plateau in den Datenstrukturen für traditionelle Architekturen erreicht. Datenstrukturen für neue Architekturen sind jedoch nach wie vor ein vielversprechender Bereich. Wenn Sie beispielsweise Datenstrukturen für Hardwarebeschleuniger erstellen möchten, unterscheiden sich die Datenstrukturen für die GPU stark von den Datenstrukturen für die CPU. Wenn Sie Datenstrukturen für Blockchains entwickeln, müssen Sie die Daten hashen und dann in einen Merkle-Baum einfügen , um Fälschungen zu vermeiden. In diesem Bereich hat die Aktivität in letzter Zeit stark zugenommen, viele leisten sehr gute Arbeit. Ich denke jedoch, dass neue Architekturen und Anwendungen zu neuen Datenstrukturen führen werden. Alte Anwendungen und traditionelle Architektur - vielleicht gibt es dort nicht viel Raum für Forschung. Aber wenn Sie die ausgetretenen Pfade verlassen und über den Rand schauen, werden Sie verrückte Dinge sehen, die der Mainstream nicht ernst nimmt - hier passieren wirklich all die aufregenden Dinge.

Vitaliy: Um ein sehr berühmter Forscher zu sein, musste ich meine eigene Architektur erfinden :-)

Maurice: Sie können die neue Architektur eines anderen "stehlen" - es scheint viel einfacher zu sein!

Jobs an der Brown University

Vitaliy: Können Sie uns mehr über die Brown University erzählen, an der Sie arbeiten? Über ihn ist im Kontext der Informationstechnologie nicht viel bekannt. Zum Beispiel weniger als über MIT.

Maurice: Die Brown University ist eine der ältesten Universitäten in den Vereinigten Staaten. Ich denke nur Harvard ist etwas älter. Brown ist Teil der sogenannten Ivy League , einer Sammlung von acht der ältesten Universitäten. Harvard, Brown, Cornell, Yale, Kolumbien, Dartmouth, PA, Princeton. Es ist eine Art alte, kleine und leicht aristokratische Universität. Der Schwerpunkt liegt auf der humanitären Bildung. Er versucht nicht wie MIT zu sein, MIT ist sehr spezialisiert und technisch. Brown ist ein großartiger Ort, um russische Literatur oder die klassische griechische Sprache und natürlich Informatik zu studieren. Er konzentriert sich auf umfassende Ausbildung. Die meisten unserer Studenten gehen zu Facebook, Apple, Google - daher denke ich, dass unsere Studenten keine Probleme haben, sich in der Branche niederzulassen. Ich habe in Brown gearbeitet, weil ich vorher bei der Digital Equipment Corporation in Boston gearbeitet habe. Es war ein Unternehmen, das viele interessante Dinge erfand, aber die Bedeutung von PCs bestritt. Ein Unternehmen mit einem schwierigen Schicksal, dessen Gründer einst junge Revolutionäre waren, sie lernten nichts und vergaßen nichts, und so wandelten sie sich für etwa ein Dutzend Jahre von Revolutionären zu Reaktionären. Sie scherzten gern darüber, dass PCs einen Platz in der Garage hatten - natürlich in einer verlassenen Garage. Es ist offensichtlich, dass sie von flexibleren Unternehmen zerstört wurden. Als klar wurde, dass die Firma Probleme hatte, rief ich meinen Freund aus Brown an, der ungefähr eine Stunde von Boston entfernt war. Ich wollte Boston damals nicht verlassen, weil es an vielen Universitäten nicht viele offene Stellen gab. Es war eine Zeit, in der es auf dem Gebiet der Informatik nicht mehr so viele offene Stellen gab wie jetzt. Aber Brown hatte eine freie Stelle, ich musste nicht von meinem Haus wegziehen, ich musste meine Familie nicht umziehen und ich lebe wirklich gerne in Boston! Also beschloss ich, nach Brown zu gehen. Es hat mir gefallen. Die Schüler sind wundervoll, deshalb habe ich nie versucht, woanders hinzugehen. In einem kreativen Urlaub habe ich ein Jahr bei Microsoft gearbeitet, war ein Jahr bei Technion in Haifa und jetzt bin ich in Algorand. Ich habe überall viele Kollegen und daher ist der physische Ort unserer Schulungen nicht so wichtig. Aber das Wichtigste sind die Studenten, sie sind die Besten hier. Ich habe nie versucht, irgendwohin zu gehen, weil ich auch hier ziemlich glücklich bin.

Trotz Browns Ruhm in den USA ist er im Ausland überraschend unbekannt. Wie Sie sehen, gebe ich jetzt mein Bestes, um diesen Zustand zu korrigieren.

Der Unterschied zwischen Forschung an der Universität und innerhalb des Unternehmens

Vitaliy: Nun, die nächste Frage betrifft digitale Geräte. Sie waren dort Forscher. Was ist der Unterschied zwischen der Arbeit in der Forschungs- und Entwicklungsabteilung eines großen Unternehmens und der Arbeit an einer Universität? Was sind die Vor- und Nachteile?

Maurice: Zwanzig Jahre lang habe ich bei Microsoft gearbeitet und eng mit Mitarbeitern von Sun Microsystems, Oracle, Facebook und jetzt Algorand zusammengearbeitet. Vor diesem Hintergrund möchte ich sagen, dass es möglich ist, erstklassige Forschung in Unternehmen und an der Universität durchzuführen. Der wichtige Unterschied besteht darin, dass Sie im Unternehmen mit Kollegen zusammenarbeiten. Wenn ich plötzlich auf die Idee eines Projekts komme, das es noch nicht gibt, muss ich meine Kollegen davon überzeugen, dass dies eine gute Idee ist. Wenn ich in Brown bin, kann ich meinen Schülern sagen: Lass uns an der Antigravitation arbeiten! Sie werden entweder zu jemand anderem gehen oder das Projekt übernehmen. Ja, ich muss eine Finanzierung finden, ich muss einen Zuschussantrag schreiben und so weiter. In jedem Fall wird es immer viele Studenten geben, und Sie können einseitig Entscheidungen treffen. Aber an der Universität werden Sie höchstwahrscheinlich nicht mit Leuten Ihres Niveaus arbeiten. In der Welt der industriellen Forschung müssen Sie zunächst alle davon überzeugen, dass es sich lohnt, Ihr Projekt zu übernehmen. . , - , – . -, , , «, , , ». . , , , . , - , - . , , . , , – ! , . , . .

: , , .

: , . , -: - , - . Microsoft Facebook : , . , , – . , , .

Hydra SPTDC

: , .

: , . , ?

: !

: , SPTDC – . SPTCC , (C D, Concurrent Distributed), , , , . Hydra ?

: . , , , . - – . , - . . proof-of-work, -, .

, , , . , , , – , , .

: , , . . , , , 120 . , , , . Hydra . , , ?

: ? , ?

: . , . , ? – . , - . . , . , , – . .

, . , , , , SPTDC Hydra 2019!

Hydra 2019, 11-12 2019 -. «Blockchains and the future of distributed computing» . .

"Es ist einfacher zu antworten als zu schweigen" - ein großes Interview mit dem Vater des Transaktionsgedächtnisses, Maurice Herlichi