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