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

Yüklə 468 b.
ölçüsü468 b.

Contest of XML Lock Protocols


  • 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 The Title Lastname Firstname

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

XTC – Architectural Overview

taDOM Storage Model – View of Lock Mgr

  • XML document The Title Lastname Firstname

Identifying Nodes – Node Numbering Schemes


  • 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)

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)

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

Yüklə 468 b.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2022
rəhbərliyinə müraciət

    Ana səhifə