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.classification.InterfaceAudience;
24  import org.apache.hadoop.hbase.Cell;
25  import org.apache.hadoop.hbase.CellUtil;
26  import org.apache.hadoop.hbase.KeyValue;
27  import org.apache.hadoop.hbase.KeyValue.KVComparator;
28  import org.apache.hadoop.hbase.KeyValueUtil;
29  import org.apache.hadoop.hbase.codec.prefixtree.decode.DecoderFactory;
30  import org.apache.hadoop.hbase.codec.prefixtree.decode.PrefixTreeArraySearcher;
31  import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellScannerPosition;
32  import org.apache.hadoop.hbase.io.encoding.DataBlockEncoder.EncodedSeeker;
33  
34  /**
35   * These methods have the same definition as any implementation of the EncodedSeeker.
36   *
37   * In the future, the EncodedSeeker could be modified to work with the Cell interface directly.  It
38   * currently returns a new KeyValue object each time getKeyValue is called.  This is not horrible,
39   * but in order to create a new KeyValue object, we must first allocate a new byte[] and copy in
40   * the data from the PrefixTreeCell.  It is somewhat heavyweight right now.
41   */
42  @InterfaceAudience.Private
43  public class PrefixTreeSeeker implements EncodedSeeker {
44  
45    protected ByteBuffer block;
46    protected boolean includeMvccVersion;
47    protected PrefixTreeArraySearcher ptSearcher;
48    protected boolean movedToPrevious = false;
49  
50    public PrefixTreeSeeker(boolean includeMvccVersion) {
51      this.includeMvccVersion = includeMvccVersion;
52    }
53  
54    @Override
55    public void setCurrentBuffer(ByteBuffer fullBlockBuffer) {
56      block = fullBlockBuffer;
57      ptSearcher = DecoderFactory.checkOut(block, includeMvccVersion);
58      rewind();
59    }
60  
61    /**
62     * Currently unused.
63     * <p/>
64     * TODO performance leak. should reuse the searchers. hbase does not currently have a hook where
65     * this can be called
66     */
67    public void releaseCurrentSearcher(){
68      DecoderFactory.checkIn(ptSearcher);
69    }
70  
71  
72    @Override
73    public ByteBuffer getKeyDeepCopy() {
74      return KeyValueUtil.copyKeyToNewByteBuffer(ptSearcher.current());
75    }
76  
77  
78    @Override
79    public ByteBuffer getValueShallowCopy() {
80      return CellUtil.getValueBufferShallowCopy(ptSearcher.current());
81    }
82  
83    /**
84     * currently must do deep copy into new array
85     */
86    @Override
87    public ByteBuffer getKeyValueBuffer() {
88      return KeyValueUtil.copyToNewByteBuffer(ptSearcher.current());
89    }
90  
91    /**
92     * currently must do deep copy into new array
93     */
94    @Override
95    public KeyValue getKeyValue() {
96      if (ptSearcher.current() == null) {
97        return null;
98      }
99      return KeyValueUtil.copyToNewKeyValue(ptSearcher.current());
100   }
101 
102   /**
103    * Currently unused.
104    * <p/>
105    * A nice, lightweight reference, though the underlying cell is transient. This method may return
106    * the same reference to the backing PrefixTreeCell repeatedly, while other implementations may
107    * return a different reference for each Cell.
108    * <p/>
109    * The goal will be to transition the upper layers of HBase, like Filters and KeyValueHeap, to
110    * use this method instead of the getKeyValue() methods above.
111    */
112   public Cell get() {
113     return ptSearcher.current();
114   }
115 
116   @Override
117   public void rewind() {
118     ptSearcher.positionAtFirstCell();
119   }
120 
121   @Override
122   public boolean next() {
123     boolean advance = ptSearcher.advance();
124     if (ptSearcher.hasMovedToPreviousAsPartOfSeek()) {
125       ptSearcher.setMovedToPreviousAsPartOfSeek(false);
126     }
127     return advance;
128   }
129 
130 //  @Override
131   public boolean advance() {
132     return ptSearcher.advance();
133   }
134 
135 
136   private static final boolean USE_POSITION_BEFORE = false;
137 
138   /**
139    * Seek forward only (should be called reseekToKeyInBlock?).
140    * <p/>
141    * If the exact key is found look at the seekBefore variable and:<br/>
142    * - if true: go to the previous key if it's true<br/>
143    * - if false: stay on the exact key
144    * <p/>
145    * If the exact key is not found, then go to the previous key *if possible*, but remember to
146    * leave the scanner in a valid state if possible.
147    * <p/>
148    * @param keyOnlyBytes KeyValue format of a Cell's key at which to position the seeker
149    * @param offset offset into the keyOnlyBytes array
150    * @param length number of bytes of the keyOnlyBytes array to use
151    * @param forceBeforeOnExactMatch if an exact match is found and seekBefore=true, back up 1 Cell
152    * @return 0 if the seeker is on the exact key<br/>
153    *         1 if the seeker is not on the key for any reason, including seekBefore being true
154    */
155   @Override
156   public int seekToKeyInBlock(byte[] keyOnlyBytes, int offset, int length,
157       boolean forceBeforeOnExactMatch) {
158     if (USE_POSITION_BEFORE) {
159       return seekToOrBeforeUsingPositionAtOrBefore(keyOnlyBytes, offset, length,
160           forceBeforeOnExactMatch);
161     } else {
162       return seekToOrBeforeUsingPositionAtOrAfter(keyOnlyBytes, offset, length,
163           forceBeforeOnExactMatch);
164     }
165   }
166 
167   /*
168    * Support both of these options since the underlying PrefixTree supports both.  Possibly
169    * expand the EncodedSeeker to utilize them both.
170    */
171 
172   protected int seekToOrBeforeUsingPositionAtOrBefore(byte[] keyOnlyBytes, int offset, int length,
173       boolean seekBefore){
174     // this does a deep copy of the key byte[] because the CellSearcher interface wants a Cell
175     KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
176 
177     return seekToOrBeforeUsingPositionAtOrBefore(kv, seekBefore);
178   }
179 
180   /*
181    * Support both of these options since the underlying PrefixTree supports
182    * both. Possibly expand the EncodedSeeker to utilize them both.
183    */
184 
185   protected int seekToOrBeforeUsingPositionAtOrBefore(Cell kv, boolean seekBefore) {
186     // this does a deep copy of the key byte[] because the CellSearcher
187     // interface wants a Cell
188     CellScannerPosition position = ptSearcher.seekForwardToOrBefore(kv);
189 
190     if (CellScannerPosition.AT == position) {
191       if (seekBefore) {
192         ptSearcher.previous();
193         return 1;
194       }
195       return 0;
196     }
197 
198     return 1;
199   }
200 
201   protected int seekToOrBeforeUsingPositionAtOrAfter(byte[] keyOnlyBytes, int offset, int length,
202       boolean seekBefore) {
203     // this does a deep copy of the key byte[] because the CellSearcher
204     // interface wants a Cell
205     KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length);
206     return seekToOrBeforeUsingPositionAtOrAfter(kv, seekBefore);
207   }
208 
209   protected int seekToOrBeforeUsingPositionAtOrAfter(Cell kv, boolean seekBefore) {
210     // should probably switch this to use the seekForwardToOrBefore method
211     CellScannerPosition position = ptSearcher.seekForwardToOrAfter(kv);
212 
213     if (CellScannerPosition.AT == position) {
214       if (seekBefore) {
215         // We need not set movedToPrevious because the intention is to seekBefore
216         ptSearcher.previous();
217         return 1;
218       }
219       return 0;
220 
221     }
222 
223     if (CellScannerPosition.AFTER == position) {
224       if (!ptSearcher.isBeforeFirst()) {
225         ptSearcher.previous();
226         ptSearcher.setMovedToPreviousAsPartOfSeek(true);
227       }
228       return 1;
229     }
230 
231     if (position == CellScannerPosition.AFTER_LAST) {
232       if (seekBefore) {
233         ptSearcher.previous();
234       }
235       return 1;
236     }
237 
238     throw new RuntimeException("unexpected CellScannerPosition:" + position);
239   }
240 
241   @Override
242   public int compareKey(KVComparator comparator, byte[] key, int offset, int length) {
243     // can't optimize this, make a copy of the key
244     ByteBuffer bb = getKeyDeepCopy();
245     return comparator.compareFlatKey(key, offset, length, bb.array(), bb.arrayOffset(), bb.limit());
246   }
247 
248   @Override
249   public int seekToKeyInBlock(Cell key, boolean forceBeforeOnExactMatch) {
250     if (USE_POSITION_BEFORE) {
251       return seekToOrBeforeUsingPositionAtOrBefore(key, forceBeforeOnExactMatch);
252     }else{
253       return seekToOrBeforeUsingPositionAtOrAfter(key, forceBeforeOnExactMatch);
254     }
255   }
256 
257   @Override
258   public int compareKey(KVComparator comparator, Cell key) {
259     ByteBuffer bb = getKeyDeepCopy();
260     return comparator.compare(key,
261         new KeyValue.KeyOnlyKeyValue(bb.array(), bb.arrayOffset(), bb.limit()));
262   }
263 }