content/release-doc/3.0.0/release-notes/evseqnums.html - river-site - Git at Google

 <!--
  ! 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
  !
  !      http://www.apache.org/licenses/LICENSE-2.0
  !
  ! 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.
  !-->
 <!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">

 <html>
 <head>
   <title>Note on JavaSpaces Technology, Persistent Outrigger Services, and Event Sequence Numbers
   </title>
 </head>

 <body text="black" bgcolor="white" link="#9b37cc" vlink="#cc1877" alink="white">
 <center>
 <h1>Note on JavaSpaces Technology, Persistent Outrigger Services, and Event Sequence Numbers
 </h1>
 </center>
 <p>
 Previously the <i>JavaSpaces Service Specification</i> required that
 event sequence numbers associated with spaces events to be <em>fully
 ordered</em>.  Fully ordered, as defined in the <i>River Distributed
 Event Specification</i>, requires that:
 <blockquote>
 	... not only do sequence numbers increase, but they are not
 	skipped. In such a case, if <code>RemoteEvent</code> <I>x</I>
 	and <I>y</I> have the same source and the same event
 	identifier, and <I>x</I> has sequence number <I>m</I> and
 	<I>y</I> has sequence number <I>n</I>, then if <I>m</I> <
 	<I>n</I> there were exactly <I>n</I>-<I>m</I>-1 events of the
 	same event type between the event that triggered <I>x</I> and
 	the event that triggered <I>y</I>. Such sequence numbers are
 	said to be "fully ordered."

 </blockquote>
 <p>
 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 <i>JavaSpaces
 Service Specification</i> (GigaSpaces is a vender of a commercial JavaSpaces
 service implementation).  For example, the guarantee requires a persistent
 implementation to store sufficient information <em>during</em> each
 <code>write</code> so that after a crash it can know the event
 registrations matched by that <code>write</code>. This requirement
 places a significant restriction on what implementation strategies are
 practical.
 <p>
 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.
 <p>
 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 <i>JavaSpaces
 Service Specification</i> so that only the basic guarantee required by the
 <i>River Distributed Event Specification</i> 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
 <I>x</I> and <I>y</I> come from the same source and have the same event
 identifier, then <I>x</I> occurred before <I>y</I>, if and only if, the
 sequence number of <I>x</I> is less than the sequence number of <I>y</I>,
 but the difference between the two sequence numbers implies nothing about
 how many events may or may not have occurred between <I>x</I> and <I>y</I>.
 <p>
 A related issue is that previous editions of the <i>JavaSpaces Service
 Specification</i> specifically allowed implementations to "compress" event
 deliveries because sequence numbers were fully ordered. This rasises the
 questions &#151; 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 <i>JavaSpaces Service
 Specification</i>.

 <h2>What This Means for Persistent Outrigger Services</h2>

 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.
 <p>
 In the 1.2 beta release, Outrigger was changed to be
 <em>delta-well-ordered</em>.  With delta-well-ordered sequence
 numbers, if two remote events <I>x</I> and <I>y</I> with the same type and
 source have sequence numbers that differ by less than some delta <I>D</I>
 (typically a large number), then the number of intervening values between
 the sequence numbers of <I>x</I> and <I>y</I> would be equal to the number
 of intervening events.  If the difference is larger than <I>D</I>, then no
 inference about the number of intervening events could be made.
 <p>
 More formally, the characterization is:
 <blockquote>

     Let <I>e</I>(<I>n</I>) and <I>e</I>(<I>m</I>) be notifications of
     an event of type <I>e</I> from the same event generator with
     sequence numbers <I>n</I> and <I>m</I>, and let <I>D</I> be some
     integer. If |<I>n</I> - <I>m</I>| < <I>D</I>, then the number of
     events that occurred between the events that triggered
     notifications <I>e</I>(<I>n</I>) and <I>e</I>(<I>m</I>) is
     |<I>n</I> - <I>m</I>| - 1.

 </blockquote>
 <p>
 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
 <I>D</I>.
 <p>

 In Outrigger, we insert a delta only after the server comes up from a
 crash (Reggie uses a similar implementation strategy).
 <p>

 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.

 <p>

 <hr>
 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
 <ul>
      <a href="http://www.apache.org/licenses/LICENSE-2.0">http://www.apache.org/licenses/LICENSE-2.0</a>
 </ul>
 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.

 </body>
 </html>
	<!--
	! 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
	!
	! http://www.apache.org/licenses/LICENSE-2.0
	!
	! 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.
	!-->
	<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">

	<html>
	<head>
	<title>Note on JavaSpaces Technology, Persistent Outrigger Services, and Event Sequence Numbers
	</title>
	</head>

	<body text="black" bgcolor="white" link="#9b37cc" vlink="#cc1877" alink="white">
	<center>
	<h1>Note on JavaSpaces Technology, Persistent Outrigger Services, and Event Sequence Numbers
	</h1>
	</center>
	<p>
	Previously the <i>JavaSpaces Service Specification</i> required that
	event sequence numbers associated with spaces events to be <em>fully
	ordered</em>. Fully ordered, as defined in the <i>River Distributed
	Event Specification</i>, requires that:
	<blockquote>
	... not only do sequence numbers increase, but they are not
	skipped. In such a case, if <code>RemoteEvent</code> <I>x</I>
	and <I>y</I> have the same source and the same event
	identifier, and <I>x</I> has sequence number <I>m</I> and
	<I>y</I> has sequence number <I>n</I>, then if <I>m</I> <
	<I>n</I> there were exactly <I>n</I>-<I>m</I>-1 events of the
	same event type between the event that triggered <I>x</I> and
	the event that triggered <I>y</I>. Such sequence numbers are
	said to be "fully ordered."

	</blockquote>
	<p>
	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 <i>JavaSpaces
	Service Specification</i> (GigaSpaces is a vender of a commercial JavaSpaces
	service implementation). For example, the guarantee requires a persistent
	implementation to store sufficient information <em>during</em> each
	<code>write</code> so that after a crash it can know the event
	registrations matched by that <code>write</code>. This requirement
	places a significant restriction on what implementation strategies are
	practical.
	<p>
	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.
	<p>
	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 <i>JavaSpaces
	Service Specification</i> so that only the basic guarantee required by the
	<i>River Distributed Event Specification</i> 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
	<I>x</I> and <I>y</I> come from the same source and have the same event
	identifier, then <I>x</I> occurred before <I>y</I>, if and only if, the
	sequence number of <I>x</I> is less than the sequence number of <I>y</I>,
	but the difference between the two sequence numbers implies nothing about
	how many events may or may not have occurred between <I>x</I> and <I>y</I>.
	<p>
	A related issue is that previous editions of the <i>JavaSpaces Service
	Specification</i> 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 <i>JavaSpaces Service
	Specification</i>.

	<h2>What This Means for Persistent Outrigger Services</h2>

	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.
	<p>
	In the 1.2 beta release, Outrigger was changed to be
	<em>delta-well-ordered</em>. With delta-well-ordered sequence
	numbers, if two remote events <I>x</I> and <I>y</I> with the same type and
	source have sequence numbers that differ by less than some delta <I>D</I>
	(typically a large number), then the number of intervening values between
	the sequence numbers of <I>x</I> and <I>y</I> would be equal to the number
	of intervening events. If the difference is larger than <I>D</I>, then no
	inference about the number of intervening events could be made.
	<p>
	More formally, the characterization is:
	<blockquote>

	Let <I>e</I>(<I>n</I>) and <I>e</I>(<I>m</I>) be notifications of
	an event of type <I>e</I> from the same event generator with
	sequence numbers <I>n</I> and <I>m</I>, and let <I>D</I> be some
	integer. If \|<I>n</I> - <I>m</I>\| < <I>D</I>, then the number of
	events that occurred between the events that triggered
	notifications <I>e</I>(<I>n</I>) and <I>e</I>(<I>m</I>) is
	\|<I>n</I> - <I>m</I>\| - 1.

	</blockquote>
	<p>
	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
	<I>D</I>.
	<p>

	In Outrigger, we insert a delta only after the server comes up from a
	crash (Reggie uses a similar implementation strategy).
	<p>

	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.

	<p>

	<hr>
	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
	<ul>
	<a href="http://www.apache.org/licenses/LICENSE-2.0">http://www.apache.org/licenses/LICENSE-2.0</a>
	</ul>
	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.

	</body>
	</html>