You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ozone.apache.org by ra...@apache.org on 2022/06/06 09:29:42 UTC
[ozone] branch master updated: HDDS-4364: [FSO]List FileStatus : startKey can be a non-existed path (#3481)
This is an automated email from the ASF dual-hosted git repository.
rakeshr pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ozone.git
The following commit(s) were added to refs/heads/master by this push:
new 50e8e49a74 HDDS-4364: [FSO]List FileStatus : startKey can be a non-existed path (#3481)
50e8e49a74 is described below
commit 50e8e49a744376d3b289fe740ffa2309aaa303d6
Author: Rakesh Radhakrishnan <ra...@apache.org>
AuthorDate: Mon Jun 6 14:59:36 2022 +0530
HDDS-4364: [FSO]List FileStatus : startKey can be a non-existed path (#3481)
---
.../apache/hadoop/ozone/client/OzoneBucket.java | 118 ++++++++-----
.../hadoop/ozone/om/helpers/OzoneFSUtils.java | 4 +
.../hadoop/ozone/om/TestListKeysWithFSO.java | 189 +++++++++++++++++++--
3 files changed, 253 insertions(+), 58 deletions(-)
diff --git a/hadoop-ozone/client/src/main/java/org/apache/hadoop/ozone/client/OzoneBucket.java b/hadoop-ozone/client/src/main/java/org/apache/hadoop/ozone/client/OzoneBucket.java
index 90f92fd770..a7c3f76de1 100644
--- a/hadoop-ozone/client/src/main/java/org/apache/hadoop/ozone/client/OzoneBucket.java
+++ b/hadoop-ozone/client/src/main/java/org/apache/hadoop/ozone/client/OzoneBucket.java
@@ -61,6 +61,7 @@ import java.util.NoSuchElementException;
import static org.apache.hadoop.ozone.OzoneConsts.QUOTA_RESET;
import static org.apache.hadoop.ozone.OzoneConsts.OZONE_URI_DELIMITER;
+import static org.apache.hadoop.ozone.om.exceptions.OMException.ResultCodes.FILE_NOT_FOUND;
/**
* A class that encapsulates OzoneBucket.
@@ -1107,7 +1108,8 @@ public class OzoneBucket extends WithMetadata {
String parentStartKeyPath = OzoneFSUtils.getParentDir(startKey);
- if (StringUtils.compare(parentStartKeyPath, keyPrefix) >= 0) {
+ if (StringUtils.isNotBlank(startKey) &&
+ StringUtils.compare(parentStartKeyPath, keyPrefix) >= 0) {
seekPaths.add(new ImmutablePair<>(parentStartKeyPath, startKey));
// recursively fetch all the sub-paths between keyPrefix and prevKey
@@ -1132,46 +1134,65 @@ public class OzoneBucket extends WithMetadata {
}
setKeyPrefix(keyPrefixName);
- if (StringUtils.isNotBlank(prevKey) &&
- StringUtils.startsWith(prevKey, getKeyPrefix())) {
- // 1. Prepare all the seekKeys after the prefixKey.
- // Example case: prefixKey="a1", startKey="a1/b2/d2/f3/f31.tx"
- // Now, stack should be build with all the levels after prefixKey
- // Stack format => <keyPrefix and startKey>, startKey should be an
- // immediate child of keyPrefix.
- // _______________________________________
- // Stack=> top | < a1/b2/d2/f3, a1/b2/d2/f3/f31.tx > |
- // |-------------------------------------|
- // | < a1/b2/d2, a1/b2/d2/f3 > |
- // |-------------------------------------|
- // | < a1/b2, a1/b2/d2 > |
- // |-------------------------------------|
- // bottom | < a1, a1/b2 > |
- // --------------------------------------|
- List<Pair<String, String>> seekPaths = new ArrayList<>();
-
- if (StringUtils.isNotBlank(getKeyPrefix())) {
- String parentStartKeyPath = OzoneFSUtils.getParentDir(prevKey);
- if (StringUtils.compare(parentStartKeyPath, getKeyPrefix()) >= 0) {
- // Add the leaf node to the seek path. The idea is to search for
- // sub-paths if the given start key is a directory.
+ if (StringUtils.isNotBlank(prevKey)) {
+ if (StringUtils.startsWith(prevKey, getKeyPrefix())) {
+ // 1. Prepare all the seekKeys after the prefixKey.
+ // Example case: prefixKey="a1", startKey="a1/b2/d2/f3/f31.tx"
+ // Now, stack should be build with all the levels after prefixKey
+ // Stack format => <keyPrefix and startKey>, startKey should be an
+ // immediate child of keyPrefix.
+ // _______________________________________
+ // Stack=> top | < a1/b2/d2/f3, a1/b2/d2/f3/f31.tx > |
+ // |-------------------------------------|
+ // | < a1/b2/d2, a1/b2/d2/f3 > |
+ // |-------------------------------------|
+ // | < a1/b2, a1/b2/d2 > |
+ // |-------------------------------------|
+ // bottom | < a1, a1/b2 > |
+ // --------------------------------------|
+ List<Pair<String, String>> seekPaths = new ArrayList<>();
+
+ if (StringUtils.isNotBlank(getKeyPrefix())) {
+ String parentStartKeyPath = OzoneFSUtils.getParentDir(prevKey);
+ if (StringUtils.compare(parentStartKeyPath, getKeyPrefix()) >=
+ 0) {
+ // Add the leaf node to the seek path. The idea is to search for
+ // sub-paths if the given start key is a directory.
+ seekPaths.add(new ImmutablePair<>(prevKey, ""));
+ removeStartKey = prevKey;
+ getSeekPathsBetweenKeyPrefixAndStartKey(getKeyPrefix(), prevKey,
+ seekPaths);
+ } else if (StringUtils.compare(prevKey, getKeyPrefix()) >= 0) {
+ // Add the leaf node to the seek path. The idea is to search for
+ // sub-paths if the given start key is a directory.
+ seekPaths.add(new ImmutablePair<>(prevKey, ""));
+ removeStartKey = prevKey;
+ }
+ } else {
+ // Key Prefix is Blank. The seek all the keys with startKey.
seekPaths.add(new ImmutablePair<>(prevKey, ""));
removeStartKey = prevKey;
getSeekPathsBetweenKeyPrefixAndStartKey(getKeyPrefix(), prevKey,
seekPaths);
- } else if (StringUtils.compare(prevKey, getKeyPrefix()) >= 0) {
- // Add the leaf node to the seek path. The idea is to search for
- // sub-paths if the given start key is a directory.
- seekPaths.add(new ImmutablePair<>(prevKey, ""));
- removeStartKey = prevKey;
}
- }
- // 2. Push elements in reverse order so that the FS tree traversal
- // will occur in left-to-right fashion[Depth-First Search]
- for (int index = seekPaths.size() - 1; index >= 0; index--) {
- Pair<String, String> seekDirPath = seekPaths.get(index);
- stack.push(seekDirPath);
+ // 2. Push elements in reverse order so that the FS tree traversal
+ // will occur in left-to-right fashion[Depth-First Search]
+ for (int index = seekPaths.size() - 1; index >= 0; index--) {
+ Pair<String, String> seekDirPath = seekPaths.get(index);
+ stack.push(seekDirPath);
+ }
+ } else if (StringUtils.isNotBlank(getKeyPrefix())) {
+ if (!OzoneFSUtils.isSibling(prevKey, getKeyPrefix())) {
+ // Case-1 - sibling: keyPrefix="a1/b2", startKey="a0/b123Invalid"
+ // Skip traversing, if the startKey is not a sibling.
+ return new ArrayList<>();
+ } else if (StringUtils.compare(prevKey, getKeyPrefix()) < 0) {
+ // Case-2 - compare: keyPrefix="a1/b2", startKey="a1/b123Invalid"
+ // Since startKey is lexographically behind keyPrefix,
+ // the seek precedence goes to keyPrefix.
+ stack.push(new ImmutablePair<>(getKeyPrefix(), ""));
+ }
}
}
}
@@ -1374,28 +1395,33 @@ public class OzoneBucket extends WithMetadata {
return;
}
- // TODO: HDDS-4859 will fix the case where startKey not started with
- // keyPrefix.
-
- OzoneFileStatus status = proxy.getOzoneFileStatus(volumeName, name,
- keyPrefix);
+ OzoneFileStatus status = null;
+ try {
+ status = proxy.getOzoneFileStatus(volumeName, name,
+ keyPrefix);
+ } catch (OMException ome) {
+ if (ome.getResult() == FILE_NOT_FOUND) {
+ // keyPrefix path can't be found and skip adding it to result list
+ return;
+ }
+ }
if (status != null) {
OmKeyInfo keyInfo = status.getKeyInfo();
String keyName = keyInfo.getKeyName();
- // removeStartKey - as the startKey is a placeholder, which is
- // managed internally to traverse leaf node's sub-paths.
- if (StringUtils.equals(keyName, removeStartKey)) {
- return;
- }
-
if (status.isDirectory()) {
// add trailing slash to represent directory
keyName =
OzoneFSUtils.addTrailingSlashIfNeeded(keyInfo.getKeyName());
}
+ // removeStartKey - as the startKey is a placeholder, which is
+ // managed internally to traverse leaf node's sub-paths.
+ if (StringUtils.equals(keyName, removeStartKey)) {
+ return;
+ }
+
OzoneKey ozoneKey = new OzoneKey(keyInfo.getVolumeName(),
keyInfo.getBucketName(), keyName,
keyInfo.getDataSize(), keyInfo.getCreationTime(),
diff --git a/hadoop-ozone/common/src/main/java/org/apache/hadoop/ozone/om/helpers/OzoneFSUtils.java b/hadoop-ozone/common/src/main/java/org/apache/hadoop/ozone/om/helpers/OzoneFSUtils.java
index 728bd57b4f..2750b63357 100644
--- a/hadoop-ozone/common/src/main/java/org/apache/hadoop/ozone/om/helpers/OzoneFSUtils.java
+++ b/hadoop-ozone/common/src/main/java/org/apache/hadoop/ozone/om/helpers/OzoneFSUtils.java
@@ -169,6 +169,10 @@ public final class OzoneFSUtils {
java.nio.file.Path childParent = childPath.getParent();
java.nio.file.Path parentParent = parentPath.getParent();
+ if (childParent != null && parentParent != null) {
+ return childParent.equals(parentParent);
+ }
+
return childParent == parentParent;
}
diff --git a/hadoop-ozone/integration-test/src/test/java/org/apache/hadoop/ozone/om/TestListKeysWithFSO.java b/hadoop-ozone/integration-test/src/test/java/org/apache/hadoop/ozone/om/TestListKeysWithFSO.java
index 13db29ffab..b8a3a54e69 100644
--- a/hadoop-ozone/integration-test/src/test/java/org/apache/hadoop/ozone/om/TestListKeysWithFSO.java
+++ b/hadoop-ozone/integration-test/src/test/java/org/apache/hadoop/ozone/om/TestListKeysWithFSO.java
@@ -142,7 +142,7 @@ public class TestListKeysWithFSO {
List<String> expectedKeys = getExpectedKeyList("a1/b2", "a1");
checkKeyList("a1/b2", "a1", expectedKeys);
- // case-2: Same prefixKey and startKey. but startKey with ending slash
+ // case-2: Same prefixKey and startKey, but with an ending slash
expectedKeys = getExpectedKeyList("a1/b2", "a1/b2/");
/**
* a1/b2/d1/
@@ -155,7 +155,29 @@ public class TestListKeysWithFSO {
*/
checkKeyList("a1/b2", "a1/b2/", expectedKeys);
- // case-3:
+ // case-3: Same prefixKey and startKey, but without an ending slash.
+ // StartKey(dir) to be included in the finalList, if its a
+ // directory and not ended with trailing slash.
+ expectedKeys = getExpectedKeyList("a1/b2", "a1/b2");
+ /**
+ * a1/b2/
+ * a1/b2/d1/
+ * a1/b2/d1/d11.tx
+ * a1/b2/d2/
+ * a1/b2/d2/d21.tx
+ * a1/b2/d2/d22.tx
+ * a1/b2/d3/
+ * a1/b2/d3/d31.tx
+ */
+ checkKeyList("a1/b2", "a1/b2", expectedKeys);
+
+ // case-4: StartKey is a file with an ending slash.
+ // StartKey(file) with or without an ending slash
+ // to be excluded in the finalList.
+ expectedKeys = getExpectedKeyList("a1/b2/d2", "a1/b2/d2/d22.tx/");
+ checkKeyList("a1/b2/d2", "a1/b2/d2/d22.tx/", expectedKeys);
+
+ // case-5:
// StartKey "a1/b2/d2/d22.tx" is a file and get all the keys lexographically
// greater than "a1/b2/d2/d22.tx".
expectedKeys = getExpectedKeyList("a1/b2", "a1/b2/d2/d22.tx");
@@ -165,7 +187,7 @@ public class TestListKeysWithFSO {
*/
checkKeyList("a1/b2", "a1/b2/d2/d22.tx", expectedKeys);
- // case-4:
+ // case-6:
// StartKey "a1/b2/d2" is a dir and get all the keys lexographically
// greater than "a1/b2/d2".
expectedKeys = getExpectedKeyList("a1/b2", "a1/b2/d2/");
@@ -177,7 +199,7 @@ public class TestListKeysWithFSO {
*/
checkKeyList("a1/b2", "a1/b2/d2/", expectedKeys);
- // case-5: In below case, the startKey is a directory which is included
+ // case-7: In below case, the startKey is a directory which is included
// in the finalList. So, should we include startKey file in the finalList ?
expectedKeys = getExpectedKeyList("a1", "a1/b2/d2/d21.tx");
/**
@@ -194,8 +216,8 @@ public class TestListKeysWithFSO {
*/
checkKeyList("a1", "a1/b2/d2/d21.tx", expectedKeys);
- // case-76 Here need to discuss - whether the startKey(dir) to be included
- // in the finalList ?
+ // case-8: StartKey(dir) to be included in the finalList, if its a
+ // directory and not ended with trailing slash.
expectedKeys = getExpectedKeyList("a1", "a1/b2/d2/");
/**
1 = "a1/b2/d2/d21.tx"
@@ -203,21 +225,165 @@ public class TestListKeysWithFSO {
3 = "a1/b2/d3/"
4 = "a1/b2/d3/d31.tx"
5 = "a1/b3/"
- 6 = "a1/b3/e1/"
- 7 = "a1/b3/e1/e11.tx"
- 8 = "a1/b3/e2/"
- 9 = "a1/b3/e2/e21.tx"
+ .....
10 = "a1/b3/e3/"
11 = "a1/b3/e3/e31.tx"
*/
checkKeyList("a1", "a1/b2/d2/", expectedKeys);
- // case-7: Reached Last Element, return EmptyList
+ // case-9: Reached Last Element, return EmptyList
expectedKeys = getExpectedKeyList("a1", "a1/b3/e3/e31.tx");
checkKeyList("a1", "a1/b3/e3/e31.tx", expectedKeys);
}
+ @Test
+ public void testListKeysWithNonExistentStartKey() throws Exception {
+ // case-1: StartKey LeafNode is lexographically ahead than prefixKey.
+ // So, will return EmptyList
+ // a1/b2 < a1/b2Invalid
+ List<String> expectedKeys = getExpectedKeyList("a1", "a1/a111/b111");
+ checkKeyList("a1", "a1/a111/b111", expectedKeys);
+ // a1/b2 < a1/b20
+ expectedKeys = getExpectedKeyList("a1/b2", "a1/b20");
+ checkKeyList("a1/b2", "a1/b20", expectedKeys);
+
+ // case-2: StartKey LeafNode's parent is lexographically ahead than
+ // prefixKey. So, will return EmptyList
+ // a1/b1 < a1/b2
+ expectedKeys = getExpectedKeyList("a1/b1", "a1/b2/d0");
+ checkKeyList("a1/b1", "a1/b2/d0", expectedKeys);
+
+ // case-3:
+ // StartKey LeafNode's parent is not matching with than prefixKey's parent.
+ // So, will return EmptyList
+ expectedKeys = getExpectedKeyList("a1/b2", "a0/b123Invalid");
+ checkKeyList("a1/b2", "a0/b123Invalid", expectedKeys);
+
+ // case-4: StartKey LeafNode is lexographically behind prefixKey.
+ // So will return all the sub-paths of prefixKey
+ // startKey=a1/b123Invalid is lexographically before prefixKey=a1/b2
+ expectedKeys = getExpectedKeyList("a1/b2", "a1/b123Invalid");
+ /**
+ * a1/b2/
+ * a1/b2/d1/
+ * a1/b2/d1/d11.tx
+ * a1/b2/d2/
+ * .....
+ * a1/b2/d3/
+ * a1/b2/d3/d31.tx
+ */
+ checkKeyList("a1/b2", "a1/b123Invalid", expectedKeys);
+
+ // case-5:
+ // StartKey LeafNode is a sub-directory of prefixKey.
+ // So will fetch and return all the sub-paths after d0.
+ expectedKeys = getExpectedKeyList("a1/b2", "a1/b2/d0");
+ /**
+ a1/b2/d1/
+ a1/b2/d1/d11.tx
+ .....
+ a1/b2/d3/
+ a1/b2/d3/d31.tx
+ */
+ checkKeyList("a1/b2", "a1/b2/d0", expectedKeys);
+ // case-6:
+ // StartKey LeafNode is a sub-file of prefixKey.
+ // So will fetch and return all the sub-paths after d111.txt.
+ expectedKeys = getExpectedKeyList("a1/b2", "a1/b2/d111.txt");
+ /**
+ * a1/b2/d2/
+ * a1/b2/d2/d21.tx
+ * a1/b2/d2/d22.tx
+ * a1/b2/d3/
+ * a1/b2/d3/d31.tx
+ */
+ checkKeyList("a1/b2", "a1/b2/d111.txt", expectedKeys);
+
+ // case-7:
+ // StartKey LeafNode is a sub-file of prefixKey.
+ // So will fetch and return all the sub-paths after "d3/d4111.tx".
+ // Since there is no sub-paths after "d3" it will return emptyList
+ expectedKeys = getExpectedKeyList("a1/b2", "a1/b2/d3/d4111.tx");
+ checkKeyList("a1/b2", "a1/b2/d3/d4111.tx", expectedKeys);
+
+ // case-8:
+ // StartKey LeafNode is a sub-dir of prefixKey.
+ // So will fetch and return all the sub-paths after "d311111".
+ expectedKeys = getExpectedKeyList("a1", "a1/b2/d311111");
+ /**
+ * a1/b3/
+ * a1/b3/e1/
+ * ....
+ * a1/b3/e3/
+ * a1/b3/e3/e31.tx
+ */
+ checkKeyList("a1", "a1/b2/d311111", expectedKeys);
+
+ // case-9:
+ // Immediate child of prefixKey is lexographically greater than "a1/b1".
+ // So will fetch and return all the sub-paths after "b11111",
+ // which is "a1/b2"
+ expectedKeys = getExpectedKeyList("a1", "a1/b11111/d311111");
+ /**
+ 0 = "a1/b2/"
+ 1 = "a1/b2/d1/"
+ 2 = "a1/b2/d1/d11.tx"
+ 3 = "a1/b2/d2/"
+ ........
+ 14 = "a1/b3/e3/e31.tx"
+ */
+ checkKeyList("a1", "a1/b11111/d311111", expectedKeys);
+
+ // case-10:
+ // StartKey "a1/b2/d2" is valid and get all the keys lexographically
+ // greater than "a1/b2/d2/d11111".
+ expectedKeys = getExpectedKeyList("a1", "a1/b2/d2/d21111");
+ /**
+ 0 = "a1/b2/d2/d22.tx"
+ 1 = "a1/b2/d3/"
+ ......
+ 7 = "a1/b3/e3/"
+ 8 = "a1/b3/e3/e31.tx"
+ */
+ checkKeyList("a1", "a1/b2/d2/d21111", expectedKeys);
+
+ // case-11:
+ // StartKey is a sub-path of prefixKey.
+ // So will fetch and return all the sub-paths after "e311111".
+ // Return EmptyList as we reached the end of the tree
+ expectedKeys = getExpectedKeyList("a1", "a1/b3/e3/e311111.tx");
+ checkKeyList("a1", "a1/b3/e3/e311111.tx", expectedKeys);
+
+ // case-12:
+ // StartKey is a sub-path of prefixKey.
+ // So will fetch and return all the sub-paths after "e4444".
+ // Return EmptyList as we reached the end of the tree
+ expectedKeys = getExpectedKeyList("a1/b2", "a1/b3/e4444");
+ checkKeyList("a1/b2", "a1/b3/e4444", expectedKeys);
+
+ // case-13:
+ // StartKey is a sub-path of prefixKey and startKey with a trailing slash.
+ // So will fetch and return all the sub-paths after "e".
+ expectedKeys = getExpectedKeyList("a1/b3", "a1/b3/e/");
+ checkKeyList("a1/b3", "a1/b3/e/", expectedKeys);
+
+ // case-14:
+ // PrefixKey is empty and search should consider startKey.
+ // Fetch all the keys after, a1/b2/d
+ expectedKeys = getExpectedKeyList("", "a1/b2/d");
+ checkKeyList("", "a1/b2/d", expectedKeys);
+
+ // case-15:
+ // PrefixKey is empty and search should consider startKey.
+ expectedKeys = getExpectedKeyList("", "a1/b2/d2/d21111");
+ checkKeyList("", "a1/b2/d2/d21111", expectedKeys);
+
+ // case-16:
+ // PrefixKey is empty and search should consider startKey.
+ expectedKeys = getExpectedKeyList("", "a0/b2/d2/d21111");
+ checkKeyList("", "a0/b2/d2/d21111", expectedKeys);
+ }
/**
* Verify listKeys at different levels.
@@ -269,7 +435,6 @@ public class TestListKeysWithFSO {
Iterator<? extends OzoneKey> ozoneKeyIterator =
legacyOzoneBucket.listKeys(keyPrefix, startKey);
-// fsoOzoneBucket.listStatus(keyPrefix, false, startKey, 5);
List<String> keys = new LinkedList<>();
while (ozoneKeyIterator.hasNext()) {
OzoneKey ozoneKey = ozoneKeyIterator.next();
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@ozone.apache.org
For additional commands, e-mail: commits-help@ozone.apache.org