001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.regionserver;
019
020import java.io.ByteArrayInputStream;
021import java.io.ByteArrayOutputStream;
022import java.io.DataInputStream;
023import java.io.DataOutputStream;
024import java.io.IOException;
025import java.util.concurrent.atomic.AtomicLong;
026import org.apache.hadoop.hbase.Cell;
027import org.apache.hadoop.hbase.PrivateCellUtil;
028import org.apache.hadoop.hbase.io.TimeRange;
029import org.apache.yetus.audience.InterfaceAudience;
030
031import org.apache.hbase.thirdparty.com.google.common.base.Preconditions;
032
033import org.apache.hadoop.hbase.shaded.protobuf.ProtobufUtil;
034import org.apache.hadoop.hbase.shaded.protobuf.generated.HBaseProtos;
035
036/**
037 * Stores minimum and maximum timestamp values, it is [minimumTimestamp, maximumTimestamp] in
038 * interval notation. Use this class at write-time ONLY. Too much synchronization to use at read
039 * time Use {@link TimeRange} at read time instead of this. See toTimeRange() to make TimeRange to
040 * use. MemStores use this class to track minimum and maximum timestamps. The TimeRangeTracker made
041 * by the MemStore is passed to the StoreFile for it to write out as part a flush in the the file
042 * metadata. If no memstore involved -- i.e. a compaction -- then the StoreFile will calculate its
043 * own TimeRangeTracker as it appends. The StoreFile serialized TimeRangeTracker is used at read
044 * time via an instance of {@link TimeRange} to test if Cells fit the StoreFile TimeRange.
045 */
046@InterfaceAudience.Private
047public abstract class TimeRangeTracker {
048
049  public enum Type {
050    // thread-unsafe
051    NON_SYNC,
052    // thread-safe
053    SYNC
054  }
055
056  static final long INITIAL_MIN_TIMESTAMP = Long.MAX_VALUE;
057  static final long INITIAL_MAX_TIMESTAMP = -1L;
058
059  public static TimeRangeTracker create(Type type) {
060    switch (type) {
061      case NON_SYNC:
062        return new NonSyncTimeRangeTracker();
063      case SYNC:
064        return new SyncTimeRangeTracker();
065      default:
066        throw new UnsupportedOperationException("The type:" + type + " is unsupported");
067    }
068  }
069
070  public static TimeRangeTracker create(Type type, TimeRangeTracker trt) {
071    switch (type) {
072      case NON_SYNC:
073        return new NonSyncTimeRangeTracker(trt);
074      case SYNC:
075        return new SyncTimeRangeTracker(trt);
076      default:
077        throw new UnsupportedOperationException("The type:" + type + " is unsupported");
078    }
079  }
080
081  public static TimeRangeTracker create(Type type, long minimumTimestamp, long maximumTimestamp) {
082    switch (type) {
083      case NON_SYNC:
084        return new NonSyncTimeRangeTracker(minimumTimestamp, maximumTimestamp);
085      case SYNC:
086        return new SyncTimeRangeTracker(minimumTimestamp, maximumTimestamp);
087      default:
088        throw new UnsupportedOperationException("The type:" + type + " is unsupported");
089    }
090  }
091
092  protected abstract void setMax(long ts);
093
094  protected abstract void setMin(long ts);
095
096  protected abstract boolean compareAndSetMin(long expect, long update);
097
098  protected abstract boolean compareAndSetMax(long expect, long update);
099
100  /**
101   * Update the current TimestampRange to include the timestamp from <code>cell</code>. If the Key
102   * is of type DeleteColumn or DeleteFamily, it includes the entire time range from 0 to timestamp
103   * of the key.
104   * @param cell the Cell to include
105   */
106  public void includeTimestamp(final Cell cell) {
107    includeTimestamp(cell.getTimestamp());
108    if (PrivateCellUtil.isDeleteColumnOrFamily(cell)) {
109      includeTimestamp(0);
110    }
111  }
112
113  /**
114   * If required, update the current TimestampRange to include timestamp
115   * @param timestamp the timestamp value to include
116   */
117  @edu.umd.cs.findbugs.annotations.SuppressWarnings(value = "MT_CORRECTNESS",
118      justification = "Intentional")
119  void includeTimestamp(final long timestamp) {
120    long initialMinTimestamp = getMin();
121    if (timestamp < initialMinTimestamp) {
122      long curMinTimestamp = initialMinTimestamp;
123      while (timestamp < curMinTimestamp) {
124        if (!compareAndSetMin(curMinTimestamp, timestamp)) {
125          curMinTimestamp = getMin();
126        } else {
127          // successfully set minimumTimestamp, break.
128          break;
129        }
130      }
131
132      // When it reaches here, there are two possibilities:
133      // 1). timestamp >= curMinTimestamp, someone already sets the minimumTimestamp. In this case,
134      // it still needs to check if initialMinTimestamp == INITIAL_MIN_TIMESTAMP to see
135      // if it needs to update minimumTimestamp. Someone may already set both
136      // minimumTimestamp/minimumTimestamp to the same value(curMinTimestamp),
137      // need to check if maximumTimestamp needs to be updated.
138      // 2). timestamp < curMinTimestamp, it sets the minimumTimestamp successfully.
139      // In this case,it still needs to check if initialMinTimestamp == INITIAL_MIN_TIMESTAMP
140      // to see if it needs to set maximumTimestamp.
141      if (initialMinTimestamp != INITIAL_MIN_TIMESTAMP) {
142        // Someone already sets minimumTimestamp and timestamp is less than minimumTimestamp.
143        // In this case, no need to set maximumTimestamp as it will be set to at least
144        // initialMinTimestamp.
145        return;
146      }
147    }
148
149    long curMaxTimestamp = getMax();
150
151    if (timestamp > curMaxTimestamp) {
152      while (timestamp > curMaxTimestamp) {
153        if (!compareAndSetMax(curMaxTimestamp, timestamp)) {
154          curMaxTimestamp = getMax();
155        } else {
156          // successfully set maximumTimestamp, break
157          break;
158        }
159      }
160    }
161  }
162
163  /**
164   * Check if the range has ANY overlap with TimeRange
165   * @param tr TimeRange, it expects [minStamp, maxStamp)
166   * @return True if there is overlap, false otherwise
167   */
168  public boolean includesTimeRange(final TimeRange tr) {
169    return (getMin() < tr.getMax() && getMax() >= tr.getMin());
170  }
171
172  /**
173   * @return the minimumTimestamp
174   */
175  public abstract long getMin();
176
177  /**
178   * @return the maximumTimestamp
179   */
180  public abstract long getMax();
181
182  @Override
183  public String toString() {
184    return "[" + getMin() + "," + getMax() + "]";
185  }
186
187  /**
188   * @param data the serialization data. It can't be null!
189   * @return An instance of NonSyncTimeRangeTracker filled w/ the content of serialized
190   *         NonSyncTimeRangeTracker in <code>timeRangeTrackerBytes</code>. n
191   */
192  public static TimeRangeTracker parseFrom(final byte[] data) throws IOException {
193    return parseFrom(data, Type.NON_SYNC);
194  }
195
196  public static TimeRangeTracker parseFrom(final byte[] data, Type type) throws IOException {
197    Preconditions.checkNotNull(data, "input data is null!");
198    if (ProtobufUtil.isPBMagicPrefix(data)) {
199      int pblen = ProtobufUtil.lengthOfPBMagic();
200      HBaseProtos.TimeRangeTracker.Builder builder = HBaseProtos.TimeRangeTracker.newBuilder();
201      ProtobufUtil.mergeFrom(builder, data, pblen, data.length - pblen);
202      return TimeRangeTracker.create(type, builder.getFrom(), builder.getTo());
203    } else {
204      try (DataInputStream in = new DataInputStream(new ByteArrayInputStream(data))) {
205        return TimeRangeTracker.create(type, in.readLong(), in.readLong());
206      }
207    }
208  }
209
210  /**
211   * This method used to serialize TimeRangeTracker (TRT) by protobuf while this breaks the forward
212   * compatibility on HFile.(See HBASE-21008) In previous hbase version ( < 2.0.0 ) we use
213   * DataOutput to serialize TRT, these old versions don't have capability to deserialize TRT which
214   * is serialized by protobuf. So we need to revert the change of serializing TimeRangeTracker back
215   * to DataOutput. For more information, please check HBASE-21012.
216   * @param tracker TimeRangeTracker needed to be serialized.
217   * @return byte array filled with serialized TimeRangeTracker.
218   * @throws IOException if something goes wrong in writeLong.
219   */
220  public static byte[] toByteArray(TimeRangeTracker tracker) throws IOException {
221    try (ByteArrayOutputStream bos = new ByteArrayOutputStream()) {
222      try (DataOutputStream dos = new DataOutputStream(bos)) {
223        dos.writeLong(tracker.getMin());
224        dos.writeLong(tracker.getMax());
225        return bos.toByteArray();
226      }
227    }
228  }
229
230  /**
231   * @return Make a TimeRange from current state of <code>this</code>.
232   */
233  TimeRange toTimeRange() {
234    long min = getMin();
235    long max = getMax();
236    // Initial TimeRangeTracker timestamps are the opposite of what you want for a TimeRange. Fix!
237    if (min == INITIAL_MIN_TIMESTAMP) {
238      min = TimeRange.INITIAL_MIN_TIMESTAMP;
239    }
240    if (max == INITIAL_MAX_TIMESTAMP) {
241      max = TimeRange.INITIAL_MAX_TIMESTAMP;
242    }
243    return TimeRange.between(min, max);
244  }
245
246  // In order to estimate the heap size, this inner class need to be accessible to TestHeapSize.
247  public static class NonSyncTimeRangeTracker extends TimeRangeTracker {
248    private long minimumTimestamp = INITIAL_MIN_TIMESTAMP;
249    private long maximumTimestamp = INITIAL_MAX_TIMESTAMP;
250
251    NonSyncTimeRangeTracker() {
252    }
253
254    NonSyncTimeRangeTracker(final TimeRangeTracker trt) {
255      this.minimumTimestamp = trt.getMin();
256      this.maximumTimestamp = trt.getMax();
257    }
258
259    NonSyncTimeRangeTracker(long minimumTimestamp, long maximumTimestamp) {
260      this.minimumTimestamp = minimumTimestamp;
261      this.maximumTimestamp = maximumTimestamp;
262    }
263
264    @Override
265    protected void setMax(long ts) {
266      maximumTimestamp = ts;
267    }
268
269    @Override
270    protected void setMin(long ts) {
271      minimumTimestamp = ts;
272    }
273
274    @Override
275    protected boolean compareAndSetMin(long expect, long update) {
276      if (minimumTimestamp != expect) {
277        return false;
278      }
279      minimumTimestamp = update;
280      return true;
281    }
282
283    @Override
284    protected boolean compareAndSetMax(long expect, long update) {
285      if (maximumTimestamp != expect) {
286        return false;
287      }
288      maximumTimestamp = update;
289      return true;
290    }
291
292    @Override
293    public long getMin() {
294      return minimumTimestamp;
295    }
296
297    @Override
298    public long getMax() {
299      return maximumTimestamp;
300    }
301  }
302
303  // In order to estimate the heap size, this inner class need to be accessible to TestHeapSize.
304  public static class SyncTimeRangeTracker extends TimeRangeTracker {
305    private final AtomicLong minimumTimestamp = new AtomicLong(INITIAL_MIN_TIMESTAMP);
306    private final AtomicLong maximumTimestamp = new AtomicLong(INITIAL_MAX_TIMESTAMP);
307
308    private SyncTimeRangeTracker() {
309    }
310
311    SyncTimeRangeTracker(final TimeRangeTracker trt) {
312      this.minimumTimestamp.set(trt.getMin());
313      this.maximumTimestamp.set(trt.getMax());
314    }
315
316    SyncTimeRangeTracker(long minimumTimestamp, long maximumTimestamp) {
317      this.minimumTimestamp.set(minimumTimestamp);
318      this.maximumTimestamp.set(maximumTimestamp);
319    }
320
321    @Override
322    protected void setMax(long ts) {
323      maximumTimestamp.set(ts);
324    }
325
326    @Override
327    protected void setMin(long ts) {
328      minimumTimestamp.set(ts);
329    }
330
331    @Override
332    protected boolean compareAndSetMin(long expect, long update) {
333      return minimumTimestamp.compareAndSet(expect, update);
334    }
335
336    @Override
337    protected boolean compareAndSetMax(long expect, long update) {
338      return maximumTimestamp.compareAndSet(expect, update);
339    }
340
341    @Override
342    public long getMin() {
343      return minimumTimestamp.get();
344    }
345
346    @Override
347    public long getMax() {
348      return maximumTimestamp.get();
349    }
350  }
351}