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