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 compare(a, b, false);
49    }
50  
51    /**
52     * Compare cells.
53     * TODO: Replace with dynamic rather than static comparator so can change comparator
54     * implementation.
55     * @param a
56     * @param b
57     * @param ignoreSequenceid True if we are to compare the key portion only and ignore
58     * the sequenceid. Set to false to compare key and consider sequenceid.
59     * @return 0 if equal, -1 if a < b, and +1 if a > b.
60     */
61    public static int compare(final Cell a, final Cell b, boolean ignoreSequenceid) {
62      // row
63      int c = compareRows(a, b);
64      if (c != 0) return c;
65  
66      c = compareWithoutRow(a, b);
67      if(c != 0) return c;
68  
69      if (!ignoreSequenceid) {
70        // Negate following comparisons so later edits show up first
71        // mvccVersion: later sorts first
72        return Longs.compare(b.getMvccVersion(), a.getMvccVersion());
73      } else {
74        return c;
75      }
76    }
77  
78    public static int findCommonPrefixInRowPart(Cell left, Cell right, int rowCommonPrefix) {
79      return findCommonPrefix(left.getRowArray(), right.getRowArray(), left.getRowLength()
80          - rowCommonPrefix, right.getRowLength() - rowCommonPrefix, left.getRowOffset()
81          + rowCommonPrefix, right.getRowOffset() + rowCommonPrefix);
82    }
83  
84    private static int findCommonPrefix(byte[] left, byte[] right, int leftLength, int rightLength,
85        int leftOffset, int rightOffset) {
86      int length = Math.min(leftLength, rightLength);
87      int result = 0;
88  
89      while (result < length && left[leftOffset + result] == right[rightOffset + result]) {
90        result++;
91      }
92      return result;
93    }
94  
95    public static int findCommonPrefixInFamilyPart(Cell left, Cell right, int familyCommonPrefix) {
96      return findCommonPrefix(left.getFamilyArray(), right.getFamilyArray(), left.getFamilyLength()
97          - familyCommonPrefix, right.getFamilyLength() - familyCommonPrefix, left.getFamilyOffset()
98          + familyCommonPrefix, right.getFamilyOffset() + familyCommonPrefix);
99    }
100 
101   public static int findCommonPrefixInQualifierPart(Cell left, Cell right,
102       int qualifierCommonPrefix) {
103     return findCommonPrefix(left.getQualifierArray(), right.getQualifierArray(),
104         left.getQualifierLength() - qualifierCommonPrefix, right.getQualifierLength()
105             - qualifierCommonPrefix, left.getQualifierOffset() + qualifierCommonPrefix,
106         right.getQualifierOffset() + qualifierCommonPrefix);
107   }
108 
109   /**************** equals ****************************/
110 
111   public static boolean equals(Cell a, Cell b){
112     return equalsRow(a, b)
113         && equalsFamily(a, b)
114         && equalsQualifier(a, b)
115         && equalsTimestamp(a, b)
116         && equalsType(a, b);
117   }
118 
119   public static boolean equalsRow(Cell a, Cell b){
120     return Bytes.equals(
121       a.getRowArray(), a.getRowOffset(), a.getRowLength(),
122       b.getRowArray(), b.getRowOffset(), b.getRowLength());
123   }
124 
125   public static boolean equalsFamily(Cell a, Cell b){
126     return Bytes.equals(
127       a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
128       b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
129   }
130 
131   public static boolean equalsQualifier(Cell a, Cell b){
132     return Bytes.equals(
133       a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
134       b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
135   }
136 
137   public static boolean equalsTimestamp(Cell a, Cell b){
138     return a.getTimestamp() == b.getTimestamp();
139   }
140 
141   public static boolean equalsType(Cell a, Cell b){
142     return a.getTypeByte() == b.getTypeByte();
143   }
144 
145   public static int compareColumns(final Cell left, final Cell right) {
146     int lfoffset = left.getFamilyOffset();
147     int rfoffset = right.getFamilyOffset();
148     int lclength = left.getQualifierLength();
149     int rclength = right.getQualifierLength();
150     int lfamilylength = left.getFamilyLength();
151     int rfamilylength = right.getFamilyLength();
152     int diff = compare(left.getFamilyArray(), lfoffset, lfamilylength, right.getFamilyArray(),
153         rfoffset, rfamilylength);
154     if (diff != 0) {
155       return diff;
156     } else {
157       return compare(left.getQualifierArray(), left.getQualifierOffset(), lclength,
158           right.getQualifierArray(), right.getQualifierOffset(), rclength);
159     }
160   }
161 
162   public static int compareFamilies(Cell left, Cell right) {
163     return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
164         right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
165   }
166 
167   public static int compareQualifiers(Cell left, Cell right) {
168     return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
169         left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
170         right.getQualifierLength());
171   }
172 
173   public final static int compareQualifiers(Cell left, byte[] right, int rOffset, int rLength) {
174     return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
175         left.getQualifierLength(), right, rOffset, rLength);
176   }
177 
178   public int compareFlatKey(Cell left, Cell right) {
179     int compare = compareRows(left, right);
180     if (compare != 0) {
181       return compare;
182     }
183     return compareWithoutRow(left, right);
184   }
185 
186   /**
187    * Do not use comparing rows from hbase:meta. Meta table Cells have schema (table,startrow,hash)
188    * so can't be treated as plain byte arrays as this method does.
189    */
190   public static int compareRows(final Cell left, final Cell right) {
191     return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
192         right.getRowArray(), right.getRowOffset(), right.getRowLength());
193   }
194 
195   /**
196    * Do not use comparing rows from hbase:meta. Meta table Cells have schema (table,startrow,hash)
197    * so can't be treated as plain byte arrays as this method does.
198    */
199   public static int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset,
200       int rlength) {
201     return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
202   }
203 
204   public static int compareWithoutRow(final Cell leftCell, final Cell rightCell) {
205     // If the column is not specified, the "minimum" key type appears the
206     // latest in the sorted order, regardless of the timestamp. This is used
207     // for specifying the last key/value in a given row, because there is no
208     // "lexicographically last column" (it would be infinitely long). The
209     // "maximum" key type does not need this behavior.
210     // Copied from KeyValue. This is bad in that we can't do memcmp w/ special rules like this.
211     // TODO
212     if (leftCell.getFamilyLength() + leftCell.getQualifierLength() == 0
213           && leftCell.getTypeByte() == Type.Minimum.getCode()) {
214       // left is "bigger", i.e. it appears later in the sorted order
215       return 1;
216     }
217     if (rightCell.getFamilyLength() + rightCell.getQualifierLength() == 0
218         && rightCell.getTypeByte() == Type.Minimum.getCode()) {
219       return -1;
220     }
221     boolean sameFamilySize = (leftCell.getFamilyLength() == rightCell.getFamilyLength());
222     if (!sameFamilySize) {
223       // comparing column family is enough.
224 
225       return Bytes.compareTo(leftCell.getFamilyArray(), leftCell.getFamilyOffset(),
226           leftCell.getFamilyLength(), rightCell.getFamilyArray(), rightCell.getFamilyOffset(),
227           rightCell.getFamilyLength());
228     }
229     int diff = compareColumns(leftCell, rightCell);
230     if (diff != 0) return diff;
231 
232     diff = compareTimestamps(leftCell, rightCell);
233     if (diff != 0) return diff;
234 
235     // Compare types. Let the delete types sort ahead of puts; i.e. types
236     // of higher numbers sort before those of lesser numbers. Maximum (255)
237     // appears ahead of everything, and minimum (0) appears after
238     // everything.
239     return (0xff & rightCell.getTypeByte()) - (0xff & leftCell.getTypeByte());
240   }
241 
242   public static int compareTimestamps(final Cell left, final Cell right) {
243     return compareTimestamps(left.getTimestamp(), right.getTimestamp());
244   }
245 
246   /********************* hashCode ************************/
247 
248   /**
249    * Returns a hash code that is always the same for two Cells having a matching equals(..) result.
250    */
251   public static int hashCode(Cell cell){
252     if (cell == null) {// return 0 for empty Cell
253       return 0;
254     }
255 
256     int hash = calculateHashForKeyValue(cell);
257     hash = 31 * hash + (int)cell.getMvccVersion();
258     return hash;
259   }
260 
261   /**
262    * Returns a hash code that is always the same for two Cells having a matching
263    * equals(..) result. Note : Ignore mvcc while calculating the hashcode
264    * 
265    * @param cell
266    * @return hashCode
267    */
268   public static int hashCodeIgnoreMvcc(Cell cell) {
269     if (cell == null) {// return 0 for empty Cell
270       return 0;
271     }
272 
273     int hash = calculateHashForKeyValue(cell);
274     return hash;
275   }
276 
277   private static int calculateHashForKeyValue(Cell cell) {
278     //pre-calculate the 3 hashes made of byte ranges
279     int rowHash = Bytes.hashCode(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
280     int familyHash =
281       Bytes.hashCode(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
282     int qualifierHash = Bytes.hashCode(cell.getQualifierArray(), cell.getQualifierOffset(),
283       cell.getQualifierLength());
284 
285     //combine the 6 sub-hashes
286     int hash = 31 * rowHash + familyHash;
287     hash = 31 * hash + qualifierHash;
288     hash = 31 * hash + (int)cell.getTimestamp();
289     hash = 31 * hash + cell.getTypeByte();
290     return hash;
291   }
292 
293 
294   /******************** lengths *************************/
295 
296   public static boolean areKeyLengthsEqual(Cell a, Cell b) {
297     return a.getRowLength() == b.getRowLength()
298         && a.getFamilyLength() == b.getFamilyLength()
299         && a.getQualifierLength() == b.getQualifierLength();
300   }
301 
302   public static boolean areRowLengthsEqual(Cell a, Cell b) {
303     return a.getRowLength() == b.getRowLength();
304   }
305 
306 
307   /*********************common prefixes*************************/
308 
309   private static int compare(byte[] left, int leftOffset, int leftLength, byte[] right,
310       int rightOffset, int rightLength) {
311     return Bytes.compareTo(left, leftOffset, leftLength, right, rightOffset, rightLength);
312   }
313 
314   public static int compareCommonRowPrefix(Cell left, Cell right, int rowCommonPrefix) {
315     return compare(left.getRowArray(), left.getRowOffset() + rowCommonPrefix, left.getRowLength()
316         - rowCommonPrefix, right.getRowArray(), right.getRowOffset() + rowCommonPrefix,
317         right.getRowLength() - rowCommonPrefix);
318   }
319 
320   public static int compareCommonFamilyPrefix(Cell left, Cell right,
321       int familyCommonPrefix) {
322     return compare(left.getFamilyArray(), left.getFamilyOffset() + familyCommonPrefix,
323         left.getFamilyLength() - familyCommonPrefix, right.getFamilyArray(),
324         right.getFamilyOffset() + familyCommonPrefix,
325         right.getFamilyLength() - familyCommonPrefix);
326   }
327 
328   public static int compareCommonQualifierPrefix(Cell left, Cell right,
329       int qualCommonPrefix) {
330     return compare(left.getQualifierArray(), left.getQualifierOffset() + qualCommonPrefix,
331         left.getQualifierLength() - qualCommonPrefix, right.getQualifierArray(),
332         right.getQualifierOffset() + qualCommonPrefix, right.getQualifierLength()
333             - qualCommonPrefix);
334   }
335 
336   /***************** special cases ****************************/
337   /**
338    * special case for KeyValue.equals
339    */
340   public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
341     return 0 == compareStaticIgnoreMvccVersion(a, b);
342   }
343 
344   private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
345     // row
346     int c = compareRows(a, b);
347     if (c != 0) return c;
348 
349     // family
350     c = compareColumns(a, b);
351     if (c != 0) return c;
352 
353     // timestamp: later sorts first
354     c = compareTimestamps(a, b);
355     if (c != 0) return c;
356 
357     //type
358     c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
359     return c;
360   }
361 
362   public static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
363     // The below older timestamps sorting ahead of newer timestamps looks
364     // wrong but it is intentional. This way, newer timestamps are first
365     // found when we iterate over a memstore and newer versions are the
366     // first we trip over when reading from a store file.
367     if (ltimestamp < rtimestamp) {
368       return 1;
369     } else if (ltimestamp > rtimestamp) {
370       return -1;
371     }
372     return 0;
373   }
374 
375   /**
376    * Counter part for the KeyValue.RowOnlyComparator
377    */
378   public static class RowComparator extends CellComparator {
379     @Override
380     public int compare(Cell a, Cell b) {
381       return compareRows(a, b);
382     }
383   }
384 
385   /**
386    * Try to return a Cell that falls between <code>left</code> and <code>right</code> but that is
387    * shorter; i.e. takes up less space. This trick is used building HFile block index.
388    * Its an optimization. It does not always work.  In this case we'll just return the
389    * <code>right</code> cell.
390    * @param comparator Comparator to use.
391    * @param left
392    * @param right
393    * @return A cell that sorts between <code>left</code> and <code>right</code>.
394    */
395   public static Cell getMidpoint(final KeyValue.KVComparator comparator, final Cell left,
396       final Cell right) {
397     // TODO: Redo so only a single pass over the arrays rather than one to compare and then a
398     // second composing midpoint.
399     if (right == null) {
400       throw new IllegalArgumentException("right cell can not be null");
401     }
402     if (left == null) {
403       return right;
404     }
405     // If Cells from meta table, don't mess around. meta table Cells have schema
406     // (table,startrow,hash) so can't be treated as plain byte arrays. Just skip out without
407     // trying to do this optimization.
408     if (comparator != null && comparator instanceof KeyValue.MetaComparator) {
409       return right;
410     }
411     int diff = compareRows(left, right);
412     if (diff > 0) {
413       throw new IllegalArgumentException("Left row sorts after right row; left=" +
414         CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
415     }
416     if (diff < 0) {
417       // Left row is < right row.
418       byte [] midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(),
419           left.getRowLength(),
420         right.getRowArray(), right.getRowOffset(), right.getRowLength());
421       // If midRow is null, just return 'right'.  Can't do optimization.
422       if (midRow == null) return right;
423       return CellUtil.createCell(midRow);
424     }
425     // Rows are same. Compare on families.
426     diff = compareFamilies(left, right);
427     if (diff > 0) {
428       throw new IllegalArgumentException("Left family sorts after right family; left=" +
429           CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
430     }
431     if (diff < 0) {
432       byte [] midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
433           left.getFamilyLength(),
434         right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
435       // If midRow is null, just return 'right'.  Can't do optimization.
436       if (midRow == null) return right;
437       // Return new Cell where we use right row and then a mid sort family.
438       return CellUtil.createCell(right.getRowArray(), right.getRowOffset(), right.getRowLength(),
439         midRow, 0, midRow.length, HConstants.EMPTY_BYTE_ARRAY, 0,
440         HConstants.EMPTY_BYTE_ARRAY.length);
441     }
442     // Families are same. Compare on qualifiers.
443     diff = compareQualifiers(left, right);
444     if (diff > 0) {
445       throw new IllegalArgumentException("Left qualifier sorts after right qualifier; left=" +
446           CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
447     }
448     if (diff < 0) {
449       byte [] midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
450           left.getQualifierLength(),
451         right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength());
452       // If midRow is null, just return 'right'.  Can't do optimization.
453       if (midRow == null) return right;
454       // Return new Cell where we use right row and family and then a mid sort qualifier.
455       return CellUtil.createCell(right.getRowArray(), right.getRowOffset(), right.getRowLength(),
456         right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength(),
457         midRow, 0, midRow.length);
458     }
459     // No opportunity for optimization. Just return right key.
460     return right;
461   }
462 
463   /**
464    * @param leftArray
465    * @param leftOffset
466    * @param leftLength
467    * @param rightArray
468    * @param rightOffset
469    * @param rightLength
470    * @return Return a new array that is between left and right and minimally sized else just return
471    * null as indicator that we could not create a mid point.
472    */
473   private static byte [] getMinimumMidpointArray(final byte [] leftArray, final int leftOffset,
474         final int leftLength,
475       final byte [] rightArray, final int rightOffset, final int rightLength) {
476     // rows are different
477     int minLength = leftLength < rightLength ? leftLength : rightLength;
478     int diffIdx = 0;
479     while (diffIdx < minLength &&
480         leftArray[leftOffset + diffIdx] == rightArray[rightOffset + diffIdx]) {
481       diffIdx++;
482     }
483     byte [] minimumMidpointArray = null;
484     if (diffIdx >= minLength) {
485       // leftKey's row is prefix of rightKey's.
486       minimumMidpointArray = new byte[diffIdx + 1];
487       System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
488     } else {
489       int diffByte = leftArray[leftOffset + diffIdx];
490       if ((0xff & diffByte) < 0xff && (diffByte + 1) < (rightArray[rightOffset + diffIdx] & 0xff)) {
491         minimumMidpointArray = new byte[diffIdx + 1];
492         System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx);
493         minimumMidpointArray[diffIdx] = (byte) (diffByte + 1);
494       } else {
495         minimumMidpointArray = new byte[diffIdx + 1];
496         System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
497       }
498     }
499     return minimumMidpointArray;
500   }
501 }