In multisupplier replication updates can be applied to an entry on different suppliers concurrently ( at the same time) where concurrent means an update on one supplier is done before the update from an other supplier is received. Even conflicting or contradictory changes can happen These situations are handled by the update resolution protocol (URP). It tries to achieve two goals:
GOAL 1: After the modifications are replicated the entries are consistent on all servers in the topology GOAL 2: The final state is the same as if the modifications would have been applied on a single supplier in the order given by the CSNs associated with the modification.
This cannot be achieved for single valued attributes (SVA) in all scenarios, even in very simple scenarios. Example1: an entry has no value of a SVA, concurrently on supplier1 a value V1 is added and on supplier2 a value of V2 is added. After replication of these two mods the entry would have two values for SVA. In the single supplier model the second modification would be rejected. Example2: modrdn
So there is a need for additional rules in URP for single valued attributes, the current design implements the following rules:
RULE 1: the latest modification succeeds RULE 2. modrdn has priority over other operations.
In RULE 1 “latest” means the operation with the highest CSN, this could be different from the clients perception
The implementation of URP for single valued attributes is complex and there still are scenarios where the results are not correct and inconsistent states are encountered.
The intention of this document is to cover all potential update scenarios for single valued attributes, define the expected results and design a test suite to verify URP for single valued attributes. If possible the implementation should be simplified.
For single valued attributes there are only three states
The SVA does not exist
The SVA does exist and has one value
The attribute exists, has one value and the attribute is part of the RDN of the entry. Pending values ????
For each state we determine which potential operations are allowed an what is the resulting state
Changetype: modify
replace: SVA
-
Changetype: modify
add: SVA
SVA: value
-
changetype: modify
replace: SVA
SVA: value
-
Changetype: modrdn
newrdn: SVA=value
deleteoldrdn: 0
-
Note: for SVA deleteoldrdn: 1 makes no difference, but the current RDN could be a required attribute.
Changetype: modify
delete: SVA
-
Changetype: modify
delete: SVA
SVA: value
-
Changetype: modify
delete: SVA
-
add: SVA
SVA: newvalue
Changetype: modify
delete: SVA
SVA: oldvalue
-
add: SVA
SVA: newvalue
changetype: modify
replace: SVA
-
add: SVA
SVA: newvalue
-
Existing value gets distinguished. This is the same ldap operation as op3, but the value to be made distinguished has to be the existing value
Changetype: modrdn
newrdn: SVA=newvalue
deleteoldrdn: 1
-
changetype: modrdn
newrdn: otherattr=somevalue
deleteoldrdn: 1
-
Changetype: modrdn
newrdn: otherattr=somevalue
deleteoldrdn: 0
-
The basic operations for state changes are simple and limited, but the schema check is performed only after all sub-operations of a modify request have been applied and all kind of intermediate states can exist. Example: Assume attribute is in state S0
changetype: modify
add: SVA
SVA: value
SVA: value2
-
delete: SVA
SVA: value1
-
add: SVA
SVA: value3
-
delete: SVA
SVA: value2
-
Finally the attribute has only one value: value3, but in the intermediate states it has two values. The variety of these operations is unlimited and a hopefully sufficient set of pathological operations has to be designed for testing. The problem with these type of operations is not in concurrency, they always will finally result in basic state change, but it has to be verified that the final state of the attribute is consistent on all servers in the topology
to be defined
to be completed
The basic rules say that modrdn has precedence over modify operations and that the latest change should win. So there is a specific scenario when an attribute is no longer distinguished and a modification was rejected at the time it was distinguished.
Example: Attribute is in state S0
On supplier1 there is a state change (t0, S0->S2, v0)
On supplier2 there is a state change (t1, S0->S1, v1)
t0,t1 concurrent, t1>t0, after replication attribute is in state S2 with value v0
On supplier1 there is a state change (t2, S2->S1), this would result in v0, but v1 was applied later and v0 is no longer distinguished, so v1 could become the current value.
To handle scenarios like this the attribute keeps a value which should be applied because of Rule1, but cannot because of Rule2 as a pending value. Note: It is sufficient to identify the scenarios in the concurrent state changes which could and should lead to pending values and extend the scenarios to make the attribute undistinguished
Question: Shouldn’t there be pending deletes ? If an attribute cannot be deleted because it is distinguished, that could be done as soon as it is no longer distinguished.
DISCUSSION TOPIC: Do we need to handle pending values at all ? Assume a mod of a value to v2 and a modrdn with the present value v1 with a csn(v1) < csn(v2), the modrdn has priority and the value remains v1. Now two weeks later there is another modrdn, making an other attribute distinguished and suddenly the value changes to v2, it could be a surprise.
There are many operations which lead to state changes in a SVA, they can be applied in any combination and order and on a wide range of suppliers.
To determine the correct behaviour all combinations in a two-supplier topology are considered. If more suppliers are involved the variety increases, but in URP there will always be only the resolution of a current state with a state change received via replication.
So systematically all combinations involving two suppliers are investigated, for the test setup an extended topology with three suppliers and one consumer is used to verify consistency and expected states and values
The following table lists all the combinations of state changes in two-supplier topology, each state change has to be executed with the potential operations to achieve this state change. It is assumed that the CSN of the state change on supplier 1 is always lower than that on supplier 2. This is also the reason that the table contains the full combinations since (–>S0,–>S1) and (–>S1,–>S0) are not symmetric.
| Supplier 1 | Supplier2 | Resulting state | Resulting value | Pending value |
|---|---|---|---|---|
| –> S0 | –> S0 | S0 | - | - |
| –> S0 | –> S1(v1) | S1 | v1 | - |
| –> S0 | –> S2(v2) | S2 | v2 | - |
| –> S1(v1) | –> S0 | S0 | - | - |
| –> S1(v1) | –> S1(v2) | S1 | v2 | - |
| –> S1(v1) | –> S2(v2) | S2 | v2 | - |
| –> S2(v1) | –> S0 | S2 | v1 | Why not pending delete ?? |
| –> S2(v1) | –> S1(v2) | S2 | v1 | v2 gets pending |
| –> S2(v1) | –> S2(v2) | S2 | v2 | - |
The operations to create the state changes are different, but results should be as in table for S0
The operations to create the state changes are different, but results should be as in table for S0
Although with more than two suppliers the update resolution procedure should sequentially applied and result in the same state resolution existing bugs show that this is not the case with the current implementation. This chapter will handle all scenarios with 3 suppliers, this also allows all three different state changes applied in parallel. An extension to more than three suppliers should not be necessary. In the tests a consumer should be added to the topology, it serves as a reference where the modifications are applied in the csn order.
| Test | Supplier 1 | Supplier2 | Supplier3 | Resulting state | Resulting value | Pending value |
|---|---|---|---|---|---|---|
| 1 | –> S0 | –> S0 | –> S0 | S0 | - | - |
| 2 | –> S0 | –> S0 | –> S1(v3) | S1 | v3 | - |
| 3 | –> S0 | –> S0 | –> S2(v3) | S2 | v3 | - |
| 4 | –> S0 | –> S1(v2) | –> S0 | S0 | - | - |
| 5 | –> S0 | –> S1(v2) | –> S1(v3) | S1 | v3 | - |
| 6 | –> S0 | –> S1(v2) | –> S2(v3) | S2 | v3 | - |
| 7 | –> S0 | –> S2(v2) | –> S0 | S2 | v2 | Pend. delete? |
| 8 | –> S0 | –> S2(v2) | –> S1(v3) | S2 | v2 | v3 |
| 9 | –> S0 | –> S2(v2) | –> S2(v3) | S2 | v3 | - |
| Test | Supplier 1 | Supplier2 | Supplier3 | Resulting state | Resulting value | Pending value |
|---|---|---|---|---|---|---|
| 10 | –> S1(v1) | –> S0 | –> S0 | S0 | - | - |
| 11 | –> S1(v1) | –> S0 | –> S1(v3) | S1 | v3 | - |
| 12 | –> S1(v1) | –> S0 | –> S2(v3) | S2 | v3 | - |
| 13 | –> S1(v1) | –> S1(v2) | –> S0 | S0 | - | - |
| 14 | –> S1(v1) | –> S1(v2) | –> S1(v3) | S1 | v3 | - |
| 15 | –> S1(v1) | –> S1(v2) | –> S2(v3) | S2 | v3 | - |
| 16 | –> S1(v1) | –> S2(v2) | –> S0 | S0 | v2 | Pend. Delete? |
| 17 | –> S1(v1) | –> S2(v2) | –> S1(v3) | S0 | v2 | v3 |
| 18 | –> S1(v1) | –> S2(v2) | –> S2(v3) | S0 | v3 | - |
| Test | Supplier 1 | Supplier2 | Supplier3 | Resulting state | Resulting value | Pending value |
|---|---|---|---|---|---|---|
| 19 | –> S2(v1) | –> S0 | –> S0 | S2 | v1 | Pend. Delete? |
| 20 | –> S2(v1) | –> S0 | –> S1(v3) | S2 | v1 | v3 |
| 21 | –> S2(v1) | –> S0 | –> S2(v3) | S2 | v3 | - |
| 22 | –> S2(v1) | –> S1(v2) | –> S0 | S2 | v1 | V2 or delete? |
| 23 | –> S2(v1) | –> S1(v2) | –> S1(v3) | S2 | v1 | v3 |
| 24 | –> S2(v1) | –> S1(v2) | –> S2(v3) | S2 | v3 | - |
| 25 | –> S2(v1) | –> S2(v2) | –> S0 | S2 | v2 | Pend delete? |
| 26 | –> S2(v1) | –> S2(v2) | –> S1(v3) | S2 | v2 | v3 |
| 27 | –> S2(v1) | –> S2(v2) | –> S2(v3) | S2 | v3 | - |
Usually replication is very fast and performing updates concurrently on different Suppliers before the changes are replicated cannot be guaranteed. So common test setup is:
Check consistency of entry on all servers in the topology
Pause replication between suppliers
Apply changes to different servers
Re-enable replication
Wait for replication convergence
Check consistency and expected results
To perform the tests out lined above, a topology of three suppliers and on consumer is used. This allows to apply all the independent state changes and if replication to consumers is not disabled the consumer will perform update resolution exactly for changes applied exactly in csn order