Balisage Paper: Processing Arbitrarily Large XML using a Persistent DOM

Related Work

One approach to overcome memory issues is to perform streaming operations in very specific situations. Peng and Chawathe (Peng05) present a streaming implementation for a limited subset of XPath operations, Florescu, Hillery et al. (Florescu03) achieve the same for XQuery; the Streaming Transformations for XML (STX) language defines a language similar to XSLT geared at streamed execution (STX); and the unreleased XSLT 2.1 specification will contain special syntax to allow a limited streaming execution mode (Kay10).

However, streaming is a very limiting programming model. Many real world XML applications require access to preceding or following nodes, like the title of the section a node is contained in. To achieve streaming execution, the above approaches have to exclude or severly limit commonly used operations like backwards navigating axes.

Another approach is to use databases to store XML documents, moving them out of memory to secondary storage. There is a wide range of literature on the topic, with early efforts focusing on shredding XML documents to store them in relational databases, either in tables tailored to a specific XML schemata, or in a generic structure (Tatarinov02). As requiring schemata upfront contradicted user expectations and a generic database layout results in too many join operations for common hierarchy navigation, later approaches propose a variety of numbering schemes to encode the document structure (Meier02). While different solutions with different features exist, these numbering schemes generally support resolving at least some structural queries based on the numbering. Early schemes required re-numbering on document modifications, later ones overcome this limitation (ONeil04).

Using databases with numbering schemes, we can overcome main memory limitations for storage and search. However the question of how to efficiently process potentially large XML documents in application code remains.

Contributions

This paper presents a different approach: a persistent, hard-disk based DOM that can store arbitrarily large XML documents and provides read/write access to them through the regular Java DOM API without using a node numbering scheme. Regular XML applications can use the familiar DOM programming model and the wealth of available XML tools relying on the DOM interface. This paper is based on EMC Documentum xDB's implementation of the presented concepts.

xDB differs from other persistent XML stores and other persistent DOM implementations in that it is optimized for direct DOM access. Navigation operations corresponding to the common DOM operations are executed in constant time comparable to main-memory based DOM implementations. xDB, unlike other XML databases, does not use a node numbering scheme but relies on indexes for fast value lookups.

We extensively describe xDB's data organization and storage layout, with a particular focus on efficient encoding of node data. We provide performance comparisons with two different main memory DOM implementations.

Traditional Document Model Implementation

DOM implementations (or any document model) usually create classes for the various XML node types, and have fields to store the node's properties, like the node name, the list of children, the parent node, and so on.

Figure 1 shows a typical DOM element implementation, ignoring any inheritance chain and inlining all fields for the sake of simplicity. We can see that the Element node keeps references to other nodes in the tree, some basic references like the first child and the next sibling to implicitly form the tree itself, and some to enhance navigation speed, like the parent reference or the previous sibling reference, that could be emulated using the basic references.

Figure 1: A typical DOM Element Implementation (simplified)

There are many different ways of representing an XML document, differing in memory consumption, navigation speed for particular axes, whether the document can be modified after parsing, and so on. Some implementations avoid storing immediate object references to limit the number of objects held in memory, but still store the complete document in memory. However they all rely on the assumption that the complete document is parsed at once, and kept in memory while operating on it.

This leads to the observed limitations in supported document size caused by memory exhaustion.

Disk based DOM architecture

Our DOM implementation avoids this limitation by storing a binary representation of an XML document on the hard disk. While this representation avoids keeping the whole document in memory at all times, it is still directly navigable from the programming interface, without requiring re-parsing or buffering parts of the document during program execution. Documents are also mutable — nodes can modified after initial parsing, again without requiring the whole document to be in memory.

Nodes are identified using a 64 bit number and stored in data pages that allocate individual nodes in slots. The first 54 bit of a node identifier point to the page, the latter 10 bits identify a slot within a particular page. As the pages are stored in files in the file system, within the first 54 bits, 20 bits are used to identify a particular file used for storage. Node identifiers directly point to the physical location of a node; there is no indirection between node identifiers and physical node location (see section “Modifications” for a detailed discussion of the impact on updates). xDB node identifiers can be considered "physical identifiers".

This approach is quite different from other XML databases, that typically use a node numbering scheme to identify nodes, separating the logical node identifier from its physical identifier/location. A node numbering scheme can be helpful to answer unbounded structural queries, such as the XPath /bib//book//author. On the other hand, such numbering schemes only help evaluating queries over a large node set; navigating within individual nodes in a DOM-like fashion will probably be slower due to the additional indirection required (i.e., typically an index lookup by node ID). We assert that unbounded structural queries are rare in actual applications. Applications typically either search for specific pieces of information, or process a complete document or document fragment. Searching within XML can be mapped to value based indexes, while processing XML commonly means visiting more or less every node of the document, thus requiring efficient navigation. xDB provides configurable index structures that can answer combined structure and value queries (e.g. /bib//book[author/lastname = 'Doe']) to support efficient searching for nodes. To process nodes once they have been found, xDB resorts to efficient navigation using physical node identifiers.

Pages are of configurable size but should be identical in size to the underlying file system's page size, for reasons of data consistency in write operations^[3]. This means pages are usually 4 kilobytes (Windows, Linux, Mac OS X) or 8 kilobytes (certain UNIXes).

Individual XML documents can spread across any number of physical files, pages, and slots, but always use at least one complete page; pages are not shared between multiple documents. The minimum storage size consumed by a document is thus one page (typically 4 kilobytes). The theoretical maximum size for an individual document is the number of possible files times the number of pages in a file, times the individual page size. A database configured with just a single file can thus (assuming 4096 bytes page size, using non-SI prefixes) hold documents up to 2³⁴ * 2¹² bytes = 2⁴⁶ ≈ 64 terabytes in size; an ideally configured database with 2²⁰ files could theoretically hold 2⁶⁶ bytes ≈ 64 exabytes. The attentive reader will have precluded that we have not been able to test the implementation with exabytes of storage. This is left as an exercise to the first customer reaching that database size. Databases with dozens of terabytes of data are common in customer deployments.

These theoretical storage limits refer to the size of documents in xDB's internal, proprietary binary XML format. We will show that this does not necessarily correspond to regular serialized XML size, but is typically comparable or slightly less.

Storage Layout

xDB's storage layout is depicted in Figure 2. Pages are stored in one of potentially many data files grouped together in segments. Data files are cached in main memory within a data structure called page cache. Each page contains multiple slots, which in turn store individual nodes. Slot size is not fixed - different nodes, even of the same type, can have different lengths. Slot allocation information is stored in an administrative section within the data page, giving start and end locations for each slot.

Figure 2: Storage Layout in xDB

The layout of an individual slot depends on the node's type. Storage layout is defined through an XML dialect, which is then used to generate Java source code through an XSL transformation as part of the build process.

Node Structure

xDB stores node trees much like other DOM implementations, spanning a tree through first-child and next-sibling pointers. The major difference is that xDB takes great care to reduce the size of objects, and that xDB directly operates on byte arrays to store nodes.

Figure 3 shows the bit layout of the two bytes comprising an XML Element header. All nodes start with a sequence of bits determining the node type. The most common nodes (elements and text nodes) only need two bits of storage for the type, as their type codes are 01 and 00. Other node types are stored using longer bit sequences starting with a bit 1. The following bits all represent booleans, indicating the presence or absence of fields in the elements storage and other properties of the node and its storage layout. This reduces on-disk storage consumption for elements that do not have children or siblings and documents that do not use various features like namespaces, post schema validation infoset (PSVI) information, and so on. The bit fields read only and namespace node handle two special cases. Inlined entity reference nodes are marked as read only to protect against incorrect modifications, thus the bit field. Additionally, xDB supports DOM Level 1 documents that do not have namespace support. For those documents, compliant DOM implementations must return null for calls to the namespace-aware methods like getLocalName(). If the bit is set to 0, xDB will return null on those calls.

Figure 3: DOM Element Header

For an element, this header is followed by the following, partially optional fields:

• Parent reference

• Next sibling reference (optional)

• Previous sibling reference (optional)

• First child reference (optional)

• Last child reference (optional)

• Local name code (integer)

• Namespace URI code (integer, optional)

• Prefix name code (integer, optional)

• First attribute reference (optional)

• Primitive type name code (integer, optional)

• Complete type name code (integer, optional)

• PSVI properties (integer, optional)

These fields following this header can have different types: 32 bit numbers, 64 bit numbers, node references as relative 64 bit node IDs, strings, and string lists. The presence of optional fields if governed by their respective bit field in the element header. If a field is absent, it takes no storage space at all and retrieving it will return a specified default value, for example null for node references or -1 for undefined namebase codes.

Another storage size optimization is the First Child next? bit field. If true, the following node on the data page is the first child of this node, allowing us not to store the node ID. This reflects the observation that most XML documents are parsed once and rarely modified. In that case, the parsing process will cause an element's children to be stored directly following the element within the data page.

xDB stores all different DOM node types using this scheme, exploiting the various optimizations possible for different node types - for example, attribute nodes do not need a type field as their type is implicitly known at the place where they are referenced.

DomNode getFirstChildRef() {
  Page slotpage = getPage();
  byte[] a = slotpage.getDataReadOnly();
  int slot = getSlot();
  int offset = getOffset(a, slot);
  int start = Page.unpack2(a, offset);
  int end = Page.unpack2(a, offset - 2);
  if (a[start] <= FORWARD_OBJECT) {
    // handle forwarded objects by updating a, start, and end
  }

  long diff;
  if ((a[start] & 1 << 3) != 0) {
    return null;
  } else if ((a[start] & 1 << 2) != 0) {
    diff = 1L;
  } else {
    int fs = start;
    fs += 2;
    fs += packedLongLen(a, fs);
    if ((a[start + 1] & 1 << 7) == 0)
      fs += packedLongLen(a, fs);
    if ((a[start + 1] & 1 << 6) == 0)
      fs += packedLongLen(a, fs);

    assert fs < end;
    diff = getRelDiff(unpackLong(a, fs));
  }
  long id = getPageAndSlot() + diff;
  Page idpage = getPageFromPS(id);
  int idslot = getSlotFromPS(id);

  return DomNode.newDomNode(idpage, idslot);
}

<address_list>
  <address id='1'>
    <firstname>...</firstname>
    ...
  </address>
  ...
</addresslist>

0001e0d0  __ __ __ __ __ __ __ __  __ __ __ 15 ff 01 70 00  |ttmjtu2/ynm...p.|
0001e0e0  10 7f 01 1a 04 16 01 02  __ __ __ __ __ __ __ __  |........?...B...|

Parsing

An important performance benchmark in XML processing is parsing XML documents. In this benchmark, we parsed a 20 MB XML document of Wikipedia article titles, URLs, abstracts, and links. The document has a relatively simple, flat structure, with an element for every document that has several children for the document's details.

xDB's parser and DOM implementation take about twice as long to parse a document, probably due to the conversions necessary for xDB's internal storage. The lower standard deviation compared to the other two implementations is most likely because xDB creates less objects in memory, and thus is affected less by Java garbage collection.

Reducing the available memory to 64 megabytes, the other two implementations failed parsing the document due to memory exhaustion. xDB's parsing time increases, as the parsed document will no longer easily fit the available cache memory and parts have to be paged out. If we increase document size further or decrease available memory more, the parsing process will be effectively limited by the throughput of the hard disk.

More thorough scalability tests of xDB XML parsing can be found in a whitepaper by Jeroen van Rotterdam (vanRotterdam09)

DOM navigation

In this test, we walk the document from the parsing test using DOM navigation, or in the case of Saxon using it's XDM data model. The tests performs an in-order visit of all nodes in the document, retrieving text values for attributes and text nodes, and node names for nodes that have a name (elements, attributes, processing instructions). The numbers for Saxon are not entirely comparable, as the code uses a different document object model to achieve the same task. Document parsing time is not included in the numbers.

Again, processing takes about twice as long on xDB's DOM implementation. Runtime increases slightly with constrained memory.

XSL transformation

In this test, we transform the aforementioned document using a simple XSLT 1.0 stylesheet. We use the Saxon and Xalan XSLT implementations, both on their native DOM implementations (Xerces for Xalan), and both on xDB's DOM implementation.

We can again see that xDB's DOM is slower than the XSLT processor's native implementations, but again the overhead is tolerable. Saxon performs slightly worse than Xalan on xDB's DOM; initial investigation suggest this might be due to Saxon's DOM driver that operates on DOM node lists, which are computationally expensive as they have to be live lists, directly reflecting any changes in the parent node. This is problematic in an implementation such as xDB, where single logical DOM nodes can be represented by many different objects. In addition, xDB does not maintain a list with all children of a node, so that indexed access to a child within a DOM list is not O(1) in all cases.

We performed the same test on an identically structured document of 900 MB. Neither Saxon nor Xalan were able to parse the document, even with 3.5 GB of memory available. Running Xalan on xDB exhausted memory as well, as the implementation appears to copy some of the DOM structure into it's own data structures, exhausting memory in the process.

Running Saxon on top of xDB's DOM implementation managed to transform the document in reasonable time. Both with a large (512 MB) and a small heap (64 MB), the document was transformed in less than a minute. Available memory has no noticeable impact on performance; runtime is effectively limited by IO throughput as xDB loads cache pages from the disk. This also explains the supra-linear runtime growth from 250 ms for a 20 MB document to 45 seconds for a 900 MB document; the first test exclusively uses heap memory, while the second test is limited at least in part by disk performance.

Interestingly, runtime profiling of these simple XSLT transformations shows that significant time (15-20%) is spent looking up element names by their namebase code. This could be entirely avoided if the DOM API provided an interface to create an implementation specific node name matcher. That would not only allow us to avoid the namebase lookup but also reduce relatively expensive string comparisons on node names to integer comparisons on namebase codes in xDB's case.

Discussion

The benchmark results show that xDB's hard-disk backed DOM implementation is slower than alternative main memory based implementations for small document sizes. On the other hand, our scheme makes it possible to handle documents of sizes that simply cannot be processed using main memory implementations. Beyond that, xDB ofcourse offers many other database features that might be useful to users.

The fact that xDB performs well compared to a DOM implementation such as Xerces might be surprising, given that, when navigating to the first child of an element, a Xerces DOM node can simply return the value of a field (or the first value of an array) where xDB has to perform a whole series of bit manipulations. We believe that this is an effect of a modern processor's memory hierarchy. As CPU internal caches and clock rates are significantly faster than main memory access, modern CPUs spend most of their clock cycles waiting for memory to be loaded into the CPU's cache (Manegold00, Chilimbi99). xDB's compact storage layout sacrifices several CPU operations for reduced memory use, but those CPU operations can execute in the time a CPU would normally spend waiting for memory to be loaded. Because related nodes are allocated in contiguous byte arrays, it is also more likely that the CPU already holds the memory location for the next node in a cache line.

Note that these benchmarks assume a document that is parsed once to be processed, and then discarded. In real world applications, documents will often be processed many times. Because of its persistent storage, xDB can avoid re-parsing documents over and over again, giving substantial benefits for such applications.