/** Instance Repository
Synopsis
Describes the algorithms and architecture of the instances repository
(that part of the repository which deals with instances).
Layout
All files belonging to the instance repository are stored under the
repository/instances directory. For each class, two files are maintained:
an index file (with a ".idx" extension) and an instance file which bears
the name of the class whose instances it contains. For example, suppose
there is a class called "Zebra". Then two files are used to manage its
instances:
repository/instances/Zebra.idx (called the index file)
repository/instances/Zebra (called the instance file)
The first line of the index file indicates how many instances have been
modified or deleted since the last reorganization of the instance file.
When this number--called a dirty count--reaches a configurable limit, the
index file and instance file are reorganized to reclaim unused space;
unused space (or gaps) is left by delete and modify operations (discussed
later). The dirty count is expressed as eight hex digits (the number had to
have a fixed size so that it could be updated in place without having to
rewrite the index file).
Each subsequent line of the index file corresponds to an instance contained
in the instance file. Each line has the following fields:
-
deleted-flag - '1' if the corresponding instance was deleted, '0' otherwise.
When instances are deleted, the corresponding entry in the index file
is marked as deleted and a gap is left in the instance file until
reorganization time.
-
hash-code - hash code for the key field below. This field is provided to
speed lookup of index entries. When looking up an entry, compute the
hash code of the key and look for entries with the same hash code.
It is still necessary to compare the keys when the hash codes are
the same (since collisions are possible), but only when they are the
same which is rare and hence this scheme saves many comparisons.
-
offset - offset within the instance file to where the instance begins.
-
size - size in bytes of the instance itself (as it appears in the instance
file).
-
key - the compound key of the instance (including all key binding pairs).
This key is in standard form which we define as follows: all property
names are shifted to lower case and the key-bindings are sorted by
property names (in this way it suffices to compare key expressions to
determine if two compound keys refer to the same instance).
Here is a sample index file:
00000002
0 02FB6B6C 0 1427 Y.key1=1001,key2="Hello World 1"
0 50699A66 1427 1433 Y.key1=1002,key2="Hello World 2"
1 EB45F85A 2860 1433 Y.key1=1004,key2="Hello World 4"
1 38B42754 4293 1431 Y.key1=1005,key2="Hello World 5"
0 F79B5B0A 8583 1427 Y.key1=1666,key2="Hello World N"
0 38B42754 4293 1431 Y.key1=1005,key2="Hello World 5"
Notice that the dirty count is equal to two and that two entries are marked
as deleted (these quantities must be equal). This indicates that the instance
file has two instances which are no longer used. The space used by these
instances will be reclaimed during reorganization.
The layout of the instance file is trivial. Instances are always appended to
the the instance file. The instances are kept end-to-end in the file.
Operations
There are three operations which may be performed on the instance repository.
create, modify, and delete. This section describes how these operations affect
the index and instance file. Note that the process described below for
performing the three operations actually contains extra steps described in
the "Recovery" section.
Creation. During creation, the instance is appended to the instance file and
an entry is appended to the index file. If an instance with the same key is
found, then the operation is disallowed.
Deletion. To delete an instance, the corresponding entry in the index file is
marked as deleted (by changing the first column from '0' to '1'). And then the
dirty count is incremented and updated. If the dirty count has reached the
configured threshold, the index and instance files are reogranized (see
the section entitled "Reorganization" for an explanation of how this is
done).
Modification. To modify an instance, the new modified instance is appended to
the instance file. Next the old entry with the same key is marked as deleted.
Finally, a new entry is inserted into the index file.
Reorganization
To improve performance, reclamation of unused space in the instance file
(called gaps) is postponed until there are m gaps. Deletion and modification
operations create gaps. A dirty-count is maintained in the index file as
described above. When this dirty count reaches m, available space is reclaimed.
Reorganization is expensive: the entire file must be rewritten. The time
complexity is O(n) where n is the number of instances in the file. By
postponing reorganization, the time complexity may be reduced to O(1).
Reorganization requires rewriting the instance file and the index file. All
gaps are deleted in the instance file. For each gap there is an entry in the
index file which is marked as deleted. This entry indicates where the gap
starts in the instance file and how long it is. The offsets in the index file
are adjusted accordingly. The index file is also updated: all entries marked
as deleted are removed from the index file.
Recovery
To avoid corruption of the instance repository, a simple recovery scheme is
provided. For all operations (described in the Operations section), the
following algorithm is used to ensure recoverability.
- Check to see if any rollback files exist for instances of the given
class. If so then perform rollback (see recoverability algorithm
for details).
- Create a rollback file for the instance file. The rollback file
contains the original size of the instance file.
- Create a rollback file for the index file. The rollback file is a
copy of the instance file (this can be optimized later).
- Modify the instance file as described in the operations section.
- Modify the index file as described in the operations section.
- Perform reorganization as described in the reorganization section
if the dirty-count has reached the threshold. Otherwise, increment
the dirty count.
- Delete the rollback files.
The recoverability algorithm itself works as follows:
- Delete the index file.
- Rename the index rollback file to have the same name as the
index file.
- Truncate the instance file to have the same number of bytes as
indicated in the instance rollback file.
- Delete the rollback files.
*/