Learning from Concurrent, Parallel, and Distributed Systems Design

The Multiple Dimensions of Parallel Development

Multiple projects, multiple variants, multiple products, multiple teams, multiple sites, multiple customer/install bases, … multi-everything! Why does it all have to be so complicated! Each "multi"-something introduces a new dimension of complexity and scale for software development. The more "multi's" we have, the more diverse and complex the task of managing, organizing, integrating, coordinating and tracking all of the work.

Agile development methods tend to focus on simplicity and keeping things simple. When it comes to process, they also believe that it’s usually better to start small and scale-up by adding incrementally instead of starting with a large all inclusive menu and trying to pare down. As a result, most agile methods don’t have too many explicit practices to handle the cases of multiple projects, multiple variants, multiple products, multiple teams, multiple sites, and multiple customer/install bases. Instead the preference is to first try to find ways to eliminate these scenarios before trying to find practices to handle them.

This is probably sound advice as many of us are often too quick to jump to a solution before asking if the problem is one that really should be solved rather than avoided. Still, for many of us, it is nonetheless the case that these scenarios are business realities that aren’t going to go away anytime soon. So we nevertheless must seek solutions for these problems.

Agile methods and the agile community sprang from software patterns and the patterns community. So patterns are often a good first place to look for finding such solutions. However, the existing body of patterns literature devoted to CM is substantially smaller than for software design patterns. When we cant find what we’re looking for in the CM patterns literature, we may need to look elsewhere.

Core Concepts for Concurrency
If we look at the world of concurrent/parallel and distributed systems design, there are many common concepts and solutions that may also apply to the domain of parallel development. We just need to comprehend them, and how to map them from their “native” domain into our own, so we can see if they are applicable to us!

The literature on concurrent/parallel and distributed computing is fraught with technical jargon about processors, processes, and threads (among other things). Here is an oversimplified primer of some basic concurrency concepts:

• A process is a task for a processor to execute. It includes the logical flow of operations to execute, and an area in memory to store the results of computations. Processes may be heavyweight or lightweight; Lightweight processes are called threads.
• A heavyweight process has its own separate flow of control/execution, and its own storage area (address space).
• A lightweight process (or thread) has its own separate flow of control but executes in a shared address space with other threads

With that in mind, we can now describe concurrent processing, parallel processing, distributed processing, and multi-threading.

• Concurrent processing amounts to doing more than one thing (executing more than one process) at the same time with the same processor.
• Throw in another processor, and we have parallel processing: two processors executing at the same time to perform separate (but possibly related) tasks
• Put them on different machines in a network, and we have distributed processing
• Multi-threading (a.k.a. multi-threaded processing) is literally multi-tasking! It is when multiple threads are active at the same time for a single process.

For a better explanation of these and other concurrency concepts, I heartily recommend chapter 5 of 

Patterns of Enterprise Application Architecture

This explicitly uses examples from the area of source-code version control "because it's relatively easy to understand as well as familiar. After all, if you aren't familiar with source code control systems, you really shouldn't be developing enterprise applications."

Mapping to the Parallel Development Domain
How does it all translate into parallel development? I would suggest the following is one valid translation (and there are probably others):

• A process is like a development task (or set of related tasks), and a place to capture the evolving contents of artifacts that were created/updated as a result of the work done.
• A heavyweight process is like a project for a particular release/variant of a product or component. It can also correspond to a subproject for a significant feature.
• A lightweight process (thread) corresponds to a change-task to develop all or part of a particular fix, feature or enhancement.
• A storage area (address space) corresponds to either a workspace in which files may be modified and temporary versions created or a version-space, in which versions may be created (e.g., a version repository, or a branch or codeline).
• Concurrent processing corresponds to simultaneous update of a file, component, or codeline
• Parallel processing corresponds to working on multiple versions (e.g., releases, variants) of a product or component at the same time (often called multi-project development)
• Distributed processing corresponds to working on the same project across multiple networked sites at the same time (often called multi-sited development).
• Multi-threading is like having multiple change-tasks active at the same either using the same codeline, or within the same workspace.

Big Deal! So What Can I Do With That?

This means the field of concurrent, parallel and distributed systems is ripe for pattern mining. By studying existing patterns and solutions in that field, I can identify possible candidate patterns and solutions in the other. The trick is to always keep in mind what the corresponding problem and solution means in the new context, and if it translates into something valid or well-formed that still makes sense and is still practical. Of course remembering that people can behave and respond quite differently than source code.

With that in mind, let's take a look at a sampling of related patterns in this field. I chose a number of sources that are already documented in pattern form, and for which substantial material is available both online and in book form. By taking a quick tour of these patterns, we can make a quick initial guess at the potential applicability of the pattern to parallel development. I won't pretend that these initial guesses are completely accurate, nor definitive. And I'm very much interested in hearing others' ideas of how these (and other) patterns do or do not "translate" into our CM-related context. 

If we are right, then in many cases these translations will correspond to some existing tried and true CM patterns for parallel development. In other cases, they may correspond to new or uncommon solutions - and we need to question their applicability, feasibility, or practicality unless we know more about their successfully recurring use on real world projects.

Fowler's Patterns of Enterprise Application Architecture
Since we already mentioned this book, let's start by looking through some of its concurrency-related patterns. 

Data Transfer Object 

Collects and carries data between processes in bulk to reduce the number of inter-process procedure calls. This might correspond to a kind of patch-set or update-packet for remote update of a repository from a networked client at a different site.

Optimistic Offline Lock 

“Prevents conflicts between concurrent business transactions by detecting a conflict and rolling back the transaction." This seems similar to the part of a two-phased atomic commit operation allows either all of the changes to be committed to a codeline, or none of the changes to be committed.

Pessimistic Offline Lock 

Prevents concurrent transactions altogether by allowing only transaction at a time to access data. This seems like classic file-locking to prevent concurrent checkouts of the same file, or like full-codeline Locking to prevent any other changes from being committed to the codeline at the same time (even if they are accessing completely different sets of files).

Coarse Grained Lock 

Allows locking of a group of related objects together with a single lock. Like Remote Façade, this pattern also seems related to fine-grained artifact management. It could also correspond to locking all the files in an associated directory or component with a single (possibly scripted) operation.

Implicit Lock 

Enforces locking policies/protocols using custom implementations that automatically perform the necessary checking and acquiring/releasing of locks in accordance with their protocol. In parallel development, we do this every time we write a script or program to automate tasks like workspace update and/or task-level commit as part of a two-phased codeline commit.

There are other candidate patterns in this book, and even more in its companion book Enterprise Integration Patterns which may be applicable to parallel development. I encourage readers to take a look and submit their feedback to the appropriate CMCrossroads.com forum and/or the scm-patterns YahooGroup!

Paul McKenney's "Selecting Locking Designs For Parallel Programs"

This work is available online at http://www.rdrop.com/users/paulmck/ and describes approximately ten locking design patterns. First it discusses the various factors that force or toward or away from a particular style of locking solution. It discusses factors like: speedup, contention, overhead, read-to-write ratio, economics, and solution complexity. I think we can all appreciate how the majority of those issues relate to parallel development. Next the paper describes the various locking design patterns, including the following: http://www.refactoring.com/catalog/ ).

File Splitting 

Is a common type of extraction refactoring pattern that takes a high-checkout-contention source file and splits it up into multiple files. This not only reduces checkout-contention, it also reduces the likelihood of merging and merge conflicts, and possibly also the amount of recompilation when rebuilding.

File Fusing is a common type of consolidation refactoring pattern where two (or more) files have code that so frequently must all be modified together that is makes sense to consolidate the related sections of code the same module/class in a single source file that already exists.

Doug Schmidt's TAO/ACE Patterns
Doug Schmidt and colleagues have published a significant collection of network computing design patterns for concurrent, parallel and distributed systems. The patterns are used extensively in the public domain ACE and TAO C++ and Java frameworks (see http://www.cs.wustl.edu/~schmidt/patterns-ace.html ). I won’t delve into descriptions of the patterns here; I’ll just briefly describe some possible translations into the domain of parallel development:

Ouch! My Brain Hurts!
We already covered a lot of material and we just careened through at a blindingly rapid pace. And for all that effort, we didn’t even sound very certain of some of the “domain mappings” we attempted. Not only that, we only mapped them to patterns/practices we already knew, and not to anything new. So not only did we just overwhelm you with new information, we didn’t discover anything new in the process! Or did we?

First off, we hopefully gave you a better grasp of how some basic concepts of concurrency and distribution translate into parallel development concepts. We also had a taste of what some common concurrency problems are, where to look to see how they are addressed in programming systems, and to find out more about the intricacies of the issues (forces) involved and how to go about resolving them.

A more in depth look at the literature would give us an understanding of terms like: safety (or correctness), liveness, deadlock, synchronization and asynchronous communication, mutual exclusion, semaphores, monitors, guards, resource contention, starvation and sharing, etc., and (more importantly) how these translate into everyday issues in parallel development regarding stability, consistency, productivity, coordination, communication, isolation/insulation of risk, encapsulating and minimizing change impact and variation. Understanding these classic problems and the forces that drive them from the programming domain gives us some more formal conceptual mechanisms for systematically reasoning about parallel development problems, devising solution alternatives, and evaluating the corresponding trade-offs.

Of course we’ve also presented a large amount of fodder for readers to “mine” the existing problem space for new parallel development pattern candidates and a few forums in which to discuss and refine them. However, not everyone has the time or patience to do all that legwork and would rather see others consolidate and present it for them.

A few of us already attempted this with the existing patterns literature several years back and the result was the pattern collections.. 

So please look at those if you wish to see cohesive sets of CM patterns that address parallel development issues. I’m hoping however that this article piqued your curiosity enough to motivate you to take a look for yourself at what’s out there (especially some of the more recent works) and begin your own study to learn and discuss (and eventually disseminate) the results of your investigations. 

References

1] Configuration Management Models in Commercial Environments; by Peter H. Feiler; SEI Technical Report CMU/SEI-91-TR-7, March 1991

2] Codeline Merging and Locking: Continuous Updates and Two-Phased Commits, by Brad Appleton, Steve Konieczka and Steve Berczuk; CM Crossroads Journal, November 2003 (Vol. 2, No. 11)

3] Enterprise Integration Patterns; by Gregor Hohpe et. al.; Addison-Wesley, 2003 (also see http://www.enterpriseintegrationpatterns.com )

4] "Selecting Locking Designs for Parallel Programs", by Paul McKenney in Pattern Languages of Program Design 2, ch. 31, pp.501-531; Addison-Wesley, 1995 (see http://www.rdrop.com/users/paulmck/ )

5] Core J2EE Patterns: Best Practices and Design Strategies (2nd ed.); by Deepak Alur, et.al.; Prentice-Hall, 2003 (also see http://java.sun.com/blueprints/corej2eepatterns/ )

6] Refactoring: Improving the Design of Existing Code; by Martin Fowler et.al.; Addison-Wesley, 1999 (see also http://www.refactoring.com/ )

7] Pattern-Oriented Software Architecture Volume 2: Patterns for Concurrent and Networked Objects; by Douglas Schmidt, Michael Stal, Hans Rohnert and Frank Buschmann; John Wiley & Sons, 2000 (also see http://www.cs.wustl.edu/~schmidt/patterns-ace.html and http://www.cs.wustl.edu/~schmidt/ACE.html and http://www.cs.wustl.edu/~schmidt/POSA/ )

8] Streamed Lines: Branching Patterns for Parallel Software Development; by Brad Appleton et. al.; Proceedings of the 5th Annual Conference on Pattern Languages of Program Design, Allerton Park, IL (PloP’98)

9] Concurrent Programming in Java: Design Principles and Patterns (2nd ed.), by Doug Lea; Addison-Wesley, 1999 (also see http://gee.cs.oswego.edu/dl/cpj/ )

JavaSpaces Principles, Patterns, and Practice; by Eric Freeman et.al; Addison-Wesley, 1999 (also see http://java.sun.com/docs/books/jini/javaspaces/index.html)

10] Patterns for Parallel Programming; by By Timothy Mattson, Beverly Sanders, Berna Massingill; Addison-Wesley, 2004 http://www.awprofessional.com/title/0321228111

11] Architectural Patterns for Parallel Programming, papers and Ph.D research by Jorge Ortega-Arjona. See http://www.cs.ucl.ac.uk/staff/J.Ortega-Arjona/