This is an automated email from the ASF dual-hosted git repository.
sammichen 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 8e52a3a6f2 HDDS-8773. [S3G] Improve list performance in FSO bucket
(#4868)
8e52a3a6f2 is described below
commit 8e52a3a6f2c9819163e602765fd4dbe9501a0f0f
Author: Hongbing Wang <[email protected]>
AuthorDate: Thu Nov 9 12:13:16 2023 +0800
HDDS-8773. [S3G] Improve list performance in FSO bucket (#4868)
---
.../apache/hadoop/ozone/client/OzoneBucket.java | 271 +++++++++++++++------
.../hadoop/ozone/om/TestListKeysWithFSO.java | 96 +++++++-
2 files changed, 290 insertions(+), 77 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 c4c68c00fd..d6e99dd139 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
@@ -1072,6 +1072,10 @@ public class OzoneBucket extends WithMetadata {
private boolean addedKeyPrefix;
private String delimiterKeyPrefix;
+ boolean shallow() {
+ return shallow;
+ }
+
String getKeyPrefix() {
return keyPrefix;
}
@@ -1088,6 +1092,14 @@ public class OzoneBucket extends WithMetadata {
this.addedKeyPrefix = addedKeyPrefix;
}
+ String getDelimiterKeyPrefix() {
+ return delimiterKeyPrefix;
+ }
+
+ void setDelimiterKeyPrefix(String delimiterKeyPrefix) {
+ this.delimiterKeyPrefix = delimiterKeyPrefix;
+ }
+
/**
* Creates an Iterator to iterate over all keys after prevKey in the
bucket.
* If prevKey is null it iterates from the first key in the bucket.
@@ -1142,8 +1154,8 @@ public class OzoneBucket extends WithMetadata {
}
/**
- * Using listStatus instead of listKeys avoiding listing all children keys.
- * Giving the structure of keys delimited by "/":
+ * Using listStatusLight instead of listKeys avoiding listing all children
+ * keys. Giving the structure of keys delimited by "/":
*
* buck-1
* |
@@ -1192,15 +1204,16 @@ public class OzoneBucket extends WithMetadata {
* In implementation, the keyPrefix "a/b" can be identified in listKeys,
* but cannot be identified in listStatus. Therefore, keyPrefix "a/b"
* needs to be split into keyPrefix "a" and call listKeys method to get
- * the next one key as the startKey in listStatus.
+ * the next one key as the startKey in listStatusLight.
*/
- protected List<OzoneKey> getNextShallowListOfKeys(String prevKey)
+ List<OzoneKey> getNextShallowListOfKeys(String prevKey)
throws IOException {
List<OzoneKey> resultList = new ArrayList<>();
String startKey = prevKey;
- // handle for first round
+ // 1. Get first element as startKey
if (!addedKeyPrefix) {
+ initDelimiterKeyPrefix();
// prepare startKey
List<OzoneKey> nextOneKeys =
proxy.listKeys(volumeName, name, getKeyPrefix(), prevKey, 1);
@@ -1218,16 +1231,9 @@ public class OzoneBucket extends WithMetadata {
startKey.equals(getKeyPrefix())) {
resultList.add(nextOneKeys.get(0));
}
-
- // prepare delimiterKeyPrefix
- delimiterKeyPrefix = getKeyPrefix();
- if (!getKeyPrefix().endsWith(OZONE_URI_DELIMITER)) {
- delimiterKeyPrefix = OzoneFSUtils.getParentDir(getKeyPrefix());
- }
}
- // Elements in statuses must be sorted after startKey,
- // which means they come after the keyPrefix.
+ // 2. Get immediate children by listStatusLight method
List<OzoneFileStatusLight> statuses =
proxy.listStatusLight(volumeName, name, delimiterKeyPrefix, false,
startKey, listCacheSize, false);
@@ -1239,16 +1245,20 @@ public class OzoneBucket extends WithMetadata {
setAddedKeyPrefix(true);
}
- List<OzoneKey> ozoneKeys = buildOzoneKeysFromFileStatus(statuses)
- .stream()
- .filter(key -> StringUtils.startsWith(key.getName(), getKeyPrefix()))
- .collect(Collectors.toList());
+ List<OzoneKey> ozoneKeys = buildKeysWithKeyPrefix(statuses);
resultList.addAll(ozoneKeys);
return resultList;
}
- private List<OzoneKey> buildOzoneKeysFromFileStatus(
+ protected void initDelimiterKeyPrefix() {
+ setDelimiterKeyPrefix(getKeyPrefix());
+ if (!getKeyPrefix().endsWith(OZONE_URI_DELIMITER)) {
+ setDelimiterKeyPrefix(OzoneFSUtils.getParentDir(getKeyPrefix()));
+ }
+ }
+
+ protected List<OzoneKey> buildKeysWithKeyPrefix(
List<OzoneFileStatusLight> statuses) {
return statuses.stream()
.map(status -> {
@@ -1264,6 +1274,7 @@ public class OzoneBucket extends WithMetadata {
keyInfo.getModificationTime(),
keyInfo.getReplicationConfig(), keyInfo.isFile());
})
+ .filter(key -> StringUtils.startsWith(key.getName(), getKeyPrefix()))
.collect(Collectors.toList());
}
@@ -1354,63 +1365,14 @@ public class OzoneBucket extends WithMetadata {
stack = new Stack();
}
+ if (shallow()) {
+ return getNextShallowListOfKeys(prevKey);
+ }
+
// normalize paths
if (!addedKeyPrefix()) {
- prevKey = OmUtils.normalizeKey(prevKey, true);
- String keyPrefixName = "";
- if (StringUtils.isNotBlank(getKeyPrefix())) {
- keyPrefixName = OmUtils.normalizeKey(getKeyPrefix(), true);
- }
- setKeyPrefix(keyPrefixName);
-
- 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())) {
- // If the prev key is a dir then seek its sub-paths
- // Say, prevKey="a1/b2/d2"
- addPrevDirectoryToSeekPath(prevKey, seekPaths);
- }
-
- // Key Prefix is Blank. The seek all the keys with startKey.
- removeStartKey = prevKey;
- getSeekPathsBetweenKeyPrefixAndStartKey(getKeyPrefix(), prevKey,
- seekPaths);
-
- // 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.isAncestorPath(getKeyPrefix(), prevKey)) {
- // Case-1 - sibling: keyPrefix="a1/b2", startKey="a0/b123Invalid"
- // Skip traversing, if the startKey is not a sibling.
- // "a1/b", "a1/b1/e/"
- 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(), ""));
- }
- }
+ if (!prepareStack(prevKey)) {
+ return new ArrayList<>();
}
}
@@ -1437,6 +1399,169 @@ public class OzoneBucket extends WithMetadata {
return keysResultList;
}
+ @Override
+ List<OzoneKey> getNextShallowListOfKeys(String prevKey)
+ throws IOException {
+ List<OzoneKey> resultList = new ArrayList<>();
+ String startKey = prevKey;
+ boolean findFirstStartKey = false;
+
+ if (!addedKeyPrefix()) {
+ initDelimiterKeyPrefix();
+
+ if (!prepareStack(prevKey)) {
+ return new ArrayList<>();
+ }
+
+ // 1. Get first element as startKey.
+ List<OzoneKey> firstKeyResult = new ArrayList<>();
+ if (stack.isEmpty()) {
+ // Case: startKey is empty
+ getChildrenKeys(getKeyPrefix(), prevKey, firstKeyResult);
+ } else {
+ // Case: startKey is non-empty
+ while (!stack.isEmpty()) {
+ Pair<String, String> keyPrefixPath = stack.pop();
+ getChildrenKeys(keyPrefixPath.getLeft(), keyPrefixPath.getRight(),
+ firstKeyResult);
+ if (!firstKeyResult.isEmpty()) {
+ break;
+ }
+ }
+ }
+ if (!firstKeyResult.isEmpty()) {
+ startKey = firstKeyResult.get(0).getName();
+ findFirstStartKey = true;
+ }
+
+ // A specific case where findFirstStartKey is false does not mean that
+ // the final result is empty because also need to determine whether
+ // keyPrefix is an existing key. Consider the following structure:
+ // te/
+ // test1/
+ // test1/file1
+ // test1/file2
+ // test2/
+ // when keyPrefix='te' and prevKey='test1/file2', findFirstStartKey
+ // will be false because 'test1/file2' is the last key in dir
+ // 'test1/'. In the correct result for this case, 'test2/' is expected
+ // in the results and "test1/" should be excluded.
+ //
+ if (!findFirstStartKey) {
+ if (StringUtils.isBlank(prevKey) || !keyPrefixExist()
+ || !StringUtils.startsWith(prevKey, getKeyPrefix())) {
+ return new ArrayList<>();
+ }
+ }
+ // A special case where keyPrefix element should present in the
+ // resultList. See the annotation of #addKeyPrefixInfoToResultList
+ if (getKeyPrefix().equals(startKey) && findFirstStartKey
+ && !firstKeyResult.get(0).isFile()) {
+ resultList.add(firstKeyResult.get(0));
+ }
+ // Note that the startKey needs to be an immediate child of the
+ // keyPrefix or black before calling listStatus.
+ startKey = adjustStartKey(startKey);
+ }
+
+ // 2. Get immediate children by listStatus method.
+ List<OzoneFileStatusLight> statuses =
+ proxy.listStatusLight(volumeName, name, getDelimiterKeyPrefix(),
+ false, startKey, listCacheSize, false);
+
+ if (!statuses.isEmpty()) {
+ // If findFirstStartKey is false, indicates that the keyPrefix is an
+ // existing key and the prevKey is the last element within its
+ // directory. In this case, the result should not include the
+ // startKey itself.
+ if (!findFirstStartKey && addedKeyPrefix()) {
+ statuses.remove(0);
+ }
+ List<OzoneKey> ozoneKeys = buildKeysWithKeyPrefix(statuses);
+ resultList.addAll(ozoneKeys);
+ }
+ return resultList;
+ }
+
+ private boolean prepareStack(String prevKey) throws IOException {
+ prevKey = OmUtils.normalizeKey(prevKey, true);
+ String keyPrefixName = "";
+ if (StringUtils.isNotBlank(getKeyPrefix())) {
+ keyPrefixName = OmUtils.normalizeKey(getKeyPrefix(), true);
+ }
+ setKeyPrefix(keyPrefixName);
+
+ 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())) {
+ // If the prev key is a dir then seek its sub-paths
+ // Say, prevKey="a1/b2/d2"
+ addPrevDirectoryToSeekPath(prevKey, seekPaths);
+ }
+
+ // Key Prefix is Blank. The seek all the keys with startKey.
+ removeStartKey = prevKey;
+ getSeekPathsBetweenKeyPrefixAndStartKey(getKeyPrefix(), prevKey,
+ seekPaths);
+
+ // 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.isAncestorPath(getKeyPrefix(), prevKey)) {
+ // Case-1 - sibling: keyPrefix="a1/b2", startKey="a0/b123Invalid"
+ // Skip traversing, if the startKey is not a sibling.
+ // "a1/b", "a1/b1/e/"
+ return false;
+ } 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(), ""));
+ }
+ }
+ }
+ return true;
+ }
+
+ private String adjustStartKey(String startKey) {
+ if (getKeyPrefix().endsWith(OZONE_URI_DELIMITER) &&
+ getKeyPrefix().equals(startKey)) {
+ return "";
+ }
+ return OzoneFSUtils.getImmediateChild(startKey, getDelimiterKeyPrefix());
+ }
+
+ private boolean keyPrefixExist() throws IOException {
+ OzoneFileStatus keyPrefixStatus = null;
+ try {
+ keyPrefixStatus =
+ proxy.getOzoneFileStatus(volumeName, name, getKeyPrefix());
+ } catch (OMException ome) {
+ // ignore exception
+ }
+ return keyPrefixStatus != null;
+ }
+
private void addPrevDirectoryToSeekPath(String prevKey,
List<Pair<String, String>> seekPaths)
throws IOException {
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 ef6412cd9a..5174fe5af7 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
@@ -412,6 +412,71 @@ public class TestListKeysWithFSO {
checkKeyList("a", "a1", expectedKeys, fsoOzoneBucket2);
}
+ @Test
+ public void testShallowListKeys() throws Exception {
+ List<String> expectedKeys;
+
+ // case-1: startKey not reaches last key
+ String keyPrefix = "a1/b1/";
+ String startKey = "a1/b1/c12/c2.tx";
+ // a1/b1/c12/
+ // a1/b1/c1222.tx
+ // a1/b1/c1333.tx
+ // a1/b1/c1444.tx
+ // a1/b1/c1555.tx
+ expectedKeys =
+ getExpectedKeyShallowList(keyPrefix, startKey, legacyOzoneBucket);
+ checkKeyShallowList(keyPrefix, startKey, expectedKeys, fsoOzoneBucket);
+
+ // case-2: startKey reaches last key
+ keyPrefix = "a1/b1/";
+ startKey = "a1/b1/c12/c3.tx";
+ // a1/b1/c1222.tx
+ // a1/b1/c1333.tx
+ // a1/b1/c1444.tx
+ // a1/b1/c1555.tx
+ expectedKeys =
+ getExpectedKeyShallowList(keyPrefix, startKey, legacyOzoneBucket);
+ checkKeyShallowList(keyPrefix, startKey, expectedKeys, fsoOzoneBucket);
+
+ // case-3: keyPrefix non-exist and startKey not reaches last key
+ keyPrefix = "a1/b";
+ startKey = "a1/b1/c1444.tx";
+ // a1/b1/
+ // a1/b2/
+ // a1/b3/
+ expectedKeys =
+ getExpectedKeyShallowList(keyPrefix, startKey, legacyOzoneBucket);
+ checkKeyShallowList(keyPrefix, startKey, expectedKeys, fsoOzoneBucket);
+
+ // case-4: keyPrefix non-exist and startKey reaches last key
+ keyPrefix = "a1/b";
+ startKey = "a1/b1/c1555.tx";
+ // a1/b2/
+ // a1/b3/
+ expectedKeys =
+ getExpectedKeyShallowList(keyPrefix, startKey, legacyOzoneBucket);
+ checkKeyShallowList(keyPrefix, startKey, expectedKeys, fsoOzoneBucket);
+
+ // case-5: keyPrefix corresponds to multiple existing keys.
+ keyPrefix = "a1/b1/c12";
+ startKey = "";
+ // a1/b1/c12/
+ // a1/b1/c1222.tx
+ expectedKeys =
+ getExpectedKeyShallowList(keyPrefix, startKey, legacyOzoneBucket);
+ checkKeyShallowList(keyPrefix, startKey, expectedKeys, fsoOzoneBucket);
+
+ // case-6: keyPrefix corresponds to multiple existing keys and
+ // startKey reaches last key
+ keyPrefix = "a1/b1/c12";
+ startKey = "a1/b1/c12/c3.tx";
+ // a1/b1/c1222.tx
+ expectedKeys =
+ getExpectedKeyShallowList(keyPrefix, startKey, legacyOzoneBucket);
+ checkKeyShallowList(keyPrefix, startKey, expectedKeys, fsoOzoneBucket);
+ }
+
/**
* Verify listKeys at different levels.
*
@@ -485,9 +550,10 @@ public class TestListKeysWithFSO {
private static List<String> getExpectedKeyList(String keyPrefix,
- String startKey, OzoneBucket legacyBucket) throws Exception {
+ String startKey, OzoneBucket legacyBucket, boolean shallow)
+ throws Exception {
Iterator<? extends OzoneKey> ozoneKeyIterator =
- legacyBucket.listKeys(keyPrefix, startKey);
+ legacyBucket.listKeys(keyPrefix, startKey, shallow);
List<String> keys = new LinkedList<>();
while (ozoneKeyIterator.hasNext()) {
@@ -497,11 +563,23 @@ public class TestListKeysWithFSO {
return keys;
}
+ private static List<String> getExpectedKeyList(String keyPrefix,
+ String startKey, OzoneBucket legacyBucket)
+ throws Exception {
+ return getExpectedKeyList(keyPrefix, startKey, legacyBucket, false);
+ }
+
+ private static List<String> getExpectedKeyShallowList(String keyPrefix,
+ String startKey, OzoneBucket legacyBucket) throws Exception {
+ return getExpectedKeyList(keyPrefix, startKey, legacyBucket, true);
+ }
+
private void checkKeyList(String keyPrefix, String startKey,
- List<String> keys, OzoneBucket fsoBucket) throws Exception {
+ List<String> keys, OzoneBucket fsoBucket, boolean shallow)
+ throws Exception {
Iterator<? extends OzoneKey> ozoneKeyIterator =
- fsoBucket.listKeys(keyPrefix, startKey);
+ fsoBucket.listKeys(keyPrefix, startKey, shallow);
ReplicationConfig expectedReplication =
Optional.ofNullable(fsoBucket.getReplicationConfig())
.orElse(cluster.getOzoneManager().getDefaultReplicationConfig());
@@ -523,6 +601,16 @@ public class TestListKeysWithFSO {
Assert.assertEquals(keys, outputKeysList);
}
+ private void checkKeyList(String keyPrefix, String startKey,
+ List<String> keys, OzoneBucket fsoBucket) throws Exception {
+ checkKeyList(keyPrefix, startKey, keys, fsoBucket, false);
+ }
+
+ private void checkKeyShallowList(String keyPrefix, String startKey,
+ List<String> keys, OzoneBucket fsoBucket) throws Exception {
+ checkKeyList(keyPrefix, startKey, keys, fsoBucket, true);
+ }
+
private static void createKeys(OzoneBucket ozoneBucket, List<String> keys)
throws Exception {
int length = 10;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
