cocoon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael Melhem <>
Subject Re: Expire Continuations
Date Tue, 03 Dec 2002 13:15:43 GMT
On Mon, Dec 02, 2002 at 10:38:33PM -0800, Ovidiu Predescu wrote:
> Hi Michael,
> OK, I'm back from a longer absence due to the Thanksgiving vacation.

Cool, I hope you didnt think about cocoon too much during your vaction!!

> On Thursday, Nov 28, 2002, at 10:28 US/Pacific, Michael Melhem wrote:
> >Hi Ovidiu!!
> >
> >How are you mate, I guess you are not coming to the Frankfurt
> >Stammtisch???? :-P
> Wait a second, I want to come! ;)

Dont worry, we wont start eating until you arrive ;)

> >I was thinking about how to Expire Continuations and have come up with
> >the following:
> >
> >We know from the "bus discussion" that placing every wk 
> >(WebContinuation)
> >into the "expirations" Sorted TreeSet is a problematic solution. So how
> >about placing only the "leaf" nodes in this set for each tree?
> The bus discussion should be placed in the references section of the 
> documentation and in the comments in the source code ;)

Hmmm... I think the next Cocoon getTogether should be held in a "bus",
because its seems thats where we had our most productive
conversations! :-P

> >This can be done by:
> >    for each new wk
> >    	(if wk.getparent().numChildren() < 2)
> >		expirations.remove(wk.getparent());
> >	expirations.add(wk);
> >
> >This could be an expensive operation especially if the set of wk's is
> >very large .... although.. the treeSet guarantees log(n) time cost for
> >basic operations. What do you think ?
> >
> >Given that we have a sorted set of "leaf" nodes (from all continuation
> >trees) we need to excute the following algorithm to rid the
> >system of expired wk's
> >
> >	For each leaf node in the set which is expired:
> >		delete it, and
> >		recursively delete its parent
> >		only if its parent has also expired
> >		*and* has no (other) children.
> >
> >We could make the ContinuationsManager an avlaon monitored Resource,
> >so that we can periodically trigger continuations clean ups.
> >
> >	This implies the max life of an "wk" after lastAcceesTime
> >	equals timeToLive + cleanUp_period.
> >
> >
> >What do you think??
> I think the TreeSet is definitely the way to go, as it is a sorted 
> collection and accesses and removals from it are very fast.

Yes, I agree that the Sorted TreeSet is a good idea.

> One observation related to your algorithm, which is an idea I had when 
> we got off The Bus, is that we don't need to handle children 
> continuations of a given continuation. This is because each and every 
> continuation will appear in the sorted tree, and we can expire 
> individual continuations separate from their children. 

Expiring individual continuations separate from their children would be 
the simplest and most efficient algorithm. However this would result in
holes being punched in the countinuatioons tree(s).

  o                 o                   
  |                 |                   
  o                 o                   o
   \   becomes     / \    becomes      / 
    o             o   o               o   
    |                 |                   
    o                 o                   o

This is not necessarily problematic in itself but we need decide
whether a subtree or an individual continuation should be considered

I would lean towards the notion of "atomic subtrees". By that I mean, 
we either set the whole subtree as expired (and deleted) or the whole 
the subtree as not-expired (and available). 

Otherwise, a user traversing backwards from a a vaild
continuation might be suprised that the parent continuation is no longer
there, especially if you consider that these continuations are part of the
same flow function. Does it make sense to only have half a flow function

> The expiration algorithm will then simply iterate over the tree set 
> until a continuation whose access time + expiration time is greater 
> than the current time. All the continuations encountered before that 
> are simply removed from the global hash set.

Yes, I think we agree on this. This is independent of how we derive the
expirations set.

> What do you think?

The algorithm I suggested would treat continuation subtrees as "atomic"
and maintain valid trees. The only question is whether this is worth the
slight performance hit??? What do you think?

Michael Melhem

> Ovidiu
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, email:

To unsubscribe, e-mail:
For additional commands, email:

View raw message