# Requirement

Many users voice the requirement to sort history events which happen inside a process instance. Such Events are
- Start / End Activity Instance 
- Create / Update / Delete Variable
- ...

# Constraints

## Timestamps don't work
The straight forward approach is to sort these events according to their timestamp. Unfortunately this does not work in general:
- Millisecond precision is not accurate enough. Nanosecond precision is required. Nanosecond support is a bit shaky across the board (databases, operating systems...),
- on a single machine the clock may change due to network synch at runtime
- in a cluster events happening in a single process instance may be generated on different nodes => system clock synchronization in a cluster is generally not accurate down to nanoseconds

## UUIDs are not sortable, in general
The UUID generator used by the process engine does not produce sortable IDs, mostly due to the fact that they are (among other aspects) time based which means that they are subject to the same limitations as the timesamp approach. In detail:
- On a single Machine:
-- The UUIDs have a random component which is different each time the generator is instantiated. This leads to IDs not being comparable if the engine is restarted.
-- The system clock may change at runtime.
- In a cluster: UUIDs generated on different cluster nodes cannot be compared among each other since the ids are partly based on a time component which is again subject to the cluster clock synchronization problem (see above).

## Global ordering comes at a cost
Another idea is to produce a global ordering sequence for all events inside a given process instance. Or put differently, there could be a counter which is incremented whenever an event happens in a process instance. Problem:
- This constrains intra process instance concurrency: concurrent transactions inside the same process instance need to synchronize their updates to the counter. (Keep in mind that synchronization is done in the database using the Optimistic Model).

# Idea: Partial Ordering of Events

Entities can maintain a local sequence counter. Whenever something happens inside those entities, these counters can be incremented.
As a result we obtain a *partial ordering* of all events which happened inside a process instance.

## Examples:
- Sort activity instances created by the same execution: Execution maintains a local sequence counter. Whenever an activity instance is created by this execution, the counter is incremented and the value is stored in the history event.
- Sort all updates to a variable: Variable instance maintains local sequence counter. Whenever a variable is updated or deleted, the value is incremented and stored in the corresponding event

## Limitations:

It would be a partial ordering. Examples of things which would not be "comparable":
- Events related to Activity Instances of concurrent activities
- Events related to different variables

## Thoughts / Problems:

- Problem: Loops: Constructs which create a hierarchy inside the execution tree (concurrency, scoping) inside a loop: how do we ensure that the activity instances created in different executions of the loop can be sorted. Ie: all activity instances created in the first execution of the loop are strictly smaller than all activity instances from any subsequent executions of a loop
-- Idea: when an entity is created, it "inherits" the sequence counter value from it's parent scope. When synchronizing: the counter of the parent is incremented to max(current value, value of synchronized child executions)  + 1
--- Also consider this with variables.

- Relation to revisions used for optimistic locking: The process engine already maintains a revision in most entities. Whenever a transaction changes the state of the entity, the revision is incremented. We could consider using this for storing the local sequence number. In that case, a transaction would not increment it by +1 but a larger value. Problems:
-- Sometimes we use this for synchronization only: parallel join increments REV of parent execution without an actual event happening. => 
-- The value of the REV is not exposed via public API. Good. With one exception where it "leaked". Bad: org.camunda.bpm.engine.history.HistoricVariableUpdate.getRevision() If we change the behavior, we change the behavior of that API method. See also: #CAM-2366