Jump to: navigation, search

OpenDaylight Controller:MD-SAL:Architecture:DOM DataStore

The Problem Statement

There are several issues with data structures used in the current implementation of the MD-SAL data store and the data store itself

  • Data structures (defined in yang-data-api) are more like XML structures, therefore it's hard to implement an optimized datastore on top of them. Rather, YANG-defined data structures should be used in the data store. YANG-defined data structures are already being used in the MD-SAL, in the Java DTOs generated by YangTools and in other components.
  • The current MD-SAL data contracts do not provide enough capabilities to more accurately specify an application's intent and to perform optimizations to clients (for example, 'do not unnecessarily deserialize data', or 'compute only necessary change sets').
  • The current datastore implementation does not allow for atomic updates on subtrees.

To improve the reliability and performance of MD-SAL, the above issues need to be addressed.

The Current MD-SAL DOM Data Broker

The current DOM Data Broker has not been designed with an assumption of a intelligent in-memory cache with tree-like structures that would be able to track dependencies, calculate change sets and maintain the relationships between commit handlers, notification listeners and the actual data. This may lead to an inefficient implementation of the two-phase commit, where all state tracking during the is done by the Data Broker itself as follows:

  1. Calculate affected subtrees
  2. Filter commit handlers by affected subtrees
  3. Filter data change listeners by affected subtrees
  4. Capture initial state for data change listeners (one read per data change listener set)
  5. Start Request Commit of all affected commit handlers
  6. Finish Commit on all affected commit handlers
  7. Capture final state for data change listeners (one read per data change listener set)
  8. Publish Data Change events to affected data change listeners.


The state kept and maintained by the current DOM Data Broker is:

  • Mapping of subtree paths to registered commit handlers
  • Mapping of subtree paths to registered data change listeners
  • Mapping of subtree paths to registered data readers


In addition, the state keeping responsibilities of the current DOM Data Broker are:

  • Read request routing for data readers
  • Two phase commit coordination
  • Publishing Data Change Events
    • Capturing Before and After state

Asynchronous Read

Most of the MD-SAL APIs were asynchronous - one exception used to be the read*Data operation, which appeared to be immediate & fast. When additional read*Data use cases are introduced, such as lazy codec generation, remote systems providing read operations (Netconf), support for multiple readers, and clustering, this is no longer true.

The proposed change is to make the DataReader contract asynchronous as well, which allows chaining of reads and allows the caller thread to be non-blocking during the read. This will result in cleaner concurrency models.

Proposed change: https://git.opendaylight.org/gerrit/#/c/5143/2


Requirements

  • Transactions
    • Consistent data store view during the transaction:
      • An application can read back all the modifications it made to the data store.
      • An application does not see any writes from transaction started after the current transaction (isolation).

What We Need to Do

  • The yang-data-api needs to be extended to provide tree structures that are a better match to data structures defined by YANG schemas.
    • Data structures need to be closely aligned with Instance Identifiers
    • Data structures should provide support for atomic operations
  • The sal-common-api, sal-core-api and sal-binding-api APIs need to be extended to better specify user intent
  • Separate operational data store and configuration data store


Proposed Changes

The New Normalized Data Tree Model

The new normalized model for data will represent the actual concepts behind the YANG Specification. It will no longer be based on the serialization format (as defined in the YANG specification and used by sal-broker-impl 1.0).

  • NormalizedNode - Base type representing a node in a tree structure; All other node types are derived from this base type. It contains a leaf identifier and a value.
    • DataContainerNode - A node which contains multiple leafs; it does not have a direct representation in the YANG syntax.
      • ContainerNode - Node, which represents a leaf which can occur only once per parent node; it contains multiple child leaves and maps to the container statement in YANG.
      • MapEntryNode - Node which represents a leaf, which can occur multiple times; a leave is uniquely identified by the value of its key. A MapEntryNode may contain multiple child leaves. MapEntryNode maps to the instance of list in YANG.
      • ChoiceNode - Node which represents a leaf, which occurs mostly once per parent node, but possible values could have different types. Maps to choice statement. Types maps to the case statements for that choice.
      • AugmentationNode - Node which represents a leaf, which occurs mostly once per parent node.
    • LeafNode - Node which represents a leaf, which occurs mostly once per parent node. Contains simple value.
    • LeafSetEntryNode - Node which represents a leaf, which type could occurs multiple times per parent node. Maps to to the instances of leaf-list in YANG.
    • LeafSetNode - Special node, which can occur only once per parent node; its leaves are LeafSetEntryNode nodes of specified type. Maps into the leaf-list in YANG.
    • MapNode - Special node, which can occur only once per parent node; its leaves are MapEntryNode nodes.

The current model does not provide a tie-in between the InstanceIdentifier and the Data Store. This problem is addressed in this proposal by defining a relationship between path arguments in InstanceIdentifier and data tree nodes.

See OpenDaylight_Controller:MD-SAL:Design:Normalized_DOM_Model

The code for the proposed APIs is in: http://git.opendaylight.org/gerrit/5441

Impact to Existing Components

This proposal will affect the components that perform schema aware data normalization:

  • Yangtools
    • yang-data-impl - XmlDocumentUtils - a set of utilities and codecs which is used by Netconf tooling to normalize input XML into yang-data-api based on provided Schema
    • binding-generator-impl - LazyGeneratedCodecRegistry - runtime generated codec from Java DTOs to yang-data-api
  • Controller
    • sal-rest-connector RestconfContext - translates input json/xml into intermediate form, which is normalized using schema context
    • sal-* DataBroker - unification of concepts between Java DTOs and yang-data-api, well defined normalized form will improve code reusability, readability and performance of Data Broker
    • DataStore - data store implementation will benefit from a normalized data model, which will lead to more efficient implementations

These components will be modifed to use the new normalized data model (that provides more efficient APIs).

New Components

In-Memory Datastore / Cache

The contract and deployment model for the new DOM Data Broker will assume the existence of an in-memory datastore (cache), which will offload the DOM Data Broker from the following responsibilities:

  • Mapping of subtree paths to registered data change listeners
  • Publishing Data Change Events:
    • Capturing the 'Before' and 'After' states

Changes to Data Modification Transactions

In the current implementation, the semantics of a Data Modification Transaction did not explicitly specify the memory and consistency model of the transaction during its lifecycle.

In this proposal, a transaction tracks the original state of the data tree and a set of proposed changes (atomic operations) on the data tree that should be applied when the transaction succeeds.

A transaction is:

  • A self-consistent snapshot of the overall data tree (reference to data tree snapshots from the creation time)
  • A set of atomic operations which should be applied to the data tree.

Transaction Sub-Operations

  • Read - reads a subtree with all proposed changes (in scope of this transaction and the original snapshot) applied.
  • Data Changes - modifies a data tree:
    • Put (Write) - the actual operation (insert or replace) depends on the original state. Submits an Insert or Replace modification to the transaction backlog.
    • Remove - removes a subtree from the data tree. Submits a Remove change to the transaction backlog. A Remove operation also cleans the previously submitted writes associated with the removed subtree.

This in effect means that all subsequent reads on a transaction will result in a consistent view of data that was present at the time of the transaction start and all changes proposed by all consumers (in this transaction) applied.

Tracking of Data Tree Modifications

A transaction tracks changes in the data tree structure separately from the original state snapshot (which is immutable). Structurally, it is organized in the same way as the snapshot data tree, but it is limited only to nodes that are affected by changes and their parent nodes.

There are two distinct node types:

  • Explicitly modified node - Explicitly changed node is a node with associated data changes submitted by consumers of the transaction. During the transaction lifecycle, an explicitly modified node never changes its type to implicitly modified node. This node tracks:
    • The original version of a node as of the time of the transaction creation.
    • The change set which should be applied to this node (e.g. a replacement of child, insertion of child) and other explicitly changed nodes.
      • Insert change - a new node which should be inserted
      • Replace change - a new node, version of an old node which is to be replaced.
      • Delete change - a version of an old node that is to be removed.
  • Implicitly modified node - this node tracks nodes which are not directly modified, but indirectly modified because of a change of a child. An implicitly modified node could change its state to explicitly modified if a change is proposed to that node. An implicitly modified node may carry the original version of that node from the snapshot for ease of debugging.

Versioning of Data Tree Nodes

In order to keep track of changes, it is required to keep the version information about each data tree node. The version of a node consists of two fields:

  • version - tracks version of actual node.
Data Change Version changes
insert child child.version = ++parent.version;
replace child child.version = ++parent.version;
remove child ++parent.nodeVersion;

Versions and their changes should be maintained by data stores during the finish phase of the Two Phase commit.

Detecting Data Tree Node Modification Collisions

Versioning and change tracking in transactions that were introduced in this proposal allow for easier collision detection between transactions and the data store for a particular element in data tree:

The simplified collision detection depends on the type of action and changes:

 // modification contains action type and new node and version of original node.
 // storedNode is already stored node in data store, which resides at target location.
 boolean isConflicting(modification,storedNode) {
   switch(modification.type) {
     case INSERT:
       return (storedNode != null); 
     case REPLACE:
     case REMOVE:
       if(storedNode == null) return false;
       return modification.originalNode.version != stored.version
   }
 }

Chained Transactions

MD-SAL APIs need to be extended to allow support for explicit transaction chaining that use the core DOM Data Broker APIs and implicit chaining that uses various utility adapters.

Transaction chaining allows to create prerequisite chains between transactions - one transaction is based on successful completion of one or more previous transactions.

There are two types of chained transaction:

  • Join Transaction - a transaction does not contains any data changes, but could have multiple parent transactions as prerequisites. This transaction represents a data tree state, where are prerequisites (ancestors) are successfully completed.
  • Data Modification Transaction - a transaction can have a prerequisite parent transaction that represents the initial state for this transaction. The parent transaction may contain the proposed Data Changes.

Data Change Listeners

Data Change Listener registration proved to very generic, which does not allow consumers to more concretely specify criteria on which they are notified, and thus could not allow for some optimizations.

Data Change Publisher contract needs to be extended to allow following new types of subscription:

  • Operational Data change only - Listener is notified if and only if subtree changed in operational data store.
  • Configuration Data change only - Listener is notified if and only if subtree changed in operational data store.
  • Operational and Configuration data store changed - (current behaviour)

Data Change Publisher contract needs also to allow define scope of triggering event

  • Base - listener is notified if node changed
  • One - listener is notified if direct child of node changed
  • Subtree - listener is notified if node or it's subtree changed (current behaviour)


The In-Memory MD-SAL Data Store Implementation

A new In-Memory Data Store that uses the Normalized Data Tree Model will be implemented. The Data Store will represent its data structures (except for additional metadata storage) as an immutable tree, which de-facto is a consistent snapshot of the actual state.

The in-memory data store is also required to adhere to the contract described for Data Modification Transactions.

There are two in-memory data stores: one that represents the configuration tree, and one that represents the operational tree.

Nodes in the Normalized Data Tree Model are extended to contain following information:

  • Node version - captures the version of the node
  • Modification timestamp - timestamp for last revision
  • List of affected data modification listeners - set data change listeners, which registered themselves to be notified about modifications to that node itself and about modifications to any nodes in the subtree rooted at the node.

Atomic Operations

  • Insertion of leaf (subtree)
  • Removal of leaf (subtree)
  • Replace of leaf (subtree)
  • Set of additions, removals, replacements of leaves of same node

Atomic operations could not be invoked outside transaction.

Data Modification Transactions

The Data Store is a participant in the two-phase commit (as a commit handler).

The Request Commit Phase

Changes are applied starting from the deepest nodes in the data tree structure and then propagated up the tree to the parent node.

  1. Reference to the initial state is captured
  2. Data store creates a new subtree by applying specified operations that affect that node
  3. Data store captures the set of affected data change listeners with the initial state (reference to the old-subtree) and the new state (reference to the new subtree)
  4. Data store propagates the new subtree to the parent node and applies atomic operations on the parent node (1.) until the root node of the data store is replaced.

The Finish Phase

  1. Data store replaces the reference to the root element to newly created root element.
  2. Data store finishes the transaction.
  3. All captured affected listeners are notified with both the initial state and the new state.

The Rollback

Noop, since the reference to consistent (and public snapshot) is changed only in finish phase. Data Store is only required to not reference newly created tree.

Transaction Use Cases

Detailed descriptions of data store transaction use cases can be found in OpenDaylight Controller:MD-SAL:Architecture:DOM DataStore:Transactions

Tracking

Plugging in a Different Data Store Implementation

The In-Memory Data Store can be replaced by another Data Store implementation, as described in OpenDaylight Controller:MD-SAL:Architecture:DOM DataStore:Plugging in a Datastore into MD-SAL