apple/turicreate

Inefficient implementation on checking if path is a s3 directory

Open

#3,049 opened on Mar 14, 2020

View on GitHub
 (0 comments) (0 reactions) (0 assignees)C++ (11,135 stars) (1,161 forks)batch import
S3good first issue

Description

our current implementation of s3 is_directory is to exhaust all keys under a certain URL (a.k.a, prefix, "folder" or "group") and compare the URL with each item returned, e.g., Contents[Key] and CommonPrefixes. This is a bad practice if the URL contains many keys and the comparison is linear O(n).

Besides that, is_directory is widely used in our codebase, not to mention the time complexity, the network delay will be observable.

A solution should be,

  • head on URL assuming it's an object. If 404, then
  • list-objects --with-delimiter and --max-items=1, and check the CommonPrefixes section. You can provide an extra parameter to tell list_objects_impl to do so by setting the max keys to return.

Contributor guide

Tech stack
cppaws
Domain
performanceinfrastructure
Issue type
performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
3
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
1-3 hours
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
Basic knowledge of AWS S3 operationsFamiliarity with the turicreate codebase structure
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
70
Research direction
Investigate the implementation of `is directory` in the S3 file system code. The current implementation exhaustively lists all keys. Replace it with a two step approach: first HEAD on the URL, then if 404, list objects with delimiter and max items=1, checking CommonPrefixes. The relevant function is likely in the S3 storage adapter file. Ensure the change is efficient and handles edge cases.
Inefficient implementation on checking if path is a s3 directory · apple/turicreate#3049 | Good First Issue