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  package org.apache.hadoop.hbase.regionserver;
20  
21  import java.util.NavigableMap;
22  import java.util.NavigableSet;
23  import java.util.TreeMap;
24  import java.util.TreeSet;
25  
26  import org.apache.hadoop.hbase.classification.InterfaceAudience;
27  import org.apache.hadoop.hbase.Cell;
28  import org.apache.hadoop.hbase.CellComparator;
29  import org.apache.hadoop.hbase.CellUtil;
30  import org.apache.hadoop.hbase.HConstants;
31  import org.apache.hadoop.hbase.KeyValue;
32  import org.apache.hadoop.hbase.util.Bytes;
33  
34  /**
35   * State and utility processing {@link HRegion#getClosestRowBefore(byte[], byte[])}.
36   * Like {@link ScanQueryMatcher} and {@link ScanDeleteTracker} but does not
37   * implement the {@link DeleteTracker} interface since state spans rows (There
38   * is no update nor reset method).
39   */
40  @InterfaceAudience.Private
41  class GetClosestRowBeforeTracker {
42    private final KeyValue targetkey;
43    // Any cell w/ a ts older than this is expired.
44    private final long now;
45    private final long oldestUnexpiredTs;
46    private Cell candidate = null;
47    private final CellComparator cellComparator;
48    // Flag for whether we're doing getclosest on a metaregion.
49    private final boolean metaregion;
50    // Offset and length into targetkey demarking table name (if in a metaregion).
51    private final int rowoffset;
52    private final int tablenamePlusDelimiterLength;
53  
54    // Deletes keyed by row.  Comparator compares on row portion of KeyValue only.
55    private final NavigableMap<Cell, NavigableSet<Cell>> deletes;
56  
57    /**
58     * @param c
59     * @param kv Presume first on row: i.e. empty column, maximum timestamp and
60     * a type of Type.Maximum
61     * @param ttl Time to live in ms for this Store
62     * @param metaregion True if this is hbase:meta or -ROOT- region.
63     */
64    GetClosestRowBeforeTracker(final CellComparator c, final KeyValue kv,
65        final long ttl, final boolean metaregion) {
66      super();
67      this.metaregion = metaregion;
68      this.targetkey = kv;
69      // If we are in a metaregion, then our table name is the prefix on the
70      // targetkey.
71      this.rowoffset = kv.getRowOffset();
72      int l = -1;
73      if (metaregion) {
74        l = Bytes.searchDelimiterIndex(kv.getRowArray(), rowoffset, kv.getRowLength(),
75          HConstants.DELIMITER) - this.rowoffset;
76      }
77      this.tablenamePlusDelimiterLength = metaregion? l + 1: -1;
78      this.now = System.currentTimeMillis();
79      this.oldestUnexpiredTs = now - ttl;
80      this.cellComparator = c;
81      this.deletes = new TreeMap<Cell, NavigableSet<Cell>>(new CellComparator.RowComparator());
82    }
83  
84    /*
85     * Add the specified KeyValue to the list of deletes.
86     * @param kv
87     */
88    private void addDelete(final Cell kv) {
89      NavigableSet<Cell> rowdeletes = this.deletes.get(kv);
90      if (rowdeletes == null) {
91        rowdeletes = new TreeSet<Cell>(this.cellComparator);
92        this.deletes.put(kv, rowdeletes);
93      }
94      rowdeletes.add(kv);
95    }
96  
97    /*
98     * @param kv Adds candidate if nearer the target than previous candidate.
99     * @return True if updated candidate.
100    */
101   private boolean addCandidate(final Cell kv) {
102     if (!isDeleted(kv) && isBetterCandidate(kv)) {
103       this.candidate = kv;
104       return true;
105     }
106     return false;
107   }
108 
109   boolean isBetterCandidate(final Cell contender) {
110     return this.candidate == null ||
111       (this.cellComparator.compareRows(this.candidate, contender) < 0 &&
112         this.cellComparator.compareRows(contender, this.targetkey) <= 0);
113   }
114 
115   /*
116    * Check if specified KeyValue buffer has been deleted by a previously
117    * seen delete.
118    * @param kv
119    * @return true is the specified KeyValue is deleted, false if not
120    */
121   private boolean isDeleted(final Cell kv) {
122     if (this.deletes.isEmpty()) return false;
123     NavigableSet<Cell> rowdeletes = this.deletes.get(kv);
124     if (rowdeletes == null || rowdeletes.isEmpty()) return false;
125     return isDeleted(kv, rowdeletes);
126   }
127 
128   /**
129    * Check if the specified KeyValue buffer has been deleted by a previously
130    * seen delete.
131    * @param kv
132    * @param ds
133    * @return True is the specified KeyValue is deleted, false if not
134    */
135   public boolean isDeleted(final Cell kv, final NavigableSet<Cell> ds) {
136     if (deletes == null || deletes.isEmpty()) return false;
137     for (Cell d: ds) {
138       long kvts = kv.getTimestamp();
139       long dts = d.getTimestamp();
140       if (CellUtil.isDeleteFamily(d)) {
141         if (kvts <= dts) return true;
142         continue;
143       }
144       // Check column
145       int ret = Bytes.compareTo(kv.getQualifierArray(), kv.getQualifierOffset(),
146           kv.getQualifierLength(),
147         d.getQualifierArray(), d.getQualifierOffset(), d.getQualifierLength());
148       if (ret <= -1) {
149         // This delete is for an earlier column.
150         continue;
151       } else if (ret >= 1) {
152         // Beyond this kv.
153         break;
154       }
155       // Check Timestamp
156       if (kvts > dts) return false;
157 
158       // Check Type
159       switch (KeyValue.Type.codeToType(d.getTypeByte())) {
160         case Delete: return kvts == dts;
161         case DeleteColumn: return true;
162         default: continue;
163       }
164     }
165     return false;
166   }
167 
168   /**
169    * @param cell
170    * @return true if the cell is expired
171    */
172   public boolean isExpired(final Cell cell) {
173     return cell.getTimestamp() < this.oldestUnexpiredTs ||
174       HStore.isCellTTLExpired(cell, this.oldestUnexpiredTs, this.now);
175   }
176 
177   /*
178    * Handle keys whose values hold deletes.
179    * Add to the set of deletes and then if the candidate keys contain any that
180    * might match, then check for a match and remove it.  Implies candidates
181    * is made with a Comparator that ignores key type.
182    * @param kv
183    * @return True if we removed <code>k</code> from <code>candidates</code>.
184    */
185   boolean handleDeletes(final Cell kv) {
186     addDelete(kv);
187     boolean deleted = false;
188     if (!hasCandidate()) return deleted;
189     if (isDeleted(this.candidate)) {
190       this.candidate = null;
191       deleted = true;
192     }
193     return deleted;
194   }
195 
196   /**
197    * Do right thing with passed key, add to deletes or add to candidates.
198    * @param kv
199    * @return True if we added a candidate
200    */
201   boolean handle(final Cell kv) {
202     if (CellUtil.isDelete(kv)) {
203       handleDeletes(kv);
204       return false;
205     }
206     return addCandidate(kv);
207   }
208 
209   /**
210    * @return True if has candidate
211    */
212   public boolean hasCandidate() {
213     return this.candidate != null;
214   }
215 
216   /**
217    * @return Best candidate or null.
218    */
219   public Cell getCandidate() {
220     return this.candidate;
221   }
222 
223   public KeyValue getTargetKey() {
224     return this.targetkey;
225   }
226 
227   /**
228    * @param kv Current kv
229    * @param firstOnRow on row kv.
230    * @return True if we went too far, past the target key.
231    */
232   boolean isTooFar(final Cell kv, final Cell firstOnRow) {
233     return this.cellComparator.compareRows(kv, firstOnRow) > 0;
234   }
235 
236   boolean isTargetTable(final Cell kv) {
237     if (!metaregion) return true;
238     // Compare start of keys row.  Compare including delimiter.  Saves having
239     // to calculate where tablename ends in the candidate kv.
240     return Bytes.compareTo(this.targetkey.getRowArray(), this.rowoffset,
241         this.tablenamePlusDelimiterLength,
242       kv.getRowArray(), kv.getRowOffset(), this.tablenamePlusDelimiterLength) == 0;
243   }
244 }