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.apache.hadoop.hbase.regionserver.StripeStoreFileManager.OPEN_KEY;
021import static org.junit.Assert.assertArrayEquals;
022import static org.junit.Assert.assertEquals;
023import static org.junit.Assert.assertFalse;
024import static org.junit.Assert.assertTrue;
025import static org.junit.Assert.fail;
026import java.io.IOException;
027import java.util.ArrayList;
028import java.util.Arrays;
029import java.util.Collection;
030import java.util.Collections;
031import java.util.Iterator;
032import java.util.List;
033import org.apache.hadoop.conf.Configuration;
034import org.apache.hadoop.fs.FileSystem;
035import org.apache.hadoop.fs.Path;
036import org.apache.hadoop.hbase.CellComparatorImpl;
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.KeyValue;
042import org.apache.hadoop.hbase.testclassification.MediumTests;
043import org.apache.hadoop.hbase.testclassification.RegionServerTests;
044import org.apache.hadoop.hbase.util.Bytes;
045import org.junit.After;
046import org.junit.Before;
047import org.junit.ClassRule;
048import org.junit.Test;
049import org.junit.experimental.categories.Category;
050import org.mockito.Mockito;
051
052@Category({RegionServerTests.class, MediumTests.class})
053public class TestStripeStoreFileManager {
054
055  @ClassRule
056  public static final HBaseClassTestRule CLASS_RULE =
057      HBaseClassTestRule.forClass(TestStripeStoreFileManager.class);
058
059  private static final HBaseTestingUtility TEST_UTIL = new HBaseTestingUtility();
060  private static final Path BASEDIR =
061      TEST_UTIL.getDataTestDir(TestStripeStoreFileManager.class.getSimpleName());
062  private static final Path CFDIR = HStore.getStoreHomedir(BASEDIR, "region", Bytes.toBytes("cf"));
063
064  private static final byte[] KEY_A = Bytes.toBytes("aaa");
065  private static final byte[] KEY_B = Bytes.toBytes("aab");
066  private static final byte[] KEY_C = Bytes.toBytes("aac");
067  private static final byte[] KEY_D = Bytes.toBytes("aad");
068
069  private static final KeyValue KV_A = new KeyValue(KEY_A, 0L);
070  private static final KeyValue KV_B = new KeyValue(KEY_B, 0L);
071  private static final KeyValue KV_C = new KeyValue(KEY_C, 0L);
072  private static final KeyValue KV_D = new KeyValue(KEY_D, 0L);
073
074  @Before
075  public void setUp() throws Exception {
076    FileSystem fs = TEST_UTIL.getTestFileSystem();
077    if (!fs.mkdirs(CFDIR)) {
078      throw new IOException("Cannot create test directory " + CFDIR);
079    }
080  }
081
082  @After
083  public void tearDown() throws Exception {
084    FileSystem fs = TEST_UTIL.getTestFileSystem();
085    if (fs.exists(CFDIR) && !fs.delete(CFDIR, true)) {
086      throw new IOException("Cannot delete test directory " + CFDIR);
087    }
088  }
089
090  @Test
091  public void testInsertFilesIntoL0() throws Exception {
092    StripeStoreFileManager manager = createManager();
093    MockHStoreFile sf = createFile();
094    manager.insertNewFiles(al(sf));
095    assertEquals(1, manager.getStorefileCount());
096    Collection<HStoreFile> filesForGet = manager.getFilesForScan(KEY_A, true, KEY_A, true);
097    assertEquals(1, filesForGet.size());
098    assertTrue(filesForGet.contains(sf));
099
100    // Add some stripes and make sure we get this file for every stripe.
101    manager.addCompactionResults(al(), al(createFile(OPEN_KEY, KEY_B),
102        createFile(KEY_B, OPEN_KEY)));
103    assertTrue(manager.getFilesForScan(KEY_A, true, KEY_A, true).contains(sf));
104    assertTrue(manager.getFilesForScan(KEY_C, true, KEY_C, true).contains(sf));
105  }
106
107  @Test
108  public void testClearFiles() throws Exception {
109    StripeStoreFileManager manager = createManager();
110    manager.insertNewFiles(al(createFile()));
111    manager.insertNewFiles(al(createFile()));
112    manager.addCompactionResults(al(), al(createFile(OPEN_KEY, KEY_B),
113        createFile(KEY_B, OPEN_KEY)));
114    assertEquals(4, manager.getStorefileCount());
115    Collection<HStoreFile> allFiles = manager.clearFiles();
116    assertEquals(4, allFiles.size());
117    assertEquals(0, manager.getStorefileCount());
118    assertEquals(0, manager.getStorefiles().size());
119  }
120
121  private static ArrayList<HStoreFile> dumpIterator(Iterator<HStoreFile> iter) {
122    ArrayList<HStoreFile> result = new ArrayList<>();
123    for (; iter.hasNext(); result.add(iter.next())) {
124      continue;
125    }
126    return result;
127  }
128
129  @Test
130  public void testRowKeyBefore() throws Exception {
131    StripeStoreFileManager manager = createManager();
132    HStoreFile l0File = createFile(), l0File2 = createFile();
133    manager.insertNewFiles(al(l0File));
134    manager.insertNewFiles(al(l0File2));
135    // Get candidate files.
136    Iterator<HStoreFile> sfs = manager.getCandidateFilesForRowKeyBefore(KV_B);
137    sfs.next();
138    sfs.remove();
139    // Suppose we found a candidate in this file... make sure L0 file remaining is not removed.
140    sfs = manager.updateCandidateFilesForRowKeyBefore(sfs, KV_B, KV_A);
141    assertTrue(sfs.hasNext());
142    // Now add some stripes (remove L0 file too)
143    MockHStoreFile stripe0a = createFile(0, 100, OPEN_KEY, KEY_B),
144        stripe1 = createFile(KEY_B, OPEN_KEY);
145    manager.addCompactionResults(al(l0File), al(stripe0a, stripe1));
146    manager.removeCompactedFiles(al(l0File));
147    // If we want a key <= KEY_A, we should get everything except stripe1.
148    ArrayList<HStoreFile> sfsDump = dumpIterator(manager.getCandidateFilesForRowKeyBefore(KV_A));
149    assertEquals(2, sfsDump.size());
150    assertTrue(sfsDump.contains(stripe0a));
151    assertFalse(sfsDump.contains(stripe1));
152    // If we want a key <= KEY_B, we should get everything since lower bound is inclusive.
153    sfsDump = dumpIterator(manager.getCandidateFilesForRowKeyBefore(KV_B));
154    assertEquals(3, sfsDump.size());
155    assertTrue(sfsDump.contains(stripe1));
156    // For KEY_D, we should also get everything.
157    sfsDump = dumpIterator(manager.getCandidateFilesForRowKeyBefore(KV_D));
158    assertEquals(3, sfsDump.size());
159    // Suppose in the first file we found candidate with KEY_C.
160    // Then, stripe0 no longer matters and should be removed, but stripe1 should stay.
161    sfs = manager.getCandidateFilesForRowKeyBefore(KV_D);
162    sfs.next(); // Skip L0 file.
163    sfs.remove();
164    sfs = manager.updateCandidateFilesForRowKeyBefore(sfs, KV_D, KV_C);
165    assertEquals(stripe1, sfs.next());
166    assertFalse(sfs.hasNext());
167    // Add one more, later, file to stripe0, remove the last annoying L0 file.
168    // This file should be returned in preference to older L0 file; also, after we get
169    // a candidate from the first file, the old one should not be removed.
170    HStoreFile stripe0b = createFile(0, 101, OPEN_KEY, KEY_B);
171    manager.addCompactionResults(al(l0File2), al(stripe0b));
172    manager.removeCompactedFiles(al(l0File2));
173    sfs = manager.getCandidateFilesForRowKeyBefore(KV_A);
174    assertEquals(stripe0b, sfs.next());
175    sfs.remove();
176    sfs = manager.updateCandidateFilesForRowKeyBefore(sfs, KV_A, KV_A);
177    assertEquals(stripe0a, sfs.next());
178  }
179
180  @Test
181  public void testGetSplitPointEdgeCases() throws Exception {
182    StripeStoreFileManager manager = createManager();
183    // No files => no split.
184    assertFalse(manager.getSplitPoint().isPresent());
185
186    // If there are no stripes, should pick midpoint from the biggest file in L0.
187    MockHStoreFile sf5 = createFile(5, 0);
188    sf5.splitPoint = new byte[] { 1 };
189    manager.insertNewFiles(al(sf5));
190    manager.insertNewFiles(al(createFile(1, 0)));
191    assertArrayEquals(sf5.splitPoint, manager.getSplitPoint().get());
192
193    // Same if there's one stripe but the biggest file is still in L0.
194    manager.addCompactionResults(al(), al(createFile(2, 0, OPEN_KEY, OPEN_KEY)));
195    assertArrayEquals(sf5.splitPoint, manager.getSplitPoint().get());
196
197    // If the biggest file is in the stripe, should get from it.
198    MockHStoreFile sf6 = createFile(6, 0, OPEN_KEY, OPEN_KEY);
199    sf6.splitPoint = new byte[] { 2 };
200    manager.addCompactionResults(al(), al(sf6));
201    assertArrayEquals(sf6.splitPoint, manager.getSplitPoint().get());
202  }
203
204  @Test
205  public void testGetStripeBoundarySplits() throws Exception {
206    /* First number - split must be after this stripe; further numbers - stripes */
207    verifySplitPointScenario(5, false, 0f,     2, 1, 1, 1, 1, 1, 10);
208    verifySplitPointScenario(0, false, 0f,     6, 3, 1, 1, 2);
209    verifySplitPointScenario(2, false, 0f,     1, 1, 1, 1, 2);
210    verifySplitPointScenario(0, false, 0f,     5, 4);
211    verifySplitPointScenario(2, false, 0f,     5, 2, 5, 5, 5);
212  }
213
214  @Test
215  public void testGetUnbalancedSplits() throws Exception {
216    /* First number - split must be inside/after this stripe; further numbers - stripes */
217    verifySplitPointScenario(0, false, 2.1f,      4, 4, 4); // 8/4 is less than 2.1f
218    verifySplitPointScenario(1, true,  1.5f,      4, 4, 4); // 8/4 > 6/6
219    verifySplitPointScenario(1, false, 1.1f,      3, 4, 1, 1, 2, 2); // 7/6 < 8/5
220    verifySplitPointScenario(1, false, 1.1f,      3, 6, 1, 1, 2, 2); // 9/6 == 9/6
221    verifySplitPointScenario(1, true,  1.1f,      3, 8, 1, 1, 2, 2); // 11/6 > 10/7
222    verifySplitPointScenario(3, false, 1.1f,      2, 2, 1, 1, 4, 3); // reverse order
223    verifySplitPointScenario(4, true,  1.1f,      2, 2, 1, 1, 8, 3); // reverse order
224    verifySplitPointScenario(0, true,  1.5f,      10, 4); // 10/4 > 9/5
225    verifySplitPointScenario(0, false, 1.4f,      6, 4);  // 6/4 == 6/4
226    verifySplitPointScenario(1, true,  1.5f,      4, 10); // reverse just in case
227    verifySplitPointScenario(0, false, 1.4f,      4, 6);  // reverse just in case
228  }
229
230
231  /**
232   * Verifies scenario for finding a split point.
233   * @param splitPointAfter Stripe to expect the split point at/after.
234   * @param shouldSplitStripe If true, the split point is expected in the middle of the above
235   *                          stripe; if false, should be at the end.
236   * @param splitRatioToVerify Maximum split imbalance ratio.
237   * @param sizes Stripe sizes.
238   */
239  private void verifySplitPointScenario(int splitPointAfter, boolean shouldSplitStripe,
240      float splitRatioToVerify, int... sizes) throws Exception {
241    assertTrue(sizes.length > 1);
242    ArrayList<HStoreFile> sfs = new ArrayList<>();
243    for (int sizeIx = 0; sizeIx < sizes.length; ++sizeIx) {
244      byte[] startKey = (sizeIx == 0) ? OPEN_KEY : Bytes.toBytes(sizeIx - 1);
245      byte[] endKey = (sizeIx == sizes.length - 1) ? OPEN_KEY : Bytes.toBytes(sizeIx);
246      MockHStoreFile sf = createFile(sizes[sizeIx], 0, startKey, endKey);
247      sf.splitPoint = Bytes.toBytes(-sizeIx); // set split point to the negative index
248      sfs.add(sf);
249    }
250
251    Configuration conf = HBaseConfiguration.create();
252    if (splitRatioToVerify != 0) {
253      conf.setFloat(StripeStoreConfig.MAX_REGION_SPLIT_IMBALANCE_KEY, splitRatioToVerify);
254    }
255    StripeStoreFileManager manager = createManager(al(), conf);
256    manager.addCompactionResults(al(), sfs);
257    int result = Bytes.toInt(manager.getSplitPoint().get());
258    // Either end key and thus positive index, or "middle" of the file and thus negative index.
259    assertEquals(splitPointAfter * (shouldSplitStripe ? -1 : 1), result);
260  }
261
262  private static byte[] keyAfter(byte[] key) {
263    return Arrays.copyOf(key, key.length + 1);
264  }
265
266  @Test
267  public void testGetFilesForGetAndScan() throws Exception {
268    StripeStoreFileManager manager = createManager();
269    verifyGetAndScanScenario(manager, null, null);
270    verifyGetAndScanScenario(manager, KEY_B, KEY_C);
271
272    // Populate one L0 file.
273    MockHStoreFile sf0 = createFile();
274    manager.insertNewFiles(al(sf0));
275    verifyGetAndScanScenario(manager, null, null,   sf0);
276    verifyGetAndScanScenario(manager, null, KEY_C,  sf0);
277    verifyGetAndScanScenario(manager, KEY_B, null,  sf0);
278    verifyGetAndScanScenario(manager, KEY_B, KEY_C, sf0);
279
280    // Populate a bunch of files for stripes, keep L0.
281    MockHStoreFile sfA = createFile(OPEN_KEY, KEY_A);
282    MockHStoreFile sfB = createFile(KEY_A, KEY_B);
283    MockHStoreFile sfC = createFile(KEY_B, KEY_C);
284    MockHStoreFile sfD = createFile(KEY_C, KEY_D);
285    MockHStoreFile sfE = createFile(KEY_D, OPEN_KEY);
286    manager.addCompactionResults(al(), al(sfA, sfB, sfC, sfD, sfE));
287
288    verifyGetAndScanScenario(manager, null, null,              sf0, sfA, sfB, sfC, sfD, sfE);
289    verifyGetAndScanScenario(manager, keyAfter(KEY_A), null,   sf0, sfB, sfC, sfD, sfE);
290    verifyGetAndScanScenario(manager, null, keyAfter(KEY_C),   sf0, sfA, sfB, sfC, sfD);
291    verifyGetAndScanScenario(manager, KEY_B, null,             sf0, sfC, sfD, sfE);
292    verifyGetAndScanScenario(manager, null, KEY_C,             sf0, sfA, sfB, sfC, sfD);
293    verifyGetAndScanScenario(manager, KEY_B, keyAfter(KEY_B),  sf0, sfC);
294    verifyGetAndScanScenario(manager, keyAfter(KEY_A), KEY_B,  sf0, sfB, sfC);
295    verifyGetAndScanScenario(manager, KEY_D, KEY_D,            sf0, sfE);
296    verifyGetAndScanScenario(manager, keyAfter(KEY_B), keyAfter(KEY_C), sf0, sfC, sfD);
297  }
298
299  private void verifyGetAndScanScenario(StripeStoreFileManager manager, byte[] start, byte[] end,
300      HStoreFile... results) throws Exception {
301    verifyGetOrScanScenario(manager, start, end, results);
302  }
303
304  @Test
305  @SuppressWarnings("unchecked")
306  public void testLoadFilesWithRecoverableBadFiles() throws Exception {
307    // In L0, there will be file w/o metadata (real L0, 3 files with invalid metadata, and 3
308    // files that overlap valid stripes in various ways). Note that the 4th way to overlap the
309    // stripes will cause the structure to be mostly scraped, and is tested separately.
310    ArrayList<HStoreFile> validStripeFiles = al(createFile(OPEN_KEY, KEY_B),
311        createFile(KEY_B, KEY_C), createFile(KEY_C, OPEN_KEY),
312        createFile(KEY_C, OPEN_KEY));
313    ArrayList<HStoreFile> filesToGoToL0 = al(createFile(), createFile(null, KEY_A),
314        createFile(KEY_D, null), createFile(KEY_D, KEY_A), createFile(keyAfter(KEY_A), KEY_C),
315        createFile(OPEN_KEY, KEY_D), createFile(KEY_D, keyAfter(KEY_D)));
316    ArrayList<HStoreFile> allFilesToGo = flattenLists(validStripeFiles, filesToGoToL0);
317    Collections.shuffle(allFilesToGo);
318    StripeStoreFileManager manager = createManager(allFilesToGo);
319    List<HStoreFile> l0Files = manager.getLevel0Files();
320    assertEquals(filesToGoToL0.size(), l0Files.size());
321    for (HStoreFile sf : filesToGoToL0) {
322      assertTrue(l0Files.contains(sf));
323    }
324    verifyAllFiles(manager, allFilesToGo);
325  }
326
327  @Test
328  public void testLoadFilesWithBadStripe() throws Exception {
329    // Current "algorithm" will see the after-B key before C key, add it as valid stripe,
330    // and then fail all other stripes. So everything would end up in L0.
331    ArrayList<HStoreFile> allFilesToGo = al(createFile(OPEN_KEY, KEY_B),
332        createFile(KEY_B, KEY_C), createFile(KEY_C, OPEN_KEY),
333        createFile(KEY_B, keyAfter(KEY_B)));
334    Collections.shuffle(allFilesToGo);
335    StripeStoreFileManager manager = createManager(allFilesToGo);
336    assertEquals(allFilesToGo.size(), manager.getLevel0Files().size());
337  }
338
339  @Test
340  public void testLoadFilesWithGaps() throws Exception {
341    // Stripes must not have gaps. If they do, everything goes to L0.
342    StripeStoreFileManager manager =
343      createManager(al(createFile(OPEN_KEY, KEY_B), createFile(KEY_C, OPEN_KEY)));
344    assertEquals(2, manager.getLevel0Files().size());
345    // Just one open stripe should be ok.
346    manager = createManager(al(createFile(OPEN_KEY, OPEN_KEY)));
347    assertEquals(0, manager.getLevel0Files().size());
348    assertEquals(1, manager.getStorefileCount());
349  }
350
351  @Test
352  public void testLoadFilesAfterSplit() throws Exception {
353    // If stripes are good but have non-open ends, they must be treated as open ends.
354    MockHStoreFile sf = createFile(KEY_B, KEY_C);
355    StripeStoreFileManager manager = createManager(al(createFile(OPEN_KEY, KEY_B), sf));
356    assertEquals(0, manager.getLevel0Files().size());
357    // Here, [B, C] is logically [B, inf), so we should be able to compact it to that only.
358    verifyInvalidCompactionScenario(manager, al(sf), al(createFile(KEY_B, KEY_C)));
359    manager.addCompactionResults(al(sf), al(createFile(KEY_B, OPEN_KEY)));
360    manager.removeCompactedFiles(al(sf));
361    // Do the same for other variants.
362    manager = createManager(al(sf, createFile(KEY_C, OPEN_KEY)));
363    verifyInvalidCompactionScenario(manager, al(sf), al(createFile(KEY_B, KEY_C)));
364    manager.addCompactionResults(al(sf), al(createFile(OPEN_KEY, KEY_C)));
365    manager.removeCompactedFiles(al(sf));
366    manager = createManager(al(sf));
367    verifyInvalidCompactionScenario(manager, al(sf), al(createFile(KEY_B, KEY_C)));
368    manager.addCompactionResults(al(sf), al(createFile(OPEN_KEY, OPEN_KEY)));
369  }
370
371  @Test
372  public void testAddingCompactionResults() throws Exception {
373    StripeStoreFileManager manager = createManager();
374    // First, add some L0 files and "compact" one with new stripe creation.
375    HStoreFile sf_L0_0a = createFile(), sf_L0_0b = createFile();
376    manager.insertNewFiles(al(sf_L0_0a, sf_L0_0b));
377
378    // Try compacting with invalid new branches (gaps, overlaps) - no effect.
379    verifyInvalidCompactionScenario(manager, al(sf_L0_0a), al(createFile(OPEN_KEY, KEY_B)));
380    verifyInvalidCompactionScenario(manager, al(sf_L0_0a), al(createFile(OPEN_KEY, KEY_B),
381        createFile(KEY_C, OPEN_KEY)));
382    verifyInvalidCompactionScenario(manager, al(sf_L0_0a), al(createFile(OPEN_KEY, KEY_B),
383        createFile(KEY_B, OPEN_KEY), createFile(KEY_A, KEY_D)));
384    verifyInvalidCompactionScenario(manager, al(sf_L0_0a), al(createFile(OPEN_KEY, KEY_B),
385        createFile(KEY_A, KEY_B), createFile(KEY_B, OPEN_KEY)));
386
387    HStoreFile sf_i2B_0 = createFile(OPEN_KEY, KEY_B);
388    HStoreFile sf_B2C_0 = createFile(KEY_B, KEY_C);
389    HStoreFile sf_C2i_0 = createFile(KEY_C, OPEN_KEY);
390    manager.addCompactionResults(al(sf_L0_0a), al(sf_i2B_0, sf_B2C_0, sf_C2i_0));
391    manager.removeCompactedFiles(al(sf_L0_0a));
392    verifyAllFiles(manager, al(sf_L0_0b, sf_i2B_0, sf_B2C_0, sf_C2i_0));
393
394    // Add another l0 file, "compact" both L0 into two stripes
395    HStoreFile sf_L0_1 = createFile();
396    HStoreFile sf_i2B_1 = createFile(OPEN_KEY, KEY_B);
397    HStoreFile sf_B2C_1 = createFile(KEY_B, KEY_C);
398    manager.insertNewFiles(al(sf_L0_1));
399    manager.addCompactionResults(al(sf_L0_0b, sf_L0_1), al(sf_i2B_1, sf_B2C_1));
400    manager.removeCompactedFiles(al(sf_L0_0b, sf_L0_1));
401    verifyAllFiles(manager, al(sf_i2B_0, sf_B2C_0, sf_C2i_0, sf_i2B_1, sf_B2C_1));
402
403    // Try compacting with invalid file (no metadata) - should add files to L0.
404    HStoreFile sf_L0_2 = createFile(null, null);
405    manager.addCompactionResults(al(), al(sf_L0_2));
406    manager.removeCompactedFiles(al());
407    verifyAllFiles(manager, al(sf_i2B_0, sf_B2C_0, sf_C2i_0, sf_i2B_1, sf_B2C_1, sf_L0_2));
408    // Remove it...
409    manager.addCompactionResults(al(sf_L0_2), al());
410    manager.removeCompactedFiles(al(sf_L0_2));
411
412    // Do regular compaction in the first stripe.
413    HStoreFile sf_i2B_3 = createFile(OPEN_KEY, KEY_B);
414    manager.addCompactionResults(al(sf_i2B_0, sf_i2B_1), al(sf_i2B_3));
415    manager.removeCompactedFiles(al(sf_i2B_0, sf_i2B_1));
416    verifyAllFiles(manager, al(sf_B2C_0, sf_C2i_0, sf_B2C_1, sf_i2B_3));
417
418    // Rebalance two stripes.
419    HStoreFile sf_B2D_4 = createFile(KEY_B, KEY_D);
420    HStoreFile sf_D2i_4 = createFile(KEY_D, OPEN_KEY);
421    manager.addCompactionResults(al(sf_B2C_0, sf_C2i_0, sf_B2C_1), al(sf_B2D_4, sf_D2i_4));
422    manager.removeCompactedFiles(al(sf_B2C_0, sf_C2i_0, sf_B2C_1));
423    verifyAllFiles(manager, al(sf_i2B_3, sf_B2D_4, sf_D2i_4));
424
425    // Split the first stripe.
426    HStoreFile sf_i2A_5 = createFile(OPEN_KEY, KEY_A);
427    HStoreFile sf_A2B_5 = createFile(KEY_A, KEY_B);
428    manager.addCompactionResults(al(sf_i2B_3), al(sf_i2A_5, sf_A2B_5));
429    manager.removeCompactedFiles(al(sf_i2B_3));
430    verifyAllFiles(manager, al(sf_B2D_4, sf_D2i_4, sf_i2A_5, sf_A2B_5));
431
432    // Split the middle stripe.
433    HStoreFile sf_B2C_6 = createFile(KEY_B, KEY_C);
434    HStoreFile sf_C2D_6 = createFile(KEY_C, KEY_D);
435    manager.addCompactionResults(al(sf_B2D_4), al(sf_B2C_6, sf_C2D_6));
436    manager.removeCompactedFiles(al(sf_B2D_4));
437    verifyAllFiles(manager, al(sf_D2i_4, sf_i2A_5, sf_A2B_5, sf_B2C_6, sf_C2D_6));
438
439    // Merge two different middle stripes.
440    HStoreFile sf_A2C_7 = createFile(KEY_A, KEY_C);
441    manager.addCompactionResults(al(sf_A2B_5, sf_B2C_6), al(sf_A2C_7));
442    manager.removeCompactedFiles(al(sf_A2B_5, sf_B2C_6));
443    verifyAllFiles(manager, al(sf_D2i_4, sf_i2A_5, sf_C2D_6, sf_A2C_7));
444
445    // Merge lower half.
446    HStoreFile sf_i2C_8 = createFile(OPEN_KEY, KEY_C);
447    manager.addCompactionResults(al(sf_i2A_5, sf_A2C_7), al(sf_i2C_8));
448    manager.removeCompactedFiles(al(sf_i2A_5, sf_A2C_7));
449    verifyAllFiles(manager, al(sf_D2i_4, sf_C2D_6, sf_i2C_8));
450
451    // Merge all.
452    HStoreFile sf_i2i_9 = createFile(OPEN_KEY, OPEN_KEY);
453    manager.addCompactionResults(al(sf_D2i_4, sf_C2D_6, sf_i2C_8), al(sf_i2i_9));
454    manager.removeCompactedFiles(al(sf_D2i_4, sf_C2D_6, sf_i2C_8));
455    verifyAllFiles(manager, al(sf_i2i_9));
456  }
457
458  @Test
459  public void testCompactionAndFlushConflict() throws Exception {
460    // Add file flush into stripes
461    StripeStoreFileManager sfm = createManager();
462    assertEquals(0, sfm.getStripeCount());
463    HStoreFile sf_i2c = createFile(OPEN_KEY, KEY_C), sf_c2i = createFile(KEY_C, OPEN_KEY);
464    sfm.insertNewFiles(al(sf_i2c, sf_c2i));
465    assertEquals(2, sfm.getStripeCount());
466    // Now try to add conflicting flush - should throw.
467    HStoreFile sf_i2d = createFile(OPEN_KEY, KEY_D), sf_d2i = createFile(KEY_D, OPEN_KEY);
468    sfm.insertNewFiles(al(sf_i2d, sf_d2i));
469    assertEquals(2, sfm.getStripeCount());
470    assertEquals(2, sfm.getLevel0Files().size());
471    verifyGetAndScanScenario(sfm, KEY_C, KEY_C, sf_i2d, sf_d2i, sf_c2i);
472    // Remove these files.
473    sfm.addCompactionResults(al(sf_i2d, sf_d2i), al());
474    sfm.removeCompactedFiles(al(sf_i2d, sf_d2i));
475    assertEquals(0, sfm.getLevel0Files().size());
476    // Add another file to stripe; then "rebalance" stripes w/o it - the file, which was
477    // presumably flushed during compaction, should go to L0.
478    HStoreFile sf_i2c_2 = createFile(OPEN_KEY, KEY_C);
479    sfm.insertNewFiles(al(sf_i2c_2));
480    sfm.addCompactionResults(al(sf_i2c, sf_c2i), al(sf_i2d, sf_d2i));
481    sfm.removeCompactedFiles(al(sf_i2c, sf_c2i));
482    assertEquals(1, sfm.getLevel0Files().size());
483    verifyGetAndScanScenario(sfm, KEY_C, KEY_C, sf_i2d, sf_i2c_2);
484  }
485
486  @Test
487  public void testEmptyResultsForStripes() throws Exception {
488    // Test that we can compact L0 into a subset of stripes.
489    StripeStoreFileManager manager = createManager();
490    HStoreFile sf0a = createFile();
491    HStoreFile sf0b = createFile();
492    manager.insertNewFiles(al(sf0a));
493    manager.insertNewFiles(al(sf0b));
494    ArrayList<HStoreFile> compacted = al(createFile(OPEN_KEY, KEY_B),
495        createFile(KEY_B, KEY_C), createFile(KEY_C, OPEN_KEY));
496    manager.addCompactionResults(al(sf0a), compacted);
497    manager.removeCompactedFiles(al(sf0a));
498    // Next L0 compaction only produces file for the first and last stripe.
499    ArrayList<HStoreFile> compacted2 = al(createFile(OPEN_KEY, KEY_B), createFile(KEY_C, OPEN_KEY));
500    manager.addCompactionResults(al(sf0b), compacted2);
501    manager.removeCompactedFiles(al(sf0b));
502    compacted.addAll(compacted2);
503    verifyAllFiles(manager, compacted);
504  }
505
506  @Test
507  public void testPriority() throws Exception {
508    // Expected priority, file limit, stripe count, files per stripe, l0 files.
509    testPriorityScenario(5,    5, 0, 0, 0);
510    testPriorityScenario(2,    5, 0, 0, 3);
511    testPriorityScenario(4,   25, 5, 1, 0); // example case.
512    testPriorityScenario(3,   25, 5, 1, 1); // L0 files counts for all stripes.
513    testPriorityScenario(3,   25, 5, 2, 0); // file to each stripe - same as one L0 file.
514    testPriorityScenario(2,   25, 5, 4, 0); // 1 is priority user, so 2 is returned.
515    testPriorityScenario(2,   25, 5, 4, 4); // don't return higher than user unless over limit.
516    testPriorityScenario(2,   25, 5, 1, 10); // same.
517    testPriorityScenario(0,   25, 5, 4, 5); // at limit.
518    testPriorityScenario(-5,  25, 5, 6, 0); // over limit!
519    testPriorityScenario(-1,  25, 0, 0, 26); // over limit with just L0
520  }
521
522  private void testPriorityScenario(int expectedPriority,
523      int limit, int stripes, int filesInStripe, int l0Files) throws Exception {
524    final byte[][] keys = { KEY_A, KEY_B, KEY_C, KEY_D };
525    assertTrue(stripes <= keys.length + 1);
526    Configuration conf = TEST_UTIL.getConfiguration();
527    conf.setInt("hbase.hstore.blockingStoreFiles", limit);
528    StripeStoreFileManager sfm = createManager(al(), conf);
529    for (int i = 0; i < l0Files; ++i) {
530      sfm.insertNewFiles(al(createFile()));
531    }
532    for (int i = 0; i < filesInStripe; ++i) {
533      ArrayList<HStoreFile> stripe = new ArrayList<>();
534      for (int j = 0; j < stripes; ++j) {
535        stripe.add(createFile(
536            (j == 0) ? OPEN_KEY : keys[j - 1], (j == stripes - 1) ? OPEN_KEY : keys[j]));
537      }
538      sfm.addCompactionResults(al(), stripe);
539    }
540    assertEquals(expectedPriority, sfm.getStoreCompactionPriority());
541  }
542
543  private void verifyInvalidCompactionScenario(StripeStoreFileManager manager,
544      ArrayList<HStoreFile> filesToCompact, ArrayList<HStoreFile> filesToInsert) throws Exception {
545    Collection<HStoreFile> allFiles = manager.getStorefiles();
546    try {
547      manager.addCompactionResults(filesToCompact, filesToInsert);
548      fail("Should have thrown");
549    } catch (IOException ex) {
550      // Ignore it.
551    }
552    verifyAllFiles(manager, allFiles); // must have the same files.
553  }
554
555  private void verifyGetOrScanScenario(StripeStoreFileManager manager, byte[] start, byte[] end,
556      HStoreFile... results) throws Exception {
557    verifyGetOrScanScenario(manager, start, end, Arrays.asList(results));
558  }
559
560  private void verifyGetOrScanScenario(StripeStoreFileManager manager, byte[] start, byte[] end,
561      Collection<HStoreFile> results) throws Exception {
562    start = start != null ? start : HConstants.EMPTY_START_ROW;
563    end = end != null ? end : HConstants.EMPTY_END_ROW;
564    Collection<HStoreFile> sfs = manager.getFilesForScan(start, true, end, false);
565    assertEquals(results.size(), sfs.size());
566    for (HStoreFile result : results) {
567      assertTrue(sfs.contains(result));
568    }
569  }
570
571  private void verifyAllFiles(
572      StripeStoreFileManager manager, Collection<HStoreFile> results) throws Exception {
573    verifyGetOrScanScenario(manager, null, null, results);
574  }
575
576  // TODO: replace with Mockito?
577  private static MockHStoreFile createFile(
578      long size, long seqNum, byte[] startKey, byte[] endKey) throws Exception {
579    FileSystem fs = TEST_UTIL.getTestFileSystem();
580    Path testFilePath = StoreFileWriter.getUniqueFile(fs, CFDIR);
581    fs.create(testFilePath).close();
582    MockHStoreFile sf = new MockHStoreFile(TEST_UTIL, testFilePath, size, 0, false, seqNum);
583    if (startKey != null) {
584      sf.setMetadataValue(StripeStoreFileManager.STRIPE_START_KEY, startKey);
585    }
586    if (endKey != null) {
587      sf.setMetadataValue(StripeStoreFileManager.STRIPE_END_KEY, endKey);
588    }
589    return sf;
590  }
591
592  private static MockHStoreFile createFile(long size, long seqNum) throws Exception {
593    return createFile(size, seqNum, null, null);
594  }
595
596  private static MockHStoreFile createFile(byte[] startKey, byte[] endKey) throws Exception {
597    return createFile(0, 0, startKey, endKey);
598  }
599
600  private static MockHStoreFile createFile() throws Exception {
601    return createFile(null, null);
602  }
603
604  private static StripeStoreFileManager createManager() throws Exception {
605    return createManager(new ArrayList<>());
606  }
607
608  private static StripeStoreFileManager createManager(ArrayList<HStoreFile> sfs) throws Exception {
609    return createManager(sfs, TEST_UTIL.getConfiguration());
610  }
611
612  private static StripeStoreFileManager createManager(
613      ArrayList<HStoreFile> sfs, Configuration conf) throws Exception {
614    StripeStoreConfig config = new StripeStoreConfig(
615        conf, Mockito.mock(StoreConfigInformation.class));
616    StripeStoreFileManager result = new StripeStoreFileManager(CellComparatorImpl.COMPARATOR, conf,
617        config);
618    result.loadFiles(sfs);
619    return result;
620  }
621
622  private static ArrayList<HStoreFile> al(HStoreFile... sfs) {
623    return new ArrayList<>(Arrays.asList(sfs));
624  }
625
626  private static ArrayList<HStoreFile> flattenLists(ArrayList<HStoreFile>... sfls) {
627    ArrayList<HStoreFile> result = new ArrayList<>();
628    for (ArrayList<HStoreFile> sfl : sfls) {
629      result.addAll(sfl);
630    }
631    return result;
632  }
633}