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>. n 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}