[mythtv-users] Mooting architecture for a DataDirect replacement

[Peter Schachte]

Jay R. Ashworth wrote:
> On Sun, Jun 24, 2007 at 03:31:22PM +1000, Peter Schachte wrote:
>>> Date-Posted:
>>>
>>> If they come in out of order, you can remember when the latest update
>>> applied was posted and ignore the older one.
>> That only works if the second posting comes in before you apply the first; in
>> general I expect you'd apply updates as soon as they arrive.  So you'd know
>> when updates arrived out of order, but you wouldn't be able to fix it.  The
>> best you could do is apply them out of order and hope there wasn't a conflict.
> 
> I think we're talking across one another.
> 
> If two updates come out that happen at different times, you're either
> going to apply the second one second, because it has a later
> Date-posted, or you're going to get the first one second, and ignore it
> because it has an *earlier* date posted.
> 
> Perhaps I should have more clearly named the header: it's the UTC
> timestamp at which the update packet was created.

No, I got that.  The real question is what an "update" is.  If an update is a
whole listing for a single program, then you're right.  Otherwise, if an update
is allowed to change parts of a listing for a program and not mention the parts
it leaves unchanged, or to replace two or more programs but leave others
unchanged, then the problem I'm describing can happen.  Here's a scenerio:  the
current listing for a program has title T, description D, start time S, end time E.

Update 1:  changes title to T1 and description to D1, and end time to E1.
update 2:  changes title to T2 and start time to S2.

Applied correctly, you wind up with title T2, description D1, start time S2,
end time E1.  If update 2 arrives first and you apply it, you have title T2,
description D, start time S2, end time E.  If update 1 now arrives and you
apply it, you get title T1, description D1, start time S2, end time E1, which
is wrong.  If you ignore it, you get title T2, description D, start time S2,
end time E, which is also wrong.  Either way you lose.

To get the right result you have to go back to the original state, and apply
the updates in order.  That means keeping track of a lot of back state.  I
think Rod suggested this earlier.  He also suggested having each update list
the updates that must be applied before it can be applied.  This avoids the
need to keep back state, but does require accumulating (and not applying)
updates until all the prerequisite updates arrive, so it requires storing an
unbounded number of forward updates.  I think a better approach would be to
compute a back-difference every time an update is made.  Ie, when applying an
update, also compute and push onto a stack the update that would have to be
applied to undo that update.  Then when a missing update arrives, pop the
back-diffs off the stack and apply them until you get back to the state when
the missing update should have been applied, then apply it and reapply the
intervening diffs.  That way you only store back-diffs, and the current
schedule is always as up-to-date as possible.  (Again, look at the patch
technology behind darcs.)  The other solution is for each update to contain all
of exactly one program, plus a time stamp.  When it arrives, apply it if and
only if the timestamp for that time slot in the current schedule is older than
the timestamp for the udpate.  That's probably the simplest netnews-based
solution that would work, though it still does nothing about the problem of
updates that *never* arrive.

-- 
Peter Schachte              I worry that 10 or 15 years from now, [my child]
schachte at cs.mu.OZ.AU        will come to me and say 'Daddy, where were you
www.cs.mu.oz.au/~schachte/  when they took freedom of the press away from
Phone: +61 3 8344 1338      the Internet?' -- Mike Godwin