rakeshadr commented on a change in pull request #1954:
URL: https://github.com/apache/ozone/pull/1954#discussion_r582577681
##########
File path:
hadoop-ozone/client/src/main/java/org/apache/hadoop/ozone/client/OzoneBucket.java
##########
@@ -828,10 +846,285 @@ public OzoneKey next() {
* @param prevKey
* @return {@code List<OzoneKey>}
*/
- private List<OzoneKey> getNextListOfKeys(String prevKey) throws
+ List<OzoneKey> getNextListOfKeys(String prevKey) throws
IOException {
return proxy.listKeys(volumeName, name, keyPrefix, prevKey,
listCacheSize);
}
}
+
+
+ /**
+ * An Iterator to iterate over {@link OzoneKey} list.
+ *
+ * buck-1
+ * |
+ * a
+ * |
+ * -----------------------------------
+ * | | |
+ * b1 b2 b3
+ * ----- -------- ----------
+ * | | | | | | | |
+ * c1 c2 d1 d2 d3 e1 e2 e3
+ * | |
+ * -------- |
+ * | | |
+ * d21.txt d22.txt e11.txt
+ *
+ * Say, keyPrefix="a" and prevKey="", then will do Depth-First-Traversal and
+ * visit node to getChildren in below fashion:-
+ * 1. getChildren("a/") 2. getChildren("a/b1") 3. getChildren("a/b1/c1")
+ * 4. getChildren("a/b1/c2") 5. getChildren("a/b2/d1")
+ * 6. getChildren("a/b2/d2") 7. getChildren("a/b2/d3")
+ * 8. getChildren("a/b3/e1") 9. getChildren("a/b3/e2")
+ * 10. getChildren("a/b3/e3")
+ *
+ * Note: Does not guarantee to return the list of keys in a sorted order.
+ */
+ private class KeyIteratorV1 extends KeyIterator{
+
+ private Stack<String> stack;
+ private List<OzoneKey> pendingItemsToBeBatched;
+ private boolean addedKeyPrefix;
+
+ /**
+ * 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.
+ * The returned keys match key prefix.
+ *
+ * @param keyPrefix
+ * @param prevKey
+ */
+ KeyIteratorV1(String keyPrefix, String prevKey) throws IOException {
+ super(keyPrefix, prevKey);
+ addedKeyPrefix = true;
+ }
+
+ @Override
+ List<OzoneKey> getNextListOfKeys(String prevKey) throws IOException {
+ if (stack == null) {
+ stack = new Stack();
+ pendingItemsToBeBatched = new ArrayList<>();
+ }
+
+ // normalize paths
+ if (!addedKeyPrefix) {
+ prevKey = OmUtils.normalizeKey(prevKey, true);
+ String keyPrefixName = "";
+ if (StringUtils.isNotBlank(getKeyPrefix())) {
+ keyPrefixName = OmUtils.normalizeKey(getKeyPrefix(), true);
+ }
+ setKeyprefix(keyPrefixName);
+ }
+
+ // Get immediate children
+ List<OzoneKey> keysResultList = new ArrayList<>();
+ getChildrenKeys(getKeyPrefix(), prevKey, keysResultList);
+
+ // TODO: Back and Forth seek all the files & dirs, starting from
+ // startKey till keyPrefix.
+
+ return keysResultList;
+ }
+
+ /**
+ * List children under the given keyPrefix and startKey path. It does
+ * recursive #listStatus calls to list all the sub-keys resultList.
+ *
+ * buck-1
+ * |
+ * a
+ * |
+ * -----------------------------------
+ * | | |
+ * b1 b2 b3
+ * ----- -------- ----------
+ * | | | | | | | |
+ * c1 c2 d1 d2 d3 e1 e2 e3
+ * | |
+ * -------- |
+ * | | |
+ * d21.txt d22.txt e11.txt
+ *
+ * Say, KeyPrefix = "a" and startKey = null;
+ *
+ * Iteration-1) RPC call proxy#listStatus("a").
+ * Add b3, b2 and b1 to stack.
+ * Iteration-2) pop b1 and do RPC call proxy#listStatus("b1")
+ * Add c2, c1 to stack.
+ * Iteration-3) pop c1 and do RPC call proxy#listStatus("c1"). Empty list.
+ * Iteration-4) pop c2 and do RPC call proxy#listStatus("c2"). Empty list.
+ * Iteration-5) pop b2 and do RPC call proxy#listStatus("b2")
+ * Add d3, d2 and d1 to stack.
+ * ..........
+ * ..........
+ * Iteration-n) pop e3 and do RPC call proxy#listStatus("e2")
+ * Add d3, d2 and d1 to stack.
+ *
+ * @param keyPrefix
+ * @param startKey
+ * @param keysResultList
+ * @return true represents it reached limit batch size, false otherwise.
+ * @throws IOException
+ */
+ private boolean getChildrenKeys(String keyPrefix, String startKey,
+ List<OzoneKey> keysResultList) throws IOException {
+
+ // listStatus API expects a not null 'startKey' value
+ startKey = startKey == null ? "" : startKey;
+
+ // 1. Add pending items to the user key resultList
+ if (addAllPendingItemsToResultList(keysResultList)) {
+ // reached limit batch size.
+ return true;
+ }
+
+ // 2. Get immediate children of keyPrefix, starting with startKey
+ List<OzoneFileStatus> statuses = proxy.listStatus(volumeName, name,
+ keyPrefix, false, startKey, listCacheSize);
+
+ // 3. Special case: ListKey expects keyPrefix element should present in
+ // the resultList, only if startKey is blank. If startKey is not blank
+ // then resultList shouldn't contain the startKey element.
+ // Since proxy#listStatus API won't return keyPrefix element in the
+ // resultList. So, this is to add user given keyPrefix to the return
list.
+ addKeyPrefixInfoToResultList(keyPrefix, startKey, keysResultList);
Review comment:
#listKeys API expects the user given `keyPrefix` element should be there
in the `returnKeysList`. Since client is calling #listStatus API, it won't
include the `keyPrefix` element in returnKeysList. Please refer [KeyManagerImpl
code](https://github.com/apache/ozone/blob/HDDS-2939/hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/KeyManagerImpl.java#L2229)
where OM is skipping the keyPrefix element. So, I have made an explicit call
to getFileStatus("keyPrefix") and add to the `returnKeysList`.
Please refer [existing test case for the existence of
keyPrefix](https://github.com/apache/ozone/blob/master/hadoop-ozone/integration-test/src/test/java/org/apache/hadoop/fs/ozone/TestOzoneFSWithObjectStoreCreate.java#L376)
in the listKeys return values.
##########
File path:
hadoop-ozone/integration-test/src/test/java/org/apache/hadoop/ozone/om/TestObjectStoreV1.java
##########
@@ -275,6 +285,246 @@ public void testLookupKey() throws Exception {
dirPathC.getObjectID(), true);
}
+ /**
+ * Verify listKeys at different levels.
+ *
+ * buck-1
+ * |
+ * a
+ * |
+ * -----------------------------------
+ * | | |
+ * b1 b2 b3
+ * ----- -------- ----------
+ * | | | | | | | |
+ * c1 c2 d1 d2 d3 e1 e2 e3
+ * | | | | | | | |
+ * c1.tx c2.tx d11.tx | d31.tx | | e31.tx
+ * -------- | e21.tx
+ * | | |
+ * d21.tx d22.tx e11.tx
+ *
+ * Above is the FS tree structure.
+ */
+ @Test
+ public void testListKeysAtDifferentLevels() throws Exception {
+ OzoneClient client = cluster.getClient();
+
+ ObjectStore objectStore = client.getObjectStore();
+ OzoneVolume ozoneVolume = objectStore.getVolume(volumeName);
+ Assert.assertTrue(ozoneVolume.getName().equals(volumeName));
+ OzoneBucket ozoneBucket = ozoneVolume.getBucket(bucketName);
+ Assert.assertTrue(ozoneBucket.getName().equals(bucketName));
+
+ String keyc1 = "/a/b1/c1/c1.tx";
+ String keyc2 = "/a/b1/c2/c2.tx";
+
+ String keyd13 = "/a/b2/d1/d11.tx";
+ String keyd21 = "/a/b2/d2/d21.tx";
+ String keyd22 = "/a/b2/d2/d22.tx";
+ String keyd31 = "/a/b2/d3/d31.tx";
+
+ String keye11 = "/a/b3/e1/e11.tx";
+ String keye21 = "/a/b3/e2/e21.tx";
+ String keye31 = "/a/b3/e3/e31.tx";
+
+ LinkedList<String> keys = new LinkedList<>();
+ keys.add(keyc1);
+ keys.add(keyc2);
+
+ keys.add(keyd13);
+ keys.add(keyd21);
+ keys.add(keyd22);
+ keys.add(keyd31);
+
+ keys.add(keye11);
+ keys.add(keye21);
+ keys.add(keye31);
+
+ int length = 10;
+ byte[] input = new byte[length];
+ Arrays.fill(input, (byte)96);
+
+ createKeys(ozoneBucket, keys);
+
+ // Root level listing keys
+ Iterator<? extends OzoneKey> ozoneKeyIterator =
+ ozoneBucket.listKeys("/a", null);
+
+ LinkedList<String> expectedKeys = new LinkedList<>();
+ expectedKeys.add("a/");
+ expectedKeys.add("a/b1/");
+ expectedKeys.add("a/b2/");
+ expectedKeys.add("a/b3/");
+ expectedKeys.add("a/b1/c1/");
+ expectedKeys.add("a/b1/c2/");
+ expectedKeys.add("a/b1/c1/c1.tx");
+ expectedKeys.add("a/b1/c2/c2.tx");
+ expectedKeys.add("a/b2/d1/");
+ expectedKeys.add("a/b2/d2/");
+ expectedKeys.add("a/b2/d3/");
+ expectedKeys.add("a/b2/d1/d11.tx");
+ expectedKeys.add("a/b2/d2/d21.tx");
+ expectedKeys.add("a/b2/d2/d22.tx");
+ expectedKeys.add("a/b2/d3/d31.tx");
+ expectedKeys.add("a/b3/e1/");
+ expectedKeys.add("a/b3/e2/");
+ expectedKeys.add("a/b3/e3/");
+ expectedKeys.add("a/b3/e1/e11.tx");
+ expectedKeys.add("a/b3/e2/e21.tx");
+ expectedKeys.add("a/b3/e3/e31.tx");
+ checkKeyList(ozoneKeyIterator, expectedKeys);
+
+ // Intermediate level keyPrefix - 2nd level
+ ozoneKeyIterator =
+ ozoneBucket.listKeys("a///b2///", null);
+ expectedKeys = new LinkedList<>();
+ expectedKeys.add("a/b2/");
+ expectedKeys.add("a/b2/d1/");
+ expectedKeys.add("a/b2/d2/");
+ expectedKeys.add("a/b2/d3/");
+ expectedKeys.add("a/b2/d1/d11.tx");
+ expectedKeys.add("a/b2/d2/d21.tx");
+ expectedKeys.add("a/b2/d2/d22.tx");
+ expectedKeys.add("a/b2/d3/d31.tx");
+ checkKeyList(ozoneKeyIterator, expectedKeys);
+
+ // Intermediate level keyPrefix - 3rd level
+ ozoneKeyIterator =
+ ozoneBucket.listKeys("a/b2/d1", null);
+ expectedKeys = new LinkedList<>();
+ expectedKeys.add("a/b2/d1/");
+ expectedKeys.add("a/b2/d1/d11.tx");
+ checkKeyList(ozoneKeyIterator, expectedKeys);
+
+ // Boundary of a level
+ ozoneKeyIterator =
+ ozoneBucket.listKeys("a/b2/d2", "a/b2/d2/d21.tx");
+ expectedKeys = new LinkedList<>();
+ expectedKeys.add("a/b2/d2/d22.tx");
+ checkKeyList(ozoneKeyIterator, expectedKeys);
+
+ // Boundary case - last node in the depth-first-traversal
+ ozoneKeyIterator =
+ ozoneBucket.listKeys("a/b3/e3", "a/b3/e3/e31.tx");
+ expectedKeys = new LinkedList<>();
+ checkKeyList(ozoneKeyIterator, expectedKeys);
Review comment:
Sure
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
