Date: Fri, 28 Aug 1998 18:35:31 +0200
From: John Walker 
To: Greg Nelson 
CC: rdnelson 
Subject: Proposed Revisions to Egg and Basket Software


Introduction
------------

The following is a description, in design specification form,
of the changes I suggest making to the egg and basket
software.  The discussion of each of these changes describes
the rationale for making it.  Many of the decisions are
entirely arbitrary--I've simply tried to pick choices which
seemed reasonable to me.  Although this reads as a finished
design, everything is up for discussion and change--it's just
easier to present, and digest, a proposal without a lot of
conditionals and subjunctives.

I'll revise this as we agree on changes so that before I
start actually modifying the code, we'll be absolutely
certain how the next revision will behave.

I do not discuss the multiple REG driver code, as that's
already in the development version and didn't seem to
stimulate much discussion.

Egg Directory and File Name Structure
-------------------------------------

The egg will, by default, store packets containing samples
in directories named based on the year and month in which
the samples were taken.  Files within the directory will be
named based on the year, month, day, and egg number.  For
example, samples collected on September 18, 1998 by egg
2523 will be found in the file:

    1998-09/1998-09-18-002523

Making the egg data files fully qualified by date and
egg number permits aggregating them in a common directory
without having files delete one another.  The names sort
in ascending order of date, and by egg number within a
day.  Up to 999999 unique egg numbers are allowed
(is this enough?).  The format can be overridden by a format
specification in the DATAFMT environment variable.  This
will be a strftime() format string with the extension that
a "%E" phrase (not used by strftime) inserts the egg
number, right justified and zero filled to the chosen
number of places.

Since the egg number is included in the file name, any number
of eggs can run on the same machine and collect their data in
a common directory, if desired.  Once the egg is modified to
not run CPU bound (see below), it will be possible to do such
things as running multiple, perhaps different REGs on a single
machine, or to run a hardware REG and a pseudorandom generator
on the same machine as a control.

I do not envision having the egg delete these data files;
they will simply accumulate over time.  Systems with
limited disc space can easily clean them up with a
cron job which discards files in the egg data directory
tree older, say, than five days, or whatever seems
appropriate based on the egg/basket connectivity.

Basket Directory and File Name Structure
----------------------------------------

Basket data is stored, by default, in directories named by
the year and month, in files named from the date the packets
were collected by the egg (*not the date the basket received
them*) and the name of the basket.  For example, samples
received by basket noosphere on September 18, 1998 will
be stored in:

    1998-08/1998-09-18-noosphere

These names allow collecting data from multiple eggs and
baskets into common directories without having one file delete
another, and permit storing egg and basket data in a
common directory, if desired (though I wouldn't anticipate
doing this, in practice).  The format may be overridden with
a DATAFMT variable as for the egg, except that thr %E
phrase inserts the basket name rather than the egg number.

Splitting Eggsh into Two Programs
---------------------------------

The existing version of eggsh combines the code which samples
the REG with that which talks to the network.  This can lead to
imprecision in sampling time and dropped packets due to loss of
time alignment (see below for proposed changes in this
area) in the case where satisfying network requests takes
longer than the interval between samples.  With the existing
storage.c, this will happen as the basket's data file grows
over a month, since storage.c has to read through all the
packets to find the first one after the time requested by
the basket.  Changing the egg data files from monthly to daily
will help greatly, but there's still the possibility of
delaying a sample, particularly when a basket contacts an
egg after a long period in which the basket was down (or
a dial-and-drop egg was off the network), since that results
in a flurry of data requests.

I propose the following changes to address these problems.
First of all, eggsh will be split up into two separate
programs, "eggsample" and "eggnet" which can be started, if
we wish, from a shell script named eggsh.  Eggsample is
responsible for reading samples from the REG at the
designated sampling interval and appending them to an
egg data file named as described above.  When compiled without
debug settings, the program will be entirely "headless"--it
will generate no output other than the egg data file.
At the start of each new day, it will begin logging in
a new file named for that day.  Eggsample will keep the
egg data file open and append records to it with unbuffered
writes, using fsync() to make sure the data are committed
to disc.  Eggsample, if run by the super user, will be able
to run at an elevated priority (for example, nice(-10), which
dramatically improves the precision of sampling time since
it will preempt other user-level tasks which might be in
control when the time for a sample occurs.

Eggsample reads its protocol specifications from a new
.eggprotocolrc file.  If this file does not exist, eggsample
creates one containing the protocol specified in the
.eggrc file.  If eggsample receives a SIGHUP signal, it
re-reads the .eggprotocolrc file and, if the protocol
has changed, begins to use the new protocol starting
with the next packet.  Eggsample logs its process ID
in the file eggsample.pid.

Eggnet is responsible for talking to one or more baskets.
Upon receiving a request from a basket, it scans egg data
files based on the date and time requested by the basket
and returns the first packet satisfying the basket request.
For each basket which has contacted eggnet, an in-memory
table is kept giving the:

    Time and date of last request from basket
    Open file handle of file containing last packet sent to basket.

If the next request from the basket consists of the next
packet, in time, after the last requested, eggnet simply
reads the next packet from the open file.  If it matches
the request it is returned to the basket and the last request
cell in memory is updated.  If a basket requests data and
none is present in the existing open file, and the current
date is later than the date of the last request, eggnet
tries to open a data file for the next day and see if it
contains a packet satisfying the basket's request.

This means that in the normal course of affairs, eggsample
and eggnet will only open and close one file per day, and
following the first request from a basket, eggnet will
be able to read sequential packets from the end of the
basket data file without any additional I/O or seeking.
Since the test for the optimisation in eggnet will be
precise, any funny business (for example, a basket which has
been restored from backup and requests a packet earlier
than its previous request) will default to the general
open-and-search code and will perform precisely as
it does today.

Eggsample reads the current protocol for the egg from
the .eggprotocolrc file.  If eggsample receives a protocol
packet from the basket which differs from the current protocol,
it writes the new values into .eggprotocolrc and sends a
SIGHUP to eggsample, using the process ID in eggsample.pid.

If the egg user interface is configured, it is updated
by eggsample on a periodic basis, by examining the last
packet in the egg data file.

Non-CPU Bound Sampling
----------------------

The existing egg sampling software uses a CPU loop to time
align samples as precisely as possible at the start of each
second.  This produces very accurate timing on a dedicated
machine, but if the machine is used for other tasks (as
innocent as an automated backup client program), can actually
lead to imprecision in sampling time.  In addition, it makes
the machine less responsive to users if it is non-dedicated.
Dedicated egg machines are obviously best, but we'll probably
be able to persuade more people to run eggs if that is not
an absolute requirement.  How can the CPU loop hurt precision?
Because Unix schedules tasks in such a way that CPU-bound
programs get longer slices of time by default, but at a lower
scheduling priority than highly-interactive tasks or those
doing lots of I/O.  This is why Unix performs so well while
running compute bound jobs in the background.  If the egg is
compute bound, however, this means that virtually any other
task can preempt it.  Even a dedicated Unix box will usually
have some cron jobs, network plumbing tasks (DNS transfers,
etc.), and if these happen to need the CPU at the top of
a second, they'll bump the egg, possibly leading to loss
of an entire ten second period (but see below for proposed
changes in this area).

I have been experimenting with an alternative synchronisation
technique to essentially eliminate the CPU burden of running
an egg while delivering synchronisation as good or better
than before.  A test jig for the technique can be found in

    noosphere:/home/john/egg/synchromesh

The trick is as follows.  First of all, if at all possible,
run the program as super-user, which permits it to raise its
priority higher than regular user programs (but not so high
as to preempt operating system services).  This gives it
much greater probability of receiving control when it wants
to, regardless of what other user tasks are active.  When
the first sample is taken, a CPU loop is used to align to
the top of the second as at present.  After taking that sample,
a delay is computed so as to reschedule the task 50 milliseconds
before the start of the next second, *taking into account the
latency of the last sample time*.  This delay is then used to
set an interval timer with setitimer() and the process goes to
sleep until the alarm goes off.

I have tested this on noosphere, while the compute bound egg
is running on it, on my Silicon Graphics development machine, and
on Suns ranging from the 8 year old SPARC 2 to the 300 MHz
Ultra 2, while running other jobs, hammering on the disc and
CPU with Netscape mail retrieval from large folders, etc.,
and in most cases synchronisation is to the order of a few
microseconds (the SGI has a clock with this resolution--on
the other machines you have to take into account clock
granularity).  Rarely, even under heavy load, do I see
mis-synchronisation greater than 10 milliseconds.

I propose eggsample adopt this synchronisation technique.  As
in the synchromesh program, a status display will be available
in debug builds to monitor the accuracy of synchronisation.

Packet Time Alignment and Missed Sample Changes
-----------------------------------------------

At present, packets are time-aligned on 10 second
boundaries.  If the first sample of a packet is collected
at a non-even 10 second interval, the entire 10 second
packet is lost.  Packets collected for the basket can
thus represent differing periods of time.

I propose the following change.  Each packet stored by the
egg represents (using the default protocol settings--the
packet will change according to the protocol) one minute
of data, stored in six records each representing a 10
second interval.  The first record in a packet will always
be the first 10 second interval in the minute, thus
packets will be time-aligned on even minutes, and in no
case will a packet contain data for more than one day.

When a new packet is initialised, the 10 second time
intervals within the minute are filled in and all data
fields in each record are set to 255, representing missing
data--as long as the number of trials per sample is less than
or equal to 254 this is completely unambiguous.  When a
sample is collected, is is stored in the data field of
the appropriate record according to *when it was actually
collected*.  Thus delays which cause mis-synchronisation
will never lead to a sample's being filed as belonging to
a second other than that in which it was actually collected.

When a sample is collected at a time later than the last slot
in a data packet, a new packet is created to store it, and the
previous packet is appended to the egg data file.

Analysis software needs only to know that samples of 255
represent missing data; the existing analysis software which
uses eggtable.c already uses 255 as a missing data marker
(for seconds in which one or more eggs did not provide a
sample) and should need no (or, at the worst, very minor)
modifications to accept egg data in this form.
Analysis software is simplified by knowing that a packet
never contains data for more than one day and that,
conversely, all the data received (so far) for a given date
is stored in the basket data file named for that day.
Finally, since (assuming the protocol is known and
uniform for all data in a basket data file) all packets are
of uniform length, the egg and basket data files can be
random accessed or read in reverse order, although there
is no current need to do this.A number of points raised here
were discussed further in a followup exchange with Greg and Roger.
As the notes show, John't approach is clear and organized.
The same characteristics show also in this picture of a part
of his physical setup. This is the "Swiss Solaris Egg"
contributing data to the GCP. The source is a PEAR REG,
which can be seen on the table just to the right of the monitor.