DAP4: Encoding for the Data Response

<< Back to OPULS Development

Background

There are two different approaches to deserializing the data received by a DAP client: The client may process the data as it is received (i.e., eager evaluation) or it may write those data to a store and process them after the fact (lazy evaluation). A variant of these techniques is to process the data and write it to a store, presumably because the initial processing steps are useful while having the data stored for later processing enables still other uses. However, in this document I'm not going to look at the latter case because experience so far with DAP2 has not provided any indication that would present any performance benefits. We do have example clients that use both eager and lazy evaluation.

HTTP/1.1 HTTP/1.1 defines a chunked transport scheme. In the past we have spent a fair amount of time on the notion of chunking as a way to achieve reliable transmission of errors when those errors are encountered during response formulation, that won't be addressed in this document. Instead, this document will assume that the entire response document described here is chunked in a way that enables reliable transmission of errors. The details of that transfer encoding will be described elsewhere.

Problem addressed

There is a need to move information from the server to a client. The way this is done should facilitate many different designs for both server and client components.

Assumptions:

1. Since DAP is so closely tied to the web and HTTP, its design is dominated by that protocol's characteristics.
2. Processing on either the client or the server is an order of magnitude faster than network transmission.
3. Server memory should be conserved with favor given to a design that does not require storage of large parts of a response before it is transmitted (but large is a relative term).
4. Clients are hard to write and the existence of a plentiful supply of high-quality clients is important (of course, servers are hard to write, too, nut there are between 5 and 10 times the number of DAP2 clients as servers).
5. DAP4 is designed to work over transports that are inherently serial in nature.
6. The response does not explicitly support a real-time stream of data (e.g., a temperature sensor which is a data structure of essentially infinite size). It may, however, be the case that the response can encode that kind of information.

Broad issues:

1. It should be fast
2. It should simple
3. It should be part of the web

Proposed solution

The DataDDX response document will use the multipart-mime standard. A DataDDX response is the server's answer to a request for data from a client. Each such request must either include a Constraint Expression enumerating the variables requested or a null CE that is taken to mean 'return the entire dataset.' A response will consist of two parts:

1. A DDX that has no attribute information and contains (only) the variables requested; and
2. A binary part that contains the data for those variables

Thus, while the response uses the multipart-mime standard, there are only two parts - the DDX containing variable names and types and the binary BLOB containing data.

Structure of the binary part

The binary part starts with the MIME headers for a Part in a multipart-related document [[1]]. This header will include the byte-order (big-endian or little-endian) used to encode values.

Data in the 'binary part' will be serialized in the order of the variables listed in the DDX part. Essentially this is the serialization form of DAP2, but has been extended to support arrays with varying dimensions and stripped of the redundant information added by various XDR implementations.

Encoding of values

Unlike DAP2, DAP4 will not use XDR. Values will be encoded using the byte order of the server. We will pad all values to four-byte words using the same algorithm as employed by XDR (single- and two-byte variables will be padded; arrays will be padded to four-byte 'boundaries' but the elements of a will not). This ensures that a Int16 x[1024][1024] takes up 2MB and not 4MB as would e the case if XDR were used to transmit it.

About serialization of varying-sized variables

There are several kinds of varying data:

1. Strings
   • String s;
2. Array variables that vary in size
   • Int32 i[*];
   • Float64 j[10][*];
3. Structure variables with varying dimensions and Sequence variables
   • Structure { int32 i; int32 j[10]; } thing[*];
   • Sequence { int32 i; int32 j[10]; } thing2;
4. Structure variables that have a varying dimension and one or more fields that vary
   • Structure { int32 i[*]; int32 j[10][*]; } thing[*];

Note that there is no practical difference between a (character) String and an integer or floating point array with varying size except that the type of elements differ. Thus, the issues associated with encoding Int32 i[*] are really no different than encoding the String type. This same logic can be extended to a varying array of Structure (with fixed size fields). A varying array of Structure that contains one or more varying fields requires that the fields and the enclosing Structure be specially serialized.

Assumptions:

1. String: it is assumed that the server will know ( or can determine w/o undue cost) the length of the String at the time serialization begins.
2. It is assumed that the size of any variable dimension will be known at the time of serialization of that variable's dimension.
3. For a Sequence, it is assumed that the total size may be considerable and not known at the time serialization begins.

General serialization rules

Narrative form:

1. Fixed size types: Serialized by writing their (encoded) data.
2. Strings: Serialized by writing their size as a N-bit integer, then their encoded value
3. Scalar Structures (which may have String/varying fields): Each field is iteratively serialized.
4. Arrays (possibly with varying dimensions): An array is serialized by serializing the vector denoted by the leftmost dimension. For a fixed size dimension, each element is serialized. For a varying dimension, the length of the vector is written and then each element is serialized.
5. Sequences are serialized row by row: First a Start of Instance marker is written, then each of the fields of the row are serialized, until the last row of the Sequence is serialized, then a End of Sequence marker

TBD:

1. How to encode the checksum information?
2. Is any information besides the byte-order needed in the BLOB header?

Notes:

1. This will use receiver-makes-right and thus needs a header (big-endian - reference the IETF std) to convey that
2. Sequences cannot contain child Sequences (i.e., we are not allowing 'nested sequences') in DAP4
3. Both an array [20][10] and [2][10][10] will be serialized as 200 sequential elements, but array[*][*] and array[*][*][*] must include markers that indicate where the different elements lie.
4. This set of serialization rules can be modified slightly to support the case where fixed, string and varying size data are separated into different parts of a multipart-mime document.

Examples

A single scalar

Dataset {
    Int32 x;
} foo;

(NB: Some poetic license used in the following)

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

x 
--<<boundary>>

A single array

Dataset {
    Int32 x[2][4];
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

x00 x01 x02 x03 x10 x11 x12 x13 
--<<boundary>>

A single structure

Dataset {
    Structure {
        Int32 x[2][4];
        Float64 y;
    } s;
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

x00 x01 x02 x03 x10 x11 x12 x13 
y 

--<<boundary>>

An array of structures

Dataset {
    Structure {
        Int32 x[2][4];
        Float64 y;
    } s[3];
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

x00 x01 x02 x03 x10 x11 x12 x13 
y 
x00 x01 x02 x03 x10 x11 x12 x13 
y 
x00 x01 x02 x03 x10 x11 x12 x13 
y 

--<<boundary>>

A single varying array (one varying dimension)

Dataset {
    String s;
    Int32 a[*];
    Int32 x[2][*];
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

16 This is a string 

5 a0 a1 a2 a3 a4

3 x00 x01 x02 6 x00 x01 x02 x03 x04 x05 

--<<boundary>>

NB: varying dimensions are treated 'like strings' and prefixed with a length count. In the last of the three variables, the array x is a 2 by varying array with the example's first 'row' containing 3 elements and the second 6.

A single varying array (two varying dimensions)

Dataset {
    Int32 x[*][*];
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

3

3 x00 x01 x02 

6 x10 x11 x12 x3 x14 x15

1  x20 

--<<boundary>>

An varying array of structures

Dataset {
    Structure {
        Int32 x[4][4];
        Float64 y;
    } s[*];
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

2

x00 x01 x02 x03 x10 x11 x12 x13
y 

x00 x01 x02 x03 x10 x11 x12 x13 
y 

--<<boundary>>

NB: two rows...

An varying array of structures with fields that have varying dimensions

Dataset {
    Structure {
        Int32 x[2][*];
        Float64 y;
    } s[*];
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

3

1 x00 4 x10 x11 x12 x13 
y 

3 x00 x01 x02 2 x10 x11
y 

2 x00 x01 2 x10 x11
y 
--<<boundary>>

An Sequence

Dataset {
    Sequence {
        Int32 x[2][*];
        Float64 y;
        Float64 x;
        Structure {
            int32 p;
            Int32 q;
        } ps_and_qs;
    } s;
} foo;

Content-Type: multipart/related; type="text/xml"; start="<<start id>>";  boundary="<<boundary>>"
 
--<<boundary>>
Content-Type: text/xml; charset=UTF-8
Content-Transfer-Encoding: binary
Content-Description: ddx
Content-Id: <<start-id>>

    <<DDX here>>
--<<boundary>>
Content-Type: application/octet-stream
Content-Transfer-Encoding: binary
Content-Description: data
Content-Id: <<next-id>>
Content-Length: <<-1 or the size in bytes of the binary data>>

SOI

1 x00 4 x10 x11 x12 x13 
y 
x
p
q

SOI
3 x00 x01 x02 2 x10 x11
y 
x
p
q

SOI
2 x00 x01 2 x10 x11
y
x
p
q

EOS
--<<boundary>>