Note on JavaSpaces Technology, Persistent Outrigger Services, and Event Sequence Numbers

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.

What This Means for Persistent Outrigger Services

As alluded to above, the persistent version of Outrigger did not generate fully ordered sequence numbers in all cases; indeed, in these cases it did not even meet the basic guarantee because it sometimes assigned the same sequence number to different events. What was especially troubling is that, in these cases, the client had no way of detecting that the same sequence number had been assigned to more than one event.

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.


Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file distributed with this work for additional information regarding copyright ownership. The ASF licenses this file to you under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.