KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > store > raw > data > ReclaimSpaceHelper


1 /*
2
3    Derby - Class org.apache.derby.impl.store.raw.data.ReclaimSpaceHelper
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.store.raw.data;
23
24 import org.apache.derby.impl.store.raw.data.BasePage;
25 import org.apache.derby.impl.store.raw.data.ReclaimSpace;
26
27
28 import org.apache.derby.iapi.services.daemon.DaemonService;
29 import org.apache.derby.iapi.services.daemon.Serviceable;
30 import org.apache.derby.iapi.services.sanity.SanityManager;
31 import org.apache.derby.iapi.error.StandardException;
32
33 import org.apache.derby.iapi.store.access.TransactionController;
34
35 import org.apache.derby.iapi.store.raw.ContainerKey;
36 import org.apache.derby.iapi.store.raw.ContainerHandle;
37 import org.apache.derby.iapi.store.raw.LockingPolicy;
38 import org.apache.derby.iapi.store.raw.Page;
39 import org.apache.derby.iapi.store.raw.PageKey;
40 import org.apache.derby.iapi.store.raw.RecordHandle;
41 import org.apache.derby.iapi.store.raw.Transaction;
42
43 import org.apache.derby.iapi.store.raw.xact.RawTransaction;
44 import org.apache.derby.iapi.store.raw.data.RawContainerHandle;
45
46
47 /**
48     This class helps a BaseDataFactory reclaims unused space.
49
50 Space needs to be reclaimed in the following cases:
51 <BR><NL>
52 <LI> Row with long columns or overflow row pieces is deleted
53 <LI> Insertion of a row that has long columns or overflows to other row pieces is rolled back
54 <LI> Row is updated and the head row or some row pieces shrunk
55 <LI> Row is updated and some long columns are orphaned because they are updated
56 <LI> Row is updated and some long columns are created but the update rolled back
57 <LI> Row is updated and some new row pieces are created but the update rolled back
58 </NL> <P>
59
60 We can implement a lot of optimization if we know that btree does not overflow.
61 However, since that is not the case and Raw Store cannot tell if it is dealing
62 with a btree page or a heap page, they all have to be treated gingerly. E.g.,
63 in heap page, once a head row is deleted (via a delete operation or via a
64 rollback of insert), all the long rows and long columns can be reclaimed - in
65 fact, most of the head row can be removed and reclaimed, only a row stub needs
66 to remain for locking purposes. But in the btree, a deleted row still needs to
67 contain the key values so it cannot be cleaned up until the row is purged.
68
69 <P><B>
70 Row with long columns or long row is deleted
71 </B><BR>
72
73 When Access purge a committed deleted row, the purge operation will see if the
74 row has overflowed row pieces or if it has long columns. If it has, then all
75 the long columns and row pieces are purged before the head row piece can be
76 purged. When a row is purged from an overflow page and it is the only row on
77 the page, then the page is deallocated in the same transaction. Note that
78 non-overflow pages are removed by Access but overflow pages are removed by Raw
79 Store. Note that page removal is done in the same transaction and not post
80 commit. This is, in general, dangerous because if the transaction does not
81 commit for a long time, uncommit deallocated page slows down page allocation
82 for this container. However, we know that access only purges committed delete
83 row in access post commit processing so we know the transaction will tend to
84 commit relatively fast. The alternative is to queue up a post commit
85 ReclaimSpace.PAGE to reclaim the page after the purge commits. In order to do
86 that, the time stamp of the page must also be remembered because post commit
87 work may be queued more than once, but in this case, it can only be done once.
88 Also, doing the page deallocation post commit adds to the overall cost and
89 tends to fill up the post commit queue. <BR>
90
91 This approach is simple but has the drawback that the entire long row and all
92 the long columns are logged in the purge operation. The alternative is more
93 complicated, we can remember all the long columns on the head row piece and
94 where the row chain starts and clean them up during post commit. During post
95 commit, because the head row piece is already purged, there is no need to log
96 the long column or the long rows, just wipe the page or just reuse the page if
97 that is the only thing on the page. The problem with this approach is that we
98 need to make sure the purging of the head row does indeed commit (the
99 transaction may commit but the purging may be rolled back due to savepoint).
100 So, we need to find the head row in the post commit and only when we cannot
101 find it can we be sure that the purge is committed. However, in cases where
102 the page can reuse its record Id (namely in btree), a new row may reuse the
103 same recordId. In that case, the post commit can purge the long columns or the
104 rest of the row piece only if the head piece no longer points to it. Because
105 of the complexity of this latter approach, the first simple approach is used.
106 However, if the performance due to extra logging becomes unbearble, we can
107 consider implementing the second approach.
108
109 <P><B>
110 Insertion of a row with long column or long row is rolled back.
111 </B><BR>
112
113 Insertion can be rolled back with either delete or purge. If the row is rolled
114 back with purge, then all the overflow columns pieces and row pieces are also
115 rolled back with purge. When a row is purged from an overflow page and it is
116 the only row on the page, then a post commit ReclaimSpace.PAGE work is queued
117 by Raw Store to reclaim that page.<BR>
118
119 If the row is rolled back with delete, then all the overflow columns pieces and
120 row pieces are also rolled back with delete. Access will purge the deleted row
121 in due time, see above.
122
123 <P><B>
124 Row is updated and the head row or some row pieces shrunk
125 </B><BR>
126
127 Every page that an update operation touches will see if the record on that page
128 has any reserve space. It it does, and if the reserve space plus the record
129 size exceed the mininum record size, then a post commit ROW_RESERVE work will
130 be queued to reclaim all unnecessary row reserved space for the entire row.
131
132 <P><B>
133 Row is updated and old long columns are orphaned
134 </B><BR>
135
136 The ground rule is, whether a column is a long column or not before an update
137 has nothing to do with whether a column will be a long column or not after the
138 update. In other words, update can turn a non-long column into a long column,
139 or it can turn a long column into a non-long column, or a long column can be
140 updated to another long column and a non-long column can be updated to a
141 non-long column. The last case - update of a non-long column to another
142 non-long column - is only of concern if it shrinks the row piece it is on (see
143 above).<BR>
144
145 So update can be looked at as 2 separate problems: A) a column is a long column
146 before the update and the update will "orphaned" it. B) a column is a long
147 column after the update and the rollback of the update will "orphaned" it if it
148 is rolled back with a delete. This section deals with problem A, next section
149 deals with problem B.<BR>
150
151 Update specifies a set of columns to be updated. If a row piece contains one
152 or more columns to be updated, those columns are examined to see if they are
153 actually long column chains. If they are, then after the update, those long
154 column chains will be orphaned. So before the update happens, a post commit
155 ReclaimSpace.COLUMN_CHAIN work is queued which contains the head rows id, the
156 column number, the location of the first piece of the column chain, and the
157 time stamp of the first page of the column chain. <BR>
158
159 If the update transaction commits, the post commit work will walk the row until
160 it finds the column number (note that it may not be on the page where the
161 update happened because of subsequent row splitting), and if it doesn't point
162 to the head of the column chain, we know the update operation has indeed
163 committed (versus rolled back by a savepoint). If a piece of the the column
164 chain takes up an entire page, then the entire page can be reclaimed without
165 first purging the row because the column chain is already orphaned.<BR>
166
167 We need to page time stamp of the first page of the column chain because if the
168 post commit ReclaimSpace.COLUMN_CHAIN is queued more than once, as can happen
169 in repeated rollback to savepoint, then after the first time the column is
170 reclaimed, the pages in the column chain can be reused. Therefore, we cannot
171 reclaim the column chain again. Since there is no back pointer from the column
172 chain to the head row, we need the timestamp to tell us if that column chain
173 has already been touched (reclaimed) or not.
174
175 <P><B>
176 Row is updated with new long columns and update is rolled back.
177 </B><BR>
178
179 When the update is rolled back, the new long columns, which got there by
180 insertion, got rolled back either by delete or by purge. If they were rolled
181 back with delete, then they will be orphaned and need to be cleaned up with
182 post abort work. Therefore, insertion of long columns due to update must be
183 rolled back with purge.<BR>
184
185 This is safe because the moment the rollback of the head row piece happens, the
186 new long column is orphaned anyway and nobody will be able to get to it. Since
187 we don't attempt to share long column pages, we know that nobody else could be
188 on the page and it is safe to deallocate the page.
189
190 <P><B>
191 Row is updated with new long row piece and update is rolled back.
192 </B><BR>
193
194 When the update is rolled back, the new long row piece, which got there by
195 insertion, got rolled back either by delete or by purge. Like update with new
196 long row, they should be rolled back with purge. However, there is a problem
197 in that the insert log record does not contain the head row handle. It is
198 possible that another long row emanating from the same head page overflows to
199 this page. That row may since have been deleted and is now in the middle of a
200 purge, but the purge has not commit. To the code that is rolling back the
201 insert (caused by the update that split off a new row piece) the overflow page
202 looks empty. If it went ahead and deallocate the page, then the transaction
203 which purged the row piece on this page won't be able to roll back. For this
204 reason, the rollback to insert of a long row piece due to update must be rolled
205 back with delete. Furthermore, there is no easy way to lodge a post
206 termination work to reclaim this deleted row piece so it will be lost forever.
207 <BR>
208
209 RESOLVE: need to log the head row's handle in the insert log record, i.e., any
210 insert due to update of long row or column piece should have the head row's
211 handle on it so that when the insert is rolled back with purge, and there is no
212 more row on the page, it can file a post commit to reclaim the page safely.
213 The post commit reclaim page needs to lock the head row and latch the head page
214 to make sure the entire row chain is stable.
215
216 <P><B>
217 */
218 public class ReclaimSpaceHelper
219 {
220     /**
221         Reclaim space based on work.
222      */
223     public static int reclaimSpace(BaseDataFileFactory dataFactory,
224                             RawTransaction tran,
225                             ReclaimSpace work)
226          throws StandardException
227     {
228     
229         if (work.reclaimWhat() == ReclaimSpace.CONTAINER)
230             return reclaimContainer(dataFactory, tran, work);
231
232         // Else, not reclaiming container. Get a no-wait shared lock on the
233 // container regardless of how the user transaction had the
234 // container opened.
235
236         LockingPolicy container_rlock =
237             tran.newLockingPolicy(LockingPolicy.MODE_RECORD,
238                                   TransactionController.ISOLATION_SERIALIZABLE,
239                                   true /* stricter OK */ );
240
241         if (SanityManager.DEBUG)
242             SanityManager.ASSERT(container_rlock != null);
243
244         ContainerHandle containerHdl =
245             openContainerNW(tran, container_rlock, work.getContainerId());
246
247         if (containerHdl == null)
248         {
249             tran.abort();
250
251             if (SanityManager.DEBUG)
252             {
253                 if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace))
254                 {
255                     SanityManager.DEBUG(
256                         DaemonService.DaemonTrace, " aborted " + work +
257                         " because container is locked or dropped");
258                 }
259             }
260
261             if (work.incrAttempts() < 3) // retry this for serveral times
262 return Serviceable.REQUEUE;
263             else
264                 return Serviceable.DONE;
265         }
266
267         // At this point, container is opened with IX lock.
268
269         if (work.reclaimWhat() == ReclaimSpace.PAGE)
270         {
271             // Reclaiming a page - called by undo of insert which purged the
272 // last row off an overflow page. It is safe to reclaim the page
273 // without first locking the head row because unlike post commit
274 // work, this is post abort work. Abort is guarenteed to happen
275 // and to happen only once, if at all.
276 Page p = containerHdl.getPageNoWait(work.getPageId().getPageNumber());
277             if (p != null)
278                 containerHdl.removePage(p);
279
280             tran.commit();
281             return Serviceable.DONE;
282         }
283
284         // We are reclaiming row space or long column. First get an xlock on the
285 // head row piece.
286 RecordHandle headRecord = work.getHeadRowHandle();
287
288         if (!container_rlock.lockRecordForWrite(
289                 tran, headRecord, false /* not insert */, false /* nowait */))
290         {
291             // cannot get the row lock, retry
292 tran.abort();
293             if (work.incrAttempts() < 3)
294                 return Serviceable.REQUEUE;
295             else
296                 return Serviceable.DONE;
297         }
298
299         // The exclusive lock on the head row has been gotten.
300
301         if (work.reclaimWhat() == ReclaimSpace.ROW_RESERVE)
302         {
303             // This row may benefit from compaction.
304 containerHdl.compactRecord(headRecord);
305
306             // This work is being done - post commit, there is no user
307 // transaction that depends on the commit being sync'd. It is safe
308 // to commitNoSync() This do as one of 2 things will happen:
309 //
310 // 1) if any data page associated with this transaction is
311 // moved from cache to disk, then the transaction log
312 // must be sync'd to the log record for that change and
313 // all log records including the commit of this xact must
314 // be sync'd before returning.
315 //
316 // 2) if the data page is never written then the log record
317 // for the commit may never be written, and the xact will
318 // never make to disk. This is ok as no subsequent action
319 // depends on this operation being committed.
320 //
321 tran.commitNoSync(Transaction.RELEASE_LOCKS);
322
323             return Serviceable.DONE;
324         }
325         else
326         {
327             if (SanityManager.DEBUG)
328                 SanityManager.ASSERT(work.reclaimWhat() == ReclaimSpace.COLUMN_CHAIN);
329
330             // Reclaiming a long column chain due to update. The long column
331 // chain being reclaimed is the before image of the update
332 // operation.
333 //
334 long headPageId = ((PageKey)headRecord.getPageId()).getPageNumber();
335             StoredPage headRowPage =
336                 (StoredPage)containerHdl.getPageNoWait(headPageId);
337
338             if (headRowPage == null)
339             {
340                 // Cannot get page no wait, try again later.
341 tran.abort();
342                 if (work.incrAttempts() < 3)
343                     return Serviceable.REQUEUE;
344                 else
345                     return Serviceable.DONE;
346             }
347
348             try
349             {
350                 headRowPage.removeOrphanedColumnChain(work, containerHdl);
351             }
352             finally
353             {
354                 headRowPage.unlatch();
355             }
356
357             // This work is being done - post commit, there is no user
358 // transaction that depends on the commit being sync'd. It is safe
359 // to commitNoSync() This do as one of 2 things will happen:
360 //
361 // 1) if any data page associated with this transaction is
362 // moved from cache to disk, then the transaction log
363 // must be sync'd to the log record for that change and
364 // all log records including the commit of this xact must
365 // be sync'd before returning.
366 //
367 // 2) if the data page is never written then the log record
368 // for the commit may never be written, and the xact will
369 // never make to disk. This is ok as no subsequent action
370 // depends on this operation being committed.
371 //
372 tran.commitNoSync(Transaction.RELEASE_LOCKS);
373
374             return Serviceable.DONE;
375         }
376     }
377
378     private static int reclaimContainer(BaseDataFileFactory dataFactory,
379                                         RawTransaction tran,
380                                         ReclaimSpace work)
381          throws StandardException
382     {
383         // when we want to reclaim the whole container, gets an exclusive
384 // XLock on the container, wait for the lock.
385
386         LockingPolicy container_xlock =
387             tran.newLockingPolicy(LockingPolicy.MODE_CONTAINER,
388                                   TransactionController.ISOLATION_SERIALIZABLE,
389                                   true /* stricter OK */ );
390
391         if (SanityManager.DEBUG)
392             SanityManager.ASSERT(container_xlock != null);
393
394         // Try to just get the container thru the transaction.
395 // Need to do this to transition the transaction to active state.
396 RawContainerHandle containerHdl = tran.openDroppedContainer(
397                                 work.getContainerId(),
398                                 container_xlock);
399
400         // if it can get lock but it is not deleted or has already been
401 // deleted, done work
402 if (containerHdl == null ||
403             containerHdl.getContainerStatus() == RawContainerHandle.NORMAL ||
404             containerHdl.getContainerStatus() == RawContainerHandle.COMMITTED_DROP)
405         {
406             if (containerHdl != null)
407                 containerHdl.close();
408             tran.abort(); // release xlock, if any
409
410             if (SanityManager.DEBUG)
411             {
412                 if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace))
413                 {
414                     SanityManager.DEBUG(
415                         DaemonService.DaemonTrace, " aborted " + work);
416                 }
417             }
418         }
419         else
420         {
421             // we got an xlock on a dropped container. Must be committed.
422 // Get rid of the container now.
423 ContainerOperation lop = new
424                 ContainerOperation(containerHdl, ContainerOperation.REMOVE);
425
426             // mark the container as pre-dirtied so that if a checkpoint
427 // happens after the log record is sent to the log stream, the
428 // cache cleaning will wait for this change.
429 containerHdl.preDirty(true);
430             try
431             {
432                 tran.logAndDo(lop);
433             }
434             finally
435             {
436                 // in case logAndDo fail, make sure the container is not
437 // stuck in preDirty state.
438 containerHdl.preDirty(false);
439             }
440
441
442             containerHdl.close();
443             tran.commit();
444
445             if (SanityManager.DEBUG)
446             {
447                 if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace))
448                 {
449                     SanityManager.DEBUG(
450                         DaemonService.DaemonTrace, " committed " + work);
451                 }
452             }
453         }
454
455         return Serviceable.DONE;
456
457     }
458
459
460     /**
461         Open container shared no wait
462      */
463     private static ContainerHandle openContainerNW(Transaction tran,
464         LockingPolicy rlock, ContainerKey containerId)
465         throws StandardException
466     {
467         ContainerHandle containerHdl = tran.openContainer
468             (containerId, rlock,
469              ContainerHandle.MODE_FORUPDATE |
470              ContainerHandle.MODE_LOCK_NOWAIT);
471
472         return containerHdl;
473     }
474
475 }
476
Popular Tags