001/**
002 *
003 * Licensed to the Apache Software Foundation (ASF) under one
004 * or more contributor license agreements.  See the NOTICE file
005 * distributed with this work for additional information
006 * regarding copyright ownership.  The ASF licenses this file
007 * to you under the Apache License, Version 2.0 (the
008 * "License"); you may not use this file except in compliance
009 * with the License.  You may obtain a copy of the License at
010 *
011 *     http://www.apache.org/licenses/LICENSE-2.0
012 *
013 * Unless required by applicable law or agreed to in writing, software
014 * distributed under the License is distributed on an "AS IS" BASIS,
015 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
016 * See the License for the specific language governing permissions and
017 * limitations under the License.
018 */
019package org.apache.hadoop.hbase.regionserver;
020
021import java.io.IOException;
022import java.util.Iterator;
023import java.util.SortedSet;
024
025import org.apache.commons.lang3.NotImplementedException;
026import org.apache.hadoop.fs.Path;
027import org.apache.hadoop.hbase.Cell;
028import org.apache.hadoop.hbase.PrivateCellUtil;
029import org.apache.yetus.audience.InterfaceAudience;
030import org.apache.hadoop.hbase.client.Scan;
031
032/**
033 * A scanner of a single memstore segment.
034 */
035@InterfaceAudience.Private
036public class SegmentScanner implements KeyValueScanner {
037
038
039  // the observed structure
040  protected final Segment segment;
041  // the highest relevant MVCC
042  private long readPoint;
043  // the current iterator that can be reinitialized by
044  // seek(), backwardSeek(), or reseek()
045  protected Iterator<Cell> iter;
046  // the pre-calculated cell to be returned by peek()
047  protected Cell current = null;
048  // or next()
049  // A flag represents whether could stop skipping KeyValues for MVCC
050  // if have encountered the next row. Only used for reversed scan
051  private boolean stopSkippingKVsIfNextRow = false;
052  // Stop skipping KeyValues for MVCC if finish this row. Only used for reversed scan
053  private Cell stopSkippingKVsRow;
054  // last iterated KVs by seek (to restore the iterator state after reseek)
055  private Cell last = null;
056
057  // flag to indicate if this scanner is closed
058  protected boolean closed = false;
059
060
061  /**
062   * Scanners are ordered from 0 (oldest) to newest in increasing order.
063   */
064  protected SegmentScanner(Segment segment, long readPoint) {
065    this.segment = segment;
066    this.readPoint = readPoint;
067    //increase the reference count so the underlying structure will not be de-allocated
068    this.segment.incScannerCount();
069    iter = segment.iterator();
070    // the initialization of the current is required for working with heap of SegmentScanners
071    updateCurrent();
072    if (current == null) {
073      // nothing to fetch from this scanner
074      close();
075    }
076  }
077
078  /**
079   * Look at the next Cell in this scanner, but do not iterate the scanner
080   * @return the currently observed Cell
081   */
082  @Override
083  public Cell peek() {          // sanity check, the current should be always valid
084    if (closed) {
085      return null;
086    }
087    if (current!=null && current.getSequenceId() > readPoint) {
088      throw new RuntimeException("current is invalid: read point is "+readPoint+", " +
089          "while current sequence id is " +current.getSequenceId());
090    }
091    return current;
092  }
093
094  /**
095   * Return the next Cell in this scanner, iterating the scanner
096   * @return the next Cell or null if end of scanner
097   */
098  @Override
099  public Cell next() throws IOException {
100    if (closed) {
101      return null;
102    }
103    Cell oldCurrent = current;
104    updateCurrent();                  // update the currently observed Cell
105    return oldCurrent;
106  }
107
108  /**
109   * Seek the scanner at or after the specified Cell.
110   * @param cell seek value
111   * @return true if scanner has values left, false if end of scanner
112   */
113  @Override
114  public boolean seek(Cell cell) throws IOException {
115    if (closed) {
116      return false;
117    }
118    if(cell == null) {
119      close();
120      return false;
121    }
122    // restart the iterator from new key
123    iter = getIterator(cell);
124    // last is going to be reinitialized in the next getNext() call
125    last = null;
126    updateCurrent();
127    return (current != null);
128  }
129
130  protected Iterator<Cell> getIterator(Cell cell) {
131    return segment.tailSet(cell).iterator();
132  }
133
134  /**
135   * Reseek the scanner at or after the specified KeyValue.
136   * This method is guaranteed to seek at or after the required key only if the
137   * key comes after the current position of the scanner. Should not be used
138   * to seek to a key which may come before the current position.
139   *
140   * @param cell seek value (should be non-null)
141   * @return true if scanner has values left, false if end of scanner
142   */
143  @Override
144  public boolean reseek(Cell cell) throws IOException {
145    if (closed) {
146      return false;
147    }
148    /*
149    See HBASE-4195 & HBASE-3855 & HBASE-6591 for the background on this implementation.
150    This code is executed concurrently with flush and puts, without locks.
151    The ideal implementation for performance would use the sub skip list implicitly
152    pointed by the iterator. Unfortunately the Java API does not offer a method to
153    get it. So we remember the last keys we iterated to and restore
154    the reseeked set to at least that point.
155    */
156    iter = getIterator(getHighest(cell, last));
157    updateCurrent();
158    return (current != null);
159  }
160
161  /**
162   * Seek the scanner at or before the row of specified Cell, it firstly
163   * tries to seek the scanner at or after the specified Cell, return if
164   * peek KeyValue of scanner has the same row with specified Cell,
165   * otherwise seek the scanner at the first Cell of the row which is the
166   * previous row of specified KeyValue
167   *
168   * @param key seek Cell
169   * @return true if the scanner is at the valid KeyValue, false if such Cell does not exist
170   */
171  @Override
172  public boolean backwardSeek(Cell key) throws IOException {
173    if (closed) {
174      return false;
175    }
176    seek(key);    // seek forward then go backward
177    if (peek() == null || segment.compareRows(peek(), key) > 0) {
178      return seekToPreviousRow(key);
179    }
180    return true;
181  }
182
183  /**
184   * Seek the scanner at the first Cell of the row which is the previous row
185   * of specified key
186   *
187   * @param cell seek value
188   * @return true if the scanner at the first valid Cell of previous row,
189   *     false if not existing such Cell
190   */
191  @Override
192  public boolean seekToPreviousRow(Cell cell) throws IOException {
193    if (closed) {
194      return false;
195    }
196    boolean keepSeeking;
197    Cell key = cell;
198    do {
199      Cell firstKeyOnRow = PrivateCellUtil.createFirstOnRow(key);
200      SortedSet<Cell> cellHead = segment.headSet(firstKeyOnRow);
201      Cell lastCellBeforeRow = cellHead.isEmpty() ? null : cellHead.last();
202      if (lastCellBeforeRow == null) {
203        current = null;
204        return false;
205      }
206      Cell firstKeyOnPreviousRow = PrivateCellUtil.createFirstOnRow(lastCellBeforeRow);
207      this.stopSkippingKVsIfNextRow = true;
208      this.stopSkippingKVsRow = firstKeyOnPreviousRow;
209      seek(firstKeyOnPreviousRow);
210      this.stopSkippingKVsIfNextRow = false;
211      if (peek() == null
212          || segment.getComparator().compareRows(peek(), firstKeyOnPreviousRow) > 0) {
213        keepSeeking = true;
214        key = firstKeyOnPreviousRow;
215        continue;
216      } else {
217        keepSeeking = false;
218      }
219    } while (keepSeeking);
220    return true;
221  }
222
223  /**
224   * Seek the scanner at the first KeyValue of last row
225   *
226   * @return true if scanner has values left, false if the underlying data is empty
227   */
228  @Override
229  public boolean seekToLastRow() throws IOException {
230    if (closed) {
231      return false;
232    }
233    Cell higherCell = segment.isEmpty() ? null : segment.last();
234    if (higherCell == null) {
235      return false;
236    }
237
238    Cell firstCellOnLastRow = PrivateCellUtil.createFirstOnRow(higherCell);
239
240    if (seek(firstCellOnLastRow)) {
241      return true;
242    } else {
243      return seekToPreviousRow(higherCell);
244    }
245  }
246
247
248  /**
249   * Close the KeyValue scanner.
250   */
251  @Override
252  public void close() {
253    if (closed) {
254      return;
255    }
256    getSegment().decScannerCount();
257    closed = true;
258  }
259
260  /**
261   * This functionality should be resolved in the higher level which is
262   * MemStoreScanner, currently returns true as default. Doesn't throw
263   * IllegalStateException in order not to change the signature of the
264   * overridden method
265   */
266  @Override
267  public boolean shouldUseScanner(Scan scan, HStore store, long oldestUnexpiredTS) {
268    return getSegment().shouldSeek(scan.getColumnFamilyTimeRange()
269            .getOrDefault(store.getColumnFamilyDescriptor().getName(), scan.getTimeRange()), oldestUnexpiredTS);
270  }
271
272  @Override
273  public boolean requestSeek(Cell c, boolean forward, boolean useBloom)
274      throws IOException {
275    return NonLazyKeyValueScanner.doRealSeek(this, c, forward);
276  }
277
278  /**
279   * This scanner is working solely on the in-memory MemStore and doesn't work on
280   * store files, MutableCellSetSegmentScanner always does the seek,
281   * therefore always returning true.
282   */
283  @Override
284  public boolean realSeekDone() {
285    return true;
286  }
287
288  /**
289   * This function should be never called on scanners that always do real seek operations (i.e. most
290   * of the scanners and also this one). The easiest way to achieve this is to call
291   * {@link #realSeekDone()} first.
292   */
293  @Override
294  public void enforceSeek() throws IOException {
295    throw new NotImplementedException("enforceSeek cannot be called on a SegmentScanner");
296  }
297
298  /**
299   * @return true if this is a file scanner. Otherwise a memory scanner is assumed.
300   */
301  @Override
302  public boolean isFileScanner() {
303    return false;
304  }
305
306  @Override
307  public Path getFilePath() {
308    return null;
309  }
310
311  /**
312   * @return the next key in the index (the key to seek to the next block)
313   *     if known, or null otherwise
314   *     Not relevant for in-memory scanner
315   */
316  @Override
317  public Cell getNextIndexedKey() {
318    return null;
319  }
320
321  /**
322   * Called after a batch of rows scanned (RPC) and set to be returned to client. Any in between
323   * cleanup can be done here. Nothing to be done for MutableCellSetSegmentScanner.
324   */
325  @Override
326  public void shipped() throws IOException {
327    // do nothing
328  }
329
330  //debug method
331  @Override
332  public String toString() {
333    String res = "Store segment scanner of type "+this.getClass().getName()+"; ";
334    res += "Scanner order " + getScannerOrder() + "; ";
335    res += getSegment().toString();
336    return res;
337  }
338
339  /********************* Private Methods **********************/
340
341  private Segment getSegment(){
342    return segment;
343  }
344
345  /**
346   * Private internal method for iterating over the segment,
347   * skipping the cells with irrelevant MVCC
348   */
349  protected void updateCurrent() {
350    Cell next = null;
351
352    try {
353      while (iter.hasNext()) {
354        next = iter.next();
355        if (next.getSequenceId() <= this.readPoint) {
356          current = next;
357          return;// skip irrelevant versions
358        }
359        // for backwardSeek() stay in the boundaries of a single row
360        if (stopSkippingKVsIfNextRow &&
361            segment.compareRows(next, stopSkippingKVsRow) > 0) {
362          current = null;
363          return;
364        }
365      } // end of while
366
367      current = null; // nothing found
368    } finally {
369      if (next != null) {
370        // in all cases, remember the last KV we iterated to, needed for reseek()
371        last = next;
372      }
373    }
374  }
375
376  /**
377   * Private internal method that returns the higher of the two key values, or null
378   * if they are both null
379   */
380  private Cell getHighest(Cell first, Cell second) {
381    if (first == null && second == null) {
382      return null;
383    }
384    if (first != null && second != null) {
385      int compare = segment.compare(first, second);
386      return (compare > 0 ? first : second);
387    }
388    return (first != null ? first : second);
389  }
390}