Supporting a new database

[prdoyle]

Here are the considerations for supporting a new database.

Subscription to partial-document updates

The database needs to offer a way to subscribe to updates, and for each update, to determine which part of the state tree is changing, and what the new value is.

Diagnostic attributes

Early on in testing, you're going to want to be able to transmit diagnostic attributes from the thread performing an update to all the threads receiving that update, because diagnostic attributes are used by DriverConformanceTest itself.

Create if not exists

The current convention is that the bosk library will initialize the database if it doesn't already exist. It's not clear whether this is a good idea in the long run, but it sure is convenient.

Object model

Bosk's object model (with Catalog and SideTable) differs from that of JSON in that bosk needs a container structure with the following features:

1. It must preserve upsertion order, with new elements going at the end
2. It must permit element replacement and deletion by ID, not by index

JSON objects fail requirement 1, while arrays fail requirement 2.

The most convenient representation of all would be a simple JSON object:

{
    "item1": { "id": "item1" },
    "item2": { "id": "item2" },
    "item3": { "id": "item3" }
  }

However, unless the database implements requirement 1, this is not a suitable choice because it loses ordering information. (MongoDB's BSON objects do, in fact, meet these requirements, so this is the format used by bosk-mongo.)

There are two ways bosk has traditionally adapted JSON to conform to bosk requirements.

The first representation uses a separate order field. A Catalog would be represented as an object with two fields, entries and order; for example:

{
  "entries": {
    "item2": { "id": "item2" },
    "item3": { "id": "item3" },
    "item1": { "id": "item1" }
  },
  "order": ["item1", "item2", "item3"]
}

An entry can be upserted efficiently as follows, assuming the following can be done atomically:

• If the new entry's ID is present in entries, then replace it
• Otherwise, add it to entries and append it to order

An entry cannot be deleted efficiently unless the implementation offers an efficient delete of an array entry by its value rather than by its index; otherwise, a linear scan over the order array is required.

The second representation uses an array of single-field objects; for example:

[
  { "item1": { "id": "item1" } },
  { "item2": { "id": "item2" } },
  { "item3": { "id": "item3" } }
]

This representation is more legible and convenient for reading and writing whole objects, so it is used by bosk-json, but updates and deletes are inefficient.

A third representation could make use of the fact that new entries are always added at the end, and use a counter:

{
  "insertCounter": 11,
  "entries": {
    "item2": { "seq": 5, "state": { "id": "item2" }},
    "item3": { "seq": 7, "state": { "id": "item3" }},
    "item1": { "seq": 3, "state": { "id": "item1" }}
  },
  "order": ["item1", "item2", "item3"]
}

This representation has obvious drawbacks in terms of verbosity and complexity, but it does in theory permit O(logn) updates and deletes by enabling a binary search of the order array based on the corresponding seq fields.

All in all, how to best represent the bosk state tree in JSON depends very much on the details of the database's storage and update model, and sometimes there is just no good match.