View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase.codec.prefixtree;
20  
21  import java.nio.ByteBuffer;
22  
23  import org.apache.hadoop.hbase.Cell;
24  import org.apache.hadoop.hbase.CellUtil;
25  import org.apache.hadoop.hbase.KeyValue;
26  import org.apache.hadoop.hbase.KeyValue.KVComparator;
27  import org.apache.hadoop.hbase.KeyValue.Type;
28  import org.apache.hadoop.hbase.KeyValueUtil;
29  import org.apache.hadoop.hbase.SettableSequenceId;
30  import org.apache.hadoop.hbase.classification.InterfaceAudience;
31  import org.apache.hadoop.hbase.codec.prefixtree.decode.DecoderFactory;
32  import org.apache.hadoop.hbase.codec.prefixtree.decode.PrefixTreeArraySearcher;
33  import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellScannerPosition;
34  import org.apache.hadoop.hbase.io.HeapSize;
35  import org.apache.hadoop.hbase.io.encoding.DataBlockEncoder.EncodedSeeker;
36  import org.apache.hadoop.hbase.util.Bytes;
37  import org.apache.hadoop.hbase.util.ClassSize;
38  
39  /**
40   * These methods have the same definition as any implementation of the EncodedSeeker.
41   *
42   * In the future, the EncodedSeeker could be modified to work with the Cell interface directly.  It
43   * currently returns a new KeyValue object each time getKeyValue is called.  This is not horrible,
44   * but in order to create a new KeyValue object, we must first allocate a new byte[] and copy in
45   * the data from the PrefixTreeCell.  It is somewhat heavyweight right now.
46   */
47  @InterfaceAudience.Private
48  public class PrefixTreeSeeker implements EncodedSeeker {
49  
50    protected ByteBuffer block;
51    protected boolean includeMvccVersion;
52    protected PrefixTreeArraySearcher ptSearcher;
53  
54    public PrefixTreeSeeker(boolean includeMvccVersion) {
55      this.includeMvccVersion = includeMvccVersion;
56    }
57  
58    @Override
59    public void setCurrentBuffer(ByteBuffer fullBlockBuffer) {
60      block = fullBlockBuffer;
61      ptSearcher = DecoderFactory.checkOut(block, includeMvccVersion);
62      rewind();
63    }
64  
65    /**
66     * <p>
67     * Currently unused.
68     * </p>
69     * TODO performance leak. should reuse the searchers. hbase does not currently have a hook where
70     * this can be called
71     */
72    public void releaseCurrentSearcher(){
73      DecoderFactory.checkIn(ptSearcher);
74    }
75  
76  
77    @Override
78    public ByteBuffer getKeyDeepCopy() {
79      return KeyValueUtil.copyKeyToNewByteBuffer(ptSearcher.current());
80    }
81  
82  
83    @Override
84    public ByteBuffer getValueShallowCopy() {
85      return CellUtil.getValueBufferShallowCopy(ptSearcher.current());
86    }
87  
88    /**
89     * currently must do deep copy into new array
90     */
91    @Override
92    public Cell getKeyValue() {
93      Cell cell = ptSearcher.current();
94      if (cell == null) {
95        return null;
96      }
97      return new ClonedPrefixTreeCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
98          cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
99          cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength(),
100         cell.getValueArray(), cell.getValueOffset(), cell.getValueLength(), cell.getTagsArray(),
101         cell.getTagsOffset(), cell.getTagsLength(), cell.getTimestamp(), cell.getTypeByte(),
102         cell.getSequenceId());
103   }
104 
105   /**
106    * <p>
107    * Currently unused.
108    * </p><p>
109    * A nice, lightweight reference, though the underlying cell is transient. This method may return
110    * the same reference to the backing PrefixTreeCell repeatedly, while other implementations may
111    * return a different reference for each Cell.
112    * </p>
113    * The goal will be to transition the upper layers of HBase, like Filters and KeyValueHeap, to
114    * use this method instead of the getKeyValue() methods above.
115    */
116   public Cell get() {
117     return ptSearcher.current();
118   }
119 
120   @Override
121   public void rewind() {
122     ptSearcher.positionAtFirstCell();
123   }
124 
125   @Override
126   public boolean next() {
127     return ptSearcher.advance();
128   }
129 
130   public boolean advance() {
131     return ptSearcher.advance();
132   }
133 
134 
135   private static final boolean USE_POSITION_BEFORE = false;
136 
137   /**
138    * Seek forward only (should be called reseekToKeyInBlock?).
139    * <p>
140    * If the exact key is found look at the seekBefore variable and:<br>
141    * - if true: go to the previous key if it's true<br>
142    * - if false: stay on the exact key
143    * </p><p>
144    * If the exact key is not found, then go to the previous key *if possible*, but remember to
145    * leave the scanner in a valid state if possible.
146    * </p>
147    * @param keyOnlyBytes KeyValue format of a Cell's key at which to position the seeker
148    * @param offset offset into the keyOnlyBytes array
149    * @param length number of bytes of the keyOnlyBytes array to use
150    * @param forceBeforeOnExactMatch if an exact match is found and seekBefore=true, back up 1 Cell
151    * @return 0 if the seeker is on the exact key<br>
152    *         1 if the seeker is not on the key for any reason, including seekBefore being true
153    */
154   @Override
155   public int seekToKeyInBlock(byte[] keyOnlyBytes, int offset, int length,
156       boolean forceBeforeOnExactMatch) {
157     if (USE_POSITION_BEFORE) {
158       return seekToOrBeforeUsingPositionAtOrBefore(keyOnlyBytes, offset, length,
159           forceBeforeOnExactMatch);
160     } else {
161       return seekToOrBeforeUsingPositionAtOrAfter(keyOnlyBytes, offset, length,
162           forceBeforeOnExactMatch);
163     }
164   }
165 
166   /*
167    * Support both of these options since the underlying PrefixTree supports both.  Possibly
168    * expand the EncodedSeeker to utilize them both.
169    */
170 
171   protected int seekToOrBeforeUsingPositionAtOrBefore(byte[] keyOnlyBytes, int offset, int length,
172       boolean seekBefore){
173     // this does a deep copy of the key byte[] because the CellSearcher interface wants a Cell
174     KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
175 
176     return seekToOrBeforeUsingPositionAtOrBefore(kv, seekBefore);
177   }
178 
179   /*
180    * Support both of these options since the underlying PrefixTree supports
181    * both. Possibly expand the EncodedSeeker to utilize them both.
182    */
183 
184   protected int seekToOrBeforeUsingPositionAtOrBefore(Cell kv, boolean seekBefore) {
185     // this does a deep copy of the key byte[] because the CellSearcher
186     // interface wants a Cell
187     CellScannerPosition position = ptSearcher.seekForwardToOrBefore(kv);
188 
189     if (CellScannerPosition.AT == position) {
190       if (seekBefore) {
191         ptSearcher.previous();
192         return 1;
193       }
194       return 0;
195     }
196 
197     return 1;
198   }
199 
200   protected int seekToOrBeforeUsingPositionAtOrAfter(byte[] keyOnlyBytes, int offset, int length,
201       boolean seekBefore) {
202     // this does a deep copy of the key byte[] because the CellSearcher
203     // interface wants a Cell
204     KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
205     return seekToOrBeforeUsingPositionAtOrAfter(kv, seekBefore);
206   }
207 
208   protected int seekToOrBeforeUsingPositionAtOrAfter(Cell kv, boolean seekBefore) {
209     // should probably switch this to use the seekForwardToOrBefore method
210     CellScannerPosition position = ptSearcher.seekForwardToOrAfter(kv);
211 
212     if (CellScannerPosition.AT == position) {
213       if (seekBefore) {
214         ptSearcher.previous();
215         return 1;
216       }
217       return 0;
218 
219     }
220 
221     if (CellScannerPosition.AFTER == position) {
222       if (!ptSearcher.isBeforeFirst()) {
223         ptSearcher.previous();
224       }
225       return 1;
226     }
227 
228     if (position == CellScannerPosition.AFTER_LAST) {
229       if (seekBefore) {
230         ptSearcher.previous();
231       }
232       return 1;
233     }
234 
235     throw new RuntimeException("unexpected CellScannerPosition:" + position);
236   }
237 
238   @Override
239   public int compareKey(KVComparator comparator, byte[] key, int offset, int length) {
240     // can't optimize this, make a copy of the key
241     ByteBuffer bb = getKeyDeepCopy();
242     return comparator.compareFlatKey(key, offset, length, bb.array(), bb.arrayOffset(), bb.limit());
243   }
244 
245   @Override
246   public int seekToKeyInBlock(Cell key, boolean forceBeforeOnExactMatch) {
247     if (USE_POSITION_BEFORE) {
248       return seekToOrBeforeUsingPositionAtOrBefore(key, forceBeforeOnExactMatch);
249     } else {
250       return seekToOrBeforeUsingPositionAtOrAfter(key, forceBeforeOnExactMatch);
251     }
252   }
253 
254   @Override
255   public int compareKey(KVComparator comparator, Cell key) {
256     ByteBuffer bb = getKeyDeepCopy();
257     return comparator.compare(key,
258         new KeyValue.KeyOnlyKeyValue(bb.array(), bb.arrayOffset(), bb.limit()));
259   }
260   /**
261    * Cloned version of the PrefixTreeCell where except the value part, the rest
262    * of the key part is deep copied
263    *
264    */
265   private static class ClonedPrefixTreeCell implements Cell, SettableSequenceId, HeapSize {
266     private static final long FIXED_OVERHEAD = ClassSize.align(ClassSize.OBJECT
267         + (5 * ClassSize.REFERENCE) + (2 * Bytes.SIZEOF_LONG) + (4 * Bytes.SIZEOF_INT)
268         + (Bytes.SIZEOF_SHORT) + (2 * Bytes.SIZEOF_BYTE) + (5 * ClassSize.ARRAY));
269     private byte[] row;
270     private short rowLength;
271     private byte[] fam;
272     private byte famLength;
273     private byte[] qual;
274     private int qualLength;
275     private byte[] val;
276     private int valOffset;
277     private int valLength;
278     private byte[] tag;
279     private int tagsLength;
280     private long ts;
281     private long seqId;
282     private byte type;
283 
284     public ClonedPrefixTreeCell(byte[] row, int rowOffset, short rowLength, byte[] fam,
285         int famOffset, byte famLength, byte[] qual, int qualOffset, int qualLength, byte[] val,
286         int valOffset, int valLength, byte[] tag, int tagOffset, int tagLength, long ts, byte type,
287         long seqId) {
288       this.row = new byte[rowLength];
289       System.arraycopy(row, rowOffset, this.row, 0, rowLength);
290       this.rowLength = rowLength;
291       this.fam = new byte[famLength];
292       System.arraycopy(fam, famOffset, this.fam, 0, famLength);
293       this.famLength = famLength;
294       this.qual = new byte[qualLength];
295       System.arraycopy(qual, qualOffset, this.qual, 0, qualLength);
296       this.qualLength = qualLength;
297       this.tag = new byte[tagLength];
298       System.arraycopy(tag, tagOffset, this.tag, 0, tagLength);
299       this.tagsLength = tagLength;
300       this.val = val;
301       this.valLength = valLength;
302       this.valOffset = valOffset;
303       this.ts = ts;
304       this.seqId = seqId;
305       this.type = type;
306     }
307 
308     @Override
309     public void setSequenceId(long seqId) {
310       this.seqId = seqId;
311     }
312 
313     @Override
314     public byte[] getRowArray() {
315       return this.row;
316     }
317 
318     @Override
319     public int getRowOffset() {
320       return 0;
321     }
322 
323     @Override
324     public short getRowLength() {
325       return this.rowLength;
326     }
327 
328     @Override
329     public byte[] getFamilyArray() {
330       return this.fam;
331     }
332 
333     @Override
334     public int getFamilyOffset() {
335       return 0;
336     }
337 
338     @Override
339     public byte getFamilyLength() {
340       return this.famLength;
341     }
342 
343     @Override
344     public byte[] getQualifierArray() {
345       return this.qual;
346     }
347 
348     @Override
349     public int getQualifierOffset() {
350       return 0;
351     }
352 
353     @Override
354     public int getQualifierLength() {
355       return this.qualLength;
356     }
357 
358     @Override
359     public long getTimestamp() {
360       return ts;
361     }
362 
363     @Override
364     public byte getTypeByte() {
365       return type;
366     }
367 
368     @Override
369     @Deprecated
370     public long getMvccVersion() {
371       return getSequenceId();
372     }
373 
374     @Override
375     public long getSequenceId() {
376       return seqId;
377     }
378 
379     @Override
380     public byte[] getValueArray() {
381       return val;
382     }
383 
384     @Override
385     public int getValueOffset() {
386       return this.valOffset;
387     }
388 
389     @Override
390     public int getValueLength() {
391       return this.valLength;
392     }
393 
394     @Override
395     public byte[] getTagsArray() {
396       return this.tag;
397     }
398 
399     @Override
400     public int getTagsOffset() {
401       return 0;
402     }
403 
404     @Override
405     public int getTagsLength() {
406       return this.tagsLength;
407     }
408 
409     @Override
410     @Deprecated
411     public byte[] getValue() {
412       return this.val;
413     }
414 
415     @Override
416     @Deprecated
417     public byte[] getFamily() {
418       return this.fam;
419     }
420 
421     @Override
422     @Deprecated
423     public byte[] getQualifier() {
424       return this.qual;
425     }
426 
427     @Override
428     @Deprecated
429     public byte[] getRow() {
430       return this.row;
431     }
432 
433     @Override
434     public String toString() {
435       String row = Bytes.toStringBinary(getRowArray(), getRowOffset(), getRowLength());
436       String family = Bytes.toStringBinary(getFamilyArray(), getFamilyOffset(), getFamilyLength());
437       String qualifier = Bytes.toStringBinary(getQualifierArray(), getQualifierOffset(),
438           getQualifierLength());
439       String timestamp = String.valueOf((getTimestamp()));
440       return row + "/" + family + (family != null && family.length() > 0 ? ":" : "") + qualifier
441           + "/" + timestamp + "/" + Type.codeToType(type);
442     }
443 
444     @Override
445     public long heapSize() {
446       return FIXED_OVERHEAD + rowLength + famLength + qualLength + valLength + tagsLength;
447     }
448   }
449 }