Actor Models 40 years
High-load systems built on the model of actors is a trend of the present time. Here is a far from complete list of articles on Habré, in which, to one degree or another, this model or one of its implementations is mentioned, for example, 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 . There is a good Wikipedia article telling about actors. Unfortunately, after reading it, I still have a lot of questions, the answers to which I could find only in the original sources. I want to present the results of this review to your attention.
Are actors a set of practices, a development methodology, an architectural pattern, a marketing move?
In my university course, like many, the concept of computability was defined through the Turing and Post machines. The machine has a state - a set of values of all the cells of the tape. The calculation process is a sequence of machine steps, each of which changes its state. Each step of the machine is the execution of one atomic indivisible action (operation). Further I will call it the traditional model of computing.
This interpretation of calculations leads to the concept of global time, when one and only one atomic operation can be performed at the same time. This property is essentially used to prove the properties of various synchronization primitives in the case of multi-threaded programming on single-processor machines, for example, in the book Gregory R. Andrews Basics of multi-threaded, parallel and distributed programming .
')
For multiprocessor machines or distributed systems, the requirement of global time is generally unacceptable. Therefore, it is necessary to generalize the concept of computability to the case of parallel computations. One of such generalizations is the model of actors.
The appearance of this model in the distant 70s was due to the strong belief that the next generation machines will be multiprocessing, and the programs will have artificial intelligence. In 1973, Carl Hewitt , Peter Bishop and Richard Steiger published an article: A Universal Modular Formalism For Artificial Intelligent . In this article, they introduced the concept of actor and explained that many classes of applications are a special case of the model of actors. By the way, this year was the 40th anniversary!
Actor is a universal abstraction of a computational entity, which, in response to a received message
The difference between them is the same as between a telephone and sending a message by mail. In the first case (this is a calculation based on global time), if several people try to call one phone number, then they begin to compete for access to the common shared resource - the addressee. Office PBXs, multichannel phones, software for call-centers - all this (a la synchronization primitives) is needed in order to ensure efficient processing of incoming calls. In the case of mailing, the sender of the letter (actor) simply sends the letter to the addressee without any delay due to the need to coordinate their actions with other senders. But! However, we do not know when the recipient will read our letter.
The two biggest specialists are Carl Hewitt and his student Gul A. Agha . Hewitt mainly deals with the rigorous rationale that other approaches to computability are a special case of the actor model, and Agha is a different application for distributed systems.
Each of the results in itself is a topic for a separate large article, so I will only give a summary and a link to the source.
Events in the model of actors form a partially ordered set. The axiomatics of this set called Ordering Laws was described by Carl Hewitt and Henry Baker in the article Actors and Continous Functionals (1977). There are a lot of axioms, and their point is to prove that the model of actors is suitable for use in practice, for example, that at any given time the number of messages addressed to one recipient is, of course.
In 1985, Gul A. Agha, under the leadership of Hewitt, defended his thesis on Actors: A Model Of Concurrent Computations in Distributed Systems . In the dissertation, Agha describes the syntax of a minimal programming language that supports actors, as well as a set of typical problems and methods for solving them (Chapter 4).
Another important contribution to practical approaches to the implementation of the model of actors can be considered the article Phillip Haller and Martin Odersky Event-Based Programming without Inversion Control . It proposed a new approach for the development of actor systems, which was used in Scala. Its essence is that the resulting parallel program for writing is very similar to "regular sequential" programming.
The same path, for example, was chosen for developing C #. Here are the actors on C # 5:
Here, the await keyword implies an asynchronous call to the corresponding method and a return to the calculations when the answer is received.
In 2011, Gul A. Aga and Karmani summed up many years of experience in the implementation of actor systems, describing the most common method of implementation. They called it Fog Cutter . True, Hewitt has repeatedly criticized such an architecture, for example, here and here. The essence of criticism is that this is just one of the possible implementations of a particular case of a model that does not fully implement the entire actor model.
Indeed, in the dissertation of the Foundations of Actor Semantics William Duglas Clinger (student of Carl Hewitt) shows that the actor model has unlimited non-determinism, while the Turing machine is boundedly non-deterministic. From this, he and Carl Hewitt conclude that there are algorithms that can be implemented in the actor model, but cannot be implemented on a Turing machine. Therefore, any attempt to implement the actor model on "ordinary" computers that implement Turing computability will result in the realization of only a special case of the actor model.
In 1988, Robert Kowalski , the creator of the Prologue, advanced the thesis that “calculations can be grouped according to logical conclusions”. This is true for sequential calculations and for some parallel models. But in 1988, Hewitt and Agha published the article Guarded Horn clause? in which it was shown that for the actor model this is incorrect in the following sense: the current state of the program can deductively not follow from the previous one. What this means in practice: debugging a program based on the model of actors is not as effective as in the case of sequential programs.
Why do functional languages arise wherever it comes to parallel programming? To answer this question, consider a small example in C ++:
Since this piece of code does not contain I / O operations, in order to allow another thread to execute its code on the same processor core, it is necessary to wait until the operating system's thread scheduler forcibly switches threads. This can occur either when a call to a system function occurs in another thread, or upon a timer event. By default, the timer event triggers 1 time in 15.6 ms , it explains why you should not reduce this time to 1 ms. It turns out that the imperative style allows you to write a "greedy" program that tries to single-handedly use all the processor resources, and we have limited resources to influence it.
Rewrite this program through tail recursion.
Forgive me admirers of functional programming languages for such a free interpretation, but my goal is only to demonstrate the idea.
The loop iteration is replaced by a function call. Suppose that the compiler embeds a code at the call point of each function to count the time spent executing the current thread and switching to another thread if necessary. Now we have the opportunity to switch from one stream to another within nanoseconds. The same idea allows to implement lightweight streams, for example, as in Erlang.
For these properties, functional languages are convenient to use where parallelism and real-time response is needed.
If you need a very fast response, then functional languages are beyond competition, but what if during the processing of a request we have to contact the database, and the response time from it is about 50-100 ms, or we have to perform many calculations, that is, to perform many function calls . The overhead costs associated with calculating the execution time and switching threads for each call make themselves felt, and imperative languages are more efficient in this case. To verify this, just look at the site benchmarksgame.alioth.debian.org . The site offers to measure the performance of programs written in different languages, comparing the solutions of the same problem. Here are some examples of comparisons: reverse-complement , mandelbrot , regex-dna , pidigits .
At once I will make a reservation, firstly, these are only tests - it is not necessary to take them very seriously. On the other hand, anyone who is dissatisfied with the position of their favorite programming language can offer their own solution and change the alignment of forces. Secondly, I cited only those links where imperative languages benefit from a clear advantage, because my goal is only to illustrate the idea expressed a few paragraphs earlier about the overhead costs associated with the organization of parallelism.
Another interesting observation is the implementation of the model of actors in imperative languages, as a rule, in tests above the functional Erlang. Again, make a reservation, everyone knows that Erlang is good not in calculations, namely, where an instant response is needed, but this only once again confirms the idea of overhead costs.
I will cite one metaphor: there are runners for long distances - marathon runners, and there are - for short - sprinters. Some are required endurance at low average speed (relative to the sprinters), and the second - the maximum performance in a very short time (relative to the marathon). Alas, it’s just physiologically impossible to show equally high results at sprint and marathon distances, simply because completely different properties are required from the muscles. These runners are distinguished even by their figures: marathon runners are dry and sinewy, and sprinters are athletic and muscular.
Another confirmation that the parallel programming is not so simple, is a project to create a 5th generation of computers.
In the 1980s, an attempt was made in Japan to create computers of the 5th generation . The project was initiated again by the belief that the future is parallel computing, large databases and logical processing of large databases.
It was spent 500 million dollars in the prices of the 80s. The project lasted 10 years and ended in complete failure! Parallel programs did not give significant performance advantages over single-threaded ones. And for decades, Intel has taken the palm with its single-threaded processors. And only when the processor manufacturers came up against the technological limitations of increasing the clock frequencies, the idea of parallelism began to gain popularity again.
The performance issues discussed above, as well as the fact that Hewitt insistently emphasizes that neither threads, nor message queues, nor any known constructions are part of the model of actors, which led to a variety of ideas and ways of implementation.
There are three directions:
You read the articles of the 70s: the future belongs to multiprocessor systems, artificial intelligence; 80s: the future belongs to multiprocessor systems, large databases, logical data processing, now: the future belongs to processors with a large number of cores, big data, cloud computing, and intelligent data analysis. It is not difficult to draw analogies between the current situation and the forecasts of 40 years ago. All this reminds an example from trainings on motivation about a donkey and a carrot. We take a step to get closer to the cherished goal, and the goal is moving away from us as far as we are closer to it, but it is she who forces us to develop and move forward.
When I first came across an actor model, and that was relatively recent. I had a question - why I didn’t find out about her before. Specially looked at books by Tanenbaum, Gregory Andrews, Patterns of integration of corporate applications , etc. - all of them give a lot of space to messaging concepts, but none of them say a word about the model of actors and Hewitt. But when you read Hewitt or Agha, a lot of time is spent criticizing the traditional model of computing. It seems that the actors simply ignore. The same thing happens in programming: in the world of imperative programming, practically nothing is known about functional - as if it does not exist, at least it was until recently, and in the world of functional programming, imperative is criticized. Can anyone have any thoughts, why did this happen?
If this article is of interest, I plan to write a series of articles, for example:
If there are wishes on the articles, I will be glad to hear.
This article is based on one of my reports.
Pro actors story begins at the fifth minute.
What is the model of actors?
Are actors a set of practices, a development methodology, an architectural pattern, a marketing move?
In my university course, like many, the concept of computability was defined through the Turing and Post machines. The machine has a state - a set of values of all the cells of the tape. The calculation process is a sequence of machine steps, each of which changes its state. Each step of the machine is the execution of one atomic indivisible action (operation). Further I will call it the traditional model of computing.
This interpretation of calculations leads to the concept of global time, when one and only one atomic operation can be performed at the same time. This property is essentially used to prove the properties of various synchronization primitives in the case of multi-threaded programming on single-processor machines, for example, in the book Gregory R. Andrews Basics of multi-threaded, parallel and distributed programming .
')
For multiprocessor machines or distributed systems, the requirement of global time is generally unacceptable. Therefore, it is necessary to generalize the concept of computability to the case of parallel computations. One of such generalizations is the model of actors.
How did it all begin?
The appearance of this model in the distant 70s was due to the strong belief that the next generation machines will be multiprocessing, and the programs will have artificial intelligence. In 1973, Carl Hewitt , Peter Bishop and Richard Steiger published an article: A Universal Modular Formalism For Artificial Intelligent . In this article, they introduced the concept of actor and explained that many classes of applications are a special case of the model of actors. By the way, this year was the 40th anniversary!
Actor is a universal abstraction of a computational entity, which, in response to a received message
- Can send a finite number of messages to other actors,
- Create a finite number of actors
- Select a behavior to receive the next message.
What are the fundamentally different actors from the traditional model of computing?
The difference between them is the same as between a telephone and sending a message by mail. In the first case (this is a calculation based on global time), if several people try to call one phone number, then they begin to compete for access to the common shared resource - the addressee. Office PBXs, multichannel phones, software for call-centers - all this (a la synchronization primitives) is needed in order to ensure efficient processing of incoming calls. In the case of mailing, the sender of the letter (actor) simply sends the letter to the addressee without any delay due to the need to coordinate their actions with other senders. But! However, we do not know when the recipient will read our letter.
Who develops the theory of actors?
The two biggest specialists are Carl Hewitt and his student Gul A. Agha . Hewitt mainly deals with the rigorous rationale that other approaches to computability are a special case of the actor model, and Agha is a different application for distributed systems.
Key results
Each of the results in itself is a topic for a separate large article, so I will only give a summary and a link to the source.
Events in the model of actors form a partially ordered set. The axiomatics of this set called Ordering Laws was described by Carl Hewitt and Henry Baker in the article Actors and Continous Functionals (1977). There are a lot of axioms, and their point is to prove that the model of actors is suitable for use in practice, for example, that at any given time the number of messages addressed to one recipient is, of course.
In 1985, Gul A. Agha, under the leadership of Hewitt, defended his thesis on Actors: A Model Of Concurrent Computations in Distributed Systems . In the dissertation, Agha describes the syntax of a minimal programming language that supports actors, as well as a set of typical problems and methods for solving them (Chapter 4).
Another important contribution to practical approaches to the implementation of the model of actors can be considered the article Phillip Haller and Martin Odersky Event-Based Programming without Inversion Control . It proposed a new approach for the development of actor systems, which was used in Scala. Its essence is that the resulting parallel program for writing is very similar to "regular sequential" programming.
The same path, for example, was chosen for developing C #. Here are the actors on C # 5:
static async Task SavePage(string file, string a) { using (var stream = File.AppendText(file)) { var html = await new WebClient().DownloadStringTaskAsync(a); await stream.WriteAsync(html); } } Here, the await keyword implies an asynchronous call to the corresponding method and a return to the calculations when the answer is received.
In 2011, Gul A. Aga and Karmani summed up many years of experience in the implementation of actor systems, describing the most common method of implementation. They called it Fog Cutter . True, Hewitt has repeatedly criticized such an architecture, for example, here and here. The essence of criticism is that this is just one of the possible implementations of a particular case of a model that does not fully implement the entire actor model.
Indeed, in the dissertation of the Foundations of Actor Semantics William Duglas Clinger (student of Carl Hewitt) shows that the actor model has unlimited non-determinism, while the Turing machine is boundedly non-deterministic. From this, he and Carl Hewitt conclude that there are algorithms that can be implemented in the actor model, but cannot be implemented on a Turing machine. Therefore, any attempt to implement the actor model on "ordinary" computers that implement Turing computability will result in the realization of only a special case of the actor model.
A spoon of tar ...
In 1988, Robert Kowalski , the creator of the Prologue, advanced the thesis that “calculations can be grouped according to logical conclusions”. This is true for sequential calculations and for some parallel models. But in 1988, Hewitt and Agha published the article Guarded Horn clause? in which it was shown that for the actor model this is incorrect in the following sense: the current state of the program can deductively not follow from the previous one. What this means in practice: debugging a program based on the model of actors is not as effective as in the case of sequential programs.
Why functional languages?
Why do functional languages arise wherever it comes to parallel programming? To answer this question, consider a small example in C ++:
int j = 0; for(int i =0; ; ++i) { ++j; } Since this piece of code does not contain I / O operations, in order to allow another thread to execute its code on the same processor core, it is necessary to wait until the operating system's thread scheduler forcibly switches threads. This can occur either when a call to a system function occurs in another thread, or upon a timer event. By default, the timer event triggers 1 time in 15.6 ms , it explains why you should not reduce this time to 1 ms. It turns out that the imperative style allows you to write a "greedy" program that tries to single-handedly use all the processor resources, and we have limited resources to influence it.
Rewrite this program through tail recursion.
void cycle(int i, int& j) { ++j; cycle(i+1, j); } Forgive me admirers of functional programming languages for such a free interpretation, but my goal is only to demonstrate the idea.
The loop iteration is replaced by a function call. Suppose that the compiler embeds a code at the call point of each function to count the time spent executing the current thread and switching to another thread if necessary. Now we have the opportunity to switch from one stream to another within nanoseconds. The same idea allows to implement lightweight streams, for example, as in Erlang.
For these properties, functional languages are convenient to use where parallelism and real-time response is needed.
Rehabilitation of imperative languages
If you need a very fast response, then functional languages are beyond competition, but what if during the processing of a request we have to contact the database, and the response time from it is about 50-100 ms, or we have to perform many calculations, that is, to perform many function calls . The overhead costs associated with calculating the execution time and switching threads for each call make themselves felt, and imperative languages are more efficient in this case. To verify this, just look at the site benchmarksgame.alioth.debian.org . The site offers to measure the performance of programs written in different languages, comparing the solutions of the same problem. Here are some examples of comparisons: reverse-complement , mandelbrot , regex-dna , pidigits .
At once I will make a reservation, firstly, these are only tests - it is not necessary to take them very seriously. On the other hand, anyone who is dissatisfied with the position of their favorite programming language can offer their own solution and change the alignment of forces. Secondly, I cited only those links where imperative languages benefit from a clear advantage, because my goal is only to illustrate the idea expressed a few paragraphs earlier about the overhead costs associated with the organization of parallelism.
Another interesting observation is the implementation of the model of actors in imperative languages, as a rule, in tests above the functional Erlang. Again, make a reservation, everyone knows that Erlang is good not in calculations, namely, where an instant response is needed, but this only once again confirms the idea of overhead costs.
I will cite one metaphor: there are runners for long distances - marathon runners, and there are - for short - sprinters. Some are required endurance at low average speed (relative to the sprinters), and the second - the maximum performance in a very short time (relative to the marathon). Alas, it’s just physiologically impossible to show equally high results at sprint and marathon distances, simply because completely different properties are required from the muscles. These runners are distinguished even by their figures: marathon runners are dry and sinewy, and sprinters are athletic and muscular.
5th generation of computer
Another confirmation that the parallel programming is not so simple, is a project to create a 5th generation of computers.
In the 1980s, an attempt was made in Japan to create computers of the 5th generation . The project was initiated again by the belief that the future is parallel computing, large databases and logical processing of large databases.
It was spent 500 million dollars in the prices of the 80s. The project lasted 10 years and ended in complete failure! Parallel programs did not give significant performance advantages over single-threaded ones. And for decades, Intel has taken the palm with its single-threaded processors. And only when the processor manufacturers came up against the technological limitations of increasing the clock frequencies, the idea of parallelism began to gain popularity again.
Approaches to the implementation of the model of actors
The performance issues discussed above, as well as the fact that Hewitt insistently emphasizes that neither threads, nor message queues, nor any known constructions are part of the model of actors, which led to a variety of ideas and ways of implementation.
There are three directions:
- New programming language. This niche is occupied by functional languages. A prime example: Erlang.
- Extensions to existing languages. For example, Scala, C #. It uses the idea of Odersky and Haller, which allows you to write parallel programs in the "usual style".
- Libraries for an existing language.
In conclusion, two observations
Belief in parallel computing.
You read the articles of the 70s: the future belongs to multiprocessor systems, artificial intelligence; 80s: the future belongs to multiprocessor systems, large databases, logical data processing, now: the future belongs to processors with a large number of cores, big data, cloud computing, and intelligent data analysis. It is not difficult to draw analogies between the current situation and the forecasts of 40 years ago. All this reminds an example from trainings on motivation about a donkey and a carrot. We take a step to get closer to the cherished goal, and the goal is moving away from us as far as we are closer to it, but it is she who forces us to develop and move forward.
Ignoring on the one hand and criticism on the other.
When I first came across an actor model, and that was relatively recent. I had a question - why I didn’t find out about her before. Specially looked at books by Tanenbaum, Gregory Andrews, Patterns of integration of corporate applications , etc. - all of them give a lot of space to messaging concepts, but none of them say a word about the model of actors and Hewitt. But when you read Hewitt or Agha, a lot of time is spent criticizing the traditional model of computing. It seems that the actors simply ignore. The same thing happens in programming: in the world of imperative programming, practically nothing is known about functional - as if it does not exist, at least it was until recently, and in the world of functional programming, imperative is criticized. Can anyone have any thoughts, why did this happen?
What's next?
If this article is of interest, I plan to write a series of articles, for example:
- Laws of ordering actors by Actors and Continous Functionals .
- An overview of the ideas set forth in the Actors: A Model Of Concurrent Computations in Distributed Systems dissertation. Gul A. Agha.
- Pros and cons of the Odersky Event-Based Programming approach with Inversion Control .
- Returning to the spoon, having degraded ... - a couple of my own ideas, already implemented and tested in practice, how to improve the reliability and resiliency of systems implemented according to the model of actors.
If there are wishes on the articles, I will be glad to hear.
PS
This article is based on one of my reports.
Pro actors story begins at the fifth minute.
Source: https://habr.com/ru/post/206300/
All Articles