1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.hadoop.hbase.regionserver;
20
21 import java.util.NavigableMap;
22 import java.util.NavigableSet;
23 import java.util.TreeMap;
24 import java.util.TreeSet;
25
26 import org.apache.hadoop.hbase.classification.InterfaceAudience;
27 import org.apache.hadoop.hbase.Cell;
28 import org.apache.hadoop.hbase.HConstants;
29 import org.apache.hadoop.hbase.KeyValue;
30 import org.apache.hadoop.hbase.KeyValue.KVComparator;
31 import org.apache.hadoop.hbase.util.Bytes;
32
33
34
35
36
37
38
39 @InterfaceAudience.Private
40 class GetClosestRowBeforeTracker {
41 private final KeyValue targetkey;
42
43 private final long now;
44 private final long oldestUnexpiredTs;
45 private KeyValue candidate = null;
46 private final KVComparator kvcomparator;
47
48 private final boolean metaregion;
49
50 private final int rowoffset;
51 private final int tablenamePlusDelimiterLength;
52
53
54 private final NavigableMap<KeyValue, NavigableSet<KeyValue>> deletes;
55
56
57
58
59
60
61
62
63 GetClosestRowBeforeTracker(final KVComparator c, final KeyValue kv,
64 final long ttl, final boolean metaregion) {
65 super();
66 this.metaregion = metaregion;
67 this.targetkey = kv;
68
69
70 this.rowoffset = kv.getRowOffset();
71 int l = -1;
72 if (metaregion) {
73 l = KeyValue.getDelimiter(kv.getBuffer(), rowoffset, kv.getRowLength(),
74 HConstants.DELIMITER) - this.rowoffset;
75 }
76 this.tablenamePlusDelimiterLength = metaregion? l + 1: -1;
77 this.now = System.currentTimeMillis();
78 this.oldestUnexpiredTs = now - ttl;
79 this.kvcomparator = c;
80 KeyValue.RowOnlyComparator rc = new KeyValue.RowOnlyComparator(this.kvcomparator);
81 this.deletes = new TreeMap<KeyValue, NavigableSet<KeyValue>>(rc);
82 }
83
84
85
86
87
88 private void addDelete(final KeyValue kv) {
89 NavigableSet<KeyValue> rowdeletes = this.deletes.get(kv);
90 if (rowdeletes == null) {
91 rowdeletes = new TreeSet<KeyValue>(this.kvcomparator);
92 this.deletes.put(kv, rowdeletes);
93 }
94 rowdeletes.add(kv);
95 }
96
97
98
99
100
101 private boolean addCandidate(final KeyValue kv) {
102 if (!isDeleted(kv) && isBetterCandidate(kv)) {
103 this.candidate = kv;
104 return true;
105 }
106 return false;
107 }
108
109 boolean isBetterCandidate(final KeyValue contender) {
110 return this.candidate == null ||
111 (this.kvcomparator.compareRows(this.candidate, contender) < 0 &&
112 this.kvcomparator.compareRows(contender, this.targetkey) <= 0);
113 }
114
115
116
117
118
119
120
121 private boolean isDeleted(final KeyValue kv) {
122 if (this.deletes.isEmpty()) return false;
123 NavigableSet<KeyValue> rowdeletes = this.deletes.get(kv);
124 if (rowdeletes == null || rowdeletes.isEmpty()) return false;
125 return isDeleted(kv, rowdeletes);
126 }
127
128
129
130
131
132
133
134
135 public boolean isDeleted(final KeyValue kv, final NavigableSet<KeyValue> ds) {
136 if (deletes == null || deletes.isEmpty()) return false;
137 for (KeyValue d: ds) {
138 long kvts = kv.getTimestamp();
139 long dts = d.getTimestamp();
140 if (d.isDeleteFamily()) {
141 if (kvts <= dts) return true;
142 continue;
143 }
144
145 int ret = Bytes.compareTo(kv.getBuffer(), kv.getQualifierOffset(),
146 kv.getQualifierLength(),
147 d.getBuffer(), d.getQualifierOffset(), d.getQualifierLength());
148 if (ret <= -1) {
149
150 continue;
151 } else if (ret >= 1) {
152
153 break;
154 }
155
156 if (kvts > dts) return false;
157
158
159 switch (KeyValue.Type.codeToType(d.getType())) {
160 case Delete: return kvts == dts;
161 case DeleteColumn: return true;
162 default: continue;
163 }
164 }
165 return false;
166 }
167
168
169
170
171
172 public boolean isExpired(final Cell cell) {
173 return cell.getTimestamp() < this.oldestUnexpiredTs ||
174 HStore.isCellTTLExpired(cell, this.oldestUnexpiredTs, this.now);
175 }
176
177
178
179
180
181
182
183
184
185 boolean handleDeletes(final KeyValue kv) {
186 addDelete(kv);
187 boolean deleted = false;
188 if (!hasCandidate()) return deleted;
189 if (isDeleted(this.candidate)) {
190 this.candidate = null;
191 deleted = true;
192 }
193 return deleted;
194 }
195
196
197
198
199
200
201 boolean handle(final KeyValue kv) {
202 if (kv.isDelete()) {
203 handleDeletes(kv);
204 return false;
205 }
206 return addCandidate(kv);
207 }
208
209
210
211
212 public boolean hasCandidate() {
213 return this.candidate != null;
214 }
215
216
217
218
219 public KeyValue getCandidate() {
220 return this.candidate;
221 }
222
223 public KeyValue getTargetKey() {
224 return this.targetkey;
225 }
226
227
228
229
230
231
232 boolean isTooFar(final KeyValue kv, final KeyValue firstOnRow) {
233 return this.kvcomparator.compareRows(kv, firstOnRow) > 0;
234 }
235
236 boolean isTargetTable(final KeyValue kv) {
237 if (!metaregion) return true;
238
239
240 return Bytes.compareTo(this.targetkey.getBuffer(), this.rowoffset,
241 this.tablenamePlusDelimiterLength,
242 kv.getBuffer(), kv.getRowOffset(), this.tablenamePlusDelimiterLength) == 0;
243 }
244 }