Overview
The easiest way to demonstrate the linked list protocol in action is by means of examples. Diagrams below contain multiple step-by-step examples of how versioning tree is built and navigated in various scenarios. It shows how the tree grows with each instance of user interacting with the entity data.
We start with one simple example, then explain how to read the versioning tree and then offer 7 step-by-step visual examples:
- Example 1. Entity versioning
- Example 2. Service transaction versioning
- Example 3. Re-linking due to correct the register (correct transaction scenario)
- Example 4. Re-linking due to correct the register (insert transaction scenario)
- Example 5. Versioning due to merges
- Example 6. Data entry versioning
- Example 7. Concurrent data entry versioning
Simple example of versioning
The below example demonstrations a simple scenario of a business service and an entity level versioning.
Step 1: Registered user John started a new registration application. He submitted it for review, the service was returned due to the issues with the company name.
Step 2: John edited the application by changing the company name, he re-submitted the application and it got approved. Verne created 2 versions of this registration application: one before John changed the company name, and one after he made the amendments. The second version of his registration application represents the first and the current version of the entity itself.
Step 3: Some time later Mary started an application to update the company postal address, she submitted the application and it got auto-approved. Verne created the second version of the entity, which became its current one, whereas the first entity version became previous (historical).
Result: Verne created three documents (service transactions) in the data base representing different versions of the entity 123 and business services that relate to it. Each document contains the full snapshot of the entity data effective at a certain point in time.
Verne will retrieve appropriate record when users request to see entity details as of the date in the past, e.g. if a user requests an extract for this entity as of 15 June 2019, then Verne will use entity version #1, if a user requests an extract for this entity as of 20 October 2019, then Verne will use entity version #2.
Verne will compare different versions to highlight the changes introduce by the application, e.g. when John resubmitted the application with updated company name, Verne highlighted the name change to the reviewer of the corresponding task so that they don’t need to review the rest of the application form again, also when Mary’s change got approved Verne created a “Change of address” filing, which highlights the exact changes made by Mary.
How to read the versioning tree?
Verne manages versions of data by means of linked list protocol. There are several key attributes in the service transaction heading that enable Verne versioning:
The following 6 attributes in the service transaction document serve as the linked list pointers:
- Previous version – points to the service transaction that holds previous approved version of the entity data. Previous version transaction will be superseded by this one should it be activated (if it hasn’t already).
- Next version – points to the service transaction that holds the next approved version of the entity data. Next version transaction has been activated and therefore superseded this one.
- Previous sibling – points to the service transaction that holds previous version of the service instance. Previous sibling transaction will be superseded by this one should it be committed (if it hasn’t already).
- Next sibling – points to the service transaction that holds the next committed version of the service instance data. Next sibling transaction has been committed and therefore superseded this one.
- Previous merge – points to the service transaction that has been the target of the successful merge and was superseded by this one as a result of the merge.
- Next merge – points to the service transaction that has been created as the result of the successful merge that this transaction was the target of.
The following 3 attributes in the service transaction document serve as unique keys that are used to navigate the tree and identify documents that belong to the same entity and same service instance:
- ID – unique identifier of each service transaction document
- Service identifier – unique identifier of a business service instance, it is generated by Verne and does not change throughout the life of a specific service instance. All service transactions with the same service identifier constitute versioning history of the corresponding service
- Identifier – unique identifier of each entity, it is generated by Verne and does not change throughout its life. All service transactions with the same identifier constitute versioning tree of the corresponding entity
The following 4 attributes in the service transaction document that help determine the status of the document (see life-cycle section for more details):
- Status – reflects the business service status effective at the point in time when service transaction was last saved
- Committed status – stored as a Committed date, that reflects transaction committed status. If the date is empty, then the transaction is considered to be not committed and it represents an unfinished data entry session, otherwise if date is populated then transaction is committed
- Ghost status – stored as two attributes Ghost flag and Ghost reason, they determine if transaction that is not yet committed is still alive (i.e. has potential to be committed) or if it is already a ghost (i.e. dead), in the latter case the reason for its death is recorded
All of the above attributes enable Verne to build and navigate the versioning tree for a given entity.
What is the current version?
The current version of an entity is derived by using the Next version and Status attributes. The algorithm is very simple:
- Next version is NULL
- Status is ‘Activated’
The current version of a service instance is derived by using the Next sibling and Next merge attributes. The algorithm is very simple:
- Next sibling is NULL
- Next merge is NULL
- Committed date is populated
There is a visual protocol with these examples. Each box represents one service transaction document with the 6 pointers (the 3 previous pointers on the left of the box and the 3 next pointers on the right of the box). The header of the box contains unique keys and statuses.
Colour protocol
- purple colour represents changes in this diagram as compared to the diagram of the previous step.
Colour of a tree branch represents the versioning stage:
- dark blue branch is the so called tree “trunk”, it contains registered entity versions, that are all approved service instances, in fact only those versions of the service instances that are current (final)
- light blue branches contain service instances (and their versions) that have not reached approval (either in-progress or already unsuccessful)
- grey branches represent unfinished data entry sessions that have not been committed yet
Versioning tree examples
Example 1. Entity versioning
Step 1. A service transaction (1) reflecting a company registration business service (S1) is created, submitted and accepted. The status is ‘Activated’ to reflect that the service transaction has approved entity data on the register. This service transaction (1) now represents the first set of entity data on the register. It has no pointers so far, as it is the only transaction representing this entity.
Step 2. Then a service transaction (2) reflecting a company maintenance business service (S2) is created, submitted and accepted. Its previous version is stamped to point to the service transaction (1) that has the previous version of entity data. The next version of service transaction (1) is now stamped to point to the service transaction (2) that has the next version of entity data. The link between the two versions is established both ways.
Example 2. Service transaction versioning
Step 1. A service transaction (1) reflecting a company registration business service (S1) is created, submitted and accepted.
Step 2. Then a service transaction (2) reflecting a company maintenance business service (S2) is created, submitted and returned for revision. Its previous version is stamped to point to the service transaction (1) that has the previous version of entity data.
Step 3. Then a service transaction (3) reflecting another company maintenance business service (S3) is created and saved for later. Its previous version is stamped to also point to the service transaction (1).
Note, the next version attribute of service transaction (1) is empty as there has been no activated services after it yet. Both (S2) and (S3) are competing to take the same vacant slot as the next version of the service transaction (1)
Step 4. Data in the service (S2) has been edited and service re-submitted. As a result:
- A service transaction (4) is created to represent the second version of this service.
- Its previous sibling is stamped to point to the service transaction (2) that has the previous version of the service data.
- The next sibling of service transaction (2) is now stamped to point to the service transaction (4) that has the next version of the service data.
Note, service transaction (4) also has previous version pointer set to service transaction (1) as it holds the current snapshot of entity data, should service (S2) be activated, then service transaction (4) will become the next entity version. Transactions (2) and (4) are called siblings as they belong to the same service instance.
Step 5. Data in service (S3) has been edited and saved again, that created a new service transaction (5) with the similar pointing arrangements as described above for service transaction (4).
Step 6. Service (S3) has been deleted by the presenter, so its status was set to Canceled, this versioning tree branch is now dead and will not grow any longer as no more changes are possible on the services that reached their final unsuccessful state.
Step 7. Service (S2) has been approved, so it became activated. The next version of the service transaction (1) is now stamped to point to the service transaction (4) that has the next approved version of entity data. The tree branch of service S2 can possibly grow further with more siblings acquired as a result of correct the register being applied (see examples below).
Example 3. Re-linking due to correct the register (correct transaction scenario)
Step 1. Registration service (S1) has been activated
Step 2. Maintenance service (S2) was started and saved for later, then it was edited and then accepted.
Step 3. After that maintenance service (S3) has bee applied.
Step 4. Service (S2) has been corrected via correct transaction service. Correct the register used service transaction (3) as a baseline and replaced it with a new service transaction (5) with corrections applied.
This resulted into the following links being established:
- service transaction (5) previous version and next version pointing to the same transactions as the corrected transaction (3)
- service transaction (3) got next sibling stamped to point to the new transaction (5) as it replaces it
- service transaction (5) got previous sibling stamped to point to the corrected transaction (3) as it replaced it
The following transactions have been re-linked:
- service transaction (3) next version pointer is set to be empty
- service transaction (1) got its next version re-linked to point the new service transaction (5), it used to point to the transaction (3) before the correction
- service transaction (4) got its previous version re-linked to point the new service transaction (5), it used to point to the transaction (3) before the correction
Example 4. Re-linking due to correct the register (insert transaction scenario)
Step 1. Registration service (S1) has been activated
Step 2. Maintenance services (S2) has been activated
Step 3. Maintenance services (S3) has been activated
Step 4. A new service instance (S4) was inserted to represented a missed filing as of the point in time in the past – between services (S1) and (S2). Correct the register used service transaction (1) as a baseline and created a new service transaction (4) to represent the missed service.
This resulted into the following links being established:
- service transaction (4) previous version is stamped to point to service transaction (1) as it represents the previous entity version
- service transaction (4) next version is stamped to point to service transaction (2) as it represents the next entity version
The following transactions have been re-linked:
- service transaction (1) got its next version re-linked to point the new service transaction (4), it used to point to the transaction (2) before the correction
- service transaction (2) got its previous version re-linked to point the new service transaction (4), it used to point to the transaction (1) before the correction
Example 5. Versioning due to merges
Step 1. A service transaction (1) reflecting a company registration business service (S1) is created, submitted and accepted.
Step 2. Then a service transaction (2) reflecting a company maintenance business service (S2) is created, submitted and returned for revision. Its previous version is stamped to point to the service transaction (1) that has the previous version of entity data.
Step 3. Then business service (S2) was edited by the user and saved again. Service transaction (3) represents the most recent version of the service (S2) and is a sibling of the service transaction (2).
Step 4. Another service (S3) has been approved and activated. Next version of service transaction (1) has been stamped to point to service transaction (4)
Step 5. Since service (S2) is still in-progress it needs to be refreshed with changes introduced by the service (S3). As a result of the successful merge the flowing tree grown has happened:
- a new service transaction (5) has been created as a result of service transaction (3) being a target of merging changes from service transaction (4)
- its previous merge pointer is stamped to point to service transaction (3) as it was the target of the merge
- its previous sibling pointer is stamped to point to service transaction (2) as it holds the previous version of service instance as far as user input goes
- its previous version pointer is stamped to point to service transaction (4) as it now hold the current version of entity data
- service transaction (3) acquired a next merge as it was superseded by the new service transaction (5)
Example 6. Data entry versioning
Step 1. A service transaction (1) reflecting a company registration business service (S1) is created, submitted and accepted.
Step 2. Then a service transaction (2) reflecting a company maintenance business service (S2) is created, submitted and returned for revision. Its previous version is stamped to point to the service transaction (1) that has the previous version of entity data.
Step 3. Then a service transaction (3) reflecting another company maintenance business service (S3) is created and saved for later. Its previous version is stamped to also point to the service transaction (1).
Step 4. User X started editing data in service (S2) and is still working on it (has not saved or discarded the changes yet). This created a new service transaction (4) that points to service transaction (1) as its previous version and service transaction (2) as its previous sibling.
Step 5. Service (S3) has been approved and activated. Next version of service transaction (1) has been stamped to point to service transaction (3)
Step 6. Since service (S2) is still in-progress it needs to be refreshed with changes introduced by the service (S3). As a result of the successful merge the flowing tree grown has happened:
- a new service transaction (5) has been created as a result of service transaction (2) being a target of merging changes from service transaction (3)
- its previous merge and previous sibling pointers are stamped to point to service transaction (2) as it is the target of the merge and the current version of the service instance at the same time
- its previous version pointer is stamped to point to service transaction (3) as it now hold the current version of entity data
- service transaction (2) acquired a next sibling and a next merge as it was superseded by the new service transaction (5)
Step 7. Service transaction (4) is still not committed and its previous sibling transaction has moved on and acquired another next sibling due to merge. This means that service transaction (4) needs to be refreshed with changes introduced in the service transaction (5). As a result of the successful merge the flowing tree grown has happened:
- a new service transaction (6) has been created as a result of service transaction (4) being a target of merging changes from service transaction (5)
- its previous merge pointer is stamped to point to service transaction (4) as it was the target of the merge
- its previous sibling pointer is stamped to point to service transaction (5) as it holds the current version of the service instance data
- its previous version pointer is stamped to point to service transaction (3) as it holds the current version of the entity data
- service transaction (4) acquired a next merge pointer as it was superseded by the new service transaction (6)
Example 7. Concurrent data entry versioning
Step 1. A service transaction (1) reflecting a company registration business service (S1) is created, submitted and accepted.
Step 2. Then a service transaction (2) reflecting a company maintenance business service (S2) is created, submitted and returned for revision. Its previous version is stamped to point to the service transaction (1) that has the previous version of entity data.
Step 3. User X started editing data in service (S2) and is still working on it (has not saved or discarded the changes yet). This created a new service transaction (3) that points to service transaction (1) as its previous version and service transaction (2) as its previous sibling.
Step 4. While User X is still working on their version of changes, User Y decided to also edit service (S2) so that it can be re-submitted. This action created a new service transaction (4) that is based on its previous sibling the service transaction (2). We now have two concurrent data entry sessions competing to take the same vacant slot in as the next sibling of service transaction (2)
Step 5. User Y finished editing the service data and saved the changes. Service transaction (4) Committed Date has been populated and the next sibling of service transaction (2) has been stamped to point to service transaction (4).
Step 6. Service transaction (3) is still not committed and its previous sibling transaction (2) has moved on and acquired another next sibling due to editing. This means that service transaction (3) needs to be refreshed with changes introduced in the service transaction (4). As a result of the successful merge the flowing tree grown has happened:
- a new service transaction (5) has been created
- its previous merge pointer is stamped to point to service transaction (3) as it was the target of the merge
- its previous sibling pointer is stamped to point to service transaction (4) as it holds the current version of the service instance data
- its previous version pointer remains to be service transaction (1) as it still holds the current version of the entity data
- service transaction (3) acquired a next merge pointer as it was superseded by the new service transaction (5)
Step 7. User Y re-submitted service (S2) and its status was set to ‘Review’
Step 8. Service transaction (5) is still not committed and its previous sibling transaction (4) has moved on and changed its status. This means that service transaction (5) can no longer be committed, its Ghost flag is set to Yes with the Ghost reason set to Obsolete.
