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