View Javadoc

1   /*
2    * Copyright 2009 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.regionserver;
21  
22  import java.util.NavigableMap;
23  import java.util.NavigableSet;
24  import java.util.TreeMap;
25  import java.util.TreeSet;
26  
27  import org.apache.hadoop.hbase.HRegionInfo;
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  class GetClosestRowBeforeTracker {
39    private final KeyValue targetkey;
40    // Any cell w/ a ts older than this is expired.
41    private final long oldestts;
42    private KeyValue candidate = null;
43    private final KVComparator kvcomparator;
44    // Flag for whether we're doing getclosest on a metaregion.
45    private final boolean metaregion;
46    // Offset and length into targetkey demarking table name (if in a metaregion).
47    private final int rowoffset;
48    private final int tablenamePlusDelimiterLength;
49  
50    // Deletes keyed by row.  Comparator compares on row portion of KeyValue only.
51    private final NavigableMap<KeyValue, NavigableSet<KeyValue>> deletes;
52  
53    /**
54     * @param c
55     * @param kv Presume first on row: i.e. empty column, maximum timestamp and
56     * a type of Type.Maximum
57     * @param ttl Time to live in ms for this Store
58     * @param metaregion True if this is .META. or -ROOT- region.
59     */
60    GetClosestRowBeforeTracker(final KVComparator c, final KeyValue kv,
61        final long ttl, final boolean metaregion) {
62      super();
63      this.metaregion = metaregion;
64      this.targetkey = kv;
65      // If we are in a metaregion, then our table name is the prefix on the
66      // targetkey.
67      this.rowoffset = kv.getRowOffset();
68      int l = -1;
69      if (metaregion) {
70        l = KeyValue.getDelimiter(kv.getBuffer(), rowoffset, kv.getRowLength(),
71          HRegionInfo.DELIMITER) - this.rowoffset;
72      }
73      this.tablenamePlusDelimiterLength = metaregion? l + 1: -1;
74      this.oldestts = System.currentTimeMillis() - ttl;
75      this.kvcomparator = c;
76      KeyValue.RowComparator rc = new KeyValue.RowComparator(this.kvcomparator);
77      this.deletes = new TreeMap<KeyValue, NavigableSet<KeyValue>>(rc);
78    }
79  
80    /**
81     * @param kv
82     * @return True if this <code>kv</code> is expired.
83     */
84    boolean isExpired(final KeyValue kv) {
85      return Store.isExpired(kv, this.oldestts);
86    }
87  
88    /*
89     * Add the specified KeyValue to the list of deletes.
90     * @param kv
91     */
92    private void addDelete(final KeyValue kv) {
93      NavigableSet<KeyValue> rowdeletes = this.deletes.get(kv);
94      if (rowdeletes == null) {
95        rowdeletes = new TreeSet<KeyValue>(this.kvcomparator);
96        this.deletes.put(kv, rowdeletes);
97      }
98      rowdeletes.add(kv);
99    }
100 
101   /*
102    * @param kv Adds candidate if nearer the target than previous candidate.
103    * @return True if updated candidate.
104    */
105   private boolean addCandidate(final KeyValue kv) {
106     if (!isDeleted(kv) && isBetterCandidate(kv)) {
107       this.candidate = kv;
108       return true;
109     }
110     return false;
111   }
112 
113   boolean isBetterCandidate(final KeyValue contender) {
114     return this.candidate == null ||
115       (this.kvcomparator.compareRows(this.candidate, contender) < 0 &&
116         this.kvcomparator.compareRows(contender, this.targetkey) <= 0);
117   }
118 
119   /*
120    * Check if specified KeyValue buffer has been deleted by a previously
121    * seen delete.
122    * @param kv
123    * @return true is the specified KeyValue is deleted, false if not
124    */
125   private boolean isDeleted(final KeyValue kv) {
126     if (this.deletes.isEmpty()) return false;
127     NavigableSet<KeyValue> rowdeletes = this.deletes.get(kv);
128     if (rowdeletes == null || rowdeletes.isEmpty()) return false;
129     return isDeleted(kv, rowdeletes);
130   }
131 
132   /**
133    * Check if the specified KeyValue buffer has been deleted by a previously
134    * seen delete.
135    * @param kv
136    * @param ds
137    * @return True is the specified KeyValue is deleted, false if not
138    */
139   public boolean isDeleted(final KeyValue kv, final NavigableSet<KeyValue> ds) {
140     if (deletes == null || deletes.isEmpty()) return false;
141     for (KeyValue d: ds) {
142       long kvts = kv.getTimestamp();
143       long dts = d.getTimestamp();
144       if (d.isDeleteFamily()) {
145         if (kvts <= dts) return true;
146         continue;
147       }
148       // Check column
149       int ret = Bytes.compareTo(kv.getBuffer(), kv.getQualifierOffset(),
150           kv.getQualifierLength(),
151         d.getBuffer(), d.getQualifierOffset(), d.getQualifierLength());
152       if (ret <= -1) {
153         // This delete is for an earlier column.
154         continue;
155       } else if (ret >= 1) {
156         // Beyond this kv.
157         break;
158       }
159       // Check Timestamp
160       if (kvts > dts) return false;
161 
162       // Check Type
163       switch (KeyValue.Type.codeToType(d.getType())) {
164         case Delete: return kvts == dts;
165         case DeleteColumn: return true;
166         default: continue;
167       }
168     }
169     return false;
170   }
171 
172   /*
173    * Handle keys whose values hold deletes.
174    * Add to the set of deletes and then if the candidate keys contain any that
175    * might match, then check for a match and remove it.  Implies candidates
176    * is made with a Comparator that ignores key type.
177    * @param kv
178    * @return True if we removed <code>k</code> from <code>candidates</code>.
179    */
180   boolean handleDeletes(final KeyValue kv) {
181     addDelete(kv);
182     boolean deleted = false;
183     if (!hasCandidate()) return deleted;
184     if (isDeleted(this.candidate)) {
185       this.candidate = null;
186       deleted = true;
187     }
188     return deleted;
189   }
190 
191   /**
192    * Do right thing with passed key, add to deletes or add to candidates.
193    * @param kv
194    * @return True if we added a candidate
195    */
196   boolean handle(final KeyValue kv) {
197     if (kv.isDelete()) {
198       handleDeletes(kv);
199       return false;
200     }
201     return addCandidate(kv);
202   }
203 
204   /**
205    * @return True if has candidate
206    */
207   public boolean hasCandidate() {
208     return this.candidate != null;
209   }
210 
211   /**
212    * @return Best candidate or null.
213    */
214   public KeyValue getCandidate() {
215     return this.candidate;
216   }
217 
218   public KeyValue getTargetKey() {
219     return this.targetkey;
220   }
221 
222   /**
223    * @param kv Current kv
224    * @param First on row kv.
225    * @param state
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.getBuffer(), this.rowoffset,
237         this.tablenamePlusDelimiterLength,
238       kv.getBuffer(), kv.getRowOffset(), this.tablenamePlusDelimiterLength) == 0;
239   }
240 }