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  package org.apache.omid.transaction;
19  
20  import java.io.IOException;
21  import java.util.Arrays;
22  import java.util.HashMap;
23  import java.util.List;
24  import java.util.Map;
25  import java.util.SortedMap;
26  import java.util.TreeMap;
27  
28  import org.apache.hadoop.hbase.Cell;
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.client.Get;
33  import org.apache.hadoop.hbase.client.Result;
34  import org.apache.hadoop.hbase.util.Bytes;
35  import org.apache.omid.HBaseShims;
36  import org.slf4j.Logger;
37  import org.slf4j.LoggerFactory;
38  
39  import org.apache.phoenix.thirdparty.com.google.common.base.Charsets;
40  import org.apache.phoenix.thirdparty.com.google.common.base.MoreObjects;
41  import org.apache.phoenix.thirdparty.com.google.common.base.Objects;
42  import org.apache.phoenix.thirdparty.com.google.common.base.MoreObjects.ToStringHelper;
43  import org.apache.phoenix.thirdparty.com.google.common.base.Optional;
44  import org.apache.phoenix.thirdparty.com.google.common.base.Preconditions;
45  import org.apache.phoenix.thirdparty.com.google.common.hash.Hasher;
46  import org.apache.phoenix.thirdparty.com.google.common.hash.Hashing;
47  
48  @SuppressWarnings("all")
49  public final class CellUtils {
50  
51      private static final Logger LOG = LoggerFactory.getLogger(CellUtils.class);
52      static final byte[] SHADOW_CELL_SUFFIX = "\u0080".getBytes(Charsets.UTF_8); // Non printable char (128 ASCII)
53      //Prefix starts with 0 to apear before other cells in TransactionVisibilityFilter
54      static final byte[] SHADOW_CELL_PREFIX = "\u0000\u0080".getBytes(Charsets.UTF_8);
55      static byte[] DELETE_TOMBSTONE = HConstants.EMPTY_BYTE_ARRAY;
56      static byte[] LEGACY_DELETE_TOMBSTONE = Bytes.toBytes("__OMID_TOMBSTONE__");
57      public static final byte[] FAMILY_DELETE_QUALIFIER = HConstants.EMPTY_BYTE_ARRAY;
58      public static final String TRANSACTION_ATTRIBUTE = "__OMID_TRANSACTION__";
59      /**/
60      public static final String CLIENT_GET_ATTRIBUTE = "__OMID_CLIENT_GET__";
61      public static final String LL_ATTRIBUTE = "__OMID_LL__";
62  
63      /**
64       * Utility interface to get rid of the dependency on HBase server package
65       */
66      interface CellGetter {
67          Result get(Get get) throws IOException;
68      }
69  
70      /**
71       * Returns true if the particular cell passed exists in the datastore.
72       * @param row row
73       * @param family column family
74       * @param qualifier columnn name
75       * @param version version
76       * @param cellGetter an instance of CellGetter
77       * @return true if the cell specified exists. false otherwise
78       * @throws IOException
79       */
80      public static boolean hasCell(byte[] row,
81                                    byte[] family,
82                                    byte[] qualifier,
83                                    long version,
84                                    CellGetter cellGetter)
85              throws IOException {
86          Get get = new Get(row);
87          get.addColumn(family, qualifier);
88          get.setTimeStamp(version);
89  
90          Result result = cellGetter.get(get);
91  
92          return result.containsColumn(family, qualifier);
93      }
94  
95      /**
96       * Returns true if the particular cell passed has a corresponding shadow cell in the datastore
97       * @param row row
98       * @param family column family
99       * @param qualifier columnn name
100      * @param version version
101      * @param cellGetter an instance of CellGetter
102      * @return true if it has a shadow cell. false otherwise.
103      * @throws IOException
104      */
105     public static boolean hasShadowCell(byte[] row,
106                                         byte[] family,
107                                         byte[] qualifier,
108                                         long version,
109                                         CellGetter cellGetter) throws IOException {
110         return hasCell(row, family, addShadowCellSuffixPrefix(qualifier),
111                 version, cellGetter);
112     }
113 
114     /**
115      * Builds a new qualifier composed of the HBase qualifier passed + the shadow cell suffix.
116      * @param qualifierArray the qualifier to be suffixed
117      * @param qualOffset the offset where the qualifier starts
118      * @param qualLength the qualifier length
119      * @return the suffixed qualifier
120      */
121     public static byte[] addShadowCellSuffixPrefix(byte[] qualifierArray, int qualOffset, int qualLength) {
122         byte[] result = new byte[qualLength + SHADOW_CELL_SUFFIX.length + SHADOW_CELL_PREFIX.length];
123         System.arraycopy(SHADOW_CELL_PREFIX, 0, result,0 , SHADOW_CELL_PREFIX.length);
124         System.arraycopy(qualifierArray, qualOffset, result, SHADOW_CELL_PREFIX.length, qualLength);
125         System.arraycopy(SHADOW_CELL_SUFFIX, 0, result, qualLength + SHADOW_CELL_PREFIX.length,
126                 SHADOW_CELL_SUFFIX.length);
127         return result;
128     }
129 
130     /**
131      * Builds a new qualifier composed of the HBase qualifier passed + the shadow cell suffix.
132      * Contains a reduced signature to avoid boilerplate code in client side.
133      * @param qualifier
134      *            the qualifier to be suffixed
135      * @return the suffixed qualifier
136      */
137     public static byte[] addShadowCellSuffixPrefix(byte[] qualifier) {
138         return addShadowCellSuffixPrefix(qualifier, 0, qualifier.length);
139     }
140 
141     /**
142      * Builds a new qualifier removing the shadow cell suffix from the
143      * passed HBase qualifier.
144      * @param qualifier the qualifier to remove the suffix from
145      * @param qualOffset the offset where the qualifier starts
146      * @param qualLength the qualifier length
147      * @return the new qualifier without the suffix
148      */
149     public static byte[] removeShadowCellSuffixPrefix(byte[] qualifier, int qualOffset, int qualLength) {
150         if (endsWith(qualifier, qualOffset, qualLength, SHADOW_CELL_SUFFIX)) {
151             if (startsWith(qualifier, qualOffset,qualLength, SHADOW_CELL_PREFIX)) {
152                 return Arrays.copyOfRange(qualifier,
153                         qualOffset + SHADOW_CELL_PREFIX.length,
154                         qualOffset + (qualLength - SHADOW_CELL_SUFFIX.length));
155             } else {
156                 //support backward competatbiliy
157                 return Arrays.copyOfRange(qualifier,
158                         qualOffset,qualOffset + (qualLength - SHADOW_CELL_SUFFIX.length));
159             }
160 
161         }
162 
163         throw new IllegalArgumentException(
164                 "Can't find shadow cell suffix in qualifier "
165                         + Bytes.toString(qualifier));
166     }
167 
168     /**
169      * Returns the qualifier length removing the shadow cell suffix and prefix. In case that que suffix is not found,
170      * just returns the length of the qualifier passed.
171      * @param qualifier the qualifier to remove the suffix from
172      * @param qualOffset the offset where the qualifier starts
173      * @param qualLength the qualifier length
174      * @return the qualifier length without the suffix
175      */
176     public static int qualifierLengthFromShadowCellQualifier(byte[] qualifier, int qualOffset, int qualLength) {
177 
178         if (endsWith(qualifier, qualOffset, qualLength, SHADOW_CELL_SUFFIX)) {
179             if (startsWith(qualifier,qualOffset, qualLength, SHADOW_CELL_PREFIX)) {
180                 return qualLength - SHADOW_CELL_SUFFIX.length - SHADOW_CELL_PREFIX.length;
181             } else {
182                 return qualLength - SHADOW_CELL_SUFFIX.length;
183             }
184         }
185         return qualLength;
186     }
187 
188 
189     /**
190      * Returns the qualifier length removing the shadow cell suffix and prefix. In case that que suffix is not found,
191      * just returns the length of the qualifier passed.
192      * @param qualifier the qualifier to remove the suffix from
193      * @param qualOffset the offset where the qualifier starts
194      * @param qualLength the qualifier length
195      * @return the qualifier length without the suffix
196      */
197     public static int qualifierOffsetFromShadowCellQualifier(byte[] qualifier, int qualOffset, int qualLength) {
198 
199         if (startsWith(qualifier, qualOffset, qualLength, SHADOW_CELL_PREFIX)) {
200             return qualOffset + SHADOW_CELL_PREFIX.length;
201         }
202         return qualOffset;
203     }
204 
205 
206     /**
207      * Complement to matchingQualifier() methods in HBase's CellUtil.class
208      * @param left the cell to compare the qualifier
209      * @param qualArray the explicit qualifier array passed
210      * @param qualOffset the explicit qualifier offset passed
211      * @param qualLen the explicit qualifier length passed
212      * @return whether the qualifiers are equal or not
213      */
214     public static boolean matchingQualifier(final Cell left, final byte[] qualArray, int qualOffset, int qualLen) {
215         return Bytes.equals(left.getQualifierArray(), left.getQualifierOffset(), left.getQualifierLength(),
216                 qualArray, qualOffset, qualLen);
217     }
218 
219     /**
220      * Check that the cell passed meets the requirements for a valid cell identifier with Omid. Basically, users can't:
221      * 1) specify a timestamp
222      * 2) use a particular suffix in the qualifier
223      */
224     public static void validateCell(Cell cell, long startTimestamp) {
225         // Throw exception if timestamp is set by the user
226         if (cell.getTimestamp() != HConstants.LATEST_TIMESTAMP
227                 && cell.getTimestamp() != startTimestamp) {
228             throw new IllegalArgumentException(
229                     "Timestamp not allowed in transactional user operations");
230         }
231         // Throw exception if using a non-allowed qualifier
232         if (isShadowCell(cell)) {
233             throw new IllegalArgumentException(
234                     "Reserved string used in column qualifier");
235         }
236     }
237 
238     /**
239      * Returns whether a cell contains a qualifier that is a delete cell
240      * column qualifier or not.
241      * @param cell the cell to check if contains the delete cell qualifier
242      * @return whether the cell passed contains a delete cell qualifier or not
243      */
244     public static boolean isFamilyDeleteCell(Cell cell) {
245         return CellUtil.matchingQualifier(cell, CellUtils.FAMILY_DELETE_QUALIFIER) &&
246                 CellUtil.matchingValue(cell, HConstants.EMPTY_BYTE_ARRAY);
247     }
248 
249     /**
250      * Returns whether a cell contains a qualifier that is a shadow cell
251      * column qualifier or not.
252      * @param cell the cell to check if contains the shadow cell qualifier
253      * @return whether the cell passed contains a shadow cell qualifier or not
254      */
255     public static boolean isShadowCell(Cell cell) {
256         byte[] qualifier = cell.getQualifierArray();
257         int qualOffset = cell.getQualifierOffset();
258         int qualLength = cell.getQualifierLength();
259 
260         return endsWith(qualifier, qualOffset, qualLength, SHADOW_CELL_SUFFIX);
261     }
262 
263     private static boolean endsWith(byte[] value, int offset, int length, byte[] suffix) {
264         if (length <= suffix.length) {
265             return false;
266         }
267 
268         int suffixOffset = offset + length - suffix.length;
269         int result = Bytes.compareTo(value, suffixOffset, suffix.length,
270                 suffix, 0, suffix.length);
271         return result == 0;
272     }
273 
274     private static boolean startsWith(byte[] value, int offset, int length, byte[] prefix) {
275         if (length <= prefix.length) {
276             return false;
277         }
278 
279         int result = Bytes.compareTo(value, offset, prefix.length,
280                 prefix, 0, prefix.length);
281         return result == 0;
282     }
283 
284     /**
285      * Returns if a cell is marked as a tombstone.
286      * @param cell the cell to check
287      * @return whether the cell is marked as a tombstone or not
288      */
289     public static boolean isTombstone(Cell cell) {
290         return CellUtil.matchingValue(cell, DELETE_TOMBSTONE) ||
291                 CellUtil.matchingValue(cell, LEGACY_DELETE_TOMBSTONE);
292     }
293 
294 
295     /**
296      * Returns a new shadow cell created from a particular cell.
297      * @param cell
298      *            the cell to reconstruct the shadow cell from.
299      * @param shadowCellValue
300      *            the value for the new shadow cell created
301      * @return the brand-new shadow cell
302      */
303     public static Cell buildShadowCellFromCell(Cell cell, byte[] shadowCellValue) {
304         byte[] shadowCellQualifier = addShadowCellSuffixPrefix(cell.getQualifierArray(),
305                 cell.getQualifierOffset(),
306                 cell.getQualifierLength());
307         return new KeyValue(
308                 cell.getRowArray(), cell.getRowOffset(), cell.getRowLength(),
309                 cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength(),
310                 shadowCellQualifier, 0, shadowCellQualifier.length,
311                 cell.getTimestamp(), KeyValue.Type.codeToType(cell.getTypeByte()),
312                 shadowCellValue, 0, shadowCellValue.length);
313     }
314 
315     /**
316      * Analyzes a list of cells, associating the corresponding shadow cell if present.
317      *
318      * @param cells the list of cells to classify
319      * @return a sorted map associating each cell with its shadow cell
320      */
321     public static SortedMap<Cell, Optional<Cell>> mapCellsToShadowCells(List<Cell> cells) {
322 
323         // Move CellComparator to HBaseSims for 2.0 support
324         // Need to access through CellComparatorImpl.COMPARATOR
325         SortedMap<Cell, Optional<Cell>> cellToShadowCellMap
326                 = new TreeMap<Cell, Optional<Cell>>(HBaseShims.cellComparatorInstance());
327 
328         Map<CellId, Cell> cellIdToCellMap = new HashMap<CellId, Cell>();
329         Map<CellId, Cell> cellIdToSCCellMap = new HashMap<CellId, Cell>();
330         for (Cell cell : cells) {
331             if (!isShadowCell(cell)) {
332                 CellId key = new CellId(cell, false);
333                 // Get the current cell and compare the values
334                 Cell storedCell = cellIdToCellMap.get(key);
335                 if (storedCell != null) {
336                     if (CellUtil.matchingValue(cell, storedCell)) {
337                         // TODO: Should we check also here the MVCC and swap if its greater???
338                         // Values are the same, ignore
339                     } else {
340                         if (cell.getSequenceId() > storedCell.getSequenceId()) { // Swap values
341                             Optional<Cell> previousValue = cellToShadowCellMap.remove(storedCell);
342                             Preconditions.checkNotNull(previousValue, "Should contain an Optional<Cell> value");
343                             cellIdToCellMap.put(key, cell);
344                             cellToShadowCellMap.put(cell, previousValue);
345                         } else {
346                             LOG.warn("Cell {} with an earlier MVCC found. Ignoring...", cell);
347                         }
348                     }
349                 } else {
350                     cellIdToCellMap.put(key, cell);
351                     Cell sc = cellIdToSCCellMap.get(key);
352                     if (sc != null) {
353                         cellToShadowCellMap.put(cell, Optional.of(sc));
354                     } else {
355                         cellToShadowCellMap.put(cell, Optional.<Cell>absent());
356                     }
357                 }
358             } else {
359                 CellId key = new CellId(cell, true);
360                 Cell savedCell = cellIdToCellMap.get(key);
361                 if (savedCell != null) {
362                     Cell originalCell = savedCell;
363                     cellToShadowCellMap.put(originalCell, Optional.of(cell));
364                 } else {
365                     cellIdToSCCellMap.put(key, cell);
366                 }
367             }
368         }
369 
370         return cellToShadowCellMap;
371     }
372 
373     private static class CellId {
374 
375         private static final int MIN_BITS = 32;
376 
377         private final Cell cell;
378         private final boolean isShadowCell;
379 
380         CellId(Cell cell, boolean isShadowCell) {
381 
382             this.cell = cell;
383             this.isShadowCell = isShadowCell;
384 
385         }
386 
387         Cell getCell() {
388             return cell;
389         }
390 
391         boolean isShadowCell() {
392             return isShadowCell;
393         }
394 
395         @Override
396         public boolean equals(Object o) {
397             if (o == this)
398                 return true;
399             if (!(o instanceof CellId))
400                 return false;
401             CellId otherCellId = (CellId) o;
402             Cell otherCell = otherCellId.getCell();
403 
404             // Row comparison
405             if (!CellUtil.matchingRow(otherCell, cell)) {
406                 return false;
407             }
408 
409             // Family comparison
410             if (!CellUtil.matchingFamily(otherCell, cell)) {
411                 return false;
412             }
413 
414             // Qualifier comparison
415             int qualifierLength = cell.getQualifierLength();
416             int qualifierOffset = cell.getQualifierOffset();
417             int otherQualifierLength = otherCell.getQualifierLength();
418             int otherQualifierOffset = otherCell.getQualifierOffset();
419 
420             if (isShadowCell()) {
421                 qualifierLength = qualifierLengthFromShadowCellQualifier(cell.getQualifierArray(),
422                         cell.getQualifierOffset(),
423                         cell.getQualifierLength());
424                 qualifierOffset = qualifierOffsetFromShadowCellQualifier(cell.getQualifierArray(), cell.getQualifierOffset(),
425                         cell.getQualifierLength());
426             }
427             if (otherCellId.isShadowCell()) {
428                 otherQualifierLength = qualifierLengthFromShadowCellQualifier(otherCell.getQualifierArray(),
429                         otherCell.getQualifierOffset(),
430                         otherCell.getQualifierLength());
431                 otherQualifierOffset = qualifierOffsetFromShadowCellQualifier(otherCell.getQualifierArray(), otherCell.getQualifierOffset(),
432                         otherCell.getQualifierLength());
433             }
434 
435             if (!Bytes.equals(cell.getQualifierArray(), qualifierOffset, qualifierLength,
436                     otherCell.getQualifierArray(), otherQualifierOffset, otherQualifierLength)) {
437                 return false;
438             }
439 
440             // Timestamp comparison
441             return otherCell.getTimestamp() == cell.getTimestamp();
442 
443         }
444 
445         @Override
446         public int hashCode() {
447             Hasher hasher = Hashing.goodFastHash(MIN_BITS).newHasher();
448             hasher.putBytes(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
449             hasher.putBytes(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
450             int qualifierLength = cell.getQualifierLength();
451             int qualifierOffset = cell.getQualifierOffset();
452             if (isShadowCell()) {
453                 qualifierLength = qualifierLengthFromShadowCellQualifier(cell.getQualifierArray(),
454                         cell.getQualifierOffset(),
455                         cell.getQualifierLength());
456                 if (startsWith(cell.getQualifierArray(), cell.getQualifierOffset(),
457                         cell.getQualifierLength(), SHADOW_CELL_PREFIX)) {
458                     qualifierOffset = qualifierOffset + SHADOW_CELL_PREFIX.length;
459                 }
460             }
461 
462             hasher.putBytes(cell.getQualifierArray(),qualifierOffset , qualifierLength);
463             hasher.putLong(cell.getTimestamp());
464             return hasher.hash().asInt();
465         }
466 
467         @Override
468         public String toString() {
469             ToStringHelper helper = MoreObjects.toStringHelper(this);
470             helper.add("row", Bytes.toStringBinary(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength()));
471             helper.add("family", Bytes.toString(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength()));
472             helper.add("is shadow cell?", isShadowCell);
473             helper.add("qualifier",
474                     Bytes.toString(cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength()));
475             if (isShadowCell()) {
476                 int qualifierLength = qualifierLengthFromShadowCellQualifier(cell.getQualifierArray(),
477                         cell.getQualifierOffset(),
478                         cell.getQualifierLength());
479                 byte[] cellWithoutSc = removeShadowCellSuffixPrefix(cell.getQualifierArray(), cell.getQualifierOffset(), cell.getQualifierLength());
480                 helper.add("qualifier whithout shadow cell suffix", Bytes.toString(cellWithoutSc));
481             }
482             helper.add("ts", cell.getTimestamp());
483             return helper.toString();
484         }
485     }
486 
487 }