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