View Javadoc

1   /*
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  package org.apache.hadoop.hbase.regionserver;
20  
21  import java.io.IOException;
22  import java.lang.management.ManagementFactory;
23  import java.lang.management.MemoryMXBean;
24  import java.util.ArrayList;
25  import java.util.Arrays;
26  import java.util.List;
27  import java.util.concurrent.atomic.AtomicLong;
28  import java.util.concurrent.atomic.AtomicReference;
29  
30  import junit.framework.TestCase;
31  
32  import org.apache.commons.logging.Log;
33  import org.apache.commons.logging.LogFactory;
34  import org.apache.hadoop.conf.Configuration;
35  import org.apache.hadoop.fs.Path;
36  import org.apache.hadoop.hbase.Cell;
37  import org.apache.hadoop.hbase.CellUtil;
38  import org.apache.hadoop.hbase.HBaseConfiguration;
39  import org.apache.hadoop.hbase.HBaseTestingUtility;
40  import org.apache.hadoop.hbase.HColumnDescriptor;
41  import org.apache.hadoop.hbase.HConstants;
42  import org.apache.hadoop.hbase.HRegionInfo;
43  import org.apache.hadoop.hbase.HTableDescriptor;
44  import org.apache.hadoop.hbase.KeepDeletedCells;
45  import org.apache.hadoop.hbase.KeyValue;
46  import org.apache.hadoop.hbase.KeyValueTestUtil;
47  import org.apache.hadoop.hbase.KeyValueUtil;
48  import org.apache.hadoop.hbase.TableName;
49  import org.apache.hadoop.hbase.client.Scan;
50  import org.apache.hadoop.hbase.testclassification.MediumTests;
51  import org.apache.hadoop.hbase.util.Bytes;
52  import org.apache.hadoop.hbase.util.EnvironmentEdge;
53  import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
54  import org.apache.hadoop.hbase.wal.WALFactory;
55  import org.junit.experimental.categories.Category;
56  
57  import com.google.common.base.Joiner;
58  import com.google.common.collect.Iterables;
59  import com.google.common.collect.Lists;
60  
61  /** memstore test case */
62  @Category(MediumTests.class)
63  public class TestDefaultMemStore extends TestCase {
64    private final Log LOG = LogFactory.getLog(this.getClass());
65    private DefaultMemStore memstore;
66    private static final int ROW_COUNT = 10;
67    private static final int QUALIFIER_COUNT = ROW_COUNT;
68    private static final byte [] FAMILY = Bytes.toBytes("column");
69    private MultiVersionConsistencyControl mvcc;
70    private AtomicLong startSeqNum = new AtomicLong(0); 
71  
72    @Override
73    public void setUp() throws Exception {
74      super.setUp();
75      this.mvcc = new MultiVersionConsistencyControl();
76      this.memstore = new DefaultMemStore();
77    }
78  
79    public void testPutSameKey() {
80      byte [] bytes = Bytes.toBytes(getName());
81      KeyValue kv = new KeyValue(bytes, bytes, bytes, bytes);
82      this.memstore.add(kv);
83      byte [] other = Bytes.toBytes("somethingelse");
84      KeyValue samekey = new KeyValue(bytes, bytes, bytes, other);
85      this.memstore.add(samekey);
86      Cell found = this.memstore.cellSet.first();
87      assertEquals(1, this.memstore.cellSet.size());
88      assertTrue(Bytes.toString(found.getValue()), CellUtil.matchingValue(samekey, found));
89    }
90  
91    /**
92     * Test memstore snapshot happening while scanning.
93     * @throws IOException
94     */
95    public void testScanAcrossSnapshot() throws IOException {
96      int rowCount = addRows(this.memstore);
97      List<KeyValueScanner> memstorescanners = this.memstore.getScanners(0);
98      Scan scan = new Scan();
99      List<Cell> result = new ArrayList<Cell>();
100     ScanInfo scanInfo =
101         new ScanInfo(null, 0, 1, HConstants.LATEST_TIMESTAMP, KeepDeletedCells.FALSE, 0,
102             this.memstore.comparator);
103     ScanType scanType = ScanType.USER_SCAN;
104     StoreScanner s = new StoreScanner(scan, scanInfo, scanType, null, memstorescanners);
105     int count = 0;
106     try {
107       while (s.next(result)) {
108         LOG.info(result);
109         count++;
110         // Row count is same as column count.
111         assertEquals(rowCount, result.size());
112         result.clear();
113       }
114     } finally {
115       s.close();
116     }
117     assertEquals(rowCount, count);
118     for (KeyValueScanner scanner : memstorescanners) {
119       scanner.close();
120     }
121 
122     memstorescanners = this.memstore.getScanners(mvcc.memstoreReadPoint());
123     // Now assert can count same number even if a snapshot mid-scan.
124     s = new StoreScanner(scan, scanInfo, scanType, null, memstorescanners);
125     count = 0;
126     try {
127       while (s.next(result)) {
128         LOG.info(result);
129         // Assert the stuff is coming out in right order.
130         assertTrue(CellUtil.matchingRow(result.get(0), Bytes.toBytes(count)));
131         count++;
132         // Row count is same as column count.
133         assertEquals(rowCount, result.size());
134         if (count == 2) {
135           this.memstore.snapshot();
136           LOG.info("Snapshotted");
137         }
138         result.clear();
139       }
140     } finally {
141       s.close();
142     }
143     assertEquals(rowCount, count);
144     for (KeyValueScanner scanner : memstorescanners) {
145       scanner.close();
146     }
147     memstorescanners = this.memstore.getScanners(mvcc.memstoreReadPoint());
148     // Assert that new values are seen in kvset as we scan.
149     long ts = System.currentTimeMillis();
150     s = new StoreScanner(scan, scanInfo, scanType, null, memstorescanners);
151     count = 0;
152     int snapshotIndex = 5;
153     try {
154       while (s.next(result)) {
155         LOG.info(result);
156         // Assert the stuff is coming out in right order.
157         assertTrue(CellUtil.matchingRow(result.get(0), Bytes.toBytes(count)));
158         // Row count is same as column count.
159         assertEquals("count=" + count + ", result=" + result, rowCount, result.size());
160         count++;
161         if (count == snapshotIndex) {
162           MemStoreSnapshot snapshot = this.memstore.snapshot();
163           this.memstore.clearSnapshot(snapshot.getId());
164           // Added more rows into kvset.  But the scanner wont see these rows.
165           addRows(this.memstore, ts);
166           LOG.info("Snapshotted, cleared it and then added values (which wont be seen)");
167         }
168         result.clear();
169       }
170     } finally {
171       s.close();
172     }
173     assertEquals(rowCount, count);
174   }
175 
176   /**
177    * A simple test which verifies the 3 possible states when scanning across snapshot.
178    * @throws IOException
179    * @throws CloneNotSupportedException 
180    */
181   public void testScanAcrossSnapshot2() throws IOException, CloneNotSupportedException {
182     // we are going to the scanning across snapshot with two kvs
183     // kv1 should always be returned before kv2
184     final byte[] one = Bytes.toBytes(1);
185     final byte[] two = Bytes.toBytes(2);
186     final byte[] f = Bytes.toBytes("f");
187     final byte[] q = Bytes.toBytes("q");
188     final byte[] v = Bytes.toBytes(3);
189 
190     final KeyValue kv1 = new KeyValue(one, f, q, v);
191     final KeyValue kv2 = new KeyValue(two, f, q, v);
192 
193     // use case 1: both kvs in kvset
194     this.memstore.add(kv1.clone());
195     this.memstore.add(kv2.clone());
196     verifyScanAcrossSnapshot2(kv1, kv2);
197 
198     // use case 2: both kvs in snapshot
199     this.memstore.snapshot();
200     verifyScanAcrossSnapshot2(kv1, kv2);
201 
202     // use case 3: first in snapshot second in kvset
203     this.memstore = new DefaultMemStore();
204     this.memstore.add(kv1.clone());
205     this.memstore.snapshot();
206     this.memstore.add(kv2.clone());
207     verifyScanAcrossSnapshot2(kv1, kv2);
208   }
209 
210   private void verifyScanAcrossSnapshot2(KeyValue kv1, KeyValue kv2)
211       throws IOException {
212     List<KeyValueScanner> memstorescanners = this.memstore.getScanners(mvcc.memstoreReadPoint());
213     assertEquals(1, memstorescanners.size());
214     final KeyValueScanner scanner = memstorescanners.get(0);
215     scanner.seek(KeyValueUtil.createFirstOnRow(HConstants.EMPTY_START_ROW));
216     assertEquals(kv1, scanner.next());
217     assertEquals(kv2, scanner.next());
218     assertNull(scanner.next());
219   }
220 
221   private void assertScannerResults(KeyValueScanner scanner, KeyValue[] expected)
222       throws IOException {
223     scanner.seek(KeyValueUtil.createFirstOnRow(new byte[]{}));
224     List<Cell> returned = Lists.newArrayList();
225 
226     while (true) {
227       Cell next = scanner.next();
228       if (next == null) break;
229       returned.add(next);
230     }
231 
232     assertTrue(
233         "Got:\n" + Joiner.on("\n").join(returned) +
234         "\nExpected:\n" + Joiner.on("\n").join(expected),
235         Iterables.elementsEqual(Arrays.asList(expected), returned));
236     assertNull(scanner.peek());
237   }
238 
239   public void testMemstoreConcurrentControl() throws IOException {
240     final byte[] row = Bytes.toBytes(1);
241     final byte[] f = Bytes.toBytes("family");
242     final byte[] q1 = Bytes.toBytes("q1");
243     final byte[] q2 = Bytes.toBytes("q2");
244     final byte[] v = Bytes.toBytes("value");
245 
246     MultiVersionConsistencyControl.WriteEntry w =
247         mvcc.beginMemstoreInsertWithSeqNum(this.startSeqNum.incrementAndGet());
248 
249     KeyValue kv1 = new KeyValue(row, f, q1, v);
250     kv1.setSequenceId(w.getWriteNumber());
251     memstore.add(kv1);
252 
253     KeyValueScanner s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
254     assertScannerResults(s, new KeyValue[]{});
255 
256     mvcc.completeMemstoreInsert(w);
257 
258     s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
259     assertScannerResults(s, new KeyValue[]{kv1});
260 
261     w = mvcc.beginMemstoreInsertWithSeqNum(this.startSeqNum.incrementAndGet());
262     KeyValue kv2 = new KeyValue(row, f, q2, v);
263     kv2.setSequenceId(w.getWriteNumber());
264     memstore.add(kv2);
265 
266     s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
267     assertScannerResults(s, new KeyValue[]{kv1});
268 
269     mvcc.completeMemstoreInsert(w);
270 
271     s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
272     assertScannerResults(s, new KeyValue[]{kv1, kv2});
273   }
274 
275   /**
276    * Regression test for HBASE-2616, HBASE-2670.
277    * When we insert a higher-memstoreTS version of a cell but with
278    * the same timestamp, we still need to provide consistent reads
279    * for the same scanner.
280    */
281   public void testMemstoreEditsVisibilityWithSameKey() throws IOException {
282     final byte[] row = Bytes.toBytes(1);
283     final byte[] f = Bytes.toBytes("family");
284     final byte[] q1 = Bytes.toBytes("q1");
285     final byte[] q2 = Bytes.toBytes("q2");
286     final byte[] v1 = Bytes.toBytes("value1");
287     final byte[] v2 = Bytes.toBytes("value2");
288 
289     // INSERT 1: Write both columns val1
290     MultiVersionConsistencyControl.WriteEntry w =
291         mvcc.beginMemstoreInsertWithSeqNum(this.startSeqNum.incrementAndGet());
292 
293     KeyValue kv11 = new KeyValue(row, f, q1, v1);
294     kv11.setSequenceId(w.getWriteNumber());
295     memstore.add(kv11);
296 
297     KeyValue kv12 = new KeyValue(row, f, q2, v1);
298     kv12.setSequenceId(w.getWriteNumber());
299     memstore.add(kv12);
300     mvcc.completeMemstoreInsert(w);
301 
302     // BEFORE STARTING INSERT 2, SEE FIRST KVS
303     KeyValueScanner s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
304     assertScannerResults(s, new KeyValue[]{kv11, kv12});
305 
306     // START INSERT 2: Write both columns val2
307     w = mvcc.beginMemstoreInsertWithSeqNum(this.startSeqNum.incrementAndGet());
308     KeyValue kv21 = new KeyValue(row, f, q1, v2);
309     kv21.setSequenceId(w.getWriteNumber());
310     memstore.add(kv21);
311 
312     KeyValue kv22 = new KeyValue(row, f, q2, v2);
313     kv22.setSequenceId(w.getWriteNumber());
314     memstore.add(kv22);
315 
316     // BEFORE COMPLETING INSERT 2, SEE FIRST KVS
317     s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
318     assertScannerResults(s, new KeyValue[]{kv11, kv12});
319 
320     // COMPLETE INSERT 2
321     mvcc.completeMemstoreInsert(w);
322 
323     // NOW SHOULD SEE NEW KVS IN ADDITION TO OLD KVS.
324     // See HBASE-1485 for discussion about what we should do with
325     // the duplicate-TS inserts
326     s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
327     assertScannerResults(s, new KeyValue[]{kv21, kv11, kv22, kv12});
328   }
329 
330   /**
331    * When we insert a higher-memstoreTS deletion of a cell but with
332    * the same timestamp, we still need to provide consistent reads
333    * for the same scanner.
334    */
335   public void testMemstoreDeletesVisibilityWithSameKey() throws IOException {
336     final byte[] row = Bytes.toBytes(1);
337     final byte[] f = Bytes.toBytes("family");
338     final byte[] q1 = Bytes.toBytes("q1");
339     final byte[] q2 = Bytes.toBytes("q2");
340     final byte[] v1 = Bytes.toBytes("value1");
341     // INSERT 1: Write both columns val1
342     MultiVersionConsistencyControl.WriteEntry w =
343         mvcc.beginMemstoreInsertWithSeqNum(this.startSeqNum.incrementAndGet());
344 
345     KeyValue kv11 = new KeyValue(row, f, q1, v1);
346     kv11.setSequenceId(w.getWriteNumber());
347     memstore.add(kv11);
348 
349     KeyValue kv12 = new KeyValue(row, f, q2, v1);
350     kv12.setSequenceId(w.getWriteNumber());
351     memstore.add(kv12);
352     mvcc.completeMemstoreInsert(w);
353 
354     // BEFORE STARTING INSERT 2, SEE FIRST KVS
355     KeyValueScanner s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
356     assertScannerResults(s, new KeyValue[]{kv11, kv12});
357 
358     // START DELETE: Insert delete for one of the columns
359     w = mvcc.beginMemstoreInsertWithSeqNum(this.startSeqNum.incrementAndGet());
360     KeyValue kvDel = new KeyValue(row, f, q2, kv11.getTimestamp(),
361         KeyValue.Type.DeleteColumn);
362     kvDel.setSequenceId(w.getWriteNumber());
363     memstore.add(kvDel);
364 
365     // BEFORE COMPLETING DELETE, SEE FIRST KVS
366     s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
367     assertScannerResults(s, new KeyValue[]{kv11, kv12});
368 
369     // COMPLETE DELETE
370     mvcc.completeMemstoreInsert(w);
371 
372     // NOW WE SHOULD SEE DELETE
373     s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
374     assertScannerResults(s, new KeyValue[]{kv11, kvDel, kv12});
375   }
376 
377 
378   private static class ReadOwnWritesTester extends Thread {
379     static final int NUM_TRIES = 1000;
380 
381     final byte[] row;
382 
383     final byte[] f = Bytes.toBytes("family");
384     final byte[] q1 = Bytes.toBytes("q1");
385 
386     final MultiVersionConsistencyControl mvcc;
387     final MemStore memstore;
388     final AtomicLong startSeqNum;
389 
390     AtomicReference<Throwable> caughtException;
391 
392 
393     public ReadOwnWritesTester(int id,
394                                MemStore memstore,
395                                MultiVersionConsistencyControl mvcc,
396                                AtomicReference<Throwable> caughtException,
397                                AtomicLong startSeqNum)
398     {
399       this.mvcc = mvcc;
400       this.memstore = memstore;
401       this.caughtException = caughtException;
402       row = Bytes.toBytes(id);
403       this.startSeqNum = startSeqNum;
404     }
405 
406     public void run() {
407       try {
408         internalRun();
409       } catch (Throwable t) {
410         caughtException.compareAndSet(null, t);
411       }
412     }
413 
414     private void internalRun() throws IOException {
415       for (long i = 0; i < NUM_TRIES && caughtException.get() == null; i++) {
416         MultiVersionConsistencyControl.WriteEntry w =
417             mvcc.beginMemstoreInsertWithSeqNum(this.startSeqNum.incrementAndGet());
418 
419         // Insert the sequence value (i)
420         byte[] v = Bytes.toBytes(i);
421 
422         KeyValue kv = new KeyValue(row, f, q1, i, v);
423         kv.setSequenceId(w.getWriteNumber());
424         memstore.add(kv);
425         mvcc.completeMemstoreInsert(w);
426 
427         // Assert that we can read back
428         KeyValueScanner s = this.memstore.getScanners(mvcc.memstoreReadPoint()).get(0);
429         s.seek(kv);
430 
431         Cell ret = s.next();
432         assertNotNull("Didnt find own write at all", ret);
433         assertEquals("Didnt read own writes",
434                      kv.getTimestamp(), ret.getTimestamp());
435       }
436     }
437   }
438 
439   public void testReadOwnWritesUnderConcurrency() throws Throwable {
440 
441     int NUM_THREADS = 8;
442 
443     ReadOwnWritesTester threads[] = new ReadOwnWritesTester[NUM_THREADS];
444     AtomicReference<Throwable> caught = new AtomicReference<Throwable>();
445 
446     for (int i = 0; i < NUM_THREADS; i++) {
447       threads[i] = new ReadOwnWritesTester(i, memstore, mvcc, caught, this.startSeqNum);
448       threads[i].start();
449     }
450 
451     for (int i = 0; i < NUM_THREADS; i++) {
452       threads[i].join();
453     }
454 
455     if (caught.get() != null) {
456       throw caught.get();
457     }
458   }
459 
460   /**
461    * Test memstore snapshots
462    * @throws IOException
463    */
464   public void testSnapshotting() throws IOException {
465     final int snapshotCount = 5;
466     // Add some rows, run a snapshot. Do it a few times.
467     for (int i = 0; i < snapshotCount; i++) {
468       addRows(this.memstore);
469       runSnapshot(this.memstore);
470       assertEquals("History not being cleared", 0, this.memstore.snapshot.size());
471     }
472   }
473 
474   public void testMultipleVersionsSimple() throws Exception {
475     DefaultMemStore m = new DefaultMemStore(new Configuration(), KeyValue.COMPARATOR);
476     byte [] row = Bytes.toBytes("testRow");
477     byte [] family = Bytes.toBytes("testFamily");
478     byte [] qf = Bytes.toBytes("testQualifier");
479     long [] stamps = {1,2,3};
480     byte [][] values = {Bytes.toBytes("value0"), Bytes.toBytes("value1"),
481         Bytes.toBytes("value2")};
482     KeyValue key0 = new KeyValue(row, family, qf, stamps[0], values[0]);
483     KeyValue key1 = new KeyValue(row, family, qf, stamps[1], values[1]);
484     KeyValue key2 = new KeyValue(row, family, qf, stamps[2], values[2]);
485 
486     m.add(key0);
487     m.add(key1);
488     m.add(key2);
489 
490     assertTrue("Expected memstore to hold 3 values, actually has " +
491         m.cellSet.size(), m.cellSet.size() == 3);
492   }
493 
494   //////////////////////////////////////////////////////////////////////////////
495   // Get tests
496   //////////////////////////////////////////////////////////////////////////////
497 
498   /** Test getNextRow from memstore
499    * @throws InterruptedException
500    */
501   public void testGetNextRow() throws Exception {
502     addRows(this.memstore);
503     // Add more versions to make it a little more interesting.
504     Thread.sleep(1);
505     addRows(this.memstore);
506     Cell closestToEmpty = this.memstore.getNextRow(KeyValue.LOWESTKEY);
507     assertTrue(KeyValue.COMPARATOR.compareRows(closestToEmpty,
508       new KeyValue(Bytes.toBytes(0), System.currentTimeMillis())) == 0);
509     for (int i = 0; i < ROW_COUNT; i++) {
510       Cell nr = this.memstore.getNextRow(new KeyValue(Bytes.toBytes(i),
511         System.currentTimeMillis()));
512       if (i + 1 == ROW_COUNT) {
513         assertEquals(nr, null);
514       } else {
515         assertTrue(KeyValue.COMPARATOR.compareRows(nr,
516           new KeyValue(Bytes.toBytes(i + 1), System.currentTimeMillis())) == 0);
517       }
518     }
519     //starting from each row, validate results should contain the starting row
520     for (int startRowId = 0; startRowId < ROW_COUNT; startRowId++) {
521       ScanInfo scanInfo = new ScanInfo(FAMILY, 0, 1, Integer.MAX_VALUE, KeepDeletedCells.FALSE,
522           0, this.memstore.comparator);
523       ScanType scanType = ScanType.USER_SCAN;
524       InternalScanner scanner = new StoreScanner(new Scan(
525           Bytes.toBytes(startRowId)), scanInfo, scanType, null,
526           memstore.getScanners(0));
527       List<Cell> results = new ArrayList<Cell>();
528       for (int i = 0; scanner.next(results); i++) {
529         int rowId = startRowId + i;
530         Cell left = results.get(0);
531         byte[] row1 = Bytes.toBytes(rowId);
532         assertTrue(
533             "Row name",
534             KeyValue.COMPARATOR.compareRows(left.getRowArray(), left.getRowOffset(),
535                 (int) left.getRowLength(), row1, 0, row1.length) == 0);
536         assertEquals("Count of columns", QUALIFIER_COUNT, results.size());
537         List<Cell> row = new ArrayList<Cell>();
538         for (Cell kv : results) {
539           row.add(kv);
540         }
541         isExpectedRowWithoutTimestamps(rowId, row);
542         // Clear out set.  Otherwise row results accumulate.
543         results.clear();
544       }
545     }
546   }
547 
548   public void testGet_memstoreAndSnapShot() throws IOException {
549     byte [] row = Bytes.toBytes("testrow");
550     byte [] fam = Bytes.toBytes("testfamily");
551     byte [] qf1 = Bytes.toBytes("testqualifier1");
552     byte [] qf2 = Bytes.toBytes("testqualifier2");
553     byte [] qf3 = Bytes.toBytes("testqualifier3");
554     byte [] qf4 = Bytes.toBytes("testqualifier4");
555     byte [] qf5 = Bytes.toBytes("testqualifier5");
556     byte [] val = Bytes.toBytes("testval");
557 
558     //Setting up memstore
559     memstore.add(new KeyValue(row, fam ,qf1, val));
560     memstore.add(new KeyValue(row, fam ,qf2, val));
561     memstore.add(new KeyValue(row, fam ,qf3, val));
562     //Creating a snapshot
563     memstore.snapshot();
564     assertEquals(3, memstore.snapshot.size());
565     //Adding value to "new" memstore
566     assertEquals(0, memstore.cellSet.size());
567     memstore.add(new KeyValue(row, fam ,qf4, val));
568     memstore.add(new KeyValue(row, fam ,qf5, val));
569     assertEquals(2, memstore.cellSet.size());
570   }
571 
572   //////////////////////////////////////////////////////////////////////////////
573   // Delete tests
574   //////////////////////////////////////////////////////////////////////////////
575   public void testGetWithDelete() throws IOException {
576     byte [] row = Bytes.toBytes("testrow");
577     byte [] fam = Bytes.toBytes("testfamily");
578     byte [] qf1 = Bytes.toBytes("testqualifier");
579     byte [] val = Bytes.toBytes("testval");
580 
581     long ts1 = System.nanoTime();
582     KeyValue put1 = new KeyValue(row, fam, qf1, ts1, val);
583     long ts2 = ts1 + 1;
584     KeyValue put2 = new KeyValue(row, fam, qf1, ts2, val);
585     long ts3 = ts2 +1;
586     KeyValue put3 = new KeyValue(row, fam, qf1, ts3, val);
587     memstore.add(put1);
588     memstore.add(put2);
589     memstore.add(put3);
590 
591     assertEquals(3, memstore.cellSet.size());
592 
593     KeyValue del2 = new KeyValue(row, fam, qf1, ts2, KeyValue.Type.Delete, val);
594     memstore.delete(del2);
595 
596     List<Cell> expected = new ArrayList<Cell>();
597     expected.add(put3);
598     expected.add(del2);
599     expected.add(put2);
600     expected.add(put1);
601 
602     assertEquals(4, memstore.cellSet.size());
603     int i = 0;
604     for(Cell cell : memstore.cellSet) {
605       assertEquals(expected.get(i++), cell);
606     }
607   }
608 
609   public void testGetWithDeleteColumn() throws IOException {
610     byte [] row = Bytes.toBytes("testrow");
611     byte [] fam = Bytes.toBytes("testfamily");
612     byte [] qf1 = Bytes.toBytes("testqualifier");
613     byte [] val = Bytes.toBytes("testval");
614 
615     long ts1 = System.nanoTime();
616     KeyValue put1 = new KeyValue(row, fam, qf1, ts1, val);
617     long ts2 = ts1 + 1;
618     KeyValue put2 = new KeyValue(row, fam, qf1, ts2, val);
619     long ts3 = ts2 +1;
620     KeyValue put3 = new KeyValue(row, fam, qf1, ts3, val);
621     memstore.add(put1);
622     memstore.add(put2);
623     memstore.add(put3);
624 
625     assertEquals(3, memstore.cellSet.size());
626 
627     KeyValue del2 =
628       new KeyValue(row, fam, qf1, ts2, KeyValue.Type.DeleteColumn, val);
629     memstore.delete(del2);
630 
631     List<Cell> expected = new ArrayList<Cell>();
632     expected.add(put3);
633     expected.add(del2);
634     expected.add(put2);
635     expected.add(put1);
636 
637 
638     assertEquals(4, memstore.cellSet.size());
639     int i = 0;
640     for (Cell cell: memstore.cellSet) {
641       assertEquals(expected.get(i++), cell);
642     }
643   }
644 
645 
646   public void testGetWithDeleteFamily() throws IOException {
647     byte [] row = Bytes.toBytes("testrow");
648     byte [] fam = Bytes.toBytes("testfamily");
649     byte [] qf1 = Bytes.toBytes("testqualifier1");
650     byte [] qf2 = Bytes.toBytes("testqualifier2");
651     byte [] qf3 = Bytes.toBytes("testqualifier3");
652     byte [] val = Bytes.toBytes("testval");
653     long ts = System.nanoTime();
654 
655     KeyValue put1 = new KeyValue(row, fam, qf1, ts, val);
656     KeyValue put2 = new KeyValue(row, fam, qf2, ts, val);
657     KeyValue put3 = new KeyValue(row, fam, qf3, ts, val);
658     KeyValue put4 = new KeyValue(row, fam, qf3, ts+1, val);
659 
660     memstore.add(put1);
661     memstore.add(put2);
662     memstore.add(put3);
663     memstore.add(put4);
664 
665     KeyValue del =
666       new KeyValue(row, fam, null, ts, KeyValue.Type.DeleteFamily, val);
667     memstore.delete(del);
668 
669     List<Cell> expected = new ArrayList<Cell>();
670     expected.add(del);
671     expected.add(put1);
672     expected.add(put2);
673     expected.add(put4);
674     expected.add(put3);
675 
676 
677 
678     assertEquals(5, memstore.cellSet.size());
679     int i = 0;
680     for (Cell cell: memstore.cellSet) {
681       assertEquals(expected.get(i++), cell);
682     }
683   }
684 
685   public void testKeepDeleteInmemstore() {
686     byte [] row = Bytes.toBytes("testrow");
687     byte [] fam = Bytes.toBytes("testfamily");
688     byte [] qf = Bytes.toBytes("testqualifier");
689     byte [] val = Bytes.toBytes("testval");
690     long ts = System.nanoTime();
691     memstore.add(new KeyValue(row, fam, qf, ts, val));
692     KeyValue delete = new KeyValue(row, fam, qf, ts, KeyValue.Type.Delete, val);
693     memstore.delete(delete);
694     assertEquals(2, memstore.cellSet.size());
695     assertEquals(delete, memstore.cellSet.first());
696   }
697 
698   public void testRetainsDeleteVersion() throws IOException {
699     // add a put to memstore
700     memstore.add(KeyValueTestUtil.create("row1", "fam", "a", 100, "dont-care"));
701 
702     // now process a specific delete:
703     KeyValue delete = KeyValueTestUtil.create(
704         "row1", "fam", "a", 100, KeyValue.Type.Delete, "dont-care");
705     memstore.delete(delete);
706 
707     assertEquals(2, memstore.cellSet.size());
708     assertEquals(delete, memstore.cellSet.first());
709   }
710   public void testRetainsDeleteColumn() throws IOException {
711     // add a put to memstore
712     memstore.add(KeyValueTestUtil.create("row1", "fam", "a", 100, "dont-care"));
713 
714     // now process a specific delete:
715     KeyValue delete = KeyValueTestUtil.create("row1", "fam", "a", 100,
716         KeyValue.Type.DeleteColumn, "dont-care");
717     memstore.delete(delete);
718 
719     assertEquals(2, memstore.cellSet.size());
720     assertEquals(delete, memstore.cellSet.first());
721   }
722   public void testRetainsDeleteFamily() throws IOException {
723     // add a put to memstore
724     memstore.add(KeyValueTestUtil.create("row1", "fam", "a", 100, "dont-care"));
725 
726     // now process a specific delete:
727     KeyValue delete = KeyValueTestUtil.create("row1", "fam", "a", 100,
728         KeyValue.Type.DeleteFamily, "dont-care");
729     memstore.delete(delete);
730 
731     assertEquals(2, memstore.cellSet.size());
732     assertEquals(delete, memstore.cellSet.first());
733   }
734 
735   ////////////////////////////////////
736   //Test for timestamps
737   ////////////////////////////////////
738 
739   /**
740    * Test to ensure correctness when using Memstore with multiple timestamps
741    */
742   public void testMultipleTimestamps() throws IOException {
743     long[] timestamps = new long[] {20,10,5,1};
744     Scan scan = new Scan();
745 
746     for (long timestamp: timestamps)
747       addRows(memstore,timestamp);
748 
749     scan.setTimeRange(0, 2);
750     assertTrue(memstore.shouldSeek(scan, Long.MIN_VALUE));
751 
752     scan.setTimeRange(20, 82);
753     assertTrue(memstore.shouldSeek(scan, Long.MIN_VALUE));
754 
755     scan.setTimeRange(10, 20);
756     assertTrue(memstore.shouldSeek(scan, Long.MIN_VALUE));
757 
758     scan.setTimeRange(8, 12);
759     assertTrue(memstore.shouldSeek(scan, Long.MIN_VALUE));
760 
761     /*This test is not required for correctness but it should pass when
762      * timestamp range optimization is on*/
763     //scan.setTimeRange(28, 42);
764     //assertTrue(!memstore.shouldSeek(scan));
765   }
766 
767   ////////////////////////////////////
768   //Test for upsert with MSLAB
769   ////////////////////////////////////
770 
771   /**
772    * Test a pathological pattern that shows why we can't currently
773    * use the MSLAB for upsert workloads. This test inserts data
774    * in the following pattern:
775    *
776    * - row0001 through row1000 (fills up one 2M Chunk)
777    * - row0002 through row1001 (fills up another 2M chunk, leaves one reference
778    *   to the first chunk
779    * - row0003 through row1002 (another chunk, another dangling reference)
780    *
781    * This causes OOME pretty quickly if we use MSLAB for upsert
782    * since each 2M chunk is held onto by a single reference.
783    */
784   public void testUpsertMSLAB() throws Exception {
785     Configuration conf = HBaseConfiguration.create();
786     conf.setBoolean(DefaultMemStore.USEMSLAB_KEY, true);
787     memstore = new DefaultMemStore(conf, KeyValue.COMPARATOR);
788 
789     int ROW_SIZE = 2048;
790     byte[] qualifier = new byte[ROW_SIZE - 4];
791 
792     MemoryMXBean bean = ManagementFactory.getMemoryMXBean();
793     for (int i = 0; i < 3; i++) { System.gc(); }
794     long usageBefore = bean.getHeapMemoryUsage().getUsed();
795 
796     long size = 0;
797     long ts=0;
798 
799     for (int newValue = 0; newValue < 1000; newValue++) {
800       for (int row = newValue; row < newValue + 1000; row++) {
801         byte[] rowBytes = Bytes.toBytes(row);
802         size += memstore.updateColumnValue(rowBytes, FAMILY, qualifier, newValue, ++ts);
803       }
804     }
805     System.out.println("Wrote " + ts + " vals");
806     for (int i = 0; i < 3; i++) { System.gc(); }
807     long usageAfter = bean.getHeapMemoryUsage().getUsed();
808     System.out.println("Memory used: " + (usageAfter - usageBefore)
809         + " (heapsize: " + memstore.heapSize() +
810         " size: " + size + ")");
811   }
812 
813   //////////////////////////////////////////////////////////////////////////////
814   // Helpers
815   //////////////////////////////////////////////////////////////////////////////
816   private static byte [] makeQualifier(final int i1, final int i2){
817     return Bytes.toBytes(Integer.toString(i1) + ";" +
818         Integer.toString(i2));
819   }
820 
821   /**
822    * Add keyvalues with a fixed memstoreTs, and checks that memstore size is decreased
823    * as older keyvalues are deleted from the memstore.
824    * @throws Exception
825    */
826   public void testUpsertMemstoreSize() throws Exception {
827     Configuration conf = HBaseConfiguration.create();
828     memstore = new DefaultMemStore(conf, KeyValue.COMPARATOR);
829     long oldSize = memstore.size.get();
830 
831     List<Cell> l = new ArrayList<Cell>();
832     KeyValue kv1 = KeyValueTestUtil.create("r", "f", "q", 100, "v");
833     KeyValue kv2 = KeyValueTestUtil.create("r", "f", "q", 101, "v");
834     KeyValue kv3 = KeyValueTestUtil.create("r", "f", "q", 102, "v");
835 
836     kv1.setSequenceId(1); kv2.setSequenceId(1);kv3.setSequenceId(1);
837     l.add(kv1); l.add(kv2); l.add(kv3);
838 
839     this.memstore.upsert(l, 2);// readpoint is 2
840     long newSize = this.memstore.size.get();
841     assert(newSize > oldSize);
842     //The kv1 should be removed.
843     assert(memstore.cellSet.size() == 2);
844     
845     KeyValue kv4 = KeyValueTestUtil.create("r", "f", "q", 104, "v");
846     kv4.setSequenceId(1);
847     l.clear(); l.add(kv4);
848     this.memstore.upsert(l, 3);
849     assertEquals(newSize, this.memstore.size.get());
850     //The kv2 should be removed.
851     assert(memstore.cellSet.size() == 2);
852     //this.memstore = null;
853   }
854 
855   ////////////////////////////////////
856   // Test for periodic memstore flushes 
857   // based on time of oldest edit
858   ////////////////////////////////////
859 
860   /**
861    * Tests that the timeOfOldestEdit is updated correctly for the 
862    * various edit operations in memstore.
863    * @throws Exception
864    */
865   public void testUpdateToTimeOfOldestEdit() throws Exception {
866     try {
867       EnvironmentEdgeForMemstoreTest edge = new EnvironmentEdgeForMemstoreTest();
868       EnvironmentEdgeManager.injectEdge(edge);
869       DefaultMemStore memstore = new DefaultMemStore();
870       long t = memstore.timeOfOldestEdit();
871       assertEquals(t, Long.MAX_VALUE);
872 
873       // test the case that the timeOfOldestEdit is updated after a KV add
874       memstore.add(KeyValueTestUtil.create("r", "f", "q", 100, "v"));
875       t = memstore.timeOfOldestEdit();
876       assertTrue(t == 1234);
877       // snapshot() will reset timeOfOldestEdit. The method will also assert the 
878       // value is reset to Long.MAX_VALUE
879       t = runSnapshot(memstore);
880 
881       // test the case that the timeOfOldestEdit is updated after a KV delete
882       memstore.delete(KeyValueTestUtil.create("r", "f", "q", 100, "v"));
883       t = memstore.timeOfOldestEdit();
884       assertTrue(t == 1234);
885       t = runSnapshot(memstore);
886 
887       // test the case that the timeOfOldestEdit is updated after a KV upsert
888       List<Cell> l = new ArrayList<Cell>();
889       KeyValue kv1 = KeyValueTestUtil.create("r", "f", "q", 100, "v");
890       kv1.setSequenceId(100);
891       l.add(kv1);
892       memstore.upsert(l, 1000);
893       t = memstore.timeOfOldestEdit();
894       assertTrue(t == 1234);
895     } finally {
896       EnvironmentEdgeManager.reset();
897     }
898   }
899 
900   /**
901    * Tests the HRegion.shouldFlush method - adds an edit in the memstore
902    * and checks that shouldFlush returns true, and another where it disables
903    * the periodic flush functionality and tests whether shouldFlush returns
904    * false. 
905    * @throws Exception
906    */
907   public void testShouldFlush() throws Exception {
908     Configuration conf = new Configuration();
909     conf.setInt(HRegion.MEMSTORE_PERIODIC_FLUSH_INTERVAL, 1000);
910     checkShouldFlush(conf, true);
911     // test disable flush
912     conf.setInt(HRegion.MEMSTORE_PERIODIC_FLUSH_INTERVAL, 0);
913     checkShouldFlush(conf, false);
914   }
915 
916   private void checkShouldFlush(Configuration conf, boolean expected) throws Exception {
917     try {
918       EnvironmentEdgeForMemstoreTest edge = new EnvironmentEdgeForMemstoreTest();
919       EnvironmentEdgeManager.injectEdge(edge);
920       HBaseTestingUtility hbaseUtility = HBaseTestingUtility.createLocalHTU(conf);
921       HRegion region = hbaseUtility.createTestRegion("foobar", new HColumnDescriptor("foo"));
922 
923       List<Store> stores = region.getStores();
924       assertTrue(stores.size() == 1);
925 
926       Store s = stores.iterator().next();
927       edge.setCurrentTimeMillis(1234);
928       s.add(KeyValueTestUtil.create("r", "f", "q", 100, "v"));
929       edge.setCurrentTimeMillis(1234 + 100);
930       assertTrue(region.shouldFlush() == false);
931       edge.setCurrentTimeMillis(1234 + 10000);
932       assertTrue(region.shouldFlush() == expected);
933     } finally {
934       EnvironmentEdgeManager.reset();
935     }
936   }
937 
938   public void testShouldFlushMeta() throws Exception {
939     // write an edit in the META and ensure the shouldFlush (that the periodic memstore
940     // flusher invokes) returns true after META_CACHE_FLUSH_INTERVAL (even though
941     // the MEMSTORE_PERIODIC_FLUSH_INTERVAL is set to a higher value)
942     Configuration conf = new Configuration();
943     conf.setInt(HRegion.MEMSTORE_PERIODIC_FLUSH_INTERVAL, HRegion.META_CACHE_FLUSH_INTERVAL * 10);
944     HBaseTestingUtility hbaseUtility = HBaseTestingUtility.createLocalHTU(conf);
945     Path testDir = hbaseUtility.getDataTestDir();
946     EnvironmentEdgeForMemstoreTest edge = new EnvironmentEdgeForMemstoreTest();
947     EnvironmentEdgeManager.injectEdge(edge);
948     edge.setCurrentTimeMillis(1234);
949     WALFactory wFactory = new WALFactory(conf, null, "1234");
950     HRegion meta = HRegion.createHRegion(HRegionInfo.FIRST_META_REGIONINFO, testDir,
951         conf, HTableDescriptor.metaTableDescriptor(conf),
952         wFactory.getMetaWAL(HRegionInfo.FIRST_META_REGIONINFO.
953             getEncodedNameAsBytes()));
954     HRegionInfo hri = new HRegionInfo(TableName.valueOf("testShouldFlushMeta"),
955         Bytes.toBytes("row_0200"), Bytes.toBytes("row_0300"));
956     HTableDescriptor desc = new HTableDescriptor(TableName.valueOf("testShouldFlushMeta"));
957     desc.addFamily(new HColumnDescriptor("foo".getBytes()));
958     HRegion r =
959         HRegion.createHRegion(hri, testDir, conf, desc,
960             wFactory.getWAL(hri.getEncodedNameAsBytes()));
961     HRegion.addRegionToMETA(meta, r);
962     edge.setCurrentTimeMillis(1234 + 100);
963     assertTrue(meta.shouldFlush() == false);
964     edge.setCurrentTimeMillis(edge.currentTime() + HRegion.META_CACHE_FLUSH_INTERVAL + 1);
965     assertTrue(meta.shouldFlush() == true);
966   }
967 
968   private class EnvironmentEdgeForMemstoreTest implements EnvironmentEdge {
969     long t = 1234;
970     @Override
971     public long currentTime() {
972       return t; 
973     }
974     public void setCurrentTimeMillis(long t) {
975       this.t = t;
976     }
977   }
978 
979   /**
980    * Adds {@link #ROW_COUNT} rows and {@link #QUALIFIER_COUNT}
981    * @param hmc Instance to add rows to.
982    * @return How many rows we added.
983    * @throws IOException
984    */
985   private int addRows(final MemStore hmc) {
986     return addRows(hmc, HConstants.LATEST_TIMESTAMP);
987   }
988 
989   /**
990    * Adds {@link #ROW_COUNT} rows and {@link #QUALIFIER_COUNT}
991    * @param hmc Instance to add rows to.
992    * @return How many rows we added.
993    * @throws IOException
994    */
995   private int addRows(final MemStore hmc, final long ts) {
996     for (int i = 0; i < ROW_COUNT; i++) {
997       long timestamp = ts == HConstants.LATEST_TIMESTAMP?
998         System.currentTimeMillis(): ts;
999       for (int ii = 0; ii < QUALIFIER_COUNT; ii++) {
1000         byte [] row = Bytes.toBytes(i);
1001         byte [] qf = makeQualifier(i, ii);
1002         hmc.add(new KeyValue(row, FAMILY, qf, timestamp, qf));
1003       }
1004     }
1005     return ROW_COUNT;
1006   }
1007 
1008   private long runSnapshot(final DefaultMemStore hmc) throws UnexpectedStateException {
1009     // Save off old state.
1010     int oldHistorySize = hmc.snapshot.size();
1011     MemStoreSnapshot snapshot = hmc.snapshot();
1012     // Make some assertions about what just happened.
1013     assertTrue("History size has not increased", oldHistorySize < hmc.snapshot.size());
1014     long t = memstore.timeOfOldestEdit();
1015     assertTrue("Time of oldest edit is not Long.MAX_VALUE", t == Long.MAX_VALUE);
1016     hmc.clearSnapshot(snapshot.getId());
1017     return t;
1018   }
1019 
1020   private void isExpectedRowWithoutTimestamps(final int rowIndex,
1021       List<Cell> kvs) {
1022     int i = 0;
1023     for (Cell kv: kvs) {
1024       byte[] expectedColname = makeQualifier(rowIndex, i++);
1025       assertTrue("Column name", CellUtil.matchingQualifier(kv, expectedColname));
1026       // Value is column name as bytes.  Usually result is
1027       // 100 bytes in size at least. This is the default size
1028       // for BytesWriteable.  For comparison, convert bytes to
1029       // String and trim to remove trailing null bytes.
1030       assertTrue("Content", CellUtil.matchingValue(kv, expectedColname));
1031     }
1032   }
1033 
1034   private static void addRows(int count, final MemStore mem) {
1035     long nanos = System.nanoTime();
1036 
1037     for (int i = 0 ; i < count ; i++) {
1038       if (i % 1000 == 0) {
1039 
1040         System.out.println(i + " Took for 1k usec: " + (System.nanoTime() - nanos)/1000);
1041         nanos = System.nanoTime();
1042       }
1043       long timestamp = System.currentTimeMillis();
1044 
1045       for (int ii = 0; ii < QUALIFIER_COUNT ; ii++) {
1046         byte [] row = Bytes.toBytes(i);
1047         byte [] qf = makeQualifier(i, ii);
1048         mem.add(new KeyValue(row, FAMILY, qf, timestamp, qf));
1049       }
1050     }
1051   }
1052 
1053 
1054   static void doScan(MemStore ms, int iteration) throws IOException {
1055     long nanos = System.nanoTime();
1056     KeyValueScanner s = ms.getScanners(0).get(0);
1057     s.seek(KeyValueUtil.createFirstOnRow(new byte[]{}));
1058 
1059     System.out.println(iteration + " create/seek took: " + (System.nanoTime() - nanos)/1000);
1060     int cnt=0;
1061     while(s.next() != null) ++cnt;
1062 
1063     System.out.println(iteration + " took usec: " + (System.nanoTime() - nanos) / 1000 + " for: "
1064         + cnt);
1065 
1066   }
1067 
1068   public static void main(String [] args) throws IOException {
1069     MemStore ms = new DefaultMemStore();
1070 
1071     long n1 = System.nanoTime();
1072     addRows(25000, ms);
1073     System.out.println("Took for insert: " + (System.nanoTime()-n1)/1000);
1074 
1075     System.out.println("foo");
1076 
1077     for (int i = 0 ; i < 50 ; i++)
1078       doScan(ms, i);
1079   }
1080 }
1081