001/**
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.regionserver;
019
020import static org.junit.Assert.assertEquals;
021import static org.junit.Assert.assertNotNull;
022import static org.junit.Assert.assertNull;
023import static org.junit.Assert.assertTrue;
024
025import java.io.IOException;
026import java.util.ArrayList;
027import java.util.Arrays;
028import java.util.List;
029import java.util.Objects;
030import java.util.concurrent.atomic.AtomicLong;
031import java.util.concurrent.atomic.AtomicReference;
032import org.apache.hadoop.conf.Configuration;
033import org.apache.hadoop.fs.Path;
034import org.apache.hadoop.hbase.Cell;
035import org.apache.hadoop.hbase.CellComparatorImpl;
036import org.apache.hadoop.hbase.CellUtil;
037import org.apache.hadoop.hbase.HBaseClassTestRule;
038import org.apache.hadoop.hbase.HBaseConfiguration;
039import org.apache.hadoop.hbase.HBaseTestingUtility;
040import org.apache.hadoop.hbase.HConstants;
041import org.apache.hadoop.hbase.KeepDeletedCells;
042import org.apache.hadoop.hbase.KeyValue;
043import org.apache.hadoop.hbase.KeyValueTestUtil;
044import org.apache.hadoop.hbase.KeyValueUtil;
045import org.apache.hadoop.hbase.TableName;
046import org.apache.hadoop.hbase.client.ColumnFamilyDescriptorBuilder;
047import org.apache.hadoop.hbase.client.Put;
048import org.apache.hadoop.hbase.client.RegionInfo;
049import org.apache.hadoop.hbase.client.RegionInfoBuilder;
050import org.apache.hadoop.hbase.client.Scan;
051import org.apache.hadoop.hbase.client.TableDescriptor;
052import org.apache.hadoop.hbase.client.TableDescriptorBuilder;
053import org.apache.hadoop.hbase.exceptions.UnexpectedStateException;
054import org.apache.hadoop.hbase.testclassification.MediumTests;
055import org.apache.hadoop.hbase.testclassification.RegionServerTests;
056import org.apache.hadoop.hbase.util.Bytes;
057import org.apache.hadoop.hbase.util.EnvironmentEdge;
058import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
059import org.apache.hadoop.hbase.util.FSTableDescriptors;
060import org.apache.hadoop.hbase.wal.WALFactory;
061import org.junit.AfterClass;
062import org.junit.Before;
063import org.junit.ClassRule;
064import org.junit.Rule;
065import org.junit.Test;
066import org.junit.experimental.categories.Category;
067import org.junit.rules.TestName;
068import org.slf4j.Logger;
069import org.slf4j.LoggerFactory;
070
071import org.apache.hbase.thirdparty.com.google.common.base.Joiner;
072import org.apache.hbase.thirdparty.com.google.common.collect.Iterables;
073import org.apache.hbase.thirdparty.com.google.common.collect.Lists;
074
075/** memstore test case */
076@Category({RegionServerTests.class, MediumTests.class})
077public class TestDefaultMemStore {
078
079  @ClassRule
080  public static final HBaseClassTestRule CLASS_RULE =
081      HBaseClassTestRule.forClass(TestDefaultMemStore.class);
082
083  private static final Logger LOG = LoggerFactory.getLogger(TestDefaultMemStore.class);
084  @Rule public TestName name = new TestName();
085  protected AbstractMemStore memstore;
086  protected static final int ROW_COUNT = 10;
087  protected static final int QUALIFIER_COUNT = ROW_COUNT;
088  protected static final byte[] FAMILY = Bytes.toBytes("column");
089  protected MultiVersionConcurrencyControl mvcc;
090  protected AtomicLong startSeqNum = new AtomicLong(0);
091  protected ChunkCreator chunkCreator;
092
093  private String getName() {
094    return this.name.getMethodName();
095  }
096
097  @Before
098  public void setUp() throws Exception {
099    internalSetUp();
100    // no pool
101    this.chunkCreator =
102        ChunkCreator.initialize(MemStoreLABImpl.CHUNK_SIZE_DEFAULT, false, 0, 0, 0, null);
103    this.memstore = new DefaultMemStore();
104  }
105
106  @AfterClass
107  public static void tearDownClass() throws Exception {
108    ChunkCreator.getInstance().clearChunkIds();
109  }
110
111  protected void internalSetUp() throws Exception {
112    this.mvcc = new MultiVersionConcurrencyControl();
113  }
114
115  @Test
116  public void testPutSameKey() {
117    byte[] bytes = Bytes.toBytes(getName());
118    KeyValue kv = new KeyValue(bytes, bytes, bytes, bytes);
119    this.memstore.add(kv, null);
120    byte[] other = Bytes.toBytes("somethingelse");
121    KeyValue samekey = new KeyValue(bytes, bytes, bytes, other);
122    this.memstore.add(samekey, null);
123    Cell found = this.memstore.getActive().first();
124    assertEquals(1, this.memstore.getActive().getCellsCount());
125    assertTrue(Bytes.toString(found.getValueArray()), CellUtil.matchingValue(samekey, found));
126  }
127
128  @Test
129  public void testPutSameCell() {
130    byte[] bytes = Bytes.toBytes(getName());
131    KeyValue kv = new KeyValue(bytes, bytes, bytes, bytes);
132    MemStoreSizing sizeChangeForFirstCell = new NonThreadSafeMemStoreSizing();
133    this.memstore.add(kv, sizeChangeForFirstCell);
134    MemStoreSizing sizeChangeForSecondCell = new NonThreadSafeMemStoreSizing();
135    this.memstore.add(kv, sizeChangeForSecondCell);
136    // make sure memstore size increase won't double-count MSLAB chunk size
137    assertEquals(Segment.getCellLength(kv), sizeChangeForFirstCell.getMemStoreSize().getDataSize());
138    Segment segment = this.memstore.getActive();
139    MemStoreLAB msLab = segment.getMemStoreLAB();
140    if (msLab != null) {
141      // make sure memstore size increased even when writing the same cell, if using MSLAB
142      assertEquals(Segment.getCellLength(kv),
143          sizeChangeForSecondCell.getMemStoreSize().getDataSize());
144      // make sure chunk size increased even when writing the same cell, if using MSLAB
145      if (msLab instanceof MemStoreLABImpl) {
146        // since we add the chunkID at the 0th offset of the chunk and the
147        // chunkid is an int we need to account for those 4 bytes
148        assertEquals(2 * Segment.getCellLength(kv) + Bytes.SIZEOF_INT,
149          ((MemStoreLABImpl) msLab).getCurrentChunk().getNextFreeOffset());
150      }
151    } else {
152      // make sure no memstore size change w/o MSLAB
153      assertEquals(0, sizeChangeForSecondCell.getMemStoreSize().getDataSize());
154      assertEquals(0, sizeChangeForSecondCell.getMemStoreSize().getHeapSize());
155    }
156  }
157
158  /**
159   * Test memstore snapshot happening while scanning.
160   * @throws IOException
161   */
162  @Test
163  public void testScanAcrossSnapshot() throws IOException {
164    int rowCount = addRows(this.memstore);
165    List<KeyValueScanner> memstorescanners = this.memstore.getScanners(0);
166    Scan scan = new Scan();
167    List<Cell> result = new ArrayList<>();
168    Configuration conf = HBaseConfiguration.create();
169    ScanInfo scanInfo = new ScanInfo(conf, null, 0, 1, HConstants.LATEST_TIMESTAMP,
170        KeepDeletedCells.FALSE, HConstants.DEFAULT_BLOCKSIZE, 0, this.memstore.getComparator(), false);
171    int count = 0;
172    try (StoreScanner s = new StoreScanner(scan, scanInfo, null, memstorescanners)) {
173      while (s.next(result)) {
174        LOG.info(Objects.toString(result));
175        count++;
176        // Row count is same as column count.
177        assertEquals(rowCount, result.size());
178        result.clear();
179      }
180    }
181    assertEquals(rowCount, count);
182    for (KeyValueScanner scanner : memstorescanners) {
183      scanner.close();
184    }
185
186    memstorescanners = this.memstore.getScanners(mvcc.getReadPoint());
187    // Now assert can count same number even if a snapshot mid-scan.
188    count = 0;
189    try (StoreScanner s = new StoreScanner(scan, scanInfo, null, memstorescanners)) {
190      while (s.next(result)) {
191        LOG.info(Objects.toString(result));
192        // Assert the stuff is coming out in right order.
193        assertTrue(CellUtil.matchingRows(result.get(0), Bytes.toBytes(count)));
194        count++;
195        // Row count is same as column count.
196        assertEquals(rowCount, result.size());
197        if (count == 2) {
198          this.memstore.snapshot();
199          LOG.info("Snapshotted");
200        }
201        result.clear();
202      }
203    }
204    assertEquals(rowCount, count);
205    for (KeyValueScanner scanner : memstorescanners) {
206      scanner.close();
207    }
208    memstorescanners = this.memstore.getScanners(mvcc.getReadPoint());
209    // Assert that new values are seen in kvset as we scan.
210    long ts = System.currentTimeMillis();
211    count = 0;
212    int snapshotIndex = 5;
213    try (StoreScanner s = new StoreScanner(scan, scanInfo, null, memstorescanners)) {
214      while (s.next(result)) {
215        LOG.info(Objects.toString(result));
216        // Assert the stuff is coming out in right order.
217        assertTrue(CellUtil.matchingRows(result.get(0), Bytes.toBytes(count)));
218        // Row count is same as column count.
219        assertEquals("count=" + count + ", result=" + result, rowCount, result.size());
220        count++;
221        if (count == snapshotIndex) {
222          MemStoreSnapshot snapshot = this.memstore.snapshot();
223          this.memstore.clearSnapshot(snapshot.getId());
224          // Added more rows into kvset. But the scanner wont see these rows.
225          addRows(this.memstore, ts);
226          LOG.info("Snapshotted, cleared it and then added values (which wont be seen)");
227        }
228        result.clear();
229      }
230    }
231    assertEquals(rowCount, count);
232  }
233
234  /**
235   * A simple test which verifies the 3 possible states when scanning across snapshot.
236   * @throws IOException
237   * @throws CloneNotSupportedException
238   */
239  @Test
240  public void testScanAcrossSnapshot2() throws IOException, CloneNotSupportedException {
241    // we are going to the scanning across snapshot with two kvs
242    // kv1 should always be returned before kv2
243    final byte[] one = Bytes.toBytes(1);
244    final byte[] two = Bytes.toBytes(2);
245    final byte[] f = Bytes.toBytes("f");
246    final byte[] q = Bytes.toBytes("q");
247    final byte[] v = Bytes.toBytes(3);
248
249    final KeyValue kv1 = new KeyValue(one, f, q, v);
250    final KeyValue kv2 = new KeyValue(two, f, q, v);
251
252    // use case 1: both kvs in kvset
253    this.memstore.add(kv1.clone(), null);
254    this.memstore.add(kv2.clone(), null);
255    verifyScanAcrossSnapshot2(kv1, kv2);
256
257    // use case 2: both kvs in snapshot
258    this.memstore.snapshot();
259    verifyScanAcrossSnapshot2(kv1, kv2);
260
261    // use case 3: first in snapshot second in kvset
262    this.memstore = new DefaultMemStore();
263    this.memstore.add(kv1.clone(), null);
264    this.memstore.snapshot();
265    this.memstore.add(kv2.clone(), null);
266    verifyScanAcrossSnapshot2(kv1, kv2);
267  }
268
269  protected void verifyScanAcrossSnapshot2(KeyValue kv1, KeyValue kv2)
270      throws IOException {
271    List<KeyValueScanner> memstorescanners = this.memstore.getScanners(mvcc.getReadPoint());
272    assertEquals(2, memstorescanners.size());
273    final KeyValueScanner scanner0 = memstorescanners.get(0);
274    final KeyValueScanner scanner1 = memstorescanners.get(1);
275    scanner0.seek(KeyValueUtil.createFirstOnRow(HConstants.EMPTY_START_ROW));
276    scanner1.seek(KeyValueUtil.createFirstOnRow(HConstants.EMPTY_START_ROW));
277    Cell n0 = scanner0.next();
278    Cell n1 = scanner1.next();
279    assertTrue(kv1.equals(n0) || kv1.equals(n1));
280    assertTrue(kv2.equals(n0)
281        || kv2.equals(n1)
282        || kv2.equals(scanner0.next())
283        || kv2.equals(scanner1.next()));
284    assertNull(scanner0.next());
285    assertNull(scanner1.next());
286  }
287
288  protected void assertScannerResults(KeyValueScanner scanner, KeyValue[] expected)
289      throws IOException {
290    scanner.seek(KeyValueUtil.createFirstOnRow(new byte[]{}));
291    List<Cell> returned = Lists.newArrayList();
292
293    while (true) {
294      Cell next = scanner.next();
295      if (next == null) break;
296      returned.add(next);
297    }
298
299    assertTrue(
300        "Got:\n" + Joiner.on("\n").join(returned) +
301        "\nExpected:\n" + Joiner.on("\n").join(expected),
302        Iterables.elementsEqual(Arrays.asList(expected), returned));
303    assertNull(scanner.peek());
304  }
305
306  @Test
307  public void testMemstoreConcurrentControl() throws IOException {
308    final byte[] row = Bytes.toBytes(1);
309    final byte[] f = Bytes.toBytes("family");
310    final byte[] q1 = Bytes.toBytes("q1");
311    final byte[] q2 = Bytes.toBytes("q2");
312    final byte[] v = Bytes.toBytes("value");
313
314    MultiVersionConcurrencyControl.WriteEntry w =
315        mvcc.begin();
316
317    KeyValue kv1 = new KeyValue(row, f, q1, v);
318    kv1.setSequenceId(w.getWriteNumber());
319    memstore.add(kv1, null);
320
321    KeyValueScanner s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
322    assertScannerResults(s, new KeyValue[]{});
323
324    mvcc.completeAndWait(w);
325
326    s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
327    assertScannerResults(s, new KeyValue[]{kv1});
328
329    w = mvcc.begin();
330    KeyValue kv2 = new KeyValue(row, f, q2, v);
331    kv2.setSequenceId(w.getWriteNumber());
332    memstore.add(kv2, null);
333
334    s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
335    assertScannerResults(s, new KeyValue[]{kv1});
336
337    mvcc.completeAndWait(w);
338
339    s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
340    assertScannerResults(s, new KeyValue[]{kv1, kv2});
341  }
342
343  /**
344   * Regression test for HBASE-2616, HBASE-2670.
345   * When we insert a higher-memstoreTS version of a cell but with
346   * the same timestamp, we still need to provide consistent reads
347   * for the same scanner.
348   */
349  @Test
350  public void testMemstoreEditsVisibilityWithSameKey() throws IOException {
351    final byte[] row = Bytes.toBytes(1);
352    final byte[] f = Bytes.toBytes("family");
353    final byte[] q1 = Bytes.toBytes("q1");
354    final byte[] q2 = Bytes.toBytes("q2");
355    final byte[] v1 = Bytes.toBytes("value1");
356    final byte[] v2 = Bytes.toBytes("value2");
357
358    // INSERT 1: Write both columns val1
359    MultiVersionConcurrencyControl.WriteEntry w =
360        mvcc.begin();
361
362    KeyValue kv11 = new KeyValue(row, f, q1, v1);
363    kv11.setSequenceId(w.getWriteNumber());
364    memstore.add(kv11, null);
365
366    KeyValue kv12 = new KeyValue(row, f, q2, v1);
367    kv12.setSequenceId(w.getWriteNumber());
368    memstore.add(kv12, null);
369    mvcc.completeAndWait(w);
370
371    // BEFORE STARTING INSERT 2, SEE FIRST KVS
372    KeyValueScanner s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
373    assertScannerResults(s, new KeyValue[]{kv11, kv12});
374
375    // START INSERT 2: Write both columns val2
376    w = mvcc.begin();
377    KeyValue kv21 = new KeyValue(row, f, q1, v2);
378    kv21.setSequenceId(w.getWriteNumber());
379    memstore.add(kv21, null);
380
381    KeyValue kv22 = new KeyValue(row, f, q2, v2);
382    kv22.setSequenceId(w.getWriteNumber());
383    memstore.add(kv22, null);
384
385    // BEFORE COMPLETING INSERT 2, SEE FIRST KVS
386    s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
387    assertScannerResults(s, new KeyValue[]{kv11, kv12});
388
389    // COMPLETE INSERT 2
390    mvcc.completeAndWait(w);
391
392    // NOW SHOULD SEE NEW KVS IN ADDITION TO OLD KVS.
393    // See HBASE-1485 for discussion about what we should do with
394    // the duplicate-TS inserts
395    s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
396    assertScannerResults(s, new KeyValue[]{kv21, kv11, kv22, kv12});
397  }
398
399  /**
400   * When we insert a higher-memstoreTS deletion of a cell but with
401   * the same timestamp, we still need to provide consistent reads
402   * for the same scanner.
403   */
404  @Test
405  public void testMemstoreDeletesVisibilityWithSameKey() throws IOException {
406    final byte[] row = Bytes.toBytes(1);
407    final byte[] f = Bytes.toBytes("family");
408    final byte[] q1 = Bytes.toBytes("q1");
409    final byte[] q2 = Bytes.toBytes("q2");
410    final byte[] v1 = Bytes.toBytes("value1");
411    // INSERT 1: Write both columns val1
412    MultiVersionConcurrencyControl.WriteEntry w =
413        mvcc.begin();
414
415    KeyValue kv11 = new KeyValue(row, f, q1, v1);
416    kv11.setSequenceId(w.getWriteNumber());
417    memstore.add(kv11, null);
418
419    KeyValue kv12 = new KeyValue(row, f, q2, v1);
420    kv12.setSequenceId(w.getWriteNumber());
421    memstore.add(kv12, null);
422    mvcc.completeAndWait(w);
423
424    // BEFORE STARTING INSERT 2, SEE FIRST KVS
425    KeyValueScanner s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
426    assertScannerResults(s, new KeyValue[]{kv11, kv12});
427
428    // START DELETE: Insert delete for one of the columns
429    w = mvcc.begin();
430    KeyValue kvDel = new KeyValue(row, f, q2, kv11.getTimestamp(),
431        KeyValue.Type.DeleteColumn);
432    kvDel.setSequenceId(w.getWriteNumber());
433    memstore.add(kvDel, null);
434
435    // BEFORE COMPLETING DELETE, SEE FIRST KVS
436    s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
437    assertScannerResults(s, new KeyValue[]{kv11, kv12});
438
439    // COMPLETE DELETE
440    mvcc.completeAndWait(w);
441
442    // NOW WE SHOULD SEE DELETE
443    s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
444    assertScannerResults(s, new KeyValue[]{kv11, kvDel, kv12});
445  }
446
447
448  private static class ReadOwnWritesTester extends Thread {
449    static final int NUM_TRIES = 1000;
450
451    final byte[] row;
452
453    final byte[] f = Bytes.toBytes("family");
454    final byte[] q1 = Bytes.toBytes("q1");
455
456    final MultiVersionConcurrencyControl mvcc;
457    final MemStore memstore;
458
459    AtomicReference<Throwable> caughtException;
460
461
462    public ReadOwnWritesTester(int id, MemStore memstore, MultiVersionConcurrencyControl mvcc,
463        AtomicReference<Throwable> caughtException) {
464      this.mvcc = mvcc;
465      this.memstore = memstore;
466      this.caughtException = caughtException;
467      row = Bytes.toBytes(id);
468    }
469
470    @Override
471    public void run() {
472      try {
473        internalRun();
474      } catch (Throwable t) {
475        caughtException.compareAndSet(null, t);
476      }
477    }
478
479    private void internalRun() throws IOException {
480      for (long i = 0; i < NUM_TRIES && caughtException.get() == null; i++) {
481        MultiVersionConcurrencyControl.WriteEntry w =
482            mvcc.begin();
483
484        // Insert the sequence value (i)
485        byte[] v = Bytes.toBytes(i);
486
487        KeyValue kv = new KeyValue(row, f, q1, i, v);
488        kv.setSequenceId(w.getWriteNumber());
489        memstore.add(kv, null);
490        mvcc.completeAndWait(w);
491
492        // Assert that we can read back
493        KeyValueScanner s = this.memstore.getScanners(mvcc.getReadPoint()).get(0);
494        s.seek(kv);
495
496        Cell ret = s.next();
497        assertNotNull("Didnt find own write at all", ret);
498        assertEquals("Didnt read own writes",
499                     kv.getTimestamp(), ret.getTimestamp());
500      }
501    }
502  }
503
504  @Test
505  public void testReadOwnWritesUnderConcurrency() throws Throwable {
506    int NUM_THREADS = 8;
507
508    ReadOwnWritesTester threads[] = new ReadOwnWritesTester[NUM_THREADS];
509    AtomicReference<Throwable> caught = new AtomicReference<>();
510
511    for (int i = 0; i < NUM_THREADS; i++) {
512      threads[i] = new ReadOwnWritesTester(i, memstore, mvcc, caught);
513      threads[i].start();
514    }
515
516    for (int i = 0; i < NUM_THREADS; i++) {
517      threads[i].join();
518    }
519
520    if (caught.get() != null) {
521      throw caught.get();
522    }
523  }
524
525  /**
526   * Test memstore snapshots
527   * @throws IOException
528   */
529  @Test
530  public void testSnapshotting() throws IOException {
531    final int snapshotCount = 5;
532    // Add some rows, run a snapshot. Do it a few times.
533    for (int i = 0; i < snapshotCount; i++) {
534      addRows(this.memstore);
535      runSnapshot(this.memstore);
536      assertEquals("History not being cleared", 0, this.memstore.getSnapshot().getCellsCount());
537    }
538  }
539
540  @Test
541  public void testMultipleVersionsSimple() throws Exception {
542    DefaultMemStore m = new DefaultMemStore(new Configuration(), CellComparatorImpl.COMPARATOR);
543    byte [] row = Bytes.toBytes("testRow");
544    byte [] family = Bytes.toBytes("testFamily");
545    byte [] qf = Bytes.toBytes("testQualifier");
546    long [] stamps = {1,2,3};
547    byte [][] values = {Bytes.toBytes("value0"), Bytes.toBytes("value1"),
548        Bytes.toBytes("value2")};
549    KeyValue key0 = new KeyValue(row, family, qf, stamps[0], values[0]);
550    KeyValue key1 = new KeyValue(row, family, qf, stamps[1], values[1]);
551    KeyValue key2 = new KeyValue(row, family, qf, stamps[2], values[2]);
552
553    m.add(key0, null);
554    m.add(key1, null);
555    m.add(key2, null);
556
557    assertTrue("Expected memstore to hold 3 values, actually has " +
558        m.getActive().getCellsCount(), m.getActive().getCellsCount() == 3);
559  }
560
561  //////////////////////////////////////////////////////////////////////////////
562  // Get tests
563  //////////////////////////////////////////////////////////////////////////////
564
565  /** Test getNextRow from memstore
566   * @throws InterruptedException
567   */
568  @Test
569  public void testGetNextRow() throws Exception {
570    addRows(this.memstore);
571    // Add more versions to make it a little more interesting.
572    Thread.sleep(1);
573    addRows(this.memstore);
574    Cell closestToEmpty = ((DefaultMemStore) this.memstore).getNextRow(KeyValue.LOWESTKEY);
575    assertTrue(CellComparatorImpl.COMPARATOR.compareRows(closestToEmpty,
576        new KeyValue(Bytes.toBytes(0), System.currentTimeMillis())) == 0);
577    for (int i = 0; i < ROW_COUNT; i++) {
578      Cell nr = ((DefaultMemStore) this.memstore).getNextRow(new KeyValue(Bytes.toBytes(i),
579          System.currentTimeMillis()));
580      if (i + 1 == ROW_COUNT) {
581        assertNull(nr);
582      } else {
583        assertTrue(CellComparatorImpl.COMPARATOR.compareRows(nr,
584            new KeyValue(Bytes.toBytes(i + 1), System.currentTimeMillis())) == 0);
585      }
586    }
587    //starting from each row, validate results should contain the starting row
588    Configuration conf = HBaseConfiguration.create();
589    for (int startRowId = 0; startRowId < ROW_COUNT; startRowId++) {
590      ScanInfo scanInfo =
591          new ScanInfo(conf, FAMILY, 0, 1, Integer.MAX_VALUE, KeepDeletedCells.FALSE,
592              HConstants.DEFAULT_BLOCKSIZE, 0, this.memstore.getComparator(), false);
593      try (InternalScanner scanner =
594          new StoreScanner(new Scan().withStartRow(Bytes.toBytes(startRowId)), scanInfo, null,
595              memstore.getScanners(0))) {
596        List<Cell> results = new ArrayList<>();
597        for (int i = 0; scanner.next(results); i++) {
598          int rowId = startRowId + i;
599          Cell left = results.get(0);
600          byte[] row1 = Bytes.toBytes(rowId);
601          assertTrue("Row name",
602            CellComparatorImpl.COMPARATOR.compareRows(left, row1, 0, row1.length) == 0);
603          assertEquals("Count of columns", QUALIFIER_COUNT, results.size());
604          List<Cell> row = new ArrayList<>();
605          for (Cell kv : results) {
606            row.add(kv);
607          }
608          isExpectedRowWithoutTimestamps(rowId, row);
609          // Clear out set. Otherwise row results accumulate.
610          results.clear();
611        }
612      }
613    }
614  }
615
616  @Test
617  public void testGet_memstoreAndSnapShot() throws IOException {
618    byte [] row = Bytes.toBytes("testrow");
619    byte [] fam = Bytes.toBytes("testfamily");
620    byte [] qf1 = Bytes.toBytes("testqualifier1");
621    byte [] qf2 = Bytes.toBytes("testqualifier2");
622    byte [] qf3 = Bytes.toBytes("testqualifier3");
623    byte [] qf4 = Bytes.toBytes("testqualifier4");
624    byte [] qf5 = Bytes.toBytes("testqualifier5");
625    byte [] val = Bytes.toBytes("testval");
626
627    //Setting up memstore
628    memstore.add(new KeyValue(row, fam, qf1, val), null);
629    memstore.add(new KeyValue(row, fam, qf2, val), null);
630    memstore.add(new KeyValue(row, fam, qf3, val), null);
631    //Creating a snapshot
632    memstore.snapshot();
633    assertEquals(3, memstore.getSnapshot().getCellsCount());
634    //Adding value to "new" memstore
635    assertEquals(0, memstore.getActive().getCellsCount());
636    memstore.add(new KeyValue(row, fam ,qf4, val), null);
637    memstore.add(new KeyValue(row, fam ,qf5, val), null);
638    assertEquals(2, memstore.getActive().getCellsCount());
639  }
640
641  //////////////////////////////////////////////////////////////////////////////
642  // Delete tests
643  //////////////////////////////////////////////////////////////////////////////
644  @Test
645  public void testGetWithDelete() throws IOException {
646    byte [] row = Bytes.toBytes("testrow");
647    byte [] fam = Bytes.toBytes("testfamily");
648    byte [] qf1 = Bytes.toBytes("testqualifier");
649    byte [] val = Bytes.toBytes("testval");
650
651    long ts1 = System.nanoTime();
652    KeyValue put1 = new KeyValue(row, fam, qf1, ts1, val);
653    long ts2 = ts1 + 1;
654    KeyValue put2 = new KeyValue(row, fam, qf1, ts2, val);
655    long ts3 = ts2 + 1;
656    KeyValue put3 = new KeyValue(row, fam, qf1, ts3, val);
657    memstore.add(put1, null);
658    memstore.add(put2, null);
659    memstore.add(put3, null);
660
661    assertEquals(3, memstore.getActive().getCellsCount());
662
663    KeyValue del2 = new KeyValue(row, fam, qf1, ts2, KeyValue.Type.Delete, val);
664    memstore.add(del2, null);
665
666    List<Cell> expected = new ArrayList<>();
667    expected.add(put3);
668    expected.add(del2);
669    expected.add(put2);
670    expected.add(put1);
671
672    assertEquals(4, memstore.getActive().getCellsCount());
673    int i = 0;
674    for(Cell cell : memstore.getActive().getCellSet()) {
675      assertEquals(expected.get(i++), cell);
676    }
677  }
678
679  @Test
680  public void testGetWithDeleteColumn() throws IOException {
681    byte [] row = Bytes.toBytes("testrow");
682    byte [] fam = Bytes.toBytes("testfamily");
683    byte [] qf1 = Bytes.toBytes("testqualifier");
684    byte [] val = Bytes.toBytes("testval");
685
686    long ts1 = System.nanoTime();
687    KeyValue put1 = new KeyValue(row, fam, qf1, ts1, val);
688    long ts2 = ts1 + 1;
689    KeyValue put2 = new KeyValue(row, fam, qf1, ts2, val);
690    long ts3 = ts2 + 1;
691    KeyValue put3 = new KeyValue(row, fam, qf1, ts3, val);
692    memstore.add(put1, null);
693    memstore.add(put2, null);
694    memstore.add(put3, null);
695
696    assertEquals(3, memstore.getActive().getCellsCount());
697
698    KeyValue del2 =
699      new KeyValue(row, fam, qf1, ts2, KeyValue.Type.DeleteColumn, val);
700    memstore.add(del2, null);
701
702    List<Cell> expected = new ArrayList<>();
703    expected.add(put3);
704    expected.add(del2);
705    expected.add(put2);
706    expected.add(put1);
707
708    assertEquals(4, memstore.getActive().getCellsCount());
709    int i = 0;
710    for (Cell cell : memstore.getActive().getCellSet()) {
711      assertEquals(expected.get(i++), cell);
712    }
713  }
714
715  @Test
716  public void testGetWithDeleteFamily() throws IOException {
717    byte [] row = Bytes.toBytes("testrow");
718    byte [] fam = Bytes.toBytes("testfamily");
719    byte [] qf1 = Bytes.toBytes("testqualifier1");
720    byte [] qf2 = Bytes.toBytes("testqualifier2");
721    byte [] qf3 = Bytes.toBytes("testqualifier3");
722    byte [] val = Bytes.toBytes("testval");
723    long ts = System.nanoTime();
724
725    KeyValue put1 = new KeyValue(row, fam, qf1, ts, val);
726    KeyValue put2 = new KeyValue(row, fam, qf2, ts, val);
727    KeyValue put3 = new KeyValue(row, fam, qf3, ts, val);
728    KeyValue put4 = new KeyValue(row, fam, qf3, ts+1, val);
729
730    memstore.add(put1, null);
731    memstore.add(put2, null);
732    memstore.add(put3, null);
733    memstore.add(put4, null);
734
735    KeyValue del =
736      new KeyValue(row, fam, null, ts, KeyValue.Type.DeleteFamily, val);
737    memstore.add(del, null);
738
739    List<Cell> expected = new ArrayList<>();
740    expected.add(del);
741    expected.add(put1);
742    expected.add(put2);
743    expected.add(put4);
744    expected.add(put3);
745
746    assertEquals(5, memstore.getActive().getCellsCount());
747    int i = 0;
748    for (Cell cell : memstore.getActive().getCellSet()) {
749      assertEquals(expected.get(i++), cell);
750    }
751  }
752
753  @Test
754  public void testKeepDeleteInmemstore() {
755    byte [] row = Bytes.toBytes("testrow");
756    byte [] fam = Bytes.toBytes("testfamily");
757    byte [] qf = Bytes.toBytes("testqualifier");
758    byte [] val = Bytes.toBytes("testval");
759    long ts = System.nanoTime();
760    memstore.add(new KeyValue(row, fam, qf, ts, val), null);
761    KeyValue delete = new KeyValue(row, fam, qf, ts, KeyValue.Type.Delete, val);
762    memstore.add(delete, null);
763    assertEquals(2, memstore.getActive().getCellsCount());
764    assertEquals(delete, memstore.getActive().first());
765  }
766
767  @Test
768  public void testRetainsDeleteVersion() throws IOException {
769    // add a put to memstore
770    memstore.add(KeyValueTestUtil.create("row1", "fam", "a", 100, "dont-care"), null);
771
772    // now process a specific delete:
773    KeyValue delete = KeyValueTestUtil.create(
774        "row1", "fam", "a", 100, KeyValue.Type.Delete, "dont-care");
775    memstore.add(delete, null);
776
777    assertEquals(2, memstore.getActive().getCellsCount());
778    assertEquals(delete, memstore.getActive().first());
779  }
780
781  @Test
782  public void testRetainsDeleteColumn() throws IOException {
783    // add a put to memstore
784    memstore.add(KeyValueTestUtil.create("row1", "fam", "a", 100, "dont-care"), null);
785
786    // now process a specific delete:
787    KeyValue delete = KeyValueTestUtil.create("row1", "fam", "a", 100,
788        KeyValue.Type.DeleteColumn, "dont-care");
789    memstore.add(delete, null);
790
791    assertEquals(2, memstore.getActive().getCellsCount());
792    assertEquals(delete, memstore.getActive().first());
793  }
794
795  @Test
796  public void testRetainsDeleteFamily() throws IOException {
797    // add a put to memstore
798    memstore.add(KeyValueTestUtil.create("row1", "fam", "a", 100, "dont-care"), null);
799
800    // now process a specific delete:
801    KeyValue delete = KeyValueTestUtil.create("row1", "fam", "a", 100,
802        KeyValue.Type.DeleteFamily, "dont-care");
803    memstore.add(delete, null);
804
805    assertEquals(2, memstore.getActive().getCellsCount());
806    assertEquals(delete, memstore.getActive().first());
807  }
808
809  //////////////////////////////////////////////////////////////////////////////
810  // Helpers
811  //////////////////////////////////////////////////////////////////////////////
812  private static byte [] makeQualifier(final int i1, final int i2){
813    return Bytes.toBytes(Integer.toString(i1) + ";" +
814        Integer.toString(i2));
815  }
816
817  /**
818   * Add keyvalues with a fixed memstoreTs, and checks that memstore size is decreased
819   * as older keyvalues are deleted from the memstore.
820   * @throws Exception
821   */
822  @Test
823  public void testUpsertMemstoreSize() throws Exception {
824    Configuration conf = HBaseConfiguration.create();
825    memstore = new DefaultMemStore(conf, CellComparatorImpl.COMPARATOR);
826    MemStoreSize oldSize = memstore.size();
827
828    List<Cell> l = new ArrayList<>();
829    KeyValue kv1 = KeyValueTestUtil.create("r", "f", "q", 100, "v");
830    KeyValue kv2 = KeyValueTestUtil.create("r", "f", "q", 101, "v");
831    KeyValue kv3 = KeyValueTestUtil.create("r", "f", "q", 102, "v");
832
833    kv1.setSequenceId(1); kv2.setSequenceId(1);kv3.setSequenceId(1);
834    l.add(kv1); l.add(kv2); l.add(kv3);
835
836    this.memstore.upsert(l, 2, null);// readpoint is 2
837    MemStoreSize newSize = this.memstore.size();
838    assert (newSize.getDataSize() > oldSize.getDataSize());
839    //The kv1 should be removed.
840    assert(memstore.getActive().getCellsCount() == 2);
841
842    KeyValue kv4 = KeyValueTestUtil.create("r", "f", "q", 104, "v");
843    kv4.setSequenceId(1);
844    l.clear(); l.add(kv4);
845    this.memstore.upsert(l, 3, null);
846    assertEquals(newSize, this.memstore.size());
847    //The kv2 should be removed.
848    assert(memstore.getActive().getCellsCount() == 2);
849    //this.memstore = null;
850  }
851
852  ////////////////////////////////////
853  // Test for periodic memstore flushes
854  // based on time of oldest edit
855  ////////////////////////////////////
856
857  /**
858   * Tests that the timeOfOldestEdit is updated correctly for the
859   * various edit operations in memstore.
860   * @throws Exception
861   */
862  @Test
863  public void testUpdateToTimeOfOldestEdit() throws Exception {
864    try {
865      EnvironmentEdgeForMemstoreTest edge = new EnvironmentEdgeForMemstoreTest();
866      EnvironmentEdgeManager.injectEdge(edge);
867      DefaultMemStore memstore = new DefaultMemStore();
868      long t = memstore.timeOfOldestEdit();
869      assertEquals(Long.MAX_VALUE, t);
870
871      // test the case that the timeOfOldestEdit is updated after a KV add
872      memstore.add(KeyValueTestUtil.create("r", "f", "q", 100, "v"), null);
873      t = memstore.timeOfOldestEdit();
874      assertTrue(t == 1234);
875      // snapshot() will reset timeOfOldestEdit. The method will also assert the
876      // value is reset to Long.MAX_VALUE
877      t = runSnapshot(memstore);
878
879      // test the case that the timeOfOldestEdit is updated after a KV delete
880      memstore.add(KeyValueTestUtil.create("r", "f", "q", 100, KeyValue.Type.Delete, "v"), null);
881      t = memstore.timeOfOldestEdit();
882      assertTrue(t == 1234);
883      t = runSnapshot(memstore);
884
885      // test the case that the timeOfOldestEdit is updated after a KV upsert
886      List<Cell> l = new ArrayList<>();
887      KeyValue kv1 = KeyValueTestUtil.create("r", "f", "q", 100, "v");
888      kv1.setSequenceId(100);
889      l.add(kv1);
890      memstore.upsert(l, 1000, null);
891      t = memstore.timeOfOldestEdit();
892      assertTrue(t == 1234);
893    } finally {
894      EnvironmentEdgeManager.reset();
895    }
896  }
897
898  /**
899   * Tests the HRegion.shouldFlush method - adds an edit in the memstore
900   * and checks that shouldFlush returns true, and another where it disables
901   * the periodic flush functionality and tests whether shouldFlush returns
902   * false.
903   * @throws Exception
904   */
905  @Test
906  public void testShouldFlush() throws Exception {
907    Configuration conf = new Configuration();
908    conf.setInt(HRegion.MEMSTORE_PERIODIC_FLUSH_INTERVAL, 1000);
909    checkShouldFlush(conf, true);
910    // test disable flush
911    conf.setInt(HRegion.MEMSTORE_PERIODIC_FLUSH_INTERVAL, 0);
912    checkShouldFlush(conf, false);
913  }
914
915  protected void checkShouldFlush(Configuration conf, boolean expected) throws Exception {
916    try {
917      EnvironmentEdgeForMemstoreTest edge = new EnvironmentEdgeForMemstoreTest();
918      EnvironmentEdgeManager.injectEdge(edge);
919      HBaseTestingUtility hbaseUtility = HBaseTestingUtility.createLocalHTU(conf);
920      String cf = "foo";
921      HRegion region =
922          hbaseUtility.createTestRegion("foobar", ColumnFamilyDescriptorBuilder.of(cf));
923
924      edge.setCurrentTimeMillis(1234);
925      Put p = new Put(Bytes.toBytes("r"));
926      p.add(KeyValueTestUtil.create("r", cf, "q", 100, "v"));
927      region.put(p);
928      edge.setCurrentTimeMillis(1234 + 100);
929      StringBuilder sb = new StringBuilder();
930      assertTrue(!region.shouldFlush(sb));
931      edge.setCurrentTimeMillis(1234 + 10000);
932      assertTrue(region.shouldFlush(sb) == expected);
933    } finally {
934      EnvironmentEdgeManager.reset();
935    }
936  }
937
938  @Test
939  public void testShouldFlushMeta() throws Exception {
940    // write an edit in the META and ensure the shouldFlush (that the periodic memstore
941    // flusher invokes) returns true after SYSTEM_CACHE_FLUSH_INTERVAL (even though
942    // the MEMSTORE_PERIODIC_FLUSH_INTERVAL is set to a higher value)
943    Configuration conf = new Configuration();
944    conf.setInt(HRegion.MEMSTORE_PERIODIC_FLUSH_INTERVAL, HRegion.SYSTEM_CACHE_FLUSH_INTERVAL * 10);
945    HBaseTestingUtility hbaseUtility = HBaseTestingUtility.createLocalHTU(conf);
946    Path testDir = hbaseUtility.getDataTestDir();
947    EnvironmentEdgeForMemstoreTest edge = new EnvironmentEdgeForMemstoreTest();
948    EnvironmentEdgeManager.injectEdge(edge);
949    edge.setCurrentTimeMillis(1234);
950    WALFactory wFactory = new WALFactory(conf, "1234");
951    HRegion meta = HRegion.createHRegion(RegionInfoBuilder.FIRST_META_REGIONINFO, testDir,
952        conf, FSTableDescriptors.createMetaTableDescriptor(conf),
953        wFactory.getWAL(RegionInfoBuilder.FIRST_META_REGIONINFO));
954    // parameterized tests add [#] suffix get rid of [ and ].
955    TableDescriptor desc = TableDescriptorBuilder
956        .newBuilder(TableName.valueOf(name.getMethodName().replaceAll("[\\[\\]]", "_")))
957        .setColumnFamily(ColumnFamilyDescriptorBuilder.of("foo")).build();
958    RegionInfo hri = RegionInfoBuilder.newBuilder(desc.getTableName())
959        .setStartKey(Bytes.toBytes("row_0200")).setEndKey(Bytes.toBytes("row_0300")).build();
960    HRegion r = HRegion.createHRegion(hri, testDir, conf, desc, wFactory.getWAL(hri));
961    addRegionToMETA(meta, r);
962    edge.setCurrentTimeMillis(1234 + 100);
963    StringBuilder sb = new StringBuilder();
964    assertTrue(meta.shouldFlush(sb) == false);
965    edge.setCurrentTimeMillis(edge.currentTime() + HRegion.SYSTEM_CACHE_FLUSH_INTERVAL + 1);
966    assertTrue(meta.shouldFlush(sb) == true);
967  }
968
969  /**
970   * Inserts a new region's meta information into the passed
971   * <code>meta</code> region. Used by the HMaster bootstrap code adding
972   * new table to hbase:meta table.
973   *
974   * @param meta hbase:meta HRegion to be updated
975   * @param r HRegion to add to <code>meta</code>
976   *
977   * @throws IOException
978   */
979  public static void addRegionToMETA(final HRegion meta, final HRegion r) throws IOException {
980    meta.checkResources();
981    // The row key is the region name
982    byte[] row = r.getRegionInfo().getRegionName();
983    final long now = EnvironmentEdgeManager.currentTime();
984    final List<Cell> cells = new ArrayList<>(2);
985    cells.add(new KeyValue(row, HConstants.CATALOG_FAMILY,
986      HConstants.REGIONINFO_QUALIFIER, now, RegionInfo.toByteArray(r.getRegionInfo())));
987    // Set into the root table the version of the meta table.
988    cells.add(new KeyValue(row, HConstants.CATALOG_FAMILY,
989      HConstants.META_VERSION_QUALIFIER, now,
990      Bytes.toBytes(HConstants.META_VERSION)));
991    meta.put(row, HConstants.CATALOG_FAMILY, cells);
992  }
993
994  private class EnvironmentEdgeForMemstoreTest implements EnvironmentEdge {
995    long t = 1234;
996    @Override
997    public long currentTime() {
998      return t;
999    }
1000    public void setCurrentTimeMillis(long t) {
1001      this.t = t;
1002    }
1003  }
1004
1005  /**
1006   * Adds {@link #ROW_COUNT} rows and {@link #QUALIFIER_COUNT}
1007   * @param hmc Instance to add rows to.
1008   * @return How many rows we added.
1009   * @throws IOException
1010   */
1011  protected int addRows(final AbstractMemStore hmc) {
1012    return addRows(hmc, HConstants.LATEST_TIMESTAMP);
1013  }
1014
1015  /**
1016   * Adds {@link #ROW_COUNT} rows and {@link #QUALIFIER_COUNT}
1017   * @param hmc Instance to add rows to.
1018   * @return How many rows we added.
1019   * @throws IOException
1020   */
1021  protected int addRows(final MemStore hmc, final long ts) {
1022    for (int i = 0; i < ROW_COUNT; i++) {
1023      long timestamp = ts == HConstants.LATEST_TIMESTAMP ?
1024        System.currentTimeMillis() : ts;
1025      for (int ii = 0; ii < QUALIFIER_COUNT; ii++) {
1026        byte [] row = Bytes.toBytes(i);
1027        byte [] qf = makeQualifier(i, ii);
1028        hmc.add(new KeyValue(row, FAMILY, qf, timestamp, qf), null);
1029      }
1030    }
1031    return ROW_COUNT;
1032  }
1033
1034  private long runSnapshot(final AbstractMemStore hmc) throws UnexpectedStateException {
1035    // Save off old state.
1036    int oldHistorySize = hmc.getSnapshot().getCellsCount();
1037    MemStoreSnapshot snapshot = hmc.snapshot();
1038    // Make some assertions about what just happened.
1039    assertTrue("History size has not increased", oldHistorySize < hmc.getSnapshot().getCellsCount
1040        ());
1041    long t = memstore.timeOfOldestEdit();
1042    assertTrue("Time of oldest edit is not Long.MAX_VALUE", t == Long.MAX_VALUE);
1043    hmc.clearSnapshot(snapshot.getId());
1044    return t;
1045  }
1046
1047  private void isExpectedRowWithoutTimestamps(final int rowIndex,
1048      List<Cell> kvs) {
1049    int i = 0;
1050    for (Cell kv : kvs) {
1051      byte[] expectedColname = makeQualifier(rowIndex, i++);
1052      assertTrue("Column name", CellUtil.matchingQualifier(kv, expectedColname));
1053      // Value is column name as bytes.  Usually result is
1054      // 100 bytes in size at least. This is the default size
1055      // for BytesWriteable.  For comparison, convert bytes to
1056      // String and trim to remove trailing null bytes.
1057      assertTrue("Content", CellUtil.matchingValue(kv, expectedColname));
1058    }
1059  }
1060
1061  private static void addRows(int count, final MemStore mem) {
1062    long nanos = System.nanoTime();
1063
1064    for (int i = 0 ; i < count ; i++) {
1065      if (i % 1000 == 0) {
1066
1067        System.out.println(i + " Took for 1k usec: " + (System.nanoTime() - nanos)/1000);
1068        nanos = System.nanoTime();
1069      }
1070      long timestamp = System.currentTimeMillis();
1071
1072      for (int ii = 0; ii < QUALIFIER_COUNT ; ii++) {
1073        byte [] row = Bytes.toBytes(i);
1074        byte [] qf = makeQualifier(i, ii);
1075        mem.add(new KeyValue(row, FAMILY, qf, timestamp, qf), null);
1076      }
1077    }
1078  }
1079
1080  static void doScan(MemStore ms, int iteration) throws IOException {
1081    long nanos = System.nanoTime();
1082    KeyValueScanner s = ms.getScanners(0).get(0);
1083    s.seek(KeyValueUtil.createFirstOnRow(new byte[]{}));
1084
1085    System.out.println(iteration + " create/seek took: " + (System.nanoTime() - nanos)/1000);
1086    int cnt=0;
1087    while(s.next() != null) ++cnt;
1088
1089    System.out.println(iteration + " took usec: " + (System.nanoTime() - nanos) / 1000 + " for: "
1090        + cnt);
1091
1092  }
1093
1094  public static void main(String [] args) throws IOException {
1095    MemStore ms = new DefaultMemStore();
1096
1097    long n1 = System.nanoTime();
1098    addRows(25000, ms);
1099    System.out.println("Took for insert: " + (System.nanoTime()-n1)/1000);
1100
1101    System.out.println("foo");
1102
1103    for (int i = 0 ; i < 50 ; i++)
1104      doScan(ms, i);
1105  }
1106}
1107