You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-commits@hadoop.apache.org by ae...@apache.org on 2018/03/03 01:01:28 UTC
[40/50] [abbrv] hadoop git commit: HDFS-13211. Fix a bug in
DirectoryDiffList.getMinListForRange. Contributed by Shashikant Banerjee
HDFS-13211. Fix a bug in DirectoryDiffList.getMinListForRange. Contributed by Shashikant Banerjee
Project: http://git-wip-us.apache.org/repos/asf/hadoop/repo
Commit: http://git-wip-us.apache.org/repos/asf/hadoop/commit/96e8f260
Tree: http://git-wip-us.apache.org/repos/asf/hadoop/tree/96e8f260
Diff: http://git-wip-us.apache.org/repos/asf/hadoop/diff/96e8f260
Branch: refs/heads/HDFS-7240
Commit: 96e8f260ab90cc7b5a5aa2a59c182ef20a028238
Parents: 22928c0
Author: Tsz-Wo Nicholas Sze <sz...@hortonworks.com>
Authored: Thu Mar 1 14:12:15 2018 -0800
Committer: Tsz-Wo Nicholas Sze <sz...@hortonworks.com>
Committed: Thu Mar 1 14:12:15 2018 -0800
----------------------------------------------------------------------
.../namenode/snapshot/DirectoryDiffList.java | 37 +++-
.../apache/hadoop/hdfs/util/ReadOnlyList.java | 18 ++
.../snapshot/TestDirectoryDiffList.java | 182 +++++++++++--------
3 files changed, 156 insertions(+), 81 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/hadoop/blob/96e8f260/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryDiffList.java
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryDiffList.java b/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryDiffList.java
index 90b01e5..d2b20d3 100644
--- a/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryDiffList.java
+++ b/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryDiffList.java
@@ -97,7 +97,13 @@ public class DirectoryDiffList implements DiffList<DirectoryDiff> {
public void setDiff(ChildrenDiff diff) {
this.diff = diff;
}
+
+ @Override
+ public String toString() {
+ return "->" + skipTo;
+ }
}
+
/**
* SkipListNode is an implementation of a DirectoryDiff List node,
* which stores a Directory Diff and references to subsequent nodes.
@@ -191,6 +197,11 @@ public class DirectoryDiffList implements DiffList<DirectoryDiff> {
return skipDiffList.get(level).getSkipTo();
}
}
+
+ @Override
+ public String toString() {
+ return diff != null ? "" + diff.getSnapshotId() : "?";
+ }
}
/**
@@ -225,13 +236,6 @@ public class DirectoryDiffList implements DiffList<DirectoryDiff> {
this.skipInterval = interval;
}
- public static DirectoryDiffList createSkipList(int capacity, int interval,
- int skipLevel) {
- DirectoryDiffList list =
- new DirectoryDiffList(capacity, interval, skipLevel);
- return list;
- }
-
/**
* Adds the specified data element to the beginning of the SkipList,
* if the element is not already present.
@@ -444,15 +448,15 @@ public class DirectoryDiffList implements DiffList<DirectoryDiff> {
* order to generate all the changes occurred between fromIndex and
* toIndex.
*
- * @param fromIndex index from where the summation has to start
- * @param toIndex index till where the summation has to end
+ * @param fromIndex index from where the summation has to start(inclusive)
+ * @param toIndex index till where the summation has to end(exclusive)
* @return list of Directory Diff
*/
@Override
public List<DirectoryDiff> getMinListForRange(int fromIndex, int toIndex,
INodeDirectory dir) {
final List<DirectoryDiff> subList = new ArrayList<>();
- final int toSnapshotId = get(toIndex).getSnapshotId();
+ final int toSnapshotId = get(toIndex - 1).getSnapshotId();
for (SkipListNode current = getNode(fromIndex); current != null;) {
SkipListNode next = null;
ChildrenDiff childrenDiff = null;
@@ -467,8 +471,21 @@ public class DirectoryDiffList implements DiffList<DirectoryDiff> {
subList.add(childrenDiff == null ? curDiff :
new DirectoryDiff(curDiff.getSnapshotId(), dir, childrenDiff));
+ if (current.getDiff().compareTo(toSnapshotId) == 0) {
+ break;
+ }
current = next;
}
return subList;
}
+
+ @Override
+ public String toString() {
+ final StringBuilder b = new StringBuilder(getClass().getSimpleName());
+ b.append("\nhead: ").append(head).append(head.skipDiffList);
+ for (SkipListNode n : skipNodeList) {
+ b.append("\n ").append(n).append(n.skipDiffList);
+ }
+ return b.toString();
+ }
}
http://git-wip-us.apache.org/repos/asf/hadoop/blob/96e8f260/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java b/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
index 6da7dba..1d76f0e 100644
--- a/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
+++ b/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
@@ -106,6 +106,11 @@ public interface ReadOnlyList<E> extends Iterable<E> {
public E get(int i) {
return list.get(i);
}
+
+ @Override
+ public String toString() {
+ return list.toString();
+ }
};
}
@@ -234,6 +239,19 @@ public interface ReadOnlyList<E> extends Iterable<E> {
public <T> T[] toArray(T[] a) {
throw new UnsupportedOperationException();
}
+
+ @Override
+ public String toString() {
+ if (list.isEmpty()) {
+ return "[]";
+ }
+ final Iterator<E> i = list.iterator();
+ final StringBuilder b = new StringBuilder("[").append(i.next());
+ for(; i.hasNext();) {
+ b.append(", ").append(i.next());
+ }
+ return b + "]";
+ }
};
}
}
http://git-wip-us.apache.org/repos/asf/hadoop/blob/96e8f260/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestDirectoryDiffList.java
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestDirectoryDiffList.java b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestDirectoryDiffList.java
index fb6e7f4..99b6da2 100644
--- a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestDirectoryDiffList.java
+++ b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestDirectoryDiffList.java
@@ -19,14 +19,13 @@ package org.apache.hadoop.hdfs.server.namenode.snapshot;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
-import org.apache.hadoop.hdfs.DFSConfigKeys;
-import org.apache.hadoop.hdfs.DFSTestUtil;
import org.apache.hadoop.hdfs.DistributedFileSystem;
import org.apache.hadoop.hdfs.MiniDFSCluster;
import org.apache.hadoop.hdfs.server.namenode.FSDirectory;
import org.apache.hadoop.hdfs.server.namenode.FSNamesystem;
import org.apache.hadoop.hdfs.server.namenode.INode;
import org.apache.hadoop.hdfs.server.namenode.INodeDirectory;
+import org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.ChildrenDiff;
import org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.DirectoryDiff;
import org.apache.hadoop.hdfs.util.ReadOnlyList;
import org.junit.After;
@@ -34,8 +33,8 @@ import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
+import java.util.Collections;
import java.util.List;
-import java.util.Iterator;
/**
* This class tests the DirectoryDiffList API's.
@@ -45,11 +44,6 @@ public class TestDirectoryDiffList{
SnapshotTestHelper.disableLogs();
}
- private static final long SEED = 0;
- private static final short REPL = 3;
- private static final short REPL_2 = 1;
- private static final long BLOCKSIZE = 1024;
-
private static final Configuration CONF = new Configuration();
private static MiniDFSCluster cluster;
private static FSNamesystem fsn;
@@ -58,9 +52,8 @@ public class TestDirectoryDiffList{
@Before
public void setUp() throws Exception {
- CONF.setLong(DFSConfigKeys.DFS_BLOCK_SIZE_KEY, BLOCKSIZE);
- cluster = new MiniDFSCluster.Builder(CONF).numDataNodes(REPL).format(true)
- .build();
+ cluster =
+ new MiniDFSCluster.Builder(CONF).numDataNodes(0).format(true).build();
cluster.waitActive();
fsn = cluster.getNamesystem();
fsdir = fsn.getFSDirectory();
@@ -75,88 +68,135 @@ public class TestDirectoryDiffList{
}
}
- private void compareChildrenList(ReadOnlyList<INode> list1,
- ReadOnlyList<INode> list2) {
- Assert.assertEquals(list1.size(), list2.size());
- for (int index = 0; index < list1.size(); index++) {
- Assert.assertEquals(list1.get(index), list2.get(index));
+ static void assertList(List<INode> expected, List<INode> computed) {
+ Assert.assertEquals(expected.size(), computed.size());
+ for (int index = 0; index < expected.size(); index++) {
+ Assert.assertEquals(expected.get(index), computed.get(index));
+ }
+ }
+
+ static void verifyChildrenList(DirectoryDiffList skip, INodeDirectory dir) {
+ final int n = skip.size();
+ for (int i = 0; i < skip.size(); i++) {
+ final List<INode> expected =
+ ReadOnlyList.Util.asList(dir.getChildrenList(i));
+ final List<INode> computed = getChildrenList(skip, i, n, dir);
+ try {
+ assertList(expected, computed);
+ } catch (AssertionError ae) {
+ throw new AssertionError(
+ "i = " + i + "\ncomputed = " + computed + "\nexpected = "
+ + expected, ae);
+ }
}
}
- private void verifyChildrenListForAllSnapshots(DirectoryDiffList list,
- INodeDirectory dir) {
- for (int index = 0;
- index < list.size(); index++) {
- ReadOnlyList<INode> list1 = dir.getChildrenList(index);
- List<DirectoryWithSnapshotFeature.DirectoryDiff> subList =
- list.getMinListForRange(index, list.size() - 1, dir);
- ReadOnlyList<INode> list2 = getChildrenList(dir, subList);
- compareChildrenList(list1, list2);
+ static void verifyChildrenList(
+ DiffList<DirectoryDiff> array, DirectoryDiffList skip,
+ INodeDirectory dir, List<INode> childrenList) {
+ final int n = array.size();
+ Assert.assertEquals(n, skip.size());
+ for (int i = 0; i < n - 1; i++) {
+ for (int j = i + 1; j < n - 1; j++) {
+ final List<INode> expected = getCombined(array, i, j, dir)
+ .apply2Previous(childrenList);
+ final List<INode> computed = getCombined(skip, i, j, dir)
+ .apply2Previous(childrenList);
+ try {
+ assertList(expected, computed);
+ } catch (AssertionError ae) {
+ throw new AssertionError(
+ "i = " + i + ", j = " + j + "\ncomputed = " + computed
+ + "\nexpected = " + expected + "\n" + skip, ae);
+ }
+ }
}
}
- private ReadOnlyList<INode> getChildrenList(INodeDirectory currentINode,
- List<DirectoryWithSnapshotFeature.DirectoryDiff> list) {
- List<INode> children = null;
- final DirectoryWithSnapshotFeature.ChildrenDiff
- combined = new DirectoryWithSnapshotFeature.ChildrenDiff();
- for (DirectoryWithSnapshotFeature.DirectoryDiff d : list) {
+ private static ChildrenDiff getCombined(
+ DiffList<DirectoryDiff> list, int from, int to, INodeDirectory dir) {
+ final List<DirectoryDiff> minList = list.getMinListForRange(from, to, dir);
+ final ChildrenDiff combined = new ChildrenDiff();
+ for (DirectoryDiff d : minList) {
combined.combinePosterior(d.getChildrenDiff(), null);
}
- children = combined.apply2Current(ReadOnlyList.Util.asList(
- currentINode.getChildrenList(Snapshot.CURRENT_STATE_ID)));
- return ReadOnlyList.Util.asReadOnlyList(children);
+ return combined;
+ }
+
+ static List<INode> getChildrenList(
+ DiffList<DirectoryDiff> list, int from, int to, INodeDirectory dir) {
+ final ChildrenDiff combined = getCombined(list, from, to, dir);
+ return combined.apply2Current(ReadOnlyList.Util.asList(dir.getChildrenList(
+ Snapshot.CURRENT_STATE_ID)));
+ }
+
+ static Path getChildPath(Path parent, int i) {
+ return new Path(parent, "c" + i);
}
@Test
- public void testDirectoryDiffList() throws Exception {
- final Path sdir1 = new Path("/dir1");
- hdfs.mkdirs(sdir1);
- SnapshotTestHelper.createSnapshot(hdfs, sdir1, "s0");
- for (int i = 1; i < 31; i++) {
- final Path file = new Path(sdir1, "file" + i);
- DFSTestUtil.createFile(hdfs, file, BLOCKSIZE, REPL_2, SEED);
- SnapshotTestHelper.createSnapshot(hdfs, sdir1, "s" + i);
+ public void testAddLast() throws Exception {
+ testAddLast(7);
+ }
+
+ static void testAddLast(int n) throws Exception {
+ final Path root = new Path("/testAddLast" + n);
+ hdfs.mkdirs(root);
+ SnapshotTestHelper.createSnapshot(hdfs, root, "s0");
+ for (int i = 1; i < n; i++) {
+ final Path child = getChildPath(root, i);
+ hdfs.mkdirs(child);
+ SnapshotTestHelper.createSnapshot(hdfs, root, "s" + i);
}
- INodeDirectory sdir1Node = fsdir.getINode(sdir1.toString()).asDirectory();
- DiffList<DirectoryDiff> diffs =
- sdir1Node.getDiffs().asList();
-
- Iterator<DirectoryDiff> itr = diffs.iterator();
- DirectoryDiffList skipList = DirectoryDiffList.createSkipList(0, 3, 5);
- while (itr.hasNext()) {
- skipList.addLast(itr.next());
+ INodeDirectory dir = fsdir.getINode(root.toString()).asDirectory();
+ DiffList<DirectoryDiff> diffs = dir.getDiffs().asList();
+
+ final DirectoryDiffList skipList = new DirectoryDiffList(0, 3, 5);
+ final DiffList<DirectoryDiff> arrayList = new DiffListByArrayList<>(0);
+ for (DirectoryDiff d : diffs) {
+ skipList.addLast(d);
+ arrayList.addLast(d);
}
+
// verify that the both the children list obtained from hdfs and
// DirectoryDiffList are same
- verifyChildrenListForAllSnapshots(skipList, sdir1Node);
+ verifyChildrenList(skipList, dir);
+ verifyChildrenList(arrayList, skipList, dir, Collections.emptyList());
}
+
@Test
- public void testDirectoryDiffList2() throws Exception {
- final Path sdir1 = new Path("/dir1");
- hdfs.mkdirs(sdir1);
- for (int i = 1; i < 31; i++) {
- final Path file = new Path(sdir1, "file" + i);
- DFSTestUtil.createFile(hdfs, file, BLOCKSIZE, REPL_2, SEED);
+ public void testAddFirst() throws Exception {
+ testAddFirst(7);
+ }
+
+ static void testAddFirst(int n) throws Exception {
+ final Path root = new Path("/testAddFirst" + n);
+ hdfs.mkdirs(root);
+ for (int i = 1; i < n; i++) {
+ final Path child = getChildPath(root, i);
+ hdfs.mkdirs(child);
}
- SnapshotTestHelper.createSnapshot(hdfs, sdir1, "s0");
- for (int i = 1; i < 31; i++) {
- final Path file = new Path(sdir1, "file" + (31 - i));
- hdfs.delete(file, false);
- SnapshotTestHelper.createSnapshot(hdfs, sdir1, "s" + i);
+ INodeDirectory dir = fsdir.getINode(root.toString()).asDirectory();
+ SnapshotTestHelper.createSnapshot(hdfs, root, "s0");
+ for (int i = 1; i < n; i++) {
+ final Path child = getChildPath(root, n - i);
+ hdfs.delete(child, false);
+ SnapshotTestHelper.createSnapshot(hdfs, root, "s" + i);
}
- INodeDirectory sdir1Node = fsdir.getINode(sdir1.toString()).asDirectory();
- DiffList<DirectoryDiff> diffs = sdir1Node.getDiffs().asList();
-
- int index = diffs.size() - 1;
- DirectoryDiffList skipList = DirectoryDiffList.createSkipList(0, 3, 5);
- while (index >= 0) {
- skipList.addFirst(diffs.get(index));
- index--;
+ DiffList<DirectoryDiff> diffs = dir.getDiffs().asList();
+ List<INode> childrenList = ReadOnlyList.Util.asList(dir.getChildrenList(
+ diffs.get(0).getSnapshotId()));
+ final DirectoryDiffList skipList = new DirectoryDiffList(0, 3, 5);
+ final DiffList<DirectoryDiff> arrayList = new DiffListByArrayList<>(0);
+ for (int i = diffs.size() - 1; i >= 0; i--) {
+ final DirectoryDiff d = diffs.get(i);
+ skipList.addFirst(d);
+ arrayList.addFirst(d);
}
// verify that the both the children list obtained from hdfs and
// DirectoryDiffList are same
- verifyChildrenListForAllSnapshots(skipList, sdir1Node);
+ verifyChildrenList(skipList, dir);
+ verifyChildrenList(arrayList, skipList, dir, childrenList);
}
}
\ No newline at end of file
---------------------------------------------------------------------
To unsubscribe, e-mail: common-commits-unsubscribe@hadoop.apache.org
For additional commands, e-mail: common-commits-help@hadoop.apache.org