Contest of xml lock Protocols Outline Key ideas of 2 groups of competing xml lock protocols

Contest of XML Lock Protocols

Outline

• Key ideas of 2 groups of competing XML lock protocols

• Doc2PL and followers
• Node2PL, NO2PL, OO2PL
• multi-granularity locking (MGL* group)
• RIX, RIX+, IRIX, IRIX+, URIX

• Our own protocols: taDOM group

• taDOM2: base protocol for DOM2
• lock conversion
• optimization to taDOM2+
• not considered taDOM3, taDOM3+

• Introduction to XTC

• identifying nodes
• meta-synchronization

• Performance evaluation

• taMIX framework
• transaction types of the Banking benchmark
• measurements and comparison

• Conclusions and outlook

DOM Storage Model

• XML document Lastname Firstname
  49.99
  

Doc2PL and its Followers

• Basic assumption: Traversal from root to context node

• Sample of operations

• nthP retrieves the nth child of C
• nthM retrieves the nth child (backw.)
• insA inserts a new node after C
• insB inserts a new node before C
• del deletes a given node

• Separation of traversal and modification of

• document structure (T/M)
• content (S/X)
• direct jumps (IDR/IDX)
• no intention locks!

Doc2PL and its Followers (2)

• 2. NO2PL

• acquires locks for all nodes whose (conceptual) pointers are traversed or modified

• example at C1: insB (C0)

Making Full-Fledged Protocols for the *-2PL Group

What Else Do Full-Fledged XML Protocols Need?

• Support of direct access via indexes

• jumps to element nodes not owning an ID attribute
• cheap mechanism to identify the ancestor node IDs!

• Lock conversion

• operations of a transaction necessarily share some part of the ancestor path
• weakest possible locks after conversion

• Appropriate intention locks and subtree locks needed

• lock depth parameter desirable

• Use ideas of MGL locking

• subtree locks + intention locks
• 4. IRX
• 5. IRX+
• specialized conversion (+)
• depending on locking situation

Applying Multi-Granularity Locking to XML

• 6. IRIX conversion

• read C1 – C3
• delete C2

MGL Group (Cont.)

• 8. URIX

• compatibility matrix
• conversion matrix

Tailored Node Locks for XML – taDOM2

• 9. taDOM2

• Node locks and compatibility matrix

• refined URIX protocol with extensions to lock a complete level in a subtree
• well known: IR/IX and R/X (here SR/SX)
• edge locks not discussed (3 modes)

Node Locks (1)

• Node read lock (NR)

• requires IR locks on the ancestor path

• Level read lock (LR)

• requested for reading the context node and all nodes located at the level below (all direct-child nodes)

• Child exclusive lock (CX)

• indicates an X lock on a child
• defined, in addition to IX, to detect conflicts with LR

Node Locks (2)

• Locking subtrees exclusively: intention exclusive lock (IX), child exclusive lock (CX), and exclusive lock (X)

• requested for updating the context node's content or deleting the context node and its entire subtree
• requires a CX lock on the parent and IX locks on the ancestors

Tunable Lock Depth

• Goal

• reduce the number of locks held by using coarser lock granularity
• may decrease concurrency
• when nodes deeper than lock depth are accessed: lock modes SR and X are used at the lock depth level

Conversion of Node Locks

• Conversion for weakest possible locking paths

• LR  CX requires explicit NR locks on all children
• node labeling scheme cannot deliver IDs of descendent nodes

taDOM* Group – Lock Protocol Optimization

• 10. taDOM2+: LRIX, SRIX, LRCX, SRCX

• new lock modes enable conversion without accessing the document
• e.g., LRCX (level read child exclusive) combines both modes and avoids application of conversion rule CXNR

• Optimization steps

• 11. taDOM3: modification of a single context node
• 12. taDOM3+: new lock modes to avoid document access

XTC – Architectural Overview

taDOM Storage Model – View of Lock Mgr

• XML document Lastname Firstname
  49.99
  

Identifying Nodes – Node Numbering Schemes

Meta-Synchronization

• Meta-synchronization

• allows identical runtime environment for lock contests
• lock mgr provides methods: supportsSharedLevelLocking, supportsSharedTreeLocking, supportsExclusiveTreeLocking

• Meta-lock requests from node manager to lock manager

• request shared node lock
• request shared level lock
• request tree lock (shared, update, exclusive)
• . . .

• Meta-lock requests are mapped to the actual lock algorithm

• lock manager implements a certain interface
• exchange of the lock manager interface implementation exchanges the system's complete XML locking mechanism

TaMix Benchmark Framework

• So far, no update benchmark for XML docs available

• TaMix infrastructure for distributed OLTP benchmarks
• a list of TX types is assigned to each client
• each client runs n TX in parallel and keeps the workload level

• Automated measurement

• per measurement point 3 runs
• configurable runtime interval
• for 12 lock protocols
• in 6 lock depths
• ~ 20 hours per measurement

Performance Measurement

• Data base (DataGuide)

• Size

• ~8 MB
• 580,000 taDOM nodes

Performance Measurement (2)

• Transaction types for Banking benchmark

• bank transfer (5 TX/client)
• jump to a randomly selected account element
• navigation through the document, update operations for Balance and Posting
• standing order (5 TX/client)
• random account, navigation to Standing Orders, read of all orders
• evaluation of the Child axis, small fraction of update operations
• customer master
• renaming of a Customer element (1 TX/client)
• in parallel, reconstruction of randomly selected Customer fragments (5 TX/client)
• account statement (5 TX/client)
• reconstruction of randomly selected Account fragments
• small amount of update operations (insertion an entry in Protocols)
• removal of a customer from the data base (2 TX/client)
• deletion of fragments

• Transaction mix

• processes all transaction types in parallel
• constant system load of 66 transactions

Performance Measurement (3)

• Number of committed transactions in Banking benchmark

Performance Measurement (4)

• Number of aborted transactions in Banking benchmark

Detailed Performance Measurement (5)

• Successful bank transfers

• node-based navigation, update operations

Detailed Performance Measurement (6)

• Successfully modified standing orders

• evaluation of child axis, few update operations

Detailed Performance Measurement (7)

• Customer Master: successfully modified Customer elements + reconstructed Customer fragments

• renaming of an inner element node

Detailed Performance Measurement (8)

• Successfully processed account statements

• reconstruction of fragments, few update operations

Detailed Performance Measurement (9)

• Successfully removed customer records

• deletion of fragments

Conclusions and Outlook

• XTC is used as a test vehicle for empirical DB research

• effectiveness of XML concurrency control
• fine-granular locking on nodes and edges
• meta-synchronization allows comparison of different compatibilities
• taDOM* protocols
• multiplicity of lock modes
• intention locks are important
• indexed document access is frequent
• ancestor path locking without accessing the storage engine desirable
• performance evaluation revealed
• use of tailored lock modes pays off
• indexed document access is frequent
• effect of isolation levels on transaction throughput
• influence of node numbering schemes (insertions at arbitrary positions)

• Outlook

• phantom prevention
• mapping different XML language models via access models to our XML storage model, e. g., to analyze the locking behavior of XQuery processing