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