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     * Currently unused.
67     * <p/>
68     * TODO performance leak. should reuse the searchers. hbase does not currently have a hook where
69     * this can be called
70     */
71    public void releaseCurrentSearcher(){
72      DecoderFactory.checkIn(ptSearcher);
73    }
74  
75  
76    @Override
77    public ByteBuffer getKeyDeepCopy() {
78      return KeyValueUtil.copyKeyToNewByteBuffer(ptSearcher.current());
79    }
80  
81  
82    @Override
83    public ByteBuffer getValueShallowCopy() {
84      return CellUtil.getValueBufferShallowCopy(ptSearcher.current());
85    }
86  
87    /**
88     * currently must do deep copy into new array
89     */
90    @Override
91    public ByteBuffer getKeyValueBuffer() {
92      return KeyValueUtil.copyToNewByteBuffer(ptSearcher.current());
93    }
94  
95    /**
96     * currently must do deep copy into new array
97     */
98    @Override
99    public Cell getKeyValue() {
100     Cell cell = ptSearcher.current();
101     if (cell == null) {
102       return null;
103     }
104     return new ClonedPrefixTreeCell(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
105         cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
106         cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength(),
107         cell.getValueArray(), cell.getValueOffset(), cell.getValueLength(), cell.getTagsArray(),
108         cell.getTagsOffset(), cell.getTagsLength(), cell.getTimestamp(), cell.getTypeByte(),
109         cell.getSequenceId());
110   }
111 
112   /**
113    * Currently unused.
114    * <p/>
115    * A nice, lightweight reference, though the underlying cell is transient. This method may return
116    * the same reference to the backing PrefixTreeCell repeatedly, while other implementations may
117    * return a different reference for each Cell.
118    * <p/>
119    * The goal will be to transition the upper layers of HBase, like Filters and KeyValueHeap, to
120    * use this method instead of the getKeyValue() methods above.
121    */
122   public Cell get() {
123     return ptSearcher.current();
124   }
125 
126   @Override
127   public void rewind() {
128     ptSearcher.positionAtFirstCell();
129   }
130 
131   @Override
132   public boolean next() {
133     return ptSearcher.advance();
134   }
135 
136   public boolean advance() {
137     return ptSearcher.advance();
138   }
139 
140 
141   private static final boolean USE_POSITION_BEFORE = false;
142 
143   /**
144    * Seek forward only (should be called reseekToKeyInBlock?).
145    * <p/>
146    * If the exact key is found look at the seekBefore variable and:<br/>
147    * - if true: go to the previous key if it's true<br/>
148    * - if false: stay on the exact key
149    * <p/>
150    * If the exact key is not found, then go to the previous key *if possible*, but remember to
151    * leave the scanner in a valid state if possible.
152    * <p/>
153    * @param keyOnlyBytes KeyValue format of a Cell's key at which to position the seeker
154    * @param offset offset into the keyOnlyBytes array
155    * @param length number of bytes of the keyOnlyBytes array to use
156    * @param forceBeforeOnExactMatch if an exact match is found and seekBefore=true, back up 1 Cell
157    * @return 0 if the seeker is on the exact key<br/>
158    *         1 if the seeker is not on the key for any reason, including seekBefore being true
159    */
160   @Override
161   public int seekToKeyInBlock(byte[] keyOnlyBytes, int offset, int length,
162       boolean forceBeforeOnExactMatch) {
163     if (USE_POSITION_BEFORE) {
164       return seekToOrBeforeUsingPositionAtOrBefore(keyOnlyBytes, offset, length,
165           forceBeforeOnExactMatch);
166     } else {
167       return seekToOrBeforeUsingPositionAtOrAfter(keyOnlyBytes, offset, length,
168           forceBeforeOnExactMatch);
169     }
170   }
171 
172   /*
173    * Support both of these options since the underlying PrefixTree supports both.  Possibly
174    * expand the EncodedSeeker to utilize them both.
175    */
176 
177   protected int seekToOrBeforeUsingPositionAtOrBefore(byte[] keyOnlyBytes, int offset, int length,
178       boolean seekBefore){
179     // this does a deep copy of the key byte[] because the CellSearcher interface wants a Cell
180     KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
181 
182     return seekToOrBeforeUsingPositionAtOrBefore(kv, seekBefore);
183   }
184 
185   /*
186    * Support both of these options since the underlying PrefixTree supports
187    * both. Possibly expand the EncodedSeeker to utilize them both.
188    */
189 
190   protected int seekToOrBeforeUsingPositionAtOrBefore(Cell kv, boolean seekBefore) {
191     // this does a deep copy of the key byte[] because the CellSearcher
192     // interface wants a Cell
193     CellScannerPosition position = ptSearcher.seekForwardToOrBefore(kv);
194 
195     if (CellScannerPosition.AT == position) {
196       if (seekBefore) {
197         ptSearcher.previous();
198         return 1;
199       }
200       return 0;
201     }
202 
203     return 1;
204   }
205 
206   protected int seekToOrBeforeUsingPositionAtOrAfter(byte[] keyOnlyBytes, int offset, int length,
207       boolean seekBefore) {
208     // this does a deep copy of the key byte[] because the CellSearcher
209     // interface wants a Cell
210     KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
211     return seekToOrBeforeUsingPositionAtOrAfter(kv, seekBefore);
212   }
213 
214   protected int seekToOrBeforeUsingPositionAtOrAfter(Cell kv, boolean seekBefore) {
215     // should probably switch this to use the seekForwardToOrBefore method
216     CellScannerPosition position = ptSearcher.seekForwardToOrAfter(kv);
217 
218     if (CellScannerPosition.AT == position) {
219       if (seekBefore) {
220         ptSearcher.previous();
221         return 1;
222       }
223       return 0;
224 
225     }
226 
227     if (CellScannerPosition.AFTER == position) {
228       if (!ptSearcher.isBeforeFirst()) {
229         ptSearcher.previous();
230       }
231       return 1;
232     }
233 
234     if (position == CellScannerPosition.AFTER_LAST) {
235       if (seekBefore) {
236         ptSearcher.previous();
237       }
238       return 1;
239     }
240 
241     throw new RuntimeException("unexpected CellScannerPosition:" + position);
242   }
243 
244   @Override
245   public int compareKey(KVComparator comparator, byte[] key, int offset, int length) {
246     // can't optimize this, make a copy of the key
247     ByteBuffer bb = getKeyDeepCopy();
248     return comparator.compareFlatKey(key, offset, length, bb.array(), bb.arrayOffset(), bb.limit());
249   }
250 
251   @Override
252   public int seekToKeyInBlock(Cell key, boolean forceBeforeOnExactMatch) {
253     if (USE_POSITION_BEFORE) {
254       return seekToOrBeforeUsingPositionAtOrBefore(key, forceBeforeOnExactMatch);
255     } else {
256       return seekToOrBeforeUsingPositionAtOrAfter(key, forceBeforeOnExactMatch);
257     }
258   }
259 
260   @Override
261   public int compareKey(KVComparator comparator, Cell key) {
262     ByteBuffer bb = getKeyDeepCopy();
263     return comparator.compare(key,
264         new KeyValue.KeyOnlyKeyValue(bb.array(), bb.arrayOffset(), bb.limit()));
265   }
266   /**
267    * Cloned version of the PrefixTreeCell where except the value part, the rest
268    * of the key part is deep copied
269    *
270    */
271   private static class ClonedPrefixTreeCell implements Cell, SettableSequenceId, HeapSize {
272     private static final long FIXED_OVERHEAD = ClassSize.align(ClassSize.OBJECT
273         + (5 * ClassSize.REFERENCE) + (2 * Bytes.SIZEOF_LONG) + (4 * Bytes.SIZEOF_INT)
274         + (Bytes.SIZEOF_SHORT) + (2 * Bytes.SIZEOF_BYTE) + (5 * ClassSize.ARRAY));
275     private byte[] row;
276     private short rowLength;
277     private byte[] fam;
278     private byte famLength;
279     private byte[] qual;
280     private int qualLength;
281     private byte[] val;
282     private int valOffset;
283     private int valLength;
284     private byte[] tag;
285     private int tagsLength;
286     private long ts;
287     private long seqId;
288     private byte type;
289 
290     public ClonedPrefixTreeCell(byte[] row, int rowOffset, short rowLength, byte[] fam,
291         int famOffset, byte famLength, byte[] qual, int qualOffset, int qualLength, byte[] val,
292         int valOffset, int valLength, byte[] tag, int tagOffset, int tagLength, long ts, byte type,
293         long seqId) {
294       this.row = new byte[rowLength];
295       System.arraycopy(row, rowOffset, this.row, 0, rowLength);
296       this.rowLength = rowLength;
297       this.fam = new byte[famLength];
298       System.arraycopy(fam, famOffset, this.fam, 0, famLength);
299       this.famLength = famLength;
300       this.qual = new byte[qualLength];
301       System.arraycopy(qual, qualOffset, this.qual, 0, qualLength);
302       this.qualLength = qualLength;
303       this.tag = new byte[tagLength];
304       System.arraycopy(tag, tagOffset, this.tag, 0, tagLength);
305       this.tagsLength = tagLength;
306       this.val = val;
307       this.valLength = valLength;
308       this.valOffset = valOffset;
309       this.ts = ts;
310       this.seqId = seqId;
311       this.type = type;
312     }
313 
314     @Override
315     public void setSequenceId(long seqId) {
316       this.seqId = seqId;
317     }
318 
319     @Override
320     public byte[] getRowArray() {
321       return this.row;
322     }
323 
324     @Override
325     public int getRowOffset() {
326       return 0;
327     }
328 
329     @Override
330     public short getRowLength() {
331       return this.rowLength;
332     }
333 
334     @Override
335     public byte[] getFamilyArray() {
336       return this.fam;
337     }
338 
339     @Override
340     public int getFamilyOffset() {
341       return 0;
342     }
343 
344     @Override
345     public byte getFamilyLength() {
346       return this.famLength;
347     }
348 
349     @Override
350     public byte[] getQualifierArray() {
351       return this.qual;
352     }
353 
354     @Override
355     public int getQualifierOffset() {
356       return 0;
357     }
358 
359     @Override
360     public int getQualifierLength() {
361       return this.qualLength;
362     }
363 
364     @Override
365     public long getTimestamp() {
366       return ts;
367     }
368 
369     @Override
370     public byte getTypeByte() {
371       return type;
372     }
373 
374     @Override
375     @Deprecated
376     public long getMvccVersion() {
377       return getSequenceId();
378     }
379 
380     @Override
381     public long getSequenceId() {
382       return seqId;
383     }
384 
385     @Override
386     public byte[] getValueArray() {
387       return val;
388     }
389 
390     @Override
391     public int getValueOffset() {
392       return this.valOffset;
393     }
394 
395     @Override
396     public int getValueLength() {
397       return this.valLength;
398     }
399 
400     @Override
401     public byte[] getTagsArray() {
402       return this.tag;
403     }
404 
405     @Override
406     public int getTagsOffset() {
407       return 0;
408     }
409 
410     @Override
411     public int getTagsLength() {
412       return this.tagsLength;
413     }
414 
415     @Override
416     @Deprecated
417     public byte[] getValue() {
418       return this.val;
419     }
420 
421     @Override
422     @Deprecated
423     public byte[] getFamily() {
424       return this.fam;
425     }
426 
427     @Override
428     @Deprecated
429     public byte[] getQualifier() {
430       return this.qual;
431     }
432 
433     @Override
434     @Deprecated
435     public byte[] getRow() {
436       return this.row;
437     }
438 
439     @Override
440     public String toString() {
441       String row = Bytes.toStringBinary(getRowArray(), getRowOffset(), getRowLength());
442       String family = Bytes.toStringBinary(getFamilyArray(), getFamilyOffset(), getFamilyLength());
443       String qualifier = Bytes.toStringBinary(getQualifierArray(), getQualifierOffset(),
444           getQualifierLength());
445       String timestamp = String.valueOf((getTimestamp()));
446       return row + "/" + family + (family != null && family.length() > 0 ? ":" : "") + qualifier
447           + "/" + timestamp + "/" + Type.codeToType(type);
448     }
449 
450     @Override
451     public long heapSize() {
452       return FIXED_OVERHEAD + rowLength + famLength + qualLength + valLength + tagsLength;
453     }
454   }
455 }