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