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