Skip to end of metadata
Go to start of metadata

Weak Consistency

We will follow the weak consistency model. That means we are not transactional, we do not guarantee that the system will be consistent all the time. Strong consistency is unfortunately an unrealistic requirement for most integration systems and this applies even stronger to provisioning systems (see explanation in the #Motivation section).

Our consistency model is similar to the LDAP model. We do not have transactions; operations on a single object are usually atomic and there may be delays in propagating changes to the target system (external resource).

We will try to apply operations with the best consistency we can get and we will try to do most operations in an atomic fashion. The mechanisms will be designed to minimize the risk of inconsistencies. However, inconsistencies may happen and the code must be able to behave reasonably in such a case.

Mechanisms

There are two mechanisms for improving data consistency: the relative change model and the optimistic locking model.

Relative change model

Changes to the objects will always be presented in a relative fashion. Any change will only define what was changed, it will not specify the data which was left unchanged. The relative changes are easy to merge and in vast majority of cases provide acceptable consistency without the need for locking.

We assume that all of the data in our system will be represented as (XML) objects. The objects have properties which we consider to be the smallest piece of information that we work with. (See Data Model for more details). Objects can be created and deleted, property values can be added, removed or replaced. But we do not support changing parts of a property value. E.g. new value bar for property foo can be added. But to change the value bar to baz it is needed to remove value bar and add value baz. We do not support replacing of a single character in the value, changing XML attributes or sub-elements in the property values, etc.

There are three operations that implement changes:

  • Add object operations will add new objects. This means adding a new complete object with an identifier and property values. This operation should fail if the object already exists.
  • Modify object will change existing objects by modifying some of their property values. It has three sub-operations. All these sub-operations work on a specific property of an object.
    • Add property values sub-operations will add new values to the existing values of a property. They will not change any of the existing values.
    • Remove property values sub-operations will remove specified values from the existing values of a property. It will not change other existing values.
    • Replace property values sub-operations will remove all of the existing values of a property and replace them with a new set of values. This operation should be used with care (see below).
  • Remove object operations will remove objects.

TODO: XML examples
TODO: Only properties can be changed

All these operations should be implemented as atomic. That means the operation must either succeed and make the changes durable or must fail without applying any changes. There must not be any intermediary state after the operation finishes and the intermediary state must not be visible to other operations even if the operation is still in progress. However, not all data storage mechanisms may support atomicity of such operations. It is the responsibility of the deployment engineer to choose the correct datastore for the requirements of a specific IDM deployment.

Relative changes are sufficient for most use-cases in the identity management field. For example adding a new group foo to a user is a single add property value operation on property groups with value of foo. Such operation will natively merge with other similar operations. E.g. if another administrator is adding group bar to the same user, the two add property value operations will have the same result no matter in what order they are executed.

Some storage mechanisms may be able to implement the operations atomically using native means. Other storage mechanisms may require short transactions or may not be able to provide atomicity at all. Caution is advised in case of choosing appropriate data store for the deployment.

TODO: Atomicity and consistency during provisioning. this is still TBD

Alternative approach is an absolute change model: read all values of properties, modify them and set all new values of the property. Such approach is used by some existing IDM systems and it is inherently problematic. IDM business logic often contains long-running approval processes. If there is such change pending in the system (e.g. awaiting approval), not other change to the property is possible. This approach would create a bottleneck in the system, especially for frequently-used properties such as roles. The problem of absolute change model is that the order of operations on a single property is important, therefore the property (or the entire object) must be locked to provide reasonable degree of consistency. Absolute change model is possible even in our solution by using the replace property value operation. Therefore we will try to avoid absolute change model whenever possible.

Relative change model is not a panacea. It fails in a case of multiple conflicting changes. For example, it will fail if one operation adds the value foo and another one removes the value foo from the same property. In such a case the order of operations is important. Similar situation can be observed if two or more operations add value to a single-valued property. The client invoking the operations must be aware of the limits of relative change model and handle conflicts and errors accordingly. However, the consistency level provided by automatic merging of operations is usually sufficient. In the rare case that a stronger consistency is required, the optimistic locking mechanism (described below) should be used.

TODO: complete operations based on set algebra may be added later
TODO: examples
TODO: best practice

Optimistic locking

TODO

Integration

TODO: Explain how operations are transformed to repository and provisioning operations.

Motivation

TODO: why the absolute changes are bad?
why we cannot use transactions?

TODO

The order of operations in the "diff algebra" sometimes matters. Therefore the results of (A patched-by delta1) patched-by delta2 may be different than (A patched-by delta2) patched-by delta1. But I argue that is does not really matter in most cases, that the usual case will end up as expected and the unusual case is indeterminable anyway. This is kind of conjecture rather than a theory, so any feedback is mostly appreciated (as usual).

Let's describe that using examples of usual IDM cases:

Example 1: Roles

Change 1: Adding role "foorole" to "foobaruser". Let's assume that this is a modification of property "role", adding a new value of "foorole" (real case is a bit more complex)
Change 2: Adding role "barrole" to "foobaruser". This would be modification of property "role", adding a new value of "barrole".

If these two changes are applied in any order, the result is still the same (assuming that "role" property is unordered, which is one important reasons to have unordered multivalued properties). This is a very common case in IDM.

Example 2: Changing department

Change 1: Changing users organizational unit to "underground". Let's assume this is modification of property "ou" to replace all existing values with value "underground".
Change 2: Changing users organizational unit to "board". Modification of property "ou" to replace all existing values with value "board".

This clearly depends on the order that the operations will be executed. The operation that will be applied last will "win" and persist, the other will be "lost". Yet, this is exactly what is expected. If the two changes happen in a very different times, that's exactly what is expected. (note that "very different times" may actually mean just seconds away). If the operations are executed almost at the same moment, it is usually a failure of business logic and has to be manually fixed anyway. Does it really make sense to promote and demote an employee at the same time?

As a rule of thumb, the multivalued properties should be modified using "add" and "delete" modification types. Single-valued properties should be modified using "replace".

In case we need stronger consistency we may still use optimistic locking. Yet, I just cannot imagine any case in IDM where that would be needed.

If we need even more "consistency" we may explore Operational Transformation (OP) method. But I think that is an overkill, at least for now.

Guaranteed message ordering is tricky. That assumes we have a single reliable source of ordering. This is usually an (ACID) database, but such database will happily shut itself down once it looses quorum, therefore sacrificing availability. Do we want that? And how do we assure ordering of changes coming from external sources (synchronization). If we sacrifice availability, we can order them according to the time they arrive to IDM. But, it is the "real" order? Could not the messages be reordered before they reach IDM? If that is possible, then the "strongly consistent" ordering may not make any sense.

I think it is simpler to just admit that we cannot guarantee fine-grain message ordering and that the timestamp is the best mechanism we have. I also speculated above that a conflicting messages very close to each other (time-wise) is a problem anyway. Fine-grain message reordering will not make it worse.

I would rather say: anybody generating a diff should pretty much know what he's diffing. And I think that is a fair assumption to make. Just think about where in midPoint we really need diff:

  • GUI. This is displaying the properties, therefore it has to know what the rich XML structure means and therefore know how to make a "smart" diff. One exception may be debug pages, "raw" XML is displayed here. But that is not critical for "ACID". Even if we create unnecessary change here, nothing bad happens.
  • Staging. It is working with the knowledge of the model, therefore it knows quite well what it is diffing. Also we have been thinking that it will in fact remember the changes made to non-trivial properties instead of just diffing XMLs.
  • Provisioninig: "diffing" the changes from resources that cannot detect changes themselves and always send the current absolute state (e.g. DB table). But the provisioning pretty much knows what is in the properties. And if provisioning does not know, then we just cannot hope that any other component will know it better than provisioning. So there needs to be custom logic for it anyway.

Issues that were not mentioned here:

  • Now we have kind of convention (black magic) to determine what is a property. This makes it difficult for example to write generic repository implementation or the diff code in staging. This should be improved.
  • How to detect conflicts? E.g. changes that were expected to be merged and were not merged? Can we have conditional operations? Will it be supported by resources? Probably not. Anyway, how to detect the "conflicts" and handle them manually?
  • There are still "window of risk" in some cases. E.g. "default" expression should only set new value if a value does not exist yet. This needs two operations (read and write). As resources does not support transactions, this may fail (e.g. something setting a value between read and write). Is it a problem at all? If it is, how to improve that (at least for resources that support transactions or some kind of locking)?
  • Can this model be formalized somehow?

External links

  • No labels