I like the Erlang model and appreciate its impressive results in its domain so I have been thinking about how it would work for other problems like the computational patterns. Modules of an application where several code paths are executed at the same time can be split into to groups.
You have those applications in which the concurrency is a part of the problem specification. Two common examples of these are web servers and switching systems where there are multiple concurrent users. Another example is GUI event loops where the events are naturally concurrent. A fourth example is web browsers where the many tabs naturally operate concurrent. In these systems the simultaneous execution are often referred to as concurrency. Furthermore, introducing simultaneous computation/actual concurrency into these systems often does not make them that much more difficult to understand, and sometimes can even make them easier to understand. Just look at web development where developers write code on a daily basis that execute concurrently without giving it a second thought. In these systems the introduction of concurrency can give many benefits such as performance, scalability, reliability, stability, security, modularity or even maintainability and simplicity. The key point is that concurrency is a natural part of the problem specification and does not need to be uncovered.
Then there are those problems where concurrency is not a part of the problem specification, but where there is still concurrency in the domain that can be exposed and used to enhance some quality attribute (As I have explained in an earlier blog, I prefer this term to non-functional requirement). The qualify attributes in question are often performance and scalability, but can also be reliability, stability and security. In these systems the simultaneous execution is usually refer to as parallelism. Examples are solutions to the thirteen dwarfs/motifs/computational patterns where parallelism is usually exploited for performance and scalability or Google Chrome where they will spawn of processes, independent of the tab processes, to render certain risky parts of HTML code in order to provide increased security. Since there is no natural concurrency in the problem specification of these problems we have to find ways to restructure the problem to expose it. This is hard and usually leads to units of parallel execution that are closely coupled and that need to communicate often and in non-trivial ways.
Erlang and "Concurrency Oriented Programming" focuses on the first set of problems where the problems are inherently concurrent and programmers are therefore encouraged to map the concurrency in the solution 1:1 with the concurrency of the problem (people in the world or transactions in a switch). Some of the challenges are then to provide a system where processes are cheap and to provide separation between the different entities so that problems in one does not spread. These problems are nicely solved by Erlang through the use of structured protocol-driven message passing and green processes.
The second problem area is harder to solve and it is this area that the OPL effort focuses on the most. Erlang could probably be useful in solving some of these problems, but for problems like the computational patterns I have more reservations. Setting aside, for a moment, the fact that these are problems in which performance is usually the goal, which raises questions about the efficiency of a high-level language like Erlang especially for supercomputing, I do not think the model of Erlang is the ideal fit. The programming model of Erlang is one where independent processes work independently and cooperate by explicit message passing. Admittedly, many of the models that we use in supercomputing today like MPI and Charm++, share these characteristics, but these are often seen as complicated to use for programmers.
As I mentioned above Armstrong argues for mapping the concurrency of our problem 1:1 with the concurrency of the world. I agree with this, which leads me to the conclusion that it would be beneficial if we could use a sequential programming model for the problems that are, or at least we think of as, sequential. However, running them sequentially is not an option. We want to simulate tomorrows weather in hours and not in days so in the absence of increased sequential speed we must parallelize the computation. However, a "mostly" sequential programming model can still be parallelized given enough information to the compiler through parallel loops, etc. These conserve most of the sequential reasoning, but gives us parallel execution. Like we can choose to map concurrent problems to one or a few processors through time sharing we can map sequential programs to several processors in parallel. One example of such a programming model is OpenMP, which is popular for shared-memory systems but not very suitable for distributed systems mostly because it is shared-memory. However, this is an active area of research and one can envision sequential programming models that expose primitives that lets the programmer specify data locality giving the compiler enough information to distribute the computations satisfactorily.
Thursday, October 22, 2009
Making reliable distributed systems in the presence of software errors - Chapter 4
Chapter 4 of Joe Armstrong's thesis discusses programming techniques that are commonly used in Erlang. These techniques have different goals; some are for reliability and others are aimed at simplicity and modularity. He starts by making the argument that since concurrent programming is perceived as harder than sequential programming we should split the concurrent parts from the sequential parts by making the concurrent parts frameworks into which we can plug in sequential code. Furthermore, the parallel sections should be written by expert programmers and the sequential parts by less experienced programmers.
Through example he shows how this can be achieved by creating a server module that accepts requests from any number of clients and for each request executes a sequential function. This function is supplied to the server on startup which means the function is independent of the server. In this example the server module handles all the concurrency by spawning processes and receiving messages and the sequential function it is armed with handles the actual work. These two are thus separate and can be developed separately. In addition one server can be used with several different functions.
Later this example is expanded with fault tolerance. Fault tolerance here means that it can handle faults and this is done by catching exceptions from the supplied function, and then notify the client that it could not complete the operation. The fault tolerance is here that the server doesn't need to go down, but can continue operating in its previous state. Note also that in the Erlang model one would likely have a supervisor looking out for the server, so if the server contains an error which means that an error occurs that it can not handle it can safely die, letting someone else handle the error. In this case that would be the supervisor which would likely respond by creating a new server to replace the old one. This is the core of the reliability model of Erlang. Handle what you can locally, but if you encounter errors (defined as an abnormality you do not know how to fix) then just die; someone else will fix it. It also has the great property that the model can handle HW errors the same as SW errors, given that the supervisor runs on a different system, as the runtime will ensure "death messages" are delivered to the supervisor. I must say having worked on a C system that had high reliability requirements because it had to run in embedded devices I really appreciate this simple error model. In C one does not even have exceptions which means that functions often contain more error handling code than actual application code. This makes it hard to find the actual code in all the error checks and error propagation.
Sharing of resources in Erlang is different from shared memory programming. Instead of using locks and semaphores one creates a server that control access. This is to me a simpler model and an analogy would be that instead of having a door with a in-use sign to the room with the shared resource, and then trust everyone to respect the sign, one has a servant that will give you what you need through a window in the door. Of course this analogy doesn't quite hold with monitors as everyone would lock the door after them, but you would still have to be sure every path into the room has a door with the same lock, which is no easy task, as well as dealing with deadlocks.
Finally, Armstrong talks about intentional programming which I believe strongly in. Could should make its intention obvious and if this means making a lot of functions then so be it.
Ben Britton asks whether we agree that concurrent code can't be written in a side-effect free manner. One the face of it I would disagree pointing to systems such as Haskel, but I believe Armstrong is here distinguishing between parallel code and concurrent code, with concurrent code being code where individual entities modeling the real world cooperate to solve a problem. In such system you would need to have central resource sharing and communication locations with responsibilities such as managing dictionaries and controlling physical devices. These would have side effects by design. If one is purely interested in solving a set of expressions then this is something else, which would draw great benefits from being side-effect free. Furthermore, Ben asks whether the abstractions described are only possible in Erlang, to which I would say definitely no. However, Erlang provide a language, runtime and philosophy that not only provides the tools to express these abstractions in a clean manner, but also invites it.
Through example he shows how this can be achieved by creating a server module that accepts requests from any number of clients and for each request executes a sequential function. This function is supplied to the server on startup which means the function is independent of the server. In this example the server module handles all the concurrency by spawning processes and receiving messages and the sequential function it is armed with handles the actual work. These two are thus separate and can be developed separately. In addition one server can be used with several different functions.
Later this example is expanded with fault tolerance. Fault tolerance here means that it can handle faults and this is done by catching exceptions from the supplied function, and then notify the client that it could not complete the operation. The fault tolerance is here that the server doesn't need to go down, but can continue operating in its previous state. Note also that in the Erlang model one would likely have a supervisor looking out for the server, so if the server contains an error which means that an error occurs that it can not handle it can safely die, letting someone else handle the error. In this case that would be the supervisor which would likely respond by creating a new server to replace the old one. This is the core of the reliability model of Erlang. Handle what you can locally, but if you encounter errors (defined as an abnormality you do not know how to fix) then just die; someone else will fix it. It also has the great property that the model can handle HW errors the same as SW errors, given that the supervisor runs on a different system, as the runtime will ensure "death messages" are delivered to the supervisor. I must say having worked on a C system that had high reliability requirements because it had to run in embedded devices I really appreciate this simple error model. In C one does not even have exceptions which means that functions often contain more error handling code than actual application code. This makes it hard to find the actual code in all the error checks and error propagation.
Sharing of resources in Erlang is different from shared memory programming. Instead of using locks and semaphores one creates a server that control access. This is to me a simpler model and an analogy would be that instead of having a door with a in-use sign to the room with the shared resource, and then trust everyone to respect the sign, one has a servant that will give you what you need through a window in the door. Of course this analogy doesn't quite hold with monitors as everyone would lock the door after them, but you would still have to be sure every path into the room has a door with the same lock, which is no easy task, as well as dealing with deadlocks.
Finally, Armstrong talks about intentional programming which I believe strongly in. Could should make its intention obvious and if this means making a lot of functions then so be it.
Ben Britton asks whether we agree that concurrent code can't be written in a side-effect free manner. One the face of it I would disagree pointing to systems such as Haskel, but I believe Armstrong is here distinguishing between parallel code and concurrent code, with concurrent code being code where individual entities modeling the real world cooperate to solve a problem. In such system you would need to have central resource sharing and communication locations with responsibilities such as managing dictionaries and controlling physical devices. These would have side effects by design. If one is purely interested in solving a set of expressions then this is something else, which would draw great benefits from being side-effect free. Furthermore, Ben asks whether the abstractions described are only possible in Erlang, to which I would say definitely no. However, Erlang provide a language, runtime and philosophy that not only provides the tools to express these abstractions in a clean manner, but also invites it.
Tuesday, October 20, 2009
Map Reduce and Event-Based Parallel Patterns
Map_Reduce
This pattern described he very topical map-reduce algorithm. Map-reduce has been around for a long time and I believe it is supported natively in some functional programming languages (OCaml?) under the guise of map-fold. The pattern does a decent job of describing the component that I need (the map and reduce functions) as well as some aspects of implementing a map-reduce framework, but I think it could do with a coding example using a simple toy map-reduce library in which a simple operation such as for example scaling down images and then merge them could be implemented.
Also, the implementation section seemed to assume a master-worker paradigm underneath ("the software architecture is logically based on master-worker"), but although this is certainly one reasonable way to implement it there is no reason why one shouldn't do statical load balancing or work stealing instead in certain situations (I don't consider work stealing a sub-category of master worker as OPL does). They do later suggest a round robin (cyclic) schedule for some tasks, but I still think they put too much focus on master-worker which is described elsewhere and really an implementation detail of this pattern.
I also wonder whether filter/reduce should be discussed as a variant of this pattern. It is certainly used out there, but maybe it is a different pattern.
Finally, I their precondition that the reduce function must be associative. Perhaps this should be changed to "should for optimal performance be" as one can certainly get great speedups from the map phase even if the reduce step has to be performed sequentially.
Event-based, Implicit Invocation
This pattern discusses the architecture of event-based systems. One very common example of this is GUI framework where events that are mainly triggered by the user are passed on to event handlers that subscribe to that event type. This pattern was contained more details than the other OPL patterns we have read and for that reason I thought it was one of the better ones. However, at one point they state that "load balancing is significantly simpler with a centralized medium". Does not a centralized medium make the load balancing problem go away entirely for this pattern?
Later on in the example section they discussed GUI event-based systems. These systems have a centralized manager and this is identified as the biggest impediment to scalability. However, I would claim that the biggest impediment is not the centralized manager, but the fact that the event handling is done as blocking functions. If any of these functions take some time to complete they will block everything. This can also be hard to figure out as if one for example use file IO then everything may work well, but then the GUI suddenly starts to lock when one start accessing files through a networked file system. I thought such issues, seeing as they are so common with this very important case of event-based systems, deserve to be mentioned more clearly.
This pattern described he very topical map-reduce algorithm. Map-reduce has been around for a long time and I believe it is supported natively in some functional programming languages (OCaml?) under the guise of map-fold. The pattern does a decent job of describing the component that I need (the map and reduce functions) as well as some aspects of implementing a map-reduce framework, but I think it could do with a coding example using a simple toy map-reduce library in which a simple operation such as for example scaling down images and then merge them could be implemented.
Also, the implementation section seemed to assume a master-worker paradigm underneath ("the software architecture is logically based on master-worker"), but although this is certainly one reasonable way to implement it there is no reason why one shouldn't do statical load balancing or work stealing instead in certain situations (I don't consider work stealing a sub-category of master worker as OPL does). They do later suggest a round robin (cyclic) schedule for some tasks, but I still think they put too much focus on master-worker which is described elsewhere and really an implementation detail of this pattern.
I also wonder whether filter/reduce should be discussed as a variant of this pattern. It is certainly used out there, but maybe it is a different pattern.
Finally, I their precondition that the reduce function must be associative. Perhaps this should be changed to "should for optimal performance be" as one can certainly get great speedups from the map phase even if the reduce step has to be performed sequentially.
Event-based, Implicit Invocation
This pattern discusses the architecture of event-based systems. One very common example of this is GUI framework where events that are mainly triggered by the user are passed on to event handlers that subscribe to that event type. This pattern was contained more details than the other OPL patterns we have read and for that reason I thought it was one of the better ones. However, at one point they state that "load balancing is significantly simpler with a centralized medium". Does not a centralized medium make the load balancing problem go away entirely for this pattern?
Later on in the example section they discussed GUI event-based systems. These systems have a centralized manager and this is identified as the biggest impediment to scalability. However, I would claim that the biggest impediment is not the centralized manager, but the fact that the event handling is done as blocking functions. If any of these functions take some time to complete they will block everything. This can also be hard to figure out as if one for example use file IO then everything may work well, but then the GUI suddenly starts to lock when one start accessing files through a networked file system. I thought such issues, seeing as they are so common with this very important case of event-based systems, deserve to be mentioned more clearly.
Making reliable distributed systems in the presence of software errors - Chapter 2
Chapter 2 of Joe Armstrong's doctoral thesis on "" discusses the architectural model of a system that can achieve this goal, presenting Erlang as one such system. Processes are here the central concept in the system and in the Erlang language. The chapter argues that the only way to have true reliability in the presence of bugs is to encapsulate each module in its own process so that errors can be contained and the process killed if an error is detected. As such modules should not attempt to correct errors, but instead kill themselves, leaving recovery to someone else (usually to the runtime environment). This is a strong property that simplifies the recovery model as one can perform recovery from code that has not had any errors yet. It also frees the programmer from programming defensively as he/she can rely on any other process either succeeding at what they were supposed to do or crashing. As such one does not have to deal with extensive error checking and error handling code for each call to another module.
The concept of a Concurrency Oriented Programming Language (COPL) is introduced in which programs should model the world like one does in Object Oriented programming. However, unlike Object Oriented programming, it recognizes that the world is concurrent and programmers are encouraged to map the concurrency of the world one-to-one with the concurrency of their programs. To achieve this it is made a first class citizen of the language and the runtime environment utilizes green threads to make concurrency cheap, which gives the programmer the freedom to model all the concurrency of the problem domain.
Processes communicate through asynchronous message passing. This means that no state can be shared and that if another process needs some data then that data must be copied to that process by sending a message. This enforces the use of the Separable parallel pattern which tends to lead to more scalable programs as one need not serialize access to the data through mutual exclusion. This property, in addition to the fact that the messages are asynchronous, also means that the potential for deadlocks is (almost?) completely removed. Finally, programs that copy data (such as one has to do in message passing APIs such as MPI) have greater data locality and avoid false sharing problematics, which are important for performance.
In Erlang concurrency is not intended for performance. The main goals of programming concurrently is reliability (through the process abstraction), scalability, security and even modularity.
The concept of a Concurrency Oriented Programming Language (COPL) is introduced in which programs should model the world like one does in Object Oriented programming. However, unlike Object Oriented programming, it recognizes that the world is concurrent and programmers are encouraged to map the concurrency of the world one-to-one with the concurrency of their programs. To achieve this it is made a first class citizen of the language and the runtime environment utilizes green threads to make concurrency cheap, which gives the programmer the freedom to model all the concurrency of the problem domain.
Processes communicate through asynchronous message passing. This means that no state can be shared and that if another process needs some data then that data must be copied to that process by sending a message. This enforces the use of the Separable parallel pattern which tends to lead to more scalable programs as one need not serialize access to the data through mutual exclusion. This property, in addition to the fact that the messages are asynchronous, also means that the potential for deadlocks is (almost?) completely removed. Finally, programs that copy data (such as one has to do in message passing APIs such as MPI) have greater data locality and avoid false sharing problematics, which are important for performance.
In Erlang concurrency is not intended for performance. The main goals of programming concurrently is reliability (through the process abstraction), scalability, security and even modularity.
Sunday, October 18, 2009
Rereading the classics
Last week I was a bit overloaded so this blog post comes a bit late, but better late than never. The last chapter of beautiful architecture titled "Rereading the classics" was a great read for me. The author were for the most part discussing object orientation and presented the programming language Smalltalk as an example of a system that had taken this to the extreme and made everything an object. I have never seen Smalltalk code before so it made for an interesting case study and I can definitely see how Smalltalk's legacy have shaped subsequent systems like Java and C#.
After having left the previous chapter, with its arguments for extending the type system through inheritance to solve most problems, with an uneasy feeling I was glad to see this chapter's careful use of it. I have indeed read Meyer's great "Effective C++" and have seen the penguins' failed attempts to fly before so I strongly agree that inheritance means is-a and is not a mechanism to compose code like the horrible COMPOSITE_PART of page 334. We learned to favor composition from our teacher this semester and the rest of the gang of four and there is no going back.
Smalltalk has a lot to teach us about Object Orientation and I find it very interesting, but not surprising, that much of the community that gave us design patterns and the guidelines for developing Object-Oriented systems that we use today came from the world of Smalltalk. I've mentioned this before, but things like this make me really wonder how much it is we that shape our tools and how much it is our tools that shape us. I certainly agree that language facilitate thought and surely this must mean that pure languages then facilitate pure thought.
The author closes with a too me surprising turnaround. After having talked up Smalltalk's strength and OO purity he makes the case for more pragmatic programming languages like C and C++ and even throws in a great quote by Stroustrup (although of course a Dane will prefer Kierkegaard!). He gives us some examples from the world of physical architecture where some of the most celebrated architectural masterpieces of the last century, like the Fallingwater house and the Villa Savoye, turned out to be completely unlivable for its inhabitants. Form must follow function and architecture must be made to facilitate the people who will live in it. It is like Alexander's villages in the Swiss alps where the naturally evolved patterns the buildings follow allows them to be beautiful while at the same time being functional for their inhabitants down to the last detail.
So is it for languages too and although I doubt Smalltalk developers will characterize it as unlivable neither has it had the same role on center stage as C++, Java and C#. However it, like beautiful functional programming languages with their purity and expressiveness, and T/16 and Erlang with their ubiquitous focus on reliability through replication it has served to inspire us and has influenced our other programming languages as well as the way that we use them. In some ways I believe the ideas that came out of the Smalltalk community have proved more powerful than any single programming language. At the risk of causing controversy I would like to draw an analogy to the socialistic democracies of Scandinavia and indeed to some degree most of present-day Europe. The ideas of Communism were very pure, but inherently flawed at their core. However, instead of implementing the anti-thesis of Capitalism, which is also very pure and although much preferable has its own problems, they landed at a hegelian synthesis of the two ideas, pragmatically borrowing what they perceived as the strengths of both with a market economy and a strong safety net. I do not endorse this one way or the other, but it is interesting how the radical pure ideas blaze for a while, but are then subsumed into more pragmatic approaches and becomes the status que that everyone takes for granted. I too, like Stroustrup, am inspired by the rationalists, but when everything is said and done prefer to live in a world based on pragmatic empiricism.
After having left the previous chapter, with its arguments for extending the type system through inheritance to solve most problems, with an uneasy feeling I was glad to see this chapter's careful use of it. I have indeed read Meyer's great "Effective C++" and have seen the penguins' failed attempts to fly before so I strongly agree that inheritance means is-a and is not a mechanism to compose code like the horrible COMPOSITE_PART of page 334. We learned to favor composition from our teacher this semester and the rest of the gang of four and there is no going back.
Smalltalk has a lot to teach us about Object Orientation and I find it very interesting, but not surprising, that much of the community that gave us design patterns and the guidelines for developing Object-Oriented systems that we use today came from the world of Smalltalk. I've mentioned this before, but things like this make me really wonder how much it is we that shape our tools and how much it is our tools that shape us. I certainly agree that language facilitate thought and surely this must mean that pure languages then facilitate pure thought.
The author closes with a too me surprising turnaround. After having talked up Smalltalk's strength and OO purity he makes the case for more pragmatic programming languages like C and C++ and even throws in a great quote by Stroustrup (although of course a Dane will prefer Kierkegaard!). He gives us some examples from the world of physical architecture where some of the most celebrated architectural masterpieces of the last century, like the Fallingwater house and the Villa Savoye, turned out to be completely unlivable for its inhabitants. Form must follow function and architecture must be made to facilitate the people who will live in it. It is like Alexander's villages in the Swiss alps where the naturally evolved patterns the buildings follow allows them to be beautiful while at the same time being functional for their inhabitants down to the last detail.
So is it for languages too and although I doubt Smalltalk developers will characterize it as unlivable neither has it had the same role on center stage as C++, Java and C#. However it, like beautiful functional programming languages with their purity and expressiveness, and T/16 and Erlang with their ubiquitous focus on reliability through replication it has served to inspire us and has influenced our other programming languages as well as the way that we use them. In some ways I believe the ideas that came out of the Smalltalk community have proved more powerful than any single programming language. At the risk of causing controversy I would like to draw an analogy to the socialistic democracies of Scandinavia and indeed to some degree most of present-day Europe. The ideas of Communism were very pure, but inherently flawed at their core. However, instead of implementing the anti-thesis of Capitalism, which is also very pure and although much preferable has its own problems, they landed at a hegelian synthesis of the two ideas, pragmatically borrowing what they perceived as the strengths of both with a market economy and a strong safety net. I do not endorse this one way or the other, but it is interesting how the radical pure ideas blaze for a while, but are then subsumed into more pragmatic approaches and becomes the status que that everyone takes for granted. I too, like Stroustrup, am inspired by the rationalists, but when everything is said and done prefer to live in a world based on pragmatic empiricism.
Subscribe to:
Posts (Atom)