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