19 heads of hydra. Big review of the program

July 11-12, St. Petersburg will host the Hydra conference dedicated to the development of parallel and distributed systems. Hydra's trick is that it unites tough scientists (which usually can be found only at foreign scientific conferences) and famous practicing engineers in one big program at the intersection of science and practice.

Hydra is one of our most important conferences in the last few years. It was preceded by a very serious preparation, selection of speakers and reports. Last week , an interview with the director of the company JUG.ru Group, Alexey Fedorov ( 23derevo ), was released.

We have already talked about three important participants, the founders of the theory of distributed systems - Leslie Lamport, Maurice Hurliha and Michael Scott. It is time to talk in more detail about the entire program!

Motivation

If you are engaged in programming, then somehow deal with multithreading and distributed computing. Specialists in their respective fields work directly with them, but implicitly, distribution looks at us from everywhere: in any multi-core computer or distributed service, there is something that performs the computations in parallel.

There are many conferences that reveal certain aspects of application programming. On the other side of the spectrum, we have special scientific schools, which in the format of lectures reveal huge amounts of complex theory. For example, in parallel with the Hydra in St. Petersburg is school SPTDC . At the Hydra conference, we tried to bring together harsh practices, science, and everything at their interface.

Think about this: we live in an amazing time when you can meet the founders of the field of science and engineering that we are doing. Physicists will not meet neither Newton nor Einstein - the train has left. But those who have laid the foundations of the theory of distributed systems, come up with popular programming languages, and put it all into working prototypes for the first time still live with us. These people have not quit their jobs halfway, right now are working on topical tasks at world-renowned universities and companies, and are the greatest sources of knowledge and experience today.

On the other hand, the opportunity to meet with them usually remains purely theoretical: few of us can constantly monitor public events at some University of Rochester in order to rush to the USA and back to the lecture to Michael Scott. Visiting all Hydra members altogether would have turned out in a small state, apart from the abyss of time spent (although this sounds like an interesting quest).

On the other hand, we have a lot of top engineers who are working right now on the actual problems of distributed systems, and they definitely have something to tell. But the problem is that they work , and their time is precious. Yes, if you are an employee of Microsoft, Google or JetBrains, the probability of meeting one of the well-known speakers at an internal event increases dramatically, but in general, no, it does not happen every day.

Thus, the Hydra conference performs an important task that most of us cannot do on our own - in one place and at the same time brings together people whose ideas or communication with whom can change your life. I admit that absolutely not everyone needs distributed systems, some complex fundamental things. You can program CRUDs for PHP until the end of your life and stay quite happy. But who needs is your chance.

From the first announcement of the Hydra conference on Habré, quite a lot of time has passed. During this time, a lot of work has been done - and here, we have a list of almost all the reports. No jerky single-threaded algorithms, just pure distributed hardcore! Let's finish with common words, and see what we now have on hand.

Keynouts

Keynouts start and end conference days. Usually, the meaning of the opening keyout is to set the general spirit and direction of the conference. The closing keyout draws a line and explains how we live with the knowledge and skills acquired during the conference days. Beginning and end: what will be remembered best of all, and in general, is of increased importance.

Cliff Click - The H2O distributed K / V algorithm

Cliff is a legend in the Java world. In the late 90s for the PhD thesis, he wrote a paper called “Combining Analyses, Combining Optimizations” , which after some time became the basis for the HotSpot JVM Server Compiler. Two years later, he worked at Sun Microsystems on JVM and showed the world that JIT has a right to exist. This whole story about the fact that Java is one of the fastest modern runtimes with the smartest and fastest optimizations went exactly from Cliff Klik. At the very beginning it was believed that if something is available to the static compiler, it is possible not to even try to jitter. Thanks to the work of Cliff and the team, all new languages ​​began to be created with the idea of ​​a JIT compilation by default. Of course, this was not work for one person, but Cliff played a very important role in it.

In the opening keyout, Cliff will talk about his other undertaking - H20 , an in-memory platform for distributed and scalable machine learning for industrial applications. Or rather, about the distributed repository of key-value pairs inside it. This is a very fast repository with lots of interesting properties (the exact list is in the description ), which allow you to use similar solutions in the mathematics of big data streaming.

Another talk that Cliff will make is The Azul Hardware Transactional Memory experience . Another part of his biography is ten years of work at Azul , where he updated and improved a lot of things in the hardware and the Azul stack: JIT compilers, runtime, thread model, error handling, work with the stack, hardware interrupts, class loading, etc. the like - well, you understand.

The most interesting part started when they made hardware for big business - a supercomputer for running Java. It was a rather innovative piece, sharpened specifically for Java, which has special requirements - reading memory barriers for low-paged garbage collection, arrays with border checking, virtual calls ... One of the coolest technologies is hardware transactional memory. The entire L1 of any of the 864 cores could participate in the transactional record, which is especially important for working with locks in Java (synchronized blocks can work in parallel, as long as there is no real conflict over memory). But the beautiful idea broke about the harsh reality - and in this report Cliff will explain why HTM and STM are not well suited for the practical needs of multi-threaded computing.

Michael Scott - Dual data structures

Michael Scott is a professor of Computer Science at the University of Rochester, with whom fate had already bound him for 34 years , and at his native university at Wisconsin – Madison, he was dean for five years. He is engaged in research in the field of parallel and distributed programming and language design and teaches students this.

The whole world knows Michael thanks to the textbook "Programming Language Pragmatics" , the latest edition of which was published relatively recently - in 2015. His work "Algorithms for scalable synchronization on shared-memory multiprocessors" won the Dijkstra Award as one of the most well-known in the field of distributed computing and is openly in the online library of the University of Rochester. You can also know him as the author of the very algorithm Michael Scott from “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms” .

As for the Java world, here is a special case: together with Doug Lea, he developed those non-blocking algorithms and synchronous queues on which Java libraries work. This is what the dual data structures keyout will be about - the implementation of these structures in Java SE 6 allowed us to improve java.util.concurrent.ThreadPoolExecutor performance 10 times. If you are wondering in advance what these “Dual data structures” are, then this is the corresponding work .

Maurice Herlihy - Blockchains

Maurice Herlihy is the winner of two Dijkstra awards. The first is for the work on Wait-Free Synchronization (Brown University), and the second, more recent, is Transactional Memory: Architectural Support for Lock-Free Data Structures (Virginia Tech University). The Dijkstra Prize is given for works whose significance and influence have been noticeable for at least ten years, and it is obvious that Maurice is one of the most famous experts in the field. He currently works as a professor at Brown University and has many advances a whole paragraph long.

On this closing keyout, Maurice will talk about the theory and practice of blockchain distributed systems from the point of view of the classic of distributed computing and how it simplifies many related problems. This is a report exclusively on the topic of the conference - not at all about the mining HYIP, but rather about how our knowledge can be amazingly efficiently and appropriately applied to a variety of tasks.

In July 2017, Maurice had already arrived in Russia at the SPTDC school, participated in the JUG.ru mitap, and you can watch the recording on YouTube:

Main program

Next will be a small overview of the reports included in the program. Some of the reports are described here in detail, some - more shortly. Long descriptions got mostly English-language reports that require references to scientific work, terms on Wikipedia, and so on. The full list can be seen on the conference website . The list on the site will be updated and supplemented.

Leslie Lamport - Q & A

Leslie Lamport is the author of the fundamental works in distributed computing. "LaTeX" stands for "Lamport TeX". It was he who, for the first time, in 1979, introduced the concept of sequential consistency , and his article “How to Make Multiprocess Programs” won the Dijkstra Prize.

This is the most unusual part of the program, because it is not even a report, but a question and answer session. When a significant part of the audience is already familiar (or can get acquainted) with all sorts of works based on the “Lamport theory”, his own articles and reports, it is more important to spend all the available time on direct communication.

The idea is simple - you’re watching two reports on YouTube: “Programming Should Be More Than Coding” and “If You’re Not Writing a Program, Don't Use a Programming Language” and prepare at least one question, and Leslie answers.

The first of these two videos we have already turned into habrostatyu . If you do not have an hour to watch the video, you can quickly read all this in the form of text.

Note: YouTube has a lot more videos from Leslie Lamport. For example, there is an excellent course on TLA + . The offline version of this entire course is on the author's home page , and he poured it on YouTube for easier viewing on mobile devices.

Martin Kleppmann - Synced Data

Martin Kleppmann is a researcher at the University of Cambridge working on CRDT and formal verification of algorithms. Martin 's book Designing Data-Intensive Applications , published in 2017, was very successful and hit the bestseller lists in the field of data storage and processing. Kevin Scott, CTO at Microsoft, once said : “This book should be mandatory for development engineers. This is a rare resource that combines theory and practice, helping developers smarter design and implement infrastructure and data processing systems. ” Something similar said and the creator of Kafka and CTO Confluent, Jay Kreps.

Before taking up academic research, Martin worked in the industry and co-founded two successful startups:

• Rapportive, dedicated to displaying the social profile of contacts from your email, which LinkedIn bought in 2012;
• Go Test It, a service for automatically checking websites in various browsers that RedGate bought in 2009.

In general, Martin, although less well-known than our key scooters, was already able to make some contribution to the development of distributed computing and to the industry.

In this report, Martin will talk about a topic that is closer to his academic research. In Google Docs and a similar co-author for joint editing of documents, “joint editing” means the task of replication: each user has his own replica of a common document, which they then modify, and all changes are sent over the network to the other participants. Changes to documents offline results in a temporary inconsistency of the document with respect to the other participants, and re-synchronization requires handling conflicts. Just for this there are Conflict-free Replicated Data Types (CRDT), in fact - quite a new thing, the essence of which was formulated only in 2011. This report discusses what has happened since then in the CRDT world, what are the most recent advances, discusses the approach to creating local-first applications in general, and using the open source Automerge library in particular.

Next week we will publish on Habré a great interview with Martin, it will be interesting.

Data wait and free transactions

Pedro has been working at Cisco and has been developing parallel algorithms for the last ten years, including synchronization mechanisms, lock-free and wait-free data structures, and everything you can imagine on this topic. His current research and engineering interests are focused on Universal Constructions, Software Transactional Memory, Persistent Memory and similar technologies that enable the implementation of correct, scalable and fault-tolerant applications. And he is the author of the widely known in narrow circles blog Concurrency Freaks .

On parallel data structures, most multi-threaded applications are now running, starting with the use of message queues between actors and ending with indexed data structures in key-value repositories. In Java JDK, they have been working successfully for many years, and they are slowly added to C ++.

The simplest way to implement a parallel data structure is a sequential (single-threaded) implementation in which the methods are protected by mutexes. This is available to any jun, but has obvious problems with scaling and performance. At the same time, the lock-free and wait-free data structures not only better cope with errors, but also have a better performance profile - however, their development requires deep expertise and adaptation to a specific method of application. One wrong line of code is enough to break everything.

How to make so that even a non-expert can design and implement such data structures? It is known that any sequential algorithm can be made thread-safe using either a universal construction or transactional memory. Behind one they can lower the threshold of entry into the solution of this problem. However, both solutions tend to lead to inefficient implementation. Pedro will talk about how they managed to make these constructions more efficient and how they can be used for their algorithms.

Heidi Howard - Liberating distributed consensus

Heidi Howard - like Martin, a researcher of distributed systems at the University of Cambridge. Her specialization is consistency, fault tolerance, performance, and distributed consensus. It is best known for generalizing the Paxos algorithm called Flexible Paxos .

Recall that Paxos is a family of protocols for solving the problem of consensus in a network of unreliable evaluators, which are based on the work of Leslie Lamport. Thus, some of our speakers work on tasks originally proposed by our other speakers — and this is wonderful.

The ability to find consensus between multiple hosts — for addressing, choosing a leader, blocking, or coordination — is a fundamental issue in modern distributed systems. Paxos is now the main way to solve problems of finding a consensus, and around it a lot of research is being carried out to expand and optimize the algorithm for various practical needs.

In this report, we will revisit the theoretical basis of Paxos, weakening the initial requirements and generalizing the algorithm. We will see that Paxos, in fact, is only one of the options among the vast range of approaches to consensus, and that other points of the spectrum are also very useful for building good distributed systems.

Alex Petrov - Reduce Your Storage Costs with Transient Replication and Cheap Quorums

Alex is a database and storage specialist and what's most important to us is a committer in Cassandra . Together with O'Reilly, he is currently working on the Database Internals book.

For systems with eventual consistency (in Russian terminology - “consistency in the long run”), after a node is dropped or a network is divided, the following dilemma must be solved: either continue to fulfill requests, sacrificing consistency, or deny their execution and sacrifice availability. In such a system, quorums, overlapping subsets of nodes and ensuring that at least one node contains the latest value, can be a good borderline solution. You can survive failures and loss of connection to some nodes, while continuing to respond with the most recent values.

However, everything has its price. A quorum replication scheme means increased storage costs: you need to store redundant data on several nodes at once to guarantee a sufficient number of available copies at the time of the problem. It turns out that you can not store all the data on all replicas. You can reduce the load on the storage, if you keep the data only on parts of the nodes, and use special nodes (Transient Replica) for failure handling scenarios.

In the course of the report, we will look at Witness Replicas , the replication scheme used in Spanner and Megastore , and the implementation of this concept in Apache Cassandra called Transient Replication & Cheap Quorums .

Dmitry Vyukov - Goroutines exposed

Dmitry is a Google developer working on dynamic testing of C / C ++ and Go - Address / Memory / ThreadSanitizer, and similar tools for the Linux kernel. In Go, I managed a scalable gorutin scheduler, network poller and parallel garbage collector. He is an expert in multithreading, the author of a dozen of new non-blocking algorithms and is the owner of Intel's Black Belt .

Now a little about the report itself. Go language has native support for multithreading in the form of gorutin (light threads) and channels (FIFO queues). Thanks to these mechanisms, it is very easy and pleasant for users to write modern multi-threaded applications, and it looks like magic. As we understand, there is no magic here. In this report, Dmitry will delve into the subtleties of the work of the Go planner and will reveal the secrets of the implementation of this "magic." First, he will give an overview of the main components of the scheduler, tell you how it works. Next, we will take a closer look at certain aspects like parking / unparking strategies and handling of blocking system calls. Finally, Dmitry will talk a little about possible improvements in the planner.

Dmitry Bugaychenko - Accelerating Distributed Graph Analysis Using Probabilistic Sketches and Not Only

Dmitry has been working in outsourcing for almost 9 years without losing contact with the university and the scientific community. Big data analysis at Odnoklassniki became for him a unique chance to combine theoretical training and a scientific foundation with the development of real, sought-after products.

Distributed analysis of graphs has been and remains a challenge: when it becomes necessary to obtain information about the connections of a neighboring vertex, data often has to be distilled between machines, which leads to an increase in execution time and load on the network infrastructure. In this report, we will see how you can get a significant acceleration of processing using probabilistic data structures or facts like the symmetry of a friend's graph in a social network. All this is illustrated by code examples on Apache Spark.

Denis Rystsov - Reduce your storage costs with Transient Replication and Cheap Quorums

Denis is the developer of Cosmos DB , an expert in consistency model validation, consensus algorithms and distributed transactions. He now works at Microsoft, and before that he was engaged in distributed systems in Amazon and Yandex.

In this report, we will introduce distributed transaction protocols, invented over the past few years, which can be implemented on the client side on top of any data warehouse that supports conditional update (compare and set). The bottom line is that life does not end with a two-phase commit, transactions can be added on top of any databases — at the application level, but different protocols (2PC, Percolator, RAMP) have different tradeoffs and are not given to us for free.

Alexey Zinoviev - Not all ML-algorithms fall into distributed paradise

Alexey ( zaleslaw ) is our long-time speaker and member of program committees at other conferences. Practicing trainer in the company EPAM Systems, and with Hadoop / Spark and other biogdata friends since 2012.

In this report, Alexey will talk about the problems of adapting classical machine learning algorithms to run in distributed mode based on his experience with Apache Spark ML, Apache Mahout, Apache Flink ML, and the experience of creating Apache Ignite ML. Alexey will also talk about the implementation of distributed ML-algorithms in these frameworks.

And finally - two reports from Yandex about Yandex Database.

Vladislav Kuznetsov - Yandex Database - how do we ensure resiliency

Vladislav is a developer at Yandex in a group of distributed platform. Yandex Database is a horizontally scalable geo-distributed fault-tolerant DBMS that can withstand the failure of disks, servers, racks and data centers without compromising consistency. To ensure resiliency, we use our own algorithm for achieving a distributed consensus, as well as a number of technical solutions, which are discussed in detail in the report. The report may be of interest both to developers of DBMS, and developers of applied solutions based on DBMS.

Semen Checherinda - Distributed Transactions in YDB

Semen is a developer in the group of distributed platform in Yandex, working on the possibility of multi-tenant use of the YDB installation.

Yandex Database is designed for OLTP requests and meets the ACID requirements for a transaction system. In the report we will consider the transaction planning algorithm that underlies the YDB transaction system. Let us examine which entities participate in transactions, who assigns global order to transactions, how transaction atomicity, reliability, and strict isolation levels are achieved. Using the example of a common task, we consider the implementation of transactions using a two-phase commit and deterministic transactions. Let's discuss their differences.

What's next?

The conference program continues to be filled with new reports. In particular, we expect a report from Nikita Koval ( ndkoval ) from JetBrains and Oleg Anastasyev ( m0nstermind ) from the company Odnoklassniki. Nikita deals with algorithms for Corutin in the Kotlin team, and Oleg develops architecture and solutions for high-load systems in the Odnoklassniki platform. In addition, there is 1 conditionally empty slot, with candidates for which the program committee is working right now.

The Hydra Conference will be held July 11-12 in St. Petersburg. Tickets can be purchased on the official website . Pay attention to the availability of online-tickets - if for some reason you can not live to get to Peter these days.

See you at Hydra!