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