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