View Javadoc

1   /**
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  
20  package org.apache.hadoop.hbase.regionserver;
21  
22  import java.io.IOException;
23  import java.util.Comparator;
24  import java.util.HashSet;
25  import java.util.List;
26  import java.util.PriorityQueue;
27  import java.util.Set;
28  
29  import org.apache.hadoop.hbase.Cell;
30  import org.apache.hadoop.hbase.CellComparator;
31  import org.apache.hadoop.hbase.classification.InterfaceAudience;
32  import org.apache.hadoop.hbase.regionserver.ScannerContext.NextState;
33  
34  /**
35   * Implements a heap merge across any number of KeyValueScanners.
36   * <p>
37   * Implements KeyValueScanner itself.
38   * <p>
39   * This class is used at the Region level to merge across Stores
40   * and at the Store level to merge across the memstore and StoreFiles.
41   * <p>
42   * In the Region case, we also need InternalScanner.next(List), so this class
43   * also implements InternalScanner.  WARNING: As is, if you try to use this
44   * as an InternalScanner at the Store level, you will get runtime exceptions.
45   */
46  @InterfaceAudience.Private
47  public class KeyValueHeap extends NonReversedNonLazyKeyValueScanner
48      implements KeyValueScanner, InternalScanner {
49    protected PriorityQueue<KeyValueScanner> heap = null;
50    // Holds the scanners when a ever a eager close() happens.  All such eagerly closed
51    // scans are collected and when the final scanner.close() happens will perform the
52    // actual close.
53    protected Set<KeyValueScanner> scannersForDelayedClose = new HashSet<KeyValueScanner>();
54  
55    /**
56     * The current sub-scanner, i.e. the one that contains the next key/value
57     * to return to the client. This scanner is NOT included in {@link #heap}
58     * (but we frequently add it back to the heap and pull the new winner out).
59     * We maintain an invariant that the current sub-scanner has already done
60     * a real seek, and that current.peek() is always a real key/value (or null)
61     * except for the fake last-key-on-row-column supplied by the multi-column
62     * Bloom filter optimization, which is OK to propagate to StoreScanner. In
63     * order to ensure that, always use {@link #pollRealKV()} to update current.
64     */
65    protected KeyValueScanner current = null;
66  
67    protected KVScannerComparator comparator;
68  
69    /**
70     * Constructor.  This KeyValueHeap will handle closing of passed in
71     * KeyValueScanners.
72     * @param scanners
73     * @param comparator
74     */
75    public KeyValueHeap(List<? extends KeyValueScanner> scanners,
76        CellComparator comparator) throws IOException {
77      this(scanners, new KVScannerComparator(comparator));
78    }
79  
80    /**
81     * Constructor.
82     * @param scanners
83     * @param comparator
84     * @throws IOException
85     */
86    KeyValueHeap(List<? extends KeyValueScanner> scanners,
87        KVScannerComparator comparator) throws IOException {
88      this.comparator = comparator;
89      if (!scanners.isEmpty()) {
90        this.heap = new PriorityQueue<KeyValueScanner>(scanners.size(),
91            this.comparator);
92        for (KeyValueScanner scanner : scanners) {
93          if (scanner.peek() != null) {
94            this.heap.add(scanner);
95          } else {
96            this.scannersForDelayedClose.add(scanner);
97          }
98        }
99        this.current = pollRealKV();
100     }
101   }
102 
103   public Cell peek() {
104     if (this.current == null) {
105       return null;
106     }
107     return this.current.peek();
108   }
109 
110   public Cell next()  throws IOException {
111     if(this.current == null) {
112       return null;
113     }
114     Cell kvReturn = this.current.next();
115     Cell kvNext = this.current.peek();
116     if (kvNext == null) {
117       this.scannersForDelayedClose.add(this.current);
118       this.current = null;
119       this.current = pollRealKV();
120     } else {
121       KeyValueScanner topScanner = this.heap.peek();
122       // no need to add current back to the heap if it is the only scanner left
123       if (topScanner != null && this.comparator.compare(kvNext, topScanner.peek()) >= 0) {
124         this.heap.add(this.current);
125         this.current = null;
126         this.current = pollRealKV();
127       }
128     }
129     return kvReturn;
130   }
131 
132   /**
133    * Gets the next row of keys from the top-most scanner.
134    * <p>
135    * This method takes care of updating the heap.
136    * <p>
137    * This can ONLY be called when you are using Scanners that implement InternalScanner as well as
138    * KeyValueScanner (a {@link StoreScanner}).
139    * @param result
140    * @return true if more rows exist after this one, false if scanner is done
141    */
142   @Override
143   public boolean next(List<Cell> result) throws IOException {
144     return next(result, NoLimitScannerContext.getInstance());
145   }
146 
147   @Override
148   public boolean next(List<Cell> result, ScannerContext scannerContext) throws IOException {
149     if (this.current == null) {
150       return scannerContext.setScannerState(NextState.NO_MORE_VALUES).hasMoreValues();
151     }
152     InternalScanner currentAsInternal = (InternalScanner)this.current;
153     boolean moreCells = currentAsInternal.next(result, scannerContext);
154     Cell pee = this.current.peek();
155 
156     /*
157      * By definition, any InternalScanner must return false only when it has no
158      * further rows to be fetched. So, we can close a scanner if it returns
159      * false. All existing implementations seem to be fine with this. It is much
160      * more efficient to close scanners which are not needed than keep them in
161      * the heap. This is also required for certain optimizations.
162      */
163 
164     if (pee == null || !moreCells) {
165       // add the scanner that is to be closed
166       this.scannersForDelayedClose.add(this.current);
167     } else {
168       this.heap.add(this.current);
169     }
170     this.current = null;
171     this.current = pollRealKV();
172     if (this.current == null) {
173       moreCells = scannerContext.setScannerState(NextState.NO_MORE_VALUES).hasMoreValues();
174     }
175     return moreCells;
176   }
177 
178   protected static class KVScannerComparator implements Comparator<KeyValueScanner> {
179     protected CellComparator kvComparator;
180     /**
181      * Constructor
182      * @param kvComparator
183      */
184     public KVScannerComparator(CellComparator kvComparator) {
185       this.kvComparator = kvComparator;
186     }
187     public int compare(KeyValueScanner left, KeyValueScanner right) {
188       int comparison = compare(left.peek(), right.peek());
189       if (comparison != 0) {
190         return comparison;
191       } else {
192         // Since both the keys are exactly the same, we break the tie in favor
193         // of the key which came latest.
194         long leftSequenceID = left.getSequenceID();
195         long rightSequenceID = right.getSequenceID();
196         if (leftSequenceID > rightSequenceID) {
197           return -1;
198         } else if (leftSequenceID < rightSequenceID) {
199           return 1;
200         } else {
201           return 0;
202         }
203       }
204     }
205     /**
206      * Compares two KeyValue
207      * @param left
208      * @param right
209      * @return less than 0 if left is smaller, 0 if equal etc..
210      */
211     public int compare(Cell left, Cell right) {
212       return this.kvComparator.compare(left, right);
213     }
214     /**
215      * @return KVComparator
216      */
217     public CellComparator getComparator() {
218       return this.kvComparator;
219     }
220   }
221 
222   public void close() {
223     for (KeyValueScanner scanner : this.scannersForDelayedClose) {
224       scanner.close();
225     }
226     this.scannersForDelayedClose.clear();
227     if (this.current != null) {
228       this.current.close();
229     }
230     if (this.heap != null) {
231       KeyValueScanner scanner;
232       while ((scanner = this.heap.poll()) != null) {
233         scanner.close();
234       }
235     }
236   }
237 
238   /**
239    * Seeks all scanners at or below the specified seek key.  If we earlied-out
240    * of a row, we may end up skipping values that were never reached yet.
241    * Rather than iterating down, we want to give the opportunity to re-seek.
242    * <p>
243    * As individual scanners may run past their ends, those scanners are
244    * automatically closed and removed from the heap.
245    * <p>
246    * This function (and {@link #reseek(Cell)}) does not do multi-column
247    * Bloom filter and lazy-seek optimizations. To enable those, call
248    * {@link #requestSeek(Cell, boolean, boolean)}.
249    * @param seekKey KeyValue to seek at or after
250    * @return true if KeyValues exist at or after specified key, false if not
251    * @throws IOException
252    */
253   @Override
254   public boolean seek(Cell seekKey) throws IOException {
255     return generalizedSeek(false,    // This is not a lazy seek
256                            seekKey,
257                            false,    // forward (false: this is not a reseek)
258                            false);   // Not using Bloom filters
259   }
260 
261   /**
262    * This function is identical to the {@link #seek(Cell)} function except
263    * that scanner.seek(seekKey) is changed to scanner.reseek(seekKey).
264    */
265   @Override
266   public boolean reseek(Cell seekKey) throws IOException {
267     return generalizedSeek(false,    // This is not a lazy seek
268                            seekKey,
269                            true,     // forward (true because this is reseek)
270                            false);   // Not using Bloom filters
271   }
272 
273   /**
274    * {@inheritDoc}
275    */
276   @Override
277   public boolean requestSeek(Cell key, boolean forward,
278       boolean useBloom) throws IOException {
279     return generalizedSeek(true, key, forward, useBloom);
280   }
281 
282   /**
283    * @param isLazy whether we are trying to seek to exactly the given row/col.
284    *          Enables Bloom filter and most-recent-file-first optimizations for
285    *          multi-column get/scan queries.
286    * @param seekKey key to seek to
287    * @param forward whether to seek forward (also known as reseek)
288    * @param useBloom whether to optimize seeks using Bloom filters
289    */
290   private boolean generalizedSeek(boolean isLazy, Cell seekKey,
291       boolean forward, boolean useBloom) throws IOException {
292     if (!isLazy && useBloom) {
293       throw new IllegalArgumentException("Multi-column Bloom filter " +
294           "optimization requires a lazy seek");
295     }
296 
297     if (current == null) {
298       return false;
299     }
300 
301     KeyValueScanner scanner = current;
302     while (scanner != null) {
303       Cell topKey = scanner.peek();
304       if (comparator.getComparator().compare(seekKey, topKey) <= 0) {
305         // Top KeyValue is at-or-after Seek KeyValue. We only know that all
306         // scanners are at or after seekKey (because fake keys of
307         // scanners where a lazy-seek operation has been done are not greater
308         // than their real next keys) but we still need to enforce our
309         // invariant that the top scanner has done a real seek. This way
310         // StoreScanner and RegionScanner do not have to worry about fake keys.
311         heap.add(scanner);
312         current = pollRealKV();
313         return current != null;
314       }
315 
316       boolean seekResult;
317       if (isLazy && heap.size() > 0) {
318         // If there is only one scanner left, we don't do lazy seek.
319         seekResult = scanner.requestSeek(seekKey, forward, useBloom);
320       } else {
321         seekResult = NonLazyKeyValueScanner.doRealSeek(
322             scanner, seekKey, forward);
323       }
324 
325       if (!seekResult) {
326         this.scannersForDelayedClose.add(scanner);
327       } else {
328         heap.add(scanner);
329       }
330       scanner = heap.poll();
331       if (scanner == null) {
332         current = null;
333       }
334     }
335 
336     // Heap is returning empty, scanner is done
337     return false;
338   }
339 
340   /**
341    * Fetches the top sub-scanner from the priority queue, ensuring that a real
342    * seek has been done on it. Works by fetching the top sub-scanner, and if it
343    * has not done a real seek, making it do so (which will modify its top KV),
344    * putting it back, and repeating this until success. Relies on the fact that
345    * on a lazy seek we set the current key of a StoreFileScanner to a KV that
346    * is not greater than the real next KV to be read from that file, so the
347    * scanner that bubbles up to the top of the heap will have global next KV in
348    * this scanner heap if (1) it has done a real seek and (2) its KV is the top
349    * among all top KVs (some of which are fake) in the scanner heap.
350    */
351   protected KeyValueScanner pollRealKV() throws IOException {
352     KeyValueScanner kvScanner = heap.poll();
353     if (kvScanner == null) {
354       return null;
355     }
356 
357     while (kvScanner != null && !kvScanner.realSeekDone()) {
358       if (kvScanner.peek() != null) {
359         try {
360           kvScanner.enforceSeek();
361         } catch (IOException ioe) {
362           // Add the item to delayed close set in case it is leak from close
363           this.scannersForDelayedClose.add(kvScanner);
364           throw ioe;
365         }
366         Cell curKV = kvScanner.peek();
367         if (curKV != null) {
368           KeyValueScanner nextEarliestScanner = heap.peek();
369           if (nextEarliestScanner == null) {
370             // The heap is empty. Return the only possible scanner.
371             return kvScanner;
372           }
373 
374           // Compare the current scanner to the next scanner. We try to avoid
375           // putting the current one back into the heap if possible.
376           Cell nextKV = nextEarliestScanner.peek();
377           if (nextKV == null || comparator.compare(curKV, nextKV) < 0) {
378             // We already have the scanner with the earliest KV, so return it.
379             return kvScanner;
380           }
381 
382           // Otherwise, put the scanner back into the heap and let it compete
383           // against all other scanners (both those that have done a "real
384           // seek" and a "lazy seek").
385           heap.add(kvScanner);
386         } else {
387           // Close the scanner because we did a real seek and found out there
388           // are no more KVs.
389           this.scannersForDelayedClose.add(kvScanner);
390         }
391       } else {
392         // Close the scanner because it has already run out of KVs even before
393         // we had to do a real seek on it.
394         this.scannersForDelayedClose.add(kvScanner);
395       }
396       kvScanner = heap.poll();
397     }
398 
399     return kvScanner;
400   }
401 
402   /**
403    * @return the current Heap
404    */
405   public PriorityQueue<KeyValueScanner> getHeap() {
406     return this.heap;
407   }
408 
409   @Override
410   public long getSequenceID() {
411     return 0;
412   }
413 
414   KeyValueScanner getCurrentForTesting() {
415     return current;
416   }
417 
418   @Override
419   public Cell getNextIndexedKey() {
420     // here we return the next index key from the top scanner
421     return current == null ? null : current.getNextIndexedKey();
422   }
423 
424   @Override
425   public void shipped() throws IOException {
426     for (KeyValueScanner scanner : this.scannersForDelayedClose) {
427       scanner.close(); // There wont be further fetch of Cells from these scanners. Just close.
428     }
429     this.scannersForDelayedClose.clear();
430     if (this.current != null) {
431       this.current.shipped();
432     }
433     if (this.heap != null) {
434       for (KeyValueScanner scanner : this.heap) {
435         scanner.shipped();
436       }
437     }
438   }
439 }