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