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.classification.InterfaceAudience;
25  import org.apache.hadoop.classification.InterfaceStability;
26  import org.apache.hadoop.hbase.KeyValue.Type;
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     //pre-calculate the 3 hashes made of byte ranges
259     int rowHash = Bytes.hashCode(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
260     int familyHash =
261       Bytes.hashCode(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
262     int qualifierHash = Bytes.hashCode(cell.getQualifierArray(), cell.getQualifierOffset(),
263       cell.getQualifierLength());
264 
265     //combine the 6 sub-hashes
266     int hash = 31 * rowHash + familyHash;
267     hash = 31 * hash + qualifierHash;
268     hash = 31 * hash + (int)cell.getTimestamp();
269     hash = 31 * hash + cell.getTypeByte();
270     hash = 31 * hash + (int)cell.getMvccVersion();
271     return hash;
272   }
273 
274 
275   /******************** lengths *************************/
276 
277   public static boolean areKeyLengthsEqual(Cell a, Cell b) {
278     return a.getRowLength() == b.getRowLength()
279         && a.getFamilyLength() == b.getFamilyLength()
280         && a.getQualifierLength() == b.getQualifierLength();
281   }
282 
283   public static boolean areRowLengthsEqual(Cell a, Cell b) {
284     return a.getRowLength() == b.getRowLength();
285   }
286 
287 
288   /*********************common prefixes*************************/
289 
290   private static int compare(byte[] left, int leftOffset, int leftLength, byte[] right,
291       int rightOffset, int rightLength) {
292     return Bytes.compareTo(left, leftOffset, leftLength, right, rightOffset, rightLength);
293   }
294 
295   public static int compareCommonRowPrefix(Cell left, Cell right, int rowCommonPrefix) {
296     return compare(left.getRowArray(), left.getRowOffset() + rowCommonPrefix, left.getRowLength()
297         - rowCommonPrefix, right.getRowArray(), right.getRowOffset() + rowCommonPrefix,
298         right.getRowLength() - rowCommonPrefix);
299   }
300 
301   public static int compareCommonFamilyPrefix(Cell left, Cell right,
302       int familyCommonPrefix) {
303     return compare(left.getFamilyArray(), left.getFamilyOffset() + familyCommonPrefix,
304         left.getFamilyLength() - familyCommonPrefix, right.getFamilyArray(),
305         right.getFamilyOffset() + familyCommonPrefix,
306         right.getFamilyLength() - familyCommonPrefix);
307   }
308 
309   public static int compareCommonQualifierPrefix(Cell left, Cell right,
310       int qualCommonPrefix) {
311     return compare(left.getQualifierArray(), left.getQualifierOffset() + qualCommonPrefix,
312         left.getQualifierLength() - qualCommonPrefix, right.getQualifierArray(),
313         right.getQualifierOffset() + qualCommonPrefix, right.getQualifierLength()
314             - qualCommonPrefix);
315   }
316 
317   /***************** special cases ****************************/
318   /**
319    * special case for KeyValue.equals
320    */
321   public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
322     return 0 == compareStaticIgnoreMvccVersion(a, b);
323   }
324 
325   private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
326     // row
327     int c = compareRows(a, b);
328     if (c != 0) return c;
329 
330     // family
331     c = compareColumns(a, b);
332     if (c != 0) return c;
333 
334     // timestamp: later sorts first
335     c = compareTimestamps(a, b);
336     if (c != 0) return c;
337 
338     //type
339     c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
340     return c;
341   }
342 
343   private static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
344     // The below older timestamps sorting ahead of newer timestamps looks
345     // wrong but it is intentional. This way, newer timestamps are first
346     // found when we iterate over a memstore and newer versions are the
347     // first we trip over when reading from a store file.
348     if (ltimestamp < rtimestamp) {
349       return 1;
350     } else if (ltimestamp > rtimestamp) {
351       return -1;
352     }
353     return 0;
354   }
355 
356 }