Ticket #165 (closed defect: fixed)
Deadlock when collective updates produce large patches
| Reported by: | Bernhard Haumacher (haui at haumacher dot de) | Owned by: | |
|---|---|---|---|
| Priority: | normal | Milestone: | 2.0 |
| Component: | uka.karo | Version: | 1.08a |
| Severity: | normal | Keywords: | |
| Cc: |
Description
Collective update of replicated objects was built with the assumption that each participating thread has to create its patch before being able to apply patches from other participants, because its own patch would otherwise include the early applied patches from the other parties. An additional assumption was that this strategy of patch creation before patch application would maximize concurrency. The first assumption is void, but the second one probably holds for replicated objects that use partial replication (ticket:171). The drawback of the "patch creation before application" approach is that the created patches must be buffered, because there are no consumers. All recipients are currently creating their own patches. The first implementation relied on the buffering of the underlying network layer. But this is limited to "small" patches. Once the network layer decides to block because of missing consumers, the collective update operation gets stuck in a deadlock.
Evaluation
The assumption that patches must be created, before other patches can be applied is void, because a patch is always applied to the original object and the corresponding backup copy. Therefore, after a patch has been applied to an already modified object, this patch will not be included in a patch that is created thereafter for the same object. The only restriction is that a patch can not be applied while a patch is created concurrently. This would corrupt the identifier assignments for objects.
Evaluation
Creating and applying patches on all replicas in a unique order (patch on replica with rank 0 is created/applied first, all other patches follow in rank order) has an additional benefit. The consistency of the replicated object after the collective update does not depend on correct partitioning of the replicated state by the application. Changes made to a replicated object have priorities: Changes on replicas with lower rank have priority over changes on replicas with higher rank.
Evaluation
Creating and applying patches on all replicas in a unique order may have negative impact on performance, if partial replication (ticket:171) is used. Here, replicas may wait for the application of a patch before creating their own patch. Unfortunately the awaited patch may be very small or empty at all, but its creation may take a non-negligible amount of time, because the same patch is a large one for other replicas.
Evaluation
Deadlock freeness and replica consistency for now are more valuable than optimal performance.
Solution
Patches during collective updates are now created and applied in global unique order. Patches for the same replica are applied all by the thread that performs the collective update. To accomplish this, an additional command type for remote invocations has been added to KaRMI. Besides application calls, service calls, and DGC operations, there is now also a so called collective operation. Such a collective operation is never executed by a KaRMI server thread, but delivered to a replicated object that is awaiting the collective operation. The thread that performs the collective operation on the local replica now has control over all connections belonging to the same collective operation.
See also
fixed since 1.08a.
