linyiqun commented on a change in pull request #1954:
URL: https://github.com/apache/ozone/pull/1954#discussion_r582880047
##########
File path:
hadoop-ozone/client/src/main/java/org/apache/hadoop/ozone/client/OzoneBucket.java
##########
@@ -828,10 +846,286 @@ 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);
+ }
+
+ @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("e3")
+ * Reached end of the FS tree.
+ *
+ * @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);
+
+ // 4. Special case: ListKey expects startKey shouldn't present in the
+ // resultList. Since proxy#listStatus API returns startKey element to
+ // the returnList, this function is to remove the startKey element.
+ removeStartKeyIfExistsInStatusList(startKey, statuses);
+
+ boolean reachedLimitCacheSize = false;
+ // This dirList is used to store paths elements in left-to-right order.
+ List<String> dirList = new ArrayList<>();
+
+ // 5. Iterating over the resultStatuses list and add each key to the
+ // resultList. If the listCacheSize reaches then it will add the rest
+ // of the statuses to pendingItemsToBeBatched
+ for (int indx = 0; indx < statuses.size(); indx++) {
+ OzoneFileStatus status = statuses.get(indx);
+ OmKeyInfo keyInfo = status.getKeyInfo();
+ String keyName = keyInfo.getKeyName();
+
+ // Add dir to the dirList
+ if (status.isDirectory()) {
+ dirList.add(keyInfo.getKeyName());
+ // add trailing slash to represent directory
+ keyName = OzoneFSUtils.addTrailingSlashIfNeeded(keyName);
+ }
+
+ OzoneKey ozoneKey = new OzoneKey(keyInfo.getVolumeName(),
+ keyInfo.getBucketName(), keyName,
+ keyInfo.getDataSize(), keyInfo.getCreationTime(),
+ keyInfo.getModificationTime(),
+ ReplicationType.valueOf(keyInfo.getType().toString()),
+ keyInfo.getFactor().getNumber());
+
+ // 5.1) Add to the resultList till it reaches limit batch size.
+ // Once it reaches limit, then add rest of the items to
+ // pendingItemsToBeBatched and this will picked in next batch iteration
+ if (!reachedLimitCacheSize && listCacheSize > keysResultList.size()) {
+ keysResultList.add(ozoneKey);
+ reachedLimitCacheSize = listCacheSize <= keysResultList.size();
+ } else {
+ pendingItemsToBeBatched.add(ozoneKey);
+ }
+ }
+
+ // 6. Push elements in reverse order so that the FS tree traversal will
+ // occur in left-to-right fashion.
+ for (int indx = dirList.size() - 1; indx >= 0; indx--) {
+ String dirPathComponent = dirList.get(indx);
+ stack.push(dirPathComponent);
+ }
+
+ if (reachedLimitCacheSize) {
+ return true;
+ }
+
+ // 7. Pop element and seek for its sub-child path(s). Basically moving
+ // seek pointer to next level(depth) in FS tree.
+ while (!stack.isEmpty()) {
+ keyPrefix = stack.pop();
+ if (getChildrenKeys(keyPrefix, "", keysResultList)) {
+ // reached limit batch size.
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ private void removeStartKeyIfExistsInStatusList(String startKey,
+ List<OzoneFileStatus> statuses) {
+
+ if (StringUtils.isNotBlank(startKey) && !statuses.isEmpty()) {
+ String startKeyPath = startKey;
+ if (startKey.endsWith(OZONE_URI_DELIMITER)) {
+ startKeyPath = OzoneFSUtils.removeTrailingSlashIfNeeded(startKey);
+ }
+ if (StringUtils.equals(statuses.get(0).getKeyInfo().getKeyName(),
+ startKeyPath)) {
+ // remove the duplicateKey from the list.
+ statuses.remove(0);
+ }
+ }
+ }
+
+ private boolean addAllPendingItemsToResultList(List<OzoneKey> keys) {
+
+ Iterator<OzoneKey> ozoneKeyItr = pendingItemsToBeBatched.iterator();
+ while (ozoneKeyItr.hasNext()) {
+ if (listCacheSize <= keys.size()) {
+ // reached limit batch size.
+ return true;
+ }
+ keys.add(ozoneKeyItr.next());
+ ozoneKeyItr.remove();
+ }
+ return false;
+ }
+
+ private void addKeyPrefixInfoToResultList(String keyPrefix,
+ String startKey, List<OzoneKey> keysResultList) throws IOException {
+
+ if (addedKeyPrefix) {
+ return;
+ }
+
+ // setting flag to true.
+ addedKeyPrefix = true;
+
+ // not required to addKeyPrefix
+ // case-1) if keyPrefix is null or empty
+ // case-2) if startKey is not null or empty
+ if (StringUtils.isBlank(keyPrefix) || StringUtils.isNotBlank(startKey)) {
+ return;
+ }
+
+ // TODO: Handle a case, where startKey not started with keyPrefix.
Review comment:
Will we also addressed on this case in HDDS-4859?
----------------------------------------------------------------
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]
