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