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