| /*- |
| * Copyright (C) 2002, 2018, Oracle and/or its affiliates. All rights reserved. |
| * |
| * This file was distributed by Oracle as part of a version of Oracle Berkeley |
| * DB Java Edition made available at: |
| * |
| * http://www.oracle.com/technetwork/database/database-technologies/berkeleydb/downloads/index.html |
| * |
| * Please see the LICENSE file included in the top-level directory of the |
| * appropriate version of Oracle Berkeley DB Java Edition for a copy of the |
| * license and additional information. |
| */ |
| |
| package com.sleepycat.je.log; |
| |
| import com.sleepycat.je.utilint.DbLsn; |
| |
| /** |
| * Specifies whether to log an entry provisionally. |
| * |
| * Provisional log entries: |
| * |
| * What are provisional log entries? |
| * |
| * Provisional log entries are those tagged with the provisional attribute |
| * in the log entry header. The provisional attribute can be applied to any |
| * type of log entry, and is implemented in |
| * com.sleepycat.je.log.LogEntryHeader as two stolen bits in the 8 bit |
| * version field. |
| * |
| * When is the provisional attribute used? |
| * |
| * The provisional attribute is used only during recovery. It very simply |
| * indicates that recovery will ignore and skip over this log entry. |
| * |
| * When is the provisional attribute set? |
| * |
| * The provisional attribute started out as a way to create atomicity among |
| * different log entries. Child pointers in the JE Btree are physical LSNs, |
| * so each Btree node's children must be logged before it in the log. On |
| * the other hand, one fundamental assumption of the JE log is that each |
| * Btree node found in the log can be replayed and placed in the in-memory |
| * tree. To do so, each Btree node must have a parent node that will house |
| * it. The grouping of multiple log entries into one atomic group is often |
| * used to fulfiil this requirement. |
| * |
| * * Atomic log entries: |
| * |
| * + When a btree is first created, we bootstrap tree creation by |
| * logging the first BIN provisionally, then creating a parent IN |
| * which is the Btree root IN, which points to this first BIN. |
| * |
| * + When we split a Btree node, we create a new IN, which is the |
| * sibling of the split node. We log the old sibling and the new |
| * sibling provisionally, and then log the parent, so that any |
| * crashes in the middle of this triumvirate which result in the |
| * failure to log the parent will skip over the orphaned siblings. |
| * |
| * + Splitting the Btree root is just a special case of a split. |
| * |
| * + Creating a duplicate subtree to hang in the middle of a btree is |
| * just a special case of a split and btree first creation. |
| * |
| * * Entries not meant to be recovered |
| * |
| * Temp DBs are not meant to be recovered and we log their LN |
| * and IN nodes in a very lax fashion, purely as a way of evicting |
| * them out of the cache temporarily. There is no guarantee that a |
| * consistent set has been logged to disk. We skip over them for both |
| * recovery performance and the "each-node-must-have-a-parent" rule. |
| * |
| * * Durable deferred-write entries |
| * |
| * Deferred-write INs are logged provisionally for the same reasons |
| * as for temp DBs (above): for recovery performance and the |
| * "each-node-must-have-a-parent" rule. |
| * |
| * Deferred-write LNs are logged non-provisionally to support |
| * obsolete LSN counting. It would be nice to log them provisionally |
| * for recovery performance and to allow LN deletion without logging; |
| * however, that is not currently practical if obsolete counting is |
| * to be supported. See [#16864]. |
| * |
| * * Checkpoint performance |
| * |
| * When we flush a series of nodes, it's a waste to replay nodes |
| * which are referenced by higher levels. For example, if we |
| * checkpoint this btree: |
| * |
| * {@literal |
| * INA -> INb -> BINc (dirty)-> LNd |
| * } |
| * |
| * we log them in this order: |
| * |
| * BINc |
| * INb |
| * |
| * And there's no point to replaying BINc, because it's referenced by |
| * INb. We skip over BINc, which we do by logging it provisionally. |
| * |
| * In addition, BEFORE_CKPT_END is used to improve cleaner |
| * performance by keeping utilization information up-to-date during |
| * the checkpoint. See below for details. |
| * |
| * * Log cleaning - removing references to deleted files. |
| * |
| * When we delete a file for log cleaning we guarantee that no active log |
| * entries refer to any log entry in the deleted file. Suppose our |
| * checkpoint looks like this: |
| * |
| * 5/100 LNa |
| * 5/200 Ckpt start |
| * 5/300 INs |
| * ... |
| * 5/500 Ckpt end |
| * ... |
| * 5/800 last entry in log |
| * |
| * Because we do not delete a file until the Ckpt end after processing |
| * (cleaning) it, nothing from 5/500 to 5/800 can refer to a file deleted |
| * due to the Ckpt end in 5/500. |
| * |
| * BEFORE_CKPT_END is motivated in part (see below for a complete |
| * description) by the fact that while log entries between 5/100 |
| * (first active lsn) and 5/500 (ckpt end) will not in of themselves |
| * contain a LSN for a cleaned, deleted file, the act of processing them |
| * during recovery could require fetching a node from a deleted file. For |
| * example, the IN at 5/300 could have an in-memory parent which has a |
| * reference to an older, cleaned version of that IN. Treating the span |
| * between 5/200 and 5/500 as provisional is both optimal, because only |
| * the high level INs need to be processed, and required, in order not to |
| * fetch from a cleaned file. |
| * |
| * The correctness issue is described in [#16037] comment 151, where we |
| * attempted to log non-provisionally below maxFlushLevel. It is |
| * repeated below. |
| * |
| * IN-A |
| * \ |
| * IN-B |
| * \ |
| * IN-C |
| * \ |
| * BIN-D |
| * |
| * 1/100 CkptStart |
| * 1/200 BIN-D provisional |
| * 1/300 IN-C non-provisional |
| * 2/100 IN-B non-provisional |
| * 2/200 IN-A non-provisional |
| * 2/300 MapLN refers to IN-A |
| * 2/400 CkptEnd |
| * 5/100 cleaner processes file 1 |
| * BIN-D and IN-C are dirty |
| * 5/200 CkptStart |
| * 5/300 BIN-D provisional |
| * 5/400 IN-C non-provisional |
| * 5/500 IN-B non-provisional (must log one extra level) |
| * IN-A is not logged |
| * MapLN still refers to IN-A at 2/200 |
| * 5/600 CkptEnd |
| * file 1 is deleted |
| * 6/100 Start recovery |
| * |
| * Note that only the bottom level BINs are logged provisionally because |
| * we're logging level 2 and up non-provisionally in this experiment. |
| * |
| * Recovery replays IN-C at 5/400 because it is non-provisional. |
| * |
| * When it does the tree lookup (getParentINForChildIN) it uses the root |
| * IN-A at 2/200. This search fetches IN-B at 2/100 and then fails |
| * fetching IN-C at 1/300 because file 1 has been deleted. |
| * |
| * In reality we log provisionally below maxFlushLevel, so that IN-C at |
| * 5/400 is not replayed. IN-B at 5/500 is at the maxFlushLevel and is |
| * non-provisional and is replayed. The search succeeds because nothing |
| * in file 1 needs to be fetched to find the parent. |
| * |
| * TODO: Could we instead replay INs in reverse order? |
| * Then IN-B at 5/500 would be replayed first. Unfortunately this would |
| * probably break something else. For example, the utilization tracking |
| * replay for INs currently depends on reading forward. This is worth |
| * exploring, however, since reducing logging during checkpoints would be |
| * extremely beneficial. |
| * |
| * Provisional.BEFORE_CKPT_END |
| * --------------------------- |
| * This property was added to solve a specific problem that occurs in earlier |
| * versions of JE: When a long checkpoint runs, the BINs are not counted |
| * obsolete until after the entire BIN level has been logged. Specifically, |
| * they are counted obsolete when their ancestor is logged non-provisionally. |
| * Most INs logged by a checkpoint are BINs. This means that during a very |
| * long checkpoint, cleaning of the files containing those old BINs is delayed, |
| * and more importantly the calculated utilization is much higher than it |
| * actually is. The correction in utilization does not occur until the end of |
| * the checkpoint, when the higher level INs are logged. This manifests as a |
| * lull in cleaning during the checkpoint, because calculated utilization is |
| * artificially high, and a spike in cleaning at the end of the checkpoint. In |
| * some cases, the cleaner cannot recover from the backlog that is created by |
| * the spike. |
| * |
| * The provisional property effects obsolete counting as follows: |
| * |
| * + If an IN is logged with Provisional.YES, the old version of the IN is not |
| * counted obsolete immediately. Instead, the offset of the old version of |
| * the IN is added to a list in its parent IN. The offsets migrate upward |
| * in the tree in this manner until an ancestor IN is logged |
| * non-provisionally. |
| * |
| * + If an IN is logged with Provisional.NO or BEFORE_CKPT_END, the old |
| * version of the IN is counted obsolete immediately (and offsets |
| * accumulated from provisional child INs are counted). This means |
| * that the obsolete offset is added to the UtilizationTracker, and may be |
| * flushed in a FileSummaryLN any time after that. At the latest, it is |
| * flushed at the end of the checkpoint. |
| * |
| * Because subtree logging is now used for checkpoints and the parent IN of |
| * each logged sub-tree is logged with BEFORE_CKPT_END, the prior version of |
| * all INs in the sub-tree will be counted obsolete at that time. This keeps |
| * the calculated utilization accurate throughout the checkpoint, and prevents |
| * the large per-checkpoint lull and spike in log cleaning. |
| * |
| * For the intermediate levels, Provisional.BEFORE_CKPT_END must be used rather |
| * than Provisional.NO, which is reserved for the highest level only. During |
| * recovery, the Provisional values are treated as follows (this is from the |
| * Provisional javadoc): |
| * + NO: The entry is non-provisional and is always processed by recovery. |
| * + YES: The entry is provisional and is never processed by recovery. |
| * + BEFORE_CKPT_END: The entry is provisional (not processed by recovery) if |
| * it occurs before the CkptEnd in the recovery interval, or is |
| * non-provisional (is processed) if it occurs after CkptEnd. |
| * |
| * The key to BEFORE_CKPT_END is that it is treated as provisional if a CkptEnd |
| * is logged, i.e., if we do not crash before completing the checkpoint. |
| * Because the checkpoint completed, we may have deleted log files that |
| * would be necessary to replay the IN. So we cannot safely replay it. |
| * |
| * Note the difference in the treatment of BEFORE_CKPT_END for obsolete |
| * counting and recovery: |
| * + For obsolete counting, BEFORE_CKPT_END is treated as non-provisional. |
| * + For recovery, when the IN occurs before CkptEnd, BEFORE_CKPT_END is |
| * treated as provisional. |
| * This difference is the reason for the existence of BEFORE_CKPT_END. |
| * |
| * TODO: Improvement to tracking of obsolete data. |
| * When we checkpoint INs, why can't we always count the previous version |
| * obsolete immediately, irrespective of whether it is logged provisionally? |
| * The previous version file can't be deleted until after a complete |
| * checkpoint. If we do not complete the next checkpoint, recovery will |
| * replay the INs logged with BEFORE_CKPT_END. So the previous version will be |
| * obsolete. This would avoid storing a list of obsolete child LSNs in each |
| * parent IN, and would make the utilization summary more up-to-date. The |
| * motivation for sub-tree logging was to keep the utilization info up-to-date, |
| * so we may be able to remove sub-tree logging as well. Additionally, I think |
| * we can remove BEFORE_CKPT_END and log provisionally (YES) instead, because |
| * recovery will replay the actions that dirtied the INs, and the ckpt at the |
| * end of recovery will flush the dirty nodes, making the previous version |
| * obsolete; however, this would duplicate the provisional INs, so perhaps it |
| * is best to continue to use BEFORE_CKPT_END. |
| */ |
| public enum Provisional { |
| |
| /** |
| * The entry is non-provisional and is always processed by recovery. |
| */ |
| NO, |
| |
| /** |
| * The entry is provisional and is never processed by recovery. |
| */ |
| YES, |
| |
| /** |
| * The entry is provisional (not processed by recovery) if it occurs before |
| * the CkptEnd in the recovery interval, or is non-provisional (is |
| * processed) if it occurs after CkptEnd. |
| */ |
| BEFORE_CKPT_END; |
| |
| /** |
| * Determines whether a given log entry should be processed during |
| * recovery. |
| */ |
| public boolean isProvisional(long logEntryLsn, long ckptEndLsn) { |
| assert logEntryLsn != DbLsn.NULL_LSN; |
| switch (this) { |
| case NO: |
| return false; |
| case YES: |
| return true; |
| case BEFORE_CKPT_END: |
| return ckptEndLsn != DbLsn.NULL_LSN && |
| DbLsn.compareTo(logEntryLsn, ckptEndLsn) < 0; |
| default: |
| assert false; |
| return false; |
| } |
| } |
| } |
