# Copryight (C) 2004  Joshua Hoblitt
#
# $Id: design.txt,v 1.1.1.1 2004-12-22 02:16:23 jhoblitt Exp $

Terminology
--
    - Storage Object
There is one Storage Object per resource (a file) that is being managed by the
IPP Pixel Data Server.  A Storage Object maps an External Identifier (eg.
file name) to a Storage ID that is internal to the IPP Pixel Data Server.  In
addition, creation time and comments may be stored in a Storage Object.
Storage Objects /do not/ contain the storage location of a resource as we need
to allow for N copies of a resource to be stored.  The actual storage location
of a resource is held in a Storage Object Instance, which maps to a Storage ID
in a many-to-one relationship.

    - [Storage Object] Instance
A Storage Object Instance, or just Instance, represents a single copy of a
resource being managed by the IPP Pixel Data Server. An Instance contains an
Instance ID, the location of the resource as a URI, a checksum of the
resource, a Storage ID, a read lock semaphore (unsigned integer), a write lock
mutex (enum( 'write', 'wait', 'free' ) - is this better then using an int and
constants?), and a UTC timestamp of the last modification date & time.

    - Lock Record
A Lock Record is used to double check the indicated lock state of an Instance
and can be used to identify system failures.  It must contain the Instance ID
of of the locked instance and the type of lock, eg, enum( 'read', 'write').

Locking semantics
--
A lock is required to either read from or write to a Storage Object Instance
being managed by the IPP Pixel Data Server.  Stated another way, locking
granularity is managed on the level of Storage Object Instances instead of on
the more abstract Storage Objects.  Although, from the client perspective,
operations are carried out on a Storage Object.   The locking state of a
Storage Object Instance is maintained by in the Storage Object Instance and a
Lock Record.

Two types of locks are used on an Instance, a semaphore is used to track read
locks and an exclusive mutex is for write locking.

    - Read lock
In order to read from a Storage Object Instance the Read Lock semaphore must
first be incremented by one and a Lock Record created.  After the read is
completed the Lock Record must be deleted and the Read Lock semaphore
decremented by one.  The incrementation of the Read Lock and Lock Record
creation or the decrementation of the Read Lock and the Lock Record deletion
must happen atomically.  A Read lock can not be aquired unless the Write mutex
is in the state of 'free'.  If a Read lock can not be aquired, a client must
not "spin lock" on the Instanace ID as it may be in the process of being
removed.  Instead, the "spin lock" should be re-resolving the external
identifier to a Storage ID, and the Storage ID to Storage Instances.

    - Write lock
In order to obtain a Write lock on a Storage Object Instance the Write Lock
mutex must be in the state of 'free' and the Read lock semaphore must have a
value of zero.  A client should either "spin lock" or fail if all the Lock
mutex is set or the Read Semaphore has a non-zero value.  A Lock Record must
be created atomically with the setting of the Write mutex.  The setting of the
Write mutex and Lock Record insertion or the clearing of the Write mutex and
the Lock Record deletion must happen atomically.  If the Write lock has a
state of 'free' and the Read lock has a non-zero value, the Write lock may be
set to the 'wait' state to prevent new Read locks from being aquired.

Storage Object Operations
--
    - Add
The resource must already be on disk (having been named through some sort of
mechanism to generate new filenames).  A new Storage Object must be created with a new/unqiue  Storage ID and has
an associated with an External Identifier.  At least one Instance must be
created atomicaly at the same time.  Each new Instance must be initially created with a Write lock.
The resource may then be written to it's storage location.  When the writing
of the resource is completed the Write lock must be cleared as early as is
feasible.  The association of an External Identifier must wait until Instance
creation is completed

    - Delete
In order to remove a Storage Object, a Write lock must be obtained on
/all/ associated Instances.  Then the resources are removed.  As each resource
is deleted the corresponding Instance must be deleted.  After all Instances are
removed the Storage Object must then be deleted.

    - Update
Storage Object Instances are not truly written to.  Instead, a new set of
Storage Object Instances and a new Storage Object are created in parallel.

Write locks must be aquired on all the orignal Intances of a Storage Object.
Then an Add operation is performed to create a new Storage Object and
associated Instances.  Then the External Identifier must be atomically moved
from the original Storage Object to the new Storage Object.  After the
External Identifier migration, the original Storage Object and it's Instances
should be removed with a special case of the Delete operation (one that will
operate on already held locks).  If the old Storage Object is merely
abandoned, ie. it still exists but doesn't have an External Identifier, it and
the associated Instances will be removed during the next Consistency Sweep.
If a Delete is not peformed, the Write locks on the orignal Instances must be
released. [use a dead Storage Object table or flag, similar to mark and sweep
garbage collection?]

    - Move
This is the same operation as an Update except the new Instances are identical
to the old.

    - Open
Sets a Read lock on an Instances of a Storage Object and determines it's
storage location.  A Read lock must only be placed on one Instance of a
Storage Object.  All Instances of a Storage Object should be iterated through
in a "spin lock" until a Read lock is aquired.

    - Close
Releases a Read lock aquired with open.

The lock must be released as soon as is feasible.

Lock sweeping
--
In the event that a Storage Object operation fails to complete successfully
stale locks will have to be identified and removed from the IPP Pixel Data
Server Database.  This should be done periodically by comparing the entries
in the Lock table to the list of active nodes maintained by the IPP
Controller.  It should also happen as soon as possible after a node goes
offline (triggered by the IPP Controller marking a node as offline?).  A sweep
must be /completed/ before an offline node can be marked on-line.

Once a node is determined to be offline all entries in the Lock table set by
that node should be identified.   The locks on the Storage Object
Instances pointed to by those entries should then be rolled back and Lock
Record entries themselves must be removed from the lock table.

Consistency sweeping
--
Periodically the IPP Pixel Data Server meta-data and Storage Object will need
to be checked for sanity.  This would be similar to running fsck on a modern
filesystem.  Consistency sweeping should include Lock sweeping and should be
considered a superset.

All Storage Objects must have at least once associated Instance.

All Storage Object Instances must be associated with a Storage Object.

All Storage Object Instances with a lock set must have the correct number of
corresponding Lock Records.

All Lock Records must be plausible, ie. the Instance pointed at must be in a
corresponding state.

Storage ID Allocation
--
Storage IDs are a signed 64-bit integer.  Negative values are considered
reserved for future use.  Allocation should be incremental and, as we are
unlikely to exceed 2^63 Storage Objects in the life time of the project, never
reused.

Allocated via [SQL auto-increment/stored procedure/app server?]

Instance ID Allocation
--
Indentical to a Storage ID but exists in a unique namespace.

Storage Location determination
--
???
