100만 파일 트리를 67초에서 0.055초로 (1,220×). 파일 한 줄도 잘못 누락하지 않으면서. 그리고 같은 변경이 부수효과로 9년 된 또 하나의 이슈 #1117 까지 닫는다 — 의도하지 않았던 결과였다.

(1편: 두 번 죽은 PR. 2편: 보수적 prune 분석. 이 글: 구현 + 벤치마크 + 부수효과.)

Part 1. 구현 — 세 파일

세 파일을 건드린다.

A. filters.py — 추가만, 변경 없음

(2편) 에서 본 함수 3개와 Filter.can_skip_directory 만 새로 들어간다. Filter.call, _match_pattern, _full_path_patterns, create_filter 모두 한 줄도 안 바꾼다. kyleknap 의 “filters.py 정책” 을 글자 그대로 지킨다.

B. filegenerator.py — 두 군데 가드

FileGenerator.__init__ 시그니처 확장:

def __init__(self, client, operation_name, follow_symlinks=True,
             page_size=None, result_queue=None, request_parameters=None,
             file_filter=None, is_dst_walker=False):
    ...
    self.file_filter = file_filter
    self.is_dst_walker = is_dst_walker

is_dst_walker=True 는 sync 의 reverse/destination walker 가 dst_patterns 를 사용하도록 한다. 단방향 cp/mv/rm 은 False (default).

가드 1 — should_ignore_file 의 사전 필터 (#1117 fix)

symlink 체크 후, triggers_warning 호출 전에 사전 필터를 삽입한다.

def should_ignore_file(self, path):
    if not self.follow_symlinks:
        if os.path.isdir(path) and path.endswith(os.sep):
            path = path[:-1]
        if os.path.islink(path):
            return True

    # === 추가된 per-file pre-filter probe ===
    if self.file_filter is not None:
        relevant_patterns = (
            self.file_filter.dst_patterns
            if self.is_dst_walker
            else self.file_filter.patterns)
    else:
        relevant_patterns = None

    if relevant_patterns:
        if not os.path.exists(path):
            return self.triggers_warning(path)
        if os.path.isdir(path):
            if self.file_filter.can_skip_directory(
                    path, 'local',
                    use_dst_patterns=self.is_dst_walker):
                return True
        else:
            probe = FileInfo(src=path, src_type='local')
            if not list(self.file_filter.call([probe])):
                return True
    # === 끝 ===

    warning_triggered = self.triggers_warning(path)
    ...

triggers_warning 전에 두는 게 결정적이다. is_readable() 이 디렉터리 가독성 체크용으로 os.listdir() 을 호출하기 때문에, 이 가드 없이는 excluded 서브트리를 readability 체크만으로 listdir 하게 된다 (fix 가 무력화된다).

가드 2 — list_files 재귀 분기에 prune (#1138 fix)

for name in names:
    file_path = join(path, name)
    if isdir(file_path):
        if self.file_filter is not None and \
                self.file_filter.can_skip_directory(
                    file_path, 'local',
                    use_dst_patterns=self.is_dst_walker):
            continue                                # prune subtree
        for x in self.list_files(file_path, dir_op):
            yield x
    else:
        stats = self._safely_get_file_stats(file_path)
        if stats:
            yield stats

이게 진짜 prune. 디렉터리 단위로 can_skip_directory 가 True 면 재귀 자체를 건너뛴다. 100만 파일이 들어 있는 가지를 통째로 무시한다.

C. subcommands.py — 단일 Filter 인스턴스 공유

이게 의외로 중요한 변경이다. 기존 코드는 sync 명령에서 Filter 를 4번 생성한다.

변경 전 (sync 기준 4회 호출):

fgen_kwargs = {..., 'result_queue': result_queue}
rgen_kwargs = {..., 'result_queue': result_queue}
...
'filters': [create_filter(self.parameters), create_filter(self.parameters)]

변경 후 (1회 호출):

file_filter = create_filter(self.parameters)
fgen_kwargs = {..., 'result_queue': result_queue, 'file_filter': file_filter}
rgen_kwargs = {..., 'result_queue': result_queue, 'file_filter': file_filter,
               'is_dst_walker': True}                  # sync only
...
'filters': [file_filter, file_filter]                  # sync
'filters': [file_filter]                               # cp / mv / rm

이유:

1. Walker 가 prune 결정을 내리려면 인스턴스 참조 필요 — kwargs 로 전달.
2. fgen/rgen 양쪽 다 — sync 는 src 와 dest 를 동시에 walk 해 Comparator 로 비교. 양쪽 모두 prune 적용해야 일관됨. cp/mv/rm 은 fgen 만 사용.
3. Post-walk 단계까지 같은 인스턴스 — walker prune 판정과 후필터링이 동일 패턴 객체를 봐야 동작 일관성 보장.
4. 부수효과: _full_path_patterns 컴파일이 sync 에서 4회 → 1회로 감소.

Part 2. 100만 파일 벤치마크

환경

fixture/
├── excluded/                           ← 제외 대상
│   ├── d0000/  ... d0999/              (1,000 디렉터리)
│   │   ├── f000  ... f998              (각 999 파일)
└── included/                           ← 전송 대상
    └── f0000  ... f0999                (1,000 파일)

총: 999,000 + 1,000 = 1,000,000 파일.

측정 방법

FileGenerator.call → Filter.call iterator chain 을 직접 실행. 실제 CLI 가 사용하는 동일 코드 경로지만 S3 네트워크 호출 없이 로컬 traverse 비용만 측정. file_filter=None 으로 하면 fix 적용 전 동작 (이하 PRE), file_filter=Filter(...) 로 하면 fix 적용 후 동작 (이하 HEAD).

filt = Filter(filter_pairs, src_root, src_root)
fg = FileGenerator(client=None, operation_name="sync",
                   file_filter=filt)  # HEAD only
n = sum(1 for _ in filt.call(fg.call(files)))

워밍업: 양쪽 모두 동일 fixture 에 대해 first run 으로 OS FS 캐시 채운 뒤 측정.

메인 시나리오

--exclude 'excluded/*' (canonical)

--exclude '*' --include 'included/*' (rsync 스타일)

Cold cache 측정도 PRE 66.75s 로 거의 동일. 병목은 disk I/O 가 아니라 listdir / stat syscall 개수 자체. 100만 vs 1천 차이가 그대로 반영된다.

정확성: 양쪽 모두 yield 한 파일 수 정확히 1,000개 (included 만). 결과 변동 없음.

Part 3. 13개 엣지 케이스

카테고리별 해석

Correctness — 13/13 결과 일치

어떤 패턴 조합에서도 fix 가 결과를 바꾸지 않는다. 회귀 0회.

Override 안전성 (A1)

--exclude 'cache/*' --include 'cache/keep.txt' — cache/ 디렉터리를 prune 해버리면 keep.txt 를 놓치는 함정. HEAD 는 can_skip_directory('cache/') 가 include 매치 가능성 감지 → False 반환 → prune 안 함. Filter.call 후처리로 정확히 keep.txt 만 yield. PR #5425 가 침몰한 design 난점이 안전하게 해결됨.

극단 케이스 (A5, B1)

• --exclude '*' 단독: 트리 전체를 root 에서 즉시 prune. 75s → 0s.
• 6단계 깊이 중첩 (a/b/c/d/e/excluded/*, 100k files at leaf): 7.3s → 0.001s, 7,290×.

이상한 컬럼 — C2, C3 의 warn 1→0

C2/C3 행만 speedup 컬럼이 다르다. warn 1→0. 다른 행들은 walk 비용을 줄였다고 표현하지만, 이 두 줄은 warning 횟수가 1에서 0이 됐다 는 의미다. 단지 빨라진 게 아니라 동작이 바뀌었다 — 이게 9년 된 또 다른 이슈 #1117 까지 닫아 버린다 (Part 4).

Fix 가 적용되지 않는 케이스 (regression 아님)

• A4, A7: 패턴이 fixture 와 매치 자체를 안 함. exclude 가 무효 → 모든 파일 yield. 양 버전 동일 동작.
• E1a --exclude 'excluded', E1b --exclude 'excluded/': trailing-slash 또는 슬래시 없는 단독 literal 패턴은 fnmatch 시멘틱상 정확한 경로 문자열만 매치. 안의 파일 (excluded/foo) 은 매치 안 됨. fix 의 책임 범위 밖 — filter 매치 시멘틱 자체는 변경되지 않음.
• A3 char class: _pattern_matches_all_under 가 보수적으로 False (rest 가 * 만 아님) → listdir 자체는 절약 0. 그럼에도 2.9× 빨라진 이유는 per-file probe 가 excluded 인 파일에 대해 stat + FileStat 객체 생성 + Filter.call 제너레이터 소비를 스킵하기 때문.

Part 4. 부수효과 — 9년 된 #1117 까지 자동으로 잡힌다

C2 와 C3 의 warn 1→0 컬럼은 단순한 성능 개선이 아니다. 우연히 또 하나의 9년 된 이슈를 풀어 버렸다.

두 케이스 자세히

C2 — excluded/secret/ 가 chmod 0 인 디렉터리.

• PRE: walker 가 excluded/ 로 들어가 secret/ 발견 → listdir 시도 → EACCES → warning 1회 → rc=2.
• HEAD: excluded/ 자체가 prune → secret/ 까지 도달 안 함 → warning 0 → rc=0.

C3 — excluded/dangle 이 broken symlink.

• PRE: walker 가 excluded/ 안의 dangle 발견 → stat 시도 → ENOENT → warning 1 → rc=2.
• HEAD: excluded/ prune → warning 0 → rc=0.

warn 1→0 의 의미: PRE 에서는 위 두 케이스 모두 사용자가 의도하지 않은 warning 을 띄우고 exit code 2 를 반환했었다. fix 후엔 warning 이 사라지고 rc=0 으로 떨어진다.

이게 aws/aws-cli#1117 다

$ mkdir demo && mkfifo demo/bad && touch demo/good
$ aws s3 sync demo/ s3://bucket/demo/ --exclude '*' --dryrun
warning: Skipping file /private/tmp/demo/bad. File is character special device, ...
$ echo $?
2

aws/aws-cli#1117 “Non zero RC for S3 sync even if file is excluded” — 2015년 4월에 열린 또 하나의 9년 된 OPEN 이슈. --exclude '*' 로 모든 걸 제외했는데도 FIFO 파일 하나가 stat 에 실패해서 warning 발생, exit code 2.

황당한 건 이 이슈를 AWS CLI 메인테이너 본인 (jamesls) 이 직접 보고했다는 점이다. 자기들이 알고 있는 명백한 버그가 9년간 OPEN 상태였다.

이슈 댓글에 쌓인 사람들의 호소가 있다.

• kachkaev: Docker volume 백업 중 socket 때문에 sync 가 항상 non-zero. Ansible 자동화 안 됨. || true 같은 정신 나간 짓 필요.
• mcblair: Concourse CI 에서 exclude 로 다 빼고 include 로만 동기화하려 했는데 exit code 2 때문에 job 실패.
• TBeijen: s3 cp 도 같은 문제. workaround: /tmp 로 일단 복사.
• deweysasser: “더 나은 도구를 누가 새로 짤 때가 됐다.”

심지어 다운스트림 사고도 있었다. 2023년 DuckDuckGo PR #17 에서 CDN publish 가 깨졌을 때, 첫 의심 대상이 AWS CLI 의 알려진 버그 (#1117 외 다수) 였다. 결국 자기 코드 오타였지만, AWS CLI 가 “사고 났을 때 일단 의심하는 대상” 으로 자리 잡았다는 증거.

왜 자동으로 잡히는가

#1138 fix 의 핵심은 walker 가 디렉터리에 들어가기 전에 필터를 묻는다는 것. 이게 #1117 의 트리거 조건을 그대로 차단한다.

[기존 흐름 — #1117 발생]                  [fix 후 — #1117 안 일어남]

list_files
  ↓ listdir(./demo)
  ↓ 발견: bad (FIFO)
  ↓ stat(./demo/bad)                       should_ignore_file
  ↓ → OSError (FIFO 못 stat)                 ↓ Filter.call([probe])
  ↓                                          ↓ → exclude (* 매치)
triggers_warning(./demo/bad)                 ↓ return True
  ↓ warning queue 에 push                  
  ↓ rc=2                                   (queue 비어 있음 → rc=0)

should_ignore_file 의 사전 필터가 triggers_warning 전에 실행된다 → excluded 파일이 stat 시도 단계까지 안 감 → warning queue 비어 있음 → rc=0.

표면적으론 #1138 (성능) 과 #1117 (rc=2) 은 다른 두 이슈였지만, 같은 뿌리에서 나왔다. walker 가 필터를 알게 만들면 두 문제가 동시에 사라진다. 9년간 누구도 이걸 한 PR 로 묶어내지 못했다.

PR #2105 가 추가한 file_filter probe 가 사실은 #1117 을 잡는 메커니즘이었다. 하지만 그 PR 은 머지가 안 됐고, 거기 들어갔던 아이디어는 그대로 묻혔다.

닫히는 두 이슈

이번 fix 가 닫는 이슈는 두 개다.

#1138 을 풀려고 만든 알고리즘이 #1117 까지 닫는 모양이 됐다. 두 PR 이 따로 가는 게 아니라, 같은 한 PR 의 두 결과인 셈이다.

Part 5. HEAD overhead 정밀 측정

엣지 케이스 표에서 일부 시나리오가 0.9× (HEAD 가 더 느림). 측정 노이즈인지 진짜 cost 인지 확인하기 위해 3회씩 재측정.

A6 — 필터 없음 (3 runs)

→ 노이즈 범위. filter 가 None 이면 추가 오버헤드 없음.

A7 — 매치 안 되는 패턴 (3 runs)

→ 일관된 패턴, 진짜 cost.

Cost 의 출처

should_ignore_file 가 HEAD 에서 파일 한 개마다 추가 실행:

if relevant_patterns:
    if not os.path.exists(path):           # ① 추가 stat 1회
        return self.triggers_warning(path)
    if os.path.isdir(path):                # ② 추가 stat 1회
        if self.file_filter.can_skip_directory(...):
            return True
    else:
        probe = FileInfo(src=path, ...)    # ③ FileInfo 생성
        if not list(self.file_filter.call([probe])):  # ④ fnmatch P회 루프
            return True

산수:

• 파일당 cost ≈ stat syscall 2회 (~4–6μs on macOS APFS warm cache) + FileInfo 생성 + fnmatch P회 + 제너레이터 setup ≈ ~8μs/파일.
• 1M 파일 × 8μs = 8s. 실측 8.04s 와 일치.

Cost 가 존재하는 이유 — #1117 fix 와 직결

--exclude '*.tmp' 같은 basename-only 패턴은 디렉터리 prune 으로 못 잡는다. 이런 케이스에서도 excluded 인 파일 (FIFO/socket/권한0) 이 stat 시도 → warning 발생하는 걸 막으려면 stat 시도 전에 filter 매치를 미리 확인 해야 한다. 그게 per-file probe 의 정체.

PRE 는 이 단계가 없으니 빠름 — 대신 #1117 같은 케이스에서 spurious warning + rc=2 그대로 발생.

기대 효과가 손해를 압도한다. trade-off 합당하다.

Part 6. yield 동일성 — count 함정 봉쇄

여기까지의 표는 PRE_yielded == HEAD_yielded 를 카운트만 비교했다. count 가 같아도 실제 파일 set 이 다른 함정 가능성을 닫기 위해 path set 비교를 추가로 했다.

pre  = frozenset(fs.src for fs in flt.call(fg_pre.call(files)))
head = frozenset(fs.src for fs in flt.call(fg_head.call(files)))
assert pre == head

yield set 비교 (총 1,100초 소요)

15/15 set-equal:

→ count 일치 + 실제 path set 도 정확히 일치. fix 가 어떤 파일도 추가하거나 제거하지 않음.

yield order 보존

sync 의 Comparator 는 src/dst 양쪽 walker 출력을 lex 순서로 동시 매칭 하므로, set 이 같아도 순서가 달라지면 매칭이 깨질 수 있다. order 보존 별도 검증:

fixture/ 트리:
  a.txt, m.txt, z.txt   (root level)
  aa/{1.txt, 2.txt}, mm/{1.txt, 2.txt}, zz/{1.txt, 2.txt}
  excluded/{x.txt, y.txt}   (제외 대상)
필터: --exclude excluded/*

→ 완전 동일 (DFS sorted). HEAD 가 excluded/ 를 prune 했지만 나머지 가지의 순회 순서엔 영향 없음.

Part 7. Danger zone — 23개 직접 노린 케이스

count 일치 + set 일치 + order 일치까지 통과했지만, 이론적으로 yield 가 갈라질 수 있는 영역을 직접 노리는 타겟 테스트도 추가했다.

Zone A: char class escape (5/5)

fnmatch 의 [*] 는 literal * 한 글자 매칭. 우리 algo 의 _literal_prefix 는 [ 에서 자르므로 과보수적 해석. 잘못 prune 안 함을 확인.

Zone B: Windows case insensitivity (5/5)

fnmatch.fnmatch 는 Windows 에서 os.path.normcase 로 lowercase 매칭. macOS 환경에서 mock 으로 시뮬:

mock.patch('awscli.customizations.s3.filters.os.path.normcase',
           side_effect=lambda p: p.lower().replace('/', os.sep))
mock.patch('awscli.customizations.s3.filters.fnmatch.fnmatch',
           side_effect=lambda n, p: real_fnmatch(n.lower(), p.lower()))

→ can_skip_directory 의 os.path.normcase 적용이 Filter._match_pattern 의 fnmatch 정규화와 정확히 일치.

Zone D: 단일 파일 dir_op=False (5/5)

aws s3 cp /file.txt s3://b/ 와 같은 경로. walker 가 list_files 의 if not dir_op: 분기를 타며 다른 코드 경로:

Zone E: symlinks (4/4)

follow=False 분기는 should_ignore_file 첫 줄에서 symlink 발견 시 즉시 True 반환 — file_filter 분기 진입 전이라 양쪽 동일.

Zone F: dst_patterns 측 rgen (3/3)

sync --delete 의 dst-walker (is_dst_walker=True). Filter 가 src/dst 두 rootdir 로 두 패턴 세트를 보유. rgen 은 dst 측을 walk 하므로 dst_patterns 로 prune 판정해야 정합:

→ rgen 의 is_dst_walker=True 와 Filter.can_skip_directory(use_dst_patterns=True) 가 정확히 동기화됨.

Part 8. 종합 — 회귀 가능성 평가

이론적으로 yield 가 갈라질 가능성은 두 곳 중 하나에 버그가 존재해야 한다:

1. _pattern_can_match_under — False 반환을 매칭 가능한 케이스에서 잘못 한 경우 (over-prune)
2. _pattern_matches_all_under — True 반환을 모든 자손 매칭 안 하는 케이스에서 잘못 한 경우 (over-prune)

23 + 15 케이스는 두 함수가 영향을 미칠 수 있는 모든 입력 형태를 (char class, glob 메타, case, separator, multi-pattern, include override, dst rooting) 직접 노렸다. 만약 잘못 prune 하는 버그가 있다면 이 중 하나에서 발견됐어야 한다. 모두 통과 → 현재 발견된 yield 분기 케이스 0.

향후 더 강한 보장을 원하면 랜덤 fuzz (랜덤 패턴 + 랜덤 트리 ×N회 비교) 가 다음 단계다. 단 23 카테고리 + 1M 실측이 통과한 시점에서 ROI 는 낮다.

Part 9. 최종 평가

PR #5425 가 4년에 걸쳐 풀려고 했던 design 난점이 보수적 prune 분석의 자연스러운 동작으로 통과한다. --exclude '*' --include '*.py' 의 silent 회귀가 step 1 에서 자동으로 잡힌다. --exclude 'cache/*' --include 'cache/keep.txt' 같은 override 도 마찬가지.

시간 / 공간 복잡도

점근적으로: prune 효과가 없을 때도 PRE 와 같은 차수, prune 이 효과를 발휘하면 N → N_v 만큼 줄어든다. N_v / N 비율이 곧 실측 speedup 의 상한.

공간 복잡도는 양쪽 모두 O(H + K + P × L). fix 가 차수를 바꾸지 않는다 — generator chain 그대로 유지.

참고: PR #5425 (bugfood) 가 시도한 “자동 부모 include 패턴 생성” 방식이었다면 패턴 리스트 자체가 사용자 입력 깊이만큼 커져서 공간 복잡도가 늘었을 텐데, 이번 fix 는 패턴 변형 없이 정적 prefix 비교만 쓰므로 깔끔하다.

느낀 점

count 비교는 약하다. 처음엔 “PRE 와 HEAD 가 같은 수의 파일을 yield 하면 OK” 로 만족할 뻔했다. count 가 같아도 어떤 파일 인지가 다를 수 있다. set 비교를 추가했더니 또 다른 함정이 보였다 — sync 의 Comparator 는 순서 에 의존한다. order 비교까지 했다. 회귀 0 이 알고리즘 차원에서 증명돼 있어도, 실측 검증을 충분히 강하게 하지 않으면 그 증명을 신뢰할 수 없다.

per-file probe 의 +12% 는 trade-off 가 아니라 #1117 의 가격이다. A7 (매치 안 되는 패턴) 에서 HEAD 가 PRE 보다 12% 느린 게 처음엔 손해처럼 보였다. 그런데 그 12% 가 정확히 #1117 fix 비용이다. stat 전에 필터를 미리 확인해야 FIFO/socket/권한0 파일이 warning queue 에 안 들어간다. 9년 된 rc=2 버그를 잡으려면 받아들여야 하는 가격.

기여를 미루는 것. 솔직하게 적자면, 이 PR 은 아직 머지되지 않았다. AWS CLI 의 외부 PR 리뷰 사이클 — bugfood 의 1.5년 무대응을 보면 알 수 있는 — 이 빠르지 않다. 알고리즘 차원에서 회귀 0 을 증명하고, 100만 파일에서 검증하고, danger zone 까지 노린 테스트를 갖춰도, 결국 메인테이너가 시간을 내 줘야 한다. 어쩌면 이 PR 도 묻힐 수 있다. 그래도 9년치 사용자 고통을 한 줄도 못 줄여 놓고 묻히는 것 보다는, 코드를 끝까지 가지고 가서 시간이 지나도 누군가 발견할 수 있는 형태로 두는 게 낫다.

Issues: aws/aws-cli#1138, aws/aws-cli#1117 Branch: minjcho/aws-cli/tree/fix-s3-filter-prune-v2 PR #5425 결정적 리뷰 코멘트: discussion_r883991435