KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sleepycat > je > recovery > LevelRecorder


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: LevelRecorder.java,v 1.3 2006/10/30 21:14:22 bostic Exp $
7  */
8
9 package com.sleepycat.je.recovery;
10
11 import java.util.HashMap JavaDoc;
12 import java.util.HashSet JavaDoc;
13 import java.util.Iterator JavaDoc;
14 import java.util.Map JavaDoc;
15 import java.util.Set JavaDoc;
16
17 import com.sleepycat.je.dbi.DatabaseId;
18
19 /**
20  * LevelRecorder is used to determine when an extra read-IN pass is needed
21  * during recovery. See SR [#14424]
22  *
23  * Splits and compression require logging up to the root of the tree, to ensure
24  * that all INs are properly returned to the correct position at recovery. In
25  * other words, splits and compression ensure that the creation and deletion of
26  * all nodes is promptly logged.
27  *
28  * However, checkpoints are not propagated to the top of the tree, in order to
29  * conserve on logging. Because of that, a great-aunt situation can occur,
30  * where an ancestor of a given node can be logged without referring to the
31  * latest on-disk position of the node, because that ancestor was part of a
32  * split or compression.
33  *
34  * Take this scenario:
35  * Root-A
36  * / \
37  * IN-B IN-C
38  * / / | \
39  * BIN-D
40  * /
41  * LN-E
42  *
43  * 1) LN-E is logged, BIN-D is dirtied
44  * 2) BIN-D is logged during a checkpoint, IN-B is dirtied
45  * 3) IN-C is split and Root-A is logged
46  * 4) We recover using Root-A and the BIN-D logged at (2) is lost
47  *
48  * At (3) when Root-A is logged, it points to an IN-B on disk that does not
49  * point to the most recent BIN-D
50  *
51  * At (4) when we recover, although we will process the BIN-D logged at (2) and
52  * splice it into the tree, the Root-A logged at (3) is processed last and
53  * overrides the entire subtree containing BIN-D
54  *
55  * This could be addressed by always logging to the root at every checkpoint.
56  * Barring that, we address it by replaying INs a second time at recovery
57  * if we can detect that a split or compression occurred -- if there are
58  * multiple level of non-provisional IN entries for the given database.
59  *
60  * In the ideal case, this would occur infrequently. If there were a checkpoint
61  * and no splits/compressions, one should only see the checkpoint top level as
62  * non-provisional log entries.
63  *
64  * One issue that may make this extra read pass occur more than it should is
65  * that cascading updates for splits and compressions are logging all entries
66  * non-provisionally, when in theory, only the root need be logged
67  * non-provisionally. This makes splits and compressions more expensive to
68  * process at recovery than they should be, and may cause unnecessary extra
69  * passes. We'll leave that implementation now for stability, and will return
70  * to this optimization.
71  */
72 class LevelRecorder {
73     
74     /* Map of DatabaseId->LevelInfo */
75     private Map JavaDoc dbLevels;
76
77     LevelRecorder() {
78         dbLevels = new HashMap JavaDoc();
79     }
80
81     /*
82      * Record whether the level seen for the current IN is the highest or
83      * lowest.
84      */
85     void record(DatabaseId dbId, int level) {
86         LevelInfo info =(LevelInfo) dbLevels.get(dbId);
87         if (info == null) {
88             info = new LevelInfo();
89             dbLevels.put(dbId, info);
90         }
91         info.recordLevel(level);
92     }
93
94     /*
95      * Get the set of databases that were logged non-provisionally with
96      * different levels in the ckpt set. These databases must be redone.
97      */
98     Set JavaDoc getDbsWithDifferentLevels() {
99         Set JavaDoc reprocessDbs = new HashSet JavaDoc();
100         Set JavaDoc entries = dbLevels.entrySet();
101         Iterator JavaDoc iter = entries.iterator();
102         while (iter.hasNext()) {
103             Map.Entry JavaDoc oneEntry = (Map.Entry JavaDoc) iter.next();
104             LevelInfo levelInfo = (LevelInfo)oneEntry.getValue();
105             if (levelInfo.getDifferenceSeen()) {
106                 reprocessDbs.add(oneEntry.getKey());
107             }
108         }
109         return reprocessDbs;
110     }
111
112     /**
113      * Remember the highest and lowest level seen for a given database.
114      */
115     private static class LevelInfo {
116         private int highest = Integer.MIN_VALUE;
117         private int lowest = Integer.MAX_VALUE;
118         private boolean differenceSeen = false;
119         
120         void recordLevel(int level) {
121             if (!differenceSeen) {
122                 if (level < lowest) {
123                     lowest = level;
124                 }
125                 if (level > highest) {
126                     highest = level;
127                 }
128                 differenceSeen = highest > lowest;
129             }
130         }
131
132         /*
133          * @return true if there is a difference between the highest and
134          * lowest.
135          */
136         boolean getDifferenceSeen() {
137             return differenceSeen;
138         }
139     }
140 }
141
Popular Tags