001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, software 013 * distributed under the License is distributed on an "AS IS" BASIS, 014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 015 * See the License for the specific language governing permissions and 016 * limitations under the License. 017 */ 018package org.apache.hadoop.hbase.regionserver.querymatcher; 019 020import java.io.IOException; 021import java.util.Iterator; 022import java.util.NavigableSet; 023import org.apache.hadoop.hbase.Cell; 024import org.apache.hadoop.hbase.CellComparator; 025import org.apache.hadoop.hbase.CellUtil; 026import org.apache.hadoop.hbase.HConstants; 027import org.apache.hadoop.hbase.KeyValue; 028import org.apache.hadoop.hbase.KeyValue.Type; 029import org.apache.hadoop.hbase.KeyValueUtil; 030import org.apache.hadoop.hbase.PrivateCellUtil; 031import org.apache.hadoop.hbase.PrivateConstants; 032import org.apache.hadoop.hbase.Tag; 033import org.apache.hadoop.hbase.TagType; 034import org.apache.hadoop.hbase.client.Scan; 035import org.apache.hadoop.hbase.filter.Filter; 036import org.apache.hadoop.hbase.regionserver.RegionCoprocessorHost; 037import org.apache.hadoop.hbase.regionserver.ScanInfo; 038import org.apache.hadoop.hbase.regionserver.ShipperListener; 039import org.apache.hadoop.hbase.regionserver.querymatcher.DeleteTracker.DeleteResult; 040import org.apache.hadoop.hbase.security.visibility.VisibilityNewVersionBehaivorTracker; 041import org.apache.hadoop.hbase.security.visibility.VisibilityScanDeleteTracker; 042import org.apache.hadoop.hbase.util.Bytes; 043import org.apache.hadoop.hbase.util.Pair; 044import org.apache.yetus.audience.InterfaceAudience; 045 046/** 047 * A query matcher that is specifically designed for the scan case. 048 */ 049@InterfaceAudience.Private 050public abstract class ScanQueryMatcher implements ShipperListener { 051 052 /** 053 * {@link #match} return codes. These instruct the scanner moving through memstores and StoreFiles 054 * what to do with the current KeyValue. 055 * <p> 056 * Additionally, this contains "early-out" language to tell the scanner to move on to the next 057 * File (memstore or Storefile), or to return immediately. 058 */ 059 public static enum MatchCode { 060 /** 061 * Include KeyValue in the returned result 062 */ 063 INCLUDE, 064 065 /** 066 * Do not include KeyValue in the returned result 067 */ 068 SKIP, 069 070 /** 071 * Do not include, jump to next StoreFile or memstore (in time order) 072 */ 073 NEXT, 074 075 /** 076 * Do not include, return current result 077 */ 078 DONE, 079 080 /** 081 * These codes are used by the ScanQueryMatcher 082 */ 083 084 /** 085 * Done with the row, seek there. 086 */ 087 SEEK_NEXT_ROW, 088 089 /** 090 * Done with column, seek to next. 091 */ 092 SEEK_NEXT_COL, 093 094 /** 095 * Done with scan, thanks to the row filter. 096 */ 097 DONE_SCAN, 098 099 /** 100 * Seek to next key which is given as hint. 101 */ 102 SEEK_NEXT_USING_HINT, 103 104 /** 105 * Include KeyValue and done with column, seek to next. 106 */ 107 INCLUDE_AND_SEEK_NEXT_COL, 108 109 /** 110 * Include KeyValue and done with row, seek to next. 111 */ 112 INCLUDE_AND_SEEK_NEXT_ROW, 113 } 114 115 /** Row comparator for the region this query is for */ 116 protected final CellComparator rowComparator; 117 118 /** Key to seek to in memstore and StoreFiles */ 119 protected final Cell startKey; 120 121 /** Keeps track of columns and versions */ 122 protected final ColumnTracker columns; 123 124 /** The oldest timestamp we are interested in, based on TTL */ 125 protected final long oldestUnexpiredTS; 126 127 protected final long now; 128 129 /** Row the query is on */ 130 protected Cell currentRow; 131 132 protected ScanQueryMatcher(Cell startKey, ScanInfo scanInfo, ColumnTracker columns, 133 long oldestUnexpiredTS, long now) { 134 this.rowComparator = scanInfo.getComparator(); 135 this.startKey = startKey; 136 this.oldestUnexpiredTS = oldestUnexpiredTS; 137 this.now = now; 138 this.columns = columns; 139 } 140 141 /** 142 * nn * @return true if the cell is expired 143 */ 144 private static boolean isCellTTLExpired(final Cell cell, final long oldestTimestamp, 145 final long now) { 146 // Look for a TTL tag first. Use it instead of the family setting if 147 // found. If a cell has multiple TTLs, resolve the conflict by using the 148 // first tag encountered. 149 Iterator<Tag> i = PrivateCellUtil.tagsIterator(cell); 150 while (i.hasNext()) { 151 Tag t = i.next(); 152 if (TagType.TTL_TAG_TYPE == t.getType()) { 153 // Unlike in schema cell TTLs are stored in milliseconds, no need 154 // to convert 155 long ts = cell.getTimestamp(); 156 assert t.getValueLength() == Bytes.SIZEOF_LONG; 157 long ttl = Tag.getValueAsLong(t); 158 if (ts + ttl < now) { 159 return true; 160 } 161 // Per cell TTLs cannot extend lifetime beyond family settings, so 162 // fall through to check that 163 break; 164 } 165 } 166 return false; 167 } 168 169 /** 170 * Check before the delete logic. 171 * @return null means continue. 172 */ 173 protected final MatchCode preCheck(Cell cell) { 174 if (currentRow == null) { 175 // Since the curCell is null it means we are already sure that we have moved over to the next 176 // row 177 return MatchCode.DONE; 178 } 179 // if row key is changed, then we know that we have moved over to the next row 180 if (rowComparator.compareRows(currentRow, cell) != 0) { 181 return MatchCode.DONE; 182 } 183 184 if (this.columns.done()) { 185 return MatchCode.SEEK_NEXT_ROW; 186 } 187 188 long timestamp = cell.getTimestamp(); 189 // check if this is a fake cell. The fake cell is an optimization, we should make the scanner 190 // seek to next column or next row. See StoreFileScanner.requestSeek for more details. 191 // check for early out based on timestamp alone 192 if (timestamp == PrivateConstants.OLDEST_TIMESTAMP || columns.isDone(timestamp)) { 193 return columns.getNextRowOrNextColumn(cell); 194 } 195 // check if the cell is expired by cell TTL 196 if (isCellTTLExpired(cell, this.oldestUnexpiredTS, this.now)) { 197 return MatchCode.SKIP; 198 } 199 return null; 200 } 201 202 protected final MatchCode checkDeleted(DeleteTracker deletes, Cell cell) { 203 if (deletes.isEmpty() && !(deletes instanceof NewVersionBehaviorTracker)) { 204 return null; 205 } 206 // MvccSensitiveTracker always need check all cells to save some infos. 207 DeleteResult deleteResult = deletes.isDeleted(cell); 208 switch (deleteResult) { 209 case FAMILY_DELETED: 210 case COLUMN_DELETED: 211 if (!(deletes instanceof NewVersionBehaviorTracker)) { 212 // MvccSensitive can not seek to next because the Put with lower ts may have higher mvcc 213 return columns.getNextRowOrNextColumn(cell); 214 } 215 case VERSION_DELETED: 216 case FAMILY_VERSION_DELETED: 217 case VERSION_MASKED: 218 return MatchCode.SKIP; 219 case NOT_DELETED: 220 return null; 221 default: 222 throw new RuntimeException("Unexpected delete result: " + deleteResult); 223 } 224 } 225 226 /** 227 * Determines if the caller should do one of several things: 228 * <ul> 229 * <li>seek/skip to the next row (MatchCode.SEEK_NEXT_ROW)</li> 230 * <li>seek/skip to the next column (MatchCode.SEEK_NEXT_COL)</li> 231 * <li>include the current KeyValue (MatchCode.INCLUDE)</li> 232 * <li>ignore the current KeyValue (MatchCode.SKIP)</li> 233 * <li>got to the next row (MatchCode.DONE)</li> 234 * </ul> 235 * @param cell KeyValue to check 236 * @return The match code instance. 237 * @throws IOException in case there is an internal consistency problem caused by a data 238 * corruption. 239 */ 240 public abstract MatchCode match(Cell cell) throws IOException; 241 242 /** Returns the start key */ 243 public Cell getStartKey() { 244 return startKey; 245 } 246 247 /** Returns whether there is an null column in the query */ 248 public abstract boolean hasNullColumnInQuery(); 249 250 /** Returns a cell represent the current row */ 251 public Cell currentRow() { 252 return currentRow; 253 } 254 255 /** 256 * Make {@link #currentRow()} return null. 257 */ 258 public void clearCurrentRow() { 259 currentRow = null; 260 } 261 262 protected abstract void reset(); 263 264 /** 265 * Set the row when there is change in row n 266 */ 267 public void setToNewRow(Cell currentRow) { 268 this.currentRow = currentRow; 269 columns.reset(); 270 reset(); 271 } 272 273 public abstract boolean isUserScan(); 274 275 /** 276 * @return Returns false if we know there are no more rows to be scanned (We've reached the 277 * <code>stopRow</code> or we are scanning on row only because this Scan is for a Get, 278 * etc. 279 */ 280 public abstract boolean moreRowsMayExistAfter(Cell cell); 281 282 public Cell getKeyForNextColumn(Cell cell) { 283 // We aren't sure whether any DeleteFamily cells exist, so we can't skip to next column. 284 // TODO: Current way disable us to seek to next column quickly. Is there any better solution? 285 // see HBASE-18471 for more details 286 // see TestFromClientSide3#testScanAfterDeletingSpecifiedRow 287 // see TestFromClientSide3#testScanAfterDeletingSpecifiedRowV2 288 if (cell.getQualifierLength() == 0) { 289 Cell nextKey = PrivateCellUtil.createNextOnRowCol(cell); 290 if (nextKey != cell) { 291 return nextKey; 292 } 293 // The cell is at the end of row/family/qualifier, so it is impossible to find any 294 // DeleteFamily cells. 295 // Let us seek to next column. 296 } 297 ColumnCount nextColumn = columns.getColumnHint(); 298 if (nextColumn == null) { 299 return PrivateCellUtil.createLastOnRowCol(cell); 300 } else { 301 return PrivateCellUtil.createFirstOnRowCol(cell, nextColumn.getBuffer(), 302 nextColumn.getOffset(), nextColumn.getLength()); 303 } 304 } 305 306 /** 307 * @param nextIndexed the key of the next entry in the block index (if any) 308 * @param currentCell The Cell we're using to calculate the seek key 309 * @return result of the compare between the indexed key and the key portion of the passed cell 310 */ 311 public int compareKeyForNextRow(Cell nextIndexed, Cell currentCell) { 312 return PrivateCellUtil.compareKeyBasedOnColHint(rowComparator, nextIndexed, currentCell, 0, 0, 313 null, 0, 0, PrivateConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode()); 314 } 315 316 /** 317 * @param nextIndexed the key of the next entry in the block index (if any) 318 * @param currentCell The Cell we're using to calculate the seek key 319 * @return result of the compare between the indexed key and the key portion of the passed cell 320 */ 321 public int compareKeyForNextColumn(Cell nextIndexed, Cell currentCell) { 322 ColumnCount nextColumn = columns.getColumnHint(); 323 if (nextColumn == null) { 324 return PrivateCellUtil.compareKeyBasedOnColHint(rowComparator, nextIndexed, currentCell, 0, 0, 325 null, 0, 0, PrivateConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode()); 326 } else { 327 return PrivateCellUtil.compareKeyBasedOnColHint(rowComparator, nextIndexed, currentCell, 328 currentCell.getFamilyOffset(), currentCell.getFamilyLength(), nextColumn.getBuffer(), 329 nextColumn.getOffset(), nextColumn.getLength(), HConstants.LATEST_TIMESTAMP, 330 Type.Maximum.getCode()); 331 } 332 } 333 334 /** Returns the Filter */ 335 public abstract Filter getFilter(); 336 337 /** 338 * Delegate to {@link Filter#getNextCellHint(Cell)}. If no filter, return {@code null}. 339 */ 340 public abstract Cell getNextKeyHint(Cell cell) throws IOException; 341 342 @Override 343 public void beforeShipped() throws IOException { 344 if (this.currentRow != null) { 345 this.currentRow = PrivateCellUtil.createFirstOnRow(CellUtil.copyRow(this.currentRow)); 346 } 347 if (columns != null) { 348 columns.beforeShipped(); 349 } 350 } 351 352 protected static Cell createStartKeyFromRow(byte[] startRow, ScanInfo scanInfo) { 353 return PrivateCellUtil.createFirstDeleteFamilyCellOnRow(startRow, scanInfo.getFamily()); 354 } 355 356 protected static Pair<DeleteTracker, ColumnTracker> getTrackers(RegionCoprocessorHost host, 357 NavigableSet<byte[]> columns, ScanInfo scanInfo, long oldestUnexpiredTS, Scan userScan) 358 throws IOException { 359 int resultMaxVersion = scanInfo.getMaxVersions(); 360 int maxVersionToCheck = resultMaxVersion; 361 if (userScan != null) { 362 if (userScan.isRaw()) { 363 resultMaxVersion = userScan.getMaxVersions(); 364 maxVersionToCheck = userScan.hasFilter() ? Integer.MAX_VALUE : resultMaxVersion; 365 } else { 366 resultMaxVersion = Math.min(userScan.getMaxVersions(), scanInfo.getMaxVersions()); 367 maxVersionToCheck = userScan.hasFilter() ? scanInfo.getMaxVersions() : resultMaxVersion; 368 } 369 } 370 371 DeleteTracker deleteTracker; 372 if (scanInfo.isNewVersionBehavior() && (userScan == null || !userScan.isRaw())) { 373 deleteTracker = new NewVersionBehaviorTracker(columns, scanInfo.getComparator(), 374 scanInfo.getMinVersions(), scanInfo.getMaxVersions(), resultMaxVersion, oldestUnexpiredTS); 375 } else { 376 deleteTracker = new ScanDeleteTracker(scanInfo.getComparator()); 377 } 378 if (host != null) { 379 deleteTracker = host.postInstantiateDeleteTracker(deleteTracker); 380 if (deleteTracker instanceof VisibilityScanDeleteTracker && scanInfo.isNewVersionBehavior()) { 381 deleteTracker = new VisibilityNewVersionBehaivorTracker(columns, scanInfo.getComparator(), 382 scanInfo.getMinVersions(), scanInfo.getMaxVersions(), resultMaxVersion, 383 oldestUnexpiredTS); 384 } 385 } 386 387 ColumnTracker columnTracker; 388 389 if (deleteTracker instanceof NewVersionBehaviorTracker) { 390 columnTracker = (NewVersionBehaviorTracker) deleteTracker; 391 } else if (columns == null || columns.size() == 0) { 392 columnTracker = new ScanWildcardColumnTracker(scanInfo.getMinVersions(), maxVersionToCheck, 393 oldestUnexpiredTS, scanInfo.getComparator()); 394 } else { 395 columnTracker = new ExplicitColumnTracker(columns, scanInfo.getMinVersions(), 396 maxVersionToCheck, oldestUnexpiredTS); 397 } 398 return new Pair<>(deleteTracker, columnTracker); 399 } 400 401 // Used only for testing purposes 402 static MatchCode checkColumn(ColumnTracker columnTracker, byte[] bytes, int offset, int length, 403 long ttl, byte type, boolean ignoreCount) throws IOException { 404 KeyValue kv = KeyValueUtil.createFirstOnRow(HConstants.EMPTY_BYTE_ARRAY, 0, 0, 405 HConstants.EMPTY_BYTE_ARRAY, 0, 0, bytes, offset, length); 406 MatchCode matchCode = columnTracker.checkColumn(kv, type); 407 if (matchCode == MatchCode.INCLUDE) { 408 return columnTracker.checkVersions(kv, ttl, type, ignoreCount); 409 } 410 return matchCode; 411 } 412}