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}