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