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