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