Improve StyxObjectStore notification mechanism

[chrisgresty]

The current mechanism is vulnerable to out-of-order notifications, whereby older database states can be emitted after newer ones. Given that it is not essential for all notifications to be emitted, only that the notifications that are emitted are in the correct order, it is possible to replace the queue implementation with one that:

• associates version indices with each new database state
• collapses consecutive notifications
• maintains a limited version history

Associated test failure

From Bamboo build #1140: StyxObjectStoreTest - Compute/Replace an existing value can result in the watcher being added early to the DB, and so receiving an unexpected early update which fails the test. This test should be re-assessed.

[mikkokar]

Issues

Out-of-order Notifications

Initial state notifications in particular are vulnerable to the out-of-order issue.

This is because normal change notification events are queued with a specific snapshot version. But initial watch notifications evaluate lazily, at event dispatch time, to the most recent database snapshot.

Consider the following event queue: [s4, s3, s2, iw, s1]

An initial watch event iw publishes version 4 because it is the most recent state at time of dispatch. But while the queue backlog is being processed, an earlier snapshot s3 is published shortly afterwards.

Watchers added too early

Watcher is added to the watchers list too early. As a result it might start receiving database change notifications before its initial watch notification.

Acceptance Criteria

A snapshot identifier

• Associate a unique identifier to each database snapshot.
• Is an integer (or long).
• Is strictly increasing, starting at zero, and increases by one for each new snapshot.
• A higher identifier implies more recent snapshot.

Notifications

• Change notifications are collapsed to the most recent snapshot.
• A following "queue invariant" holds true: the notification queue contains at most 1 notification change event.

Suppose a burst of database modifications, resulting queue backlog of: sn, .. , s7, s6], while snapshot 5 is being processed. Once the snapshot 5 has been emitted, the database can skip all intermediate snapshots s6, s7, ... and go straight to the most recent snapshot n. Therefore there is no need to store more than one watch notification.

• The change notifications and initial watch notifications must preserve their relative order.

An initial watch notification is sent to a new watch subscriber only. Therefore each initial watch notification should be queued as a separate event. The relative ordering among initial watch notifications, and among the database change event must be preserved.

• Initial watch notification should always emit the most recently published snapshot. This is to prevent the initial watch notification from being followed by a database change notification for an earlier snapshot.

[mikkokar]

Fixed by: #537