1 mike  1.1 
  2           /** Provider-specific Repositories: Recommendations and Conventions
  3           
  4           <h1>Synopsis</h1>
  5           
  6               This document explains how a provider may have its own private repository.
  7               It also establishes conventions for doing so.
  8           
  9           <h1>Overview</h1>
 10           
 11               In certain circumstances providers may wish to manage their own private
 12               repository. This document recommends creating another instance of the
 13               CIMRepository class which refers to a distinct repository (other than the
 14               default CIMOM repsistory). This will allow the provider to create classes,
 15               instances, and qualifiers, which do not appear in the public CIMOM
 16               repository.
 17           
 18               There are a copule of cases in which provider-specific repositories are 
 19               needed:
 20           
 21           	<ul>
 22 mike  1.1 	<li>For storing provider-specific configuration information.</li>
 23           	<li>For temporarily storing CIM objects.</li>
 24           	</ul>
 25           
 26               Provider usage of repositories raises several questions:
 27           
 28           	<ul>
 29           	<li>Do these repositories need the default schema</li>
 30           	<li>Where will these repositories reside?</li>
 31           	<li>How will they be created?</li>
 32           	<li>How will these repositories be populated?</li>
 33           	<li>
 34           	</ul>
 35           
 36               
 37           
 38               
 39           
 40           All files belonging to the instance repository are stored under the
 41           repository/instances directory. For each class, two files are maintained:
 42           an index file (with a ".idx" extension) and an instance file which bears
 43 mike  1.1 the name of the class whose instances it contains. For example, suppose 
 44           there is a class called "Zebra". Then two files are used to manage its 
 45           instances:
 46           
 47               <pre>
 48               repository/instances/Zebra.idx (called the index file)
 49               repository/instances/Zebra (called the instance file)
 50               </pre>
 51           
 52           The first line of the index file indicates how many instances have been 
 53           modified or deleted since the last reorganization of the instance file.
 54           When this number--called a dirty count--reaches a configurable limit, the 
 55           index file and instance file are reorganized to reclaim unused space; 
 56           unused space (or gaps) is left by delete and modify operations (discussed 
 57           later). The dirty count is expressed as eight hex digits (the number had to 
 58           have a fixed size so that it could be updated in place without having to 
 59           rewrite the index file).
 60           
 61           Each subsequent line of the index file corresponds to an instance contained 
 62           in the instance file. Each line has the following fields:
 63           
 64 mike  1.1     <ul>
 65           
 66               <li>
 67               deleted-flag - '1' if the corresponding instance was deleted, '0' otherwise.
 68           	When instances are deleted, the corresponding entry in the index file
 69           	is marked as deleted and a gap is left in the instance file until
 70           	reorganization time.
 71               </li>
 72           
 73               <li>
 74               hash-code - hash code for the key field below. This field is provided to
 75           	speed lookup of index entries. When looking up an entry, compute the 
 76           	hash code of the key and look for entries with the same hash code.
 77           	It is still necessary to compare the keys when the hash codes are
 78           	the same (since collisions are possible), but only when they are the
 79           	same which is rare and hence this scheme saves many comparisons.
 80               </li>
 81           
 82               <li>
 83               offset - offset within the instance file to where the instance begins.
 84               </li>
 85 mike  1.1 
 86               <li>
 87               size - size in bytes of the instance itself (as it appears in the instance
 88           	file).
 89               </li>
 90           
 91               <li>
 92               key - the compound key of the instance (including all key binding pairs). 
 93           	This key is in standard form which we define as follows: all property 
 94           	names are shifted to lower case and the key-bindings are sorted by
 95           	property names (in this way it suffices to compare key expressions to
 96           	determine if two compound keys refer to the same instance).
 97               </li>
 98           
 99               </ul>
100           
101           Here is a sample index file:
102           
103               <pre>
104               00000002
105               0 02FB6B6C 0 1427 Y.key1=1001,key2="Hello World 1"
106 mike  1.1     0 50699A66 1427 1433 Y.key1=1002,key2="Hello World 2"
107               1 EB45F85A 2860 1433 Y.key1=1004,key2="Hello World 4"
108               1 38B42754 4293 1431 Y.key1=1005,key2="Hello World 5"
109               0 F79B5B0A 8583 1427 Y.key1=1666,key2="Hello World N"
110               0 38B42754 4293 1431 Y.key1=1005,key2="Hello World 5"
111               </pre>
112           
113           Notice that the dirty count is equal to two and that two entries are marked 
114           as deleted (these quantities must be equal). This indicates that the instance 
115           file has two instances which are no longer used. The space used by these 
116           instances will be reclaimed during reorganization.
117           
118           The layout of the instance file is trivial. Instances are always appended to
119           the the instance file. The instances are kept end-to-end in the file.
120           
121           <h1>Operations</h1>
122           
123           There are three operations which may be performed on the instance repository.
124           create, modify, and delete. This section describes how these operations affect 
125           the index and instance file. Note that the process described below for 
126           performing the three operations actually contains extra steps described in
127 mike  1.1 the "Recovery" section.
128           
129           Creation. During creation, the instance is appended to the instance file and
130           an entry is appended to the index file. If an instance with the same key is
131           found, then the operation is disallowed.
132           
133           Deletion. To delete an instance, the corresponding entry in the index file is 
134           marked as deleted (by changing the first column from '0' to '1'). And then the 
135           dirty count is incremented and updated. If the dirty count has reached the 
136           configured threshold, the index and instance files are reogranized (see
137           the section entitled "Reorganization" for an explanation of how this is 
138           done).
139           
140           Modification. To modify an instance, the new modified instance is appended to
141           the instance file. Next the old entry with the same key is marked as deleted.
142           Finally, a new entry is inserted into the index file.
143           
144           <h1>Reorganization</h1>
145           
146           To improve performance, reclamation of unused space in the instance file 
147           (called gaps) is postponed until there are m gaps. Deletion and modification
148 mike  1.1 operations create gaps. A dirty-count is maintained in the index file as
149           described above. When this dirty count reaches m, available space is reclaimed.
150           Reorganization is expensive: the entire file must be rewritten. The time
151           complexity is O(n) where n is the number of instances in the file. By 
152           postponing reorganization, the time complexity may be reduced to O(1).
153           
154           Reorganization requires rewriting the instance file and the index file. All
155           gaps are deleted in the instance file. For each gap there is an entry in the 
156           index file which is marked as deleted. This entry indicates where the gap 
157           starts in the instance file and how long it is. The offsets in the index file
158           are adjusted accordingly. The index file is also updated: all entries marked
159           as deleted are removed from the index file.
160           
161           <h1>Recovery</h1>
162           
163           To avoid corruption of the instance repository, a simple recovery scheme is
164           provided. For all operations (described in the Operations section), the 
165           following algorithm is used to ensure recoverability.
166           
167               <ul>
168           
169 mike  1.1     <li>Check to see if any rollback files exist for instances of the given
170           	class. If so then perform rollback (see recoverability algorithm
171           	for details).
172               </li>
173           
174               <li>Create a rollback file for the instance file. The rollback file 
175           	contains the original size of the instance file.
176               </li>
177           
178               <li>Create a rollback file for the index file. The rollback file is a
179           	copy of the instance file (this can be optimized later).
180               </li>
181           
182               <li>Modify the instance file as described in the operations section.
183               </li>
184           
185               <li>Modify the index file as described in the operations section.
186               </li>
187           
188               <li>Perform reorganization as described in the reorganization section
189           	if the dirty-count has reached the threshold. Otherwise, increment
190 mike  1.1 	the dirty count.
191               </li>
192           
193               <li>Delete the rollback files.
194               </li>
195           
196               </ul>
197           
198           The recoverability algorithm itself works as follows:
199           
200               <ul>
201           
202               <li>Delete the index file.
203               </li>
204           
205               <li>Rename the index rollback file to have the same name as the
206           	index file.
207               </li>
208           
209               <li>Truncate the instance file to have the same number of bytes as
210           	indicated in the instance rollback file.
211 mike  1.1     </li>
212           
213               <li>Delete the rollback files.
214               </li>
215           
216               </ul>
217           
218           */