1 /**
2 * Copyright (c) 2011, University of Konstanz, Distributed Systems Group
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of the University of Konstanz nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 package org.treetank.access;
29
30 import static com.google.common.base.Objects.toStringHelper;
31 import static com.google.common.base.Preconditions.checkArgument;
32 import static com.google.common.base.Preconditions.checkState;
33
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.List;
37
38 import org.treetank.access.conf.ConstructorProps;
39 import org.treetank.api.IBucketReadTrx;
40 import org.treetank.api.IData;
41 import org.treetank.api.ISession;
42 import org.treetank.bucket.IConstants;
43 import org.treetank.bucket.IndirectBucket;
44 import org.treetank.bucket.MetaBucket;
45 import org.treetank.bucket.DataBucket;
46 import org.treetank.bucket.DataBucket.DeletedData;
47 import org.treetank.bucket.RevisionRootBucket;
48 import org.treetank.bucket.UberBucket;
49 import org.treetank.bucket.interfaces.IBucket;
50 import org.treetank.bucket.interfaces.IReferenceBucket;
51 import org.treetank.exception.TTException;
52 import org.treetank.exception.TTIOException;
53 import org.treetank.io.IBackendReader;
54 import org.treetank.revisioning.IRevisioning;
55
56 import com.google.common.cache.Cache;
57 import com.google.common.cache.CacheBuilder;
58
59 /**
60 * <h1>BucketReadTrx</h1>
61 *
62 * <p>
63 * State of a reading transaction. The only thing shared amongst transactions is the bucket cache. Everything
64 * else is exclusive to this transaction. It is required that only a single thread has access to this
65 * transaction.
66 * </p>
67 *
68 * <p>
69 * A path-like cache boosts sequential operations.
70 * </p>
71 */
72 public class BucketReadTrx implements IBucketReadTrx {
73
74 /** Bucket reader exclusively assigned to this transaction. */
75 private final IBackendReader mBucketReader;
76
77 /** Uber bucket this transaction is bound to. */
78 private final UberBucket mUberBucket;
79
80 /** Cached root bucket of this revision. */
81 protected final RevisionRootBucket mRootBucket;
82
83 /** Cached name bucket of this revision. */
84 protected final MetaBucket mMetaBucket;
85
86 /** Configuration of the session */
87 protected final ISession mSession;
88
89 /** Boolean for determinc close. */
90 private boolean mClose;
91
92 /** Cache for reading data. */
93 protected final Cache<Long, DataBucket> mCache;
94
95 /**
96 * Standard constructor.
97 *
98 * @param pSession
99 * State of state.
100 * @param pUberBucket
101 * Uber bucket to start reading with.
102 * @param pRevBucket
103 * RevisionBucket with reference from either log to commit or persistent memory.
104 * @param pMetaBucket
105 * MetaBucket with reference from either log to commit or persistent memory.
106 * @param pReader
107 * for this transaction
108 * @throws TTIOException
109 * if the read of the persistent storage fails
110 */
111 protected BucketReadTrx(final ISession pSession, final UberBucket pUberBucket,
112 final RevisionRootBucket pRevBucket, final MetaBucket pMetaBucket, final IBackendReader pReader)
113 throws TTException {
114 mSession = pSession;
115 mBucketReader = pReader;
116 mUberBucket = pUberBucket;
117 mRootBucket = pRevBucket;
118 mMetaBucket = pMetaBucket;
119 mClose = false;
120 mCache = CacheBuilder.newBuilder().maximumSize(100).build();
121 }
122
123 /**
124 * Getting the data related to the given data key.
125 *
126 * @param pDataKey
127 * searched for
128 * @return the related data
129 * @throws TTIOException
130 * if the read to the persistent storage fails
131 */
132 public IData getData(final long pDataKey) throws TTIOException {
133 checkArgument(pDataKey >= 0);
134 checkState(!mClose, "Transaction already closed");
135 // Calculate bucket and data part for given datakey.
136 final long seqBucketKey = pDataKey >> IConstants.INDIRECT_BUCKET_COUNT[3];
137 final int dataBucketOffset = dataBucketOffset(pDataKey);
138 DataBucket bucket = mCache.getIfPresent(seqBucketKey);
139 if (bucket == null) {
140 final List<DataBucket> listRevs = getSnapshotBuckets(seqBucketKey);
141 final DataBucket[] revs = listRevs.toArray(new DataBucket[listRevs.size()]);
142 checkState(revs.length > 0, "Number of Buckets to reconstruct must be larger than 0");
143 // Build up the complete bucket.
144 final IRevisioning revision = mSession.getConfig().mRevision;
145 bucket = revision.combineBuckets(revs);
146 mCache.put(seqBucketKey, bucket);
147 }
148 final IData returnVal = bucket.getData(dataBucketOffset);
149 // root-fsys is excluded from the checkagainst deletion based on the necesssity of the data-layer to
150 // reference against this data while creation of the transaction
151 if (pDataKey == 0) {
152 return returnVal;
153 } else {
154 return checkItemIfDeleted(returnVal);
155 }
156
157 }
158
159 /**
160 * Closing this Readtransaction.
161 *
162 * @throws TTIOException
163 * if the closing to the persistent storage fails.
164 */
165 public boolean close() throws TTIOException {
166 if (!mClose) {
167 mSession.deregisterBucketTrx(this);
168 mBucketReader.close();
169 mClose = true;
170 return true;
171 } else {
172 return false;
173 }
174
175 }
176
177 /**
178 * {@inheritDoc}
179 */
180 public long getRevision() throws TTIOException {
181 checkState(!mClose, "Transaction already closed");
182 return mRootBucket.getRevision();
183 }
184
185 /**
186 * {@inheritDoc}
187 */
188 @Override
189 public boolean isClosed() {
190 return mClose;
191 }
192
193 /**
194 * {@inheritDoc}
195 */
196 @Override
197 public MetaBucket getMetaBucket() {
198 checkState(!mClose, "Transaction already closed");
199 return mMetaBucket;
200 }
201
202 /**
203 * Method to check if an {@link IData} is a deleted one.
204 *
205 * @param pToCheck
206 * of the IItem
207 * @return the item if it is valid, null otherwise
208 */
209 protected final IData checkItemIfDeleted(final IData pToCheck) {
210 if (pToCheck == null) {
211 throw new IllegalStateException(new StringBuilder("Data not existing.").toString());
212 } else if (pToCheck instanceof DeletedData) {
213 return null;
214 } else {
215 return pToCheck;
216 }
217 }
218
219 /**
220 * Dereference data bucket reference.
221 *
222 * @param pSeqDataBucketKey
223 * Key of data bucket.
224 * @return Dereferenced bucket.
225 *
226 * @throws TTIOException
227 * if something odd happens within the creation process.
228 */
229 protected final List<DataBucket> getSnapshotBuckets(final long pSeqDataBucketKey) throws TTIOException {
230
231 // Return Value, since the revision iterates a flexible number of version, this has to be a list
232 // first.
233 final List<DataBucket> dataBuckets = new ArrayList<DataBucket>();
234
235 // Getting the keys for the revRoots
236 final long[] pathToRoot =
237 BucketReadTrx.dereferenceLeafOfTree(mBucketReader,
238 mUberBucket.getReferenceKeys()[IReferenceBucket.GUARANTEED_INDIRECT_OFFSET], mRootBucket
239 .getRevision());
240 final RevisionRootBucket rootBucket =
241 (RevisionRootBucket)mBucketReader.read(pathToRoot[IConstants.INDIRECT_BUCKET_COUNT.length]);
242
243 final int numbersToRestore =
244 Integer.parseInt(mSession.getConfig().mProperties.getProperty(ConstructorProps.NUMBERTORESTORE));
245 // starting from the current databucket
246 final long[] pathToRecentBucket =
247 dereferenceLeafOfTree(mBucketReader,
248 rootBucket.getReferenceKeys()[IReferenceBucket.GUARANTEED_INDIRECT_OFFSET], pSeqDataBucketKey);
249
250 DataBucket bucket;
251 long bucketKey = pathToRecentBucket[IConstants.INDIRECT_BUCKET_COUNT.length];
252 // jumping through the databuckets based on the pointers
253 while (dataBuckets.size() < numbersToRestore && bucketKey > -1) {
254 bucket = (DataBucket)mBucketReader.read(bucketKey);
255 dataBuckets.add(bucket);
256 bucketKey = bucket.getLastBucketPointer();
257 }
258
259 // check if bucket was ever written before to perform check
260 if (bucketKey > -1) {
261 checkStructure(mBucketReader, pathToRecentBucket, rootBucket, pSeqDataBucketKey);
262 checkStructure(mBucketReader, pathToRoot, mUberBucket, mRootBucket.getRevision());
263 }
264
265 return dataBuckets;
266
267 }
268
269 /**
270 * Calculate data bucket offset for a given data key.
271 *
272 * @param pDataKey
273 * data key to find offset for.
274 * @return Offset into data bucket.
275 */
276 protected static final int dataBucketOffset(final long pDataKey) {
277 // INDIRECT_BUCKET_COUNT[3] is only taken to get the difference between 2^7 and the actual
278 // datakey as offset. It has nothing to do with the levels.
279 final long dataBucketOffset =
280 (pDataKey - ((pDataKey >> IConstants.INDIRECT_BUCKET_COUNT[3]) << IConstants.INDIRECT_BUCKET_COUNT[3]));
281 return (int)dataBucketOffset;
282 }
283
284 /**
285 * Find reference pointing to leaf bucket of an indirect tree.
286 *
287 * @param pStartKey
288 * Start reference pointing to the indirect tree.
289 * @param pSeqBucketKey
290 * Key to look up in the indirect tree.
291 * @return Reference denoted by key pointing to the leaf bucket.
292 *
293 * @throws TTIOException
294 * if something odd happens within the creation process.
295 */
296 protected static final long[] dereferenceLeafOfTree(final IBackendReader pReader, final long pStartKey,
297 final long pSeqBucketKey) throws TTIOException {
298
299 final long[] orderNumber = getOrderNumbers(pSeqBucketKey);
300
301 // Initial state pointing to the indirect bucket of level 0.
302 final long[] keys = new long[IConstants.INDIRECT_BUCKET_COUNT.length + 1];
303 IndirectBucket bucket = null;
304 keys[0] = pStartKey;
305 // Iterate through all levels...
306 for (int level = 0; level < orderNumber.length; level++) {
307 // ..read the buckets and..
308 bucket = (IndirectBucket)pReader.read(keys[level]);
309 // ..compute the offsets out of the order-numbers pre-computed before and store it in the
310 // key-array.
311 keys[level + 1] = bucket.getReferenceKeys()[dataBucketOffset(orderNumber[level])];
312 // if the bucketKey is 0, return -1 to distinguish mark non-written buckets explicitly.
313 if (keys[level + 1] == 0) {
314 Arrays.fill(keys, -1);
315 return keys;
316 }
317 }
318
319 // Return reference to leaf of indirect tree.
320 return keys;
321 }
322
323 /**
324 * Checking the structure based on a long array denoting the path to a leaf (either data or revrootbucket)
325 * and their super-bucket.
326 *
327 * The check is performed but no feedback is given because of the side-effects because of caching. This
328 * can easily be covered by flag, etc. but not in the scope of this prototype.
329 *
330 * @param pReader
331 * reader for getting the data from the backend
332 * @param pKeys
333 * long array denoting the path to the leaf starting from top to bottom
334 * @param mRootOfSubtree
335 * referencebucket representing the root
336 * @param pSeqBucketKey
337 * order key for getting the offsets on each level
338 * @throws TTIOException
339 */
340 private static final void checkStructure(final IBackendReader pReader, final long[] pKeys,
341 final IReferenceBucket mRootOfSubtree, final long pSeqBucketKey) throws TTIOException {
342
343 // getting the offsets on each level, globally
344 final long[] orderNumbers = getOrderNumbers(pSeqBucketKey);
345 // starting from the bottong...
346 IBucket currentBucket = pReader.read(pKeys[pKeys.length - 1]);
347 // ...all data is reconstructed bottom up (meaning from behind to the begin of the path...
348 for (int i = orderNumbers.length - 1; i >= 0; i--) {
349 // ..for each element, compute the hash and..
350 // final byte[] currentHash = currentBucket.secureHash().asBytes();
351 // just for benchmarking, since the hash is atm not checked to to side-effekts in caching
352 // resolvable
353 // over flags within this retrieval
354 currentBucket.secureHash().asBytes();
355 // ..retrieve the parent and.
356 currentBucket = pReader.read(pKeys[i]);
357 // ..retrieve the hash form the storage.
358 final byte[] storedHash =
359 ((IReferenceBucket)currentBucket).getReferenceHashs()[dataBucketOffset(orderNumbers[i])];
360 // if the hash was either bootstrapped or the bucket is currently in progress,
361 if (Arrays.equals(storedHash, IConstants.NON_HASHED)
362 || Arrays.equals(storedHash, IConstants.BOOTSTRAP_HASHED)) {
363 // ..just return.
364 return;
365 }// ...otherwise compare and print the error.
366 // else {
367 // if (!Arrays.equals(currentHash, storedHash)) {
368 // System.err.println("Hashes differ!");
369 // }
370 // }
371 }
372 // for the last level, the top (either revrootbucket or uberbucket, do the same.
373 // final byte[] currentHash = currentBucket.secureHash().asBytes();
374 // just for benchmarking, since the hash is atm not checked to to side-effekts in caching resolvable
375 // over flags within this retrieval
376 currentBucket.secureHash().asBytes();
377 final byte[] storedHash =
378 mRootOfSubtree.getReferenceHashs()[IReferenceBucket.GUARANTEED_INDIRECT_OFFSET];
379 // since the revroot currently in progress is linked to former substructure but has no actual hash,
380 // ignore it in that case.
381 if (Arrays.equals(storedHash, IConstants.NON_HASHED)
382 || Arrays.equals(storedHash, IConstants.BOOTSTRAP_HASHED)) {
383 return;
384 // } else {
385 // if (!Arrays.equals(currentHash, storedHash)) {
386 // System.err.println("Hashes differ!");
387 // }
388 }
389 }
390
391 private static final long[] getOrderNumbers(final long pSeqBucketKey) {
392 // computing the ordernumbers within all level. The ordernumbers are the position in the sequence of
393 // all buckets within the same level.
394 // ranges are for level 0: 0-127; level 1: 0-16383; level 2: 0-2097151; level 3: 0-268435455; ;level
395 // 4: 0-34359738367
396 final long[] orderNumber = new long[IConstants.INDIRECT_BUCKET_COUNT.length];
397 for (int level = 0; level < orderNumber.length; level++) {
398 orderNumber[level] = pSeqBucketKey >> IConstants.INDIRECT_BUCKET_COUNT[level];
399 }
400 return orderNumber;
401 }
402
403 /**
404 * {@inheritDoc}
405 */
406 @Override
407 public String toString() {
408 return toStringHelper(this).add("mBucketReader", mBucketReader).add("mBucketReader", mUberBucket)
409 .add("mRootBucket", mRootBucket).add("mClose", mClose).toString();
410 }
411
412 }