Portable object constant-time field lookup

Problem

Portable object serialization is first released in Apache Ignite 1.4 as an experimental feature and is not available form public API.

Some critical Ignite features like indexing/queries require object introspection without deserialization. To achieve this portable protocol writes object fields as follows:

[X  ..X+4] - Field 1 ID

[X+4..X+8] - Field 1 length

[X+8..Y  ] - Field 1 content

[Y  ..Y+4] - Field 2 ID

To read a field we get it's ID and search for it starting from the object head. This gives good performance and data locality for regular serialziation/deserialization cycles because normally fields are written in the same order as they are read. As a result usually we can find the field during read in O(1) time.

void writePortable(PortableWriter w) {
    w.write("A", a);
    w.write("B", b);
}
 
void readPortable(PortableReader r) {
    a = r.read("A");
    b = r.read("B");
}

To the contrast, indexing engine usually read fields in random order with O(N) complexity on average.

In Ignite 1.5 we need to change the protocol so that field position could be found in ~O(1) on average.

Protocol 

The following changes are proposed:

• FIeld IDs and lengths are moved to object footer.
• Relative footer offset is added to object header.
• All field IDs are hashed in order they are written. Resulting value is saved to object header. We refer to is as *schema ID*.

Resulting object layout (unrelated header pieces are ommited):

[0   .. 4   ] - Footer offset; could be zero if the whole object is written in raw mode.

[4   .. 8   ] - Schema ID. Absent in case footer offset is zero.

[8   .. X   ] - Field 1.

[X   .. Y   ] - Field 2.

[Y   .. Y+4 ] - Footer start, field 1 ID. 

[Y+4 .. Y+8 ] - Field 1 offset.

[Y+8 .. Y+12] - Field 2 ID, etc.

Implementation details