patternMinor
What is the fastest way to a Publish/Subscribe pattern?
Viewed 0 times
publishthewhatwayfastestsubscribepattern
Problem
I am running in a conceptual problem in my development which I previously also encountered in the Drupal CMS and was wondering what would be the best solution to circumvent the problem.
Drupal, and my own Snap Websites software, make use of a publish / subscribe pattern where one can write functions that automatically get called whenever a certain event happens. This can be shown in the following process (note that neither are using threads in those specific processes, it runs within one single main thread in one single main process--although Snap! supports backends—separate processes, I have no concerns with those at this point):
Shown here we see that process P2 emits a signal (p2 signal) and that generates functions of observers O12, followed by O22, etc. up to On2 to be called. The exact same thing happens in process P4.
In most cases that works just fine. However, once in a while, a change made by one of the observers is required by the next observer. In other words, the order O12 then O22 is important. However, if the end user has the possibility to switch the two observers around, then the process becomes O22 then O12 which breaks the proper sequence and thus something will not happen.
The Drupal awkward solution is to use a weight to sort their modules in a given order. This is an issue because that forces all observers of that module to
Drupal, and my own Snap Websites software, make use of a publish / subscribe pattern where one can write functions that automatically get called whenever a certain event happens. This can be shown in the following process (note that neither are using threads in those specific processes, it runs within one single main thread in one single main process--although Snap! supports backends—separate processes, I have no concerns with those at this point):
+----+ +----+ +----+ +----+ +----+
| P1 |--->| P2 |--->| P3 |--->| P4 |-...->| Pn |
+----+ +----+ +----+ +----+ +----+
| |
| | p4 signal +------+ +------+ +------+
| +----------->| O1/4 |--->| O2/4 |-...->| On/4 |
| +------+ +------+ +------+
|
| p2 signal +------+ +------+ +------+
+----------->| O1/2 |--->| O2/2 |-...->| On/2 |
+------+ +------+ +------+Shown here we see that process P2 emits a signal (p2 signal) and that generates functions of observers O12, followed by O22, etc. up to On2 to be called. The exact same thing happens in process P4.
In most cases that works just fine. However, once in a while, a change made by one of the observers is required by the next observer. In other words, the order O12 then O22 is important. However, if the end user has the possibility to switch the two observers around, then the process becomes O22 then O12 which breaks the proper sequence and thus something will not happen.
The Drupal awkward solution is to use a weight to sort their modules in a given order. This is an issue because that forces all observers of that module to
Solution
Since you are asking on CS.SE rather than StackOverflow, I presume you are looking for a principled look at the fundamental underlying problem and principled solutions to the general problem, from a scientific/conceptual perspective (as opposed to a "quick hack" or a engineering solution that'll work for your specific situation). So, that's what I'll try to provide.
The problem
What you are describing is an instance of the plan interference problem.
Let me summarize the problem in abstract terms. You are in the middle of delivering an event to the observers, one by one, and the code of one of the observers happens to mutate the underlying state; this mutation might cause the notifications to the other observers to happen in the wrong order, or to expose an inconsistent state to them.
For a more general description of the plan interference problem, I recommend the following papers:
-
The Problem with Threads. Edward A. Lee. IEEE Computer, May 2006. (See especially Section 4.)
-
Concurrency Among Strangers: Programming in E as Plan Coordination. Mark S. Miller, E. Dean Tribble, and Jonathan Shapiro. TGC 2005. (See especially Sections 1-4.)
Some candidate solutions
One possible solution, proposed in the first paper above, is to stop using threads with mutable shared state as your form of concurrency. Instead, look at systems like Erlang and others that are more event-based and use alternative models of concurrency.
Another possible solution, proposed in the second paper above, is to stop using threads with mutable shared state as your form of concurrency. Instead, look at systems that are inspired by actors. These systems treat invoking a method on an object $O$ as sending a message to the object $O$, and instead of using a stack discipline, they use a message queue. This ensures that messages are delivered in an order that are consistent with the causality, and avoids causing plan interference. For instance, if you're in the middle of delivering an event to a bunch of observers, and the third observer triggers a state-changing method call $c$, then these systems would queue up $c$ and not deliver/invoke it until all of the observers have been informed. This avoids unexpected violations of atomicity and avoids many kinds of plan interference bugs. See the second paper for details.
A third alternative solution is to continue using threads with mutable shared state as your form of concurrency, and just be really careful. You could make yourself aware of the common kinds of plan interference hazards, and write your code so you won't shoot yourself in the foot in this way. For instance, the state-holding object could make itself responsible for queuing up notifications about state changes, to ensure that notifications happen in a consistent order. It could also establish a contract that forbids observers from making mutations to itself (so there is no mutual recursion where a change to the state of object $x$ triggers a notification to observer $O_i$ which in turn mutates the state of object $x$ some more). You could structure your code so that the order in which observers are invoked should never matter. There are all sorts of ways you could structure your code to try to avoid these hazards from ever affecting you.
Obviously, this last approach is very challenging, because it is difficult to reason about all the things that could happen in such a system. It's easy to screw something up. But hey, concurrency is really hard to think about. If you write your code using shared-state concurrency, don't be surprised if it makes your code harder to reason about.
Plan interference can occur even in single-threaded programs, so this problem is not exclusive to multi-threading. (I mention multi-threading only because it is the most common cause of plan interference problems.) The second paper above does propose solutions to plan interference that will apply even to single-threaded programs.
The problem
What you are describing is an instance of the plan interference problem.
Let me summarize the problem in abstract terms. You are in the middle of delivering an event to the observers, one by one, and the code of one of the observers happens to mutate the underlying state; this mutation might cause the notifications to the other observers to happen in the wrong order, or to expose an inconsistent state to them.
For a more general description of the plan interference problem, I recommend the following papers:
-
The Problem with Threads. Edward A. Lee. IEEE Computer, May 2006. (See especially Section 4.)
-
Concurrency Among Strangers: Programming in E as Plan Coordination. Mark S. Miller, E. Dean Tribble, and Jonathan Shapiro. TGC 2005. (See especially Sections 1-4.)
Some candidate solutions
One possible solution, proposed in the first paper above, is to stop using threads with mutable shared state as your form of concurrency. Instead, look at systems like Erlang and others that are more event-based and use alternative models of concurrency.
Another possible solution, proposed in the second paper above, is to stop using threads with mutable shared state as your form of concurrency. Instead, look at systems that are inspired by actors. These systems treat invoking a method on an object $O$ as sending a message to the object $O$, and instead of using a stack discipline, they use a message queue. This ensures that messages are delivered in an order that are consistent with the causality, and avoids causing plan interference. For instance, if you're in the middle of delivering an event to a bunch of observers, and the third observer triggers a state-changing method call $c$, then these systems would queue up $c$ and not deliver/invoke it until all of the observers have been informed. This avoids unexpected violations of atomicity and avoids many kinds of plan interference bugs. See the second paper for details.
A third alternative solution is to continue using threads with mutable shared state as your form of concurrency, and just be really careful. You could make yourself aware of the common kinds of plan interference hazards, and write your code so you won't shoot yourself in the foot in this way. For instance, the state-holding object could make itself responsible for queuing up notifications about state changes, to ensure that notifications happen in a consistent order. It could also establish a contract that forbids observers from making mutations to itself (so there is no mutual recursion where a change to the state of object $x$ triggers a notification to observer $O_i$ which in turn mutates the state of object $x$ some more). You could structure your code so that the order in which observers are invoked should never matter. There are all sorts of ways you could structure your code to try to avoid these hazards from ever affecting you.
Obviously, this last approach is very challenging, because it is difficult to reason about all the things that could happen in such a system. It's easy to screw something up. But hey, concurrency is really hard to think about. If you write your code using shared-state concurrency, don't be surprised if it makes your code harder to reason about.
Plan interference can occur even in single-threaded programs, so this problem is not exclusive to multi-threading. (I mention multi-threading only because it is the most common cause of plan interference problems.) The second paper above does propose solutions to plan interference that will apply even to single-threaded programs.
Context
StackExchange Computer Science Q#27801, answer score: 6
Revisions (0)
No revisions yet.