You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@accumulo.apache.org by kt...@apache.org on 2019/04/02 20:25:56 UTC
[accumulo] branch master updated: fixes #1033 optimize default
compaction strategy (#1036)
This is an automated email from the ASF dual-hosted git repository.
kturner pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/accumulo.git
The following commit(s) were added to refs/heads/master by this push:
new 07033aa fixes #1033 optimize default compaction strategy (#1036)
07033aa is described below
commit 07033aadfe7dba11fb31add155c97843dd0d0661
Author: Keith Turner <kt...@apache.org>
AuthorDate: Tue Apr 2 16:25:51 2019 -0400
fixes #1033 optimize default compaction strategy (#1036)
---
.../compaction/DefaultCompactionStrategy.java | 198 ++++++++++++++-----
.../compaction/DefaultCompactionStrategyTest.java | 211 ++++++++++++++++++++-
.../tserver/compaction/SizeWindowTest.java | 108 +++++++++++
3 files changed, 458 insertions(+), 59 deletions(-)
diff --git a/server/tserver/src/main/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategy.java b/server/tserver/src/main/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategy.java
index 52b0bef..875ece2 100644
--- a/server/tserver/src/main/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategy.java
+++ b/server/tserver/src/main/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategy.java
@@ -17,17 +17,119 @@
package org.apache.accumulo.tserver.compaction;
import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.List;
+import java.util.Map;
import java.util.Map.Entry;
-import java.util.TreeMap;
-import java.util.TreeSet;
import org.apache.accumulo.core.conf.Property;
import org.apache.accumulo.core.metadata.schema.DataFileValue;
import org.apache.accumulo.server.fs.FileRef;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
public class DefaultCompactionStrategy extends CompactionStrategy {
+ /**
+ * Keeps track of the sum of the size of all files within a window. The files are sorted from
+ * largest to smallest. Supports efficiently creating sub windows, sliding the window, and
+ * shrinking the window.
+ */
+ @VisibleForTesting
+ static class SizeWindow {
+
+ List<CompactionFile> files;
+ long sum = 0;
+
+ int first;
+ int last;
+
+ SizeWindow() {}
+
+ SizeWindow(Map<FileRef,DataFileValue> allFiles) {
+ files = new ArrayList<>();
+ for (Entry<FileRef,DataFileValue> entry : allFiles.entrySet()) {
+ files.add(new CompactionFile(entry.getKey(), entry.getValue().getSize()));
+ }
+
+ Collections.sort(files, Comparator.comparingLong(CompactionFile::getSize)
+ .thenComparing(CompactionFile::getFile).reversed());
+
+ for (CompactionFile file : files) {
+ sum += file.size;
+ }
+
+ first = 0;
+ last = files.size();
+ }
+
+ void pop() {
+ if (first >= last)
+ throw new IllegalStateException("Can not pop");
+
+ sum -= files.get(first).size;
+ first++;
+ }
+
+ long topSize() {
+ return files.get(first).size;
+ }
+
+ boolean slideUp() {
+ if (first == 0)
+ return false;
+
+ first--;
+ last--;
+
+ sum += files.get(first).size;
+ sum -= files.get(last).size;
+
+ return true;
+ }
+
+ SizeWindow tail(int windowSize) {
+ Preconditions.checkArgument(windowSize > 0);
+
+ SizeWindow sub = new SizeWindow();
+
+ sub.files = files;
+ sub.first = Math.max(last - windowSize, first);
+ sub.last = last;
+ sub.sum = 0;
+
+ for (int i = sub.first; i < sub.last; i++) {
+ sub.sum += files.get(i).size;
+ }
+
+ return sub;
+ }
+
+ long sum() {
+ return sum;
+ }
+
+ int size() {
+ return (last - first);
+ }
+
+ public List<FileRef> getFiles() {
+ List<FileRef> windowFiles = new ArrayList<>(size());
+ for (int i = first; i < last; i++) {
+ windowFiles.add(files.get(i).file);
+ }
+ return windowFiles;
+ }
+
+ @Override
+ public String toString() {
+ return "size:" + size() + " sum:" + sum() + " first:" + first + " last:" + last + " topSize:"
+ + topSize();
+ }
+ }
+
@Override
public boolean shouldCompact(MajorCompactionRequest request) {
CompactionPlan plan = getCompactionPlan(request);
@@ -54,6 +156,14 @@ public class DefaultCompactionStrategy extends CompactionStrategy {
this.file = file;
this.size = size;
}
+
+ long getSize() {
+ return size;
+ }
+
+ FileRef getFile() {
+ return file;
+ }
}
private List<FileRef> findMapFilesToCompact(MajorCompactionRequest request) {
@@ -61,6 +171,7 @@ public class DefaultCompactionStrategy extends CompactionStrategy {
if (reason == MajorCompactionReason.USER) {
return new ArrayList<>(request.getFiles().keySet());
}
+
if (reason == MajorCompactionReason.CHOP) {
// should not happen, but this is safe
return new ArrayList<>(request.getFiles().keySet());
@@ -68,75 +179,58 @@ public class DefaultCompactionStrategy extends CompactionStrategy {
if (request.getFiles().size() <= 1)
return null;
- TreeSet<CompactionFile> candidateFiles = new TreeSet<>((o1, o2) -> {
- if (o1 == o2)
- return 0;
- if (o1.size < o2.size)
- return -1;
- if (o1.size > o2.size)
- return 1;
- return o1.file.compareTo(o2.file);
- });
double ratio = Double.parseDouble(request.getTableConfig(Property.TABLE_MAJC_RATIO.getKey()));
int maxFilesToCompact = Integer
.parseInt(request.getTableConfig(Property.TSERV_MAJC_THREAD_MAXOPEN.getKey()));
int maxFilesPerTablet = request.getMaxFilesPerTablet();
- for (Entry<FileRef,DataFileValue> entry : request.getFiles().entrySet()) {
- candidateFiles.add(new CompactionFile(entry.getKey(), entry.getValue().getSize()));
- }
+ int minFilesToCompact = 0;
+ if (request.getFiles().size() > maxFilesPerTablet)
+ minFilesToCompact = request.getFiles().size() - maxFilesPerTablet + 1;
- long totalSize = 0;
- for (CompactionFile mfi : candidateFiles) {
- totalSize += mfi.size;
- }
+ minFilesToCompact = Math.min(minFilesToCompact, maxFilesToCompact);
- List<FileRef> files = new ArrayList<>();
+ SizeWindow all = new SizeWindow(request.getFiles());
- while (candidateFiles.size() > 1) {
- CompactionFile max = candidateFiles.last();
- if (max.size * ratio <= totalSize) {
- files.clear();
- for (CompactionFile mfi : candidateFiles) {
- files.add(mfi.file);
- if (files.size() >= maxFilesToCompact)
- break;
- }
+ List<FileRef> files = null;
+
+ // Within a window of size maxFilesToCompact containing the smallest files check to see if any
+ // files meet the compaction ratio criteria.
+ SizeWindow window = all.tail(maxFilesToCompact);
+ while (window.size() > 1 && files == null) {
- break;
+ if (window.topSize() * ratio <= window.sum()) {
+ files = window.getFiles();
}
- totalSize -= max.size;
- candidateFiles.remove(max);
- }
- int totalFilesToCompact = 0;
- if (request.getFiles().size() > maxFilesPerTablet)
- totalFilesToCompact = request.getFiles().size() - maxFilesPerTablet + 1;
+ window.pop();
+ }
- totalFilesToCompact = Math.min(totalFilesToCompact, maxFilesToCompact);
+ // Previous search was fruitless. If there are more files than maxFilesToCompact, then try
+ // sliding the window up looking for files that meet the criteria.
+ if (files == null || files.size() < minFilesToCompact) {
+ window = all.tail(maxFilesToCompact);
- if (files.size() < totalFilesToCompact) {
+ files = null;
- TreeMap<FileRef,Long> tfc = new TreeMap<>();
- for (Entry<FileRef,DataFileValue> entry : request.getFiles().entrySet()) {
- tfc.put(entry.getKey(), entry.getValue().getSize());
+ // When moving the window up there is no need to pop/shrink the window. All possible sets are
+ // covered without doing this. Proof is left as an exercise for the reader. This is predicated
+ // on the first search shrinking the initial window.
+ while (window.slideUp() && files == null) {
+ if (window.topSize() * ratio <= window.sum()) {
+ files = window.getFiles();
+ }
}
- tfc.keySet().removeAll(files);
-
- // put data in candidateFiles to sort it
- candidateFiles.clear();
- for (Entry<FileRef,Long> entry : tfc.entrySet())
- candidateFiles.add(new CompactionFile(entry.getKey(), entry.getValue()));
+ }
- for (CompactionFile mfi : candidateFiles) {
- files.add(mfi.file);
- if (files.size() >= totalFilesToCompact)
- break;
- }
+ // Ensure the minimum number of files are compacted.
+ if ((files != null && files.size() < minFilesToCompact)
+ || (files == null && minFilesToCompact > 0)) {
+ // get the smallest files of size minFilesToCompact
+ files = all.tail(minFilesToCompact).getFiles();
}
return files;
}
-
}
diff --git a/server/tserver/src/test/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategyTest.java b/server/tserver/src/test/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategyTest.java
index 78d3d4c..7c78100 100644
--- a/server/tserver/src/test/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategyTest.java
+++ b/server/tserver/src/test/java/org/apache/accumulo/tserver/compaction/DefaultCompactionStrategyTest.java
@@ -20,15 +20,23 @@ import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import java.io.DataInputStream;
+import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
+import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
+import java.util.List;
+import java.util.LongSummaryStatistics;
import java.util.Map;
+import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.atomic.AtomicBoolean;
+import org.apache.accumulo.core.conf.AccumuloConfiguration;
+import org.apache.accumulo.core.conf.ConfigurationCopy;
import org.apache.accumulo.core.conf.DefaultConfiguration;
+import org.apache.accumulo.core.conf.Property;
import org.apache.accumulo.core.crypto.CryptoServiceFactory;
import org.apache.accumulo.core.data.ByteSequence;
import org.apache.accumulo.core.data.Key;
@@ -155,6 +163,9 @@ public class DefaultCompactionStrategyTest {
static final DefaultConfiguration dfault = DefaultConfiguration.getInstance();
private static class TestCompactionRequest extends MajorCompactionRequest {
+
+ Integer mfpt = null;
+
@Override
public FileSKVIterator openReader(FileRef ref) {
return new TestFileSKVIterator(ref.toString());
@@ -166,20 +177,41 @@ public class DefaultCompactionStrategyTest {
setFiles(files);
}
- }
+ TestCompactionRequest(KeyExtent extent, MajorCompactionReason reason,
+ Map<FileRef,DataFileValue> files, AccumuloConfiguration config) {
+ super(extent, reason, config, getServerContext());
+ setFiles(files);
+ }
+
+ public void setMaxFilesPerTablet(int mfpt) {
+ this.mfpt = mfpt;
+ }
+
+ @Override
+ public int getMaxFilesPerTablet() {
+ if (mfpt != null)
+ return mfpt;
+ return super.getMaxFilesPerTablet();
+ }
- private MajorCompactionRequest createRequest(MajorCompactionReason reason, Object... objs) {
- return createRequest(new KeyExtent(TableId.of("0"), null, null), reason, objs);
}
- private MajorCompactionRequest createRequest(KeyExtent extent, MajorCompactionReason reason,
- Object... objs) {
+ static Map<FileRef,DataFileValue> createFileMap(Object... objs) {
Map<FileRef,DataFileValue> files = new HashMap<>();
for (int i = 0; i < objs.length; i += 2) {
files.put(new FileRef("hdfs://nn1/accumulo/tables/5/t-0001/" + objs[i]),
new DataFileValue(((Number) objs[i + 1]).longValue(), 0));
}
- return new TestCompactionRequest(extent, reason, files);
+ return files;
+ }
+
+ private TestCompactionRequest createRequest(MajorCompactionReason reason, Object... objs) {
+ return createRequest(new KeyExtent(TableId.of("0"), null, null), reason, objs);
+ }
+
+ private TestCompactionRequest createRequest(KeyExtent extent, MajorCompactionReason reason,
+ Object... objs) {
+ return new TestCompactionRequest(extent, reason, createFileMap(objs));
}
private static Set<String> asSet(String... strings) {
@@ -203,10 +235,15 @@ public class DefaultCompactionStrategyTest {
@Test
public void testGetCompactionPlan() throws Exception {
+
+ // test are expecting this default
+ assertEquals(10,
+ DefaultConfiguration.getInstance().getCount(Property.TSERV_MAJC_THREAD_MAXOPEN));
+
DefaultCompactionStrategy s = new DefaultCompactionStrategy();
// do nothing
- MajorCompactionRequest request = createRequest(MajorCompactionReason.IDLE, "file1", 10, "file2",
+ TestCompactionRequest request = createRequest(MajorCompactionReason.IDLE, "file1", 10, "file2",
10);
s.gatherInformation(request);
CompactionPlan plan = s.getCompactionPlan(request);
@@ -232,5 +269,165 @@ public class DefaultCompactionStrategyTest {
assertEquals(3, plan.inputFiles.size());
assertEquals(asStringSet(plan.inputFiles), asSet("file1,file2,file3".split(",")));
+ // Two windows (of size 10 or less) meet the compaction criteria. Should select the smallest set
+ // of files that meet the criteria.
+ request = createRequest(MajorCompactionReason.NORMAL, "file0", 100, "file1", 100, "file2", 100,
+ "file3", 10, "file4", 10, "file5", 10, "file6", 10, "file7", 10, "file8", 10, "file9", 10,
+ "fileA", 10);
+ s.gatherInformation(request);
+ plan = s.getCompactionPlan(request);
+ assertEquals(8, plan.inputFiles.size());
+ assertEquals(asStringSet(plan.inputFiles),
+ asSet("file3,file4,file5,file6,file7,file8,file9,fileA".split(",")));
+
+ // The last 10 files do not meet compaction ratio critea. Should move window of 10 files up
+ // looking for files that meet criteria.
+ request = createRequest(MajorCompactionReason.NORMAL, "file0", 19683, "file1", 19683, "file2",
+ 19683, "file3", 6561, "file4", 2187, "file5", 729, "file6", 243, "file7", 81, "file8", 27,
+ "file9", 9, "fileA", 3, "fileB", 1);
+ s.gatherInformation(request);
+ plan = s.getCompactionPlan(request);
+ assertEquals(10, plan.inputFiles.size());
+ assertEquals(asStringSet(plan.inputFiles),
+ asSet("file0,file1,file2,file3,file4,file5,file6,file7,file8,file9".split(",")));
+
+ // No window of files meets the compaction criteria, but there are more files than the max
+ // allowed. Should compact the smallest 2.
+ request = createRequest(MajorCompactionReason.NORMAL, "file1", 19683, "file2", 19683, "file3",
+ 6561, "file4", 2187, "file5", 729, "file6", 243, "file7", 81, "file8", 27, "file9", 9,
+ "fileA", 3, "fileB", 1);
+ request.setMaxFilesPerTablet(10);
+ s.gatherInformation(request);
+ plan = s.getCompactionPlan(request);
+ assertEquals(2, plan.inputFiles.size());
+ assertEquals(asStringSet(plan.inputFiles), asSet("fileA,fileB".split(",")));
+
+ // The last 9 files meet the compaction criteria, but 10 files need to be compacted. Should move
+ // window of 10 files up looking for files that meet criteria.
+ request = createRequest(MajorCompactionReason.NORMAL, "file01", 1500, "file02", 1400, "file03",
+ 1300, "file04", 1200, "file05", 1100, "file06", 1000, "file07", 900, "file08", 800,
+ "file09", 700, "file10", 600, "file11", 500, "file12", 400, "file13", 400, "file14", 300,
+ "file15", 200, "file16", 100, "file17", 9, "file18", 8, "file19", 7, "file20", 6, "file21",
+ 5, "file22", 4, "file23", 3, "file24", 2, "file25", 1);
+ request.setMaxFilesPerTablet(15);
+ s.gatherInformation(request);
+ plan = s.getCompactionPlan(request);
+ assertEquals(10, plan.inputFiles.size());
+ assertEquals(asStringSet(plan.inputFiles),
+ asSet("file12,file13,file14,file15,file16,file17,file18,file19,file20,file21".split(",")));
+
+ }
+
+ class SimulatedTablet {
+
+ private int maxFilesPerTablet;
+ private ConfigurationCopy config;
+
+ int nextFile = 0;
+ Map<FileRef,DataFileValue> files = new HashMap<>();
+
+ long totalRead = 0;
+ long added = 0;
+
+ SimulatedTablet(int maxFilesToCompact, int maxFilesPertablet) {
+ this.maxFilesPerTablet = maxFilesPertablet;
+
+ config = new ConfigurationCopy(DefaultConfiguration.getInstance());
+ config.set(Property.TSERV_MAJC_THREAD_MAXOPEN, maxFilesToCompact + "");
+ }
+
+ void addFiles(int num, int size, int entries) {
+ for (int i = 0; i < num; i++) {
+ String name = "hdfs://nn1/accumulo/tables/5/t-0001/I" + String.format("%06d", nextFile)
+ + ".rf";
+ nextFile++;
+
+ files.put(new FileRef(name), new DataFileValue(size, entries));
+ added += size;
+ }
+ }
+
+ long compact(MajorCompactionReason reason) {
+ TestCompactionRequest request = new TestCompactionRequest(
+ new KeyExtent(TableId.of("0"), (Text) null, null), reason, files, config);
+ request.setMaxFilesPerTablet(maxFilesPerTablet);
+
+ DefaultCompactionStrategy s = new DefaultCompactionStrategy();
+
+ if (s.shouldCompact(request)) {
+ CompactionPlan plan = s.getCompactionPlan(request);
+
+ long totalSize = 0;
+ long totalEntries = 0;
+
+ for (FileRef fr : plan.inputFiles) {
+ DataFileValue dfv = files.remove(fr);
+
+ totalSize += dfv.getSize();
+ totalEntries += dfv.getNumEntries();
+
+ totalRead += dfv.getSize();
+ }
+
+ String name = "hdfs://nn1/accumulo/tables/5/t-0001/C" + String.format("%06d", nextFile)
+ + ".rf";
+ nextFile++;
+
+ files.put(new FileRef(name), new DataFileValue(totalSize, totalEntries));
+
+ return totalSize;
+
+ } else {
+ return 0;
+ }
+ }
+
+ long getTotalRead() {
+ return totalRead;
+ }
+
+ public long getTotalAdded() {
+ return added;
+ }
+
+ void print() {
+ List<Entry<FileRef,DataFileValue>> entries = new ArrayList<>(files.entrySet());
+
+ Collections.sort(entries,
+ (e1, e2) -> Long.compare(e2.getValue().getSize(), e1.getValue().getSize()));
+
+ for (Entry<FileRef,DataFileValue> entry : entries) {
+
+ System.out.printf("%s %,d %,d\n", entry.getKey().path().getName(),
+ entry.getValue().getSize(), entry.getValue().getNumEntries());
+ }
+ }
+
+ public int getNumFiles() {
+ return files.size();
+ }
+ }
+
+ @Test
+ public void simulationTest() throws Exception {
+ for (int n = 1; n < 10; n++) {
+ LongSummaryStatistics lss = new LongSummaryStatistics();
+ SimulatedTablet simuTablet = new SimulatedTablet(10, 15);
+
+ for (int i = 0; i < 1000; i++) {
+ simuTablet.addFiles(n, 1000, 10);
+
+ simuTablet.compact(MajorCompactionReason.NORMAL);
+
+ lss.accept(simuTablet.getNumFiles());
+ }
+
+ while (simuTablet.compact(MajorCompactionReason.NORMAL) > 0) {
+ lss.accept(simuTablet.getNumFiles());
+ }
+
+ assertTrue(simuTablet.getTotalRead() < 6 * simuTablet.getTotalAdded());
+ assertTrue(lss.getAverage() < (n >= 8 ? 15 : 7));
+ }
}
}
diff --git a/server/tserver/src/test/java/org/apache/accumulo/tserver/compaction/SizeWindowTest.java b/server/tserver/src/test/java/org/apache/accumulo/tserver/compaction/SizeWindowTest.java
new file mode 100644
index 0000000..642b774
--- /dev/null
+++ b/server/tserver/src/test/java/org/apache/accumulo/tserver/compaction/SizeWindowTest.java
@@ -0,0 +1,108 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.accumulo.tserver.compaction;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.stream.Collectors;
+
+import org.apache.accumulo.core.metadata.schema.DataFileValue;
+import org.apache.accumulo.server.fs.FileRef;
+import org.apache.accumulo.tserver.compaction.DefaultCompactionStrategy.SizeWindow;
+import org.junit.Test;
+
+public class SizeWindowTest {
+
+ static class TestSizeWindow extends SizeWindow {
+ private static Map<FileRef,DataFileValue> convert(Map<String,Integer> testData) {
+ Map<FileRef,DataFileValue> files = new HashMap<>();
+ testData.forEach((k, v) -> {
+ files.put(new FileRef("hdfs://nn1/accumulo/tables/5/t-0001/" + k), new DataFileValue(v, 0));
+ });
+ return files;
+ }
+
+ /**
+ * A constructor that is more friendly for testing.
+ */
+ TestSizeWindow(Map<String,Integer> testData) {
+ super(convert(testData));
+ }
+ }
+
+ static Collection<String> getFileNames(SizeWindow sw) {
+ return sw.getFiles().stream().map(fr -> fr.path().getName()).collect(Collectors.toSet());
+ }
+
+ static Map<String,Integer> genTestData(int start, int end) {
+ Map<String,Integer> testData = new HashMap<>();
+
+ for (int i = start; i <= end; i++) {
+ testData.put("F" + i, i);
+ }
+
+ return testData;
+ }
+
+ @Test
+ public void testSlide() {
+
+ Map<String,Integer> testData = genTestData(1, 20);
+
+ TestSizeWindow tsw = new TestSizeWindow(testData);
+
+ SizeWindow tail = tsw.tail(10);
+
+ for (int i = 10; i <= 20; i++) {
+ int expectedSum = i * (i + 1) / 2 - ((i - 10) * (i - 9) / 2);
+ assertEquals(expectedSum, tail.sum());
+ assertEquals(10, tail.size());
+ assertEquals(genTestData(i - 9, i).keySet(), getFileNames(tail));
+ assertEquals(i, tail.topSize());
+ if (tail.slideUp())
+ assertTrue(i < 20);
+ else
+ assertEquals(20, i);
+ }
+ }
+
+ @Test
+ public void testPop() {
+ Map<String,Integer> testData = genTestData(1, 20);
+
+ TestSizeWindow tsw = new TestSizeWindow(testData);
+
+ SizeWindow tail = tsw.tail(10);
+
+ int expectedSize = 10;
+
+ while (expectedSize > 0) {
+ int expectedSum = expectedSize * (expectedSize + 1) / 2;
+ assertEquals(expectedSum, tail.sum());
+ assertEquals(expectedSize, tail.size());
+ assertEquals(genTestData(1, expectedSize).keySet(), getFileNames(tail));
+ assertEquals(expectedSize, tail.topSize());
+
+ tail.pop();
+ expectedSize--;
+ }
+ }
+}