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  /** Returns the minimumTimestamp */
173  public abstract long getMin();
174
175  /** Returns the maximumTimestamp */
176  public abstract long getMax();
177
178  @Override
179  public String toString() {
180    return "[" + getMin() + "," + getMax() + "]";
181  }
182
183  /**
184   * @param data the serialization data. It can't be null!
185   * @return An instance of NonSyncTimeRangeTracker filled w/ the content of serialized
186   *         NonSyncTimeRangeTracker in <code>timeRangeTrackerBytes</code>.
187   */
188  public static TimeRangeTracker parseFrom(final byte[] data) throws IOException {
189    return parseFrom(data, Type.NON_SYNC);
190  }
191
192  public static TimeRangeTracker parseFrom(final byte[] data, Type type) throws IOException {
193    Preconditions.checkNotNull(data, "input data is null!");
194    if (ProtobufUtil.isPBMagicPrefix(data)) {
195      int pblen = ProtobufUtil.lengthOfPBMagic();
196      HBaseProtos.TimeRangeTracker.Builder builder = HBaseProtos.TimeRangeTracker.newBuilder();
197      ProtobufUtil.mergeFrom(builder, data, pblen, data.length - pblen);
198      return TimeRangeTracker.create(type, builder.getFrom(), builder.getTo());
199    } else {
200      try (DataInputStream in = new DataInputStream(new ByteArrayInputStream(data))) {
201        return TimeRangeTracker.create(type, in.readLong(), in.readLong());
202      }
203    }
204  }
205
206  /**
207   * This method used to serialize TimeRangeTracker (TRT) by protobuf while this breaks the forward
208   * compatibility on HFile.(See HBASE-21008) In previous hbase version ( < 2.0.0 ) we use
209   * DataOutput to serialize TRT, these old versions don't have capability to deserialize TRT which
210   * is serialized by protobuf. So we need to revert the change of serializing TimeRangeTracker back
211   * to DataOutput. For more information, please check HBASE-21012.
212   * @param tracker TimeRangeTracker needed to be serialized.
213   * @return byte array filled with serialized TimeRangeTracker.
214   * @throws IOException if something goes wrong in writeLong.
215   */
216  public static byte[] toByteArray(TimeRangeTracker tracker) throws IOException {
217    try (ByteArrayOutputStream bos = new ByteArrayOutputStream()) {
218      try (DataOutputStream dos = new DataOutputStream(bos)) {
219        dos.writeLong(tracker.getMin());
220        dos.writeLong(tracker.getMax());
221        return bos.toByteArray();
222      }
223    }
224  }
225
226  /** Returns Make a TimeRange from current state of <code>this</code>. */
227  TimeRange toTimeRange() {
228    long min = getMin();
229    long max = getMax();
230    // Initial TimeRangeTracker timestamps are the opposite of what you want for a TimeRange. Fix!
231    if (min == INITIAL_MIN_TIMESTAMP) {
232      min = TimeRange.INITIAL_MIN_TIMESTAMP;
233    }
234    if (max == INITIAL_MAX_TIMESTAMP) {
235      max = TimeRange.INITIAL_MAX_TIMESTAMP;
236    }
237    return new TimeRange(min, max);
238  }
239
240  // In order to estimate the heap size, this inner class need to be accessible to TestHeapSize.
241  public static class NonSyncTimeRangeTracker extends TimeRangeTracker {
242    private long minimumTimestamp = INITIAL_MIN_TIMESTAMP;
243    private long maximumTimestamp = INITIAL_MAX_TIMESTAMP;
244
245    NonSyncTimeRangeTracker() {
246    }
247
248    NonSyncTimeRangeTracker(final TimeRangeTracker trt) {
249      this.minimumTimestamp = trt.getMin();
250      this.maximumTimestamp = trt.getMax();
251    }
252
253    NonSyncTimeRangeTracker(long minimumTimestamp, long maximumTimestamp) {
254      this.minimumTimestamp = minimumTimestamp;
255      this.maximumTimestamp = maximumTimestamp;
256    }
257
258    @Override
259    protected void setMax(long ts) {
260      maximumTimestamp = ts;
261    }
262
263    @Override
264    protected void setMin(long ts) {
265      minimumTimestamp = ts;
266    }
267
268    @Override
269    protected boolean compareAndSetMin(long expect, long update) {
270      if (minimumTimestamp != expect) {
271        return false;
272      }
273      minimumTimestamp = update;
274      return true;
275    }
276
277    @Override
278    protected boolean compareAndSetMax(long expect, long update) {
279      if (maximumTimestamp != expect) {
280        return false;
281      }
282      maximumTimestamp = update;
283      return true;
284    }
285
286    @Override
287    public long getMin() {
288      return minimumTimestamp;
289    }
290
291    @Override
292    public long getMax() {
293      return maximumTimestamp;
294    }
295  }
296
297  // In order to estimate the heap size, this inner class need to be accessible to TestHeapSize.
298  public static class SyncTimeRangeTracker extends TimeRangeTracker {
299    private final AtomicLong minimumTimestamp = new AtomicLong(INITIAL_MIN_TIMESTAMP);
300    private final AtomicLong maximumTimestamp = new AtomicLong(INITIAL_MAX_TIMESTAMP);
301
302    private SyncTimeRangeTracker() {
303    }
304
305    SyncTimeRangeTracker(final TimeRangeTracker trt) {
306      this.minimumTimestamp.set(trt.getMin());
307      this.maximumTimestamp.set(trt.getMax());
308    }
309
310    SyncTimeRangeTracker(long minimumTimestamp, long maximumTimestamp) {
311      this.minimumTimestamp.set(minimumTimestamp);
312      this.maximumTimestamp.set(maximumTimestamp);
313    }
314
315    @Override
316    protected void setMax(long ts) {
317      maximumTimestamp.set(ts);
318    }
319
320    @Override
321    protected void setMin(long ts) {
322      minimumTimestamp.set(ts);
323    }
324
325    @Override
326    protected boolean compareAndSetMin(long expect, long update) {
327      return minimumTimestamp.compareAndSet(expect, update);
328    }
329
330    @Override
331    protected boolean compareAndSetMax(long expect, long update) {
332      return maximumTimestamp.compareAndSet(expect, update);
333    }
334
335    @Override
336    public long getMin() {
337      return minimumTimestamp.get();
338    }
339
340    @Override
341    public long getMax() {
342      return maximumTimestamp.get();
343    }
344  }
345}