TaDOM is a family of hierachical lock protocols tailored for the application on XML document trees.

The protocols allow for concurrent transaction processing on XML documents while preserving transaction serializability. The key are fine-grained lock types and modes, carefully adjusted to XML its typical processing patterns.

The name taDOM comes from "transactional DOM", because the original protocol was originally developed for the synchronization of DOM API. The taDOM3+ protocol is the most advanced variant in our protocol familily and provides the highest concurrency.

In combination with DeweyIDs, the taDOM3+ protocol can be used to synchronize concurrent access throught different XML-APIs like DOM, SAX, and XQuery/XPath at the same time!

Node Locks

Node Locks are used to serialize concurrent read and write access to document nodes. An NR (Node Read) lock is required to read a node.  To make potential write transactions aware of the read operation, an IR (Intention Read) lock must be acquired for all ancestor nodes.

The LR lock allows to read the context node as well as all direct child nodes. It was introduced to reduce the lock overhead for the frequent XML-operations getChildren() and getAttributes() to a single lock request. Finally, the SR (Subtree Read) lock is used to protect a whole subtree in a document from concurrent modifications by other transactions.

For write operations the taDOM protocol provides two different types of exclusive locks. Similar to the NR lock, the NX (Node Exclusive) lock only locks the context node for exclusive access., i.e., other transactions are still able to read and/or modifiy nodes in the subtree below. This mode is used for renaming element nodes and content updates on text and attribute nodes, because the update is local the respective context node.

Insert and delete operations, however, always affect the specific node together with all its descendants. Thus, those operations require the acquisition of an SX (Subtree Exclusive) lock on the context node.

Both exclusive write modes have in common that they require an CX (Child Exclusive) lock on the direct parent node, and IX (Intention Exclusive) locks an all ancestors above. The CX lock is necessary to prevent other transactions from the acquisition of an LR lock on the parent, because this would implicitly allow its owner to read the exclusively locked child node.

Compatibility Matrix

The full taDOM3+ protocol consists of 19 lock modes. In addition to the shown read und exclusive locks, the protocol employs combinations of this base locks (conversion modes), which become useful, when more than mode is requested for a single node.

Further, the special update locks NU, SU are available. Once granted, these locks allow for a direct (non-blocking) conversion of a lock into either a shared read lock or an exclusive write lock. Careful use of this locks allows to avoid deadlocks.

 

Example

Here is an example of taDOM3+ in action:

Performance

We continously run benchmarks to monitor the results of one of these benchmark runs.  Here, 50 clients concurrently accessed an 8MB XMark document and performed various read and write transactions, like, e.g., reading seller information, placing bids on items, updating user data, and reading or inserting new mails.   The transaction mix was designed to cover typical operations on XML documents like, e.g., navigation, direct jumps to nodes, content updates, and the reconstruction and insertion of whole subtrees. To test the robustness of our approach we varied also the weights of the different transaction types in our three benchmark workloads. In the Default mix the document tree was equally accessed in both higher and deeper levels, whereas in the Deep and the Flat workload, the document tree was mainly read and modified at deeper and higher levels respectively.   As you can see, when both serializability and concurrency are important, taDOM is superior to the simple "only one transaction at a time" model of most other XML Database Systems.