Return to instances.txt CVS log | Up to [Pegasus] / pegasus / src / Pegasus / Repository |
File: [Pegasus] / pegasus / src / Pegasus / Repository / Attic / instances.txt
(download)
Revision: 1.4, Fri Oct 24 16:48:54 2008 UTC (15 years, 8 months ago) by kumpf Branch: MAIN CVS Tags: TASK-PEP362_RestfulService-merged_out_from_trunk, TASK-PEP348_SCMO-merged_out_from_trunk, TASK-PEP317_pullop-merged_out_from_trunk, TASK-PEP317_pullop-merged_in_to_trunk, HPUX_TEST, HEAD Changes since 1.3: +0 -0 lines FILE REMOVED BUG#: 8036 TITLE: Instance repository documentation should be kept with code DESCRIPTION: Move documentation from independent text files to code comments. |
/** Instance Repository <h1>Synopsis</h1> Describes the algorithms and architecture of the instances repository (that part of the repository which deals with instances). <h1>Layout</h1> 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: <pre> repository/instances/Zebra.idx (called the index file) repository/instances/Zebra (called the instance file) </pre> 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: <ul> <li> 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. </li> <li> 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. </li> <li> offset - offset within the instance file to where the instance begins. </li> <li> size - size in bytes of the instance itself (as it appears in the instance file). </li> <li> 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). </li> </ul> Here is a sample index file: <pre> 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" </pre> 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. <h1>Operations</h1> 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. <h1>Reorganization</h1> 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. <h1>Recovery</h1> 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. <ul> <li>Check to see if any rollback files exist for instances of the given class. If so then perform rollback (see recoverability algorithm for details). </li> <li>Create a rollback file for the instance file. The rollback file contains the original size of the instance file. </li> <li>Create a rollback file for the index file. The rollback file is a copy of the instance file (this can be optimized later). </li> <li>Modify the instance file as described in the operations section. </li> <li>Modify the index file as described in the operations section. </li> <li>Perform reorganization as described in the reorganization section if the dirty-count has reached the threshold. Otherwise, increment the dirty count. </li> <li>Delete the rollback files. </li> </ul> The recoverability algorithm itself works as follows: <ul> <li>Delete the index file. </li> <li>Rename the index rollback file to have the same name as the index file. </li> <li>Truncate the instance file to have the same number of bytes as indicated in the instance rollback file. </li> <li>Delete the rollback files. </li> </ul> */
No CVS admin address has been configured |
Powered by ViewCVS 0.9.2 |