Previously the JavaSpaces Service Specification required that event sequence numbers associated with spaces events to be fully ordered. Fully ordered, as defined in the River Distributed Event Specification, requires that:
... not only do sequence numbers increase, but they are not
skipped. In such a case, if RemoteEvent x
and y have the same source and the same event
identifier, and x has sequence number m and
y has sequence number n, then if m <
n there were exactly n-m-1 events of the
same event type between the event that triggered x and
the event that triggered y. Such sequence numbers are
said to be "fully ordered."
In the Fall of 2000, we received feedback (from Asaf Kariv of GigaSpaces
Technologies Ltd.) stating that requiring event sequence numbers to be fully
ordered places too high a burden on implementors of the JavaSpaces
Service Specification (GigaSpaces is a vender of a commercial JavaSpaces
service implementation). For example, the guarantee requires a persistent
implementation to store sufficient information during each
write so that after a crash it can know the event
registrations matched by that write. This requirement
places a significant restriction on what implementation strategies are
practical.
An additional wrinkle was that at the time, the persistent version of Outrigger itself did not generate fully ordered event sequence numbers in all cases. While we believe we could have fixed this issue in the Outrigger codebase with minimal performance impact, serving only our own needs would not promote our goal of having JavaSpaces implementations from a number of vendors.
After substantial discussions within the River Community(SM) for more than a year, we came to the conclusion that weakening the fully ordered guarantee would be unlikely to have significant negative impact on users of JavaSpaces technology. As a result, in the 1.2 FCS release, we changed the JavaSpaces Service Specification so that only the basic guarantee required by the River Distributed Event Specification on event sequences numbers is called for. This basic guarantee requires that all sequence numbers are unique and ordered, but that gaps in the sequence do not necessarily imply that events have been missed. Put another way, if two remote events x and y come from the same source and have the same event identifier, then x occurred before y, if and only if, the sequence number of x is less than the sequence number of y, but the difference between the two sequence numbers implies nothing about how many events may or may not have occurred between x and y.
A related issue is that previous editions of the JavaSpaces Service Specification specifically allowed implementations to "compress" event deliveries because sequence numbers were fully ordered. This rasises the questions — is compression still allowed? and should we be calling it out in the specification? It was decided that the event specification does allow for event notifications to be dropped even when only the basic sequence number guarantee is present, and that it was not necessary to call this possibility out in the JavaSpaces Service Specification.
In the 1.2 beta release, Outrigger was changed to be delta-well-ordered. With delta-well-ordered sequence numbers, if two remote events x and y with the same type and source have sequence numbers that differ by less than some delta D (typically a large number), then the number of intervening values between the sequence numbers of x and y would be equal to the number of intervening events. If the difference is larger than D, then no inference about the number of intervening events could be made.
More formally, the characterization is:
Let e(n) and e(m) be notifications of an event of type e from the same event generator with sequence numbers n and m, and let D be some integer. If |n - m| < D, then the number of events that occurred between the events that triggered notifications e(n) and e(m) is |n - m| - 1.
The delta-well-ordered guarantee lets the implementation deliver a fully ordered guarantee where possible, but not where it becomes too burdensome. For example, a persistent implementation might be fully ordered in the usual case, incrementing the sequence number by one, but efficient during crash recovery by incrementing the sequence number by D.
In Outrigger, we insert a delta only after the server comes up from a crash (Reggie uses a similar implementation strategy).
Note that this will affect any existing code that assumes it can calculate the number of intervening events by subtracting sequence numbers. If your existing code is using persistent Outrigger across a crash, such code might be surprised to suddenly find that a few billion events seem to have transpired while it wasn't looking. The discussions within the River Community have yet to locate a critical dependency of this form, but one is possible.