View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase;
20  
21  import java.io.Serializable;
22  import java.util.Comparator;
23  
24  import org.apache.hadoop.hbase.KeyValue.Type;
25  import org.apache.hadoop.hbase.classification.InterfaceAudience;
26  import org.apache.hadoop.hbase.classification.InterfaceStability;
27  import org.apache.hadoop.hbase.util.Bytes;
28  
29  import com.google.common.primitives.Longs;
30  
31  /**
32   * Compare two HBase cells.  Do not use this method comparing <code>-ROOT-</code> or
33   * <code>hbase:meta</code> cells.  Cells from these tables need a specialized comparator, one that
34   * takes account of the special formatting of the row where we have commas to delimit table from
35   * regionname, from row.  See KeyValue for how it has a special comparator to do hbase:meta cells
36   * and yet another for -ROOT-.
37   */
38  @edu.umd.cs.findbugs.annotations.SuppressWarnings(
39      value="UNKNOWN",
40      justification="Findbugs doesn't like the way we are negating the result of a compare in below")
41  @InterfaceAudience.Private
42  @InterfaceStability.Evolving
43  public class CellComparator implements Comparator<Cell>, Serializable{
44    private static final long serialVersionUID = -8760041766259623329L;
45  
46    @Override
47    public int compare(Cell a, Cell b) {
48      return compareStatic(a, b, false);
49    }
50  
51    public static int compareStatic(Cell a, Cell b, boolean onlyKey) {
52      // row
53      int c = compareRows(a, b);
54      if (c != 0) return c;
55  
56      c = compareWithoutRow(a, b);
57      if(c != 0) return c;
58  
59      if (!onlyKey) {
60        // Negate following comparisons so later edits show up first
61  
62        // compare log replay tag value if there is any
63        // when either keyvalue tagged with log replay sequence number, we need to compare them:
64        // 1) when both keyvalues have the tag, then use the tag values for comparison
65        // 2) when one has and the other doesn't have, the one without the log
66        // replay tag wins because
67        // it means the edit isn't from recovery but new one coming from clients during recovery
68        // 3) when both doesn't have, then skip to the next mvcc comparison
69        long leftChangeSeqNum = getReplaySeqNum(a);
70        long RightChangeSeqNum = getReplaySeqNum(b);
71        if (leftChangeSeqNum != Long.MAX_VALUE || RightChangeSeqNum != Long.MAX_VALUE) {
72          return Longs.compare(RightChangeSeqNum, leftChangeSeqNum);
73        }
74        // mvccVersion: later sorts first
75        return Longs.compare(b.getMvccVersion(), a.getMvccVersion());
76      } else {
77        return c;
78      }
79    }
80  
81    /**
82     * Return replay log sequence number for the cell
83     *
84     * @param c
85     * @return Long.MAX_VALUE if there is no LOG_REPLAY_TAG
86     */
87    private static long getReplaySeqNum(final Cell c) {
88      Tag tag = Tag.getTag(c.getTagsArray(), c.getTagsOffset(), c.getTagsLength(),
89          TagType.LOG_REPLAY_TAG_TYPE);
90  
91      if (tag != null) {
92        return Bytes.toLong(tag.getBuffer(), tag.getTagOffset(), tag.getTagLength());
93      }
94      return Long.MAX_VALUE;
95    }
96  
97    public static int findCommonPrefixInRowPart(Cell left, Cell right, int rowCommonPrefix) {
98      return findCommonPrefix(left.getRowArray(), right.getRowArray(), left.getRowLength()
99          - rowCommonPrefix, right.getRowLength() - rowCommonPrefix, left.getRowOffset()
100         + rowCommonPrefix, right.getRowOffset() + rowCommonPrefix);
101   }
102 
103   private static int findCommonPrefix(byte[] left, byte[] right, int leftLength, int rightLength,
104       int leftOffset, int rightOffset) {
105     int length = Math.min(leftLength, rightLength);
106     int result = 0;
107 
108     while (result < length && left[leftOffset + result] == right[rightOffset + result]) {
109       result++;
110     }
111     return result;
112   }
113 
114   public static int findCommonPrefixInFamilyPart(Cell left, Cell right, int familyCommonPrefix) {
115     return findCommonPrefix(left.getFamilyArray(), right.getFamilyArray(), left.getFamilyLength()
116         - familyCommonPrefix, right.getFamilyLength() - familyCommonPrefix, left.getFamilyOffset()
117         + familyCommonPrefix, right.getFamilyOffset() + familyCommonPrefix);
118   }
119 
120   public static int findCommonPrefixInQualifierPart(Cell left, Cell right,
121       int qualifierCommonPrefix) {
122     return findCommonPrefix(left.getQualifierArray(), right.getQualifierArray(),
123         left.getQualifierLength() - qualifierCommonPrefix, right.getQualifierLength()
124             - qualifierCommonPrefix, left.getQualifierOffset() + qualifierCommonPrefix,
125         right.getQualifierOffset() + qualifierCommonPrefix);
126   }
127 
128   /**************** equals ****************************/
129 
130   public static boolean equals(Cell a, Cell b){
131     return equalsRow(a, b)
132         && equalsFamily(a, b)
133         && equalsQualifier(a, b)
134         && equalsTimestamp(a, b)
135         && equalsType(a, b);
136   }
137 
138   public static boolean equalsRow(Cell a, Cell b){
139     return Bytes.equals(
140       a.getRowArray(), a.getRowOffset(), a.getRowLength(),
141       b.getRowArray(), b.getRowOffset(), b.getRowLength());
142   }
143 
144   public static boolean equalsFamily(Cell a, Cell b){
145     return Bytes.equals(
146       a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
147       b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
148   }
149 
150   public static boolean equalsQualifier(Cell a, Cell b){
151     return Bytes.equals(
152       a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
153       b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
154   }
155 
156   public static boolean equalsTimestamp(Cell a, Cell b){
157     return a.getTimestamp() == b.getTimestamp();
158   }
159 
160   public static boolean equalsType(Cell a, Cell b){
161     return a.getTypeByte() == b.getTypeByte();
162   }
163 
164   public static int compareColumns(final Cell left, final Cell right) {
165     int lfoffset = left.getFamilyOffset();
166     int rfoffset = right.getFamilyOffset();
167     int lclength = left.getQualifierLength();
168     int rclength = right.getQualifierLength();
169     int lfamilylength = left.getFamilyLength();
170     int rfamilylength = right.getFamilyLength();
171     int diff = compare(left.getFamilyArray(), lfoffset, lfamilylength, right.getFamilyArray(),
172         rfoffset, rfamilylength);
173     if (diff != 0) {
174       return diff;
175     } else {
176       return compare(left.getQualifierArray(), left.getQualifierOffset(), lclength,
177           right.getQualifierArray(), right.getQualifierOffset(), rclength);
178     }
179   }
180 
181   public static int compareFamilies(Cell left, Cell right) {
182     return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
183         right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
184   }
185 
186   public static int compareQualifiers(Cell left, Cell right) {
187     return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
188         left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
189         right.getQualifierLength());
190   }
191 
192   public int compareFlatKey(Cell left, Cell right) {
193     int compare = compareRows(left, right);
194     if (compare != 0) {
195       return compare;
196     }
197     return compareWithoutRow(left, right);
198   }
199 
200   public static int compareRows(final Cell left, final Cell right) {
201     return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
202         right.getRowArray(), right.getRowOffset(), right.getRowLength());
203   }
204 
205   public static int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset,
206       int rlength) {
207     return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
208   }
209 
210   public static int compareWithoutRow(final Cell leftCell, final Cell rightCell) {
211     if (leftCell.getFamilyLength() + leftCell.getQualifierLength() == 0
212         && leftCell.getTypeByte() == Type.Minimum.getCode()) {
213       // left is "bigger", i.e. it appears later in the sorted order
214       return 1;
215     }
216     if (rightCell.getFamilyLength() + rightCell.getQualifierLength() == 0
217         && rightCell.getTypeByte() == Type.Minimum.getCode()) {
218       return -1;
219     }
220     boolean sameFamilySize = (leftCell.getFamilyLength() == rightCell.getFamilyLength());
221     if (!sameFamilySize) {
222       // comparing column family is enough.
223 
224       return Bytes.compareTo(leftCell.getFamilyArray(), leftCell.getFamilyOffset(),
225           leftCell.getFamilyLength(), rightCell.getFamilyArray(), rightCell.getFamilyOffset(),
226           rightCell.getFamilyLength());
227     }
228     int diff = compareColumns(leftCell, rightCell);
229     if (diff != 0) return diff;
230 
231     diff = compareTimestamps(leftCell, rightCell);
232     if (diff != 0) return diff;
233 
234     // Compare types. Let the delete types sort ahead of puts; i.e. types
235     // of higher numbers sort before those of lesser numbers. Maximum (255)
236     // appears ahead of everything, and minimum (0) appears after
237     // everything.
238     return (0xff & rightCell.getTypeByte()) - (0xff & leftCell.getTypeByte());
239   }
240 
241   public static int compareTimestamps(final Cell left, final Cell right) {
242     long ltimestamp = left.getTimestamp();
243     long rtimestamp = right.getTimestamp();
244     return compareTimestamps(ltimestamp, rtimestamp);
245   }
246 
247   /********************* hashCode ************************/
248 
249   /**
250    * Returns a hash code that is always the same for two Cells having a matching equals(..) result.
251    * Currently does not guard against nulls, but it could if necessary.
252    */
253   public static int hashCode(Cell cell){
254     if (cell == null) {// return 0 for empty Cell
255       return 0;
256     }
257 
258     int hash = calculateHashForKeyValue(cell);
259     hash = 31 * hash + (int)cell.getMvccVersion();
260     return hash;
261   }
262 
263   /**
264    * Returns a hash code that is always the same for two Cells having a matching
265    * equals(..) result. Currently does not guard against nulls, but it could if
266    * necessary. Note : Ignore mvcc while calculating the hashcode
267    * 
268    * @param cell
269    * @return hashCode
270    */
271   public static int hashCodeIgnoreMvcc(Cell cell) {
272     if (cell == null) {// return 0 for empty Cell
273       return 0;
274     }
275 
276     int hash = calculateHashForKeyValue(cell);
277     return hash;
278   }
279 
280   private static int calculateHashForKeyValue(Cell cell) {
281     //pre-calculate the 3 hashes made of byte ranges
282     int rowHash = Bytes.hashCode(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
283     int familyHash =
284       Bytes.hashCode(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
285     int qualifierHash = Bytes.hashCode(cell.getQualifierArray(), cell.getQualifierOffset(),
286       cell.getQualifierLength());
287 
288     //combine the 6 sub-hashes
289     int hash = 31 * rowHash + familyHash;
290     hash = 31 * hash + qualifierHash;
291     hash = 31 * hash + (int)cell.getTimestamp();
292     hash = 31 * hash + cell.getTypeByte();
293     return hash;
294   }
295 
296 
297   /******************** lengths *************************/
298 
299   public static boolean areKeyLengthsEqual(Cell a, Cell b) {
300     return a.getRowLength() == b.getRowLength()
301         && a.getFamilyLength() == b.getFamilyLength()
302         && a.getQualifierLength() == b.getQualifierLength();
303   }
304 
305   public static boolean areRowLengthsEqual(Cell a, Cell b) {
306     return a.getRowLength() == b.getRowLength();
307   }
308 
309 
310   /*********************common prefixes*************************/
311 
312   private static int compare(byte[] left, int leftOffset, int leftLength, byte[] right,
313       int rightOffset, int rightLength) {
314     return Bytes.compareTo(left, leftOffset, leftLength, right, rightOffset, rightLength);
315   }
316 
317   public static int compareCommonRowPrefix(Cell left, Cell right, int rowCommonPrefix) {
318     return compare(left.getRowArray(), left.getRowOffset() + rowCommonPrefix, left.getRowLength()
319         - rowCommonPrefix, right.getRowArray(), right.getRowOffset() + rowCommonPrefix,
320         right.getRowLength() - rowCommonPrefix);
321   }
322 
323   public static int compareCommonFamilyPrefix(Cell left, Cell right,
324       int familyCommonPrefix) {
325     return compare(left.getFamilyArray(), left.getFamilyOffset() + familyCommonPrefix,
326         left.getFamilyLength() - familyCommonPrefix, right.getFamilyArray(),
327         right.getFamilyOffset() + familyCommonPrefix,
328         right.getFamilyLength() - familyCommonPrefix);
329   }
330 
331   public static int compareCommonQualifierPrefix(Cell left, Cell right,
332       int qualCommonPrefix) {
333     return compare(left.getQualifierArray(), left.getQualifierOffset() + qualCommonPrefix,
334         left.getQualifierLength() - qualCommonPrefix, right.getQualifierArray(),
335         right.getQualifierOffset() + qualCommonPrefix, right.getQualifierLength()
336             - qualCommonPrefix);
337   }
338 
339   /***************** special cases ****************************/
340   /**
341    * special case for KeyValue.equals
342    */
343   public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
344     return 0 == compareStaticIgnoreMvccVersion(a, b);
345   }
346 
347   private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
348     // row
349     int c = compareRows(a, b);
350     if (c != 0) return c;
351 
352     // family
353     c = compareColumns(a, b);
354     if (c != 0) return c;
355 
356     // timestamp: later sorts first
357     c = compareTimestamps(a, b);
358     if (c != 0) return c;
359 
360     //type
361     c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
362     return c;
363   }
364 
365   private static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
366     // The below older timestamps sorting ahead of newer timestamps looks
367     // wrong but it is intentional. This way, newer timestamps are first
368     // found when we iterate over a memstore and newer versions are the
369     // first we trip over when reading from a store file.
370     if (ltimestamp < rtimestamp) {
371       return 1;
372     } else if (ltimestamp > rtimestamp) {
373       return -1;
374     }
375     return 0;
376   }
377 
378   /**
379    * Counter part for the KeyValue.RowOnlyComparator
380    */
381   public static class RowComparator extends CellComparator {
382     @Override
383     public int compare(Cell a, Cell b) {
384       return compareRows(a, b);
385     }
386   }
387 
388 }